Skip to main content
2 of 3
expanded and generalized the answer
user avatar
user avatar

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 values of $1-P_i$ may be impossible to estimate by hand, 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. And determining the reachability of a position may take too long -- it may itself be an intractable problem in general.

user21349