当使用Minimax和AlphaBeta修剪时，如何找到最佳节点

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
   

   您甚至可以扩展它来跟踪搜索树中的“最佳路径”