Shannon number
From Wikipedia, the free encyclopedia
The Shannon number, 10120, is an estimated lower bound on the game-tree complexity of chess, calculated by information theorist Claude Shannon as an aside in his 1950 paper "Programming a Computer for Playing Chess ".[1]. (This influential paper introduced the field of computer chess.) Shannon 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 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]
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 Universe, to which it is often compared, is estimated to be between 4x1079 and 1081.
[edit] Other uses
The term "Shannon number" has been informally suggested as an analog to the Erdős number [4].
[edit] Notes and references
- ^ Claude Shannon (1950). "Programming a Computer for Playing Chess". Philosophical Magazine 41 (314).
- ^ In chess played according to the laws of the Fédération Internationale des Échecs, the fifty move rule and the related draw due to threefold repetition of a position require an appeal 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 rook and bishop versus rook endgame, 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 9090074880.
- ^ Andrew W. Eckford (2007). "What's your Shannon number?". IEEE Information Theory Society Newsletter 57 (1).
