Breakthrough is a well-known abstract board game played regularly at the Computer Games Olympiad. Despite the straightforward gameplay mechanics of the game, determining optimal play strategies poses significant challenges. We have (weakly) solved a variant of the game played on the board, representing the largest board instance of the game solved to date. The game is a win for the first player. We apply a hybrid approach of computing endgame tablebases, defining game-specific race patterns, using a family of parallelizable proof-number-based solvers, and training a neural-network-based heuristic job scheduler to construct a solution tree and proof of the game’s game-theoretic value. This approach allowed us to not only solve the game variant, but also lays the foundation for solving the game’s larger board-size variants.
AllisL. V. (1994). Searching for solutions in games and artificial intelligence [PhD thesis]. Rijksuniversiteit Limburg.
2.
BerlekampE.ConwayJ. H.GuyR. K. (1982). Winning ways for your mathematical plays (Vol. 2). Academic Press.
3.
BreukerD. M.UiterwijkJ. W. H. M.van den HerikH. J. (2001). The PN-search algorithm. In H. van den Herik & B. Monien (Eds.), Advances in computer games 9 (pp. 115–132). Maastricht University.
4.
ConsidineJ. (2024). Compressed game solving. In M. Hartisch, C. Hsueh, & J. Schaeffer (Eds.), Computers and games—12th international conference, CG 2024, Virtual Event, November 25–29, 2024, Revised Selected Papers. Volume of 15550 Lecture Notes in Computer Science (pp. 79–90). Springer.
5.
de ManR. (2013). Syzygy: Chess endgame database (tablebase) generator.
6.
GaoC.MüllerM.HaywardR. (2017). Focused depth-first proof number search using convolutional neural networks for the game of hex. In C. Sierra (Ed.), Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI 2017), Melbourne, Australia, 2017 (pp. 3668–3674). ijcai.org.
7.
GasserR. (1996). Solving nine men’s morris. Computational Intelligence, 12, 24–41.
8.
HandsombK. (2001). game design competition: The winning game: Breakthrough…and two other favorites. Abstract games.
9.
HendersonP. T. (2010). Playing and solving the game of Hex [PhD thesis]. University of Alberta.
10.
IrvingG. (2014). Pentago is a first player win: Strongly solving a game using parallel in-core retrograde analysis. CoRR, abs/1404.0743.
11.
IsaacA.LorentzR. (2016). Using partial tablebases in breakthrough. In A. Plaat, W. A. Kosters, & H. J. van den Herik (Eds.), Computers and games—9th international conference, CG 2016, Leiden, The Netherlands, June 29–July 1, 2016, revised selected papers. Volume 10068 of Lecture Notes in Computer Science (pp. 1–10). Springer.
12.
KishimotoA.WinandsM. H. M.MüllerM.SaitoJ.-T. (2012). Game-tree search using proof numbers: The first twenty years. ICGA Journal, 35(3), 131–156.
13.
KreherD. L.StinsonD. R. (1999). Combinatorial algorithms: Generation, enumeration, and search. CRC Press.
14.
MatsakisN.StoneJ., &contributors (2015–2025). Rayon: A data parallelism library for Rust. GitHub. https://github.com/rayonrs/rayon.
SaffidineA.JouandeauN.CazenaveT. (2012). Solving breakthrough with race patterns and job-level proof number search. In H. J. van den Herik & A. Plaat (Eds.), Advances in computer games, Berlin, Heidelberg (pp. 196–207). Springer Berlin Heidelberg.
17.
SchaddM. P. D.WinandsM. H. M.UiterwijkJ. W. H. M.van den HerikJ.BergsmaM. H. J. (2008). Best play in Fanorona leads to draw. New Mathematics and Natural Computation, 4(3), 369–387.
18.
SchaefferJ. (2021). The computer olympiads 1989–2021. ICGA Journal, 43(3), 184–187.
19.
SchaefferJ.BurchN.BjörnssonY.KishimotoA.MüllerM.LakeR.LuP.SutphenS. (2007). Checkers is solved. Science (New York, N.Y.), 317, 1518–1522.
20.
TakizawaH. (2023). Othello is solved. arXiv, abs/2310.19387.
21.
ThompsonK. (1986). Retrograde analysis of certain endgames. Journal of the International Computer Games Association, 9, 131–139.
22.
van den HerikH. J.UiterwijkJ. W. H. M.van RijswijckJ. (2002). Games solved: Now and in the future. Artificial Intelligence, 134(1–2), 277–311.
23.
WinandsM. H. M.UiterwijkJ. W. H. M. (2001). PN, PN and PN* in Lines of Action. In J. W. H. M. Uiterwijk (Ed.), The CMG sixth computer olympiad computer-games workshop proceedings. Universiteit Maastricht.
24.
WuT.ShihC.WeiT.TsaiM.HsuW.WuI. (2022). Alphazero-based proof cost network to aid game solving. In The tenth international conference on learning representations, ICLR 2022, Virtual Event, April 25–29, 2022. OpenReview.net.
25.
ZakharovV.MaknhychevV. (2013). Creating tables of chess 7-piece endgames on the Lomonosov supercomputer. Superkompyutery, 15, 34–37.
