Alphabeta修剪,alpha等于或大于beta.为何等于？

Question

虽然我理解MiniMax树和alpha-beta修剪概念,但我不明白为什么在许多(例如维基百科)有关alpha-beta修剪的资源中存在像α> =β这样的条件.具体来说,平等是令人困惑的.据我所知,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.但是算法可以在两个移动之间进行选择,因为它们具有相同的分数,但正如我们在min-max中看到的那样,正确的选择稍微差一些.如果算法仅指定α>β,则不会发生这种情况,因此它也需要搜索2.

维基百科的伪代码(以及许多其他资源)中的错字是什么？或者我在这里误解了一些非常大的东西.

Answer 1

维基百科上的算法不返回一步，它返回根节点的分数，即 3。这个分数与极小极大结果相同。您需要稍微修改算法才能进行棋步而不是分数。

一种方法是在当前状态下的每个可能的移动中运行 Alphabeta 函数，并选择得分最高的移动。按照维基百科上的链接给出了执行此操作的实现。

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