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:

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