algorithm - Alpha-beta 修剪与领带导致可避免的损失

Question

在开发玩一些简单策略游戏的软件时，我使用标准技术进行搜索和评估，包括 alpha-beta 修剪。但是我遇到了一个意想不到的问题，导致一名玩家选择了最终失败的举动，而不是与游戏挂钩的举动。

想象一下这个场景：MAX 玩家在深度 D 处至少有两个动作要评估。一个结果是平局，所以它的值是 0 并且 alpha 设置为 0。在搜索第二个 MAX 动作时，alpha = 0，在深度D+1, MIN 至少有两个回复要评估。其中之一是 MIN 的强制胜利。较早的 MIN 回复导致平局，因此其值为 0，并且 beta 设置为 0。这会触发 MIN 的 alpha-beta 截止，因为 beta 0 <= alpha 0。因此，从未见过后来的 MIN 强制获胜，并且第二个 MAX 移动的值为 0。因此可以选择它而不是第一个 MAX 移动（平局），从而导致 MAX 的可避免损失。

这是一个更具体的例子：井字游戏可以表示为……</p>

0 1 2
3 4 5
6 7 8

假设 MIN 玩家选择了第 8 格。MAX 玩家有 8 种可能的回答。检查的前四个回复 - 方块 0、1、2 和 3 - 都被评估为最终导致 MAX 的损失。正方形 4 被评估为平局，值为 0，因此 alpha 设置为 0。接下来评估正方形 5，作为该过程的一部分，将 0 的 alpha 值向下传递，并且可能的回复由 MIN一次评估一个。方块 0 被评估为 MIN 为平局，因此 beta 设置为 0。MIN 的下一个可能回复，方块 1，也是平局。此时，beta 和 alpha 都为 0，触发对剩余的 MIN 回复进行 alpha-beta 修剪。这些包括方块 4、6 和 7，所有这些都允许 MIN 获胜。但由于 alpha-beta 修剪，这些从未见过。值 0 向上传递到搜索树。最后，

有人看到这个分析有问题吗？这不是 alpha-beta 修剪的问题吗？

标签： algorithmrecursionsearchminimaxalpha-beta-pruning