39

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.

Joel David Hamkins
  • 224,022
  • Off topic, but - you hold the overnight camp at the same time as the US open? Doesn't Larry Evans participate in that? – BlueRaja Jul 30 '13 at 03:24
  • Cool question. Here's a sequence whose partial sums are relevant (modulo reversible moves): http://oeis.org/A019319 – Vidit Nanda Jul 30 '13 at 03:27
  • 2
    @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. – Joel David Hamkins Jul 30 '13 at 03:43
  • 3
    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. – The Masked Avenger Jul 30 '13 at 05:06
  • 2
    Perhaps an easier question first: what proportion of positions are legal when all the original pieces are on the board? – abo Jul 30 '13 at 05:27
  • 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 :( ) – BlueRaja Jul 30 '13 at 05:29
  • 1
    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. – Joel David Hamkins Jul 30 '13 at 05:32
  • 2
    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? – Pete L. Clark Jul 30 '13 at 05:58
  • 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. – The Masked Avenger Jul 30 '13 at 06:00
  • 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. – Julien Puydt Jul 30 '13 at 09:33
  • 1
    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. – Joel David Hamkins Jul 30 '13 at 13:48
  • @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. – Joel David Hamkins Jul 30 '13 at 16:09
  • 1
    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. – domotorp Jul 30 '13 at 16:35
  • 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". – Andreas Blass Jul 30 '13 at 18:00
  • @Andreas Yes, see http://www.chess.com/blog/kurtgodden/the-chess-mysteries-of-professor-smullyan and http://www.goodreads.com/book/show/2170413.The_Chess_Mysteries_of_the_Arabian_Knights. – Joel David Hamkins Jul 30 '13 at 18:10
  • @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. – Pete L. Clark Jul 30 '13 at 20:29
  • @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. – Joel David Hamkins Jul 31 '13 at 14:23
  • A position with legal material can only be illegal if it has pawns – ARi Jul 31 '13 at 15:10
  • 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. – Joel David Hamkins Jul 31 '13 at 15:29
  • 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. – ARi Jul 31 '13 at 16:03
  • This is one example. (see the last post) – ARi Jul 31 '13 at 16:12
  • 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). – Joel David Hamkins Jul 31 '13 at 16:27
  • Amazing! I was wondering if exact question was approachable just yesterday! – Jon Bannon Aug 02 '13 at 11:05
  • 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. – domotorp Aug 02 '13 at 12:12
  • 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 14 '13 at 04:12
  • 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. – ARi Aug 29 '13 at 11:19
  • 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. – Joel David Hamkins Aug 29 '13 at 15:24
  • Here is a recent paper with references on related questions: https://arxiv.org/abs/2112.09386 – domotorp Dec 20 '21 at 06:57

9 Answers9

19

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.

Joel David Hamkins
  • 224,022
  • 5
    Good. Now on to the hard part, involving one or more captures. – The Masked Avenger Aug 04 '13 at 03:28
  • Let's start small. Suppose there are 31 pieces, with all 16 pawns present. So at most one of them is out-of-file. But then a similar calculation will kick in to still give a very small proportion of legal positions. Right? And then we can aim to consider 30 pieces with all 16 pawns still present, etc., until the bound isn't much good. – Joel David Hamkins Aug 04 '13 at 03:56
  • You can actuallly consider all configurations with 6 black and 6 white pawns present which have not captured. The problem is we still don't know how such legal games stand in relation to all legal configurations. Domotorps consideration of 28 will play a significant role,if for no other reason than helping to determine the set of legal multisets of pieces. – The Masked Avenger Aug 04 '13 at 15:56
  • In the above, I should be more clear and say 6 sets of opposing pawns. – The Masked Avenger Aug 04 '13 at 16:14
  • Yes, I agree, but why should that stop us from making some definite calculations in these cases with still lots of pawns? To my way of thinking, there is still a lot we can say about the legal proportion of positions using specific piece collections, if we only make the calculations. – Joel David Hamkins Aug 04 '13 at 20:49
  • A nitpick: a "position" in chess is more than the position of the pieces, it is actually a tuple (position of the pieces, whose turn it is, number of moves since capture/pawn movement, number of times a given position occurred in the past). This proof does not work for this more refined notion of "position". – Boris Bukh Aug 14 '13 at 18:05
  • @BorisBukh, your nitpick is discussed already in the comments on the question. – Joel David Hamkins Aug 14 '13 at 18:26
