Loading article…
主変分探索（実質的に同一の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 のヒューリスティック値 を返します。 node の各子に対して、子が最初の子である場合、 score := − pvs(child, depth − 1, − β, − α, − color) とします。そうでない場合は 、score := − pvs(child, depth − 1, − α − 1, − α, − color) (* null ウィンドウを使用して検索 *) α < score < βの場合、 score := − pvs(child, depth − 1, − β, − α, − color) (* 失敗した場合は、完全な再検索を実行 *) α := max(α, score) α ≥ βの場合、ブレーク(* β カットオフ *) αを返す