αβ法では、評価値の高い（相手局面では評価値の低い）ノードから探索を行なうと探索ノード数を減らすことができます。
評価値の高いノードの探索を行うと、探索の下限が上昇します。
その結果、探索の上限と下限の幅が狭くなります。
探索の上限と下限の幅が狭い方が枝刈りが多く発生するので、探索ノードが減ることになります。

本節では、探索時に候補手に対して１手読みを行い、その評価値を基に候補手の並び替えを行ないます。
候補手の並び替えを行なうことで評価値の高そうなノードから探索を行なうことができます。

• 着手情報の定義

  まず着手箇所（実際に使用するのは候補手リストの要素）と評価値を格納するための構造体を定義します。
  

  typedef struct _MoveInfo MoveInfo;
  struct _MoveInfo
  {
  	MoveList *Move;
  	int Value;
  };
  

• 並び替え関数

  次に候補手の並び替えを行なう関数を実装します。
  

  static int Com_Sort(Com *self, int in_color, MoveInfo *out_info)
  {
  	int info_num = 0;
  	MoveList *p;
  	MoveInfo info_tmp, *best_info;
  	int i, j;
  
  	for (p = self->Moves->Next; p; p = p->Next) {
  		if (Board_Flip(self->Board, in_color, p->Pos)) {
  			out_info[info_num].Move = p;
  			out_info[info_num].Value = Evaluator_Value(self->Evaluator, self->Board);
  			info_num++;
  			Board_Unflip(self->Board);
  		}
  	}
  	if (in_color == WHITE) {
  		for (i = 0; i < info_num; i++) {
  			out_info[i].Value = -out_info[i].Value;
  		}
  	}
  	for (i = 0; i < info_num; i++) {
  		best_info = &out_info[i];
  		for (j = i + 1; j < info_num; j++) {
  			if (out_info[j].Value > best_info->Value) {
  				best_info = &out_info[j];
  			}
  		}
  		info_tmp = *best_info;
  		*best_info = out_info[i];
  		out_info[i] = info_tmp;
  	}
  	return info_num;
  }
  

  引数は以下の通りです。
  self : Comクラスへのポインタ
  in_color : 手番
  out_info : 並び替え結果を格納するMoveInfo構造体へのポインタ
  

  処理は３つに分かれており、それぞれ以下のようになっています。
  

  • 候補手リストから着手可能な要素を抜き出し、評価値づけを行なう
  • 白番であれば評価値に-1を掛ける
  • 評価値に基づいてMoveInfo構造体の並び替えを行なう

  ソート方法には選択ソートを使用しました。
  

• 探索処理への導入

  それでは候補手の並び替えを探索処理に導入します。
  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;
  
  	if (in_depth == 0) {
  		self->Node++;
  		return Evaluator_Value(self->Evaluator, self->Board);
  	}
  	*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_Flip(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_Unflip(self->Board);
  			RecoverList(info[i].Move);
  			if (value > max) {
  				max = value;
  				*out_move = info[i].Move->Pos;
  				if (max >= in_beta) {
  					return in_beta;
  				}
  			}
  		}
  	} else {
  		for (p = self->Moves->Next; p; p = p->Next) {
  			if (Board_Flip(self->Board, in_color, p->Pos)) {
  				RemoveList(p);
  				if (!can_move) {
  					*out_move = p->Pos;
  					can_move = 1;
  				}
  				value = -Com_MidSearch(self, in_depth - 1, -in_beta, -max, in_opponent, in_color, 0, &move);
  				Board_Unflip(self->Board);
  				RecoverList(p);
  				if (value > max) {
  					max = value;
  					*out_move = p->Pos;
  					if (max >= in_beta) {
  						return in_beta;
  					}
  				}
  			}
  		}
  	}
  	if (!can_move) {
  		if (in_pass) {
  			*out_move = NOMOVE;
  			self->Node++;
  			max = DISK_VALUE * (Board_CountDisks(self->Board, in_color) - Board_CountDisks(self->Board, in_opponent));
  		} else {
  			*out_move = PASS;
  			max = -Com_MidSearch(self, in_depth - 1, -in_beta, -max, in_opponent, in_color, 1, &move);
  		}
  	}
  	return max;
  }
  

  探索の残り手数が２手を超えていれば並び替えを行うようにしました。
  リーフ近くで並び替えをしてしまうと、並び替えの処理時間が長くなってしまいます。
  そのため比較的浅いノードでのみ並び替えを行なうようにします。
  並び替えを行なった後の処理は、並び替えを行なわない場合の処理と同様です。
  

  Com_EndSearch()では残り手数が８手を超えている場合に並び替えを行なうようにしました。
  Com_EndSearch()の修正はCom_MidSearch()とほぼ同じなので省略します。
  

• 導入結果

  それでは実際に動作させてみましょう。
  並び替えを行なう分１ノードあたりの処理時間が長くなってしまいました。
  しかし探索ノード数が大きく減っているために、全体としては高速になっているのがわかると思います。