0

MiniMax とアルファ ベータ プルーニングを使用して、オセロ ゲームの AI を実装しています。取得できる値を教えてくれる Alpha Beta アルゴリズムを実装しましたが、どのノードを選択すればよいでしょうか? したがって、私の質問は、Alpha-Beta を使用して、結果の値がどうなるかではなく、どのノードを選択する必要があるかを伝える方法です。これが私の Alpha-Beta アルゴリズムの疑似コードです。

01 function alphabeta(node, depth, α, β, maximizingPlayer)
02      if depth = 0 or node is a terminal node
03          return the heuristic value of node
04      if maximizingPlayer
05          v := -∞
06          for each child of node
07              v := max(v, alphabeta(child, depth – 1, α, β, FALSE))
08              α := max(α, v)
09              if β ≤ α
10                  break (* β cut-off *)
11          return v
12      else
13          v := ∞
14          for each child of node
15              v := min(v, alphabeta(child, depth – 1, α, β, TRUE))
16              β := min(β, v)
17              if β ≤ α
18                  break (* α cut-off *)
19          return v
4

1 に答える 1

0

ルート ポジションのベスト ムーブだけを知りたい場合は、ルート ポジションのどのムーブが最高スコアを持っていたかを覚えておけば十分です。そのためには、スコアを返すだけで十分です。疑似コードを変更する必要はありません。

重要なノードへのパスについて質問しているように、主な変動を再構築する方法について質問していると思います。これにより、検索で予想された一連の動きについての洞察が得られます。

理論的には、再帰呼び出しから値と主要な変動を返すことができます。これにより、パスを再構築できます。Triangular PV-Tableは、その目的のために最適化されたデータ構造です。

検索で転置表を使用する場合、より簡単な方法は、ルート ポジションを開始して、転置表で最適な動きを検索することです。次に、ゲームが終了するか、エントリが見つからなくなるまで、その動きを繰り返します (最良の動きを検索し、最良の動きを作成し、再度検索するなど)。結局、行われた動きが主要なバリエーションです。

転置テーブルのアプローチは、主要なバリエーションを明示的に追跡するほど正確ではありませんが、実装が簡単で、検索中にオーバーヘッドが追加されることはありません。

于 2017-01-01T19:56:17.010 に答える