Massively Parallel Proof-Number Search for Impartial Games and Beyond
This work addresses the bottleneck of parallelization in game-solving algorithms, enabling faster and more complex proofs for impartial games like Sprouts, though it is incremental in improving an existing method.
The authors tackled the problem of poor scalability in parallel Proof-Number Search algorithms by developing a massively parallel version that scales efficiently on many CPU cores, achieving a 332.9× speedup on 1024 cores and verifying the Sprouts Conjecture for 42 new positions.
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, to the Sprouts game, a case study motivated by the long-standing Sprouts Conjecture. Our solver achieves a significantly improved 332.9$\times$ speedup when run on 1024 cores, enabling it to outperform the state-of-the-art Sprouts solver GLOP by four orders of magnitude in runtime and to generate 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.