7

I count $173558929221226891302430767615551561533417485504 = 1.7356 \times 10^{47}$ ways to place a legal collection of chessmen on the board. Of these, $24639467089379915386890365075260915223928803040 = 2.4639 \times 10^{46}$ have no pawns on the first or last ranks, so at most $14.2\%$ of ways to place a legal collection of chessmen on the board produce a legal position. It is likely that improvements would find more significant restrictions on the set of legal positions.

It takes some effort to determine the possible collections of legal chessmen. ("Chessmen" includes pawns. "Piece" technically refers to a non-pawn.) For example, if White has 8 pawns, 2 bishops, 2 knights, and a king, then it is not possible for Black to have 4 pawns, 3 queens, 4 rooks, 2 bishops, 2 knights, and a king. However, Black could have 4 pawns, 3 queens, 4 rooks, 2 bishops, 1 knight, and a king. If White still has 8 pawns, then each promotion of a Black pawn can be paired with a capture for one side or the other, and in the first collection there were at least 4 promotions and at most 3 captures.

I started by finding the possible vectors of opposed pawns, unopposed pawns, and original pieces not counting kings for each side. Call a pawn opposed if it has not moved from its original column, and neither has the opponent's pawn in that column. Each side starts with $8$ opposed pawns, $0$ unopposed pawns, and $7$ original pieces. Moves include $(-2,+2,0,-2,+1,0)$, which occurs when a White opposed pawn captures a Black opposed pawn, which converts $2$ White opposed pawns into unopposed pawns, and converts $1$ Black pawn into an unopposed pawn. There are $17932$ possible vectors of opposed pawns, unopposed pawns, and original pieces.

Next, convert each vector into the possible vectors of pawns, promotions, and captures. Each unopposed pawn can promote or stay a pawn. Convert each vector of pawns, promotions, and captures into the possible vectors of pawns, knights, bishops, rooks, queens, and king for each side. I used a hash table to avoid duplicates, since the same vector of counts may occur from different numbers of promoted pawns. Count how many ways there were to place these chessmen on the board, and how many ways there were under the restriction that the pawns have to be placed within the $48$ squares in the second through seventh ranks. I used C# with a big integer package. The computation took $2$ hours $34$ minutes on a $2$ GHz processor. Here are the counts filtered by the total number of pieces other than kings:

$$\begin{matrix} 4032 & 4032\newline 2499840 & 2374848\newline 762451200 & 688021440\newline 152490240000 & 130689523200\newline 22492310400000 & 18305596012800\newline 2609108006400000 & 2016206442390528\newline 247865260608000000 & 181841738563525632\newline 19829220848640000000 & 13808933884008775680\newline 1363258933344000000000 & 901054038699836313600\newline 81795535837048927998720 & 51305183887862557540800\newline 4335162450829839506110464 & 2580103899370081990144800\newline 204934580948509440712459776 & 115714657023418620663724800\newline 8709625161842041324664929152 & 4665050555573374751447039520\newline 334969016041319033638193529600 & 170173825673382454767520248000\newline 11721777898941512268159714220800 & 5647729008729626602595924112000\newline 374885578524998042949781990656000 & 171301515200792754380618149854720\newline 10995798990911566467975707768400000 & 4765529886571048034261032746780960\newline 296499744424712483942201077363200000 & 121910613390103852405088592091960320\newline 7359259246674152754334338180912672000 & 2871962662751699192209092269498673600\newline 168140268992852540807133006561199334400 & 62319197518162641915225476408569670400\newline 3532159391229553383833527063326170154240 & 1244357903407170974320709795637765066240\newline 68072251892766786279733898221633351480320 & 22815946937203267917191715682760288217600\newline 1199612470722563512991607127423133252405760 & 382949338893972841238132883627848055957120\newline 19244922194683190664837287286758917707571200 & 5858794635470333659860790877285971462732800\newline 278995789496829967243384718498911484120064000 & 81113217425471696961324265298226557473881600\newline 3512763516196652188175623254752242110008524800 & 967860625456447714742338884049918383560140800\newline 30032513167097689765684275178492499448148377600 & 7180859208049984902733460962414426023904281600\newline 90835621190174574287987518323083620781868441600 & 13544187413659480412286575232707703090739353600\newline 46469725378042907543299835558295158351228160000 & 2814661208855794476422354880818644910233920000\newline 2404159138638549255694710397739697094118400000 & 44498154253195662774573947559960251923200000\newline 4634726695587809641192045982323285670400000 & 21392082322155637297725861387221535360000\newline \end{matrix}$$

