{"ID":2842292,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.10339","arxiv_id":"2511.10339","title":"Massively Parallel Proof-Number Search for Impartial Games and Beyond","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2511.10339","url_pdf":"https://arxiv.org/pdf/2511.10339v2","authors":"[\"Tomáš Čížek\",\"Martin Balko\",\"Martin Schmid\"]","published":"2025-11-13T14:12:57Z","proceeding":"cs.AI","tasks":"[\"cs.AI\",\"cs.DC\",\"cs.GT\"]","methods":"[]","has_code":false}