为什么我的 alpha-beta 搜索结果取决于访问节点的顺序？

Question

我在 Python 中编写了一个 n x n tic-tac-toe 游戏并添加了一个 minimax 搜索，它似乎可以正常工作。但是，当我添加 alpha-beta p运行ing 时，搜索结果取决于访问节点的顺序。

在下面显示的 minimax 函数中，如果我在调用 node.create_children() 之后添加行 random.shuffle(node._children)，极小极大搜索的结果将变得不可预测（我通过运行通过 GUI 进行电脑对战电脑游戏，然后 diffing 生成的游戏文件）。但是，如果我删除了两个 if alpha >= beta: break 语句，那么节点改组对搜索结果没有影响。

我最初发现这个错误是因为我试图对子节点进行排序以提高 p运行ing 的有效性。只要这两个 if 语句保持不变，以任何方式（反转、排序、混洗等）更改节点的顺序都会更改搜索结果。这使我得出结论，这些 if 语句以某种方式导致搜索依赖于访问节点的顺序。

功能大致基于this pseudocode。主要区别在于我的 minimax 函数仅用于设置每个节点的值，而不是 return 值。

下面是函数定义。完整代码是 here (scroll up for class definitions). The minimax function is called by Tree.get_next_board (here)，只要引擎移动，就会从 GUI 调用它。我希望最终减少代码中的大量状态，但我希望算法中的问题有更明显的原因。

def minimax(node: Node, stats: Stats, alpha=core.NEG_INF, beta=core.INF, depth=8):
    stats.visited += 1

    if node.is_leaf():
        return

    if depth == 0:
        node.set_val(eval_board(node.get_board()))
        return

    stats.created += node.create_children()

    if node.is_max_node():
        new_val = core.NEG_INF
        for child in node.get_children():
            minimax(child, stats, alpha, beta, depth - 1)
            new_val = max(new_val, child.get_val())
            alpha = max(alpha, new_val)
            if alpha >= beta:
                break
    else:
        new_val = core.INF
        for child in node.get_children():
            minimax(child, stats, alpha, beta, depth - 1)
            new_val = min(new_val, child.get_val())
            beta = min(beta, new_val)
            if alpha >= beta:
                break

    node.set_val(new_val)

有没有人看出添加 alpha-beta p运行ing 会使我的搜索依赖于访问节点的顺序的明显原因？如果没有，任何人都可以提出此类问题的常见原因吗？如果问题很可能隐藏在我的代码的状态性中，我将欢迎有关如何减少状态性同时仍然使用树来缓存板的建议。如果一切都失败了，我认为我最好的选择是将 minimax 重新实现为一个没有树或其他状态的纯函数，看看是否能解决问题。

如果有人对运行代码感到好奇，他们可以下载 tic_tac_toe 模块和运行 python3 -m tic_tac_toe（已知可用于 Python 3.8 .6 Linux).

Answer 1

事实证明，添加 alpha-beta 剪枝实际上并没有改变 minimax 函数识别的最优节点 value，而是改变了root 被选为游戏引擎的下一步。我已经用普通的 minimax 算法注意到了这种行为，并实现了一种打破关系的方法（我的问题中没有显示），该方法与访问节点的顺序无关。然而，我对alpha-beta剪枝的理解是它在识别出一个最优节点后终止搜索，这意味着可能还有其他从未识别出的最优节点，所以添加alpha-beta剪枝导致我的游戏引擎选择不同的（但仍然是最优的）根据访问节点的顺序移动。

我的问题中显示的代码可能由于其状态性而仍然存在错误。此后，我重构了 minimax 函数和 Node class 以尽可能减少代码的状态性，同时仍将搜索结果缓存在树中。

另请参阅我的相关问题 here 关于在 alpha-beta 修剪期间同样最优节点的行为。

为什么我的 alpha-beta 搜索结果取决于访问节点的顺序？

Why does the result of my alpha-beta search depend on the order in which nodes are visited?

python

algorithm

game-theory

tic-tac-toe

minimax