EUVIMEDEUVIMED entdecken
Crossref

Massively Parallel Proof-Number Search for Impartial Games and Beyond

Tomáš Čížek, Martin Balko, Martin Schmid

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 36838-36846

DOI: 10.1609/aaai.v40i43.41010 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Tomáš Čížek und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.9x 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,000x 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.

Zitieren

APA

Čížek, T., Balko, M., & Schmid, M. (2026). Massively Parallel Proof-Number Search for Impartial Games and Beyond. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 36838-36846. https://doi.org/10.1609/aaai.v40i43.41010

Vancouver

Čížek T, Balko M, Schmid M. Massively Parallel Proof-Number Search for Impartial Games and Beyond. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):36838-36846. doi:10.1609/aaai.v40i43.41010

BibTeX
@article{ek2026,
  author = {Čížek, Tomáš and Balko, Martin and Schmid, Martin},
  title = {Massively Parallel Proof-Number Search for Impartial Games and Beyond},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {43},
  pages = {36838--36846},
  doi = {10.1609/aaai.v40i43.41010}
}
Kostenlos starten →