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
45 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 20, 2021 at 6:57 | comment | added | domotorp | Here is a recent paper with references on related questions: arxiv.org/abs/2112.09386 | |
| Aug 29, 2013 at 15:24 | comment | added | Joel David Hamkins | I just want bounds, as clearly the exact value is beyond reach. In particular, I'll be happy with very tiny upper bounds, if this is how the situation turns out, as it did with the full 32 piece set. | |
| Aug 29, 2013 at 11:19 | comment | added | ARi | In my opinion the time taken to find the exact number of Illegal positions would be around same as the time taken to solve the game itself ( or unless someone proves that P=NP). Of course what we can get by some diligence are polynomial time approximation schemes. | |
| Aug 14, 2013 at 17:51 | answer | added | user21349 | timeline score: 1 | |
| Aug 14, 2013 at 4:12 | comment | added | user21349 | Let $r(p)$ be the number of ways that position $p$ can be reached in a legal game. If $p$ is chosen randomly, then $r$ is a random variable. The number of reachable and unreachable positions is about $10^{47}$, while the game-tree complexity is about $10^{120}$ (the "Shannon number"). This suggests that $r$ has an extremely fat tail, with many positions having $r\gtrsim10^{73}$. But Joel David Hamkins' answer proves that $r>0$ has a probability as low as $\sim10^{-10}$. This suggests trying to characterize $r$'s distribution, e.g., as a Pareto distribution. | |
| Aug 13, 2013 at 18:09 | answer | added | Douglas Zare | timeline score: 7 | |
| S Aug 10, 2013 at 0:29 | history | bounty ended | Joel David Hamkins | ||
| S Aug 10, 2013 at 0:29 | history | notice removed | Joel David Hamkins | ||
| Aug 4, 2013 at 2:40 | answer | added | Joel David Hamkins | timeline score: 20 | |
| Aug 2, 2013 at 12:12 | comment | added | domotorp | While I am happy with a bounty offered, I really don't believe that there is any way to provide a strong, concrete lower bound without estimating the number of all possible positions (with legal pieces), which seems to be a challenging problem already. Nevertheless, based on estimations, I guess that the answer is between 1% and 99% and that you won't get a much better bound than this in a week. | |
| Aug 2, 2013 at 11:05 | comment | added | Jon Bannon | Amazing! I was wondering if exact question was approachable just yesterday! | |
| Aug 2, 2013 at 10:27 | answer | added | Paul Burchett | timeline score: 1 | |
| S Aug 2, 2013 at 5:15 | history | bounty started | Joel David Hamkins | ||
| S Aug 2, 2013 at 5:15 | history | notice added | Joel David Hamkins | Improve details | |
| Aug 2, 2013 at 5:11 | answer | added | Joel David Hamkins | timeline score: 3 | |
| Jul 31, 2013 at 16:27 | comment | added | Joel David Hamkins | Oh, I agree with that, and had thought about adding that requirement, but decided to just stick with a simpler conception, where "legal" means that it could appear during play. For a full "position" definition to be used in playing, one needs to know the board set-up, the turn indicator, and also information about the history, such as whether the king has moved (to determine legality of castling), the last move (to determine legality of en passant) and actually the entire history of positions (to determine draw by repetition). | |
| Jul 31, 2013 at 16:12 | comment | added | ARi | This is one example. (see the last post) | |
| Jul 31, 2013 at 16:03 | comment | added | ARi | Ok..Secondly it may not be possible to classify a position in itself as legal or illegal without reference to which side is to move. i.e. There would be a few positions which can be treated as both legal and illegal based on whose turn it is. | |
| Jul 31, 2013 at 15:29 | comment | added | Joel David Hamkins | Well, both kings could be in check, even when there are no pawns. Or one king could be in check in a double manner that could not have arisen from any previous move, e.g. black king checked by white rooks from different directions. | |
| Jul 31, 2013 at 15:10 | comment | added | ARi | A position with legal material can only be illegal if it has pawns | |
| Jul 31, 2013 at 14:23 | comment | added | Joel David Hamkins | @ARi, I am sorry, but I don't understand your first comment. Could you explain? It seems that we can easily have legal positions with no pawns (and these often arise in practice). For your second comment, I guess you are saying that any arrangement of up to six pawns in a column (from second to seven ranks) can arise, and that seems right, although of course captures will have been made to achieve it. | |
| Jul 30, 2013 at 20:29 | comment | added | Pete L. Clark | @Joel: I agree with that (and thought as much when I posted my comment yesterday). My comment was meant only to be a slight sharpening of statements like "20-something" from a previous comment. | |
| Jul 30, 2013 at 18:25 | answer | added | domotorp | timeline score: 2 | |
| Jul 30, 2013 at 18:10 | comment | added | Joel David Hamkins | @Andreas Yes, see chess.com/blog/kurtgodden/… and goodreads.com/book/show/…. | |
| Jul 30, 2013 at 18:00 | comment | added | Andreas Blass | Tangential to a tangential statement in the question: Smullyan wrote a second book of this sort; if I remember correctly, the title is "Chess Mysteries of the Arabian Nights". | |
| Jul 30, 2013 at 16:35 | answer | added | The Masked Avenger | timeline score: 3 | |
| Jul 30, 2013 at 16:35 | comment | added | domotorp | I agree with Joel that its a good idea to study what pieces would give a great portion. However, I think the bulk of positions would come from 28 piece-cases, where previously 4 pawns are taken. Here any figure can be anywhere (except kings because of checks) and we can even choose half of the figures. | |
| Jul 30, 2013 at 16:09 | comment | added | Joel David Hamkins | @Pete, it seems to me that in order to promote all pawns, the 8 captured pieces could be any 8 non-king non-pawn pieces. Just imagine pushing the pawns into a zig-zag pattern in the center of the board, and then position any desired piece into the nook of one of the zig-zags, so that a pawn can capture it and one pawn of each color can promote. These nooks can be arranged to be any desired color square, so that the desired bishops can be placed there. Note also that placement becomes easier once a file opens up. | |
| Jul 30, 2013 at 13:48 | comment | added | Joel David Hamkins | Another idea may be to argue that there are more positions using the full original set of 32 pieces than with any other legal collection of pieces, since there are more ways to place 32 pieces on the board than any smaller collection. So we might hope for decent bounds by analyzing just the 32-piece positions. | |
| Jul 30, 2013 at 12:20 | answer | added | domotorp | timeline score: 6 | |
| Jul 30, 2013 at 9:33 | comment | added | Julien Puydt | Going from @TheMaskedAvenger's comment, I would say from the positions of the pawns on the board, it's possible to know how many times pawns captured and moved. | |
| Jul 30, 2013 at 8:54 | answer | added | none | timeline score: 4 | |
| Jul 30, 2013 at 6:00 | comment | added | The Masked Avenger | A pawn promotion can't happen without a capture occurring. I suspect 8 captures are needed for 16 pawns to promote, in which case there won't be much else besides 20 bishops and two kings. | |
| Jul 30, 2013 at 5:58 | comment | added | Pete L. Clark | One could start by figuring out which collections of pieces are legal. E.g. as Joel says there can be up to $20$ rooks (resp. bishops or knights) and up to $18$ queens, but to attain this maximum there must be at least $8$ captured pieces (right?). Which combinations of $8$ captured pieces are possible? | |
| Jul 30, 2013 at 5:32 | comment | added | Joel David Hamkins | Yes, @BlueRaja, that is what I meant in the description just after the question: a collection of pieces is legal if it occurs in some legal game. But I don't think you can have 20 queens, although 18 queens seems possible, if all 16 pawns promote. | |
| Jul 30, 2013 at 5:29 | comment | added | BlueRaja | Does your "using a legal collection of chess pieces" include extra pieces? Remember, due to pawn-promotions it's possible for a legal game to have 20-some bishops (or knights, or rooks, or possibly even queens) on the board at once. (Also, awe, I didn't realize Larry Evans is dead :( ) | |
| Jul 30, 2013 at 5:27 | comment | added | abo | Perhaps an easier question first: what proportion of positions are legal when all the original pieces are on the board? | |
| Jul 30, 2013 at 5:06 | comment | added | The Masked Avenger | I bet you could get to within a couple of orders of magnitude by just considering the proportion of legal 16 pawn placements to all considered placements of pawns. Rough guessing suggests the ratio is about 2^-32. | |
| Jul 30, 2013 at 3:43 | comment | added | Joel David Hamkins | @BlueRaja, there have been two Larry Evanses in chess, one (now deceased) was a brilliant grandmaster player and the other (here in California) is a brilliant IM player and brilliant teacher. | |
| Jul 30, 2013 at 3:27 | comment | added | Vidit Nanda | Cool question. Here's a sequence whose partial sums are relevant (modulo reversible moves): oeis.org/A019319 | |
| S Jul 30, 2013 at 3:26 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
fixed syntax in first line of examples
|
| S Jul 30, 2013 at 3:26 | history | suggested | Fred Daniel Kline | CC BY-SA 3.0 |
fixed syntax in first line of examples
|
| Jul 30, 2013 at 3:24 | comment | added | BlueRaja | Off topic, but - you hold the overnight camp at the same time as the US open? Doesn't Larry Evans participate in that? | |
| Jul 30, 2013 at 3:22 | review | Suggested edits | |||
| Jul 30, 2013 at 3:26 | |||||
| Jul 30, 2013 at 3:10 | history | asked | Joel David Hamkins | CC BY-SA 3.0 |