一个置换表会导致搜索不稳定吗？

Question

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

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

置换表会导致搜索不稳定吗？我记得读过置换表可能会导致搜索不稳定。这就是它的意思吗？所以，这是正常现象还是我的代码中存在严重错误？

- chessprogrammer

Answer 1

是的，置换表会引入搜索不稳定性。

幸运的是，这种情况很少发生，置换表的优点远远超过了这种复杂性。

1. 置换表的作用是什么？

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

1. 改进移动排序：TT中的移动通常是最佳移动
2. 早期剪枝：当您再次到达已经以更大距离搜索过的位置时，可以停止并使用存储在TT条目中的值

在国际象棋中，改进的移动排序是最重要的因素。只有在残局中，置换的可能性增加，您将看到更多的早期剪枝。

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

2. 简单的极小极大/α-β搜索算法

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

注意，您的搜索将具有可重复性的属性，并且不会出现搜索不稳定。即使您通过转置表中的移动来改进移动顺序，每次搜索仍将获得相同的结果。但是，在添加TT之后，较深搜索的额外截止会一般打破该属性并引入不稳定性。

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

- 距离较近的搜索可能看不到它，但距离较远的搜索则会看到。 - 在将结果存储在TT中之后，重新使用低距离进行搜索将看到该战术。它现在与原始搜索的行为不同。 - 更糟糕的是，当TT条目被覆盖时，改进的知识再次丧失。

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

3.搜索扩展

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

一个著名的例子是后移减少法 (LMR)。它利用了移动排序的质量通常非常高，只有前几个移动需要彻底搜索，而其他移动很可能是糟糕的，将只使用缩短距离进行搜索。

LMR只是一个例子，其中移动排序使搜索 less repeatable。但是，优点仍然占优势。

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

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

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

- Philipp Claßen

---

请注意，“distance”的更好的技术术语是“depth”。 - ABCD

因此，如果您为每个深度存储单独的值，并且不进行覆盖，则可以消除不稳定性。 - Thomas Ahle

@ThomasAhle 如果您从不覆盖值，只在当前距离与存储距离完全匹配的情况下使用存储结果，则可以消除不稳定性。尽管如此，这两个假设都不实际。首先，您最终会用尽内存；其次，深度搜索的条目是非常有用的，不容忽视。 - Philipp Claßen

你仅仅通过删除旧条目就获得不稳定性吗？我认为应该没问题，因为你只需要重新搜索它们并获得与之前相同的值。但是，高深度节点很有用。然而，你可以保留已找到的移动以进行排序。 - Thomas Ahle

@ThomasAhle 是的，你说得对。只要你只使用具有完全相同深度的条目进行删除，那么删除就应该是可以的。然后它应该会产生完全相同的结果。因此，如果您重复搜索并删除之前访问过的某些条目，则仍应计算出相同的结果。是的，您可以在不影响稳定性的情况下使用所有条目进行移动排序。 - Philipp Claßen

Answer 2

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

是的。

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

Jonathan Schaeffer的建议（在“攻略”下）：

如果你最初限制TT查找仅在表深度完全匹配所需深度时有效，则TT不会改变固定深度alpha-beta搜索的结果。但是，它应该减少搜索的节点数。请确保这一点正常工作。

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

只有当你确定以上所有内容都100%正常工作后，才应该继续进行更多的搜索增强和更好的评估函数。

- Adam Stelmaszczyk