我正在编写一个国际象棋引擎，最近添加了转置表。
在进行了一些测试后，我发现虽然搜索仍然返回了相同的最佳走法，但走法的价值（对最大化玩家有多好）出现了波动。
这是转置表的正常行为吗？我记得读到过转置表会导致搜索不稳定。这就是那个意思吗？所以这是正常现象还是我代码中的严重错误？
回答：
是的，转置表确实会引入搜索不稳定性。
幸运的是，这种情况发生的频率足够低，转置表的优势远远超过这一复杂性。
1. 转置表的功能是什么？
在你的程序中添加转置表（TT）后，你应该会注意到两个主要的变化：
- 改进走法排序：来自转置表的走法通常是最佳可能的走法
- 提前截断：当你再次达到一个已经以更大距离搜索过的位置时，你可以停止并使用存储在转置表条目中的值
在国际象棋中，改进的走法排序是最重要的因素。只有在残局中，转置的可能性增加，你会看到更多的提前截断。
那么，搜索不稳定性是什么意思呢？它意味着当你以给定的距离搜索一个位置，然后再次重复相同的搜索（相同的位置，相同的距离），你会得到相同的结果。
2. 简单的极小极大/alpha-beta搜索算法
让我们先忽略搜索扩展，从简单的极小极大或alpha-beta搜索开始。
请注意，你的搜索将具有可重复性的特性，并且不会看到搜索不稳定性。即使你通过转置表的走法来改进走法排序，你仍然会得到每次搜索的相同结果。然而，在添加转置表后，来自更深层次搜索的额外截断通常会破坏这一特性并引入不稳定性。
例如，考虑一个包含深层战术的位置：
- 低距离的搜索可能看不到它，但更大距离的搜索会看到。
- 将该结果存储在转置表中后，低距离的重新搜索也会看到该战术。现在它的行为与原始搜索相比有所不同。
- 更糟糕的是，当转置表条目被覆盖时，改进的知识又会丢失。
因此，使用额外的知识来强制提前截断是导致不稳定的一个因素。（但在实践中，这是值得的，因为这更多是一个理论问题。）
3. 搜索扩展
当应用于简单的alpha-beta搜索时，改进的走法排序本身不会导致搜索不稳定性。在实施了许多扩展的现实世界搜索算法中，情况更为复杂。其中一些扩展对走法排序也很敏感。
一个突出的例子被称为晚期走法减少（LMR）。它利用了这样一个事实，即走法排序的质量通常非常高，以至于只需要彻底搜索前几个走法，而其他走法很可能是坏的，只会以减少的距离进行搜索。
LMR只是走法排序使搜索不那么可重复的一个例子。但同样，优势占主导地位。
4. 正常的搜索不稳定性有多大？
没有明确的答案。在实践中，你无法完全消除不稳定性，但如果不稳定性失控，你的搜索将变得低效。
当然，错误也可能是导致不稳定性的原因。那么，这是你的搜索中的错误吗？嗯，我不知道。可能是。:-)
