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.