Negascout
NegaScout または PVS (Principal Variation Search) は Alexander Reinefeld によって考案された アルファ・ベータ法よりも効率の良いミニマックス法アルゴリズムの一種である。
NegaScout は手の選択肢を列挙し何らかの方法で並べ替えた上で、初めに最も良さそうな手を通常の探索窓で探索し評価値を得る。 それ以降の手はまず Null Window Search を行いそれまでに見つかった最善手の評価値を超えるかどうかを調べ、 超えた場合にのみあらためて通常の探索窓で再探索し評価値を得る。 但し、得られた評価値がβ値以上でもあれば再探索を行わずその場でカットできる。 Null Window Searchは探索窓が狭くカットが頻繁に起こるため通常の探索よりも短時間で終了するが、 探索順序がランダムだと再探索が頻繁に起こり、結局はアルファ・ベータ法よりも時間が掛かってしまう。