Solved board games

A two-player game can be "solved" on several levels.

1. In the weakest sense, solving a game means proving whether the first player will win, lose, or draw from the initial position, given perfect play[?] on both sides.
2. More typically, solving a game means providing an algorithm which secures a win for one player, or a draw for either, against any possible moves by the opponent, from the initial position only.
3. The strongest sense of solution requires an algorithm which can produce perfect play from any position, i.e. even if mistakes have already been made on one or both sides. For a game with a finite number of positions, this is always possible with a powerful enough computer, by checking all the positions. However, there is the question of finding an efficient algorithm, or an algorithm that works on computers currently available.

Solved games

• Awari[?]
  • Solved by Henri Bal[?] and John Romein[?] at the Free University[?] in Amsterdam, Netherlands (2002). Either player can force the game into a draw.
• Connect 4[?]
  • Solved by both Victor Allis[?] (1988) and James Allen[?] (1989) independently. First player can force a win.
• Gomoku
  • Solved by Victor Allis[?] (1993) First player can force a win.
• Hex
  • Completely solved (definition #3) by several computers for board sizes up to 6x6.
  • Jing Yang has demonstrated a winning strategy (http://www.ee.umanitoba.ca/~jingyang/) (definition #2) for board sizes 7x7 and 8x8.
  • John Nash showed that all board sizes are won for the first player (definition #1).
• Nine men's morris
  • Solved by Ralph Gasser (1996). Either player can force the game into a draw.
• Qubic[?]
  • Solved by Patashnik[?] (1980).
• Three Men's Morris
  • Trivially solvable. Either player can force the game into a draw
• Tic-tac-toe
  • Trivially solvable. Either player can force the game into a draw

Partially solved games

• Checkers
  • Endgames up to 8? pieces have been solved. Not all early-game positions have been solved, but almost all midgame positions are solved. Contrary to popular belief, Checkers is not completely solved.
• Chess
  • Completely solved (definition #3) by retrospective computer analysis for all 2- to 5-piece endgames, counting the two kings as pieces. Also solved for pawnless 3-3 and most 4-2 endgames.
• Go
  • Completely solved (definition #3) for board sizes up to 5x5. [1] (http://www.ipsj.or.jp/members/SIGNotes/Eng/16/2000/077/article007.html)

External links

• Computational Complexity of Games and Puzzles (http://www.ics.uci.edu/~eppstein/cgt/hard.html)

References

• Allis, Beating the World Champion? The state-of-the-art in computer game playing. in New Approaches to Board Games Research.