null window search

 今現在ゼミの関係でリバーシのプログラムを作っているのだが、探索アルゴリズムに使われているnull window searchの概念がイマイチつかめなかった。
 このたびようやく理解できたのでまとめる。




 上の図はいわゆるalpha-beta法(正確にはnegamax法にalpha-betaを適用したもの)である。
 左側の部分木の評価値が-4に決まったあと右側の部分木の評価に移る。
 このとき、もし右側の部分木の評価値が-4より大きくなれば、その手は切り捨てられる。なぜならnegamax法では下の節の値を符号反転させたもののうちから最大値を取るからである。
 右側の部分木の葉を一つづつ調べていくと評価値3の葉を調べ終わったときに、もはや右側の部分木は探索の必要がなくなったことがわかる。3を符号反転した-3は-4より大きい値だからである。
 こうして残りの2つの葉は評価されることなく終わる。


 もし、上の探索をalpha-beta法でなくminimax法(alpha-betaのように枝刈りを行わない探索法)で行ったとするとどうなるだろう。もちろん根に返される値はalpha-beta法と変わらない。
 変わるのは右部分木の評価値である。もし枝刈りを行わなかったなら全ての葉の中で一番小さい(符号反転すれば一番大きい)2が評価値として選ばれていただろう。結果右部分木の評価値は-2となっているはずである。


 もしalpha-beta法で枝刈りが行われた状況を想定すると、同じ探索をminimaxで行った場合はalpha-beta法で得られた値よりも同じか、少し悪い値が返ってきているはずである。上の図でalpha-betaのときは-3、minimaxのときは-2が部分木の評価値になっていることからもそれがわかる(符号反転すると-3のほうが大きくなる)。
 
 この性質を利用すると、alpha値とbeta値の範囲を0にした探索を行い、実際の評価値を見積もることができるようになる。
 これがnull window searchである。これを探索に利用したものにはScout法(negamax法に適用したものをNegaScout法)がある。


 書いている内に気づいたけれど、alpha値とbeta値の説明を全くしていなかった。
 まあいいか。