How Many Chess Games are Possible?

How Many Chess Games are Possible?

Here is a fun question: how many different games of chess are possible? Counting the number of possible chess games is quite hard, as the numbers are large and chess board positions can be quite complicated. In this note we will try to estimate the number of possible short games of chess.

Long games with many possibilities

This allows Labelle to bound the number of possible long chess games to the range 10²⁹²⁴¹ to 10³⁴⁰⁸².

We will restrict ourselves to typical and short chess games.

Warmup: the number of typical games by the Fermi problem method

The Fermi problem method is to propose an approximate break-down of what we want to know into arithmetic over a few other things we can in turn try to estimate. The trick is to pick a arithmetic form that is both simple enough to calculate over and plausible enough to be a good estimate.

For the chess problem we propose the estimate number_of_typical_games ~ typical_number_of_options_per_movetypical_number_of_moves_per_game. This equation is subjective, in that it isn’t yet justified beyond our opinion that it might be a good estimate. It is then a matter of finding usable values for typical_number_of_moves_per_game and typical_number_of_options_per_move.

We also need to know how many different possible moves a player is typically considering. We get an estimate by examining a puzzle from Lichess.org:

We can work out that black has 46 legal moves by counting. We write this as 10^log10(46) ~ 10^1.66 for easier calculation.

Then our Fermi estimate is that there are easily on order of (10^1.66)¹⁰⁰ = 10¹⁶⁶ typical games of chess. This has some of the grace I tried to describe in “The Joy of Calculation”.

This sort of argument was famously used by Claude Shannon to argue a lower bound of 10¹²⁰ possible chess games (ref).

These estimates, while useful, are subjective, far apart, and sensitive to the subjective ad-hoc inputs. We will address this in the next sections.

The Knuth path product estimate

Estimating from a single game

To keep things simple, we are going limit ourselves to “short chess games.” We define “short” as games taking no more than 100 half moves to achieve an end condition (win, lose, stalemate, or draw by the rules of chess as implemented in the Python chess package- including insufficient material for mate detection). We can sample from this population of games by generating games through the process of picking legal moves uniformly at random, and rejecting samples that exceed the half move limit before achieving an ending condition.

We consider a single sample game g generated by generating legal moves uniformly at random.

End of sample game (move 43, White checkmates Black)

Given our sample working chess game “g” we then replace our Fermi estimate of

   typical_number_of_options_per_movetypical_number_of_moves_per_game

with Knuth’s path product estimator

   p(g) = ∏i number_of_legal_moves_in_position(g[i])

where g[i] is the i-th position in the single game g we are examining.

If the sample game was exactly typical (i.e. lasted for exactly typical_number_of_moves_per_game half moves and always had typical_number_of_options_per_move legal moves per position) these two calculations would be identical. Things are rarely so perfectly “typical”, so we expect this new estimate to often be over or under the original Fermi method estimate (depending on which game we use as our working example).

Knuth proved this path product estimate is quite good in the following technical sense.

Let G be the set of all possible short chess games. We want to know |G|, the size of G. The issue is |G| is so large that we can not hope to directly enumerate all of the elements of G to directly perform the counting.

Theorem: Eg in G, under uniform move distribution[p(g)] = |G| where E[] is the expected value operator

Knuth considered this surprising enough that he wrote: “We shall consider two proofs, at least one of which should be convincing.”

The point is: we can approximate the average on the left side of the equations, and this now means we can approximate |G|.

In our case our new single game based path product estimate for the total number of possible short chess games is: 10^116.96179. As we are dealing with large numbers we will content ourselves with “order of magnitude” measurements and just reporting an approximation with an integer exponent. So we will round the exponent and take our estimate as 10¹¹⁷.

Estimating from many games

The usual way to improve expected value estimates is averaging more examples. We consider a sample of 10000 independently generated games.

In this sample the log 10 of our different size estimates are distributed as follows.

The average estimate from this sample (which we hope is not too far from the average of the population it is being drawn from) is 10¹⁵¹.

Unfortunately, the observed standard error (or observed uncertainty in our estimate of the average) is just as large. In this circumstance this means we shouldn’t consider the sample reliable.

A larger sample

We try to solve this variance issue by using an independent second larger sample from a larger simulation run.

We can look at subsets of our larger (size 1000000) sample to explore how the estimate behaves with respect to varying sample size.

The initial jumps and trend-like behavior of this graph is the sample becoming big enough to find important rare large examples. Without additional arguments we can’t be certain there are not more of these un-encountered large estimates for any reasonable sample size, meaning there are some remaining risks in this estimate. We are looking for this estimate to stabilize at a given value. We also are looking for the ratio of the standard error (observed uncertainty in the estimate) over the estimate to drop below 1. This ratio is called the coefficient of variation, and we plot this below.

We want the coefficient of variation to be smaller than 1. This would imply the sample estimate is at least not contradicting itself. We are starting to see this as we move to the larger sample sizes.

The average estimate from this larger sample sample is again 10¹⁵¹. That will be our claimed estimate for the number of possible short chess games.
As a check, our two sample based estimates rendered to more digits in the exponent are:

• Smaller sample estimate is 10^150.94
• Larger sample estimate is 10^151.27.

How reliable is the path sampling scheme?

The Knuth path sampling scheme appears to be quite reliable. The main risk, as mentioned by Knuth, is high unobserved variance. This is the worrying possibility that our sample is unrepresentative because there is something large out there we have not yet seen.

In the case where we know there are no large monster games hiding, the procedure is preternaturally accurate. For example, the graph below is the percent error in estimating the number of chess games that reach at least the first k-ply for k equals 1 through 15. For these very short games the exact values of the counts are reported in The On-Line Encyclopedia of Integer Sequences A048987, allowing us to check our results.

The right-most point on the graph indicates that we are off by about 1/2 a percent in estimating the size of a population of 2015099950053364471960 possible games. This is using a sample of only size 100000, which is much smaller than the population size of 2015099950053364471960 we are estimating.

Initially the number of games is growing almost exponentially, so is quite regular and easy to estimate. However, as we see in the next graph, the Knuth path sample estimator is much closer to the actual counts than any simple exponential trend. The minimal exponential trend, even if fit to the entirety of the known data, is routinely off by over +- 30 percent even in its own fitting region.

Conclusion

We approximated the number of possible short chess games with both the Fermi problem method and Knuth’s path-product estimation method. Our final estimate was that it is plausible that there are on the order of 10¹⁵¹ possible short games of chess.

When we switch from the Fermi problem method to the Knuth path-product method we:

• Avoid having to guess a useful subjective arithmetic form.
• Become more able to incorporate the exact rules of the system we are exploring.
• Remove the need for subjective estimated inputs.
• Can try to “buy reliability” by building larger samples.

And, of course, the methods apply to a lot more than just chess.

John Mount