Many chess positions that one may easily set up on a chess board
are impossible to achieve in a game of legal moves. For example,
among the impossible situations would be:
- A position in which both kings are in check.
- A position in which there are pawns on the first or on the
last rank. - A position with two white pawns on the same file, but black
still has all his pieces. - A position with a white bishop on the first rank, trapped by two
white pawns on the second rank, but the bishop is not on c1 or f1. - A position with two black-square white bishops and eight white pawns.
The logician Raymond Smullyan wrote a delightful book The Chess Mysteries of Sherlock Holmes: Fifty Tantalizing Problems of Chess Detection,
containing many interesting chess detective stories, some
involving positions that were impossible for sometimes very subtle
reasons.
My question is:
Question. What proportion of the chess positions that one can
set up on the board, using a legal collection of chess pieces, can
actually arise in a legal chess game?
What I mean is that collection of pieces is legal, if it occurs
in a position of a legal chess game, a game played according to
the rules. This collection is somewhat broader than one might
naively expect, since it is legally possible, for example, to have
a king of each color with nine white queens, as white may have
promoted all the pawns while all other pieces were captured. And
other similarly strange collections of pieces are possible. So the
collection of positions I am considering are those that can be
obtained by messing up the pieces on the board from an actual
legal game.
Of course it will be too difficult to get an exact answer, and I
shall be satisfied merely with good bounds. The Wikipedia page on
chess and mathematics mentions some numbers, including estimates on the
number of legal positions, but the information there doesn't seem
to answer this question. Perhaps those who are more familiar with
that work can point to where this question is answered there.
I guess the answer must be a rather small proportion, because it
seems that many legal chess positions can be easily transformed
into many illegal ones, by placing both kings in check, by adding
a pawn to the first rank (unless all pawns are already used), etc.
Is this right, and can such an argument be used to make tight
bounds?
I am here at the Mountain Lake Chess Camp, where we've been
discussing the question, when one of the instructors mentioned the
numerical bounds on the total number of chess positions, and the
question arose whether this included impossible-to-achieve
positions or not.
Best Answer
The overwhelming majority of positions using the full original set of 32 pieces are illegal and cannot arise in a legal game of chess. Specifically, the proportion of legal positions among all those using the 32 piece set is strictly less than $4.0763\cdot 10^{-10}$.
To see this, consider a legal position using the 32 piece set. Since it has 32 pieces, there can have been no captures yet. In particular, each pawn must still be on its original file, not in the first or last rank, and furthermore, still opposed by the opposite-color pawn still facing it on that file. Within each file, therefore, you can easily count precisely 15 arrangements of one black pawn and one white pawn that exhibit this feature. Thus, there are precisely $15^8$ many ways to arrange the pawns overall in such a way that the position is not immediately seen as illegal. But there are are ${64 \choose 8}\cdot{56\choose 8}$ many ways to arrange the $16$ black and white pawns on an empty board. For each arrangement of the pawns, there are exactly the same number of ways to arrange the remaining pieces. The proportion of legal positions using the full 32 piece set is therefore at most $${15^8 \over {64\choose 8}\cdot{56\choose 8}}= { 2562890625\over 4426165368\cdot 1420494075}\approx 4.0762706\cdot 10^{-10},$$ and so we get the upper bound as claimed.