コンピュータ囲碁の作成 (C++) 原始モンテカルロ囲碁の実装

コンピュータ囲碁

・コンピュータ囲碁の作成メモ。
・今回は原始モンテカルロ囲碁の実装を行い速度計測をした。

速度計測

１手毎のプレイアウト回数，処理時間. プレイアウト/秒.

補足：プレイアウト = 現在の盤面からランダム打ちで終局まですすめること

playout：2430 回, time：3.56529sec. 681.571playout/sec. 
playout：2370 回, time：3.30962sec. 716.094playout/sec. 
playout：2310 回, time：3.27608sec. 705.111playout/sec. 
playout：2250 回, time：3.11644sec. 721.978playout/sec. 
playout：2190 回, time：3.04761sec. 718.596playout/sec. 
playout：2130 回, time：3.33368sec. 638.933playout/sec. 
playout：2070 回, time：3.03189sec. 682.743playout/sec. 
playout：2010 回, time：2.8284sec. 710.65playout/sec. 
playout：1950 回, time：2.75128sec. 708.761playout/sec. 
playout：1890 回, time：2.6032sec. 726.029playout/sec. 
playout：1830 回, time：2.70769sec. 675.854playout/sec. 
playout：1770 回, time：2.37165sec. 746.316playout/sec. 
playout：1710 回, time：2.18103sec. 784.032playout/sec. 
playout：1650 回, time：2.12766sec. 775.5playout/sec. 
playout：1590 回, time：2.25741sec. 704.348playout/sec. 
playout：1530 回, time：1.96828sec. 777.327playout/sec. 
playout：1470 回, time：1.96365sec. 748.605playout/sec. 
playout：1410 回, time：1.85945sec. 758.29playout/sec. 
playout：1350 回, time：1.77097sec. 762.292playout/sec. 
playout：1230 回, time：1.49595sec. 822.219playout/sec. 
playout：1170 回, time：1.54045sec. 759.517playout/sec. 
playout：1110 回, time：1.57594sec. 704.339playout/sec. 
playout：1050 回, time：1.50617sec. 697.134playout/sec. 
playout：990 回, time：1.39518sec. 709.587playout/sec. 
playout：930 回, time：1.51352sec. 614.463playout/sec. 
playout：870 回, time：1.0416sec. 835.249playout/sec. 
playout：810 回, time：1.03184sec. 785.008playout/sec. 
playout：660 回, time：0.794395sec. 830.821playout/sec. 
playout：600 回, time：0.728319sec. 823.815playout/sec. 
playout：540 回, time：0.515863sec. 1046.79playout/sec. 
playout：480 回, time：0.38962sec. 1231.97playout/sec. 
playout：420 回, time：0.3254sec. 1290.72playout/sec. 
playout：360 回, time：0.28399sec. 1267.65playout/sec. 
playout：360 回, time：0.254123sec. 1416.64playout/sec. 
playout：450 回, time：0.404765sec. 1111.76playout/sec. 
playout：390 回, time：0.341503sec. 1142.01playout/sec. 
playout：300 回, time：0.122305sec. 2452.88playout/sec. 
playout：210 回, time：0.07024sec. 2989.75playout/sec. 
playout：210 回, time：0.066703sec. 3148.28playout/sec. 
playout：90 回, time：0.018878sec. 4767.45playout/sec. 
playout：0 回, time：0.000102sec. 0playout/sec. 
終局

考察など

・スコア計算が入った分遅くなっていると考えられる。
・pythonの方で教えてもらった高速化を適用すれば理想値(1000playout/sec)に近ずくかもしれない。
・速度が上がったことでUCBの実装に進める。

ソースコード

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <iostream>
#include <iomanip>
#include <map>
#include <unistd.h> // usleep関数
#include <time.h>   // for clock()

using namespace std;
#define BOARD_SIZE 9
#define W_SIZE 11
#define KOMI  6.5
// 石を打ったときの処理
#define SUCCESS  0      // 打てる
#define KILL     1      // 自殺手
#define KO       2      // 劫
#define ME       3      // 眼
#define MISS     4      // すでに石がある
#define PASS     5      // パス
// 盤上の種類
#define SPACE 0
#define BLACK 1
#define WHITE 2
#define WALL  3
// 戦略
#define RANDOM 1
#define MONTE_CARLO 2
// 真偽値
#define FALSE 0
#define TRUE  1
// 座標
typedef struct{
    int y;
    int x;
} point;

