本節ではMPCを使用した探索を行なえるようにします。
修正するファイルは"com.h"と"com.c"です。
なお、本節の修正の前に7.1節の修正は元に戻しておきます。

• MPCパラメータの定義

  最初にMPCに必要なパラメータを定義します。
  "com.h"を修正します。
  

  #define MPC_DEPTH_MIN 3
  typedef struct _MPCInfo MPCInfo;
  struct _MPCInfo
  {
  	int Depth;
  	int Offset;
  	int Deviation;
  };
  

  MPC_DEPTH_MINはMPCを行なう残り手数の最小値です。
  上の定義では、残り3手以上からMPCを使用します。
  

  MPCInfoは、MPCの情報を格納するための構造体です。
  MPCを行なう残り手数毎に、このMPC情報を用意します。
  Depthは浅い探索の手数です。
  Offsetは前節登場した以下の式のb、Deviationは同式のt * σに対応します。
  

  v + b + t * σ < α
  v + b - t * σ > β
  

• MPCパラメータの読み込み

  次にMPCパラメータを読み込む関数を定義します。
  

  int		Com_LoadMPCInfo(Com *self, const char *in_file_name);
  

  引数は以下の通りです。
  self : Comクラスへのポインタ
  in_file_name : MPCパラメータを格納したファイルの名前
  読み込みに成功したら1を返し、失敗したら0を返します。
  

• Comクラスの初期化処理

  最初にComクラスにMPC情報用変数を追加します。
  

  struct _Com
  {
  	Board *Board;
  	Evaluator *Evaluator;
  	Opening *Opening;
  	int UseOpening;
  	int MidDepth;
  	int WLDDepth;
  	int ExactDepth;
  	int Node;
  	MoveList Moves[BOARD_SIZE * BOARD_SIZE];
  	int MPCInfoNum;
  	MPCInfo *MPCInfo;
  };
  

  MPCInfoNumはMPC情報の個数、MPCInfoにはMPC情報の配列を格納します。
  MPC情報読み込み時に必要なメモリ領域を確保して、MPCInfoがそれを保持します。
  次にComクラス初期化時に追加した変数を初期化するようにします。
  またComクラス破棄時にMPCInfoが保持しているメモリ領域を開放します。
  

  static int Com_Initialize(Com *self, Evaluator *evaluator, Opening *opening)
  {
  	memset(self, 0, sizeof(Com));
  	self->Board = Board_New();
  	if (!self->Board) {
  		return 0;
  	}
  	self->Evaluator = evaluator;
  	if (!self->Evaluator) {
  		return 0;
  	}
  	self->Opening = opening;
  	if (!self->Opening) {
  		return 0;
  	}
  	self->UseOpening = 0;
  	self->MidDepth = 1;
  	self->WLDDepth = 1;
  	self->ExactDepth = 1;
  	self->Node = 0;
  	self->MPCInfoNum = 0;
  	self->MPCInfo = NULL;
  
  	return 1;
  }
  
  void Com_Delete(Com *self)
  {
  	if (self->MPCInfo) {
  		free(self->MPCInfo);
  	}
  	if (self->Board) {
  		Board_Delete(self->Board);
  	}
  	free(self);
  }
  

