多线程alpha-beta修剪的有效性是什么



如果

多线程被反复使用。例如,线程一会查看第一个分支,线程二会查看第二个线程,等等。我认为这应该只在第一个深度(AI进行的下一次移动)进行,因为其他深度可能会被切断。

一个线程在生成的第一个"移动"中搜索生成的移动集的一半,第二个线程在最后一个生成的"移动"并搜索回移动集的半部分。在这里,我认为可以提高速度,因为最后一步可以被认为是最好的一步,因此,第二个线程可能会导致第一个线程无法实现的中断。

多线程被用来思考对手的时间。例如,假设对手花了一些时间思考和采取行动。人工智能可以迭代地深化搜索并找到结果,而对手正在思考,我想,这不一定会导致加速,但有更多的时间进行极小值分析。

我想,可能还有其他优化,但这些只是我想到的少数几个。不过,我不知道他们是否真的会有所改善。

如果我正确理解你的想法,你计划并行搜索根位置的移动。与严格的顺序算法相比,它应该更好,但我不希望它能很好地扩展(使用多个CPU)。

为了进行比较,这里总结了国际象棋中现有的并行化策略:

  • https://www.chessprogramming.org/Parallel_Search

由于alpha-beta是一种顺序算法,所有的并行化策略都是推测性的。因此,您要避免花费时间搜索搜索树的某些部分,这些部分最终会被其他操作所削减。避免搜索不相关子树的一个相对简单的策略叫做Young Brothers Wait Concept。

还有一些算法具有改进的可扩展性,但代价是更难理解和实现。例如,支持工作窃取应该可以提高可扩展性。

最新更新