如何使用置换表与MTD(f)

Question

如何使用置换表与MTD(f)

algorithmlanguage-agnosticartificial-intelligence

14

我正在为一款纸牌游戏编写人工智能，经过一些测试，我发现在我的alpha-beta算法中使用MTD(f)（一系列零窗口搜索）比仅使用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？

- Daniel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nick Larsen · Accepted Answer

您的问题在于如何将置换表与Alpha-Beta搜索结合使用的概念理解清楚。我也遇到过这个问题，后来找到了这篇讨论，其中比我看过的任何文章都更自然地向我解释了这个概念。

基本上，您不能将所有的Alpha-Beta结果视为相同的，因为当截断发生时，结果仅代表一个边界，而不是真正的极小值或极大值。已经证明，使用边界仍然会始终给出相同的最佳下一步状态，但可能没有确切的分数值。当您存储从截断的状态时，需要将其视为一个边界，并在下一次搜索中尝试改进它。这通常会评估多次相同的节点，但随需持续改进实际分数。

这里有一个很好的例子，其中包含了前面链接文章中列出的概念的更完整实现。请翻到第14页。