• MPCパラメータの読み込み

  次にMPCパラメータをファイルから読み込む関数、Com_LoadMPCInfo()を記述します。
  MPCパラメータファイルのフォーマットは以下の通りです。
  

  名前	意味	型	個数
  Num	MPC情報の個数	int	1
  Info	MPC情報	MPCInfo	Num

  MPC情報は、１個目が残り手数MPC_DEPTH_MINのMPC情報、２個目が残り手数MPC_DEPTH_MIN+1のMPC情報、、、
  となっています。
  

  int Com_LoadMPCInfo(Com *self, const char *in_file_name)
  {
  	FILE *fp;
  
  	fp = fopen(in_file_name, "rb");
  	if (!fp) {
  		return 0;
  	}
  	if (!Com_ReadMPCInfo(self, fp)) {
  		fclose(fp);
  		self->MPCInfoNum = 0;
  		if (self->MPCInfo) {
  			free(self->MPCInfo);
  			self->MPCInfo = NULL;
  		}
  		return 0;
  	}
  	fclose(fp);
  	return 1;
  }
  

  ファイルを開いてCom_ReadMPCInfo()を呼び出しています。
  ファイルからパラメータを読み込むのはCom_ReadMPCInfo()で行なっています。
  Com_ReadMPCInfo()の内容は以下の通りです。
  

  static int Com_ReadMPCInfo(Com *self, FILE *fp)
  {
  	MPCInfo *info;
  
  	if (fread(&self->MPCInfoNum, sizeof(int), 1, fp) < 1) {
  		return 0;
  	}
  	if (self->MPCInfoNum == 0) {
  		if (self->MPCInfo) {
  			free(self->MPCInfo);
  		}
  		self->MPCInfo = NULL;
  		return 1;
  	}
  	info = realloc(self->MPCInfo, sizeof(MPCInfo) * self->MPCInfoNum);
  	if (!info) {
  		return 0;
  	}
  	self->MPCInfo = info;
  	if (fread(self->MPCInfo, sizeof(MPCInfo), self->MPCInfoNum, fp) < (size_t)self->MPCInfoNum) {
  		return 0;
  	}
  	return 1;
  }
  

  最初にファイルからMPC情報の個数を読み込み、必要であればメモリ領域を確保します。
  その後最初の個数分だけMPC情報を読み込んでいます。
  

• 探索

  最後は中盤探索関数Com_MidSearch()です。
  

  static int Com_MidSearch(Com *self, int in_depth, int in_alpha, int in_beta, int in_color, int in_opponent, int in_pass, int *out_move)
  {
  	MoveList *p;
  	int value, max = in_alpha;
  	int can_move = 0;
  	int move;
  	MoveInfo info[BOARD_SIZE * BOARD_SIZE / 2];
  	int i, info_num;
  	MPCInfo *mpc_info;
  
  	if (in_depth == 0) {
  		self->Node++;
  		return Evaluator_Value(self->Evaluator, self->Board);
  	}
  	if (in_depth >= MPC_DEPTH_MIN && in_depth < MPC_DEPTH_MIN + self->MPCInfoNum) {
  		mpc_info = &self->MPCInfo[in_depth - MPC_DEPTH_MIN];
  		value = in_alpha - mpc_info->Deviation - mpc_info->Offset;
  		if (Com_MidSearch(self, mpc_info->Depth, value - 1, value, in_color, in_opponent, in_pass, out_move) < value) {
  			return in_alpha;
  		}
  		value = in_beta + mpc_info->Deviation - mpc_info->Offset;
  		if (Com_MidSearch(self, mpc_info->Depth, value, value + 1, in_color, in_opponent, in_pass, out_move) > value) {
  			return in_beta;
  		}
  	}
  
  	（中略）
  
  }
  

  MPCを使用する残り手数の場合には、浅い探索を行ないます。
  最初に ( α - b - t * σ - 1 ) から ( α - b - t * σ ) の範囲で探索を行ないます。
  次に ( β - b + t * σ ) から ( β - b + t * σ + 1 ) の範囲で探索を行ないます。
  この範囲で探索を行なう理由は以下の通りです。
  

  調べたい不等式が以下であることは既に説明しました。
  

  v + b + t * σ < α
  v + b - t * σ > β
  

  この式を、vについて解くと以下のようになります。
  

  v < α - b - t * σ
  v > β - b + t * σ
  

  この式を満たすかどうかを調べるために、上限と下限の幅を０（実装上は１）にしてWindow探索を行ないます。
  それが上記の範囲での探索です。
  上限と下限の幅を０にする探索をNull Window探索と呼びます。
  

これでMPCを使用した探索を行なえるようになりました。
しかし、MPCパラメータを計算していないので、実際に対局することはできません。 次節ではMPCパラメータの計算を行います。