Massively Parallel Proof-Number Search for Impartial Games and Beyond
Tomáš Čížek, Martin Balko, Martin Schmid
Proof-Number Search是一种最好的第一搜索算法,具有许多成功的应用程序,特别是在游戏解决方面。 随着大规模计算集群变得越来越容易获得,并行化是加速计算的自然方式。 然而,已知Proof-Number Search的现有并行版本在许多CPU内核上扩展得很差。 使用两个并行级别和工人之间的共享信息,我们提出了Proof-Number Search的第一个大规模并行版本,即使在大量CPU上也能有效扩展。 我们应用我们的求解器,用Grundy数字增强以减少游戏树,到Sproouts游戏,这是一个由长期Sproouts猜想驱动的案例研究。 我们的求解器在运行 1024 核心时实现了显著改进的 332.9 倍的提速,使其能够在运行时超过最先进的 Sproouts 求解器 GLOP 四个数量级,并生成 1000 倍更复杂的证明。 尽管游戏树的大小呈指数级增长,但我们的求解器验证了42个新位置的Sproouts猜想,几乎使已知结果的数量翻了一番。
Proof-Number Search is a best-first search algorithm with many successful applications, especially in game solving. As large-scale computing clusters become increasingly accessible, parallelization is a natural way to accelerate computation. However, existing parallel versions of Proof-Number Search are known to scale poorly on many CPU cores. Using two parallelized levels and shared information among workers, we present the first massively parallel version of Proof-Number Search that scales eff...
