本節では置換表を利用した探索を行います。
修正を行うファイルは"com.c"です。

• 置換表の追加

  Comクラスに置換表を追加します。
  最初にメンバ変数の追加します。
  

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

  次にComクラスを生成するときにHashクラスを生成するようにします。
  

  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->Hash = Hash_New(HASH_SIZE);
  	if (!self->Hash) {
  		return 0;
  	}
  	Hash_Clear(self->Hash);
  	self->UseOpening = 0;
  	self->MidDepth = 1;
  	self->WLDDepth = 1;
  	self->ExactDepth = 1;
  	self->Node = 0;
  	self->MPCInfoNum = 0;
  	self->MPCInfo = NULL;
  	return 1;
  }
  

  HADH_SIZEは以下のように定義しました。
  局面表の大きさは20bit（1048576局）になります。
  

  #define HASH_SIZE	20
  

• 置換表の初期化

  探索時に置換表の初期化を行っいます。
  ただし置換表そのものを初期化するのではなく、Hash_ClearInfo()を呼ぶだけにします。
  

  int Com_NextMove(Com *self, const Board *in_board, int in_color, int *out_value)
  {
  	int result;
  	int left;
  	int value;
  	int color;
  
  	Board_Copy(in_board, self->Board);
  	self->Node = 0;
  	left = Board_CountDisks(self->Board, EMPTY);
  	Com_MakeList(self);
  	Board_InitializePattern(self->Board);
  	Hash_ClearInfo(self->Hash);
  	value = Com_OpeningSearch(self, in_color, Board_OpponentColor(in_color), &result);
  	（中略）
  }
  

• 中盤探索

  中盤探索関数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;
  	HashValue hash_value;
  	HashInfo hash_info;
  
  	if (in_depth == 0) {
  		self->Node++;
  		return Evaluator_Value(self->Evaluator, self->Board);
  	}
  	if (in_depth > 2) {
  		Board_HashValue(self->Board, in_color, &hash_value);
  		if (Hash_Get(self->Hash, &hash_value, &hash_info)) {
  			if (hash_info.Depth >= in_depth) {
  				if (hash_info.Upper <= in_alpha) {
  					*out_move = hash_info.Move;
  					return in_alpha;
  				} else if (hash_info.Lower >= in_beta) {
  					*out_move = hash_info.Move;
  					return in_beta;
  				} else if (hash_info.Lower >= hash_info.Upper) {
  					*out_move = hash_info.Move;
  					return hash_info.Lower;
  				}
  				if (hash_info.Upper < in_beta) {
  					in_beta = hash_info.Upper;
  				}
  				if (hash_info.Lower > in_alpha) {
  					in_alpha = hash_info.Lower;
  				}
  			} else {
  				hash_info.Depth = in_depth;
  				hash_info.Lower = -MAX_VALUE;
  				hash_info.Upper = MAX_VALUE;
  			}
  		} else {
  			hash_info.Depth = in_depth;
  			hash_info.Lower = -MAX_VALUE;
  			hash_info.Upper = MAX_VALUE;
  		}
  	}
  	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;
  		}
  	}
  	*out_move = NOMOVE;
  	if (in_depth > 2) {
  		info_num = Com_Sort(self, in_color, info);
  		if (info_num > 0) {
  			*out_move = info[0].Move->Pos;
  			can_move = 1;
  		}
  		for (i = 0; i < info_num; i++) {
  			Board_FlipPattern(self->Board, in_color, info[i].Move->Pos);
  			RemoveList(info[i].Move);
  			value = -Com_MidSearch(self, in_depth - 1, -in_beta, -max, in_opponent, in_color, 0, &move);
  			Board_UnflipPattern(self->Board);
  			RecoverList(info[i].Move);
  			if (value > max) {
  				max = value;
  				*out_move = info[i].Move->Pos;
  				if (max >= in_beta) {
  					hash_info.Lower = max;
  					hash_info.Move = *out_move;
  					Hash_Set(self->Hash, &hash_value, &hash_info);
  					return in_beta;
  				}
  			}
  		}
  
  		if (*out_move != PASS) {
  			hash_info.Upper = max;
  			hash_info.Move = *out_move;
  			Hash_Set(self->Hash, &hash_value, &hash_info);
  		}
  	} else {
  	（中略）
  }
  

  探索深さが2より大きい場合にだけ置換表を利用するようにしました。
  最初に局面情報の取得を行います。
  局面情報の取得に成功し、かつ登録情報の探索手数が現在の探索手数以上のときに、以下の処理を行います。
  

  • 登録情報の上限がα値以下の場合にはα値を返して関数を終了する。
  • 登録情報の下限がβ値以上の場合にはβ値を返して関数を終了する。
  • 登録情報の上限が下限以上の場合には登録局面の評価値が確定しているので、その評価値を返して関数を終了する。
  • 登録情報の上限がβ値よりも小さい場合にはβ値を上限に設定する。
  • 登録情報の下限がα値よりも大きい場合にはα値を下限に設定する。

  また関数終了時には、局面情報を設定して置換表に登録を行います。
  

