Shannon Number - Wikipedia

Estimate of number of possible chess games

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

[edit]

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 6331 (8!)-2 (where the ! represents the factorial and the underlined superscript represents a falling factorial), or roughly 3.7×1034. 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[2]	Number of possible positions[3]	Number of checkmates[4]
1	20	20	0
2	400	400	0
3	8,902	5362	0
4	197,281	72,078	8
5	4,865,609	822,518	347
6	119,060,324	9,417,681	10,828
7	3,195,901,860	96,400,068	435,767
8	84,998,978,956	988,187,354	9,852,036
9	2,439,530,234,167	9,183,421,888	400,191,963
10	69,352,859,712,417	85,375,278,064	8,790,619,155
11	2,097,651,003,696,806	726,155,461,002	362,290,010,907
12	62,854,969,236,701,747	8,361,091,858,959
13	1,981,066,775,000,396,239	346,742,245,764,219
14	61,885,021,521,585,529,237
15	2,015,099,950,053,364,471,960

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

[edit]

Upper, positions

[edit]

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.[5] Later work proved an upper bound of 8.7×1045,[6] and showed an upper bound 4×1037 in the absence of promotions.[7][8]

Accurate, positions

[edit]

John Tromp and Peter Österlund estimated the number of legal chess positions with a 95% confidence level at (4.822±0.028)×1044, based on an efficiently computable bijection between integers and chess positions.[6]

Lower, complexity

[edit]

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

[edit]

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).[9]

See also

[edit]

• Solving chess
• Go and mathematics
• Game complexity
• Combinatorial explosion

Notes and references

[edit]

1. ^ Shannon, Claude E. (March 1950). Levy, David (ed.). "XXII. Programming a computer for playing chess" (PDF). Philosophical Magazine. 7. 41 (314). New York, NY: Springer: 256–275. doi:10.1080/14786445008521796. ISBN 978-1-4757-1970-3. ISSN 1941-5982. Archived from the original (PDF) on 2020-05-23. {{cite journal}}: ISBN / Date incompatibility (help)
2. ^ "A048987". OEIS.
3. ^ "A083276". OEIS.
4. ^ "A079485". OEIS.
5. ^ Allis, Victor (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Maastricht, The Netherlands: Ph.D. Thesis, University of Limburg. ISBN 978-90-900748-8-7.
6. ^ a b Tromp, John (2022). "Chess Position Ranking". GitHub.
7. ^ Steinerberger, Stefan (August 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. ISSN 0020-7276. S2CID 31972497.
8. ^ Gourion, Daniel (12 October 2022). "An upper bound for the number of chess diagrams without promotion". ICGA Journal. 44 (2) (version 2 ed.): 44–55. arXiv:2112.09386v2. doi:10.3233/ICG-220210. Retrieved 2021-12-18.
9. ^ Grime, James (24 July 2015). How many chess games are possible? (Video). Numberphile – via YouTube. Dr. James Grime talking about the Shannon Number and other chess stuff (films by Brady Haran). MSRI, Mathematical Sciences.

External links

[edit]

• Mathematics and chess

v t e Large numbers
Examples innumerical order	Hundred Thousand Ten thousand Hundred thousand Million Billion Trillion Quadrillion Quintillion Sextillion Septillion Octillion Nonillion Decillion Eddington number Googol Shannon number Googolplex Skewes's number Moser's number Graham's number TREE(3) SSCG(3) BH(3) Rayo's number
Expressionmethods	Notations Scientific notation Knuth's up-arrow notation Conway chained arrow notation Steinhaus–Moser notation Operators Hyperoperation Tetration Ackermann function Grzegorczyk hierarchy Fast-growing hierarchy Slow-growing hierarchy Hardy hierarchy Veblen function
Related articles(alphabetical order)	Busy beaver Extended real number line Indefinite and fictitious numbers Infinitesimal Largest known prime number List of numbers Long and short scales Number systems Number names Orders of magnitude Power of two Power of three Power of 10 Sagan Unit
Names History