やあ！アルファベータ検索を実装しようとしていますが、最初に、ある種の疑似コードを使用して実装するだけでなく、その背後にあるすべてのロジックを理解したいと考えています。
私が理解していることは次のとおりです。白人のプレーヤーが動きます（動き1と呼びましょう）。最初の手はアルファ (プレーヤーが保証される最小値) として保存されます。ここで、白の次の可能な手 (move2) に移動し、黒のプレーヤーの最初の応答がアルファよりも悪い評価になることがわかった場合、白が手 2 を作るときは既にわかっているため、可能なすべての黒のカウンターの動きをスキップできます。 、考えられる最悪の結果は、move1 の考えられる最悪の結果よりも悪いです。
しかし、私が理解していないのはそのベータ変数です。チェスプログラミングウィキから私は読んだ：「最小化プレーヤーが保証される最大スコア」。しかし、私はその背後にあるアイデアを本当に得ることができません。
誰かがそれを非常に簡単な言葉で説明できますか? どうもありがとうございました。
チェスでは、move1 が move2 よりも優れているかどうかを判断する簡単な方法はありません (あなたの例から)。概算は、「ハード」パラメーターを調べることによって達成されます: ピースの数と値、ダブルまたはフリー ポーンの存在... 通常、このような概算はミニマックス アルゴリズムに組み込まれます。
簡単に言えば、アイデアは次のとおりです。まず、事前に定義された深さまたは時間制限に達するまで、すべての可能な動きが展開されます (白-黒-白-黒...)。これにより、ボードの位置のツリーが作成され (エッジとしての移動を使用)、葉はヒューリスティックを使用して評価されます (上記のように)。次に、ツリーが折りたたまれ、最後に move1 と move 2 の評価が行われます。
崩壊はどのように機能しますか？ツリーの葉から開始し、各ノード (別名ボード位置) に値を割り当てます。すべての子の値がわかっているノードごとに、子の値が集計されます。白の番の場合は、白の最良の値が取得されます (最大)。黒の番なら最悪（最小）。したがって、ミニマックスという名前です。これをルートに到達するまで繰り返します。
次のボード ポジションのツリーを想定します。
A
| \
B1 B2
| | \
A11 A21 A22
ここで、次の評価を想定します: A11 = 0、A21 = -1、A22 = +1 (正の値は白に適しています)。概算から、位置 A21 は A22 (黒の場合) よりも優れていると想定するため、ノード B2 に -1 を割り当てます。B1 の場合、これは明らかで、その値は 0 です。ここで、B1 は B2 よりも白の方が優れていると仮定します。したがって、A の値は 0 であり、白は位置 B1 を達成するために移動する必要があります。
ここでの考え方は、ツリー全体を構築することではなく、早期のカットオフを達成するために、より有望な手を深さ優先で検索することです。上記の例で、ツリーの深さ優先を左から右 (A-B1-A11-B2-A21-...) にたどると、A21 を評価した後、白の位置 B2 が位置 B1 より悪いことがわかります。したがって、A22 を評価する必要はもうありません。アルファとベータは、現在知られている白の可能な最良の手と、現在知られている黒の可能な最良の応答の評価を単純に保存します。ツリーのノードがウォークされる順序 (初期順序) によって、カットオフが可能かどうか、および可能なカットオフの数が決まります。ウィキペディアから:
通常、アルファベータ期間中、サブツリーは一時的に最初のプレーヤーのアドバンテージによって支配されます (多くの最初のプレーヤーの動きが適切であり、各検索深度で最初のプレーヤーによってチェックされた最初の動きが適切である場合、すべての 2 番目のプレーヤーの応答は反論を見つけようとする）、またはその逆。...
順序付けが最適ではない場合、より多くのサブツリーを完全に調査する必要があります。
反復深化深さ優先探索も参照してください 。
厳密に言えば、ツリーはDAGです。同じボードの位置は、さまざまな動きの組み合わせ (例:トランスポジション) によって達成できるためです。ハッシュテーブルを使用して同一の位置を検出します。これにより、計算量が大幅に節約されます。
基本的には、アルファとベータは、ゲーム ツリーで既に調査したものからの最適な結果の上限と下限であるため、それらの境界外のものは調査する価値がありません。
minimax と alpha-beta pruning について詳しく理解してからしばらく経ちましたが、私の覚えている要点は次のとおりです。
あなたが言ったように、白のmove1スコアが 10 であることをすでに知っていて、調査中move2に黒が対応して、白が最高スコアの 8 になるように強制されることがわかった場合move2、これ以上調査する価値はありません。私たちができる最善のことは、私たちが知っている別のオプションよりも悪いことであることを私たちはすでに知っています.
しかし、これはミニマックス アルゴリズムの半分にすぎません。今、白の を調べmove3て、黒のすべての応答を見ているとしましょう。黒の を探索しmoveX、それに対する白の応答の 1 つが少なくとも 15 のスコアを強制できることを発見しました。その後、黒の探索を開始し(moveY依然として白の元の に対するmove3応答)、それに対する白の応答を見つけたmoveY場合、スコアは で強制されます。少なくとも 18 であれば、黒に由来するゲーム ツリー全体moveYが無意味であることがすぐにわかります。黒は白が 15 点を獲得できるようにするだけで、白が 18 点を獲得できるように黒を強制するだけなmoveYので、黒は .moveXmoveY
アルファは、我々が調査しているポイントに至るまでにさまざまな選択を行うことによって、白が強制できることがすでにわかっている最小スコアを表します。したがって、 alphaを超える可能性がないことがわかったら、パスを探索し続ける価値はありません。白ではそのパスに到達できないためです。
ベータは、私たちが調査しているポイントに至るまでにさまざまな選択を行うことで、黒が強制できることがわかっている最大スコアを表します。したがって、 beta未満になる可能性がないことがわかったら、パスを探索し続ける価値はありません。黒ではそのパスに到達できないためです。