Encyclopedia > Solved board games

  Article Content

Solved board games

A two-player game can be "solved" on several levels.
  1. 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.
  2. 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. 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

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
    • Completely solved (definition #3) for board sizes up to 5x5. [1] (http://www.ipsj.or.jp/members/SIGNotes/Eng/16/2000/077/article007)

External links

References

  • Allis, Beating the World Champion? The state-of-the-art in computer game playing. in New Approaches to Board Games Research.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Dynabee

... will not simply fall over, but start precessing around. (The precessing motion is perpendicular to the torque trying to make the gyro fall over.) The axis of the ...

 
 
 
This page was created in 37.8 ms