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 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.
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.[4] Recent results[5] improve that estimate, by proving an upper bound of 8.7x1045, and showing[6][7] 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 and Peter Österlund estimated the number of legal chess positions with a 95% confidence level at , based on an efficiently computable bijection between integers and chess positions.[5]
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).[8]
^ abJohn Tromp (2022). "Chess Position Ranking". GitHub.
^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.
^Gourion, Daniel (2021-12-16), An upper bound for the number of chess diagrams without promotion, arXiv:2112.09386, retrieved 2021-12-18
^"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
Mathematics and chess
April 18, 2023
shannon, number, named, after, american, mathematician, claude, shannon, conservative, lower, bound, game, tree, complexity, chess, 10120, based, average, about, possibilities, pair, moves, consisting, move, white, followed, move, black, typical, game, lasting. 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 Claude Shannon Contents 1 Shannon s calculation 2 Tighter bounds 2 1 Upper 2 2 Lower 2 3 Accurate estimates 3 Number of sensible chess games 4 See also 5 Notes and references 6 External linksShannon s calculation EditShannon 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 64 32 8 2 2 6 displaystyle scriptstyle frac 64 32 8 2 2 6 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 2 Number of checkmates 3 1 20 02 400 03 8 902 04 197 281 85 4 865 609 3476 119 060 324 10 8287 3 195 901 860 435 7678 84 998 978 956 9 852 0369 2 439 530 234 167 400 191 96310 69 352 859 712 417 8 790 619 15511 2 097 651 003 696 806 362 290 010 90712 62 854 969 236 701 747 8 361 091 858 95913 1 981 066 775 000 396 239 346 742 245 764 21914 61 885 021 521 585 529 23715 2 015 099 950 053 364 471 960After 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 EditUpper 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 4 Recent results 5 improve that estimate by proving an upper bound of 8 7x1045 and showing 6 7 an upper bound 4 1037 in the absence of promotions Lower 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 Accurate estimates Edit John Tromp and Peter Osterlund estimated the number of legal chess positions with a 95 confidence level at 4 822 0 028 10 44 displaystyle 4 822 pm 0 028 times 10 44 based on an efficiently computable bijection between integers and chess positions 5 Number of sensible chess games EditAs 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 8 See also Edit Chess portalSolving chess Go and mathematics Game complexity Combinatorial explosionNotes and references Edit Claude Shannon 1950 Programming a Computer for Playing Chess PDF Philosophical Magazine 41 314 Archived from the original PDF on 2020 05 23 A048987 Oeis A079485 Oeis 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 a b John Tromp 2022 Chess Position Ranking GitHub 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 Gourion Daniel 2021 12 16 An upper bound for the number of chess diagrams without promotion arXiv 2112 09386 retrieved 2021 12 18 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 EditMathematics and chess Retrieved from https en wikipedia org w index php title Shannon number amp oldid 1128780873, wikipedia, wiki, book, books, library,
