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
We will restrict ourselves to typical and short chess games.
Warmup: the number of typical games by the Fermi problem method
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.
Then our Fermi estimate is that there are easily on order of (101.66)100 = 10166 typical games of chess. This has some of the grace I tried to describe in “The Joy of Calculation”.
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). 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)
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).
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: (1 / |G|) ∑g in G p(g) = |G|.
This is traditionally written in terms of the expected value operator as Eg in G[p(g)] = |G|.
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|.
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 10151.
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.
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.
As a check, our two sample based estimates rendered to more digits in the exponent are:
- Smaller sample estimate is 10150.94
- Larger sample estimate is 10151.27.
How reliable is the path sampling scheme?
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.
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.
Categories: Computer Science Mathematics