# 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.

http://en.wikipedia.org/wiki/Solved_board_games

Jaap van den Herik, Jos Uiterwijk and Jack van

Rijswijk published a comprehensive
survey of solved games circa 2001.

http://www.fdaw.unimaas.nl/education/4.2ZT/

Literature/GamesSolved.pdf

## Some Games That Have Been Solved

*Awari* was solved by John Romein and Henri Bal (2002).

http://www.cs.vu.nl/~john/papers/Computer-03/awari.ps

They have a nice applet for viewing the proof.

http://awari.cs.vu.nl

*Connect Four* was solved independently at roughly the same time by
James Allen and Victor Allis (1988).

http://www.connectfour.net/Files/connect4.pdf

Recently, the game has been strongly solved by John Tromp

http://homepages.cwi.nl/~tromp/c4/c4.html

*Go Moku* was solved by Victor Allis (1994).

http://fragrieu.free.fr/SearchingForSolutions.pdf

*Nine Men’s Morris* was solved by Ralph Gasser (1994). http://www.msri.org/publications/books/

Book29/files/gasser.pdf

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

http://fragrieu.free.fr/SearchingForSolutions.pdf

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

Hex (7x7)

http://www.cs.ualberta.ca/~hayward/publications.html

Go (5x5)

http://erikvanderwerf.tengen.nl/5x5/5x5solved.html

Amazons (5x5)

http://www.cs.ualberta.ca/~mmueller/ps/5x5gpw.pdf.gz

Othello (6x6)

http://www.feinst.demon.co.uk/Othello/6x6sol.html.

## 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.

http://www.cs.ualberta.ca/~mmueller/ps/aaai-ghi.pdf

## Cool Links

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

http://gamescrafters.berkeley.edu/