# Shannon number

Claude Shannon

The Shannon number, named after Claude Shannon, is an estimated lower bound on the game-tree complexity of chess. Shannon calculated it as an aside in his 1950 paper "Programming a Computer for Playing Chess".[1] (This influential paper introduced the field of computer chess.) He notes:

 “ With chess it is possible, in principle, to play a perfect game or construct a machine to do so as follows: One considers in a given position all possible moves, then all moves for the opponent, etc., to the end of the game (in each variation). The end must occur, by the rules of the games after a finite number of moves (remembering the 50 move drawing rule).[2] Each of these variations ends in win, loss or draw. By working backward from the end one can determine whether there is a forced win, the position is a draw or is lost. It is easy to show, however, even with the high computing speed available in electronic calculators this computation is impractical. In typical chess positions there will be of the order of 30 legal moves. The number holds fairly constant until the game is nearly finished as shown [...] by De Groot, who averaged the number of legal moves in a large number of master games. Thus a move for White and then one for Black gives about 103 possibilities. A typical game lasts about 40 moves to resignation of one party. This is conservative for our calculation since the machine would calculate out to checkmate, not resignation. However, even at this figure there will be 10120 variations to be calculated from the initial position. A machine operating at the rate of one variation per micro-second would require over 1090 years to calculate the first move! ”

Shannon also estimated the number of possible positions, "of the general order of $\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. Taking these 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.[3] Recent results[4] improve that estimate, by proving an upper bound of only 2155, which is less than 1046.7.

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 estimated to be between 4×1079 and 1081.