多线程alpha-beta-pruning的有效性是什么?

问题描述 投票:0回答:1

如果符合以下条件,使用alpha beta修剪的多线程的有效性是什么?

迭代地使用多线程。例如,线程1将查看第一个分支,第二个线程将查看第二个线程,等等。我认为这应该只在第一个深度完成(AI制作的下一个移动),因为其他深度可能是隔断。

一个线程在第一次“移动”时生成搜索到生成的移动集的一半,第二个线程在最后一次“移动”生成并搜索到移动集的一半。在这里,我认为可能会有更高的加速,因为最后一步可能被认为是最好的举动,因此,第二个线程可能导致第一个线程无法切断。

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

我想,可能还有其他一些优化,但这些是我想到的少数优化。不过,我不知道他们是否会改善任何事情。

multithreading minimax alpha-beta-pruning
1个回答
1
投票

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

为了比较,这里是国际象棋中现有并行化策略的摘要:

由于alpha-beta是一种顺序算法,所有并行化策略都是推测性的。因此,您希望避免花时间搜索搜索树的部分内容,最终会被其他移动切割。避免搜索不相关的子树的一个相对简单的策略叫做Young Brothers Wait Concept

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

© www.soinside.com 2019 - 2024. All rights reserved.