The $14.2\%$ value from restricting pawns to $3/4$ of the board indicates that typical positions of legal sets of chessmen have many pawns, about $\log .142/\log .75 \sim 7$, which is not obvious because there are many ways a pawn could underpromote or could be captured. Perhaps one could get a better restriction by keeping track of pairs of opposed pawns, which have to be in their original columns in order. This would add a lot of complexity to the bookkeeping, but it would produce a severe restriction for collections of chessmen which can only occur with a pair of opposed pawns still in their original column, perhaps trimming a few percent off of the $14.2\%$.

Douglas Zare
  • 27,806
  • How many distinct multisets (collections of legal chessmen) did you find? And was respecting bishop placement (but perhaps ignoring trapped bishops) observed? – The Masked Avenger Aug 13 '13 at 19:24
  • Also, it was conjectured that 28-piece games would be a significant contributor to the ratio, and I conjectured that leaving out all arrangements with 26 pieces or fewer would not seriously change the ratio by a factor alpha where (1 - alpha) has size at most .001. Does your work shed light on those conjectures? – The Masked Avenger Aug 13 '13 at 19:29
  • I didn't keep track of the number of distinct multisets. I did keep track of the numbers of pieces for each side, so I could add up the values for 27 or more total pieces, but why not execute a similar calculation yourself? I didn't distinguish the bishop colors. I doubt trapped bishops or bishop color violations are significant. As I said, there is a sense in which the weighted average of the number of pawns is about 7 compared with 16 for the initial position, so there is a lot of capturing and promotion in a typical position. You can underpromote to a second bishop on a color. – Douglas Zare Aug 13 '13 at 19:46
  • I am attempting estimates by hand, and am interested in verification, but do not have a good enough handle on the number and shape of legal multisets yet. Also, I believe bishop placement will turn your 14% into 4%, and likely smaller if games with more bishops are more numerous. – The Masked Avenger Aug 13 '13 at 19:55
  • Also, my first idea was to label the pawns, and note that legal labeled placements were fewer than .006% of all labeled placements. Granted it is a different problem, and ignores pawns passing through each other, but is that idea useful, and how poor is that estimate? – The Masked Avenger Aug 13 '13 at 20:03
  • Douglas, thank you very much for your outstanding answer! I appreciate it very much. If most positions have a lot of pieces, then it seems to me that double checks on one side or both will seriously cut into the proportion of legal positions. – Joel David Hamkins Aug 13 '13 at 20:08
  • 1
    @Joel David Hamkins: Once you have the distribution of multisets of pieces, you can sample from it, and sample random positions, and see how often there are double checks. I haven't done this. – Douglas Zare Aug 13 '13 at 20:10
  • Also, I have an OPN chat room, but am willing to chat there now about this, if you wish. – The Masked Avenger Aug 13 '13 at 20:16
  • Thank you for the distribution. To me it would seem artistic to leave an angled notch in each display of numbers. – The Masked Avenger Aug 14 '13 at 17:28
  • I'm trying to reproduce the first stage of your calculations and failing. With vectors $(-2,2,0,-2,1,0), (-1,1,0,0,0,-1), (0,0,0,-1,0,0), (0,0,0,0,-1,0), (0,0,0,0,0,-1)$ (representing respectively pawn takes pawn, pawn takes piece, piece takes piece, and piece takes pawn in two forms) and the symmetric vectors for the other colour, I already get 105464 different vectors - and I think there are other deltas required in some cases. Would you mind expanding your description of that phase? – Peter Taylor Jan 28 '14 at 23:35
  • @Peter Taylor: I'll take a look again when I have time, perhaps in a few days. – Douglas Zare Jan 28 '14 at 23:46
  • @Peter Taylor: If you project to the possible triples of pawn types (opposed, white unopposed, black unopposed) there are $1+4+9+...+64=204$ possible projections. If you project to the number of White pieces there are $17$ possibilities, and the same for the number of Black pieces. So, the total number of possible vectors is at most $204\times 17^2 = 58956$ which is lower than your figure. Please check your work. I did a BFS with a particular set of move vectors, eliminating duplicates. I could say the move vectors, but your notation is different from the one I used in the answer. – Douglas Zare Jan 29 '14 at 15:44
  • The notation is copied from the answer, except that I've skipped the $+$ for brevity. The key point, which the use of a 6-tuple obscures, is that the definition of "opposed" means that both players must have the same number of opposed pawns. Thanks for your comment, which highlighted this for me. For the benefit of anyone else trying to reproduce this, it's actually 285 possible projections to pawn type triples, because with $0$ opposed pawns there are a further $9^2$ cases. – Peter Taylor Jan 29 '14 at 23:37
  • @Peter Taylor: Yes, I made a fence-posting error and left out the $9^2$ term. I also should have said that the projections were contained in the set rather than that they are equal to it. So, did you confirm the value $17932$? – Douglas Zare Jan 29 '14 at 23:44
  • @Peter Taylor: The order in my notation was (White opposed pawns, White unopposed pawns, White pieces, Black opposed pawns, Black unopposed pawns, Black pieces). For example, if a Black piece takes a White opposed pawn, Black loses an opposed pawn and gains an unopposed pawn, so the change would be $(-1,0,0,-1,+1,0)$. – Douglas Zare Jan 29 '14 at 23:49
  • Yes, I also get 17932. I had the correct order for the notation, but I was reading "unopposed" as "passed" and trying to account for cases where a capture by a pawn didn't pass the pawn. – Peter Taylor Jan 30 '14 at 08:44