typedef struct{
    int black;
    int white;
} score_t;

const char *visual[4] = {"・","🔴 ","⚪️ "};

void getNeighbors(point center, point *neighbors){
//  printf("getNeighbors\n");
    neighbors[0] = (point){center.y-1,center.x};
    neighbors[1] = (point){center.y+1,center.x};
    neighbors[2] = (point){center.y,center.x-1};
    neighbors[3] = (point){center.y,center.x+1};
}

class Board{
private:
public:
    int data[W_SIZE][W_SIZE];
    point ko;
    Board(){
        for(int y = 0; y<W_SIZE; y++){
            for (int x = 0; x<W_SIZE; x++)
            {
                this->data[y][x] = SPACE;           
            }
        }
        for(int i=0; i<W_SIZE; i++){
            this->data[0][i] = this->data[W_SIZE-1][i] = this->data[i][0] = this->data[i][W_SIZE-1] = WALL;
        }
        this->ko = (point){1000,1000};
    }
    void copy(Board *board){
        memcpy(board->data, this->data, sizeof(this->data));
        board->ko = ko;
    }
    // 石の設置と取得
    void set(point position, int stone){
//      printf("set\n");
        this->data[position.y][position.x] = stone;
    }
    int get(point position){
        return this->data[position.y][position.x];
    }
    // 取り除く
    void remove(point position){
//      printf("remove\n");
        set(position, SPACE);
    }

    // 碁盤描画
    void draw(void){
        printf("  ");
        for (int x = 1; x<W_SIZE-1; x++) printf("%d ", x);
        printf("\n");
        for (int y = 1; y<W_SIZE-1; y++){
            printf("%d ", y);
            for (int x = 1; x<W_SIZE-1; x++){
                printf("%s",visual[this->data[y][x]]);
            }
            printf("\n");
        }
    }

    vector<point> getSpaces(){
//      printf("getSpaces\n");
        vector<point> space_array;
        for(int y = 1; y<10;y++){
            for(int x = 1; x<10;x++){
                point position = (point){y,x};
                if(get(position) == SPACE){
                    space_array.push_back(position);
                }
            }
        }
        return space_array;
    }
};

void count_around(int checked[9][9], Board *board, point position, int color, int* joined, int* liberty);
void count_joined_liberty(Board *board, point position, int color, int* joined, int* liberty);

void getPoints(Board *board, double *count){
    int black_points = 0;
    int white_points = 0;
    for(int y=1; y<W_SIZE-1; y++){
        for(int x=1; x<W_SIZE-1; x++){
            int data = board->get((point){y,x});
            if(data == BLACK){
                black_points += 1;
            }
            else if(data == WHITE){
                white_points += 1;
            }
            else{
                int around[4] = {0,0,0,0}; // ４方向のSPACE,BLACK,WHITE,WALLの数
                point neighbors[4];
                getNeighbors((point){y,x}, neighbors);
                for(int i=0; i<4 ;i++){
                    around[board->get(neighbors[i])] += 1;
                }
                // 黒だけに囲まれていれば黒地
                if(around[BLACK] > 0 && around[WHITE] == 0){
                    black_points += 1;
                }
                // 白だけに囲まれていれば白地
                if(around[WHITE] > 0 && around[BLACK] == 0){
                    white_points += 1;
                }
            }
        }
    }
    count[0] = (double)black_points; // 黒石＋黒地
    count[1] = (double)white_points; // 白石＋白地
}

void scoring(Board *board, double *score){
    getPoints(board, score);
    score[0] -= KOMI;
}
void judge(double *score){
    printf("%s：%3.1f ",visual[BLACK],score[0]);
    printf("%s：%3.0f\n",visual[WHITE],score[1]);
    if(score[0]>score[1]){
        printf("黒の勝ち\n");
    }else{
        printf("白の勝ち\n");       
    }
}


class Player{
private:
public:
    int color;
    int un_color;
    int tact;

