The number of Shannon

a simple proof how deep chess can be

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 10¹²⁰ 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 10⁸¹ . The number of legal positions in chess according to him, however, is about 10⁵⁰ .

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