#include "mcts.h"

int  m_komi = 7;
char check_base[(19+2)*(19+2)]; /* 各位置のチェック状態初期値 */
int  playout_hands = 19*19*2;   /* プレイアウト処理の最大手数 */
int  dir4[4] = {1,-1,999,-999}; /* 右左下上の隣接位置の４つの加算値 */
                                /* (999 と -999 はサイズ決定後に書替え) */
/* モンテカルロ木探索(MCTS)を用いて着手位置を決定する */
/*   引数:現手番の色,碁盤サイズ(9,13,19),現碁盤配置,現劫位置 */
/*   戻値:0=正常 -9=メモリ不足 */
__declspec(dllexport) int mcts(int* x, int* y, int* pos_array, int color_in, int size, int ko_x ,int ko_y, int playout, int komi)
{
	int color, ko_pos, in_ko_pos;
	int posl[(19+2)*(19+2)];
	int i, j, rtn;
	int playout_max, win_max;
	int best_pos;
	int rate_min, rate_max;
	uct_node *root;
	uct_node *que, *work;

	m_komi = komi;
	/* 出力位置の初期化 */
	*x = 0;
	*y = 0;
	/* 入力碁石の色変換 */
	if(color_in == 2) color = WHITE;
	else              color = color_in;
	/* 入力劫位置変換 */
	in_ko_pos = ko_y*(size+2) + ko_x%(size+2);
	ko_pos = in_ko_pos;
	/* プレイアウト処理の最大手数設定 */
	playout_hands = size * size * 2;
	/* 隣接位置情報設定 */
	dir4[2] = size + 2;
	dir4[3] = (-1) * size - 2;
	/* 各位置のチェック状態をチェック前として初期化 */
	memset(check_base, '\0', (size+2) * (size+2));
	/* 碁盤の外周(横方向の先頭と最終)をチェック済とする  */
	for(i = 0; i < (size+2); i++){
		check_base[i] = 1;
		check_base[i + (size+2) * (size+1)] = 1;
	}
	/* 碁盤の外周(縦方向の先頭と最終)をチェック済とする  */
	for(i = 1; i < (size+1); i++){
		check_base[(size+2) * i] = 1;
		check_base[size+1 + (size+2) * i] = 1;
	}
	/* 乱数シード値設定 */
	init_genrand((unsigned)time(NULL));
	/* ルートノード作成(ひとつ) */
	que = NULL;
	root = make_uct(&que, size);
	if(root == NULL) return -9; /* メモリ不足 */
	/* 子ノード作成(全着手可能な位置分) */
	if(expand_node(&que, root, size, pos_array, ko_pos) != 0){
		free(root);
		return -9; /* メモリ不足 */
	}
	/* プレイアウト数分UCT探索を繰り返す */
	for(i=0; i<playout ; i++){
		/* 盤上の現在の碁石の配置を作業用のエリアにコピー */
		memcpy(posl, pos_array, sizeof(posl[0])*(size+2)*(size+2));
		/* 子ノード(UCT)探索 */
		if((rtn = search_uct(&que, root, color, size, posl)) < 0){
			/* 置ける場所がないかメモリ不足なら確保済メモリを解放 */
			while(1){
				work = que->next;
				free(que);
				if(work == NULL) break;
				que = work;
			}
			if(rtn == -1) return  0; /* 置ける場所がない */
			else          return -9; /* メモリ不足 */
		}
	}
	/* 候補手を決定する */
	playout_max = -999;
	win_max = 0;
	rate_min = 1;
	rate_max = 0;
	best_pos = 0;
	/* １層目の子ノードを調べる */
	for(i = 0, j = 0; j < root->child_num; i++){
		if(root->child[i] == NULL) continue;
		j++;
		if(verify_legal(root->child[i]->pos, color, pos_array, &ko_pos, 0) == 0)
			/* 置けない石はないはずだが念のためチェックアウト */
			continue;
		if(color == BLACK){
			/* 現在の手番が黒石のときの処理 */
			/* プレイアウト回数の多いものを候補手とする */
			if(root->child[i]->playout_sum > playout_max){
				best_pos = root->child[i]->pos;
				playout_max = root->child[i]->playout_sum;
				win_max = root->child[i]->win_black;
			}
			/* プレイアウト回数が同じなら勝利数の多いものを候補手とする */
			else if(root->child[i]->playout_sum == playout_max){
				if(root->child[i]->win_black > win_max){
					best_pos = root->child[i]->pos;
					win_max = root->child[i]->win_black;
				}
			}
			/* 最小勝率 100% 未満はあるか? */
			if(rate_min == 1){
				if (root->child[i]->win_black < root->child[i]->playout_sum)
					rate_min = 0;
			}
			/* 最大勝率 0% 以外はあるか? */
			if(rate_max == 0){
				if(root->child[i]->win_black > 0)
					rate_max = 1;
			}
		}
		else{
			/* 現在の手番が白石のときの処理 */
			/* プレイアウト回数の多いものを候補手とする */
			if(root->child[i]->playout_sum > playout_max)
			{
				best_pos = root->child[i]->pos;
				playout_max = root->child[i]->playout_sum;
				win_max = root->child[i]->win_white;
			}
			/* プレイアウト回数が同じなら勝利数の多いものを候補手とする */
			else if(root->child[i]->playout_sum == playout_max){
				if(root->child[i]->win_white > win_max){
					best_pos = root->child[i]->pos;
					win_max = root->child[i]->win_white;
				}
			}
			/* 最小勝率 100% 未満はあるか? */
			if(rate_min == 1){
				if (root->child[i]->win_white < root->child[i]->playout_sum)
					rate_min = 0;
			}
			/* 最大勝率 0% 以外はあるか? */
			if (rate_max == 0){
				if (root->child[i]->win_white > 0)
					rate_max = 1;
			}
		}
	}
/*
if(best_pos == 0 || rate_min == 1 || rate_max == 0){
	for (i = 0, j = 0; j < root->child_num; i++){
		if (root->child[i] == NULL) continue;
		j++;
		printf("%d %d %d %d\n",
			root->child[i]->pos,
			root->child[i]->win_black,
			root->child[i]->win_white,
			root->child[i]->playout_sum);
	}
}
*/
	/* 確保済メモリを解放 */
	while(1){
		work = que->next;
		free(que);
		if(work == NULL) break;
		que = work;
	}
	/* 候補手(盤上の碁石の位置)を返却 */
	if(best_pos == 0){       /* 置ける場所がない */
		return 0;
//	}else if(rate_min == 1){ /* 勝利 */
//		*x = 0;
//		if(color == BLACK) *y = 1; /* 黒の勝ち */
//		else               *y = 2; /* 白の勝ち */
//	}else if(rate_max == 0){ /* 敗北 */
//		*x = 0;
//		if(color == BLACK) *y = 2; /* 白の勝ち */
//		else               *y = 1; /* 黒の勝ち */
	}else{
		*x = best_pos % (size+2);
		*y = best_pos / (size+2);
	}
	return 0;
}
/* ノード(UCT)領域確保 */
/*   引数:メモリ解放用の先頭キューノード,碁盤サイズ(9,13,19) */
/*   戻値:着手位置管理ノード(UCT) */
uct_node* make_uct(uct_node** que, int size)
{
	uct_node *uct, *work;

	/* メモリ確保 */
	if((uct = (uct_node *)
		malloc(sizeof(uct_node)
			+ sizeof(uct->child)*(size*size-1))) == NULL)
		return(NULL); /* メモリ不足 */
	/* メモリクリア */
	memset(uct, '\0', sizeof(uct_node)+sizeof(uct->child)*(size*size-1));
	/* メモリ解放用にノードキュー先頭にエンキュー */
	work = *que;
	*que = uct;
	uct->next = work;

	return(uct);
}
/* 探索子ノード(UCT)作成 */
/*   引数:メモリ解放用の先頭キューノード,親ノード,碁盤サイズ(9,13,19),現碁盤配置,現劫位置 */
/*   戻値:0(正常) -9(メモリ不足) */
int expand_node(uct_node** que, uct_node* parent, int size, int *pos_array, int ko_pos)
{
	int pos;

	for(pos=0; pos<size*size; pos++){
		/* 劫以外の空き位置(最大19×19=361)分、子ノードを作成 */
		if(pos_array[(pos+size)/size*(size+2)+1+pos%size] == SPACE
			&& (pos+size)/size*(size+2)+1+pos%size != ko_pos){
			parent->child[pos] = make_uct(que, size);
			if(parent->child[pos] == NULL) return(-9); /* メモリ不足 */
			/* 親ノードを更新 */
			parent->child_num++; /* 子ノード数 */
			/* 子ノードを更新 */
			parent->child[pos]->pos = (pos+size)/size*(size+2)+1+pos%size; /* 盤上の位置 */
			parent->child[pos]->parent = parent; /* 親ノードのアドレス */
		}
	}
	return(0);
}
/* 子ノード(UCT)探索 */
/*   引数:メモリ解放用の先頭キューノード,親ノード,現手番の色,碁盤サイズ(9,13,19),現碁盤配置 */
/*   戻値:0(正常) -1(置ける場所がない) -9(メモリ不足) */
int search_uct(uct_node** que, uct_node *node, int color, int size, int *posl)
{
	int i, j, ko_pos, select_i;
	int score;
	double ucb, max_ucb;
	uct_node *select_node;
	uct_node *parent_node;

	ko_pos = 0;
	select_node = NULL;
	/* 子ノード検索 */
	while(node->child_num > 0){
		max_ucb = -999;
		select_i = 0;
		select_node = NULL;
		/* 子ノード選択 */
		for(i=0, j=0; j<node->child_num; i++){
			if(node->child[i] == NULL) continue;
			j++;
			/* UCB(Upper Confidence Bound)判定 */
			if(node->child[i]->playout_sum == 0){
				/* プレイアウト未のノードを優先するよう適当な値を設定 */
				/*ucb = UCBMAX;*/
				ucb = genrand_int32();
			}else{
				/* プレイアウト済なら UCB を算出 */
				if (color == BLACK)
					ucb = (double)(node->child[i]->win_black)
							/ (double)(node->child[i]->playout_sum)
						+ C *
						sqrt(2.0 * (double)log(node->child[i]->parent->playout_sum)
										/ (double)node->child[i]->playout_sum);
				else
					ucb = (double)(node->child[i]->win_white)
							/ (double)(node->child[i]->playout_sum)
						+ C *
						sqrt(2.0 * (double)log(node->child[i]->parent->playout_sum)
										/ (double)node->child[i]->playout_sum);
			}
			/* UCB の大きいノードを候補手とする */
			if(ucb > max_ucb){
				max_ucb = ucb;
				select_i = i;
				select_node = node->child[i];
			}
		}
		/* 候補手がなければ検索は終了(置ける場所がない) */
		if(select_node == NULL) return(-1);
		/* 碁石が打てれば子ノード検索は終了 */
		if(verify_legal(select_node->pos, color, posl, &ko_pos, 1))
			break;
/*
printf("打てない(%d)\n",select_node->pos);
*/
		/* 碁石が打てない子ノードは選択候補からはずし再選択 */
		node->child_num--;
		node->child[select_i] = NULL;
	}
	/* 選択ノードがなければ検索は終了(置ける場所がない) */
	if(select_node == NULL) return(-1);
	/* 選択ノードのプレイアウト回数判定 */
	if(select_node->playout_sum < THRESHOLD){
		/* 選択ノードのプレイアウト回数が閾値未満はプレイアウト処理 */
		score = playout((-1)*color, size, posl, ko_pos);
		/* 選択ノードのプレイアウト回数更新 */
		select_node->playout_sum += 1;
		if(score > 0){
			/* 黒石の勝ちなら選択ノードの黒石勝利数更新 */
			select_node->win_black++;
			/* 親ノード更新(逆伝播) */
			while (select_node->parent != NULL){
				parent_node = select_node->parent;
				parent_node->win_black++;      /* 黒石勝利数 */
				parent_node->playout_sum += 1; /* プレイアウト回数 */
				select_node = parent_node;
			}
		}else{
			/* 白石の勝ちなら選択ノードの白石勝利数更新 */
			select_node->win_white++;
			/* 親ノード更新(逆伝播) */
			while (select_node->parent != NULL){
				parent_node = select_node->parent;
				parent_node->win_white++;      /* 白石勝利数 */
				parent_node->playout_sum += 1; /* プレイアウト回数 */
				select_node = parent_node;
			}
		}
		return(0);
	}else{
		/* 選択ノードのプレイアウト回数が閾値になったら */
		if(select_node->child_num == 0){
			/* 子ノード作成 */
			if(expand_node(que, select_node, size, posl, ko_pos) != 0)
				return(-9); /* メモリ不足 */
		}
		/* 子ノード(UCT)探索(再帰処理) */
		if(search_uct(que, select_node, (-1)*color, size, posl) == -9)
			return(-9); /* メモリ不足 */
	}
	return(0);
}
/* プレイアウト処理 */
/*   引数:現手番の色,碁盤サイズ(9,13,19),現碁盤配置,現劫位置 */
/*   戻値:黒の地の数 - コミ */
int playout(int color, int size, int *posl, int ko_pos)
{
	int  i, j, jp, jr, selected, rand_pos;
	int  win, color_tmp, pre_pos;
	int  possibles[19*19+1];
	int  stone_num[3], neighbor_num[5];
	int  score;

	win = 1;
	color_tmp = color;
	pre_pos = -1;
	/* 黒白交互にランダム着手 */
	for(i=0; i<playout_hands; i++){
		/* 盤上の現在の碁石の配置より着手位置候補を抽出 */
		memset(possibles, '\0', sizeof(possibles));
		for(j=size+3, jp=0; j<(size+2)*(size+1)-1; j++){
			if(posl[j] == SPACE && j != ko_pos){
				/* 劫でない空きなら候補位置に追加 */
				possibles[jp] = j;
				jp++;
			}
		}
		/* 石が打てるまで候補位置で着手をトライ */
		while(1){
			if(jp == 0){
				/* 着手位置候補がなければ着手断念 */
				selected = 0;
				break;
			}else{
				/* ランダムな着手位置候補に石を打つ */
				rand_pos = genrand_int32()%jp;
				selected = possibles[rand_pos];
				if(verify_legal(selected, color_tmp, posl, &ko_pos, 1))
				/* 問題なく石を打てたら次の打ち込みへ */
					break;
				/* 石を打てない位置なら着手位置候補から除外 */
				for(jr=rand_pos; jr+1<jp; jr++){
					possibles[jr] = possibles[jr+1];
					possibles[jr+1] = 0;
				}
				jp--;
			}
		}
		/* 自分と相手で続けて石を打てなくなったらプレイアウト終了 */
		if(selected == 0 && pre_pos == 0) break;
		pre_pos = selected;
		color_tmp *= (-1);
	}
	/* 勝敗判定(中国ルール) */
	score = 0;
	memset(stone_num, '\0', sizeof(stone_num));
	/* 盤上の全位置をチェックする */
	for(i=size+3; i<(size+2)*(size+1)-1; i++){
		/* 壁は無視 */
		if(posl[i] == SENTINEL) continue;
		/* 空き、黒石、白石の数を更新 */
		/* 石の生き死に判定ができないので死に石まで加算！ */
		/* 中国ルールで打てるかぎり打つという前提で黙認！ */
		stone_num[posl[i]+1]++;
		/* 空きの場合四方の石の数で判断 */
		if(posl[i] != SPACE) continue;
		memset(neighbor_num, '\0', sizeof(neighbor_num));
		/* 隣接する石の空き、黒石、白石、壁の数を更新 */
		for(j=0; j<4; j++) neighbor_num[posl[i + dir4[j]]+1]++;
		/* 黒石あり、白石なしならば得点加算 */
		if(neighbor_num[BLACK+1] > 0 && neighbor_num[WHITE+1] == 0)
			score++;
		/* 白石あり、黒石なしならば得点減算 */
		if(neighbor_num[WHITE+1] > 0 && neighbor_num[BLACK+1] == 0)
			score--;
	}
	/* 得点に(黒 - 白 - コミ)を加算 */
	score += (stone_num[BLACK+1] - stone_num[WHITE+1] - m_komi);
	/* 黒の勝敗を返却 */
	return(score);
}
/* 碁石の着手位置検証と更新 */
/*   引数:着手位置,現手番の色,現碁盤配置,現劫位置,更新要否 */
/*   戻値:黒石の地数 */
int verify_legal(int pos, int color, int *posl, int *ko_pos, int update)
{
	int  i, j, c_len, n_len, liberty;
	int  exist_space, is_ko, eye;
	short n[19*19];
	short captures[19*19];
	char check[(19+2)*(19+2)];

	/* 碁石の着手位置が空きなし、劫は着手不可で復帰 */
	if(posl[pos] != SPACE || pos == *ko_pos) return(0);
	/* 劫位置と取り込む石(アゲハマ)を初期化 */
	is_ko = 0;
	memset(captures, '\0', sizeof(captures));
	c_len = 0;
	eye = 0;
	/* 着手位置のダメの数を確認 */
	memcpy(check, check_base, sizeof(check));
	liberty = verify_liberty(pos, color, check, posl);
	/* 隣接４位置をチェック */
	for(i=0; i<4; i++){
		memcpy(check, check_base, sizeof(check));
		check[pos] = 1;
		exist_space = 0;
		/* 相手の石のみチェックする */
		if(posl[pos+dir4[i]] != (-1)*color){
			if(posl[pos+dir4[i]] != SPACE)
				eye++; /* 自分の石か壁 */
			continue;
		}
		/* 隣接する石の隣接状態をチェックする */
		n_len = verify_neighbor(pos+dir4[i], (-1)*color, check, posl, n);
		/* 隣接する石が単独で囲まれていたら劫の可能性ありとする */
		if(n_len == 1) is_ko = 1;
		/* 隣接する石が囲まれていたら */
		/*if(n_len >= 1) eye--;*/
		/* 隣接する石が囲まれていたら取り込む石(アゲハマ)に追加する */
		for(j=0; j<n_len; j++){
			captures[c_len] = n[j];
			c_len++;
		}
	}
	/* 着手位置が眼なら着手不可とする */
	if(eye == 4){
		for (i = 0; i<4; i++) {
			if (posl[pos + dir4[i]] != color) continue;
			memcpy(check, check_base, sizeof(check));
			check[pos] = 1;
			n_len = verify_neighbor(pos + dir4[i], color, check, posl, n);
			if (n_len > 0) break;
		}
		if (i >= 4) return(0);
		/*return(0);*/
	}
	/* 着手位置のダメの数がひとつ以下なら着手不可とする */
	if(liberty <= 1 && c_len == 0) return(0);
	if(update == 0) return(1);
	/* 盤上の現在の碁石の配置状態を更新 */
	posl[pos] = color;
	/* 隣接する取り込む石があれば */
	if(c_len > 0){
		/* 盤上の現在の碁石の配置状態を更新(取った位置を空きとする) */
		for(i=0; i<c_len; i++) posl[captures[i]] = SPACE;
		/* 着手位置に劫の可能性があれば着手位置のダメの数を確認 */
		if(is_ko){
			/* 着手位置のダメ検証 */
			memcpy(check, check_base, sizeof(check));
			liberty = verify_liberty(pos, color, check, posl);
			/* 着手位置のダメの数がひとつなら劫の位置を更新 */
			if(liberty == 1){
				*ko_pos = captures[0];
				return(1);
			}
		}
	}
	/* 着手成功 */
	*ko_pos = 0;
	return(1);
}
/* 隣接位置検証 */
/*   引数:着手位置,現手番の色,各位置のチェック状態,現碁盤配置,取り込む石のリスト */
/*   戻値:取り込む石の数 */
int verify_neighbor(int pos, int color, char *check, int *posl, short *captures)
{
	int   i, j, y, c_len, n_len, ni, found_new;
	short newly_found[19*19+1];
	short n[19*19+1];

	newly_found[0] = (short)pos;
	newly_found[1] = 0;
	captures[0] = (short)pos;
	c_len = 1;
	found_new = 1;
	/* まず入力の隣接位置から検証する */
	while(found_new){
		found_new = 0;
		n_len = 0;
		memset(n, '\0', sizeof(n));
		for(i=0; newly_found[i]!=0; i++){
			for(j=0; j<4; j++){
				y = newly_found[i] + dir4[j];
				if(check[y])
					/* 隣接する位置がチェック済なら次の隣接位置のチェックへ */
					continue;
				else if(posl[y] == SPACE)
					/* 隣接する位置がひとつでも空いていればチェック終了 */
					return(0);
				else if(posl[y] == color){
					/* 隣接する位置に相手の石があれば退避済か確認 */
					for(ni=0; ni<n_len; ni++)
						if(y == n[ni]) break;
					/* 退避済でなければ隣接位置リストに追加する */
					if(ni == n_len){
						n[ni] = (short)y;
						n_len++;
						found_new = 1;
					}
				}
			}
			/* チェックした位置をチェック済とする */
			check[newly_found[i]] = 1;
		}
		if(found_new){
			/* 次の隣接位置検証がまだ必要なら取り込み対象に加え */
			for(i=0; i<n_len; i++){
				captures[c_len] = n[i];
				c_len++;
			}
			/* 検証位置リストに隣接位置リストをコピーする */
			memcpy(newly_found, n, n_len*sizeof(n[0]));
			newly_found[n_len] = 0;
		}
	}
	/* 取り込む石の数を返却する */
	return(c_len);
}
/* ダメ検証 */
/*   引数:着手位置,現手番の色,各位置のチェック状態,現碁盤配置 */
/*   戻値:取り込む石の数 */
int verify_liberty(int pos, int color, char *check, int *posl)
{
	int   i, j, y, found_new;
	int   liberty_pos;
	short newly_found[19*19+1];
	short n[19*19+1];

	liberty_pos = 0;
	newly_found[0] = (short)pos;
	newly_found[1] = 0;
	found_new = 1;
	/* まず入力の自分の位置から検証する */
	while(found_new){
		found_new = 0;
		memset(n, '\0', sizeof(n));
		for(i=0; newly_found[i]!=0; i++){
			/* 自分の位置をチェック済とする */
			check[newly_found[i]] = 1;
			for(j=0; j<4; j++){
				y = newly_found[i] + dir4[j];
				/* 隣接する位置がチェック済なら次の隣接位置のチェックへ */
				if(check[y]) continue;
				/* 隣接する位置をチェック済とする */
				check[y] = 1;
				if(posl[y] == SPACE)
					/* 隣接する位置が空いていたらダメの数を更新する */
					liberty_pos++;
				else if(posl[y] == color){
					/* 自分の石なら隣接位置リストに追加する */
					n[found_new] = (short)y;
					found_new++;
				}
			}
		}
		if(found_new){
			/* 検証位置リストに隣接位置リストをコピーする */
			memcpy(newly_found, n, found_new*sizeof(n[0]));
			newly_found[found_new] = 0;
		}
	}
	/* ダメの数を返却する */
	return(liberty_pos);
}