Timeline for 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?
Current License: CC BY-SA 3.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 4, 2016 at 20:51 | comment | added | Ellie | @BenCrowell Dear Ben, I thought you might interested in this recent work tackling the structure of the state space of chess: arxiv.org/abs/1609.04648 given your interest towards chess and physics. | |
| Aug 17, 2013 at 19:06 | comment | added | user21349 | let us continue this discussion in chat | |
| Aug 17, 2013 at 19:05 | comment | added | Douglas Zare | So, what is the difference between your statements, "I don't think it helps much to construct and analyze sample positions as suggested in Douglas Zare's comment" and "Possibly some kind of random sampling would work." It seems you are saying that when I propose random sampling, it's terrible, but when you think of it, it may help. Is there any mathematics behind these guesses? | |
| Aug 17, 2013 at 19:05 | comment | added | user21349 | Re the comment beginning with "To simplify things," I've stated three times now, once in the revised answer and twice in comments, that I don't think it's particularly important whether my conjecture about $P_2$ holds. I'm now getting the message reading "Please avoid extended discussions in comments," which is probably good advice. I would be happy to move this to chat, but I would ask that before we do that, you take a look at my revised answer and acknowledge my repeated statements that the hypothesis about $P_2$ is not relevant to the more fundamental issues. | |
| Aug 17, 2013 at 19:01 | comment | added | user21349 | What is the difference you are making? By random sampling I mean generating $n$ random positions on a computer, using the computer to determine whether each position is reachable, counting the number $m$ of unreachable positions, and estimating $P_i=m/n$. | |
| Aug 17, 2013 at 19:00 | comment | added | Douglas Zare | To simplify things, let positions A and B have the kings in the same positions. In a large proportion of the possibilities, if a piece p does not deliver check in position A or position B, then you can move p from its position in A to its position B without delivering check at an intermediate position. I think it takes something special like a pin or an unusual board configuration for this not to happen, so I don't think it fails 99.9999% of the time. The failures don't come from having a large collection of powerful pieces. Even queens aren't that powerful. | |
| Aug 17, 2013 at 19:00 | comment | added | user21349 | If you can move from positions A to B ignoring checks, and A and B do not have a check, then what stops you from "homotoping" the path to one with no checks? This would be an argument against the hypothesis that $P_2$ is close to 1. I don't understand the argument (e.g., I don't know what you mean by "homotoping"), but in any case, as I've said repeatedly now, I don't think it's particularly important whether this particular conjecture about $P_2$ holds. | |
| Aug 17, 2013 at 18:53 | comment | added | Douglas Zare | I still don't see these "fundamental reasons," just skepticism which appears misguided. If you can move from positions A to B ignoring checks, and A and B do not have a check, then what stops you from "homotoping" the path to one with no checks? Do you claim the "power of the pieces" blocks this homotopy? In explicit examples I have tried, it does not. I also don't know how you can say that my suggestion of "constructing and analyzing sample positions" would be unhelpful, at the same time that you say "Possibly some kind of random sampling would work." What is the difference you are making? | |
| Aug 17, 2013 at 18:42 | comment | added | user21349 | @DouglasZare: What exactly do you mean by, "It's pretty difficult to get that many powerful pieces on the board without causing a checkmate." What I meant by that is simply that I conjectured that $P_2$ was close to 1. | |
| Aug 17, 2013 at 18:40 | comment | added | user21349 | @DouglasZare: Your skepticism about what I call $M_2$ may be entirely correct, and it may be true that my $P_2$ is small rather than close to 1 as I conjectured. I don't know. But the point that I've tried to make clear in my revised answer is that there are fundamental reasons that if one tries to attack this problem using this general approach of listing mechanisms and multiplying probabilities, there are fundamental reasons why nobody will be able to verify that the resulting estimate is correct. | |
| Aug 17, 2013 at 18:24 | comment | added | Douglas Zare | You are asking me what "difficult" means? What exactly do you mean by, "It's pretty difficult to get that many powerful pieces on the board without causing a checkmate." This doesn't seem plausible to me. If it's true, you should be able to give an example of whatever YOU mean by that part of your answer. | |
| Aug 15, 2013 at 17:40 | history | edited | user21349 | CC BY-SA 3.0 |
deleted 12 characters in body
|
| Aug 15, 2013 at 17:36 | comment | added | user21349 | Thanks, all, for interesting comments. I've expanded and clarified my answer. | |
| Aug 15, 2013 at 17:35 | history | edited | user21349 | CC BY-SA 3.0 |
expanded and generalized the answer
|
| Aug 15, 2013 at 16:11 | comment | added | user21349 | @DouglasZare: Does "difficult to determine" mean difficult for me? For you? For software like Natch? Suppose there is an $O(n)$ algorithm for determining whether a position with $n$ pieces is reachable; this would tell us nothing about the tractability of the problem, which involves proving things about astronomically large numbers of positions. If you want to disprove the hypothesis of intractability, I can think of two methods: (1) give a rigorous proof of bounds $a$ and $b$ as defined above with a small $|a-b|$; (2) show by random sampling that $x$ is large enough to estimate by sampling. | |
| Aug 15, 2013 at 15:12 | comment | added | TROLLHUNTER | Dude, positions with 18 queens and 4 rooks on the board are reachable. Id be surprised if there were any legal non-reachable position at all without pawns. | |
| Aug 15, 2013 at 5:20 | comment | added | Douglas Zare | If you think these are extremely common, and dominate, then please construct some examples of random-looking positions where you think it is difficult to determine whether the position can be reached legally. I think it is usually not difficult to promote the necessary pawns, and move the kings into place, and then move pieces around without even checking the kings. Difficulties can occur when there are a lot of pinned pieces, but I don't think these are so bad, and having a lot of pinned pieces is uncommon. | |
| Aug 15, 2013 at 4:33 | comment | added | user21349 | OK, let me try to express this still more clearly. Say you want to prove that $a < \log_{10} x < b$ for some $a$ and $b$. I'm saying that it appears unlikely that you can do this for small values of $|a-b|$. | |
| Aug 15, 2013 at 1:02 | comment | added | Joel David Hamkins | But we've already proved such a bound ($\log_{10} x\leq -9$) in the case of the 32 piece positions. Why shouldn't we hope for a similar such bound in the general case? We didn't need to undertake a decades-long complete analysis of the 32 piece positions in order to get that bound. | |
| Aug 14, 2013 at 23:46 | comment | added | user21349 | My point is that if there is a small enough bound, then 0 will be correct to many orders of magnitude Well, zero differs from any finite number by infinitely many orders of magnitude :-) What I'm saying is that if the answer is $x$, then I think it may be an intractable problem to find a bound on $\log x$ that isn't many, many decades wide. | |
| Aug 14, 2013 at 23:12 | comment | added | Joel David Hamkins | My point is that if there is a small enough bound, then $0$ will be correct to many orders of magnitude (as it is for positions with 32 pieces). I suspect that in positions with a lot of pieces but few pawns, most are outright illegal because of double checks, precisely because there are so many powerful pieces. | |
| Aug 14, 2013 at 22:43 | comment | added | user21349 | @JoelDavidHamkins: I'm not arguing that it's impossible to determine bounds. I'm arguing that it's hard to make an estimate that's accurate to within many orders of magnitude. I'm also arguing that the kind of relatively normal positions you analyzed (similar to my set A) does not require the same type of analysis as the far more numerous ones (similar to my set B), whose proliferation of heavy weaponry makes it hard to prove whether or not you can reach them without a checkmate. | |
| Aug 14, 2013 at 18:21 | comment | added | Joel David Hamkins | Thank you for your answer. Your objection, however, would seem to apply also to the class of positions using the original 32 piece set. But in that case, we were able to show that the proportion of legal positions is vanishingly small (less than $4.077\cdot10^{-10}$). So why can't we hope for similar bounds in the overall problem, without having to undertake the complicate theory you envision? | |
| Aug 14, 2013 at 18:04 | comment | added | The Masked Avenger | I actually start such an attempt using cages. For me the roadblock is developing a theory of unblocked positions. I want small numbers n and p and a result that says all legal arrangements of p pieces on a large enough subset of an nxn board are reachable from each other. (To make this feasible, I fix the set of pieces in advance.) | |
| Aug 14, 2013 at 17:51 | history | answered | user21349 | CC BY-SA 3.0 |