Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
4
Help us understand the problem. What is going on with this article?
@simanezumi1989

コンピュータ囲碁の作成 (C++) Playerクラスの実装と速度計測

More than 3 years have passed since last update.

コンピュータ囲碁

・コンピュータ囲碁の作成メモ。
・pythonで実装していたが処理が遅かったので,アルゴリズムが悪いのか言語が悪いのかを調べるために,C++で作り直すことにしたメモ。
・今回はPlayerクラスを作り,ランダム打ちの時間計測までを行いました。

速度計測

10試合した結果

Time:1試合あたりの時間
1秒あたりのプレイアウト数(理想値は1000)

Time : 0.002298(sec)
435.161010(playout/sec)

Time : 0.002761(sec)
362.187613(playout/sec)

Time : 0.000829(sec)
1206.272618(playout/sec)

Time : 0.000916(sec)
1091.703057(playout/sec)

Time : 0.001035(sec)
966.183575(playout/sec)

Time : 0.001288(sec)
776.397516(playout/sec)

Time : 0.001360(sec)
735.294118(playout/sec)

Time : 0.001042(sec)
959.692898(playout/sec)

Time : 0.000857(sec)
1166.861144(playout/sec)

Time : 0.001107(sec)
903.342367(playout/sec)

平均

Time:0.0013493(sec)
860.3095916(playout/sec)

考察

・理想的な速度にはなっている。
・pythonは25(playout/sec)程度なので言語の違いがあったと言える。
・今回はランダム打ちのみなのでスコアの実装を行い原始モンテカルロ囲碁での速度はまだどれぐらいかはわからない。

ソースコード

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

using namespace std;
#define BOARD_SIZE 9
#define W_SIZE 11
// 石を打ったときの処理
#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;

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:
    int data[W_SIZE][W_SIZE];
public:
    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 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);


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

    point posi;
    Player(int color){
        this->color = color;
        un_color = 3 - this->color;
        //this->tact = tactics(strategy);
    }
    int play(Board *board){

        return SUCCESS;
    }
    // 相手の石を取る
    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);
        // 打つ前の4方向をしらべる
        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;
    }

    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);
            //printf("random_choice_select\n");
            // board->draw();
            if(result == SUCCESS){
                posi = position;
                return SUCCESS;
            }
            // printf("l=%d\n", l);
            spaces[n] = spaces[l-1];
            l -=1;
        }
        return PASS;
    }
};

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);
    // printf("count_joined_liberty END\n");
}
// 二次元配列を受け取り変更して返す
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){
    clock_t start = clock();
    srand((unsigned) time(NULL));
    // 碁盤の作成
    Board board;
    // プレイヤー
    Player black = Player(BLACK);
    Player white = Player(WHITE);
    Player player = black;
    // 先手
    int length = 0;
    int passed = 0;
    // 対局開始
    while(passed < 2){
        int result = player.random_choice(&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;
        }
    }
    clock_t end = clock();
    board.draw();
    printf("Time : %f(sec)\n", (double)(end-start)/CLOCKS_PER_SEC);
    printf("%f(playout/sec)\n", (double)CLOCKS_PER_SEC/(end-start));
    return 0;
}

github

関連記事

(C++)
コンピュータ囲碁の作成 (C++) ランダム打ちの実装
(python版)
コンピュータ囲碁の作成
コンピュータ囲碁の作成 ランダム打ちの実装
コンピュータ囲碁の作成 ルールの実装
コンピュータ囲碁の作成 原始モンテカルロ囲碁

参考図書

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

4
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
simanezumi1989
大学時代に微分方程式の定性的理論に関する研究が国際誌に掲載せれたことが自慢です。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
4
Help us understand the problem. What is going on with this article?