6

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.

domotorp
  • 18,332
  • 3
  • 54
  • 121
  • @Joel: Thanks for your comment. When I look back at it now I would certainly interpret promotion the way you say, but based on my previous comment I must have been thinking about it differently (and incorrectly, I would say). Trivia: I have an appointment to play some blitz chess later this evening. – Pete L. Clark Jul 30 '13 at 21:43
  • Pete, I hope you have some good games; and let me say that I'm glad to see you back here more often again on MO! – Joel David Hamkins Jul 30 '13 at 23:51
  • Does this consider that to get 18 Queens on the board, you have to promote 16 pawns AND sacrifice 8 other pieces (so the pawns can be doubled and move out of each others' way) https://chess.stackexchange.com/questions/4123/maximum-number-of-queens-possible – JeffUK Dec 15 '20 at 16:44
  • 1
    @Jeff Yes, this is the special case of applying the above (1) eight times. – domotorp Dec 15 '20 at 17:01
  • Could you please explain (2)? – 2080 Jan 18 '21 at 11:51
  • @2080 It tries to model that a pawn takes a pawn. Following that 3 pawns might be promoted. – domotorp Jan 18 '21 at 12:35
  • I understand the first part, meaning that the same pawn may either be captured, or promoted. I also understand that another pawn may capture this pawn and promote during that move, but why is it "at most two pawns of the opposite color"? – 2080 Jan 18 '21 at 12:48
  • @2080 Suppose white a-pawn captures black b-pawn. The two white pawns on b can be promoted and one black pawn on a. – domotorp Jan 18 '21 at 15:11
  • 2
    See https://chess.stackexchange.com/questions/33347/which-collections-of-pieces-are-legal where 4 necessary & sufficient inequalities are given for a collection to be achievable – Andrew Buchanan Jan 20 '21 at 03:21
  • My answer in chess.stackexchange.com/questions/33347/… to compute the number of legal collections to be 58,084,310. This matches a prior table computed by Kryukov, so I can now go on to the "extra credit" challenge of distinguishing the bishops – Andrew Buchanan Jan 25 '21 at 14:51
4

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".

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.

none
  • 41
  • 2
    If one of the guesses in the comments ($2^{-32}$) is anywhere near correct, you'll be waiting a long tie for Natch to accept one of your randomly generated positions. – Gerry Myerson Jul 30 '13 at 09:19
  • 1
    Isn't finding even a single proof game difficult, let alone the shortest one? Reachability is difficult in general, and the shortest game path may have exponential length (see http://mathoverflow.net/questions/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach). – Joel David Hamkins Jul 30 '13 at 13:11
  • I think Kernighan or Brent in the early days of UNIX developed a database of end game positions for up to 6 pieces. For small collections, one could try none's suggested approach and see how the ratio falls as the number of pieces grows. Just looking at 3 pieces, one gets bad arrangements only for bishops and pawns that aren't excluded already by adjacent kings. – The Masked Avenger Jul 30 '13 at 22:16
  • @Masked: About end game positions, see http://en.wikipedia.org/wiki/Endgame_tablebase but I doubt this would be of much use. – domotorp Jul 31 '13 at 11:18
  • It seems it was Thompson, 5 pieces, and if they did straightforward isomorphic reductions, one might extract the number of legal positions for 5 pieces from that work, and use that as a better basis for extrapolation. – The Masked Avenger Jul 31 '13 at 19:13
  • Natch is a really good program: one of the fastest around at its chosen task. The chess problem database PDB contains 1350+ proofgames validated by Natch. These include some with over 60 single moves. Hence I myself wouldn't have selected the word "purport" to describe its capabilities. – Andrew Buchanan Jan 25 '21 at 16:23
3

EDIT 3

These things always come to me after I post.

Let's build one cage for both kings. Allocate a corner and a 2-rank by 4-file space for the cage. (One can do a vertical 4 by 2 cage also, but the analysis with pawns is harder. Let's stick to horizontal for now.) Allocate 5 pieces to form the walls of the cage. The nice thing here is that pawns of both colors can be involved, and you can put either king in the corner office. There will be three forbidden squares for one color knight and only one for the other color in the remaining 56 squares. We only need at most two promotions to build a cage, but there are 7x5x7x7x6=10290 different cages to build. Swapping kings or using a different corner gives another factor of 2x4. Without even considering differing multisets beyond what is needed to build a cage, we can use much of the analysis below to get over 10000P many legal games. With more work, we can push the provable lower bound for the ratio to above 10^-12, and that is assuming the weak upper bound for all positions of roughly Qx10^5. I now expect the actual ratio to be between 10^-4 and 10^-7.

