本章では前向き枝刈りについて説明します。

• 枝刈り

  枝刈りとは、探索ノードを減らす手法を指します。
  枝刈りを行なってもMinMax法と同じ結果が得られる枝刈り手法を後向き枝刈り、 必ずしもMinMax法と同じ結果が得られない枝刈り手法を前向き枝刈りといいます。
  αβ法は、後向き枝刈りです。
  

  後向き枝刈りは、MinMax法と同じ結果が得られる代わりに減らせる探索ノード数が限定されます。
  前向き枝刈りは、後向き枝刈りよりも多くの探索ノード数を減らせる可能性がありますが、探索の精度が落ちます。
  

  前向き枝刈りの基本方針は、「そのノードの評価値がα以下またはβ以上になりそうだったら探索を打ち切る」というものです。
  「α値以下またはβ値以上になりそう」であることの判定方法はいくつかあります。
  本節では、以下のような単純なアルゴリズムによる枝刈りを実装してみます。
  

  • 探索の残り手数が一定以上のノードで、静的評価を行なう
  • 静的評価による評価値がα値−一定値以下の場合には、そのノードの評価値をα値として探索を打ち切る
  • 静的評価による評価値がβ値＋一定値以上の場合には、そのノードの評価値をβ値として探索を打ち切る

• 枝刈り基準の定義

  それでは実装を行ないます。
  修正するファイルは"com.c"です。
  

  最初に枝刈り基準の定義を行ないます。
  静的評価による評価値がα値−CUT_WIDTH以下またはβ値＋CUT_WIDTH以上の場合に探索を打ち切ります。
  ここではDISK_VALUEの10倍の値としていますが、明確な根拠があるわけではありません。
  適切な枝刈り基準の決め方については次節以降で説明します。
  

  #define CUT_WIDTH	(DISK_VALUE * 10)
  

• 枝刈り処理の実装

  次に中盤探索関数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)
  {
  
  	（中略）
  
  	if (in_depth > 2) {
  		info_num = Com_Sort(self, in_color, info);
  		if (info_num > 0) {
  			if (info[0].Value <= in_alpha - CUT_WIDTH) {
  				return in_alpha;
  			} else if (info[0].Value >= in_beta + CUT_WIDTH) {
  				return in_beta;
  			}
  			*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) {
  					return in_beta;
  				}
  			}
  		}
  	} else {
  
  	（中略）
  
  }
  

  inf[0].Valueがα値以下またはβ値以上になるかどうかを調べています。
  inf[0].Valueは一手読みによる評価値なので静的評価ではありませんが、特に問題ではありません。
  

• 導入結果

  前向き枝刈りを導入しないプログラム（以下枝刈りありプログラム）と導入したプログラム（以下枝刈りなしプログラム）とで対局を行ないました。
  結果は以下のようになりました。
  

  中盤手数 +0

  中盤手数	勝率 ( % )	ノード数比	思考時間比
  4	48	0.909	0.817
  6	34	0.548	0.529
  8	32	0.308	0.294
  10	32	0.165	0.152

  中盤手数 +1

  中盤手数	勝率 ( % )	ノード数比	思考時間比
  4	73	3.11	2.58
  6	64	1.56	1.39
  8	44	0.763	0.705
  10	37	0.391	0.358

  中盤手数 +2

  中盤手数	勝率 ( % )	ノード数比	思考時間比
  4	79	5.51	5.05
  6	67	2.96	2.83
  8	59	1.53	1.49
  10	40	0.795	0.741

  中盤手数 +3

  中盤手数	勝率 ( % )	ノード数比	思考時間比
  4	96	16.0	14.2
  6	85	7.68	7.42
  8	74	3.69	3.55
  10	55	1.78	1.68

  表の見方を説明します。
  

  • 中盤手数 +n
    枝刈りありプログラムが枝刈りなしプログラムより中盤でn手深く探索を行なっていることを意味します。
    終盤探索の手数は同じです。
    
  • 中盤手数
    枝刈りなしプログラムの中盤での探索手数です。
    
  • 勝率
    枝刈りありプログラムの勝率です。
    各組み合わせ毎に200局の対局を行ないました。
    
  • ノード数比
    中盤の探索ノード数の比です。
    ( 枝刈りありプログラムのノード数 ) / ( 枝刈りなしプログラムのノード数 )を意味しています。
    
  • 思考時間比
    中盤の思考時間の比です。
    ( 枝刈りありプログラムの思考時間 ) / ( 枝刈りなしプログラムの思考時間 )を意味しています。
    

  表を見ると、枝刈りありプログラムでは、枝刈りなしよりも思考時間が減少していることがわかります。
  このため同じ持ち時間であれば探索手数を伸ばすことができます。
  しかし、探索手数を伸ばしても勝率は上がっていません。
  思考時間比が1.0以下の場合は常に勝率が50%以下になっています。
  つまり前向き枝刈り導入を行なっても良い効果は得られていないことがわかります。
  

今回のような単純な枝刈り方法ではうまく機能しないという結果になりました。
次節では適切な前向き枝刈り方法を説明します。