Shannon number
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 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
Upper, positions
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
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
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 plies (or, equivalently, 40 moves).[9]
See also
Notes and references
- ↑ Shannon, Claude E. (March 1950). Levy, David. ed. "XXII. Programming a computer for playing chess". Philosophical Magazine. 7 (New York, NY: Springer) 41 (314): 256–275. doi:10.1080/14786445008521796. ISBN 978-1-4757-1970-3. ISSN 1941-5982. http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf.
- ↑ "A048987". https://oeis.org/A048987.
- ↑ "A083276". https://oeis.org/A083276.
- ↑ "A079485". https://oeis.org/A079485.
- ↑ Allis, Victor (1994). Searching for Solutions in Games and Artificial Intelligence. Maastricht, The Netherlands: Ph.D. Thesis, University of Limburg. ISBN 978-90-900748-8-7. http://fragrieu.free.fr/SearchingForSolutions.pdf.
- ↑ 6.0 6.1 Tromp, John (2022). "Chess Position Ranking". https://github.com/tromp/ChessPositionRanking.
- ↑ 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.
- ↑ Gourion, Daniel (12 October 2022). "An upper bound for the number of chess diagrams without promotion". ICGA Journal 44 (2): 44–55. doi:10.3233/ICG-220210. https://univ-avignon.hal.science/hal-03483904. Retrieved 2021-12-18.
- ↑ 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
 |  |
