# Shannon number

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 ${\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 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×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 ${\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

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]