The number of Shannon

a simple proof how deep chess can be

Shannon

Claude Shannon

photo: Wikipedia

Claude Elwood Shannon (1916-2001) was a famous electrical engineer and mathematician, remembered as “the father of information theory”. He was fascinated by chess and was the first one to calculate with precision the game tree complexity of chess i.e. the number of possible chess games. He based his calculation on a logical approximation that each game has an average of 40 moves and each move a player chooses between 30 possible moves. That makes a total of 10120 possible games. This number is known as the number of Shannon.

To a similar conclusion came Peterson in 1996. An interesting comparison is the estimation of the total numbers of atoms in the universe 1081 . The number of legal positions in chess according to him, however, is about 1050 .

All these calculations will suffer slight changes when we apply new rules to chess, such as the Sofia rule or further estimation of the effect of en-passant. However, the numbers are close enough to show you how deep chess can be.

Other game tree complexities (log game tree):

Tic tac toe 5


Connect Four 21


Othello 58


Chess 120


Backgammon 140


Connect six 140


Go 766

Number of positions in chess after n moves

Chess mathematics can be fascinating. At first sight chess seems to be easy to calculate. It has logical patterns and finite board space. However, the simplest questions may require serious mathematical skills.

A good example is the number of possible positions after n moves, n being 1, 2, 3, etc. After the first move there are exactly 20 positions, after the second, there are 400. White has a choice of 20 first moves, Black the same number of replies, making 400 different possible positions after one move for each color. From here on it is difficult to keep on counting since the number is rapidly growing. After the third move we have 5362 positions, and after the fourth the number is 71852. A really large number for 8×8 board!

These numbers are a good back up of the complexity of The number of Shannon. In 1889 Cunningham got close to the number of moves after the 4th move, stating they are 71782. Fabel got even closer in 1895, he calculated 71870 possible moves. The first one to find the correct number, 71852, was C. Flye St. Marie in 1903.

As far as the Chessdom team knows, there are estimations of the number of positions after the 5th and the 6th moves. They are 809798 and 9132484 respectively. However, we would like to receive confirmation or a more correct information from our mathematician readers. Do not forget to include special moves like en passant .