如何使用转置表与MTD（f）

Question

我正在为纸牌游戏编写人工智能，经过一些测试后，我发现在我的alpha测试版算法中使用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的结果（显然是截断值），我应该在表中存储它作为α= 3到β= 6有效吗？或者beta = 7？

Answer 1

您的问题归结为如何在alpha测试搜索旁边使用换位表的概念性理解。这也是我遇到的一个巨大问题，在四处看后，我发现this discussion这比我关于该主题阅读的任何文章都更自然地向我解释了这个概念。

基本上你不能把所有的alpha-beta结果都视为相同的，因为当发生截断时，结果只表示一个界限，而不是真正的minimax值。已经证明，使用边界仍然会始终给你相同的最佳状态，但可能没有确切的分数。当你从截止状态存储状态时，你需要把它作为一个界限，并在下一个阶段尝试改进。这通常会多次评估同一个节点，但它会根据需要不断改进实际分数。

Here is a good example更完整地实现了前面链接文章中列出的概念。滚动到第14页。