Shannon number

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". (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 . 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, 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,

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 (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).

See also * [[combinatorial-explosion]] * [[game-complexity]] * [[go-and-mathematics]] * [[solving-chess]]

Notes and references ## External links * [Mathematics and chess](http://mathworld.wolfram.com/Chess.html)