本節ではMPCパラメータの計算を行い、MPCパラメータファイルを作成できるようにします。
"main.c"を修正します。

• MPC情報の計算方法

  ソースコードを修正する前にMPC情報の計算方法について説明します。
  浅い探索による評価値vと深い探索による評価値Vの間の関係として以下を仮定することは既に述べました。
  

  V = v + b + e
  

  この式を変形すると以下のようになります。
  

  b + e = V - v
  

  eは平均０、標準偏差σの正規分布に従うので、左辺は平均b、標準偏差σの正規分布に従います。
  すると、右辺のV - vも平均b、標準偏差σの正規分布に従うことになります。
  このことから、V - vの平均をb、標準偏差をσとすればよいことがわかります。
  

• 定数の定義

  最初に必要な定数を定義します。
  

  #define MPC_NUM 12
  #define MPC_FILE "mpc.dat"
  #define MPC_LEARN_FILE "mpc_learn.dat"
  

  最初のMPC_NUMはMPC情報の数です。
  MPCを使用する探索手数の最小値はMPC_DEPTH_MINなので、探索手数がMPC_DEPTH_MIN以上(MPC_DEPTH_MIN + MPC_NUM)未満の場合にMPCを使用することになります。
  次のMPC_FILEはMPCパラメータを格納するファイルです。
  次のMPC_LEARN_FILEは学習時に使用するMPCパラメータファイルです。
  学習時にはMPCを使用しないようにします。
  そこでMPC情報を含まないMPCパラメータファイルを作成しておきます。
  

• MPCパラメータの保存

  MPCパラメータの保存処理を記述します。
  save_mpc()にMPC情報の個数と、MPCInfo構造体の配列を渡すとファイルに保存を行ないます。
  

  static int write_mpc(FILE *fp, int in_num, const MPCInfo *in_info)
  {
  	if (fwrite(&in_num, sizeof(int), 1, fp) < 1) {
  		return 0;
  	}
  	if (fwrite(in_info, sizeof(MPCInfo), in_num, fp) < (size_t)in_num) {
  		return 0;
  	}
  	return 1;
  }
  
  static int save_mpc(int in_num, const MPCInfo *in_info)
  {
  	FILE *fp;
  
  	fp = fopen(MPC_FILE, "wb");
  	if (!fp) {
  		return 0;
  	}
  	if (!write_mpc(fp, in_num, in_info)) {
  		return 0;
  	}
  	fclose(fp);
  	return 1;
  }
  

