转置表是否会导致搜索不稳定

Question

我正在写一个国际象棋引擎,最近添加了一个换位表.

在进行一些测试时,我发现尽管搜索仍然返回了相同的最佳移动,但移动的值(对于最大化玩家有多好)会波动.

这是换位表的正常行为吗？我记得读过换位表会导致搜索不稳定.这是什么意思？这是我的代码中的正常事件或严重错误吗？

Answer 1

是的，换位表会导致搜索不稳定。

幸运的是，这种情况很少发生，以至于换位表的优势远远超过了这种复杂性。

1、换位表的作用是什么？

将换位表 (TT) 添加到您的程序后，您应该注意到两个主要区别：

1. 改进走法顺序：TT 的走法通常是最好的走法
2. Early cutoffs：当您再次到达已经搜索过更远距离的位置时，您可以停止并使用存储在 TT 条目中的值

在国际象棋中，改进的移动顺序是最重要的因素。只有在残局中，换位的可能性才会增加，你会看到更多的早期截断。

那么，搜索不稳定是什么意思呢？这意味着当您以给定距离搜索一个位置，然后重复相同的搜索（相同位置，相同距离）时，您将获得相同的结果。

2. 简单的极大极小/阿尔法测试搜索算法

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

请注意，您的搜索将具有搜索可重复的属性，并且不会发现搜索不稳定。即使您通过换位表中的移动来改进您的移动顺序，您仍然会在每次搜索时获得相同的结果。但是，在添加 TT 之后，更深层次搜索的额外截止通常会破坏该属性并引入不稳定性。

例如，考虑一个包含深度策略的位置：

• 距离较近的搜索可能看不到，但距离较远的搜索会。
• 在将该结果存储在 TT 中之后，以低距离重新搜索也会看到该策略。与原始搜索相比，它现在的行为有所不同。
• 更糟糕的是，当 TT 条目被覆盖时，改进的知识再次得到很多。

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

3. 搜索扩展

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

一个突出的例子称为后期移动减少（LMR）。它利用了这样一个事实，即移动排序的质量通常如此之高，以至于只需要彻底搜索前几个移动，而其他移动很可能是坏的移动，只会在更短的距离内搜索。

LMR 只是移动排序降低搜索可重复性的一个例子。但同样，优势占主导地位。

4. 多少搜索不稳定是正常的？

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

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

Answer 2

这是转置表的正常行为吗？我记得读到转置表可能会导致搜索不稳定。是这个意思吗？

是的。

那么这是我的代码中的正常现象还是严重的错误？

乔纳森·谢弗的建议（在“攻击计划”下）：

如果您最初限制 TT 查找仅在表深度与您需要的深度完全匹配时才有效，则 TT 不会更改固定深度 alpha-beta 搜索的结果。但是，它应该减少搜索的节点数量。验证其是否正常工作。

添加迭代深化和移动排序。如果你做得正确，它不应该改变搜索的最终结果，但同样，它应该减少搜索的节点数量。

只有当您确定上述所有内容 100% 有效时，您才可以继续使用更多搜索增强功能和更好的评估功能。