Solved board games

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

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. This can be a non-constructive proof, and not actually help players.
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.
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.
Chomp
- An elegant argument proves this is a 1st player win.
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 [1].
- 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 using the strategy-stealing argument (definition #1).
- Strongly solving hex on an N×N board is unlikely as the problem has been shown to be PSPACE-complete.
L game
- Easily solvable. Either player can force the game into a draw.
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 [2].
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.

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 for all opening moves [3]. 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.

Allis, Beating the World Champion? The state-of-the-art in computer game playing. in New Approaches to Board Games Research.
H. Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck, "Games solved: Now and in the future" Artificial Intelligence 134 (2002) 277311. Online: pdf, ps
Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications — Volume 29, 1996, pages 339–344. Online (PDF)

Categories: Board games