How many possible chess games are there? (Part 1)

This is a bit of a trick question, because it’s actually downright near impossible to calculate. Some outstanding minds have addressed this problem, including Claude Shannon, the “father of information theory.” Shannon wrote a seminal paper in 1950, the first to formally describe how a computer could be programmed to play chess. (Alan Turing, the founder of modern computer science, was likely the first to have a full chess program a few years earlier, but he never disseminated it.) In the introduction of the paper, Shannon estimated that the total number of unique chess games is a mind-boggling 10¹²⁰, a number now known as the Shannon Number. He actually arrived at this number quite simply, as follows. Based on a study of master chess games, the average length of a game was 40 moves, and the average number of legal moves at any given turn was around 30. So, if on any move white has about 30 possibilities for a move, and then black does, too, that gives 900 possible scenarios for one full move. Shannon rounded this to 1000, which would correspond to 31-32 possible moves per turn. Over the 40 moves of a typical game, the total possibilities are 1000⁴⁰ = 10^(3×40) = 10¹²⁰.

The Shannon Number is unfathomably large (and possibly a few orders of magnitude off). Consider that a very sound estimate for the total number of atoms in the visible universe is 10⁸⁰. This means that if for each unique chess game an atom was used to count it, by the time we ran out of atoms in the universe we would only be 1/10⁴⁰th complete! But, this fraction is now so ridiculously small it doesn’t make much sense, either.

What is large enough that this small fraction of it (10^-40) would still be something meaningful to us? We need 10⁴⁰ somethings, such that just 1 of those somethings is still, well, something. So, the number of atoms that comprise our earth is well-estimated to be around 1.4 x 10⁵⁰, which is actually a billion times too large for our purposes. It is actually rather difficult to come up with a good physical reference for 10⁴⁰, but I think I’ve found a reasonable one: the total molecules of water in Lake Winnipeg in Manitoba, Canada is right around 10⁴⁰. (Or, if you prefer, it’s twice the number of water molecules in Lake Tahoe, and 3/5 the amount of water in Lake Erie.)

So, in counting up all the possible chess games, we are using the atoms of the universe as counters, but we run out of these pretty quickly. So, every time we go through the universe’s atoms, then we take out one molecule of water from Lake Winnipeg and start from the beginning again with the atoms of the universe. This is one way to make sense of the Shannon Number.

This is still not quite good enough, though, because we don’t have a good feel for just how small a molecule of water is and how huge is the number of them in Lake Winnipeg. One more thought should help: if we counted one molecule of those 10⁴⁰ in the lake every nanosecond (10^-9  seconds or 1 billionth of a second), then it would only take us 22 trillion ages of the universe (15 billion years) to empty the lake.

A photo from 1950 where Claude Shannon (right) demonstrates the first digital chess problem solver (which could only handle up to six pieces) to former world chess champion Edward Lasker.

So, now can we can reformulate a bit our understanding of the 10¹²⁰ possible unique chess games: there are at least 10⁴⁰ possible games for every atom in the universe, and if each of those 10⁴⁰ games for the first atom of the universe was played in one nanosecond, it would take 22 trillion ages of the universe to play them all (and you would also have one game for every molecule of water in Lake Winnipeg). Only then could you move on to the games associated with the second atom of the universe, and then the third, and then the….10⁸⁰th atom!

The feeling you and your head are now experiencing, if you’ve tried to understand these numbers and analogies, is part of a sublime experience. The sublime has been described as a hint of a representation of the unrepresentable. If anything counts as being unrepresentable, it’s the Shannon Number, and the notion that there are 10¹²⁰ possible chess games is truly sublime!

In Part 2, we will look more at the problems of calculating the total possible games of chess and why Shannon resorted to a simple approximation.

Photo credit: The Shannon and Lasker photo is unaltered and courtesy of the chess programming wiki.

Advertisements