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/
