如何使用MTD转置表(f)

Question

我正在为纸牌游戏编写AI,经过一些测试,我发现在我的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？

Answer 1

您的问题归结为如何在alpha beta搜索中使用转置表的概念性理解.这也是我遇到的一个很大的问题,在环顾四周后,我发现这个讨论比我在这个主题上读到的任何论文更自然地向我解释了这个概念.

基本上你不能将所有alpha-beta结果都视为相同,因为当发生截止时,结果只表示一个边界,而不是真正的极小极大值.已经证明,使用边界仍将始终为您提供相同的最佳下一个状态,但可能没有确切的分数.当您从截止状态存储状态时,您需要将其视为边界并尝试在下一次传递时对其进行改进.这通常会多次评估同一节点,但会根据需要不断改进实际得分.

以下是更完整实现上一个链接文章中列出的概念的一个很好的示例.滚动到第14页.