• MPC情報の計算

  それではMPC情報の計算を行ないます。
  

  static void calc_mpc(Board *board, Com *com)
  {
  	MPCInfo info[MPC_NUM];
  	int depth[] = {1, 2, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6};
  	int i, j, k;
  	int num, value_low, value_high;
  	int color;
  	double mean, var;
  	char transcript[][TRANSCRIPT_SIZE] = {
  		"c4c3c2d6e6f6f5e3f4f3g5c6d3c5e2b4f7f2d2b3g4g6f1h5e7h3d7g3b5d8f8c8e8g8a4b6a7a5a6c7h4d1h6a3a2b7e1g1h2h7h8g7g2h1b8a8a1b1b2c1",
  		"e6d6c6f4g3e7f6d7d8f5e8f3g4g5h4f8g8f7c7h3g6h5h6h7e3c5f2b6c3c4b4b5a4d3b3a5h2h1g2e1c2e2a6b8c8h8g7b7a8a7d1d2c1g1f1b2a3a1b1a2",
  		"f5d6c3g5g6f3f4e3d3c4h5f6g3f2e6e7c6f7c5g4h4h3h2b5d2b4e2c1d1f1c2e1d7b3a5a6a4h7a7c8a3b2h6h1a1g2g1a2b1b6d8e8f8a8b7c7b8g7g8h8",
  		"e6f4c3c4d3c2f3d6f5e3e2f1c5c6d7f2d2e1c1g3b1g4g5c7b4d1g1b3b6f6e7b5g6d8h5e8a6f7a5a3a4a7h4a2g7h3f8h6h7h8g8b7a8c8a1b2b8g2h2",
  		"e6d6c5b4c6e7b5f6e8b6d7f4g6f5c4c7c8f7g5d8f8g4a3h5c3e3d3h6e2f2a4a5a6e1f1g1f3g3g7d1h3d2h4h8c2c1b3g8b1a1g2a2b2h2b7b8h1a7a8h7",
  		"c4e3f5c6e2f3d3d2c3f4f2b4c5g4c1b6b3e6f6c2d6a3b5a4b1g3c7g5g6f7e7h5b2a1a5e8h3b8a6d7h4f1d1h2b7e1h7a7h6h8g7g2c8d8a8g8h1g1f8a2",
  		"c4e3f2c3f3c5b4d3e2d2c1f4b3e1f1d1c2b5f5a5a4a3f6e6e7g3g4g2d6c6b6d7a6f8a2b2a1b1c8c7b8h4h5h6b7g6g5f7h1g1h3h2h7a8a7d8g8e8g7h8",
  		"f5f4c3g6f3d3g4f2g3h4e6h5e3f6g5d6f1c5f7c4h6e7h3f8g7e2e1d2d1c2b3c1b4g1b6c6c7d7c8h8d8a5e8h7g8g2a4a6b7b5a7h2h1a3a2b2a1b1b8a8",
  		"c4c5f6f3d6f5c6c3e6b5d3b4g4e3f4c7f2d7e2g5c2h3b6c1g6a5d8d2c8g3d1b7b1f7e8e7b3f8h6b8a8a7h5h4h2g7h7b2g2h1g1e1f1a1a4h8g8a3a6a2",
  		"c4c3c2f4f6d6f3c5f5d3e3d2e6g4d7c6b4e7c7c8e2f2g3b5a6b3a3f1b6c1d8e8f8g8f7h4e1d1g2g6h5h6h3g5g1b8b1h1h2a1b2a2b7a8a7a5a4g7h8h7",
  		"f5f4f3g4h3f6g5e6e3g3c4f2g6e2f1c6h4c5e7c3d6d7c8f7c7d8e8g8f8b8b3b4e1g7d3d2a4g1h1b5a5h2b6h7g2a6d1c2h8b2a2a3a1h5a8b1h6b7a7c1",
  		"d3e3f2c5d6c2f3e2c3c6f5e6f6d2c4f4f1e1c1g1g5g6d1b1e7g3g4b5b3b4h3a3d7h6h5c7b6d8a5a4a6a7g2f8f7h1e8h2h4g7g8h8h7b7c8b8a8a2b2a1",
  		"c4c3e6f6f5d6c5e3d3c6f2d2c2c1d1f3f4e1e7g4g3e2h3g6g5f1h6f8d8g7f7e8d7c8c7g8h8b6b5a6a5b7b3a4b8b4a8a7b2h4a3a1h5h7g1h1h2a2b1g2",
  		"c4c3c2f4f5b2e3c5d3e2b3f2g3f6f3d6b6g4c6e6h4d2g5g6a1b4a4b5a5c7c1a3a2b1e1d1f1h5g2h3h2a7e7f7a6e8a8b7d8h1g1b8c8d7f8g7g8h8h7h6",
  		"e6f4e3d2g3g5g4f6d6d7c5f5c4f3d3c3c1c6e7c2b5f2b6c7e2b4a3d1f1b1h6d8f8h4b3e8c8h2g6h7h8f7h3h5e1b2a1a2g2a5a6h1a4g1g8g7b7b8a7a8",
  		"f5f4c3c6e3f6g3f3g4d3g5e6d6g6c5c4f7h4h3h5d7c7b4b5b3c2e7f2h6a5a3d8c8b8a4a2e2e1d1c1d2g2h1h2g1g8f8a6b7e8b6g7h8a8a7h7a1b2b1f1",
  		""
  	};
  
  	save_mpc(0, info);
  	Com_LoadMPCInfo(com, MPC_FILE);
  	for (i = 0; i < MPC_NUM; i++) {
  		num = 0;
  		mean = var = 0.0;
  		printf("MPC計算中 %d / %d\r", i, MPC_NUM);
  		for (j = 0; transcript[j][0] != '\0';j++) {
  			Board_Clear(board);
  			color = BLACK;
  			for (k = 0; transcript[j][k] != '\0' && transcript[j][k+1] != '\0'; k += 2) {
  				if (!Board_Flip(board, color, Board_Pos(tolower(transcript[j][k]) - 'a', transcript[j][k+1] - '1'))) {
  					break;
  				}
  				if (Board_CanPlay(board, color)) {
  					color = Board_OpponentColor(color);
  				}
  				if (k < 16) {
  					continue;
  				} else if (Board_CountDisks(board, EMPTY) <= i + MPC_NUM + 6) {
  					break;
  				}
  				Com_SetLevel(com, depth[i], 0, 0);
  				Com_NextMove(com, board, color, &value_low);
  				Com_SetLevel(com, i + MPC_DEPTH_MIN, 0, 0);
  				Com_NextMove(com, board, color, &value_high);
  				num++;
  				mean += (double)(value_high - value_low);
  				var += (double)(value_high - value_low) * (double)(value_high - value_low);
  			}
  		}
  		mean /= num;
  		var /= num;
  		info[i].Depth = depth[i];
  		info[i].Offset = (int)mean;
  		info[i].Deviation = (int)(1.4 * sqrt(var - mean * mean));
  		save_mpc(i + 1, info);
  		Com_LoadMPCInfo(com, MPC_FILE);
  	}
  	printf("計算完了しました                    \n");
  }
  

  少々長いですが、処理は単純です。
  棋譜に従って着手を行い、各局面で浅い探索の評価値と深い探索の評価値の差の平均と分散を計算しているだけです。
  平均は変数mean、分散は変数varに格納しています。
  

  配列depthは深い探索の手数と浅い探索の手数の関係を定義しています。
  この関係は以下の表のようになります。
  

  深い探索の手数	浅い探索の手数
  3	1
  4	2
  5	1
  6	2
  7	3
  8	4
  9	3
  10	4
  11	5
  12	6
  13	5
  14	6
  15	5
  16	6

  配列transcriptは、評価値のサンプルを採集するための棋譜を定義しています。
  序盤がランダムになるような棋譜を選びました。
  各棋譜の局面毎に浅い探索、深い探索それぞれの評価値を計算します。
  

  MPCの計算は少ない手数から行い、ある手数のMPC情報を計算したら、一度保存しています。
  これは、あるノードでMPC探索を行なっている時に、さらにMPC探索が発生する可能性があるためです。
  例えば、探索の残りが８手のときには上の表から４手のMPC探索を行ないますが、４手の探索時には２手のMPC探索が発生します。
  この２重のMPC探索が発生することを考慮して手数毎にMPC情報を保存しているのです。
  