    point posi;
    Player(int color, int strategy){
        this->color = color;
        un_color = 3 - this->color;
        this->tact = strategy;
    }
    int play(Board *board){
        return tactics(board);
    }
    // 相手の石を取る
    void capture(Board *board, point position){
//      printf("capture\n");
        board->remove(position);
        point neighbors[4];
        getNeighbors(position,neighbors);
        for(int i=0; i<4; i++){
            point neighbor = neighbors[i];
            if(board->get(neighbor) == this->un_color){
                capture(board, neighbor);
            }
        }
    }
    int move(Board *board, point position){
//      printf("move\n");
        if (position.y == 0 && position.x == 0){
            return PASS;
        }
        // すでに石がある
        if(board->get(position) != SPACE){
//          printf("すでに石がある\n");
            return MISS;
        }
        // positionに対して四方向の [連石, 呼吸点, 色]を調べる
        int joineds[4] = {0,0,0,0};
        int libertys[4] = {0,0,0,0};
        int colors[4] = {0,0,0,0};

        int space = 0;
        int wall = 0;
        int mikata_safe = 0;
        int take_sum = 0;
        point ko = {0,0};
        point neighbors[4] = {0,0,0,0};
        getNeighbors(position,neighbors);
        // 打つ前の４方向をしらべる
        for(int i=0; i<4; i++){
            colors[i] = board->get(neighbors[i]);
            if (colors[i] == SPACE){
                space += 1;
                continue;
            }
            if (colors[i] == WALL){
                wall += 1;
                continue;
            }
            // 連石と呼吸点の数を数える
            count_joined_liberty(board, neighbors[i], colors[i], &joineds[i], &libertys[i]);
            if (colors[i] == this->un_color && libertys[i] == 1){
                take_sum += joineds[i];
                ko = neighbors[i];
            }
            if (colors[i] == this->color && libertys[i] >= 2){
                mikata_safe += 1;
            }
        }
        // ルール違反
        if (take_sum == 0 && space == 0 && mikata_safe == 0){
            return KILL;
        }
        if (position.y == board->ko.y && position.x == board->ko.x){
            return KO;
        }
        if(wall + mikata_safe == 4){
            return ME;
        }
        // 石を取る
        point neighbors2[4] = {0,0,0,0};
        getNeighbors(position,neighbors2);
        for (int i = 0; i < 4; ++i){
            if (colors[i] == this->un_color && libertys[i] == 1){
                capture(board, neighbors2[i]);
            }
        }
        // 石を打つ
        // printf("%s (%d,%d)\n", visual[this->color], position.y, position.x);
        board->set(position, this->color);
        int joined = 0;
        int liberty = 0;
        count_joined_liberty(board, position, this->color, &joined, &liberty);
//      printf("エラーチェック1\n");
        if (take_sum == 1 && joined == 1 && liberty == 1){
            board->ko = ko;
//          printf("エラーチェック2\n");
        }
        else{
//          printf("エラーチェック3\n");
            board->ko = (point){10000,10000};
        }
//      printf("エラーチェック4\n");
        return SUCCESS;
    }

    void playout(Board *board, double *score){
        Player player1 = Player(un_color, RANDOM);
        Player player2 = Player(color, RANDOM);
        Player player = player1;
        int passed = 0;

        while(passed<2){
            int result = player.play(board);
            if(result == SUCCESS){
                passed = 0;
            }
            else{
                passed += 1;
            }
            if(player.color==player1.color){
                player = player2;
            }
            else{
                player = player1;
            }
        }
        scoring(board, score);
    }

    int random_choice(Board *board){
//      printf("random_choice\n");
        vector<point> spaces = board->getSpaces();
        int l = spaces.size();
        while(l>0){
            int n = rand()%l;
            point position = spaces[n];
            int result = move(board, position);
            if(result == SUCCESS){
                posi = position;
                return SUCCESS;
            }
            // printf("l=%d\n", l);
            spaces[n] = spaces[l-1];
            l -=1;
        }
        return PASS;
    }

