Shannon number

File:ClaudeShannon MFO3807.jpg

The Shannon number, named after the American mathematician Claude Shannon, is a conservative lower bound of the game-tree complexity of chess of 10¹²⁰, based on an average of about 10³ 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 10¹²⁰ possible games, to demonstrate the impracticality of solving chess by brute force, in his 1950 paper "Programming a Computer for Playing Chess".{{Cite journal |last=Shannon |first=Claude E. |author-link=Claude Shannon |date=March 1950 |editor-last=Levy |editor-first=David |title=XXII. Programming a computer for playing chess |url=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 |journal=Philosophical Magazine |series=7 |location=New York, NY |publisher=Springer |volume=41 |issue=314 |pages=256–275 |doi=10.1080/14786445008521796 |isbn=978-1-4757-1970-3 |issn=1941-5982 |archive-url=https://web.archive.org/web/20200523062243/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 |archive-date=2020-05-23}} (This influential paper introduced the field of computer chess.)

Shannon also estimated the number of possible positions, of the general order of $\frac{63!}{32!{8!}^2}$ , or roughly $3.7*10^{43}$ . 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 positions{{Cite web \|title=A048987 \|url=https://oeis.org/A048987 \|website=OEIS}}	Number of checkmates{{Cite web \|title=A079485 \|url=https://oeis.org/A079485 \|website=OEIS}}
class="wikitable" style="text-align: right;"
1	20	0
2	400	0
3	8,902	0
4	197,281	8
5	4,865,609	347
6	119,060,324	10,828
7	3,195,901,860	435,767
8	84,998,978,956	9,852,036
9	2,439,530,234,167	400,191,963
10	69,352,859,712,417	8,790,619,155
11	2,097,651,003,696,806	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 =

Taking Shannon's numbers into account, Victor Allis calculated an upper bound of 5×10⁵² for the number of positions, and estimated the true number to be about 10⁵⁰.{{Cite book |last=Allis |first=Victor |author-link=Victor Allis |url=http://fragrieu.free.fr/SearchingForSolutions.pdf |title=Searching for Solutions in Games and Artificial Intelligence |publisher=Ph.D. Thesis, University of Limburg |year=1994 |isbn=978-90-900748-8-7 |location=Maastricht, The Netherlands}} Later work proved an upper bound of 8.7×10⁴⁵, and showed an upper bound 4×10³⁷ in the absence of promotions.{{Cite journal |last=Steinerberger |first=Stefan |date=August 2015 |title=On the number of positions in chess without promotion |journal=International Journal of Game Theory |volume=44 |issue=3 |pages=761–767 |doi=10.1007/s00182-014-0453-7 |issn=0020-7276 |s2cid=31972497}}{{Cite journal |last=Gourion |first=Daniel |date=12 October 2022 |title=An upper bound for the number of chess diagrams without promotion |url=https://univ-avignon.hal.science/hal-03483904 |journal=ICGA Journal |edition=version 2 |volume=44 |issue=2 |pages=44–55 |arxiv=2112.09386v2 |doi=10.3233/ICG-220210 |access-date=2021-12-18}}

= Lower =

Allis also estimated the game-tree complexity to be at least 10¹²³, "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 10⁸⁰.

= Accurate estimates =

John Tromp and Peter Österlund estimated the number of legal chess positions with a 95% confidence level at $(4.822 \pm 0.028) \times 10^{44}$ , based on an efficiently computable bijection between integers and chess positions.{{Cite web |last=Tromp |first=John |year=2022 |title=Chess Position Ranking |url=https://github.com/tromp/ChessPositionRanking |website=GitHub}}

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 10⁴⁰ 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).{{Cite AV media |url=https://www.youtube.com/watch?v=Km024eldY1A |title=How many chess games are possible? |date=24 July 2015 |last=Grime |first=James |type=Video |publisher=Numberphile |via=YouTube}} Dr. James Grime talking about the Shannon Number and other chess stuff (films by Brady Haran). MSRI, Mathematical Sciences.