3 TIDE

EDIT 2

Here is a lower bound which hinges on several parts.  We will build two cages to isolate the kings, promote 9 pawns, scattershoot the remaining pieces, and remove the illegal and some legal combinations, and then indicate some variations to pump up the lower bound.

The basic setup involves castling both kings on King side, and moving them to the corners and using two stationary pawns and a preselected piece to guard the king.  To simplify things, we will choose one of twenty combinations for guarding: each king gets a nonpawn of their color, or each gets an opposing knight or bishop.  Both kings are on the h file corners and the guard pieces are adjacent to them on the g file.

Once guard pieces are chosen, advance King and Queen pawns, advance material to castle, and then maneuver the guard pieces into position, moving a king out of check if needed (although it should not be necessary).  Now that the kings are caged, advance pawns and move nonpawns in a nonthreatening manner to the g and h files.

Now plan for three pawn captures, especially if bishop color matters.  Place the remaining nonpawns (two of each color) in the file behind pawns of the same color that will promote on that file. To make the analysis simpler, promote no more than four pawns to queens of the same color, and no more than three of any other type.

Once all of the promotions have been made, there will be 56 squares for 21 pieces, and I assert that all the illegal placements are covered by monochromatic bishop placement and by knights putting opposing kings in check.  Before dealing with that assertion, let's count how many potentially legal positions that could be.  As a starter calculation, assume among the 21 pieces outside the cages that there are three or two of each of the 8 allowed types of nonpawns, and call this multiset R  There are P=(56_R)=$(56!)/((35!)(3!)^5(2!)^3)$ such positions.  When we compare this to the standard Q defined below, we get P=Q[((8!)^2(2!)^3 (56!)(32!))/((3!)^5(64!)(35!)) ] This means P/Q is roughly about 1/2x10^-12 . But wait! There's more!

Let us get some hand-waving out of the way. I assert that any legal arrangement of 21 pieces on the reduced board can be reached from any other legal arrangement. Here legal is more strict and includes no knights placing kings in check. The basic idea is to move all 21 pieces into files a-e, and then argue that you can move enough pieces into a restricted portion of files f-h so that you can swap any two pieces, sort of like a complex 14-15 puzzle with the only parity issue involving bishops. I handwave that from any arrangement of 21 pieces in files a-e, you can legally place 8 or more pieces in files f-h without checking either king, leaving 13 or fewer pieces in files a-e. If it helps, I invoke the fact that we can promote so that all of the 8 types of pieces have at least 2 representatives in the 21. (One may need to prove that there is room enough to permute arbitrary piece types, but there are 12 squares to work with in files f-h, so I am asserting with confidence. One also needs to show that there is no locked configuration of 13 pieces on a 5 by 8 board, but by tiling the board by p pentominoes, you can likely show that there will be more than one piece that can move usefully.)

