5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Do you mean "legal" as in "possible to reach from the starting position"? $\endgroup$ – Milo Brandt Aug 23 '15 at 14:29
  • 3
    $\begingroup$ A king can be in check by 2 different pieces, consider this board, if the rook moves to attack the king the latter will be under check both by the rook and by the bishop $\endgroup$ – Alessandro Codenotti Aug 23 '15 at 14:31
  • $\begingroup$ @Alessandro Thanks, never thought of that. $\endgroup$ – Markus Klyver Aug 23 '15 at 14:36
  • 1
    $\begingroup$ Does "state" include which sides have castled, and the history information that determines when one of the players can claim a draw? $\endgroup$ – Henning Makholm Aug 23 '15 at 14:37
  • 1
    $\begingroup$ Duplicate of How many different chess-board situations can occur?. $\endgroup$ – Henning Makholm Aug 23 '15 at 14:44
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.