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. His influential 1950 paper on it, "Programming a Computer for Playing Chess", introduced the field of computer chess.

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.

Shannon also estimated the number of possible positions, of the general order of (where the ! represents the factorial and the underlined superscript represents a falling factorial), or roughly . 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 Number of possible positions Number of checkmates 1 20 20 0 2 400 400 0 3 8,902 5,362 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. Later work proved an upper bound of 8.7×1045, and showed an upper bound 4×1037 in the absence of promotions.

Accurate, positions 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.

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 (i.e., 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).

Shannon number

Bron en licentie