0

我正在使用带有 Alpha Beta 修剪的 MiniMax 为 Othello 游戏实现 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

如果你只想知道根位置的最佳移动，记住根位置的哪个移动得分最高就足够了。为此，只需返回分数就足够了。不需要更改伪代码。

当您询问到关键节点的路径时，我猜您是在询问一种重建主要变化的方法，它可以提供有关搜索预期的一系列移动的见解。

理论上，您可以只返回递归调用的值和主要变化。这使您可以重建路径。三角 PV 表是为此目的而优化的数据结构。

如果您的搜索使用换位表，则更简单的方法是从根位置开始并在换位表中查找最佳移动。然后进行该动作并重复（查找最佳动作，做出最佳动作，再次查找等），直到游戏结束或未找到条目。最后，所做的动作是主要的变化。

转置表方法不像显式跟踪主要变化那样精确，但实现起来很简单，并且在搜索过程中不会增加开销。

于 2017-01-01T19:56:17.010 回答