What proportion of chess positions that one can set up on the board, using a legal collection of pieces, can actually arise in a legal chess game? 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.
 A: Here I try to describe the legal collection of pieces, as defined by Joel, so this is not an answer to the original question. I think that a collection of pieces is legal if it can be obtained from the original collection using the following steps:
(1) Delete any (non-king) piece and promote at most one white and at most one black pawn.
(2) Delete a pawn and promote at most one pawn of the same color and at most two pawns of the opposite color.
I don't have a rigorous proof that this is correct, so let me know if I've missed anything.
A: A series of moves from the starting position to position X (therefore showing X can arrive in a legal game) is called a "proof game" and finding them is a branch of "retrograde analysis".


*

*http://en.wikipedia.org/wiki/Proof_game
has some info and links, particularly to a program called Natch, which purports to find the shortest proof game for an arbitrary position (I don't offhand see how to do that in a reasonable amount of time, hmm).
Anyway one thing to try is generating a bunch of random positions and running them through Natch, to see what proportion are reachable.  If not Natch, then maybe some other heuristics or algorithm can be figured out.
A: In order to make some concrete progress, let me make a definite
upper bound, based on the idea of my earlier comment.
What I claim is that at most $3612/4032\approx 89.6\%$ of the
positions using a legal collection of pieces are legal.
My reason is that I claim proportion $420/4032$ of the positions using a
legal collection of pieces have adjacent kings, and this arrangement is illegal in any chess game. To see this, consider a fixed legal
collection of pieces. Thus, this collection has one white and one
black king. Let us partition the possible positions using this collection of
pieces into groups, where two positions are in the same group if
the kings have the same locations in the two positions. Each group
is exactly the same size, since the other pieces occupy all the
other $62$ squares in all possible ways that they can. There are
$4032=64\cdot 63$ many groups, since there are this many ways to
place the two kings. Among those, there are $420=36\cdot 8+24\cdot
5+4\cdot 3$ many ways to place the kings on adjacent squares,
since if we place the white king on any of the 36 center squares,
there are 8 choices for an adjacent black king, but on the 24 edge
(non-corner) squares, there are 5 choices each for the black king,
and for each of the 4 corner squares for the white king, there are
3 adjacent squares each for the black king. So proportion
$420/4032$ of the groups are invalid based solely on the adjacency
of the kings. Since with any fixed collection of pieces, the
groups are all the same size, it follows that at most proportion
$3612/4032\approx 89.6\%$ of the positions using this fixed
collection of pieces can legally occur in a chess game. And since this same proportion arises for each of the legal collecton of pieces, it follows
that at most this proportion of all positions using a legal
collection of pieces can be legal.
I expect that further analysis will greatly improve this upper
bound.
A: I think some positive proportion, like 50% of all positions with legal pieces may arise in a legal game. I also think that the upper bound of $10^{47}$ in wikipedia might be wrong. Consider only the 28-piece, no pawn configurations. If all pieces were different, this would give $(64!)/(36!)\approx 3.4\cdot 10^{47}$ positions. Also, there are ${19 \choose 7}\approx 5\cdot 10^4$ ways to promote the 12 pawns into 8 possible non-king pieces (not counting those with too many white/black pieces). Of course now we have to divide with the figures that are the same, but that should be around (and here is the only place where I make an estimate) $4^8=6.5 \cdot 10^4$ usually, as there are 8 non-king pieces, on average 3 of each, and I rounded up because factorials are like that... So multiplying and dividing these numbers we get about $10^{47}$ positions. Of course because of the kings in chess (few because of too many bishops on same color or when the one is in check, the other could not make the last move etc) not all of these are possible, but we were quite generous when not counting positions with pawns, so I believe that there are at least this many legal positions that can arise during a game and the same order of magnitude when counting positions that can be set up with legal pieces, as almost all with 28 pieces are from a legal game.
A: 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.
A: To JDH:  Double checks can be legal.  OF course, one can't double check with the following pairs:  QQ, RR, BB, NN, NP, PP, BP.  I believe that's it.  But other than these combinations, double checks are allowed in certain circumstances.  However, triple checks can never occur.
A: This answer was originally a specific argument that the problem might be intractable due to dominance by positions that are unreachable for a specific reason. I've rewritten the answer to be more general.
Joel David Hamkins' answer has put an upper bound on the result. The bound comes from a certain mechanism, a specific constraint involving the arrangement of the pawns. Let's call call this mechanism $M_1$.
Let $x$ be the fraction of reachable positions. Suppose our goal is to put bounds on it, $a<\log_{10} x < b$, with a relatively small value of $\Delta=|a-b|$. Mechanism $M_1$ gives $b=-9.4$. Douglas Zare's answer estimates $10^{47}$ positions, and if, say, at least $10^6$ distinct positions have been reached in real games, we have $a=-41$. That gives us $\Delta\approx 32$, which is pretty wide. I would consider the problem intractable if this can't be improved to something more like $\Delta=4$.
Here is a second mechanism, $M_2$, which may also make many positions unreachable. As an illustration, consider two sets of positions. A is the set of all positions in which white has 8 pawns, 2 bishops, and no queens, and black has the same. B is the set of all positions in which white has no pawns, 5 bishops and 5 queens, and the same for black. B is about 30 times bigger than A. We should expect that most positions have this character: boards crowded with powerful pieces as a result of many pawn promotions, including a lot of underpromotions.
A given position in B may or may not be reachable. It's pretty difficult to get that many powerful pieces on the board without causing a checkmate. If such a position is reachable, then watching it be developed on the board would probably resemble a chessboard history in which two amicable superpowers cooperate very carefully to allow one another the utmost possible peaceful development of their respective civilizations. Every time they approach the brink of a Cuban missile crisis, they unexpectedly find a clever way to avoid a premature end to the game.
I could imagine that no positions in B are reachable or that some significant fraction of them are. Getting the answer would require developing an entire theory for positions of type B, which would probably be as much work as developing a topic of practical chess theory such as bishop versus knight endings with pawns.
Some folks have expressed skepticism in comments that $M_2$ really makes very many positions unreachable. I don't know -- all I've offered is a plausibility argument. The question arises of how one would ever establish the answer reliably and verifiably. I don't think it helps much to construct and analyze sample positions as suggested in Douglas Zare's comment, because this proves nothing about the probability in general that a position is unreachable due to $M_2$. Possibly some kind of random sampling would work.
The answers so far seem to have focused on looking for insight into mechanisms $M_i$ that prevent a position from being reachable, and then trying to estimate the probability $P_i$ that a randomly chosen position is unreachable due to that mechanism. We could then guess $\log x=\Sigma \log (1-P_i)$, assuming that the probabilities are independent. But there are some real problems with this approach.
First and most importantly, we can't necessarily enumerate all the mechanisms $M_i$ or convince other people that we've enumerated them all.
Some of the $P_i$ may be impossible to estimate by hand as Joel David Hamkins did for $P_1$, which leaves us with the possibility of estimating them by random sampling on a computer. But the definition of $M_i$ may not be specific enough to allow software to determine whether it is "the" reason that a certain position is unreachable. Also, $1-P_i$ may be too small to make it possible to find any reachable positions in a random sample. Or even if $1-P_i$ is 0.5, we may be unable to demonstrate that by sampling, because determining the reachability of a single position may be an intractable problem in many cases.
