FACTOID # 16: In the 2000 Presidential Election, Texas gave Ralph Nader the 3rd highest popular vote count of any US state.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Solved board games

A two-player game can be "solved" on several levels. A game is a recreational activity involving one or more players. ...

  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 does 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. For many games "a powerful enough computer" may never exist; the number of theoretically possible chess positions exceeds the number of atoms in the universe by some fifty orders of magnitude. (see Shannon number)

Contents

In game theory, perfect play is the behavior or strategy of a player which leads to the best possible outcome for that player. ... In mathematics, a nonconstructive proof, is a mathematical proof that purports to demonstrate the existence of something, but which does not say how to construct it. ... A chess table is a table with a chessboard painted or engraved on it. ... The Shannon number, 10120, is an estimation of the game-tree complexity of chess. ...


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

Oware is an abstract strategy game and the mancala game most widely considered suitable for serious adult competition. ... A foldable, wooden Mancala board Mancala is a family of board games played around the world, sometimes called sowing games or count and capture games, which comes from the general gameplay. ... Free University may refer to: The Free University of Berlin, a university in Berlin, Germany. ... Amsterdam Location Country The Netherlands Province North Holland Population 739,295 (1 January 2005) Coordinates 4°54E - 52°22N Website www. ... Chomp is a 2-player game played on a rectangular chocolate bar made up of smaller square blocks. ... In combinatorial game theory, the Strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy. ... Connect Four (also known as Plot Four) is a two-player board game in which the objective is to be the first to get four of ones own discs in a line. ... L. Victor Allis is a Dutch computer expert who works to find better ways of developing artificial intelligence. ... Gomoku, go-moku, or gobang (Japanese: 五目並べ, Gomoku Narabe, five points) is a board game traditionally played with go pieces (black and white stones) on a go board (19x19 intersections). ... L. Victor Allis is a Dutch computer expert who works to find better ways of developing artificial intelligence. ... Hex is a board game played on a hexagonal grid, usually in the shape of a 10 by 10 or a 11 by 11 rhombus. ... John Forbes Nash John Forbes Nash Jr. ... In combinatorial game theory, the Strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy. ... In complexity theory, PSPACE-complete is a complexity class. ... The L game was invented by Edward De Bono, intended to illustrate lateral thinking. ... Nim is a two-player mathematical game of strategy in which players take turns removing objects from heaps, one or more objects at a time but only from a single heap. ... Nine Mens Morris is a two-player strategy game with a long history in Europe. ... A pentomino is a geometric shape composed of five (Greek πέντε / pente) identical squares, connected orthogonally. ... a selfmade Qubic game Qubic is a four-in-a-row game played in a 4×4×4 matrix. ... Three mens morris is played on a three by three board (counting lines) and is a game of position. ... Tic-tac-toe, also called noughts and crosses and many other names, is a paper and pencil game between two players, O and X, who alternate in marking the spaces in a 3×3 board. ...

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.
  • 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 (AKA 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.

starting position on a 10×10 draughts board Draughts, also known as checkers, is a group of mental sport board games between two players which involve diagonal moves of uniform pieces and mandatory captures by jumping over the enemys pieces. ... January is the first month of the year in the Gregorian Calendar and one of seven Gregorian months with the length of 31 days. ... 2005 is a common year starting on Saturday of the Gregorian calendar. ... A chess table is a table with a chessboard painted or engraved on it. ... Black to move. ... The king (♔♚) is the most important piece in the game of chess. ... Go is a strategic, two-player board game originating in ancient China between 2000 BC and 200 BC. Go is a popular game in East Asia. ... Screen dump of WZebra 4. ... // Overview The mnk-game (or m,n,k-game) is an abstract board game in which two players take turns in placing a stone of their color on an m×n board, the winner being the player who first gets k stones of their own color in a row, horizontally... In combinatorial game theory, the Strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy. ...

See also

In game theory, game complexity is a measure of the complexity of a game. ... The idea of creating a chess-playing machine dates back to the eighteenth century. ...

External link

  • Computational Complexity of Games and Puzzles

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)

  Results from FactBites:
 
Solved board games - Wikipedia, the free encyclopedia (609 words)
The variant allowing game ending "grand slams" was solved by Henri Bal and John Romein at the Free University in Amsterdam, Netherlands (2002).
The 5×5 board is weakly solved for all opening moves [3].
On 8x8, 10x10 and greater boards the game is strongly supposed to be a draw.
Talk:Solved board games - Wikipedia, the free encyclopedia (528 words)
While there are a few exception (for instance Scrabble) virtually all board games which are solved or coming close to be solved are abstract.
Maybe the article should be moved to solved games but I don't really see much of a problem with its current title.
Board games are only a small subset of abstract games, so this article is more about the latter than the former.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m