Shannon number

From Wikipedia, the free encyclopedia
Claude Shannon

The Shannon number, named after the American mathematician Claude Shannon, is a conservative lower bound 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 a move for Black, and a typical game lasting about 40 such pairs of moves.

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
1 20
2 400
3 8,902
4 197,281
5 4,865,609
6 119,060,324
7 3,195,901,860
8 84,998,978,956
9 2,439,530,234,167
10 69,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][5] an upper bound 4×1037 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.

Accurate Estimates[]

John Tromp estimated the number of legal chess positions with a 95% confidence level at , based on an efficiently computable bijection between integers and chess positions.[6]

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 plies (or, equivalently, 40 moves).[7]

See also[]

Notes and references[]

  1. ^ Claude Shannon (1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine. 41 (314). Archived from the original (PDF) on 2020-05-23.
  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 (2015). "On the Number of Positions in Chess Without Promotion". International Journal of Game Theory. 44 (3): 761–767. doi:10.1007/s00182-014-0453-7. S2CID 31972497.
  5. ^ Gourion, Daniel (2021-12-16), An upper bound for the number of chess diagrams without promotion, retrieved 2021-12-18
  6. ^ John Tromp (2021). "Chess Position Ranking". GitHub.
  7. ^ "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.

External links[]

Retrieved from ""