コンピュータ囲碁の作成 (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の実装に進める。

#ソースコード

```cpp
#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++)　ランダム打ちの実装](http://qiita.com/simanezumi1989/items/a43bcd5b2f855cda8936)
[コンピュータ囲碁の作成 (C++)　Playerクラスの実装と速度計測](http://qiita.com/simanezumi1989/items/5c5bbbf42b7de84db170)
（python版）
[コンピュータ囲碁の作成](http://qiita.com/simanezumi1989/items/107ffa3960ba70d9fd15)
[コンピュータ囲碁の作成　ランダム打ちの実装](http://qiita.com/simanezumi1989/items/7fd716c8dd798e1e4d3f#comment-a94525946242e46da62f)
[コンピュータ囲碁の作成　ルールの実装](http://qiita.com/simanezumi1989/items/3ee9007cf1904f17850d)
[コンピュータ囲碁の作成　原始モンテカルロ囲碁](http://qiita.com/simanezumi1989/items/111a447832b43550a5cf)

#参考図書
<a  href="http://www.amazon.co.jp/gp/product/4320123271/ref=as_li_tf_tl?ie=UTF8&camp=247&creative=1211&creativeASIN=4320123271&linkCode=as2&tag=simanezumi104-22">コンピュータ囲碁 ―モンテカルロ法の理論と実践―</a><img src="http://ir-jp.amazon-adsystem.com/e/ir?t=simanezumi104-22&l=as2&o=9&a=4320123271" width="1" height="1" border="0" alt="" style="border:none !important; margin:0px !important;" />