我正在为一个卡牌游戏编写 AI，经过一些测试后，我发现将 MTD(f) 算法应用到我的 alpha-beta 算法（一系列零窗口搜索）上比单独使用 alpha-beta 算法更快。

MTD(f) 算法在这里有很好的描述：http://people.csail.mit.edu/plaat/mtdf.html

我遇到的问题是，在 MTD(f) 搜索的每次迭代（对于每个猜测）中，我都没有重用任何以前存储的位置，即使链接上的文章建议我应该这样做（实际上，在迭代之间清除表格会加速算法）。

我的问题是，当我在置换表中存储一个位置和一个值时，我还会存储它有效的 alpha 和 beta 值。因此，通过具有不同猜测（因此 alpha 和 beta）的树的第二次传递不可能重用任何信息。这是应该预期的吗？或者我遗漏了一些基本的东西？

例如，如果对于 alpha=3，beta=4，我们得到了结果 7（显然是一个截止），我应该将它存储在表格中，对于 alpha=3 到 beta=6 有效吗？还是 beta=7？

回答：

你的问题归结于对如何在 alpha-beta 搜索旁边使用置换表的概念理解。这也是我遇到的一个大问题，经过一番搜索，我找到了这个讨论，它比我读过的任何关于这个主题的论文都更自然地向我解释了这个概念。

基本上，你不能将所有 alpha-beta 结果都视为相同，因为当发生截止时，结果仅代表一个界限，而不是真正的极小极大值。已经证明，使用界限仍然总是会给你相同的最佳下一个状态，但可能没有准确的分数。当你存储来自截止的状态时，你需要将其视为一个界限，并在下一次传递中尝试改进它。这将经常多次评估同一个节点，但它会根据需要不断改进实际分数。

这是一个很好的例子，更完整地实现了之前链接文章中列出的概念。滚动到第 14 页。