用于并行象棋搜索的共享哈希表

Question

这是一个关于并行象棋搜索的shared hashtable algorithm的概念性问题。

我已经实现了一个产生4个线程的alpha-beta搜索，每个线程执行一个搜索并返回最佳移动/评估。然而，我观察到了搜索的不稳定性，其中线程返回不同的结果。我使用的是链接中描述的无锁哈希表，因此一些条目可能会被覆盖或损坏，尽管损坏的数据实际上永远不会被使用。

为什么搜索线程会返回不同的结果？这是并行搜索的预期结果，还是存在问题？如果是预期的，我如何知道要选择哪个移动？

Answer 1

并行搜索应该是不确定的。一旦你通过转置表(也就是哈希表)分享知识，你就会有这样的效果。

如果运行并行搜索，没有简单的方法来确定正确的结果是什么。那么，你能做什么呢？如果你有四个线程，你可以尝试多数票，但我不知道有这样做的引擎。

请注意，一旦开始使用转换表，您甚至会在顺序搜索算法中遇到搜索稳定性的问题。

如果您使用转置表运行顺序搜索算法，然后重复相同的搜索(不重置转置表)，则不能保证获得相同的结果。对于并行搜索也是如此，只是并行搜索甚至不是确定性的。

搜索稳定性和确定性不是一回事：

• 在顺序搜索中，可以实现确定性(对调试很有用)。在并行搜索中，您无法在practice.
• Neither中避免它。在实践中，顺序搜索或并行搜索都无法排除搜索稳定性。然而，在一个好的搜索算法中，这应该是相对不太可能的。

要解释为什么转置表会导致搜索不稳定，请查看this question。