The Limits of Comprehension

The Limits of Comprehension

Shannon Number

The Shannon Number, named after Claude Shannon, the father of information theory. The estimated number has definitely caught my attention.

In 1950 he wrote a paper called Programming a Computer for Playing Chess. 

This is based on an average of $10^3$ move options per turn and a typical game of 40 moves.  

Shannon estimated there are at least 10^120 possible chess games. It’s a number beyond human comprehension.

It exceeds the number of atoms in the observable universe ($10^{80}$) by over a billion billion billion billion times.

It's fascinating to observe how rapidly the number of potential game positions grows after each move.

At the beginning of a game, each player has 20 possible moves (16 pawn moves and 4 knight moves per side).

After both players have made their first move, there are already 400 possible moves to consider.

After each move, the number of possibilities grows exponentially due to the branching factor, the number of potential moves at any given position.

It's useful to understand how chess moves generate exponential possibilities. Each individual move by a player is called a half-move (or ply), and a full move consists of two half-moves...1 by White and 1 by Black.

 The table below illustrates this exponential growth, showing the number of possible games after a certain number of half-moves:

A half-move = 1 single move made by one player, while a "move" in chess terms involves both players taking their turn. 

The table below shows how quickly the number of possible games explodes with each move, growing exponentially.

Cliche fun fact which is useful for visualisation of differences:

Million:   10^6 seconds =  12 days  

Billion:    10^9 seconds = 31 years

Trillion:   10^12 seconds = 31,680 years

All 30-digits numbers lie between 10^29 and 10^30 (except 10^29 itself).  We get an idea, but is hard to visualize it. It's the same percentage increase rate as from 10 to 100. But 10 and 100 are easier to visualize because we deal with this amount of things in everyday life. We will compare now how many things are relatable with the number of moves and possible games.

Putting the number into perspective

As numbers grow, the number of digits becomes more important than the digits themselves. For easier understanding we will round the number to the number of digits because at that scale is very insignificant difference.

Example:  10^1 = seconds in 1 minute, because 60 is between 10 and 99

Move 1 - 20 games:  A pack of cigarettes contains 20 cigarettes.

Move 2 - 400 games:  Common jigsaw puzzle contains 400 pieces.

Move 3 - 8,902 games:  Mount Everest's highest point is 8,848 meters.

Move 4 - 197,291 games:  Half the distance to the Moon is around 192,220 km.

Move 5 - 10^6 games:  On average, the human eye blinks 4,200,000 times a year.

Move 6 - 10^8 games:  The number of seconds passed during 6 years is 189,216,000.

Move 7 - 10^9 games:  Human heart beats over 3,000,000,000 times during lifetime.

Move 8 - 10^10 games:  It takes 50 billion steps to walk around the Earth.

Move 9 - 10^12 games:  

If you earned 100$ per hour, 24/7, with no expenses, it would take 2,739,726 years to save 2.4 trillion dollars.

If you earned 25$ million per year with no expenses, it would take 96,000 years to save 2.4 trillion dollars.

Move 10 - 10^13 games:  Around 14.3 trillion photos exist in total.

Move 11 - 10^15 games:  The Niagara Falls use up a quadrillion liters in over 200 years.

Move 12 - 10^16 games:  There are about 10^16 ants on Earth.

Move 13 - 10^18 games:  A single drop of water contains 1.7 x 10^18 water molecules.

Move 14 - 10^19 games:  The distance between Milky Way and Andromeda galaxy is 18 x 10^19 kilometers.

Move 15 - 10^21 games:  There are 10^21 grains of sand on earth.

...

Move 40 - 10^120 games:  The number of hydrogen atoms needed to completely fill the observable universe is 10^113.

If each hydrogen atom in the observable universe were assigned 10^7 (10 million) unique chess games, it would reach 10^120 possible games.  

Here’s another way to think about it: if every human on Earth (about 8 billion people) played 1 chess game per 1 second in a period of  10^100 years, it won't be even close to 1% of  all possible games of chess.

That’s longer than the estimated lifespan of the universe itself (13.8 billion years).

Average legal moves per turn

The tree diagram maps all possible moves and outcomes. When you move, computer records it, analyses winning possibilities and responds.

The branching factor is often cited as 35, likely estimated decades ago by analyzing random game positions. While it's reasonable in practice, it's not an exact figure.

The total number of moves played was 194,389,820 (76.5 per game) and the total number of available moves was 6,039,013,721 giving an average of about 31.1 per move.

As pieces are captured and the game advances, the remaining pieces decrease, but the available spaces for movement increase, so the average legal moves per turn are still constant (roughly speaking): 

This growth in possibilities highlights the complexity of chess. Unlike many other games, the branching factor in chess...the number of possible moves at each turn grows exponentially. This is why modern chess engines, despite their computing power, don’t attempt to calculate every single move. Instead they focus on evaluating the most promising ones. 

Engines like Stockfish and AlphaZero rely on heuristics (rules of thumb) and advanced techniques such as: Monte Carlo Tree Search and neural networks. These allow them to evaluate positions and prioritize promising moves without needing to explore every possibility. 

For us mortals, it’s impressive to think that this level of complexity emerges from such simple rules: an 8x8 board and a handful of pieces with defined movement patterns. So if you blunder on move 10, it’s just 1 game among googles of games . Every position is part of an enormous number of possibilities, and your next move will probably lead to a game that’s never been played before.

Now, imagine chess on a 12x12 board or variants (like Bughouse) with alternative pieces like

Amazon, Elephant or Archbishop...

If standard chess already outpaces that much complexity, what happens when we add more dimensions? At what point does a game become so complex that even the best computers struggle to evaluate a single position?

If chess is already beyond human calculation, how much deeper can we go when we add a few rules, introduce new pieces and expand the board?

Maybe chess is just one of the first moves in a far greater game of complexity. And if no intelligence (human or artificial) can ever truly solve it...maybe the real challange isn't winning, but mapping the game.

Game tree complexities for other games (log base 10): 

Tic Tac Toe: 5

Kalah: 18

Connect Four: 21

3D Tic Tac Toe: 34

Chess: 120

Backgammon: 144

Japanese chess (Shogi): 226

Go: 505

Infinite Chess: Infinite