Combinatorics – How Many Legal States of Chess Exist?

combinatoricsgame theory

I have a fairly simple question. How many legal states of chess exists? "Legal" as in allowed by the rules and "state" as an unique configuration of the pieces.

I'm not asking for the number of possible chess games. I'm asking for the number of possible legal states, or chess board configurations, the rules of chess allows.

For example, a white pawn can't be on [A-H]1 and a king can't be in check by two different pieces at the same time. Such states are obviously not allowed by the rules and illegal.

Best Answer

You should clarify whether you wish to differentiate between positions based on en passant, castling, and whose side it is to move. Francis Labelle and others have used the term "chess position" to indicate a board state including the above information, and "chess diagram" to indicate a board state not including the above information, i.e. just what pieces are on the board and where. In neither case is information for drawing rules like the 50-move rule or the triple repetition rule included.

The best upper bound found for the number of chess positions is 7728772977965919677164873487685453137329736522, or about $7.7 * 10^{45}$, based on a complicated program by John Tromp; according to him, better documentation is required in order for the program to be considered verifiable. He also has a much simpler program that gives an upper bound of $4.5 * 10^{46}$.

For chess diagrams, Tromps simpler program gives an upper bound of about $2.2 * 10^{46}$; he does not say what bound is obtained by the complicated program, but it is probably a little less than half (since side to move doubles the bound, whereas castling and en passant add relatively little), so likely about $3.8 * 10^{45}$. More information at Tromp's website

The best bound published in a journal was obtained by Shirish Chinchalkar in "An Upper Bound for the Number of Reachable Positions". I do not have access to this paper, but according to Tromp it is about $10^{46.25}$. Although it refers to "positions", it could very easily be a bound for the number of diagrams.

As for lower bounds, they are much more difficult, since a given position could be illegal for very subtle reasons. Wikipedia has claimed that the number of positions is "between $10^{43}$ and $10^{47}$", but I think it is unlikely that the lower bound has been proven.

I would guess that the actual number of diagrams is between $10^{44}$ and $10^{45}$, but this is purely speculation.

Related Question