    int monte_carlo(Board *board){
        clock_t start = clock();

        const int TRY_GAMES = 30;
        int try_total = 0;
        int best_winner = -1;
        point best_position = {0,0};

        // すべての手対して１手打つ（盤面は崩れるのでコピー）
        Board thinking_board;
        Board thinking_board_next;
        vector<point> spaces = board->getSpaces();
        int l = spaces.size();
        for(int i=0; i<l; i++){
            point position = spaces[i];
            board->copy(&thinking_board);
            int result = this->move(&thinking_board, position);
            if(result != SUCCESS){
                continue;
            }
            int win_count = 0;
            for (int n=0; n<TRY_GAMES; n++){
                thinking_board.copy(&thinking_board_next);
                double score[2] = {0.0,0.0};
                playout(&thinking_board_next, score);
                if((score[0] > score[1] && this->color == BLACK)||(score[0] < score[1] && this->color == WHITE)){
                    win_count += 1;
                }
            }
            try_total += TRY_GAMES;

            if(win_count > best_winner){
                best_winner = win_count;
                best_position = position;
            }
        }
        printf("playout：%d 回, ", try_total);
        clock_t end = clock();
        double elap = (double)(end-start)/CLOCKS_PER_SEC;
        std::cout << "time：" << elap << "sec. " << (double)try_total/elap << "playout/sec. " << std::endl;
        // printf("%s (%d,%d)\n",visual[this->color], best_position.y,best_position.x);
        if(best_position.y==0 && best_position.x==0){
            return PASS;
        }
        return this->move(board, best_position);
    }

    int tactics(Board *board){
        if(this->tact==MONTE_CARLO){
            return monte_carlo(board);
        }
        else{
            return random_choice(board);
        }
    }
};

void count_around(int checked[11][11], Board *board, point position, int color, int* joined, int* liberty){
    int y = position.y;
    int x = position.x;
    // printf("count (%d,%d)\n", y, x); 
    checked[y][x] = TRUE;
    *joined +=1;
    // 周辺を調べる
    point neighbors[4] = {(point){y-1,x}, (point){y+1,x}, (point){y,x-1}, (point){y,x+1}};
    for(int i = 0; i<4; i++){
        point neighbor = neighbors[i];
        if(checked[neighbor.y][neighbor.x]==TRUE){
            continue;
        }
        int data = board->get(neighbor);
        if(data==SPACE){
            checked[neighbor.y][neighbor.x] = TRUE;
            *liberty += 1;
        }
        else if(data == color){
            // printf("count繰り返し\n");
            count_around(checked, board, neighbor, data, joined, liberty);
        }
    }
}
void count_joined_liberty(Board *board, point position, int color, int* joined, int* liberty){
    int checked[11][11] = {{FALSE}};
    count_around(checked, board, position, color, joined, liberty);
}
// 二次元配列を受け取り変更して返す
int(* double_array(int array[][9]))[9]{
    for(int i = 0; i<10; i++){
        for(int j = 0; j<10;j++){
            array[i][j] = 1;
        }
    }
    return array;
}


int main(void){
    srand((unsigned) time(NULL));
    // 碁盤の作成
    Board board;
    // プレイヤー
    Player black = Player(BLACK, MONTE_CARLO);
    Player white = Player(WHITE, RANDOM);
    Player player = black;
    // 先手
    int passed = 0;
    // 対局開始
    while(passed < 2){
        int result = player.play(&board);
        if(result==SUCCESS){
            // board.draw();
            // usleep(100000); // 1000000=1sec
        }
        // パス判定
        if (result==PASS){
            passed += 1;
        }
        else{
            passed = 0;
        }

        if(player.color == BLACK){
            player = white;
        }
        else{
            player = black;
        }
    }
    double score[2] = {0,0};
    scoring(&board, score);
    judge(score);
    clock_t end = clock();
    board.draw();
    return 0;
}

github

感想

速度が上がったのでUCBの実装にも取り掛かろうと思う。
コメント等，自分のアウトプットに反応してもらえて嬉しいです。いつもありがとうございます。

関連記事

（C++）
コンピュータ囲碁の作成 (C++)　ランダム打ちの実装
コンピュータ囲碁の作成 (C++)　Playerクラスの実装と速度計測
（python版）
コンピュータ囲碁の作成
コンピュータ囲碁の作成　ランダム打ちの実装
コンピュータ囲碁の作成　ルールの実装
コンピュータ囲碁の作成　原始モンテカルロ囲碁

参考図書

コンピュータ囲碁 ―モンテカルロ法の理論と実践―