Now let us handle the illegal combinations. They are monochromatic bishops and checking knights. In case there is only one white bishop among the 21, it needs to be on a color square that is different from the square that the guarding white bishop is on. Potentially half of those P many positions may thus be illegal, and less than half if there are two or more bishops among the 21. Similarly the black knights are forbidden from simultaneously occupying f2 and g3, so let them occupy the other 54 squares instead. With at most five knights of one color, this reduces the number of positions by a factor of at most (51x50)/(56x55), so by a factor of more than 80%. So I claim that at least 64/4=16% of the P many combinations are legal, by factoring in contributions from both colors of bishops and knights.

Now to pump up the numbers. First note that we can use a queen side arrangement to double the number of legal positions, counteracting the white bishops complication. Also, we can move the pawns in the h file (or a file for Queen side) and reduce the number of squares from 56 to 53 or 52, depending on if you want a piece between black and white pawns. This (more handwaving using 10*35*34*33/56*55*54) restores another factor of close to 2. Also, by considering capturing one or two pieces of the 21 gives us a factor of about (1 + 21/35(1 + something positive)), so we build back up to P many positions which are legal, using queen side and using slightly fewer pieces.

Now to bump things up. The above was based on a fixed multiset R, and using just that multiset we got at least 0.64P legal positions, building up to P by capturing one or two of the 21 pieces not involved in the cages. However, there are 56 different multisets allowed for the 21 pieces, if there are only two or three of each type. If we allow one color to have a 4 3 3 2 distribution and the other a 3 2 2 2 among the types, we get 2x12x4 additional multisets at a cost of reducing P by 3/4. So we actually have at least a factor of (56 + 96x3/4)=128 to use in our lower bound. Finally, we have the factor of 20 different guard combinations. Even if we don't consider multisets of size smaller than 29, we get a lower bound of 1600P many legal combinations, which puts us within striking distance of Qx10^-9.

Although there is much work left, I now expect the ratio lies between 10^-15 and 10^-7. The feeling I get is that games involving 26 pieces or less will make no significant contribution to the ratio, and even 28 piece games will not shift the order of magnitude of approximations.

2 TIDE

EDIT

Unfortunately, the details will not be ready until after the bounty expires. Someone else may be able to use the sketch below.

Let S be the multiset of pieces used at the start of a chess game. Let Q=(64_S) be the number of possible arrangements, one piece per square, using S on a chessboard. Q is (the value of) a multinomial coefficient using data from S, and is about 4x10^42.

If one looks at the number of possible arrangements using a legal submultiset S' of S (in particular the collection of pieces arising from a legal game of chess involving no promotions), one encounters an expression like Q(1 + 30/33*(1 + 29/34*(1 + 28/35...))), which evaluates to something less than 5Q. Further, considering legal collections T, one needs only those submultisets of T which are legal and have not been considered earlier in a sequential enumeration of legal submultisets. Thus, a good approximation to the total number of all positions considered should be the sum over T a maximal legal multiset of terms (64_T).

The T I have found so far that gives a maximum value for (64_T) is slighly less than 8Q, involves one pawn capture and 3 queen promotions of different colors. After two pieces being captured, it is hard for me to see any optimal T occurring.

There are 165 possible multisets arising from promoting 8 pawns of one color. I suspect an upper bound for the number of maximal legal multisets is 165*165, given that 2k promotions usually require k captures. This suggests an upper bound of 27225*8Q for the number of all possible positions, or about 217800Q.

I was hoping to find a T such that I could beat Joel Hamkins's ratio of legal game positions using T/(64_T) while also satisfying (64_T) > Q, but time has run out for that. It looks like 2^-32 remains unverified at this writing.

TIDE

If the idea is to come up with a rough figure, the following approach using labeled pieces might help.

