How many legal states of chess exists?

Solution 1:

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.

Solution 2:

Since you want all the states "that the rules allow," it is very unlikely that you can get an exact answer with current computers, but perhaps you can get upper and lower bounds. One hand-wavy proof for why this should be is that in order to count states, you would almost certainly have to enumerate them (or enumerate equivalence classes of them where you have a counting formula for each equivalence class). But in computer-based chess strategy, enumeration of possible future states (and understanding which state can lead to which state) is how virtually all computer chess players play, and yet they can't enumerate everything to the point of finding an initial winning strategy (or proving that no winning strategy exists). In fact, even super-computers can't even come close.