Monday, 16 March 2009

Claude Shannon - Chess & The Shannon Number


Claude Shannon:

Claude Shannon (1916-2001) was a mathematician and electrical engineer. He is considered the "father of information theory" and also known for founding both digital computer and digital circuit design theory. Chess was a hobby of Shannon's - publishing the important paper Programming a Computer for Playing Chess (1950). Shannon used his knowledge of information theory, and its applications to game theory, to make fortunes at both Blackjack (Las Vegas) and on the stock market. Unfortunately, in the later parts of his life he was affected by Alzheimer's disease. [Wikipedia]

Claude Shannon calculated the possible number of chess moves to be around 10120. This being known as the Shannon Number. The calculation was published in his 1950 scientific paper - Programming a Computer for Playing Chess (download pdf here). The relevant section of the paper quoting the result is below:
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 [4] (remembering the 50 move drawing rule). 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 thiscomputation 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 in fig. 1. This graph was constructed from data given by De Groot, who averaged the number of legal moves in a large number of master games (De Groot, 1946, a). 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!
In comparison to the Shannon Number, the number of atoms in the observable Universe, is estimated to be around 1080.

Reference:
Claude E. Shannon [Bell Telephone Laboratories, Inc., Murray Hill, N.J.]
XXII. Programming a Computer for Playing Chess
Philosophical Magazine, Ser.7, Vol. 41, No. 314 - March 1950.
[Received November 8, 1949]

No comments: