当使用带有 Alpha-Beta 修剪的 Minimax 时，我将如何找到最佳节点

Question

我正在尝试制作一个国际象棋引擎，基本思想是当我单击按钮时，计算机会移动。这是我的代码：

def alphabeta(board, node, depth, a, b, maximizer):
if depth == 0:
return evaluate.node(node)
if maximizer == True:
value = -10**3 # Number that's smaller than what the evaluation algorithm can return
for child in board.get_all_nodes(node):
m = alphabeta(board, child, depth-1, a, b, False)
value = max(value, m)
a = max(a, value)
if a >= b:
break
return value
else:
value = 10**3 # Number that's bigger than what the evaluation algorithm can return
for child in board.get_all_nodes(node):
m = alphabeta(board, child, depth - 1, a, b, True)
value = min(value, m)
b = min(b, value)
if a >= b:
break
return value

问题是此代码返回最佳移动的评估，而不是移动树本身。如何在不再次运行整个函数的情况下找到最佳移动？

Answer 1

有两种方法可以解决这个问题：

1. 创建另一个看起来类似于alphabeta的函数getbestmove，但是当它获得最佳值时，它还会将相应的child(move(分配给新的变量bestnode。而不是返回值，它返回该bestnode。不要让这个函数递归地调用自己，而是alphabeta，至于更深的搜索级别你不需要记住最好的动作。

   你总是会打电话给getbestmove以获得最好的举动，...不再需要从getbestmove外部直接拨打alphabeta.

2. 调整alphabeta，以便它以元组的形式返回值和相应的移动。当深度为 0 时，您没有移动，所以只需让最佳移动None。递归调用应从返回的元组(值部分(中提取第一个值，alphabeta的最外层调用可以从返回元组的第二部分获得最佳移动。

   def alphabeta(board, node, depth, a, b, maximizer):
   if depth == 0:
   return (evaluate.node(node), None) # tuple of value and move
   bestmove = None
   if maximizer == True:
   value = -10**3 # Number that's smaller than what the evaluation algorithm can return
   for child in board.get_all_nodes(node):
   m = alphabeta(board, child, depth-1, a, b, False)[0] # ignore the move part
   value = max(value, m)
   if value > a:
   bestmove = child
   a = value
   if a >= b:
   break
   else:
   value = 10**3 # Number that's bigger than what the evaluation algorithm can return
   for child in board.get_all_nodes(node):
   m = alphabeta(board, child, depth - 1, a, b, True)[0] # ignore the move part
   value = min(value, m)
   if value < b:
   bestmove = child
   b = value
   if a >= b:
   break
   return (value, bestmove) # tuple of value and move
   

   您甚至可以扩展它以跟踪搜索树中的"最佳路径"。