Recent Articles

Solved board games

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

1. Ultra-weak: 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. Weak: 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. Strong: 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 (a game of the Mancala family)
  • The variant allowing game ending "grand slams" was 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 Four
  • Solved by both Victor Allis (1988) and James D. 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 6×6.
  • Jing Yang has demonstrated a winning strategy (definition #2) for board sizes 7×7, 8×8 and 9×9 .
  • A winning strategy for hex with swapping is known for the 7×7 board.
  • John Nash showed that all board sizes are won for the first player (definition #1).
  • Strongly solving hex on an N×N board is unlikely as the problem has been shown to be PSPACE-complete.
• Nim
  • Completely solved for all starting configurations.
• Nine men's morris
  • Solved by Ralph Gasser (1993). Either player can force the game into a draw .
• Pentominoes
  • Weakly solved (definition #2) by H. K. Orman. It is a win for the first player.
• 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 9 pieces (and some 10 piece endgames) have been solved. Not all early-game positions have been solved, but almost all midgame positions are solved. In August, 2004, the opening called White Doctor was proven to be a draw. Contrary to popular belief, Checkers is not completely solved, but this may happen soon.
• Chess
  • Completely solved (definition #3) by retrograde 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
  • Solved (definition #3) for board sizes up to 4×4. The 5×5 board is weakly solved . Humans usually play on a 19×19 board.
• Reversi
  • Solved on a 4×4 and 6×6 board as a second player win.
• mnk-games
  • It is trivial to show that the second player can never win; see strategy-stealing argument. Almost all cases have been solved weakly for k ≤ 4. Some results are known for k = 5. The games are drawn for k ≥ 8.

See Also: Board game complexity