How Many Chess Games Are Possible?
Hacker News
This article explores the immense number of possible chess games, using estimation methods like the Fermi problem and Knuth's path product to arrive at figures like 10^166 for typical games.
有多少種可能的西洋棋對局？
AI 生成摘要
本文探討了西洋棋對局的龐大可能性數量，利用費米問題和克努特路徑積等估算方法，得出典型對局約有 10^166 種的可能性。
How Many Chess Games are Possible? – Win Vector LLC
Win Vector LLC
Data science advising, consulting, and training
How Many Chess Games are Possible?
By John Mount on January 27, 2026 • ( Leave a comment )
How Many Chess Games are Possible?
Long games with many possibilities
Many of his results are derived from building monster cooperative games with clever mechanisms creating a great numbers of possible games. As we see in the example below, board positions in long games tend to look a bit atypical.
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.
From this graph we can take 100 half-moves (or 50 moves for each player) as a simple, not too far off typical game length.
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”.
The Knuth path product estimate
Estimating from a single game
with Knuth’s path product estimator
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
A larger sample
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.
Conclusion
When we switch from the Fermi problem method to the Knuth path-product method we:
And, of course, the methods apply to a lot more than just chess.
Share this:
Like this:
Categories: Computer Science Mathematics
Tagged as: algorithms approximation chess Combinatorics
John Mount
Leave a ReplyCancel reply
Site Map
Recent Posts
search
search
Discover more from Win Vector LLC
Subscribe now to keep reading and get access to the full archive.
Type your email…
Subscribe
Continue reading