Solved board games

From Academic Kids

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. This can be a non-constructive proof, and not actually help players.
  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.
Contents

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 [1] (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
    • Solved by Ralph Gasser (1993). Either player can force the game into a draw [2] (http://www.ics.uci.edu/~eppstein/cgt/morris.html).
  • 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 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.
  • Go
    • Solved (definition #3) for board sizes up to 44. The 55 board is weakly solved for all opening moves [3] (http://www.cs.unimaas.nl/~vanderwerf/5x5/5x5solved.html). Humans usually play on a 1919 board.
  • Reversi
    • Solved on a 44 and 66 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.

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 (http://www.cs.ualberta.ca/~javhar/research/gamessolved.pdf), ps (http://www.cs.ualberta.ca/~javhar/research/gamessolved.ps)
  • Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance (http://www.msri.org/publications/books/Book29/contents.html), MSRI Publications -- Volume 29, 1996, pages 339-344. Online (http://www.msri.org/publications/books/Book29/files/orman.pdf) (PDF)
Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools