The Shannon number: how many chess games are possible?

The Shannon number is often quoted to illustrate the richness of chess. It is also an excellent basis for working on powers of 10, scientific notation and orders of magnitude, from secondary school upwards. You still need to know where it comes from, what exactly it measures, and what it does not measure.

Shannon number

A cautious estimate, about 10¹²⁰, of the number of possible chess games, proposed by the American mathematician and engineer Claude Shannon in the paper “Programming a Computer for Playing Chess”, published in 1950 in the journal Philosophical Magazine.

The Shannon number: where does the calculation come from?

Claude Shannon (1916–2001) is known as the founder of information theory. In 1950 he published one of the first papers on programming a computer to play chess. To show that a machine cannot simply calculate every sequence of moves, he makes a quick estimate:

1. In a typical position, there are about 30 legal moves. This number stays roughly constant for much of the game.
2. A White move followed by a Black move therefore gives about 30 × 30 = 900 possibilities, which Shannon rounds to 10³.
3. A typical game lasts about 40 moves (40 White moves and 40 Black moves) until a player resigns.
4. The number of sequences of moves is therefore about (10³)⁴⁰ = 10¹²⁰.

Shannon adds that a machine examining one variation per microsecond would take more than 10⁹⁰ years to calculate its first move. He concludes that a chess program must evaluate positions and choose which variations to explore, as a human player does.

Games and positions: two different numbers

The number of games (sequences of moves) must not be confused with the number of positions (arrangements of the pieces on the chessboard). The same position can be reached by millions of different games.

Shannon estimated the number of positions with the formula 64! / (32! × 8!² × 2!⁶), which counts the ways of arranging the 32 starting pieces on the 64 squares; the result is about 4.6 × 10⁴², which he rounds to “about 10⁴³”. John Tromp's modern estimate, (4.82 ± 0.03) × 10⁴⁴ legal positions, is obtained differently: by randomly sampling two million positions from a set that can be counted, then checking which ones are actually reachable in a game, with the help of Peter Österlund for the computer analysis.

The first moves: an exact count

At the start of the game, an exact count is possible. White has 20 possible moves (16 pawn moves and 4 knight moves). Black has the same. This gives:

Values recalculated by program from the starting position (counting all sequences of legal moves).

After only two moves by each side, there are already more than 197,000 possible sequences. The multiplying factor then increases, because the pieces come out and have more choices: this is what justifies the assumption of about thirty moves per position.

Where does the estimate of 10¹²³ come from?

In 1994, the Dutch researcher Victor Allis redid the calculation with different assumptions: about 35 possible moves per position, and games of 80 plies (40 moves by each side). This gives 35⁸⁰. To write it as a power of 10, you use the common logarithm: 80 × log(35) ≈ 80 × 1.544 ≈ 123.5. Hence the order of magnitude of 10¹²³. The method is exactly Shannon's; only the parameters change, which shows how much the result depends on the assumptions.

With Shannon's exact parameters, incidentally, 900⁴⁰ is about 10¹¹⁸ and not 10¹²⁰: it is the rounding of 900 up to 1,000 that gives the neat round figure. For an order of magnitude this gigantic, the difference has no practical importance.

How to explain it in class

The Shannon number is ideal for working on powers of 10, which are on the 4e curriculum (age 13–14). A few ideas:

• Write the number: 10¹²⁰ is written with a 1 followed by 120 zeros. You can have pupils write it on the board… and time how long it takes.
• Calculate with powers: (10³)⁴⁰ = 10^{3 × 40} = 10¹²⁰ is a direct application of the rule (a^m)ⁿ = a^{m × n}.
• Compare orders of magnitude: 10¹²⁰ divided by 10⁸⁰ gives 10⁴⁰. Even if every atom in the Universe were a computer, each would still have to process 10⁴⁰ games.
• Discuss the assumptions: why 30 moves per position? why 40 moves per game? What difference does a 60-move game make? (Answer: (10³)⁶⁰ = 10¹⁸⁰.)

The number of grains on Sissa's chessboard, about 1.8 × 10¹⁹, looks tiny beside it: comparing the two is a good exercise. See the calculation for Sissa's chessboard.

Can chess be “solved”?

To solve a game is to know with certainty what result (a win for White, a win for Black or a draw) perfect play by both sides gives. The Shannon number shows that this cannot be done by exploring all the games. Computers have nonetheless solved all positions with few pieces, thanks to endgame tablebases. To find out where the question stands, Le Palais des Échecs has asked whether chess could ever be solved.

The Shannon number and the other big numbers of the chessboard

The chessboard is a small factory of big numbers: 2⁶⁴ − 1 grains for Sissa, more than 26 trillion closed knight's tours, 92 solutions to the eight queens, 204 squares… Find them on our page the great chessboard puzzles.