Why do they make such a big deal out of having numbered the positions? That's kind of a basic thing about a countable set, you can enumerate its elements if you want. We already knew the set of legal chess positions was countable.
Thanks, that is helpful! Let me ask a more specific question. Combinatorics gives us lots of ways to calculate the sizes of sets, and in my experience, they rarely if ever involve an explicit enumeration. Why then is an explicit enumeration an important milestone in this particular problem? To a combinatorialist, it would be more interesting to see the more-easily-countable-structure you're presumably mapping these positions to/from.
This chess position ranking wouldn't be possible without making use of such combinatorics, as you can see with the use [1] [2] of the multinomial ranking [3].
You're right that counting is much easier than ranking. That's reflected in my Haskell counting program [4] being MUCH simpler and MUCH faster than the ranking program.
But counting is only good for upper bounding and doesn't let you draw a random sample to determine the fraction of legal ones, as needed for estimation.
So at a high level, you need the ranking because you need to do computations on individual elements of the set (e.g. random samples) to refine the estimate. Which is not necessary in a lot of ordinary combinatorics problems, but is here because this one is so hard. Cool, thank you!
I can imagine this project being of interest in the seminar of the right university department.
> Combinatorics gives us lots of ways to calculate the sizes of sets, and in my experience, they rarely if ever involve an explicit enumeration.
I don't think that this is true. I think that explicit enumerations are rarer than exact size computations, which are themselves rarer than asymptotic size estimations, for presumably obvious reasons; but a bijective proof (https://en.wikipedia.org/wiki/Bijective_proof) is still regarded as the gold standard in combinatorics, and as a desideratum.
I think the knowledge that the set is countable and can thus be counted is, as you say, quite obvious. However, actually counting it or generating the complete set is terrifically hard in practice. There are many more illegal positions than legal ones (I suspect, would be curious to know if this is actually the case). Moreover each legal position may be the result of thousands of games played legally or thousands of games played illegally. Computers historically haven't been able to enumerate this set, or judge from a position if it is conclusively legal or illegal since the complexity of that question is immense. We're on the cusp of being able to do that and I think that's what makes this project more than a trivial exercise in counting countable things.
Are there any intelligent approaches to automating proof games? Can I just play the position backwards, unwinding it with a bias to returning pieces to their home positions?
Also isn’t this relatively easy if you can just waste turns (pointless moves by a Queen) while returning pieces back home?
This is fascinating because on the surface it seems very do-able but I bet the devil is in the details.
Great question. This was foreseen long ago (1500s?); the turn wasting thing is limited by the fifty move rule. A game ends in a draw if no pawn is moved or piece captured for 50 moves. Since pieces can only be removed not added and pawns can only move forward, never backward, this proves that cycles are not possible in chess (they certainly would be without this rule of course)
Yes, definitely. I hadn't remembered that one. You could have much longer chains with the 3 fold repetition rule alone though. I guess both together potentially make it easier on the players and arbiters
It seems the 50 move rule is probably older according to Wikipedia (1800s vs 1500s), which is kind of surprising to me, I would have expected the other way around. It's easier to keep track of "moves since last capture/pawn advance" than every board position played so far. Maybe just in theory not in practice. I am a terrible chess player.
Let's assume the 50-move rule is automatically applied. We can have 49 moves per pawn move, followed by 49 moves per piece captured. A maximum of 8 pawns (4 white and 4 black, for example) can possibly be advanced over the course of the game to the opposite side (6 squares ahead from their home square). Therefore, it seems to me that the maximum number of pawn moves could involve one player advancing their pawns 4 spaces, followed by the opposing player capturing all those pawns (using pieces rather than pawns, as both moving a pawn and capturing a pawn would be a waste), and then advancing their pawns to the back rank. This would be 8x4 + 86 = 80 pawn moves, plus 8 pawn captures. That's 88 allowances for 49-move knight sequences, plus the initial 49-move knight sequence made from move one. So, with no pawns remaining, and all of black's pawns converted to pieces on the back rank, we have 8949=4361 moves. Now, there are 22 pieces and 2 kings remaining on the board. That puts an upper limit of 22 captures, leading to an additional 2249 allowable moves. All together, that is 11149=5439 total moves. I'm probably off by a few.
> A maximum of 8 pawns (4 white and 4 black, for example) can possibly be advanced over the course of the game to the opposite side (6 squares ahead from their home square).
Not so! Pawns move diagonally via capturing, which theoretically could allow white to promote all 8 pawns just in the d column, and black to promote all 8 in the e column (at the expense of various other pieces).
edit: of course, you'd run out of pieces first, but you can accomplish something similar by using multiple columns.
Sample game start that accomplishes a subset of this (2 pawns promoted from each side, 6 pawns remaining from each side):
> A maximum of 8 pawns (4 white and 4 black, for example) can possibly be advanced over the course of the game to the opposite side
I think they all can.
If white’s A pawn takes a black piece in the B file and black’s B pawn takes a white piece in the A file, both white’s two B pawns and black’s two A pawns have a clear route to promotion.
You can do the same for files C and D, E and F, and G and H, at the cost of 8 taken pieces.
Of course, that “white’s A pawn takes a black piece” is wasteful in the sense that it is both a pawn move and a piece being taken, but I think it still is better than letting the pawns end up facing each other without being able to move more.
That probably involves creating the maximum number of pieces, by capturing 4 pawns to promote the 12 others.
Let's give each side 1 king, 3 queens, 3 rooks, 3 knights, 2 light squared bishops, and 2 dark squared bishops.
Then have these move through as many board permutations as possible without triple repetition. This would give a multinomial of (64 choose 36 1 3 3 3 2 2 1 3 3 3 2 2) ~ 4.6 x 10^41 positions to move through, which could be multiplied by 2 for side to move (over estimating a lot since many positions will have the wrong king in check, or the right king in impossible check) and another factor 2 for first repetition, giving roughly a 2e42 upper bound.
No mutual agreement is needed. Either player can decide to claim a draw by threefold repetition (§9.2) or 50 moves (§9.3). The only difference with the fivefold repetition and 75 move rules (§9.6) is that those draws are automatic.
The rule says a player can claim a draw, but they are not obligated to do. So, if you're a player and want to exhaust the search space, this only helps you if you seek a draw; but perhaps there would be a guaranteed win somewhere if you kept playing (and the opponent didn't claim their draw).
There's the usual limits where one may claim a draw (threefold repetition or 50 moves without capture or pawn move), but there also are limits where a draw is automatic and should be enforced by the arbiter even if players do not request it (fivefold repetition or 75 moves without capture or pawn move).
One could imagine some games require captures, castles and en passants to reach, so maybe in the general case, but devil indeed. I thought I recognized Tromp from Equihash work and indeed same person.
I was thinking about writing a reverse move generator for chessIO just recently. Shouldn't be too hard. The question is how large the tree will grow. Its a fascinating idea looking for useful applications :-)
I think it may be possible to automate finding what I would call proof game kernels, which is just the subsequence of pawn moves (including promotions) and pawn captures.
One could further simplify the search by abstracting away from the exact location of pawns, but recording only their color and order within each file.
Many of the 381 illegal positions can be proven illegal just by absence of such proof kernels.
Proof game kernels can also guide construction of full proof games.
I in fact corresponded with Francois in the past 2 weeks about the possibility of using his retrograde analysis program jacobi [1] for finding proof games, which he was kind enough to explore. It turned out to be infeasible, even when providing the program with a sequence of requires pawn captures and promotions.
"They're all legal. That is, reachable from the starting position in a valid game of chess."
Help me out on the legality of some of these boards. I see excess pieces on many boards (for example, 2 or more queens, 4 or more knights of one color).
There is sometimes a point when you need to avoid giving stalement, like in the famous Savedraa study [1] or the vastly more intricate Babson task [2].
Sometimes the queen having both rook and bishop moves is a liability. There are positions (real positions from real games, not merely hypothetical ones) where promoting to a queen results in immediate stalemate, while promoting to a rook wins the game.
There are even times when this is the right move. Sometimes you can put them in check by promoting to a knight, for example, where a queen would not. Common in beginner puzzles.
This is a very nice illustration of this, where a player had to turn off autoconversion to queen on the last seconds to win the game: https://youtu.be/HFG8pCInJKw
So assuming all pawns of one color are converted, I guess 9 queens or 10 knights would be a legal, if unlikely, board setting, but 10 queens or 11 knights are not?
The 10 queens situation is obviously impossible, but so is having 2 white queens and black has all of his pawns on the starting squares.
It's more difficult than you're thinking. If white has 6 dark squared bishops, they you know that he promoted at least 5 pawns on dark squares so one pawn must have taken a piece since it's promoting on a dark square instead of a white one. Not every board set-up will have enough missing pieces that 5 pawns can maneuver to get promoted on dark squares.
We don't know whether the game is already a forced win for white before a single move is made. It could be. So this system is not workable because we don't know what positions are not forced wins.
So at only 10 seconds per game, we could annotate all these positions with Stockfish in a mere 10^38 years. We might even be done before all the stars go out!
> Black to move, and in the final position, the pawn at h4 can be captured en-passant.
> They're all legal.
But then, looking at the final position[1], black is in check by the knight on b2. If white's pawn can be captured en passant, this implies the knight was not the most recent move, so the black king was in check on the previous turn as well.
It's obviously not legal to remain in check. What am I missing?
I'll have to make some changes to my README.
Meanwhile, congratulations on spotting the error. And I'll be sure to mention you in the eventual publication.
This underscores the need to back up my classification with proof games...
But just today github user @mcdallas found another position misclassfied as legal [1], so the two misjudgements cancel out and the original 538 count currently still stands. Lovely:-)
It's funny-- except for Tenoke all the responses so far boil down to essentially this.
I'll try again.
Assume an alternate reality where this incredibly important rule doesn't exist. In it, the other player simply takes the king on the next turn from a neophyte who didn't realize they are still in check.
What bad things would happen as a result of the non-existence of the gratuitous rule?
And don't just speculate based on the zero cost of posting on HN. Give me the real reason based on the history of the creation of chess rules and/or the documented behavior of real chess players in history.
> Assume an alternate reality where this incredibly important rule doesn't exist. In it, the other player simply takes the king on the next turn from a neophyte who didn't realize they are still in check.
This is not merely an alternate reality; this is effectively the reality of blitz chess, where capturing the king is a way of claiming victory by declaring that the opponent made an illegal move when they didn't move out of check. In blitz chess you do not have the right to correct illegal moves after the opponent points them out.
If the penalty for the specific illegal move of not getting oneself out of check is to lose the game, what could the practical significance of the rule possibly be?
The other respondent is claiming that chess would become a game of "gotcha," as if the rule somehow prevents chess players from faking injuries to distract the chess ref and get free moves.
There is no immediate penalty, normally the opponent notices the illegal move and points it out, and the player has to undo the illegal move and continue with a legal move. Now if the player disobeys, then the opponent is able to declare the game forfeit.
An interesting edge case is if the opponent does not notice the illegal move. See FIDE for details.
I feel as if I'm asking something fundamental that hasn't been considered by insiders. As if I asked music afficionados why Beethoven's Appassionata Sonata couldn't be performed in F-sharp minor and the response is something like, "Because arbitrarily changing the keys of sonatas would make a travesty of classical music, and performing the piece in F minor supports the preferences of the people who enjoy listening to classical music."
I don't know the history, but it's consistent with all the other rules, e.g. checkmate stops the game one move before the king is captured, stalemate occurs if the king would have to open himself up to capture, etc.
Chess is a politically-themed wargame featuring monarchy. The King, being top kick, makes the rules of the land. Of course the King would enact such a rule that makes putting/leaving him in danger illegal.
Think about actual, medieval monarchs in their castles, holding literal absolute power over everyone. If someone were to invent a board game featuring a King, and the King were to be made aware that you moved him into danger and got him captured, he might have your head.
Being in check means it’s your move and the pieces are positioned so that if it was your opponent’s move they could capture your king. So, to “remain in check” would mean to make a move which still allows your opponent to capture your king. If this were allowed the opponent would just capture your king and you would lose. Instead, the rules of chess require you to “get out of check”, i.e. make a move which prevents your opponent from capturing your king. If there is no such move you are said to be in “checkmate” and you lose.
It's a good question as most games, including chess have few rules about making otherwise legal moves illegal just because they might be suboptimal. In novice games the other player might not even realize they can win, so it being illegal to stay in check is an oddity but one that's actually in the rules.
As far as I’m aware, the only game-theory difference between chess and a variant of chess
where moving into check is legal, is that stalemate exists. Otherwise the “can’t move into check” rule is basically useless.
I'm assuming you're refering to the number of legal Go positions versus the number of legal chess positions.
Obviously the former is more fun, since you feel like you scaled the summit when you determine the exact count in all its glory.
When you can only estimate, you cannot reach the summit, only reach a little higher than the previous explorer by spending much more effort on your estimation climb. I do feel some satisfaction in having established base camp though:-)
No, I mean the number of legal Go and chess positions vs Busy Beaver numbers. BB sequences don't have much in the way of summits, but they do allow for establishing basecamps more precisely.
I very much enjoyed determining functional busy beaver numbers [1].
Maybe somewhere in between the enjoyment from the computable numbers of Go and chess. There is no estimation involved there. Although there are lower bounds.
The other difference being that it's a much more esoteric subject (on account of the prevalence of the Turing Machine based definition) with a much more limited audience.
Absolutely awesome project. I will definitely try to contribute as I can in finding proof games. Though, I want to understand the problem and all the methods and mathematics used a bit better. Do you have any recommendations of resources? Hell, even if you just list topics I should look into it'd be helpful.
You could check out all the references at the bottom of the README. The ranking implementation was heavily inspired by Brent Yorgey's Data.Enumeration.Invertible [1] that he blogged about at [2].
reply