Skip to main content
deleted 12 characters in body
Source Link
user21349
user21349

Some of the values of $1-P_i$$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. AndOr 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 take too long -- it may itself be an intractable problem in generalmany cases.

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.

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.

expanded and generalized the answer
Source Link
user21349
user21349

Here is anThis answer was originally a specific argument that suggeststhe problem might be intractable due to dominance by positions that estimating this numberare 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, evena 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 within many ordersput bounds on it, $a<\log_{10} x < b$, with a relatively small value of magnitude$\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.

And B is only one ofSome folks have expressed skepticism in comments that $M_2$ really makes very many similarly defined categoriespositions unreachable. EachI don't know -- all I've offered is a plausibility argument. The question arises of these lives onhow 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 huge brushy branchkind of random sampling would work.

The answers so far seem to have focused on looking for insight into mechanisms $M_i$ that prevent a game treeposition from being reachable, which may have many disconnected parts and whose parts may or may not be connectedthen trying to estimate the startingprobability $P_i$ that a randomly chosen position of chess sois unreachable due to that they're legally reachablemechanism. Each categoryWe 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 subcategoryconvince other people that we've enumerated them all.

Some of the values of $1-P_i$ may require significant theorem-proving in order to determine its contributionbe impossible to estimate by hand, which leaves us with the total numberpossibility of reachable positionsestimating them by random sampling on a computer. The total amountBut the definition of analysis to$M_i$ may not be completedspecific enough to allow software to determine whether it is "the" reason that a certain position is unreachable. Also, $1-P_i$ may be many orders of magnitude greater thantoo small to make it possible to find any reachable positions in a random sample. And determining the amountreachability of analysis that has ever actually been done on practical chessa position may take too long -- it may itself be an intractable problem in general.

Here is an argument that suggests that estimating this number, even to within many orders of magnitude, is intractable.

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.

And B is only one of many similarly defined categories. Each of these lives on some huge brushy branch of a game tree, which may have many disconnected parts and whose parts may or may not be connected to the starting position of chess so that they're legally reachable. Each category or subcategory may require significant theorem-proving in order to determine its contribution to the total number of reachable positions. The total amount of analysis to be completed may be many orders of magnitude greater than the amount of analysis that has ever actually been done on practical chess.

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.

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.

Source Link
user21349
user21349

Here is an argument that suggests that estimating this number, even to within many orders of magnitude, is intractable.

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.

And B is only one of many similarly defined categories. Each of these lives on some huge brushy branch of a game tree, which may have many disconnected parts and whose parts may or may not be connected to the starting position of chess so that they're legally reachable. Each category or subcategory may require significant theorem-proving in order to determine its contribution to the total number of reachable positions. The total amount of analysis to be completed may be many orders of magnitude greater than the amount of analysis that has ever actually been done on practical chess.