Consider the white king's pawn. It cannot inhabit 24 of the squares on the chessboard (I assume promotion is strict and monotone. I let others argue whether to add 8 to the number 24.) . For the other king side pawns 24 grows to 26, 30, and 36. Starting with these ratios, a set of four pawns labeled with their starting squares can occupy about 9% of all possible positions available. Raise this to the fourth power, and one gets a ratio of 6x10^-5 as an upper bound on positions of labeled pawns, where as a rough count I include pawns sharing the same square.

Now the bishops provide another factor of about 6x10^-2, the two kings together a factor of about 7/8, and the rest provide a factor that is likely closer to 1. This gives a weak upper bound for all 32 labeled pieces of 3 x 10^-7 fraction of legal positions to all positions.

I imagine with refinements one can probably subtract one more from the exponent. Hopefully the fraction involving unlabeled pieces will not be much different.

I just noticed domotorp's comment regarding positions having just 28 pieces. While this suggests the fraction of legal positions may be higher, for the labeled case, the ratio (all possible for 28) to (all for 32) should still be small, and should have a small effect on the rough calculation.

And now I just noticed more recent comments from Joel David Hamkins, who made some similar and more refined observations. Perhaps he can place the above musings on a more rigorous footing, and maybe someone can convert the labeled analysis to an unlabeled one.

The Masked Avenger
  • 2,158
  • I awarded you the bounty, in appreciation for your efforts; thank you very much!. I hope that you will carry through the details as you indicated. I continue to think that we can hope for some definite good bounds with the right calculations and the right way of thinking about it. – Joel David Hamkins Aug 10 '13 at 00:31
  • I hope this recent edit affirms your faith. I suspect this forum can prove bounds to within a couple of orders of magnitude from the actual number. – The Masked Avenger Aug 11 '13 at 05:19
  • Even wihout the consideration of fewer pieces, these 29 piece arrangements give at least twice as many positions as what you calculated for the 32 piece multiset. I think once the multisets are computed, we will find many fewer legal games than domotorp predicts. – The Masked Avenger Aug 11 '13 at 05:31
  • Of course I would now think of a 7 piece cage in a corner, giving perhaps an additional factor of 100 for 28 pieces – The Masked Avenger Aug 11 '13 at 09:06
3

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.

Joel David Hamkins
  • 224,022
  • You may find an additional factor of about 1/120 by analyzing pawns of one color. In addition to the fact that most of them inhabit just 3/4 of the board (at most one pawn can be promoted at any time), certain monotone arrangements are not allowed (e.g. a2,a3, and b2). I now think the actual ratio you seek is closer to 2^-24. I am finding a preliminary analysis by hand of feasible 8-pawn positions complex but well within reach of a computer analysis. – The Masked Avenger Aug 02 '13 at 05:21
  • I also expect such kind of reasoning to succeed (and I did vote up your answer), but can you carry through your analysis with a definite calculation? For example, there are many legal collection of pieces with no pawns, and so we would seem to need an analysis showing what fraction of the positions have sufficient pawns to carry through your idea. But as I've said, I think you will succeed---let's see some definite calculations! – Joel David Hamkins Aug 02 '13 at 05:28
  • What I have at present is pretty hairy and incomplete, but here is a sample. For any board B, look at B* which has all pieces removed except for white pawns. Computing the number of distinct B* is interesting with an upper bound of 64 choose 8 + similar terms = roughly 64 choose 8 or 4.4 x 10^9 (5.1 if you want less roughly). No pawn captures and no promotions means 6^8 positions; one promotion means 8x6^7. One pawn capture and no promotions is about 600x6^6; with promotion about three times as many. I am still enumerating feasible 8 pawn positions but have not reached 1% yet. – The Masked Avenger Aug 02 '13 at 05:39
  • Of course, I need also to convince you that for any board without pawns, that there are many more with pawns. I suspect that can be done by showing that all but a small fraction of such boards are one or two legal moves away from a pawn capture or promotion, and that it can happen in more than one way. – The Masked Avenger Aug 02 '13 at 05:51
2

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.

