Massively Parallel Proof-Number Search for Impartial Games and Beyond (arxiv.org)

Researchers developed the first massively parallel version of Proof-Number Search (PNS), a best-first search algorithm widely used for solving impartial games, by introducing two levels of parallelization and explicit sharing of search information among workers. The implementation also integrates Grundy-number reductions to collapse equivalent subgames and prune the game tree. On a 1024-core cluster the solver obtained a 332.9× speedup, dramatically outperforming the prior state-of-the-art Sprouts solver (GLOP) by about four orders of magnitude in runtime and producing proofs roughly 1,000× more complex. Despite the exponential blowup typical of combinatorial game trees, the approach scaled efficiently and enabled verification of the Sprouts Conjecture for 42 new starting positions, almost doubling the set of known outcomes. This work is significant because it demonstrates that hierarchical parallelism plus shared global information can overcome longstanding scalability bottlenecks in PNS, making best-first proof search practical on large CPU clusters. The combination of parallel architecture and game-specific reductions (Grundy numbers) shows a clear path to handling much larger search spaces and generating larger, verifiable proofs. Beyond Sprouts, the techniques are broadly relevant to other impartial games, combinatorial search, and automated reasoning tasks where proof-number–style searches and equivalent-state reductions apply.