• 終盤探索

  終盤探索関数Com_EndSearch()でも置換表を参照するようにします。
  内容はCom_MidSearch()と同じなので、説明は割愛します。
  

  static int Com_EndSearch(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;
  	HashValue hash_value;
  	HashInfo hash_info;
  
  	if (in_depth == 1) {
  		self->Node++;
  		p = self->Moves->Next;
  		value = Board_CountFlips(self->Board, in_color, p->Pos);
  		max = Board_CountDisks(self->Board, in_color) - Board_CountDisks(self->Board, in_opponent);
  		if (value > 0) {
  			*out_move = p->Pos;
  			return max + value + value + 1;
  		}
  		value = Board_CountFlips(self->Board, in_opponent, self->Moves->Next->Pos);
  		if (value > 0) {
  			*out_move = PASS;
  			return max - value - value - 1;
  		}
  		*out_move = NOMOVE;
  		return max;
  	}
  	*out_move = NOMOVE;
  	if (in_depth > 8) {
  		Board_HashValue(self->Board, in_color, &hash_value);
  		if (Hash_Get(self->Hash, &hash_value, &hash_info)) {
  			if (hash_info.Depth >= in_depth) {
  				if (hash_info.Upper <= in_alpha) {
  					*out_move = hash_info.Move;
  					return in_alpha;
  				} else if (hash_info.Lower >= in_beta) {
  					*out_move = hash_info.Move;
  					return in_beta;
  				} else if (hash_info.Lower >= hash_info.Upper) {
  					*out_move = hash_info.Move;
  					return hash_info.Lower;
  				}
  				if (hash_info.Upper < in_beta) {
  					in_beta = hash_info.Upper;
  				}
  				if (hash_info.Lower > in_alpha) {
  					in_alpha = hash_info.Lower;
  				}
  			} else {
  				hash_info.Depth = in_depth;
  				hash_info.Lower = -MAX_VALUE;
  				hash_info.Upper = MAX_VALUE;
  			}
  		} else {
  			hash_info.Depth = in_depth;
  			hash_info.Lower = -MAX_VALUE;
  			hash_info.Upper = MAX_VALUE;
  		}
  		info_num = Com_Sort(self, in_color, info);
  		if (info_num > 0) {
  			*out_move = info[0].Move->Pos;
  			can_move = 1;
  		}
  		for (i = 0; i < info_num; i++) {
  			Board_FlipPattern(self->Board, in_color, info[i].Move->Pos);
  			RemoveList(info[i].Move);
  			value = -Com_EndSearch(self, in_depth - 1, -in_beta, -max, in_opponent, in_color, 0, &move);
  			Board_UnflipPattern(self->Board);
  			RecoverList(info[i].Move);
  			if (value > max) {
  				max = value;
  				*out_move = info[i].Move->Pos;
  				if (max >= in_beta) {
  					hash_info.Lower = max;
  					hash_info.Move = *out_move;
  					Hash_Set(self->Hash, &hash_value, &hash_info);
  					return in_beta;
  				}
  			}
  		}
  		if (*out_move != PASS && *out_move != NOMOVE) {
  			hash_info.Upper = max;
  			hash_info.Move = *out_move;
  			Hash_Set(self->Hash, &hash_value, &hash_info);
  		}
  	} else {
  	（中略）
  }
  

次節では、残りの関数の実装と置換表の効果の検証を行います。