|
|
|
|
|
Solved Board GamesA 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)
- Chomp
- An elegant argument proves this is a 1st player win.
- Connect Four
- 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 66.
- Jing Yang has demonstrated a winning strategy (definition #2) for board sizes 77, 88 and 99 http://www.ee.umanitoba.ca/~jingyang/.
- A winning strategy for hex with swapping is known for the 77 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 NN 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
- Pentominoes
- Weakly solved (definition #2) by H. K. Orman. It is a win for the first player.
- Qubic
- 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
- Reversi
- Solved on a 44 and 66 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 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) 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)
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|