Shannon number
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 
, 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.
See also[edit]
Notes and references[edit]
- ^ Claude Shannon (1950). "Programming a Computer for Playing Chess". Philosophical Magazine 41 (314).
- ^ In chess played according to the rules of chess by the Fédération Internationale des Échecs, the fifty-move rule and the related draw due to threefold repetition of a position require a claim to be made by one of the players. So if neither player claims the draw, a game may go on indefinitely. (See [1], discussing the rapid chess game Fressinet-Kosteniuk, Château de Villandry 2007, won by Kosteniuk in 237 moves, the last 116 moves of which were in a pawnless endgame with a rook and bishop versus a rook, in which Fressinet did not try to claim a draw because he was not recording the moves, as the rules normally require in order to claim a draw by virtue of the 50-move rule.) This does not affect the argument that it is in principle possible to play a perfect game, because all searches involving the repetition of a position can be immediately marked as draws without affecting the correctness of the evaluation (because if either player could force a win they could do so without repeating the position), and since there are a finite number of positions eventually one must be repeated or the game must come to an end.
- ^ Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0.
- ^ John Tromp (2010). "John's Chess Playground".
