Possible number of chess games

[mad mathematician]

Why is it so much hard to precisely estimate the number of possible games?

Can a reliable quantum computer do this task? or do we need a universal computer?
What ever universal computer may be, of course.

https://perso.uclouvain.be/jean-charles.delvenne/WhatIsComputer.pdf

 

[phinds]

Why is it so much hard to precisely estimate the number of possible games?

What research have you done on this so far? What have you found?

A simple Google search gave me a number of answers.

 

[WWGD]

A good amount of nonsense usually, within the 100 million or so hits you get, including distortions from SEOs. I have trouble getting straight answers for most of my questions.

 

[BWV]

How do you define precise relative to Shannon’s lower bound of 10^120?

 

[jedishrfu]

You must understand the problem before successfully programming the computer to solve it.

While many moves can be made, some are illegal, and you should not count them in your summation.

There are different approaches to the problem:

1) Start with the opening position and count the number of choices white has:
- all pawns can move forward one or two squares
- the knights can jump out to two positions each.
- next, black has a similar set of moves

Each of the white moves would constitute whole subtrees of possible follow-on moves. It would simply take too long to go through them one by one. Some

2) Another approach might be to use combinatorics to determine the number of ways white and black can be arrayed on a board, taking care to have only valid moves and no dual check moves. Only one king can be in check at a time; he must either get out of check or be placed in checkmate.

Each arrangement would constitute one possible board position. From there, you can use more combinatorics to determine the number of games, but once again, you run into board positions where one board position doesn't lead to another and so can't be counted.

Famous Estimates​

• Claude Shannon's Estimate: In his 1950 paper, Shannon estimated there are about $10^{120}$ possible chess games. This number, known as the Shannon Number, is based on:
  • An average branching factor of about 35 moves per position.
  • A typical game length of 40 moves.

https://en.wikipedia.org/wiki/Shannon_number#:~:text=The Shannon number, named after,game lasting about 40 such

It's a tough problem to solve and often some simplifying assumptions.

 

[thomsj4]

Let $G = (V, E)$. A node in the graph represents a distinct ephemeral position. Formally, an ephemeral position is a tuple $P = (B, C, E, H)$ where $B$ is an 8x8 matrix representing the board layout, with each element $B_{ij} \in \{ \text{pieces} \} \cup \{ \text{empty} \}$. $C \in \{ \text{true, false} \}^4$ represents castling rights (White Kingside, White Queenside, Black Kingside, Black Queenside). $E \in \{ (i, j) | 1 \le i, j \le 8 \} \cup \{ \text{null} \}$ represents the en passant square, if any. $H \in \mathbb{Z}_{\ge 0}$ is the half-move clock (used for the fifty-move rule). Let $V$ be the set of all possible ephemeral positions, and let $M = |V|$ denote its cardinality. The edges of the graph, represented by the set $E$, are implicitly defined by the legal moves in chess. Define the adjacency matrix $A$ of size $M \times M$, where each element $A_{uv}$ is defined as $A_{uv} = \begin{cases} 1, & \text{if there exists a legal move from position } u \in V \text{ to position } v \in V \text{ (i.e., } (u,v) \in E \text{)} \\ 0, & \text{otherwise} \end{cases}$. Here, "legal move" is defined according to the official rules of chess, including piece movement, captures, checks, checkmates, and special moves like castling and en passant. The total number of distinct sequences of moves up to a maximum length $n_{\text{max}}$ can be expressed as $$ N = \sum_{k=1}^{n_{\text{max}}} \sum_{u=1}^M \sum_{v=1}^M (A^k)_{uv} $$. Here, $(A^k)_{uv}$ denotes the element in the $u$-th row and $v$-th column of the matrix $A$ raised to the power of $k$, which represents the number of walks of length $k$ from node $u$ to node $v$ in the directed graph $G$. Apparently identical board layouts can occupy different nodes due to differing histories (e.g., castling or en passant rights), leading to different possible future moves from the same board arrangement. The threefold repetition rule introduces further complexity by allowing for early termination (draws) upon certain repeated states, effectively adding structure to the graph. Although $A$ is extremely sparse (most positions connect to few others), the magnitude of $M$ makes the explicit computation of $(A^k)_{uv}$ for large $k$ computationally infeasible. This problem belongs to the class of #P-complete counting problems, for which no known polynomial-time algorithm exists, even on quantum computers. While a universal quantum computer might offer advantages for certain algorithms, no known quantum shortcut exists for computing this full enumeration of walks. Any universal computer, whether quantum or classical, would face astronomical memory or time requirements to handle all entries of $A^k$. So the precise calculation of $N$ remains effectively unattainable.

