如何编写多线程 Alpha-Beta 搜索算法？
How do I write a Multi threaded Alpha-Beta Search algorithm?
我正在尝试使用 alpha beta minimax 搜索算法创建一个国际象棋引擎，但代码太慢了。我已经做了我能想到的所有优化，但它在单线程中仍然很慢。我查看了一些其他引擎的源代码以了解它们是如何实现的以及国际象棋编程 wiki (https://www.chessprogramming.org/Parallel_Search#Parallel_Alpha-Beta)，但是代码超出了我的水平，我看不懂它们。我也找不到任何书面资料或代码片段。
谁能解释一下如何在 alpha-beta 搜索算法中高效地实现线程化？谢谢
Alpha-beta 是一种固有的顺序算法，因为您的 alpha 和 beta 值会在整个搜索过程中不断更新，并且截止值是根据这些值决定的。出于这个原因，通过增加线程数量来获得任何加速是非常困难的，你投入的线程越多，收益就越小。
然而，仍然有几种方法可以做到这一点，其中大多数都相当复杂，而且它们在线程更多的情况下的扩展性极差。 go to 算法曾经是 Young Brothers wait 的概念，它是一个相当复杂的算法，直到几年前 Stockfish 才使用它。然而，随着现代计算机上可用内核数量的增加，扩展性非常差，代码也非常复杂。今天，大多数现代引擎都使用一种叫做 Lazy SMP 的东西。该算法几乎尽可能地简单，并且比其他算法具有更好的扩展性。
在惰性 SMP 中，您所要做的就是开始与您通常所做的完全相同的搜索，只是在多个线程上。它依赖于一个有效的换位 table，线程通过该换位相互通信。线程永远不会完全同步，随机性将导致每个线程探索搜索树的略有不同的部分，然后将它们的结果保存到转置 table 中，它可能会被另一个线程使用。当然每个线程都有很多重复的工作，但是它仍然比试图巧妙地拆分工作和减慢算法要好，当你开始增加线程数量时尤其如此。
我建议您查看国际象棋编程 wiki，您甚至可以在其中找到一些关于如何实现它的伪代码。
https://www.chessprogramming.org/Lazy_SMP
虽然我还应该指出，如果您正在寻找的是提高您的深度时间，那么实施多线程对您来说不会有太大帮助（在某些极端情况下，它甚至可能会减慢速度！ ).相反，您需要的是更积极地 p运行ing 搜索树和更有效的实现（例如，没有内存分配，因此垃圾收集器永远不必 运行，等等）。
我正在尝试使用 alpha beta minimax 搜索算法创建一个国际象棋引擎，但代码太慢了。我已经做了我能想到的所有优化，但它在单线程中仍然很慢。我查看了一些其他引擎的源代码以了解它们是如何实现的以及国际象棋编程 wiki (https://www.chessprogramming.org/Parallel_Search#Parallel_Alpha-Beta)，但是代码超出了我的水平，我看不懂它们。我也找不到任何书面资料或代码片段。
谁能解释一下如何在 alpha-beta 搜索算法中高效地实现线程化？谢谢
Alpha-beta 是一种固有的顺序算法，因为您的 alpha 和 beta 值会在整个搜索过程中不断更新，并且截止值是根据这些值决定的。出于这个原因，通过增加线程数量来获得任何加速是非常困难的，你投入的线程越多，收益就越小。
然而，仍然有几种方法可以做到这一点，其中大多数都相当复杂，而且它们在线程更多的情况下的扩展性极差。 go to 算法曾经是 Young Brothers wait 的概念，它是一个相当复杂的算法，直到几年前 Stockfish 才使用它。然而，随着现代计算机上可用内核数量的增加，扩展性非常差，代码也非常复杂。今天，大多数现代引擎都使用一种叫做 Lazy SMP 的东西。该算法几乎尽可能地简单，并且比其他算法具有更好的扩展性。
在惰性 SMP 中，您所要做的就是开始与您通常所做的完全相同的搜索，只是在多个线程上。它依赖于一个有效的换位 table，线程通过该换位相互通信。线程永远不会完全同步，随机性将导致每个线程探索搜索树的略有不同的部分，然后将它们的结果保存到转置 table 中，它可能会被另一个线程使用。当然每个线程都有很多重复的工作，但是它仍然比试图巧妙地拆分工作和减慢算法要好，当你开始增加线程数量时尤其如此。
我建议您查看国际象棋编程 wiki，您甚至可以在其中找到一些关于如何实现它的伪代码。 https://www.chessprogramming.org/Lazy_SMP
虽然我还应该指出，如果您正在寻找的是提高您的深度时间，那么实施多线程对您来说不会有太大帮助（在某些极端情况下，它甚至可能会减慢速度！ ).相反，您需要的是更积极地 p运行ing 搜索树和更有效的实现（例如，没有内存分配，因此垃圾收集器永远不必 运行，等等）。