Shannon number

The Shannon number, named after the American mathematician Claude Shannon, is a conservative lower bound (not an estimate) of the game-tree complexity of chess of 10120, based on an average of about 103 possibilities for a pair of moves consisting of a move for White followed by one for Black, and a typical game lasting about 40 such pairs of moves.

Claude Shannon

Shannon's calculation

Shannon showed a calculation for the lower bound of the game-tree complexity of chess, resulting in about 10120 possible games, to demonstrate the impracticality of solving chess by brute force, in his 1950 paper "Programming a Computer for Playing Chess".[1] (This influential paper introduced the field of computer chess.)

Shannon also estimated the number of possible positions, "of the general order of , or roughly 1043". This includes some illegal positions (e.g., pawns on the first rank, both kings in check) and excludes legal positions following captures and promotions.

Number of plies
(half-moves)		Number of
possible games
120
2400
38,902
4197,281
54,865,609
6119,060,324
73,195,901,860
884,998,978,956
92,439,530,234,167
1069,352,859,712,417

After each player has moved a piece 5 times each (10 ply) there are 69,352,859,712,417 possible games that could have been played.

Tighter bounds

Upper

Taking Shannon's numbers into account, Victor Allis calculated an upper bound of 5×1052 for the number of positions, and estimated the true number to be about 1050.[2] Recent results[3] improve that estimate, by proving an upper bound below 2155, which is less than 1046.7 and showing[4] an upper bound 2×1040 in the absence of promotions.

Lower

Allis also estimated the game-tree complexity to be at least 10123, "based on an average branching factor of 35 and an average game length of 80". As a comparison, the number of atoms in the observable universe, to which it is often compared, is roughly estimated to be 1080.

Number of sensible chess games

As a comparison to the Shannon number, if chess is analyzed for the number of "sensible" games that can be played (not counting ridiculous or obvious game-losing moves such as moving a queen to be immediately captured by a pawn without compensation), then the result is closer to around 1040 games. This is based on having a choice of about three sensible moves at each ply (half-move), and a game length of 80 ply.[5]

gollark: That's you. I was very clear.
gollark: ↓ you, as a result
gollark: Allegedly.
gollark: He lies.
gollark: Just autogenerate rhythms.

See also

Notes and references
  1. Claude Shannon (1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine. 41 (314).
  2. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 978-90-900748-8-7.
  3. John Tromp (2010). "John's Chess Playground".
  4. S. Steinerberger (2014). "International Journal of Game Theory". International Journal of Game Theory. 44 (3): 761–767. doi:10.1007/s00182-014-0453-7.
  5. "How many chess games are possible?" Dr. James Grime talking about the Shannon Number and other chess stuff (films by Brady Haran). MSRI, Mathematical Sciences.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.