0

树

您好，我正在尝试从以下代码中以国际象棋为例来理解 alpha beta 剪枝算法：

def minimax(position, depth):
"""Returns a tuple (score, bestmove) for the position at the given depth"""
    if depth == 0 or position.is_checkmate() or position.is_draw():
        return (position.evaluate(), None)
    else: 
        if position.to_move == "white":
            bestscore = -float("inf")
            bestmove = None
            for move in position.legal_moves():
                new_position = position.make_move(move)
                score, move = minimax(new_position, depth - 1)
                if score > bestscore: # white maximizes her score
                    bestscore = score
                    bestmove = move
            return (bestscore, bestmove)
        else:
            bestscore = float("inf")
            bestmove = None
            for move in position.legal_moves():
                new_position = position.make_move(move)
                score, move = minimax(new_position, depth - 1)
                if score < bestscore: # black minimizes his score
                    bestscore = score
                    bestmove = move
            return (bestscore, bestmove)

这是我从中获得的博客的链接：LINK（如果您喜欢突出显示的语法，可以从链接中查看代码）

我不明白的是，在 alpha beta 修剪中，当你在树上更高时，alpha 和 beta 变量的值有时必须改变。我附上了一张图片来解释我的问题 - 虽然我理解步骤 1)、2) 和 3)，但我没有得到 4) 步骤。我知道 4) 步骤应该如图所示，但我不知道值发生变化的那一步代码中发生了什么。我仔细地遵循了代码，但由于某种原因，我最终在 4) 步骤中得到了 a = 5 和 b = 5，这很荒谬，因为这意味着右边的分支将被删除，这显然是错误的。

4

1 回答 1

0

我认为您在评论中的推理不正确。从您的评论中，您隐含地认为搜索会转到树的右分支，然后返回树的左分支，这当然是不正确的。

你的逻辑是错误的，因为在树的左分支的 (5) 非叶节点处，搜索只访问了下面的节点（叶节点 (5) 和 (4)。它没有访问树的右分支，因此不知道值是什么。因此您的评论

“有一个最大节点（正方形），在 5（左侧）和 4（右侧）之间进行选择。它们上方的 MAX 节点需要更大的值，所以我认为 alpha 应该设置为 5是一个下界。” 是不正确的。

这是错误的，因为只有根节点（最大节点）知道右边的值 4，但只能在第 4 步之后进行。实际上只能在搜索结束时进行，在所有节点之后访问树的右分支。

于 2015-01-06T02:39:16.327 回答