• MPC情報の読み込み

  残っているのは比較的細かい修正です。
  まず、対局時と学習時にMPCパラメータファイルを読み込むようにします。
  

  static void play(Board *board, Com *com)
  
  	（中略）
  
  	Com_SetOpening(com, 1);
  	Com_LoadMPCInfo(com, MPC_FILE);
  
  	（中略）
  
  }
  
  static void learn(Board *board, Evaluator *evaluator, Com *com)
  {
  	char buffer[BUFFER_SIZE];
  	int history_color[BOARD_SIZE * BOARD_SIZE];
  	int i, j, move, num, turn, value;
  	int color;
  	int result;
  
  	printf("対戦回数を入力してください\n");
  	get_stream(buffer, BUFFER_SIZE, stdin);
  	num = atoi(buffer);
  
  	Com_SetLevel(com, 4, 12, 12);
  	Com_SetOpening(com, 0);
  	Com_LoadMPCInfo(com, MPC_LEARN_FILE);
  
  	（中略）
  
  }
  

• main関数の修正

  次にmain()を修正します。
  MPC計算モードを追加します。
  

  int main(int argc, char **argv)
  {
  	MainParam param;
  	char buffer[BUFFER_SIZE];
  
  	srand((unsigned)time(NULL));
  	if (!main_param_initialize(&param)) {
  		printf("初期化に失敗しました\n");
  		return 0;
  	}
  
  	while (1) {
  		printf("モードを選択してください (1:対戦 2:学習 3:定石登録 4:MPC計算 q:終了)\n");
  		get_stream(buffer, BUFFER_SIZE, stdin);
  		if (!strcmp(buffer, "1")) {
  			play(param.Board, param.Com);
  		} else if (!strcmp(buffer, "2")) {
  			learn(param.Board, param.Evaluator, param.Com);
  		} else if (!strcmp(buffer, "3")) {
  			opening_initialize(param.Board, param.Opening);
  		} else if (!strcmp(buffer, "4")) {
  			calc_mpc(param.Board, param.Com);
  		} else if (!strcmp(buffer, "q")) {
  			break;
  		}
  	}
  
  	main_param_finalize(&param);
  
  	return 0;
  }
  

• 導入結果

  それではMPCの計算を行なってみましょう。
  環境にもよりますが計算には数十分から数時間かかります。
  

  単純な前向き枝刈り導入時と同様に、MPCありプログラムとMPCなしプログラムとで対局を行ないました。
  結果は以下のようになりました。
  

  中盤手数 +0

  中盤手数	勝率 ( % )	ノード数比	思考時間比
  4	51	0.997	0.931
  6	43	0.569	0.446
  8	35	0.277	0.188
  10	29	0.130	0.0867

  中盤手数 +1

  中盤手数	勝率 ( % )	ノード数比	思考時間比
  4	73	2.92	2.48
  6	56	1.38	1.02
  8	46	0.618	0.442
  10	41	0.269	0.180

  中盤手数 +2

  中盤手数	勝率 ( % )	ノード数比	思考時間比
  4	86	5.49	4.32
  6	81	2.68	2.05
  8	65	1.19	0.847
  10	50	0.50	0.337

  中盤手数 +3

  中盤手数	勝率 ( % )	ノード数比	思考時間比
  4	94	14.4	11.5
  6	86	6.09	4.54
  8	71	2.60	1.84
  10	51	1.00	0.672

表の見方は単純な枝刈りの場合と同様です。
思考時間比が1.0未満でも65%の勝率だったり（中盤手数+2の８手読み）、 思考時間が３分の１で50%の勝率（中盤手数+2の10手読み）である等、MPCの導入の効果が現れています。
少々物足りない気もしますが、MPCは思考時間削減のための有効な手段といえます。