domotorp
  • 18,332
  • 3
  • 54
  • 121
  • I would be more convinced by this if you had a better figure on the distinct multisets on 26 pieces using 8 labels. You seem to estimate it at near 1280; I think it might be a bit smaller, given the five color count alternatives. – The Masked Avenger Jul 30 '13 at 18:45
  • Good point, I did have a stupid mistake, now it should be better. – domotorp Jul 30 '13 at 19:20
  • Could you explain why you think almost all positions with 28 pieces are from a legal game? With so many pieces, it seems a significant number will have both kings in check. – Joel David Hamkins Aug 02 '13 at 14:40
  • 1
    Yes, I did mention this in my answer. This is again some factor that we have to multiply with, I guess around 50%. The problem that any such calculation/estimation seems to be too complicated for a human to carry through and a bit uninteresting for me - why should we care if it is 30% or 70%? – domotorp Aug 03 '13 at 07:28
1

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.

Paul Burchett
  • 540
  • 1
    How can a double check be legal? If I understand the rules correctly, at one point in a legal game one of the players has to put the other player's king in check without causing his own king being in check (that would be an illegal move). At that point the other player must (try to) resolve the check by either moving his king away, blocking the way of the attacking piece or taking it off the board. He is not allowed to just "countercheck" the first player and leaving his king where it is. Did I misunderstand something in the rules? – Johannes Hahn Dec 28 '13 at 00:00
  • 2
    Might there be a miscommunication here about the meaning of double check? If "double check" means that both black and white kings are in check, then this cannot legally occur. But if "double check" is understood in the sense that one king can be checked by two different pieces, this is of course possible (and in fact this term comes up frequently in the literature on chess tactics). – Todd Trimble Dec 28 '13 at 00:20
  • 2
    In any case, I feel very confident that "double check" in JDH's sense is the one implied in the third line of his post (both kings in check as an example of an illegal position), and I'm also confident that Paul Burchett had in mind the standard meaning of "double check" where one king is checked by two chessmen (he had enumerated the pairs of men that could not deliver a double check, and this fits the meaning I'm ascribing to him here). I'm hoping Paul will acknowledge the misunderstanding, and also that his meaning is not very relevant for the present thread. – Todd Trimble Dec 28 '13 at 01:31
  • Apologies to you both. I was skimming. Although the typical meaning of "double check" to players is the legal possible definition. – Paul Burchett Dec 28 '13 at 21:22
  • How about simultaneous check? – Paul Burchett Dec 28 '13 at 21:34
  • The more I think about it simultaneous check wouldn't work either, for the word simultaneous shows up a lot in chess literature! – Paul Burchett Dec 28 '13 at 22:44
  • @ToddTrimble: That makes sense. Thanks for clearing that up. – Johannes Hahn Dec 29 '13 at 00:13
  • @ToddTrimble

    My post I think you will find, or possibly have now found, it to be relevant. Double check in the standard sense can also be analyzed and possibilities possibly pruned there as well - although perhaps not as many as with other suggestions!

     – Paul Burchett Apr 27 '14 at 04:33
  • Also, and respectfully, this is a long thread. For those that want to follow, don't you think the standard definition should be used! It's just much easier? – Paul Burchett Apr 27 '14 at 04:36
1

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.

  • 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.) – The Masked Avenger Aug 14 '13 at 18:04
  • 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? – Joel David Hamkins Aug 14 '13 at 18:21
  • @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 '13 at 22:43
  • 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. – Joel David Hamkins Aug 14 '13 at 23:12
  • 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 '13 at 23:46
  • 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. – Joel David Hamkins Aug 15 '13 at 01:02
  • 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 '13 at 04:33
  • 1
    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. – Douglas Zare Aug 15 '13 at 05:20
  • 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. – TROLLHUNTER Aug 15 '13 at 15:12
  • @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 '13 at 16:11
  • Thanks, all, for interesting comments. I've expanded and clarified my answer. –  Aug 15 '13 at 17:36
  • 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. – Douglas Zare Aug 17 '13 at 18:24
  • @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 '13 at 18:40
  • @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 '13 at 18:42
  • 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? – Douglas Zare Aug 17 '13 at 18:53
  • 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 '13 at 19:00
  • 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. – Douglas Zare Aug 17 '13 at 19:00
  • 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 '13 at 19:01
  • 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 '13 at 19:05
  • 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? – Douglas Zare Aug 17 '13 at 19:05
  • let us continue this discussion in chat –  Aug 17 '13 at 19:06
  • @BenCrowell Dear Ben, I thought you might interested in this recent work tackling the structure of the state space of chess: https://arxiv.org/abs/1609.04648 given your interest towards chess and physics. – Ellie Nov 04 '16 at 20:51