#define BOARD_SIZE (21*32)	// 672

#define BOARD_SIZE_HASH (19*19+1)	// +1 はパス

typedef struct child {
	int   iti;			// 手の場所
	int   games;		// この手を探索した回数
	float value;		// この手の評価値(+1 で勝ち、0 で負け)
} CHILD;

typedef struct hash_go {
	uint64 hashcode64;			// ハッシュコード
	int child_num;				// 子局面の数
	CHILD child[BOARD_SIZE_HASH];
	double value;		// 評価値
	int games_sum;		// この局面に来た回数(子局面の回数の合計)
	int best_move;		// この局面での最善手（位置） 
	int flag;			// 
	int col;			// 手番
} HASH_GO;



double go::uct_tree(int col)
{
	int loop;
	int create_new_node_limit = ban_size * ban_size;
	const int ILLEGAL_MOVE_POS = -1;

	if ( depth >= 2 && path[depth-1]==0 && path[depth-2]==0 ) {
		return evaluate_two_pass(col,1);
	}
	uct_nodes++;
	Lock(tree_lock);	// すぐさま、木構造全体をロック。彩ではハッシュ表に木構造を保存。

	HASH_GO *phg = HashGoRead();
	if ( phg->flag == 0 ) { PRT("no found hash, mc_go_use=%d,uct_nodes=%d,hashcode64=%I64x,root=%I64x\n",hash_go_use,uct_nodes,hashcode64,root_hashcode64); debug(); }

	// 乱数で、着手を決定
	int child_num = phg->child_num;
	if ( child_num == 0 ) { PRT("no legal move?\n"); debug(); return -MAX_VALUE; }

	// 上位 n手で枝刈を行う(progressive widening)
	int upper_num = (int) (log((phg->games_sum/40.0)) / log(1.4) + 2);	// 19路。9路でもこちらが好成績。
//	int upper_num = child_num;	// 枝刈なし
	if ( upper_num < 2 ) upper_num = 2;
	if ( upper_num > child_num ) upper_num = child_num;

select_again:

	int select = -1;
	double max_value = -10000;
	for (loop=0; loop<upper_num; loop++) {
		CHILD *pc  = &phg->child[loop];
		if ( pc->iti == ILLEGAL_MOVE_POS ) {
			upper_num++;
			if ( upper_num > child_num ) upper_num = child_num;
			continue;
		}
		double uct_value;
		if ( pc->games ) {
			const double factor = 1.0 / sqrt(5.0); // sqrt(2.0);	// 1.0 / sqrt(5.0);
			double uct = factor * sqrt( log((double)phg->games_sum) / pc->games );
			uct_value = pc->value + uct;
		} else {	// 未展開ノード
			uct_value = 10000 + rand_mc_max(100);
		}

//		PRT("%2d/%2d:%04x,%4d,v=%7.3f,uct_value=%10.3f,max_value=%10.3f\n",loop,upper_num,dsp(pc->iti), pc->games, pc->value, uct_value,max_value);
		if ( uct_value > max_value ) {
			max_value = uct_value;
			select = loop;
		}
	}
	if ( select < 0 ) { PRT("select move Err, upper_num=(%d/%d)\n",upper_num,child_num); debug(); }

	// 実際に着手
	TE *p_te = &te[0][depth];	// 一直線なので [depth][0]; でなくてもOK
	CHILD *pc = &phg->child[select];
	p_te->iti   = pc->iti;
	p_te->color = col;

	if ( add_stone(p_te) ) {	// 手を進める
		pc->iti = ILLEGAL_MOVE_POS;
		goto select_again;
	}

	update_prob_list_all(p_te->iti,col);	// この石を中心とした8箇所の3x3の範囲の確率を更新

	path[depth] = p_te->iti;	// 手順を（位置を）記憶
	depth++;
	if ( depth >= DEPTH_MAX_MC ) { PRT("depth over=%d\n",depth); debug(); }

	if ( pc->games >= create_new_node_limit ) {	// ある回数以上調べたらノードを作る。ノード作成が重いため。
		HASH_GO *phg2 = HashGoRead();
		if ( phg2->flag == 0 ) create_node(UN_COL(col));
	}

	double win = 0;
	if ( pc->games < create_new_node_limit || depth == (DEPTH_MAX_MC-1) ) {
		UnLock(tree_lock);	// モンテカルロシミュレーションのみを並列に実行
		win = -mc_one_simulation_start(UN_COL(col));	// 1 or 0
		Lock(tree_lock);
	} else {
		UnLock(tree_lock);
		win = -uct_tree(UN_COL(col));
		Lock(tree_lock);
	}
	float win_prob = (float)(pc->games * pc->value + win) / (pc->games + 1);
	pc->value = win_prob;	// この手の勝率（累計）
	pc->games++;			// この手を探索した回数
	phg->games_sum++;		// 全部の探索手の合計

	depth--;
	del_stone(p_te);		// 手を戻す

	UnLock(tree_lock);
	return win;			// 0か1か、のみを返す
}