State Space Complexity of Chess
It appears that the exact upper bound for the number of valid chess configurations, considering up to 32 pieces on a chessboard, has yet to be calculated. The highest estimated upper bound is 13^64, which encompasses many configurations that are categorically impossible, such as having a board full of kings. Given there are 3,612 legal placements for two kings, we can introduce from 0 to 16 pawns for each configuration. Following the loss of every two pawns, a promoted piece may be introduced—up to 9 queens, or 10 bishops/rooks/knights could theoretically exist. Restrictions include pawns not occupying the back rows, kings not being adjacent, ensuring both kings aren't in check simultaneously, and no single king being checked by more than two pieces. The complexities arise when considering piece blocking to prevent double checkmates and eliminating invalid pawn structures, such as pawns aligning in a single file, which would necessitate capturing opponent pieces.
The calculations become exponentially complex through brute-force combinatorial approaches. However, as an admirer of Claude Shannon, I believe his methodologies could help in deriving a more precise lower bound for the chess state space. Shannon's lower bound estimation of the game-tree complexity is around 10^120 possible chess games but the focus here is simply on the states themselves. Leveraging a more precise approach to simply count all possible board states may not only estimate a lower upper bound for chess configurations but also encode the possible board configurations themselves. Since the total number of valid states might be on the order of 10^47, such a vast number remains beyond the processing capability of modern machines for analyzing valid moves and mapping all possible states in valid chains. The challenge is further compounded by the Kolmogorov complexity of encoding a chessboard, we need to store ~162 bits per board (this includes all relevant state data such as if king or rook moved for castling). Disregarding the 50-move rule and player turn information, we can compute how big a Hard Drive we need. Just storing 10^47 board configurations would require approximately 10 septillion times more storage than the total data stored globally as of 2020, which was around 64 zettabytes! This is just to store the unique valid states themselves.
It is clear that we are far from completely solving chess with current methods. The essence of this discussion is to explore whether a formula that precisely calculates the precise bound on the chessboard state space, incorporating all game rules, could be employed in a novel strategy to find a solution without brute force. The goal is to analyze transitions between states based on valid moves without the need to explicitly generate and store each board configuration. If we can find a formula for computing all the possible board states, that also incorporates the rules of chess for piece placement without leveraging recursion, then this opens up the door for a mathematical solution for computing the valid transitions between those states as a whole. In effect, this would solve the Universal Chess Problem determining the winner/draw for any starting position without calculating the entire game tree with brute force.
The true tightest upper bound on possible configurations in any real game may require pruning states that do not link to initial board configuration anywhere up the chain of pointers where all states are connected based on legal moves for either side. We need a proof that randomly dropping pieces (but never in an illegal configuration) only produces states that are actually reachable from real gameplay. Has anyone found at least 1 counterexample to this? If such a proof does not hold than the pruning step will also need to be solved on a higher level without directly analyzing individual states.
None of this is enough to actually build something like a full blown engine but a complete mathematical expression for the game of chess could someday serve as the base for a perfect one if we can manage to derive the mathematical proof. This approach may theoretically provide a way around the data storage limitations necessary to completely solve the game of chess someday but the algorithmic complexity of such a formula itself could remain untouchable for classical machines necessitating the use of a Quantum Computer (No public algorithm such as Shor's or Grover's exists for this specific problem yet). Furthermore, as of 2024 it is still unknown whether QC actually preserves infinite precision of the probability amplitudes it uses for computation in intermediate states, all of modern Quantum Computation theory is built on top of the ludicrous assumption that it does. For now all we know is that QC precision is higher than the precision of our most advanced equipment used for testing and if there truly is no limit that is bad news for RSA but good news for chess. Leveraging quantum annealing on a machine with even a few thousand coherent quantum bits to run something like stockfish could eventually help us arrive at a compressed algorithmic solution to the game but that would be less fun than manual discovery even if both require a working quantum computer to arrive at an answer.
For now, let's try to find the coveted number representing the state space complexity of traditional chess for any number of turns (only accounting for chess rules on an individual piece level). If you'd like to collaborate please feel free to reach out.
