Solved Games

Various games have been solved. Here are some useful links.

General Information About Solved Board Games

The wikipedia has an excellent article on the subject.

Jaap van den Herik, Jos Uiterwijk and Jack van
Rijswijk published a comprehensive survey of solved games circa 2001.

Some Games That Have Been Solved

Awari was solved by John Romein and Henri Bal (2002).
They have a nice applet for viewing the proof.

Connect Four was solved independently at roughly the same time by James Allen and Victor Allis (1988).
Recently, the game has been strongly solved by John Tromp

Go Moku was solved by Victor Allis (1994).

Nine Men’s Morris was solved by Ralph Gasser (1994).

Qubicwas solved by Oren Patashnik (1980) and later by Victor Allis (1994).

Some popular games have been solved for small board sizes, including:

Hex (7x7)

Go (5x5)

Amazons (5x5)

Othello (6x6)

Useful Algorithms

Proof number search is a best-first search algorithm used to solve many games.
L. Victor Allis, Maarten van der Meulen, and H. Jaap van den Herik, “Proof-number Search”, Artificial Intelligence, vol. 66, no. 1, pp. 91-124, March 1994.

Depth-first proof number search is the depth-first search variant.
A. Nagai, Df-PN Algorithm for Searching AND/OR Trees and Its Applications, Ph.D. thesis, Department of Information Science, University of Tokyo, 2002.

Proof number search was based on David McAllester’s Conspiracy Numbers algorithm.
David McAllester, “Conspiracy Numbers for Min-Max Search”, Artificial Intelligence, vol. 35, pp. 287-310, 1988.

The graph-history interaction (GHI) problem can cause problems with  proofs. Akihiro Kishimoto and Martin Muller developed a high- performance and accurate solution to this problem (2004).
Akihiro Kishimoto and Martin Müller, “A General Solution to the Graph History Interaction Problem”, American Association for Artificial Intelligence National Conference (AAAI), pp. 644-649, 2004.

Cool Links

Dan Garcia has built a nice site for solved games, including software for helping you solve your own game.

Top of Page