As a side note, this reminds me conceptually of Wolfram's "Ruliad," representing the entangled limit of all possible computational processes.

 

[mad mathematician]

How do you define precise relative to Shannon’s lower bound of 10^120?

Good question, but it's more about how to estimate the error in the computer calculations.
And this is a question in Numerical Analysis, which I am not sure how to pose clearly here.

 

[Hornbein]

I think the number of possible games is much higher than that if the legal moves don't have to make any sense, as in neither party is trying to win. The unavoidable limitation is that the game is a draw if the last fifty successive moves made by both players contain no capture or pawn move. So an upper bound on moves is (captures + pawn moves) * (50-1) = (30 + 16*6)*49 = 126*49 = 12600/2 - 126 = 6300-126 = 6174. I expect there are large numbers of trivial variations leading up to each of the large number of ending configurations.

 

[pbuk]

A simple Google search gave me a number of answers.

And while you are searching @mad mathematician, you should also search for the terms "universal computer" and "numerical analysis" because these terms have meanings which do not match the way you use them.

 

[Office_Shredder]

I think the number of possible games is much higher than that if the legal moves don't have to make any sense, as in neither party is trying to win. The unavoidable limitation is that the game is a draw if the last fifty successive moves made by both players contain no capture or pawn move. So an upper bound on moves is (captures + pawn moves) * (50-1) = (30 + 16*6)*49 = 126*49 = 12600/2 - 126 = 6300-126 = 6174. I expect there are large numbers of trivial variations leading up to each of the large number of ending configurations.

You can lower the upper bound a bit because you need at least one pawn captured before it promotes for the rest of the pawns to make it through. It's not obvious to me one pawn capture is enough to let everyone through but maybe it is

 

[PeroK]

I think the number of possible games is much higher than that if the legal moves don't have to make any sense, as in neither party is trying to win. The unavoidable limitation is that the game is a draw if the last fifty successive moves made by both players contain no capture or pawn move. So an upper bound on moves is (captures + pawn moves) * (50-1) = (30 + 16*6)*49 = 126*49 = 12600/2 - 126 = 6300-126 = 6174. I expect there are large numbers of trivial variations leading up to each of the large number of ending configurations.

There doesn't seem to be a lot of point in calculating the number of games. As opposed to calculating the longest possible game or the number of positions, which make more sense.

The problem is that after 1. e3 e6, say, both players could make a large number of moves with their two Knights, Queen and Bishop (in a very large number of different sequences) before they all eventually return to their starting squares. We have, therefore, a pointlessly huge number of possible games just to get to this simple opening position. And then, after 2. e4, we can go round the whole palaver again.

 

[Halc]

The Shannon estimate is comically low since it assumes the game is competitive rather than going for max moves.

The unavoidable limitation is that the game is a draw if the last fifty successive moves made by both players contain no capture or pawn move. So an upper bound on moves is (captures + pawn moves) * (50-1) = (30 + 16*6)*49 = 126*49 = 12600/2 - 126 = 6300-126 = 6174.

First reasonable answer. Yes, that rule of 50 makes it a huge number, but finite.
So most moves don't involve either pawn or capture. That's perhaps 10-15 legal moves per half-move. Really hard to say since so much of the game is played with a thinning board where the number of legal moves is so much less.

