转置表会导致搜索不稳定吗

我正在编写一个国际象棋引擎，最近添加了转置表。

在进行了一些测试后，我发现虽然搜索仍然返回了相同的最佳走法，但走法的价值（对最大化玩家有多好）出现了波动。

这是转置表的正常行为吗？我记得读到过转置表会导致搜索不稳定。这就是那个意思吗？所以这是正常现象还是我代码中的严重错误？

回答：

是的，转置表确实会引入搜索不稳定性。

幸运的是，这种情况发生的频率足够低，转置表的优势远远超过这一复杂性。

1. 转置表的功能是什么？

在你的程序中添加转置表（TT）后，你应该会注意到两个主要的变化：

在国际象棋中，改进的走法排序是最重要的因素。只有在残局中，转置的可能性增加，你会看到更多的提前截断。

那么，搜索不稳定性是什么意思呢？它意味着当你以给定的距离搜索一个位置，然后再次重复相同的搜索（相同的位置，相同的距离），你会得到相同的结果。

2. 简单的极小极大/alpha-beta搜索算法

让我们先忽略搜索扩展，从简单的极小极大或alpha-beta搜索开始。

请注意，你的搜索将具有可重复性的特性，并且不会看到搜索不稳定性。即使你通过转置表的走法来改进走法排序，你仍然会得到每次搜索的相同结果。然而，在添加转置表后，来自更深层次搜索的额外截断通常会破坏这一特性并引入不稳定性。

例如，考虑一个包含深层战术的位置：

因此，使用额外的知识来强制提前截断是导致不稳定的一个因素。（但在实践中，这是值得的，因为这更多是一个理论问题。）

3. 搜索扩展

当应用于简单的alpha-beta搜索时，改进的走法排序本身不会导致搜索不稳定性。在实施了许多扩展的现实世界搜索算法中，情况更为复杂。其中一些扩展对走法排序也很敏感。

一个突出的例子被称为晚期走法减少（LMR）。它利用了这样一个事实，即走法排序的质量通常非常高，以至于只需要彻底搜索前几个走法，而其他走法很可能是坏的，只会以减少的距离进行搜索。

LMR只是走法排序使搜索不那么可重复的一个例子。但同样，优势占主导地位。

4. 正常的搜索不稳定性有多大？

没有明确的答案。在实践中，你无法完全消除不稳定性，但如果不稳定性失控，你的搜索将变得低效。

当然，错误也可能是导致不稳定性的原因。那么，这是你的搜索中的错误吗？嗯，我不知道。可能是。:-)

学技术