Alpha Betaを使用してノードを選択する方法

Question

Alpha Betaプルーニングを使用するMiniMaxを使用してOthelloゲーム用のAIを実装しています。私はアルファベータアルゴリズムを実装しました。このアルファベータアルゴリズムは、私が得ることができる値を教えてくれますが、どのノードを選択すべきかはわかりません。だから私の質問は、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 

Answer 1

ルートポジションでの最適な移動を知りたい場合は、ルートポジションで最も高いスコアを持つ移動を覚えていれば十分です。そのためには、スコアを返すだけで十分です。擬似コードの変更は必要ありません。

重要なノードへのパスについて質問しているので、principal variationを再構築する方法について質問しているので、検索の一連の動きについての洞察が得られます。

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

transposition tableを使用している場合、簡単な方法は、ルートの位置を開始し、転置テーブルで最良の移動を検索することです。その後、ゲームが終了するか、エントリが見つからなくなるまで、その動きを繰り返して（最高の動きを見て、最良の動きを見せ、再度参照するなど）最終的に、行われた動きが主要なバリエーションです。

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