5

虽然我了解 MiniMax 树和 alpha-beta 修剪概念，但我不明白为什么在许多（例如维基百科）关于 alpha-beta 修剪的资源中存在像 α >= β 这样的条件。具体来说，等于是令人困惑的。据我了解， alpha beta 返回移动 minmax 会返回，但大多数情况下它会更快。但这个例子与之矛盾：

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

上面是原始的 min-max 树。正如我们所看到的，它会选择得分为 3 的一步。现在让我们进行 alpha-beta：

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

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

那么这是维基百科伪代码（和许多其他资源）中的错字吗？或者我在这里误解了一些非常大的东西。

4

2 回答 2

4

维基百科上的算法不返回移动，它返回根节点的分数，即 3。正是这个分数与极小极大结果相同。您需要稍微修改算法以使移动而不是得分。

一种方法是在当前状态的每个可能移动上运行alphabeta函数并播放得分最高的一个。按照 wikipedia 上的链接提供了执行此操作的实现。

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

于 2015-07-15T17:15:20.290 回答
2

通常使用 equals ，因为它可以获得可识别的性能增益，并且您的返回值不会从相等的分支中改变。

在第一层搜索深度中它至少可能有用的唯一一点，但性能损失在这里是最糟糕的。

Minimax 依赖于对手总是下出最好的动作，而不是猜测他是否会犯错误。如果您包含一些特殊评估以选择两个相等分支中的更好者，您将花费资源进行推测（由于它的定义，您不会在 minimax 中这样做）。

所以总而言之，不使用equals是没有意义的。

于 2015-07-16T07:43:02.677 回答