大规模并行证明数搜索突破性能瓶颈，高效验证了42个新棋局结果。
Massively Parallel Proof-Number Search for Impartial Games and Beyond
- 采用双层并行与共享信息机制，实现高可扩展性并行搜索
- 在1024核上达332.9倍加速，比现有最优解法快四数量级
- 适用于公平博弈求解，尤其适合大规模游戏树验证任务
证明数搜索是一种成功的最佳优先搜索算法，广泛应用于游戏求解。随着大规模计算集群的普及，并行化成为加速计算的自然途径。然而，现有的证明数搜索并行版本在大量CPU核心上扩展性不佳。本文提出首个大规模并行的证明数搜索版本，通过两级并行与工作节点间共享信息，实现了在大量CPU上的高效扩展。我们将该求解器结合格伦迪数用于简化公平博弈的游戏树，应用于斯普罗茨游戏（Sprouts），这是由长期存在的斯普罗茨猜想所驱动的案例研究。算法在1024核上实现332.9倍加速，显著优于以往并行化方案，且在运行时间上比当前最先进的斯普罗茨求解器GLOP快四个数量级，同时生成的证明复杂度提高1000倍。尽管游戏树规模呈指数增长，本求解器仍成功验证了42个新位置的斯普罗茨猜想，使已知结果数量几乎翻倍。
原文摘要 · Abstract (English)
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 efficiently even on a large number of CPUs. We apply our solver, enhanced with Grundy numbers for reducing game trees of impartial games, to the Sprouts game, a case study motivated by the long-standing Sprouts Conjecture. Our algorithm achieves 332.9$\times$ speedup on 1024 cores, significantly improving previous parallelizations and outperforming the state-of-the-art Sprouts solver GLOP by four orders of magnitude in runtime while generating proofs 1,000$\times$ more complex. Despite exponential growth in game tree size, our solver verified the Sprouts Conjecture for 42 new positions, nearly doubling the number of known outcomes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。