如何使用Alpha Beta選擇一個節點

我正在使用Alpha Beta修剪的MiniMax實現一個Othello遊戲的AI。我已經實現了Alpha Beta算法，告訴我可以獲得的價值，但不知道我應該選擇哪個節點？所以我的問題是如何使用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

來源

2016-12-31 Matthew Fennell

_不是什麼結果值_ - 但你也需要這樣做。你需要返回2件事情。一個確切的答案將取決於你的'節點'，編程語言等的定義。 –

@HenkHolterman爲什麼我需要返回結果值？例如，如果我的樹是二叉搜索樹，我只需要知道要選擇哪個節點，而不是該值是什麼？當然，儘管我需要這個值來確定選擇哪個節點 –

你剛剛回答自己：「確定哪個...」 –

如果您只想知道根位置上的最佳移動，就足以記住哪個移動在根位置得分最高。爲此，只需返回分數就足夠了。僞代碼沒有變化是必要的。

當您詢問關鍵節點的路徑時，我想您正在問一個重建principal variation的方法，該方法提供了關於搜索所期望的一系列移動的見解。

理論上，您可以直接從遞歸調用中返回值和主要變量。這可以讓你重建路徑。 Triangular PV-Tables是爲此目的而優化的數據結構。

如果您的搜索使用transposition table，一個簡單的方法是剛剛開始的根位置，並期待在置換表的最佳舉措。然後做出這個動作並重復（查找最佳動作，做出最佳動作，再次查找等），直到遊戲結束或者沒有找到任何條目。最終，所做出的舉動是主要的變化。

轉置表方法並不像明確跟蹤主要變化那樣精確，但實現起來很簡單，並且在搜索過程中不會增加開銷。

來源

2017-01-01 19:56:17

只是爲了澄清，轉置表可能會增加大量開銷（如果使用Zobrist散列，則減少更多）。但是，這個成本通常遠遠小於搜索樹大小的減少。 –

@NathanS。真正。「沒有開銷」假設搜索已經使用轉置表，但到目前爲止，我還沒有看到沒有轉置表的優化Alpha Beta搜索。至少在國際象棋中，每個引擎都使用它，主要是爲了改善移動順序。我認爲其他類似遊戲也是如此（例如Reversi）。 –

@PhillipClaßen非常真實 - 唯一不會使用換位表的遊戲是換位很少的地方。 –

如何使用Alpha Beta選擇一個節點

回答

相關問題