#コンピュータ囲碁
・コンピュータ囲碁の作成メモ。
・今回は原始モンテカルロ囲碁の実装を行い速度計測をした。
#速度計測
##１手毎のプレイアウト回数，処理時間. プレイアウト/秒.
補足：プレイアウト = 現在の盤面からランダム打ちで終局まですすめること
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
https://github.com/Tsunehiko511/Cpp_Go
#感想
速度が上がったのでUCBの実装にも取り掛かろうと思う。
コメント等，自分のアウトプットに反応してもらえて嬉しいです。いつもありがとうございます。
#関連記事
（C++）
コンピュータ囲碁の作成 (C++) ランダム打ちの実装
コンピュータ囲碁の作成 (C++) Playerクラスの実装と速度計測
（python版）
コンピュータ囲碁の作成
コンピュータ囲碁の作成 ランダム打ちの実装
コンピュータ囲碁の作成 ルールの実装
コンピュータ囲碁の作成 原始モンテカルロ囲碁
#参考図書
コンピュータ囲碁 ―モンテカルロ法の理論と実践―
