换位表会导致搜索不稳定吗

Question

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

在运行一些测试时，我发现尽管搜索仍然返回相同的最佳移动，但移动的值（对最大化玩家来说有多好）是波动的。

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

Answer 1

这是换位表的正常行为吗？我记得读过换位表会导致搜索不稳定。这是什么意思吗？

对

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

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

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

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

只有当你确信以上所有内容都是100%有效的时候，你才应该继续进行更多的搜索增强和更好的评估功能。

Answer 2

是的，换位表引入了搜索不稳定性。

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

1.换位表的功能是什么？

在向程序中添加转置表（TT）后，您应该注意到两个主要区别：

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

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

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

2. 简单的最小值/阿尔法贝塔搜索算法

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

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

例如，考虑一个包含深度策略的头寸：

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

因此，利用额外的知识来迫使早期截止是导致不稳定的一个因素。（但在实践中，这是值得的，因为这更多的是一个理论问题。）

3.搜索扩展

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

一个突出的例子是所谓的后期移动减少(LMR)。它利用了这样一个事实，即走法排序的质量通常很高，只有前几个走法需要彻底搜索，而其他的走法很可能是不好的走法，只需以减小的距离进行搜索。

LMR只是移动排序使搜索不那么可重复的一个例子。但是，优势再次占据主导地位。

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

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

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