Negascout

通常のアルファベータ法が返す値は探索窓の範囲内の値であるが、 子ノードを探索した結果が探索窓の範囲外だった場合、 探索窓の境界値ではなく実際に出現した子ノードの最大値を返すと探索量が減る事がある。 これは親ノードに伝わったときにβ値以上となってカットしたりα値を更新して探索窓を狭めたりできる可能性が高くなるためである。 このような性質を Fail-Soft と言い、 Null Window Search などの狭い探索窓による探索や置換表を使った探索をする場合にその効果がよく現れる。

以下に NegaScout の擬似コードを示す。

 function NegaScout( node, α, β, depth ) {
     if ( node.IsLeafNode || depth == 0 )
         return Evaluate( node ); /* 終端ノードなので現在のノードを評価する */
 
     node.ExpandChildNode(); /* 手を列挙 */
     node.MoveOrdering(); /* 手の並べ替え */
 
     child = node.GetNextChild(); 
     max = v = -NegaScout ( child, -β, -α, depth - 1 ); /* 最善候補を通常の窓で探索 */
     if ( β <= v ) return v; /* カット */
     if ( α < v ) α = v;
 
     while ( ( child = node.GetNextChild() ) != null ){
         v = -NegaScout ( child, -α - 1, -α, depth - 1 ); /* Null Window Search */
         if ( β <= v ) return v; /* カット */
         if ( α < v ) {
             α = v;
             v = -NegaScout( child, -β, -α, depth - 1 ); /* 通常の窓で再探索 */
             if ( β <= v ) return v; /* カット */
             if ( α < v ) α = v;
         }
         if( max < v ) max = v;
     }
     return max; /* 子ノードの最大値を返す (fail-soft) */
 }

• Alexander Reinefeld. Spielbaum-Suchverfahren. Informatik-Fachbericht 200, Springer-Verlag, Berlin (1989), ISBN 3-540-50742-6