Solved game
From Free net encyclopedia
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 (often a strategy stealing argument is used), and does 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.
Even if an algorithm for solving the game in one of the above senses is known, the game is not considered solved unless the algorithm can be run in a reasonable time on existing computers. For a game with a finite number of positions, there is a simple algorithm which would strongly solve the game by checking all the positions, but for many such games using this algorithm would require far more computing power than will be available in the foreseeable future.
Separate from these is the question of whether a game remains interesting for humans to play. A game solved in the strong sense can still be interesting if the solution is too complex to be memorized (e.g. 9×9 Hex); conversely, a weakly solved game may lose its attraction if the winning strategy is simple enough to remember (e.g Maharajah and the Sepoys). An ultra-weak solution (e.g. Chomp or Hex on a sufficiently large board) generally does not affect playability.
Contents |
[edit]
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
- A strategy-stealing argument proves this is a 1st player win starting from a rectangle. However, this “ultra-weak” solution is merely a curiosity arising from the fact that, in effect, the first player has a “pass” move available (remove just one block) and hence can choose to become the second player if this is more advantageous. An actual winning strategy for the game is not known except in the simplest cases. If the “pass” move is forbidden as an opening then it is not even known in general which player wins.
- 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 [2].
- A winning strategy for Hex with swapping is known for the 7×7 board.
- If Hex is played on an N × N+1 board then the player who has the shorter distance to connect can always win by a simple pairing strategy, even with the disadvantage of playing second.
- 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.
- Kalah
- Most variants solved by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk (2000) except Kalah (6/6). Strong first-player advantage was proven in most cases. [3]
- L Game
- Easily solvable. Either player can force the game into a draw.
- Maharajah and the Sepoys
- This asymmetrical game is a win for Black with correct play.
- 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 [4].
- Pentominoes
- Weakly solved (definition #2) by H. K. Orman. It is a win for the first player.
- Qubic
- Weakly solved by Oren Patashnik (1980), strongly solved by Victor Allis. The first player win.
- Teeko
- Completely solved by Guy Steele (1998). Depending on the variant either a first-player win or a draw. [7].
- 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.
[edit]
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 January, 2005, the opening called White Doctor was proven to be a draw. Contrary to popular belief, Checkers is not completely solved, but this may happen in several years, as computer power increases.
- 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. The full game has 32 pieces.
- Go
- Solved (definition #3) for board sizes up to 4×4. The 5×5 board is weakly solved for all opening moves [8]. Humans usually play on a 19×19 board.
- Reversi (alias Othello)
- Solved on a 4×4 and 6×6 board as a second player win. On 8x8, 10x10 and greater boards the game is strongly supposed to be a draw. Nearly solved on 8x8 board (the standard one): there are thousands of draw lines.
- 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.
[edit]
See also
[edit]
External links
[edit]
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)