algorithm - Alpha Beta 剪枝，alpha 等于或大于 beta。为什么等于？

Question

虽然我了解 MiniMax 树和 alpha-beta 修剪概念，但我不明白为什么在许多(例如维基百科)有关 alpha-beta 修剪的资源中存在像 α >= β 这样的条件。具体来说，equals 令人困惑。据我所知，alpha beta 返回的移动是 minmax 返回的，但主要是速度更快。但是这个例子与之矛盾:

        .
      / |  \
    1   3*   2
  / |  / \   | \ \
  1 1 5   3  4 3 2

上面是原始的最小-最大树。正如我们所见，它会选择得分为 3 的一步。现在让我们进行 alpha-beta:

        .
      / |  \
    1   3*   3*
  / |  / \   | \
  1 1 5   3  4 3

它切断了最右边的移动，因为 3 >= 3。但是算法可以在 2 个移动之间进行选择，因为它们具有相同的分数，但正如我们在 min-max 中看到的那样，正确的选择稍差。如果算法仅指定 α > β，则不会发生这种情况，因此它也需要搜索 2。

那是维基百科伪代码(以及许多其他资源)中的拼写错误吗？或者我在这里误解了一些非常重要的事情。

Answer 1

Wikipedia 上的算法不返回走法，它返回根节点的分数，即 3。这个分数与 minimax 结果相同。您将需要稍微修改算法以获得下棋而不是得分。

这样做的一种方法是在当前状态的每个可能移动上运行 alphabeta 函数并播放得分最高的一个。按照维基百科上的链接给出 implementation就是这样做的。

我认为您还可以跟踪在 alphabeta 函数中找到的最佳着法，但如果多个节点在同一级别具有相同分数，则返回找到的第一个。这可能会更好，因为需要评估的节点更少。