You can lower the upper bound a bit because you need at least one pawn captured before it promotes for the rest of the pawns to make it through.

Not so. A pawn takes a piece, letting it through. Next pawn can make it through the same hole without taking anything. All pawns can make it to the end with only 8 captures taking place, but a capture by a pawn counts as both a capture and a pawn move, so the 126 above reduces to 116. Maybe ~5700 moves.
So our number of legal games is around 10⁷⁰⁰⁰

There doesn't seem to be a lot of point in calculating the number of games. As opposed to calculating the longest possible game or the number of positions, which make more sense.

Longest possible game yes. My calculation was based mostly on that. Number of positions is much smaller and irrelevant since it is legal to reach the same position by more than unique history, but at most twice (with the same person to move next) per game.

 

[PeroK]

Longest possible game yes. My calculation was based mostly on that. Number of positions is much smaller and irrelevant since it is legal to reach the same position by more than unique history, but at most twice (with the same person to move next) per game.

Although online chess may enforce a draw after three-fold repetition, in over-the-board chess it's up to one player to claim a draw. There's nothing to stop the game going on. Apparently, and this is news to me, the game should officially be declared drawn after a five-fold repetition.

 

[Halc]

Although online chess may enforce a draw after three-fold repetition, in over-the-board chess it's up to one player to claim a draw. There's nothing to stop the game going on. Apparently, and this is news to me, the game should officially be declared drawn after a five-fold repetition.

You forget that nobody is playing a competitive game here. We're counting possible legal chess games, and for that we need rules enforced, else the answer is trivially not finite.

For the record, one can legally break the 50-move rule in specific situations since certain end games (knight-bishop ending I think) has been shown to require up to 200 moves given perfect play on both sides. I cannot find a reference to that since Kt-B ending are reported to work within the 50 rule.

 

[PeroK]

You forget that nobody is playing a competitive game here. We're counting possible legal chess games, and for that we need rules enforced, else the answer is trivially not finite.

I didn't forget that. It's perfectly legal to play on after a three-fold repetition. It's the five-fold repetition that you need to enforce.

It's the same for the 50-move rule. It's legal to play on. But, technically after 75 moves the game should be officially drawn.

In any case, if Shannon's was a estimate for "sensible" chess, then that seems a lot more interesting to me.

For the record, one can legally break the 50-move rule in specific situations since certain end games (knight-bishop ending I think) has been proven to require up to 200 moves given perfect play on both sides.

The rules covering those endgame exceptions were rescinded in 2001.

 

[Halc]

I didn't forget that. It's perfectly legal to play on after a three-fold repetition. It's the five-fold repetition that you need to enforce.

Fine, but that rule doesn't really gate the final answer much. It's the 50 one that counts.
I think the 50 rule is actually a 100 half-move rule, which turns the 49 into 99 in the calculation above, which results in far more legal games than the POOMA figure I posted.

In any case, if Shannon's was a estimate for "sensible" chess, then that seems a lot more interesting to me.

There are a lot less than 35 sensible moves available from a given sensible position. Few enough that I can see chess being 'solved' some day, but probably not. Not so for the game of Go which has just an idiotic branching width, even on sensible games. Such was the last bastion of human gaming superiority, until it fell.

The rules covering those endgame exceptions were rescinded in 2001.

OK. Wasn't working that one into my calculations anyway.

 

[BWV]

Checkers was solved and has ~10^20 possible games. I cannot find anything on the web about this, but ITSM it would be interesting to run up to this limit with some sort of scoring algorithm for position and material advantage. Start with opening tables to reduce the complexity then score the advantage at move n


Also, could you get to the solved endgame databases if one assumes the opening tables are optimal, leaving just the middle game? A 15 move middlegame with 15 possible moves would (30^15~10^22) be close to the scale of checkers

 

[Hornbein]

I've gotten interested in this amusing question.

Officially, moves are defined as a piece moved by each player, that is, two half-moves. Instead of using this definition I'm going to call a half-move a move. So there is a chess rule that the games ends in a draw after one hundred such moves with no captures or pawn moves.

