主変異検索

主変異探索(実質的に同一であるNegaScoutと同一視されることもある) は、アルファベータ剪定よりも高速なネガマックスアルゴリズムです。アルファベータ剪定と同様に、NegaScout はツリー内のノードのミニマックス値を計算するための方向性探索アルゴリズムです。アルファベータ剪定によって剪定できるノードを検査しないという意味で、NegaScout はアルファベータ剪定よりも優れていますが、この利点を生かすには正確なノード順序付けが必要です。

NegaScout は、移動順序が適切である場合に最も効果的に機能します。実際には、移動順序は以前のより浅い検索によって決定されることがよくあります。最初に探索されたノードが最適であると想定することで、アルファ-ベータよりも多くのカットオフを生成します。言い換えると、最初のノードが主バリエーション内にあると想定します。次に、残りのノードをヌル ウィンドウ (アルファとベータが等しい場合、スカウト ウィンドウとも呼ばれる) で検索することで、それが真かどうかを確認できます。これは、通常のアルファ-ベータ ウィンドウで検索するよりも高速です。証明が失敗した場合、最初のノードは主バリエーション内になく、検索は通常のアルファ-ベータとして続行されます。したがって、NegaScout は、移動順序が適切である場合に最も効果的に機能します。ランダムな移動順序では、NegaScout は通常のアルファ-ベータよりも時間がかかります。アルファ-ベータが探索しなかったノードは探索しませんが、多くのノードを再検索する必要があります。

アレクサンダー・ラインフェルドはアルファベータ剪定の発明から数十年後にNegaScoutを発明した。彼は著書の中でNegaScoutの正しさを証明している。^[1]

SSS*と呼ばれる別の検索アルゴリズムでは、理論的には検索されるノードが少なくなります。ただし、元の定式化には実用的な問題があり (特に、ストレージに OPEN リストに大きく依存している)、今日ではほとんどのチェス エンジンが検索に NegaScout の形式を使用しています。ほとんどのチェス エンジンは、検索ツリーの関連部分が格納される転置テーブルを使用します。ツリーのこの部分のサイズは、SSS* の OPEN リストのサイズと同じです。^[2] MT-SSS* と呼ばれる再定式化により、転置テーブルを使用する Alpha–Beta (または NegaScout) への一連の null ウィンドウ呼び出しとして実装できるようになり、ゲームをプレイするプログラムを使用して直接比較できるようになりました。実際には NegaScout より優れたパフォーマンスを発揮しませんでした。実際には NegaScout よりも優れたパフォーマンスを発揮する傾向がある別の検索アルゴリズムは、MTD(f)と呼ばれるベスト ファースト アルゴリズムですが、どちらのアルゴリズムも他方より優れているわけではありません。 NegaScout が SSS* や MTD(f) よりも少ないノードを検索するツリーがあり、その逆も同様です。

NegaScout は、1980 年にJudea Pearlが発明した SCOUT に倣ったもので、これはアルファ ベータを上回り、漸近的に最適であることが証明された最初のアルゴリズムでした。^{[3] [4]} ネガマックス設定で β=α+1 のヌル ウィンドウは、JP Fishburn によって独立に発明され、博士論文の付録にある SCOUT に似たアルゴリズム、^[5]並列アルファ ベータ アルゴリズム、^[6]および検索ツリーのルート ノードの最後のサブツリーで使用されました。^[7]

ほとんどの動きは両方のプレイヤーにとって受け入れられるものではないため、正確なスコアを得るためにすべてのノードを完全に検索する必要はありません。正確なスコアは、主バリエーション(両方のプレイヤーにとって最適な動きのシーケンス) のノードにのみ必要であり、そのスコアはルートまで伝播します。反復深化検索では、前の反復でそのようなシーケンスの候補がすでに確立されており、これは一般に主バリエーションとも呼ばれます。この主バリエーションの非リーフについては、その子は、この主バリエーションの次のノードが最初の子になるように並べ替えられます。他のすべての子は、現在のプレイヤーにとってより悪いか等しいスコアになると想定されます (この想定は、現在の PV 候補が実際の PV であるという想定に従います)。これをテストするために、最初の動きをフルウィンドウで検索して、他の子のスコアの上限を確立し、それに対してゼロウィンドウ検索を実行して、動きを改善できるかどうかをテストします。ゼロウィンドウ検索はベータカットオフの頻度が高いため、はるかに安価であるため、多くの労力を節約できます。ある動きがアルファを上げることができるとわかった場合、その動きに対する仮定は反証されたことになり、正確なスコアを得るために全ウィンドウで再探索を行います。 ^{[8] [9]}

関数pvs(node, depth, α, β, color)は
    、 depth = 0またはnodeが終端ノードの場合、 color × nodeの各子のノードのヒューリスティック値
    を返します。childが最初の子の場合、
        
        
            スコア := −pvs(子, 深さ − 1, −β, −α, −色)
        そうでない場合、
            スコア:= −pvs(child, depth − 1, −α − 1, −α, −color) (* ヌルウィンドウで検索 *)
             α < スコア < βの場合、
                スコア:= −pvs(child, depth − 1, −β, −α, −color) (* 高い値で失敗した場合は、完全な再検索を実行します *)
        α := max(α, スコア)
        α ≥ βの場合、
            ブレーク (* ベータカットオフ *)
     α
を返す

• キラーヒューリスティック

• コンピュータチェスのプログラミング理論
• 戦略ゲームプログラミング