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.**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.

Table of contents |

2 Partially solved games |

## Solved games

- Awari (a game of the Mancala family)
- 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 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 (definition #2) for board sizes 7x7, 8x8 and 9x9. [1]
- John Nash showed that all board sizes are won for the first player (definition #1).
- The discovery of an efficient general algorithm for an NxN board is unlikely as the problem has been shown to be NP-hard.

- 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. [1]

- 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

- 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
- Solved (definition #3) for board sizes up to 4x4. The 5x5 board is partially solved. [1] Humans usually play on a 19x19 board (which has an enormous complexity). Therefore solving the game appears very unlikely. On the other hand, a heuristic algorithmic solution might be achievable in the future. While not mathematically complete, it could give good results in practice, perhaps beating even the best human players.

- Reversi
- solved on a 4x4 and 6x6 board as a second player win.

- mnk-games
- It is trivial to show that the second player can never win. Almost all cases have been solved weakly for
*k*<= 4. Some results are known for*k*= 5. The games are drawn for*k*>= 8.

- It is trivial to show that the second player can never win. Almost all cases have been solved weakly for

*See Also:*Board game complexity

### External link

### References

- 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) 277–311. 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)