Any game has at most 30 captures followed by the kings sashaying about for another one hundred moves so that's 31*100=3100. Now you want to maximize the number of possibilities per move. If all you have is a queen and a king then you usually have 7*8+8=64 possibilities per move. To maximize possibilities you value the most mobile pieces. So you want to promote your pawns into queens. One may sacrifice four pawns to get them out of the way. Move a pawn four squares, taken by enemy pawn. This allows three pawns to advance a full six squares. So this makes for (3*6+4-1)*4 = 84 pawn moves minus pawn captures. The length of the longest game is about (31+84)*100 = 11500 moves (which in official chess terminology is a 5750 move game). Games less than this length contribute little to the number of possible games.

So what about the average number of possibilities per move. The maximum is more than an eight queen board with its 64*8=512 possibilities. Let's reduce this to 200, each side has three queens and a couple of bishops or rooks. The number of games is then about 200^11500. Very roughly this is 10^26450. Optimists can round up to 10^30000, pessimists down to a measly 10^20000.

 

[Halc]

If all you have is a queen and a king then you usually have 7*8+8=64 possibilities per move.

One queen can move to 21 to 27 squares depending on where it is, and assuming it is nowhere blocked. Not sure where the 56 comes from. A crowded board with lots of queens will have many otherwise legal moves blocked, plus one has to for the most part avoid putting either king in check, which gets hard with queens everywhere. I estimate 60ish legal moves from a typical position of random mayhem, not 200.

By 'legal' move, that means no captures (except every 100th move mandates a specific subset of moves) and no putting either king in check which is illegal (your own) and significantly move limiting (opposing king).

One should experiment with a few assorted 'random' positions to see exactly how many moves are typically legal.

So this makes for (3*6+4-1)*4 = 84 pawn moves minus pawn captures. The length of the longest game is about (31+84)*100 = 11500 moves (which in official chess terminology is a 5750 move game).

All 16 pawns can go the distance, at a cost of 8 captures (of non-pawns). So (25+96)*100 = 12100 moves. How else are we going to get 18 queens on the board?

60^12100 = 10^21500 legal games, not too far off your figure.


Not that it matters, but the 50 rule is 50 moves after the game has made progress, with progress being anything that cannot be undone. That means we can add two castling moves to the list, so our game is not 12300 moves. Makes not enough difference to the final figure to make up for the total guess of 60.

Technically, any initial king move counts as the castling move since it does permanent damage. One can restart the count. Somehow I think the tournament people will give me the stink eye for attempting to leverage this one.

 

[Hornbein]

One queen can move to 21 to 27 squares depending on where it is, and assuming it is nowhere blocked. Not sure where the 56 comes from.

Whoops!

All 16 pawns can go the distance, at a cost of 8 captures (of non-pawns). So (25+96)*100 = 12100 moves. How else are we going to get 18 queens on the board?

Aha. White pawn captures and moves into a new column. The black pawn in that column captures in the original column of our white hero. Then both doubled up pawns can advance fully. So (16*6 + 30 - 8 + 2 + 1 ) * 100 = 12100. It appears you had 32 captures when only 30 are possible but the castling moves make up for it.

With minimal effort I came up with an 18 queen setup with 100 possible moves per side. I was able to jam some more pieces in there at no net cost. With eight queens it's about 90. It's easy to "protect" the king, just stick it in a corner with maybe a friendly blocking piece next to it. Moving the pieces around didn't change things much.

With two queens it's about 25+8= 33 possible moves per side. So a geometric average of 60 moves seems cautious but possible. I figure that for about a third of the game the geometric average is about 50, for 2/3 about 90. This makes for an overall GA of 74. That would be 10^23000 games.

 

[jbriggs444]

Any game has at most 30 captures followed by the kings sashaying about for another one hundred moves so that's 31*100=3100.

In addition to capturing and castling, an advance by a pawn also resets the 100 half-move counter. That extends the maximum game length by a fair bit.