Ah, wow, I read the article wrong all this time, thank you. I thought they meant "the maximum number of moves you can make to reach any chess position is 218", and I was wondering why the article made no sense to me.
It's conceivable that the maximum number of plies (half-moves) you need is 218. The best known lower bound on needed number of plies is 185 for "Harry Goldsteen's furthest position" https://timkr.home.xs4all.nl/chess2/diary.htm
So perhaps the hardest-to-reach position manages to improve on that by an additional 33 plies.
I read it as “there is no legal position for which the minimum number of moves necessary to reach it is greater than 218” but I also did not read the whole article before coming to check the comments
It’s also rare to have one with more than 50 moves. I’m curious if this class of observation will help establish a true bounds. Especially because we don’t have a definition of what it means - my instinct is to first do that, so “infinity” isn’t the obvious upper bound.
Proving this feels more difficult than proving what’s in the OP article, because here you have to show path lengths between original position and all possible positions have a max length, while OP article had to show all positions have a max degree. Path length just seems like a harder problem compared to node degree.
The upper bound is a few thousand. A game is considered drawn if no pawn has moved and no piece has been captured for 50 moves. And there's also the threefold repetition rule: if the same exact position (counting things like castling eligibility etc) occurs three times it's drawn.
I think the upper bound is 6300, then. Each pawn can move 6 times, times 16 pawns, times 50 moves before a game ending draw, plus each capturable piece that can delay the game another 50 moves (15 on each side)
You read a comment saying it’s rare to have more than 200 moves, then a reply noting more than 50 is also rare, then suggested you were confused and maybe it was unreadable and asked “What?” because…some games have above 50 moves. shrugs
Thanks for note re: upper bound with 75 moves without pawn advancing constraint.
Huh. I also have that personal policy. Yet this time I jumped first to the comments before reading the article. I’m not certain why. Perhaps I subconsciously intuited that the ambiguity in the headline might be resolved by some of you smart people. Brains are weird; mine is, anyway.
Thanks for that link! I was looking for that answer a few years ago, but I couldn't find anyone who had carried it out all the way through (with the cost of "switching control" fully accounted for), nor many people who were even aware of the 75-move rule.
The 50 move rule is still there: either player has the right to claim a draw after 50 moves without a pawn move or a capture. So the game can end then if either player wishes it to (and it almost always will end, because at least one player can expect no better than a draw).
After 75 moves, however, it's not optional, the game has ended. It's still a draw if the game subsequently "ends" in checkmate or a loss on time, though maybe not the players sign the score sheet, move on to the next round, etc.
Actually no. 50×(16×6 + 32) = 50×(16× 8) works I think. Every 50 moves, move a pawn or capture. There are 16 pawns. Each pawn can be moved 6 times, so there are 16×6 pawn moves available. In addition there are 32 captures available.
The 50 move rule is a rule of chess so it must be considered.
The 3 repetition rule is an opportunity for one of the players to declare a draw, but games can continue beyond that. The mandatory draw rule is 5 repetitions. In any case, the 50 move rule is far more limiting as to the number of moves in a game, since repetitions are necessarily neither pawn moves nor captures (the whole point of the 50 move rule being limited to those is that they are irreversible).
Not explicitly, but when you consider the "cannot repeat the same board layout three times" rule, the number of moves possible in a game does have a limit.
The 3 repetition draw rule has no bearing on the number of possible chess positions. And for the number of possible moves in a game the 50 moves with no capture or pawn move rule is a much more stringent limit.
BTW, the 3 repetition rule only comes into play is one of the players invokes it ... games can legally have more than 3 repetitions, but not more than 5 repetitions.
I didn't know it required a player to invoke it, I was basing the statement on chess implementations I've read (and written) where it kicks in automatically... but the 5-time limit you mention still supports my case that there's an upper limit. As long as the number of pieces remains the same, there are a finite number of arrangements for them so eventually (after a finite number of moves) a position would be repeated enough times. If a piece is captured (or converted) it resets this but still yields a finite number of new arrangements. Eventually you either cannot avoid the repetition, or a win condition is met, or a draw for insufficient material.
Compare this to, say, the L game, where the number of moves is unbounded.
Your "case" that there's a limit isn't in question ... as I said, the 50 move rule is a far more stringent limitation. And those 50 moves cannot include repetitions--they are captures and pawn moves, which are irreversible.
If you read my comment that you responded to carefully, you will find that it is precise and accurate--as I said, the repetition rule has no bearing on the number of positions.
Yes, very strange that the phrase "possible moves" never occurs in the article. The key word is "possible". The article consistently just uses the phrasing "have moves" but this is not an obvious way of phrasing things to the average person (although I think it's more common in chess lingo).
in chess lingo, most common is "moves"; only in a weird circumstance (beginners?) would you need to say "legal".
the "possible" qualifier would probably be used for an "english" reason rather than a "chess" reason, to suggest "future" moves as opposed to the moves already made to get to a position. it would be more likely for whatever reason to say "how many possible moves" than "how many future/hypothetical moves", i.e. the use of possible is not to rule out the idea of impossible, simply to mean how many "could you make now from a particular position" and/or i guess to suggest "possible initial moves" as opposed to future follow-on moves.
the ambiguity is not really in chess, it's in english (and probably every other language also)
"moves" includes the idea of possible. "reachable" chess positions can only be the result of moves which are only those possible, and any follow-on moves would also only be those that are possible
But if you say a position "has possible moves" (or "available moves") that unambiguously means moves that are possible from that position (i.e., future moves), whereas simply saying that a position "has moves" is ambiguous about whether those moves are in the past or the future.
Right, and by "reachable" they mean it is theoretically possible to get to this board position through a normal (albeit obviously methodically chosen) series of moves.
I thought they meant that no game could go more than 218 moves. I can imagine some upper limit since three-fold repetition ends the game. But it’s a lot higher than 218.
Another relevant rule is a draw after 50 moves without a capture or a pawn move. But yes, the maximum number of moves would be extremely large when both players are trying. Just think of a first 2 moved allowing the king out, an outrageous king march, followed by another pawn move...
Thank you. I don't understand why people can't just explain what they're talking about before spending paragraphs talking about it. I thought this was like "After 218 moves there is no reachable chess position" which made no logical sense to me but I don't know enough about chess.
Oh, that makes more sense. That is an interesting thing to examine, but I wonder how useful it is. It reminds me of a tip I heard about improving at chess by actually counting all legal moves in a position so that you ensure you're not completely overlooking an option.
The caption on the first position is "Reachable chess position with 218 moves for White, published by Petrović in 1964."
And the title is unambiguous: "There is no reachable chess position with more than 218 moves" -- that cannot possibly mean "There is no reachable chess position that it takes more than 218 moves to reach". Also, lichess is a chess site, where people are certain to know that chess games can go way beyond 218 moves.
It should be obvious that there are no 8.7 × 10^45 possible chess moves from any chess position.
All pieces have less than 32 moves per piece and 19 pieces means less than 608 moves.
No, they do mean possible moves and they don't mean maximum length game. There are on the order of 10^45 reachable chess positions. The article did not say that was the number of moves from one position. The article says 218 is the maximum number of moves from one reachable position--it's the whole point of the article!
Their post was edited to remove the part I was responding to; the "do" in my post was directly correcting the "don't" in their original post, and vice versa.
Every board on the page, with the exception of the illegal "all queens" board, has a black king. The king is the one with the cross above the crown. In the first board, the 218 winner, it's at A1.
The first image, which I assume is the solution because the title is 'Reachable chess position with 218 moves for White, published by Petrović in 1964.', has no black king?
No, it's 100% on you. If the piece on a1 is a white king, then what's the piece on f1? And why would there be no black king, when the subject is reachable (and thus legal) positions?
Interestingly, mixed integer linear programming solvers already support these. The technical term for this is 'row generation'. It comes from the usually way these problems are written in matrix form, where rows correspond to constraints and columns correspond to variables.
(Dynamically) adding a row is equivalent to introducing a constraint only if it's violated.
This approach is often used for the traveling salesman problem.
relaxing and omitting chess rules also changed the choice of variables. I did try lazy constraints etc. before diving into the math, but they did not yield a significant speedup. For example, not considering the white king as being in check simplified A LOT.
> relaxing and omitting chess rules also changed the choice of variables.
I wonder if you can recast some of that in terms of (dynamic) row generation?
> I did try lazy constraints etc. before diving into the math, but they did not yield a significant speedup.
Yes, I can believe that. My point wasn't so much that using heuristics like these is somehow bad, but more that the off-the-shelf solvers can be made to cooperate with (many of) your heuristics.
> For example, not considering the white king as being in check simplified A LOT.
I guess you could classify that as branch-and-bound, if you squinted really hard?
Well, my point is that you can encode the tricks described in the linked article directly in a modern MILP solver in a way that is legible to the solver. We'd expect similar behaviour in that case, or perhaps slightly better, because the solver can 'see' them better.
Yes, if you do a naive programme only, it would be a massive search space.
Just want to give Lichess a shoutout here. They are fantastic, provide great content, have things for free that you need to pay for on Chess.com, and a fantastic amount of variants.
Even better, the level of play in those variants, like 960 or Crazyhouse, is MUCH higher on Lichess than on Chess.com.
It's free, it has the same features as commercial servers, it's open source, developer-friendly, with no ads (not even on free accounts) and a transparent corporate structure under French law.
Genuinely interested in being educated here: If Gurobi's integer programming solver didn't find a solution better than 218, is that a guarantee that there exists no solution better than 218? Is it equivalent to a mathematical proof?
(Let's assume, for the sake of argument, that there's no bugs in Gurobi's solver and no bugs in the author's implementation of the problem for Gurobi to solve.)
I guess I'm basically asking whether it's possible that Gurobi got trapped in a local maximum, or whether this can be considered a definitive universal solution.
Yes, if Gurobi and my code run as intended and I did not mess up any thinking while simplifying my chess model, then what I did is proof that the maximum number of legal moves available in a chess position reachable by a sequence of legal moves from the starting position is 218 (upper and lower bound). Gurobi proved the entire search space as "at most as good" using bounds, basically.
In addition to the value of the best integer solution found so far, Gurobi also provides a bound on the value of the best possible solution, computed using the linear relaxation of the problem, cutting planes and other techniques. So, assuming there are no bugs in the solver, this is truly the optimal solution.
Unless I missed something, though, the highest bound the author reported for the relaxation was 271 2/3 moves, which is obviously significantly higher than 218...
I think that was an intermediate model. The author updated it, then Gurobi solved the new model to optimality (i.e., the bound became equal to the value of the best solution found).
> With this improved model, I tried again and after ~23 000 seconds, Gurobi solved it to optimality!
> Gurobi solved the new model to optimality (i.e., the bound became equal to the value of the best solution found).
Ah, I was not aware that that's what this language indicated. Thanks for helping me understand more!
I've used Gurobi (and other solvers) in the past, but always in situations where we just needed to find a solution that was way better than what we were going to find with, say, a heuristic... I've never needed to find a provably optimal solution...
I'm not sure about Gurobi or how the author used it in this case. But in general, yes: these combinatorial solvers construct proof trees showing that, no matter how you assign the variables, you can't find a better solution. In simpler cases you can literally inspect the proof tree and check how it's reached a contradiction. I imagine the proof tree from this article would be an obscenely large object, but in principle you could inspect it here too.
Well, if the solver isn't wrong and there were no bugs in impl, yes, the approach is rigorous. Allow strictly more "powerful" configurations yet still prove that the maximum is X, then achieve X through a construction, is standard math
One is "legal" the other is "total problem space"
From a computing point of view, the total problem space is what matter because you still have to "compute" if it's legal or not before moving on. There isn't a straightforward way to only iterate over legal positions.
a friend of mine pointed out that my article is being discussed in this forum.
I am sorry for choosing a suboptimal title and I hope that it is unambiguous now. I am grateful for your feedback and kind words!
If you have any questions, also in regard to proving similar chess facts, I'd be happy to help ^^
That's ceil(log2(~4.8x10^44)) = 149 bits. But to make it efficiently decodable you'd use the ceil(log2(8726713169886222032347729969256422370854716254)) = 153 bit representation of the ChessPositionRanking project linked to in my other comment. The ChessCounter project does not provide an efficiently decodable code.
The king can reach any of 64 tiles. Rooks, queens, and knights can also do so, but they can also be captured, so 65 states for those 5 pieces. Bishops can only reach half of those tiles, so those two pieces get 33 states each. Pawns are interesting: they can promote into 4 pieces that each can move 64 tiles, they can be captured, or they can move into a somewhat variable number but 20-30ish positions as a pawn, or about 290 states per pawn. This means it takes 111.something bits to represent the board position of a color, or rounding up, 224 bits to represent the board positions of both black and white. En passant and castling restrictions don't add to the bit representations once you round up, since that's just 1 extra state for several pieces. That's probably the most compact representation for a fixed-size direct board representation.
For a sparse representation, note that both kings have to exist, so you can represent the live pieces with a base-10 number of n digits with n + 2 64-bit numbers representing piece position, and a little bit extra information for castling and en passant legality. If half the pieces are gone (a guesstimate for average number of pieces on the board), that amounts to about 180 bits for a board representation.
Move history requires about 10 bits per move (pair of white/black turns, with a ply of around 32 = 5 bits), which means you get to 18 moves, which appears to be somewhat shorter than the halfway point of an average chess game.
To be honest, it looks to me like getting more compact than the upper hundreds will require building impossibly large dictionaries.
So, either a fixed-length encoding of the whole board, 64 * (4 bits) = 256 bits = 32 bytes.
Or, sparse variable length encoding of pieces only, 6 bits to index each of 64 squares, = 10 bits * piece count. E.g. initial position takes 32*10 = 320 bits or 40 bytes.
While this is an upper bound for a "board position", it should be noted that it is not an upper bound for a "game state". That includes the (unbounded) whole board position history because of the threefold repetition rule. If you ignore that (and the fifty-move rule which can alternatively be kept using a six-bit counter), you also need the castling state and the en passant state.
Plus one bit of the player on move, obviously :-)
The vast majority of the positions are illegal. There is only 1 black king on the board; practically all of the represented positions have more than one. And there are over a dozen kinds of pieces to repeat that for. A better upper bound is almost 100 orders of magnitude smaller.
The 8.7e45 "restricted" number in that repo rules out certain patterns of pawn promotions. It looks like the 5.68e50 "general" number is the true upper bound, allowing any promotions possible.
The black pawn on b2 is eating a lot of possible moves for the other pieces…
It has only one legal move, take the Knight on c1. If that pawn wasn't there it would free that square for 4 white queens and a Knight. But of course the black king would already be in checkmate so these moves wouldn't really be available.
Tempting to put that e5 Queen elsewhere so that it doesn't immediately checkmate and leave the b2 square available for others.
edit: I imagine that pawn also needs to survive that far in order to avoid a stalemate.
The black b2 pawn has no moves in the position with white to move.
If it were black's move, it would still have no moves since it is pinned by the white queen on e5. If it were not pinned it would have 4 moves, as it can also underpromote.
The position is White to move, so even if the b2 pawn was not pinned by a white queen to the black king, it could not move. The b2 pawn is necessary to shield the black king from checks as this position is White to move - otherwise it would be illegal.
Also, rest assured, I checked everything thoroughly. There is indeed no way to squeeze out more than 218 legal moves for White here, but it's fun to try and I'm glad that people actually care about my article, didn't expect that, haha ^^
I was also confused about "black pieces are useless" as 2 white queens looking at each other can be replaced with 1 white and 1 black to add moves about eating each other - but then I realized it's simply "only 1 side can move"
It's white to move. If black is in check with white to move, that makes the position illegal, and unreachable -- there's no possible legal move by black that led to this position where he is in check.
Replacing one of the black pawns by a white knight would add some moves, but there is no budget for that -- both knights are already on the board, and all pawns were promoted to queens. (And replacing both pawns would again make it impossible for black to have made the previous move)
It's 271.666... moves, not 271.0 :) This bound comes from model where whole decisions (0 or 1) are relaxed to continuous ones (0.0 to 1.0 and anything in between), e.g. a piece can only be 0.23 there and only be 0.843 able to make a particular move. The advantage of this black magic is that it is way faster to compute and only overestimates the number of moves - hence we can use that to prove away bad partial solutions. Without a technique of this kind, searching the solution space would be absolutely intractable!
I did read the entire article yeah, and I was rounding down with "271", but it wasn't clear to me what change you made that got you to the finish line. Are you saying that the next improvement was to force Gurobi to use integer values? It's surprising to me that wouldn't kill performance since ILP is NP-hard whereas real LP can be solved in polynomial time.
This part is unclear; what exactly did you change? Are you saying that the LP relaxation has value 271.666, but, when you enforce integrality, Gurobi can actually find and prove optimality of a solution with value 218?
Were you really just solving LPs up to this point in the article? How can these intermediate LPs be so slow to solve (6+ years) and yet Gurobi is able to solve the integer-restricted problem?
I've always been solving the integer problem of course. But throughout the article, I improve the model formulation again and again through insights, which makes the LP relaxation tighter. Initially, it gave 305.0 as upper bound, but after tightening the model (addind constraints that cut off that 305 solution and others) it gives 271.666...
- which leads to insanely faster search. It's like brute-forcing through all passwords of length 20 and a wizard telling you that you're wrong when you reach character 7 instead of 13.
I found a position that takes 78,352 moves and can't find a shorter combo. Both white bishops end up on dark squares. You have to castle at just the right moment. There is a race condition with a window far too narrow to be noticeable in any normal play, but a timing analysis uncovered it. There may be more.
Am I missing something, or is the configuration shown initially not actually reachable? It's white to move, yet the black pawns are in their starting location and the black king has no adjacent empty square, it's entombed by its pawns and the white bishop so the configuration could not have been reached.
To be clear you're misunderstanding the position though. Black pawns are NOT in starting position. They've moved all the way across the board. Those are white pawn starting positions.
Pure defensive (and extremely rude and hostile) projection. (And the response is more of the same, and full of fallacies and false statements). There was no condescension in my comment, just an attempt to be helpful (speaking of "suppression", I will attempt that again with this person). I did not say your question was stupid (it wasn't), I said that you were projecting stupidity on the author of the article (I didn't say you think they are stupid, but apparently this distinction is too subtle for some), and that warrants a rethink.
That your comment was downvoted to death indicates maybe you should reconsider how you are being perceived if you truly believe you weren't (and still aren't) being condescending. I don't believe my comment was any more rude or hostile than your original one.
If people were to follow your advice as a general rule, that's how we get groupthink, and how learning is suppressed by making people afraid to ask questions. See the children's story "the emperor's new clothes" for an example.
It takes effort to be negative to see a comment opening with the poster saying "am I missing something" and think they're calling the author stupid instead of acknowledging their own ignorance.
Probably by just thinking about it and working to incrementally improve their answers. I'd expect plenty of people solved it before them but never published or publicized their solution. It's quite logical in many ways. For instance just thinking about the problem abstractly:
- You can only have 9 queens and they're going to want to be as centrally placed as possible with as little overlap as possible.
- The black king will need to be tucked in a corner and covered by a minimum of his pieces and nonchecking pieces of your own.
- All your other pieces, if useable, will probably end up on the edge of the board since minimizing the number of squares they block is likely to be more impactful than maximizing the number of squares they cover.
There's probably other heuristics I'm not considering, but just with those 3 you're already well on your way to the solution. So you'd lay out the pieces, and then try to find a way to do it one move better, and iterate! The concerns I'd have: pawn promotion can complicate things dramatically. Pawns can promote to 4 different pieces which would technically be 4 different moves. And a pawn can have up to 3 different paths to promote - so that's 12 possible moves tucked in a very tiny space. And then king placement - castling can add up to 2 more moves, and so compensating for that (and the corresponding rook position) adds some complexity.
Composing such a position is much easier than mathematically proving that there isn't a better one. Perhaps there is an elegant proof. Perhaps they had reasoning that proved that they couldn't do better while composing it. Probably involves plenty of case distinctions. So I decided to just let a computer reason through it, also because human minds are fallible ^^
Glancing at it a chess players first instinct looks to be the "solution".
Assume all pawns are queens, then maximize queen moves, work backwards from there. Couple of other "obvious" assumptions such as minimal black pieces, which means shoving the king in a corner but somehow not in check, Rooks cover the next largest amount of space so they're going in corners, bishops will be mirrored, etc.
Not to say it isn't still impressive, but I always wonder how many "sane" positions there are for solving a puzzle like this in the first place. The paper quotes some huge number and someone else says it's a smaller, but still massive, number, but when you look at the stated goal and start from some obvious starting points, start working out rules (obviously 4 queens right in the middle blocks other queens and costs space), and eliminate symmetrical positions, well you're left with a decently solvable problem. At least compared to the kind of shit that's usually brute force solved.
Edit:
This is actually a fun one to think about for a bit the more I look at it.
It quickly becomes apparent that your basically getting 7 moves out a of a rank/column MAX, so you maximize for that first.
It quickly becomes apparent that the knights L move shape is also the optimal way to start tiling your 9 queens to maximize for squares taken.
As I said before the black position obviously has to be the dead minimum, and it makes sense that'd be a king and 2 pawns due to various end game stuff (basically impossible to prevent the king from being in check otherwise while taking up as much space as possible).
Once you know you're doing that with the black king you'll want to "block" the remaining space with pieces that can't threaten it, so you shove a bishop adjacent (which can still take the pawn), and figure you're going to mirror that bishop because that's kinda how bishop's work in play/mathematically.
It's actually quite neat to see how each step sorta leads you to the next one, like one of those metal puzzles or the sudoku's with unique rules and only 1 or 2 starting numbers.
Still i'm positive if I hadn't seen this picture first I probably NEVER would've gotten this answer correct, but I do think i would've come closer than I ever expected.
Edit 2:
Ahh i do see they have at least one or two solutions that are 218 where there's only 2 black pieces. I'm somewhat surprised that's a possible legal position but so be it. Interesting that still leads to the same net realestate. Thats the one area i'd expect to gain something if you could cheat.
Lots of clarifications re what they mean by "number of moves"; but seems like they could productively have dropped the term "branching factor" in a couple places and thereby cleared the whole thing up.
Meanwhile, for the game of Go, as played on a standard 19x19 board, we have:
The maximum number of possible next moves is 361, which happens only in the initial empty position.
The 361 hardest-to-reach positions (assuming logical rules like [2]) are all the positions with 360 white stones and 1 empty point. these take 2*361 = 722 ply to reach, with black passing all their turns.
And these answers were found without checking all 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935 legal positions :-) [1]
A game of Go can be legally infinite due to recaptures. (player passes 360 times, then eats the entire board and it starts over).
It's also a natural infinite game due to Kos which can be the best move to play. This requires a set of extra rules to prevent. (Ko, superKo, triple kos, etc)
White cannot play on the last empty point as this would be suicide, which is prevented by the (assumed) superko rule forbidding repetition of the empty position.
The phrasing "Legal but non-reachable " makes clear that they use some notion of legal that differs from the normal one of reachability.
It's hard to imagine what sensible notion that could be though.
Something like: each side having only one king, no pawns on first/last row, at most one king in check, etc ?!
The caption of the last diagram is "Legal but non-reachable position with 271 moves for White. Corner queens can be replaced with bishops." There are 24 white queens.
That's the difference between illegal an unreachable. To reach that position you'd need to start from a different point (start both sides with 16 pawns or w/e), but you wouldn't need to break any other chess rules.
If you can start from any arbitrary different point, you can just start from the point you’re intending to reach, and don't need to break any other rules.
As per FIDE rule 3.10.3 "A position is illegal when it cannot have been reached by any series of legal moves". The position isn't legal per FIDE rules.
Beyond there being too many queens… black could not possibly have made the last move. For white to have any moves right now, the last move must have been black moving the king to H8. But G8, G7, H7 are all occupied, so where could the King have moved from?
Legality is a long standing term of art used by chess problem creators. Essentially it means a position withtwo kings on the board, non touching, and not both in check. And no pawns on first or eighth ranks. It has nothing to do with whether the position is reachable from standard chess rules. Along came FIDE in 1999 with its standardized nomenclature but that doesn't invalidate the terminology used by chess problem creators in their own work.
I don't think I’ve ever heard it used like that, and in trying to find any example other than the page we’re commenting on, I’ve only found counterexamples.
Whether it’s wikipedia’s 'Glossary of Chess Problems' or OzProblems or 'Sam Loyd and his chess problems' from 1913, they’re all using 'legal' as synonymous with 'reachable'.
I'm not sure but I think the original utility and motivation for this mathematical puzzle is how to represent possible legal moves when programming chess, and this would be evidence that an 8bit unsigned integer is sufficient for the worst case scenario, although you would need some complex kind of encoding mechanism to make the representation terse enough to represent the common moves along with 7 promoted queens in the same 256-moves space.
Practically I think I'll stay with a fixed-length encoding for each of the starting pieces and their movements assuming maximum freedom, while adding a variable length variable in case of promotions.
Although nowadays with OOP and classes and superfast CPUs you probably have entirely variable length encodings, you know, an array of piece objects each with their own legal_moves function. But back in the day, when chess engines were written in C, these things were managed globally with all kinds of hack to save space, not due to space reasons, but to improve locality by reducing cache sizes.
For example, even though the chess board is 8x8, a common trick is to make the board 12x12 to account for knight moves that go off the board (and mark them as ilegal of course.) Which goes to show that even with efficiency as the upmost consideration, a terse representation is not ideal, so I doubt we are going to see 8bit variables to represent moves.
my motiviation was intellectual curiosity and some random Lichess reading about chess engine authors wondering whether 8 bit e.g. numbers 0 to 255 (or 1 to 256), will be enough for storing the number of legal moves. Which triggered my brain: "I HAVE THE KNOWLEDGE TO SOLVET HIS FOR HUMANITY :O". It's not at all relevant practically, as you have elaborated, and there probably is a more elegant proof that 256 can't be exceeded.
> although you would need some complex kind of encoding mechanism to make the representation terse enough to represent the common moves along with 7 promoted queens in the same 256-moves space.
If you have an algorithm for generating the list of legal moves in a position that always generates them in the same order, you can just use the index at which the move is in the list.
Of course that would come at the cost of speed (you always need to generate that list to know what move was made is meant).
>If you have an algorithm for generating the list of legal moves in a position that always generates them in the same order, you can just use the index at which the move is in the list.
Right, that's exactly what I'm saying, the algorithm that generates the list of legal moves would be an encoder (maps a move into an index), and the reverse would be a decoder (maps the index into a move).
You don't necessarily need to generate the list of legal moves, though. Consider a 16 bit encoding where the first 4 bits represent the piece moved, and the next 5 bits represent the direction, and the next 4 bits represent the distance and so on.
Haha yeah, I saw the code and it is pretty comprehensible but some things are curious. I thought some of the naming was amusing "ENABLE_ROYAL_CUDDLING" etc.
Maybe one of us is misunderstanding, but aren't there far fewer than 218 on the first move? The position in the article needed nine unobstructed queens to achieve 218 possible moves. For the first move, I think we could just enumerate the moves by hand, right? Eight pawns can move one or two spaces, that's 16 moves. The two knights have two moves, that's 4. Nothing else can move, can it? That's only 20 moves.
EDIT: I think I understand the confusion. A "move" in this case is a legal possibility for white's next turn. It's not talking about the number of moves in the game, but rather the number of legal choices for white in a single turn.
The initial board position is certainly reachable (and reached in every game!), but there are only 20 legal moves available: the 16 legal pawn moves for White, and the 4 legal knight moves for White.
They dont really spell it out but they mean "from this position the player has 218 possible legal moves to choose from"
Ah, wow, I read the article wrong all this time, thank you. I thought they meant "the maximum number of moves you can make to reach any chess position is 218", and I was wondering why the article made no sense to me.
It's conceivable that the maximum number of plies (half-moves) you need is 218. The best known lower bound on needed number of plies is 185 for "Harry Goldsteen's furthest position" https://timkr.home.xs4all.nl/chess2/diary.htm So perhaps the hardest-to-reach position manages to improve on that by an additional 33 plies.
The word 'available' inserted at the right spot would make all the difference in clarity here.
imo "possible" would be better
I'd go with "legal," which also implies possible.
I thought the same, but no doubt pawn promotion rules dramatically increase the depth needed to reach certain positions.
Is that weird? I feel like it’s plausible though. Very rare to have chess games with more than 200 moves.
Yeah I kind of thought that it meant "you can get to any valid position in 218 moves max", it was hard to parse.
I read it as “there is no legal position for which the minimum number of moves necessary to reach it is greater than 218” but I also did not read the whole article before coming to check the comments
It’s also rare to have one with more than 50 moves. I’m curious if this class of observation will help establish a true bounds. Especially because we don’t have a definition of what it means - my instinct is to first do that, so “infinity” isn’t the obvious upper bound.
Proving this feels more difficult than proving what’s in the OP article, because here you have to show path lengths between original position and all possible positions have a max length, while OP article had to show all positions have a max degree. Path length just seems like a harder problem compared to node degree.
The upper bound is a few thousand. A game is considered drawn if no pawn has moved and no piece has been captured for 50 moves. And there's also the threefold repetition rule: if the same exact position (counting things like castling eligibility etc) occurs three times it's drawn.
I think the upper bound is 6300, then. Each pawn can move 6 times, times 16 pawns, times 50 moves before a game ending draw, plus each capturable piece that can delay the game another 50 moves (15 on each side)
What? Lots of serious chess games last more than 50 moves
Not sure if I'm reading your comment correctly
The upper bound of moves is 8848.5 https://www.reddit.com/r/chess/comments/168qmk6/longest_poss...
... under the rule that after 75 moves without a capture or pawn advancement the game is drawn
You read a comment saying it’s rare to have more than 200 moves, then a reply noting more than 50 is also rare, then suggested you were confused and maybe it was unreadable and asked “What?” because…some games have above 50 moves. shrugs
Thanks for note re: upper bound with 75 moves without pawn advancing constraint.
More than 50 moves in a game is hardly rare, hence my surprised reaction
[dead]
lol same here.
This is not so interesting then…
I thought it was "How many moves in a game does it take to reach this position"
I thought it was "there's no position in chess that requires more than 218 moves to reach."
I thought “there is no chess problem that is both reachable from starting position and requires more than 218 moves to solve”
There are no more than 218 ways to interpret this title
It'll take at most 218 comments on HN to figure out the meaning of the submission title
It'll take at most 218 characters to express the fact I did not understand the submitted article's title.
I seriously thought they meant "it's not possible to have a chess game with more than 218 moves"
Yeah, I'm still confused.
There is no reachable[1] chess position[2] at which a player has more than 218 valid moves[3] to choose from.
[1] Able to happen while following the rules of chess
[2] The arrangement of chess pieces on the board
[3] A valid move is the motion of one piece to a place on the board, which doesn't break the rules of chess - e.g: "King to E4."
I also thought this but OP is right: https://dev.timenote.info/de/Nenad-Petrovic
> In 1964 Petrović constructed a position with 218 possible moves for White.
Same, which also damages my personal policy of reading the link before any HN comments.
Huh. I also have that personal policy. Yet this time I jumped first to the comments before reading the article. I’m not certain why. Perhaps I subconsciously intuited that the ambiguity in the headline might be resolved by some of you smart people. Brains are weird; mine is, anyway.
The right™ order is to check the comments before the article, but to read the article before commenting.
But this an interesting problem too. More specifically is there an upper bound for the number of moves in a legal chess game?
I believe 8848.5 under modern rules (with the 75-move rule, as in FIDE rules since 2014). There's a reasonably rigorous demonstration here:
https://wismuth.com/chess/longest-game.html
Thanks for that link! I was looking for that answer a few years ago, but I couldn't find anyone who had carried it out all the way through (with the cost of "switching control" fully accounted for), nor many people who were even aware of the 75-move rule.
75 move rule?! Did they go and change the 50 move rule or something, because I've never heard of it.
The 50 move rule is still there: either player has the right to claim a draw after 50 moves without a pawn move or a capture. So the game can end then if either player wishes it to (and it almost always will end, because at least one player can expect no better than a draw).
After 75 moves, however, it's not optional, the game has ended. It's still a draw if the game subsequently "ends" in checkmate or a loss on time, though maybe not the players sign the score sheet, move on to the next round, etc.
how can the longest game have half a move???
"Moves" are counted for both players. Half a move means White moved but Black hasn't yet.
thank you!
An A press is an A press. You can't say it's only a half.
there certainly is if you consider 50 moves rule.
And you can derive an easy upper bound from that as 50x8x8x2 (basically each 50 moves you make a pawn move)
if you only consider 3 moves repetition and not 50 move rule then this is harder and the number becomes one of those crazy combinatorical numbers.
> And you can derive an easy upper bound from that as 50x8x8x2 (basically each 50 moves you make a pawn move)
This is not high enough, because the 50 move rule also resets when a piece is captured.
Actually no. 50×(16×6 + 32) = 50×(16× 8) works I think. Every 50 moves, move a pawn or capture. There are 16 pawns. Each pawn can be moved 6 times, so there are 16×6 pawn moves available. In addition there are 32 captures available.
The 50 move rule is a rule of chess so it must be considered.
The 3 repetition rule is an opportunity for one of the players to declare a draw, but games can continue beyond that. The mandatory draw rule is 5 repetitions. In any case, the 50 move rule is far more limiting as to the number of moves in a game, since repetitions are necessarily neither pawn moves nor captures (the whole point of the 50 move rule being limited to those is that they are irreversible).
The 50 moves rule doesn't have be considered as it is optional. The players may claim, but they don't have to. So the game can continue.
The 75 move rule is the exact same thing but mandatory. That has to be considered.
(same thing is true for 5 times repetition vs 3 times).
Captures also reset the counter, not only pawn moves.
Not explicitly, but when you consider the "cannot repeat the same board layout three times" rule, the number of moves possible in a game does have a limit.
The 3 repetition draw rule has no bearing on the number of possible chess positions. And for the number of possible moves in a game the 50 moves with no capture or pawn move rule is a much more stringent limit.
BTW, the 3 repetition rule only comes into play is one of the players invokes it ... games can legally have more than 3 repetitions, but not more than 5 repetitions.
I didn't know it required a player to invoke it, I was basing the statement on chess implementations I've read (and written) where it kicks in automatically... but the 5-time limit you mention still supports my case that there's an upper limit. As long as the number of pieces remains the same, there are a finite number of arrangements for them so eventually (after a finite number of moves) a position would be repeated enough times. If a piece is captured (or converted) it resets this but still yields a finite number of new arrangements. Eventually you either cannot avoid the repetition, or a win condition is met, or a draw for insufficient material.
Compare this to, say, the L game, where the number of moves is unbounded.
Your "case" that there's a limit isn't in question ... as I said, the 50 move rule is a far more stringent limitation. And those 50 moves cannot include repetitions--they are captures and pawn moves, which are irreversible.
If you read my comment that you responded to carefully, you will find that it is precise and accurate--as I said, the repetition rule has no bearing on the number of positions.
This horse is dead, so I'm moving on.
The 50 moves rule also needs to be claimed by one of the players.
However there is a 75 move rule and a 5 time repetition rule that are both automatic (don't need to be claimed).
Same. I was astonished it was remotely possible to do this.
To do what?
To find "How many moves in a game does it take to reach this position". Which was a wrong interpretation.
Yes, very strange that the phrase "possible moves" never occurs in the article. The key word is "possible". The article consistently just uses the phrasing "have moves" but this is not an obvious way of phrasing things to the average person (although I think it's more common in chess lingo).
in chess lingo the most common is “legal moves”
in chess lingo, most common is "moves"; only in a weird circumstance (beginners?) would you need to say "legal".
the "possible" qualifier would probably be used for an "english" reason rather than a "chess" reason, to suggest "future" moves as opposed to the moves already made to get to a position. it would be more likely for whatever reason to say "how many possible moves" than "how many future/hypothetical moves", i.e. the use of possible is not to rule out the idea of impossible, simply to mean how many "could you make now from a particular position" and/or i guess to suggest "possible initial moves" as opposed to future follow-on moves.
the ambiguity is not really in chess, it's in english (and probably every other language also)
> the ambiguity is not really in chess, it's in english (and probably every other language also)
Sure, but the article is written in English. :-)
"moves" includes the idea of possible. "reachable" chess positions can only be the result of moves which are only those possible, and any follow-on moves would also only be those that are possible
But if you say a position "has possible moves" (or "available moves") that unambiguously means moves that are possible from that position (i.e., future moves), whereas simply saying that a position "has moves" is ambiguous about whether those moves are in the past or the future.
Ah, thank you. I was confused reading this article, thinking it's about the unique position that takes the most moves to reach.
Thanks, I misunderstood the entire article. Great writing!
How can those two things be true at the same time? Unless you appreciate misunderstanding what you read...?
What other reason would a person have for juxtaposing two statements?
You hit the nail on the head. They aren't both true which is why the second sentence is sarcasm.
How could someone ever write something while intending to convey the exact opposite meaning?
Right, and by "reachable" they mean it is theoretically possible to get to this board position through a normal (albeit obviously methodically chosen) series of moves.
Yeah I gave up when I realized I didn’t understand what problem he was trying to solve
I thought they meant that no game could go more than 218 moves. I can imagine some upper limit since three-fold repetition ends the game. But it’s a lot higher than 218.
Another relevant rule is a draw after 50 moves without a capture or a pawn move. But yes, the maximum number of moves would be extremely large when both players are trying. Just think of a first 2 moved allowing the king out, an outrageous king march, followed by another pawn move...
The confusion is perhaps caused by the word “reachable”. “No legal chess position with more than 218 possible moves” would have been more clear imho.
Thank you. I don't understand why people can't just explain what they're talking about before spending paragraphs talking about it. I thought this was like "After 218 moves there is no reachable chess position" which made no logical sense to me but I don't know enough about chess.
Oh, that makes more sense. That is an interesting thing to examine, but I wonder how useful it is. It reminds me of a tip I heard about improving at chess by actually counting all legal moves in a position so that you ensure you're not completely overlooking an option.
I had the same confusion, until they showed the existing 218 position and realized it was about maximizing white's legal moves.
If only they had appended "to choose from" to the article headline, it would have been clear from the start.
The caption on the first position is "Reachable chess position with 218 moves for White, published by Petrović in 1964."
And the title is unambiguous: "There is no reachable chess position with more than 218 moves" -- that cannot possibly mean "There is no reachable chess position that it takes more than 218 moves to reach". Also, lichess is a chess site, where people are certain to know that chess games can go way beyond 218 moves.
the word "possible" is missing
It should be obvious that there are no 8.7 × 10^45 possible chess moves from any chess position. All pieces have less than 32 moves per piece and 19 pieces means less than 608 moves.
No, they do mean possible moves and they don't mean maximum length game. There are on the order of 10^45 reachable chess positions. The article did not say that was the number of moves from one position. The article says 218 is the maximum number of moves from one reachable position--it's the whole point of the article!
The person you responded to knows that.
Their post was edited to remove the part I was responding to; the "do" in my post was directly correcting the "don't" in their original post, and vice versa.
But black has no king, so surely the game is over and there are no more legal moves?
Why does black have two pawns but no king?
I don’t understand any of this
Every board on the page, with the exception of the illegal "all queens" board, has a black king. The king is the one with the cross above the crown. In the first board, the 218 winner, it's at A1.
The first image, which I assume is the solution because the title is 'Reachable chess position with 218 moves for White, published by Petrović in 1964.', has no black king?
Look again. It's at A1. You may be confusing that symbol with a different piece.
Ugh. Sigh, I see it now - I thought that was the white king, because it has quite some white in it.
I will allocate 50% blame to my brain and eyes, and 50% to whoever designed a black king to have so much white in it :P Thanks!
No, it's 100% on you. If the piece on a1 is a white king, then what's the piece on f1? And why would there be no black king, when the subject is reachable (and thus legal) positions?
https://lichess.org/@/Tobs40/blog/there-is-no-reachable-ches... describes how the author removed some more complicated rules in the first pass, and is willing to re-introduce them, if necessary. Ie if the solution found violates them.
Interestingly, mixed integer linear programming solvers already support these. The technical term for this is 'row generation'. It comes from the usually way these problems are written in matrix form, where rows correspond to constraints and columns correspond to variables.
(Dynamically) adding a row is equivalent to introducing a constraint only if it's violated.
This approach is often used for the traveling salesman problem.
(Weirdly enough, Wikipedia has https://en.wikipedia.org/wiki/Column_generation but nothing on row generation.)
Hi, author of the Lichess article here.
relaxing and omitting chess rules also changed the choice of variables. I did try lazy constraints etc. before diving into the math, but they did not yield a significant speedup. For example, not considering the white king as being in check simplified A LOT.
Best regards, Tobi
Thanks!
> relaxing and omitting chess rules also changed the choice of variables.
I wonder if you can recast some of that in terms of (dynamic) row generation?
> I did try lazy constraints etc. before diving into the math, but they did not yield a significant speedup.
Yes, I can believe that. My point wasn't so much that using heuristics like these is somehow bad, but more that the off-the-shelf solvers can be made to cooperate with (many of) your heuristics.
> For example, not considering the white king as being in check simplified A LOT.
I guess you could classify that as branch-and-bound, if you squinted really hard?
The most commonly used term for this is lazy constraints (https://support.gurobi.com/hc/en-us/articles/360013197972-Ho...).
I'm quite curious to see if the MILP solver would terminate (given the massive search space), my guess is not.
Well, my point is that you can encode the tricks described in the linked article directly in a modern MILP solver in a way that is legible to the solver. We'd expect similar behaviour in that case, or perhaps slightly better, because the solver can 'see' them better.
Yes, if you do a naive programme only, it would be a massive search space.
Just want to give Lichess a shoutout here. They are fantastic, provide great content, have things for free that you need to pay for on Chess.com, and a fantastic amount of variants.
Even better, the level of play in those variants, like 960 or Crazyhouse, is MUCH higher on Lichess than on Chess.com.
It's free, it has the same features as commercial servers, it's open source, developer-friendly, with no ads (not even on free accounts) and a transparent corporate structure under French law.
It's almost ridiculously good. Donate if you can!
And a nice API
Genuinely interested in being educated here: If Gurobi's integer programming solver didn't find a solution better than 218, is that a guarantee that there exists no solution better than 218? Is it equivalent to a mathematical proof?
(Let's assume, for the sake of argument, that there's no bugs in Gurobi's solver and no bugs in the author's implementation of the problem for Gurobi to solve.)
I guess I'm basically asking whether it's possible that Gurobi got trapped in a local maximum, or whether this can be considered a definitive universal solution.
Author here!
Yes, if Gurobi and my code run as intended and I did not mess up any thinking while simplifying my chess model, then what I did is proof that the maximum number of legal moves available in a chess position reachable by a sequence of legal moves from the starting position is 218 (upper and lower bound). Gurobi proved the entire search space as "at most as good" using bounds, basically.
In addition to the value of the best integer solution found so far, Gurobi also provides a bound on the value of the best possible solution, computed using the linear relaxation of the problem, cutting planes and other techniques. So, assuming there are no bugs in the solver, this is truly the optimal solution.
Unless I missed something, though, the highest bound the author reported for the relaxation was 271 2/3 moves, which is obviously significantly higher than 218...
I think that was an intermediate model. The author updated it, then Gurobi solved the new model to optimality (i.e., the bound became equal to the value of the best solution found).
> With this improved model, I tried again and after ~23 000 seconds, Gurobi solved it to optimality!
> Gurobi solved the new model to optimality (i.e., the bound became equal to the value of the best solution found).
Ah, I was not aware that that's what this language indicated. Thanks for helping me understand more!
I've used Gurobi (and other solvers) in the past, but always in situations where we just needed to find a solution that was way better than what we were going to find with, say, a heuristic... I've never needed to find a provably optimal solution...
The article was interesting, but this bit felt a bit like "and then a miracle occurred".
The fractional stuff was poorly explained, I didn't understand it at all.
I'm not sure about Gurobi or how the author used it in this case. But in general, yes: these combinatorial solvers construct proof trees showing that, no matter how you assign the variables, you can't find a better solution. In simpler cases you can literally inspect the proof tree and check how it's reached a contradiction. I imagine the proof tree from this article would be an obscenely large object, but in principle you could inspect it here too.
In theory, it's not proof. In practice, it is.
Well, if the solver isn't wrong and there were no bugs in impl, yes, the approach is rigorous. Allow strictly more "powerful" configurations yet still prove that the maximum is X, then achieve X through a construction, is standard math
> There is no reachable chess position with more than 218 moves.
"no more than 218 possible next moves" would be a lot clearer...
> By checking all approximately 8.7x10^45 reachable chess positions?
That's a large overestimate.
https://github.com/tromp/ChessPositionRanking accurately estimates the number of legal chess positions at ~4.8x10^44.
Isn't that estimate just 20x bigger? Which is not a big difference considering the magnitude.
One is "legal" the other is "total problem space" From a computing point of view, the total problem space is what matter because you still have to "compute" if it's legal or not before moving on. There isn't a straightforward way to only iterate over legal positions.
Hi all,
a friend of mine pointed out that my article is being discussed in this forum. I am sorry for choosing a suboptimal title and I hope that it is unambiguous now. I am grateful for your feedback and kind words!
If you have any questions, also in regard to proving similar chess facts, I'd be happy to help ^^
Best regards, Tobi
so just to be clear: for every board position there are no more than 218 moves available? is that the understanding?
It's your turn and you have 218 moves to choose from. This is the best possible and the article proves this (assuming no bugs in machine or mind).
What is the least number of bits that can describe any reachable chess board?
update: article says there are approximately 8.7x10^45 reachable chess positions and https://github.com/lechmazur/ChessCounter says this is an upper bound.
(this would correspond to about 153 bits)
That's ceil(log2(~4.8x10^44)) = 149 bits. But to make it efficiently decodable you'd use the ceil(log2(8726713169886222032347729969256422370854716254)) = 153 bit representation of the ChessPositionRanking project linked to in my other comment. The ChessCounter project does not provide an efficiently decodable code.
The king can reach any of 64 tiles. Rooks, queens, and knights can also do so, but they can also be captured, so 65 states for those 5 pieces. Bishops can only reach half of those tiles, so those two pieces get 33 states each. Pawns are interesting: they can promote into 4 pieces that each can move 64 tiles, they can be captured, or they can move into a somewhat variable number but 20-30ish positions as a pawn, or about 290 states per pawn. This means it takes 111.something bits to represent the board position of a color, or rounding up, 224 bits to represent the board positions of both black and white. En passant and castling restrictions don't add to the bit representations once you round up, since that's just 1 extra state for several pieces. That's probably the most compact representation for a fixed-size direct board representation.
For a sparse representation, note that both kings have to exist, so you can represent the live pieces with a base-10 number of n digits with n + 2 64-bit numbers representing piece position, and a little bit extra information for castling and en passant legality. If half the pieces are gone (a guesstimate for average number of pieces on the board), that amounts to about 180 bits for a board representation.
Move history requires about 10 bits per move (pair of white/black turns, with a ply of around 32 = 5 bits), which means you get to 18 moves, which appears to be somewhat shorter than the halfway point of an average chess game.
To be honest, it looks to me like getting more compact than the upper hundreds will require building impossibly large dictionaries.
Piece type and color fit in 4 bits.
So, either a fixed-length encoding of the whole board, 64 * (4 bits) = 256 bits = 32 bytes.
Or, sparse variable length encoding of pieces only, 6 bits to index each of 64 squares, = 10 bits * piece count. E.g. initial position takes 32*10 = 320 bits or 40 bytes.
That's a fine upper bound, but it doesn't minimize but usage since it also can represent illegal positions.
While this is an upper bound for a "board position", it should be noted that it is not an upper bound for a "game state". That includes the (unbounded) whole board position history because of the threefold repetition rule. If you ignore that (and the fifty-move rule which can alternatively be kept using a six-bit counter), you also need the castling state and the en passant state. Plus one bit of the player on move, obviously :-)
The vast majority of the positions are illegal. There is only 1 black king on the board; practically all of the represented positions have more than one. And there are over a dozen kinds of pieces to repeat that for. A better upper bound is almost 100 orders of magnitude smaller.
The 8.7e45 "restricted" number in that repo rules out certain patterns of pawn promotions. It looks like the 5.68e50 "general" number is the true upper bound, allowing any promotions possible.
8726713169886222032347729969256422370854716254 is an unrestricted upper bound proven in the ChessPositionRanking project.
The black pawn on b2 is eating a lot of possible moves for the other pieces…
It has only one legal move, take the Knight on c1. If that pawn wasn't there it would free that square for 4 white queens and a Knight. But of course the black king would already be in checkmate so these moves wouldn't really be available.
Tempting to put that e5 Queen elsewhere so that it doesn't immediately checkmate and leave the b2 square available for others.
edit: I imagine that pawn also needs to survive that far in order to avoid a stalemate.
The black b2 pawn has no moves in the position with white to move. If it were black's move, it would still have no moves since it is pinned by the white queen on e5. If it were not pinned it would have 4 moves, as it can also underpromote.
Author here.
The position is White to move, so even if the b2 pawn was not pinned by a white queen to the black king, it could not move. The b2 pawn is necessary to shield the black king from checks as this position is White to move - otherwise it would be illegal.
Also, rest assured, I checked everything thoroughly. There is indeed no way to squeeze out more than 218 legal moves for White here, but it's fun to try and I'm glad that people actually care about my article, didn't expect that, haha ^^
I was also confused about "black pieces are useless" as 2 white queens looking at each other can be replaced with 1 white and 1 black to add moves about eating each other - but then I realized it's simply "only 1 side can move"
It's white to move. If black is in check with white to move, that makes the position illegal, and unreachable -- there's no possible legal move by black that led to this position where he is in check.
Replacing one of the black pawns by a white knight would add some moves, but there is no budget for that -- both knights are already on the board, and all pawns were promoted to queens. (And replacing both pawns would again make it impossible for black to have made the previous move)
I'm confused, what did he change after the 271-move model to get it to produce the optimal solutions? It just says "With this improved model"...
Author here!
Did you read the entire article?
It's 271.666... moves, not 271.0 :) This bound comes from model where whole decisions (0 or 1) are relaxed to continuous ones (0.0 to 1.0 and anything in between), e.g. a piece can only be 0.23 there and only be 0.843 able to make a particular move. The advantage of this black magic is that it is way faster to compute and only overestimates the number of moves - hence we can use that to prove away bad partial solutions. Without a technique of this kind, searching the solution space would be absolutely intractable!
I did read the entire article yeah, and I was rounding down with "271", but it wasn't clear to me what change you made that got you to the finish line. Are you saying that the next improvement was to force Gurobi to use integer values? It's surprising to me that wouldn't kill performance since ILP is NP-hard whereas real LP can be solved in polynomial time.
This part is unclear; what exactly did you change? Are you saying that the LP relaxation has value 271.666, but, when you enforce integrality, Gurobi can actually find and prove optimality of a solution with value 218?
Were you really just solving LPs up to this point in the article? How can these intermediate LPs be so slow to solve (6+ years) and yet Gurobi is able to solve the integer-restricted problem?
Ah, I see the misunderstanding.
I've always been solving the integer problem of course. But throughout the article, I improve the model formulation again and again through insights, which makes the LP relaxation tighter. Initially, it gave 305.0 as upper bound, but after tightening the model (addind constraints that cut off that 305 solution and others) it gives 271.666...
- which leads to insanely faster search. It's like brute-forcing through all passwords of length 20 and a wizard telling you that you're wrong when you reach character 7 instead of 13.
I found a position that takes 78,352 moves and can't find a shorter combo. Both white bishops end up on dark squares. You have to castle at just the right moment. There is a race condition with a window far too narrow to be noticeable in any normal play, but a timing analysis uncovered it. There may be more.
Am I missing something, or is the configuration shown initially not actually reachable? It's white to move, yet the black pawns are in their starting location and the black king has no adjacent empty square, it's entombed by its pawns and the white bishop so the configuration could not have been reached.
Proof is provided here for one of them: https://lichess.org/study/PLtuv3v5/zWPNxbSA
To be clear you're misunderstanding the position though. Black pawns are NOT in starting position. They've moved all the way across the board. Those are white pawn starting positions.
Yep that's what I was missing. Thank you for the link.
The black pawns are on white's side of the board.
That's what I missed. Thank you :-)
[flagged]
Thanks for the condescension. It really helps me file your comment's suggestions appropriately.
Here's a general rule of thumb: If the options are
a) answer someone's question, and
b) answer someone's question but also then spend triple the word count telling them it was a stupid question
Then picking (b) makes you an asshole. If all you had written was your first sentence this could have been a pleasant interaction for us both.
Pure defensive (and extremely rude and hostile) projection. (And the response is more of the same, and full of fallacies and false statements). There was no condescension in my comment, just an attempt to be helpful (speaking of "suppression", I will attempt that again with this person). I did not say your question was stupid (it wasn't), I said that you were projecting stupidity on the author of the article (I didn't say you think they are stupid, but apparently this distinction is too subtle for some), and that warrants a rethink.
That your comment was downvoted to death indicates maybe you should reconsider how you are being perceived if you truly believe you weren't (and still aren't) being condescending. I don't believe my comment was any more rude or hostile than your original one.
If people were to follow your advice as a general rule, that's how we get groupthink, and how learning is suppressed by making people afraid to ask questions. See the children's story "the emperor's new clothes" for an example.
It takes effort to be negative to see a comment opening with the poster saying "am I missing something" and think they're calling the author stupid instead of acknowledging their own ignorance.
Now I wonder how Nenad Petrović and Jenő Bán came up with the optimal solutions to the problems in the 60s.
Probably by just thinking about it and working to incrementally improve their answers. I'd expect plenty of people solved it before them but never published or publicized their solution. It's quite logical in many ways. For instance just thinking about the problem abstractly:
- You can only have 9 queens and they're going to want to be as centrally placed as possible with as little overlap as possible.
- The black king will need to be tucked in a corner and covered by a minimum of his pieces and nonchecking pieces of your own.
- All your other pieces, if useable, will probably end up on the edge of the board since minimizing the number of squares they block is likely to be more impactful than maximizing the number of squares they cover.
There's probably other heuristics I'm not considering, but just with those 3 you're already well on your way to the solution. So you'd lay out the pieces, and then try to find a way to do it one move better, and iterate! The concerns I'd have: pawn promotion can complicate things dramatically. Pawns can promote to 4 different pieces which would technically be 4 different moves. And a pawn can have up to 3 different paths to promote - so that's 12 possible moves tucked in a very tiny space. And then king placement - castling can add up to 2 more moves, and so compensating for that (and the corresponding rook position) adds some complexity.
Author here!
Composing such a position is much easier than mathematically proving that there isn't a better one. Perhaps there is an elegant proof. Perhaps they had reasoning that proved that they couldn't do better while composing it. Probably involves plenty of case distinctions. So I decided to just let a computer reason through it, also because human minds are fallible ^^
Glancing at it a chess players first instinct looks to be the "solution".
Assume all pawns are queens, then maximize queen moves, work backwards from there. Couple of other "obvious" assumptions such as minimal black pieces, which means shoving the king in a corner but somehow not in check, Rooks cover the next largest amount of space so they're going in corners, bishops will be mirrored, etc.
Not to say it isn't still impressive, but I always wonder how many "sane" positions there are for solving a puzzle like this in the first place. The paper quotes some huge number and someone else says it's a smaller, but still massive, number, but when you look at the stated goal and start from some obvious starting points, start working out rules (obviously 4 queens right in the middle blocks other queens and costs space), and eliminate symmetrical positions, well you're left with a decently solvable problem. At least compared to the kind of shit that's usually brute force solved.
Edit:
This is actually a fun one to think about for a bit the more I look at it.
It quickly becomes apparent that your basically getting 7 moves out a of a rank/column MAX, so you maximize for that first.
It quickly becomes apparent that the knights L move shape is also the optimal way to start tiling your 9 queens to maximize for squares taken.
As I said before the black position obviously has to be the dead minimum, and it makes sense that'd be a king and 2 pawns due to various end game stuff (basically impossible to prevent the king from being in check otherwise while taking up as much space as possible).
Once you know you're doing that with the black king you'll want to "block" the remaining space with pieces that can't threaten it, so you shove a bishop adjacent (which can still take the pawn), and figure you're going to mirror that bishop because that's kinda how bishop's work in play/mathematically.
It's actually quite neat to see how each step sorta leads you to the next one, like one of those metal puzzles or the sudoku's with unique rules and only 1 or 2 starting numbers.
Still i'm positive if I hadn't seen this picture first I probably NEVER would've gotten this answer correct, but I do think i would've come closer than I ever expected.
Edit 2:
Ahh i do see they have at least one or two solutions that are 218 where there's only 2 black pieces. I'm somewhat surprised that's a possible legal position but so be it. Interesting that still leads to the same net realestate. Thats the one area i'd expect to gain something if you could cheat.
Lots of clarifications re what they mean by "number of moves"; but seems like they could productively have dropped the term "branching factor" in a couple places and thereby cleared the whole thing up.
Meanwhile, for the game of Go, as played on a standard 19x19 board, we have:
The maximum number of possible next moves is 361, which happens only in the initial empty position.
The 361 hardest-to-reach positions (assuming logical rules like [2]) are all the positions with 360 white stones and 1 empty point. these take 2*361 = 722 ply to reach, with black passing all their turns.
And these answers were found without checking all 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935 legal positions :-) [1]
[1] https://tromp.github.io/go/legal.html
[2] https://tromp.github.io/go.html
A game of Go can be legally infinite due to recaptures. (player passes 360 times, then eats the entire board and it starts over).
It's also a natural infinite game due to Kos which can be the best move to play. This requires a set of extra rules to prevent. (Ko, superKo, triple kos, etc)
I assume superko as is standard in several rulesets to prevent infinite play.
Then white plays 1 stone, capturing all the black stones at once, essentially resetting the game with a 360 points lead.
(black goes first, white has Komi, so really a 260+komi points lead)
White cannot play on the last empty point as this would be suicide, which is prevented by the (assumed) superko rule forbidding repetition of the empty position.
Blue is of course the color of math, his primary school is doing it wrong.
I guess the next low hanging fruit would be to prove (or disprove!) the same for chess960
> I inserted this picture for the sole purpose of making this article look less text-heavy.
Taking care of the short attention span readers
How can a position with more than 9 white queens be legal? The limit seems to be one queen plus 8 promoted pawns.
The phrasing "Legal but non-reachable " makes clear that they use some notion of legal that differs from the normal one of reachability. It's hard to imagine what sensible notion that could be though. Something like: each side having only one king, no pawns on first/last row, at most one king in check, etc ?!
There are only 9 queens on the board
The caption of the last diagram is "Legal but non-reachable position with 271 moves for White. Corner queens can be replaced with bishops." There are 24 white queens.
That's the difference between illegal an unreachable. To reach that position you'd need to start from a different point (start both sides with 16 pawns or w/e), but you wouldn't need to break any other chess rules.
If you can start from any arbitrary different point, you can just start from the point you’re intending to reach, and don't need to break any other rules.
As per FIDE rule 3.10.3 "A position is illegal when it cannot have been reached by any series of legal moves". The position isn't legal per FIDE rules.
Beyond there being too many queens… black could not possibly have made the last move. For white to have any moves right now, the last move must have been black moving the king to H8. But G8, G7, H7 are all occupied, so where could the King have moved from?
Legality is a long standing term of art used by chess problem creators. Essentially it means a position withtwo kings on the board, non touching, and not both in check. And no pawns on first or eighth ranks. It has nothing to do with whether the position is reachable from standard chess rules. Along came FIDE in 1999 with its standardized nomenclature but that doesn't invalidate the terminology used by chess problem creators in their own work.
I don't disbelieve you but… where?
I don't think I’ve ever heard it used like that, and in trying to find any example other than the page we’re commenting on, I’ve only found counterexamples.
Whether it’s wikipedia’s 'Glossary of Chess Problems' or OzProblems or 'Sam Loyd and his chess problems' from 1913, they’re all using 'legal' as synonymous with 'reachable'.
I understand this as follows:
Legal: doesn’t break the rules of chess. For example: no pawns on the eighth rank or in check when it’s not their turn.
Reachable: there is a series of moves that lead to this position from the standard starting position.
I'm not sure but I think the original utility and motivation for this mathematical puzzle is how to represent possible legal moves when programming chess, and this would be evidence that an 8bit unsigned integer is sufficient for the worst case scenario, although you would need some complex kind of encoding mechanism to make the representation terse enough to represent the common moves along with 7 promoted queens in the same 256-moves space.
Practically I think I'll stay with a fixed-length encoding for each of the starting pieces and their movements assuming maximum freedom, while adding a variable length variable in case of promotions.
Although nowadays with OOP and classes and superfast CPUs you probably have entirely variable length encodings, you know, an array of piece objects each with their own legal_moves function. But back in the day, when chess engines were written in C, these things were managed globally with all kinds of hack to save space, not due to space reasons, but to improve locality by reducing cache sizes.
For example, even though the chess board is 8x8, a common trick is to make the board 12x12 to account for knight moves that go off the board (and mark them as ilegal of course.) Which goes to show that even with efficiency as the upmost consideration, a terse representation is not ideal, so I doubt we are going to see 8bit variables to represent moves.
Author here,
my motiviation was intellectual curiosity and some random Lichess reading about chess engine authors wondering whether 8 bit e.g. numbers 0 to 255 (or 1 to 256), will be enough for storing the number of legal moves. Which triggered my brain: "I HAVE THE KNOWLEDGE TO SOLVET HIS FOR HUMANITY :O". It's not at all relevant practically, as you have elaborated, and there probably is a more elegant proof that 256 can't be exceeded.
> although you would need some complex kind of encoding mechanism to make the representation terse enough to represent the common moves along with 7 promoted queens in the same 256-moves space.
If you have an algorithm for generating the list of legal moves in a position that always generates them in the same order, you can just use the index at which the move is in the list.
Of course that would come at the cost of speed (you always need to generate that list to know what move was made is meant).
>If you have an algorithm for generating the list of legal moves in a position that always generates them in the same order, you can just use the index at which the move is in the list.
Right, that's exactly what I'm saying, the algorithm that generates the list of legal moves would be an encoder (maps a move into an index), and the reverse would be a decoder (maps the index into a move).
You don't necessarily need to generate the list of legal moves, though. Consider a 16 bit encoding where the first 4 bits represent the piece moved, and the next 5 bits represent the direction, and the next 4 bits represent the distance and so on.
I interpreted this as: "There is no chess position which is only reachable in more than 218 consecutive moves"
Great article! Thanks for sharing
Thanks for appreciating my article ^__^
This is pretty cool. Would have been neat to see some descriptive text about encoding to integer programming problem.
Author here,
I considered but decided against the complexity, haha.
I added a Github link towards the bottom of the article though. Code might not be pretty though .__.
Haha yeah, I saw the code and it is pretty comprehensible but some things are curious. I thought some of the naming was amusing "ENABLE_ROYAL_CUDDLING" etc.
Thanks for the writeup.
Oh no, I forgot to rename that variable before publishing, haha
[dead]
Isn't the very first move of any chess game a reachable chess position with more than 218 moves?
Maybe one of us is misunderstanding, but aren't there far fewer than 218 on the first move? The position in the article needed nine unobstructed queens to achieve 218 possible moves. For the first move, I think we could just enumerate the moves by hand, right? Eight pawns can move one or two spaces, that's 16 moves. The two knights have two moves, that's 4. Nothing else can move, can it? That's only 20 moves.
EDIT: I think I understand the confusion. A "move" in this case is a legal possibility for white's next turn. It's not talking about the number of moves in the game, but rather the number of legal choices for white in a single turn.
Author here!
You are correct! It's White to move and White has 218 moves to choose from as their next move. My article proves that you can't do better than 218.
The initial board position is certainly reachable (and reached in every game!), but there are only 20 legal moves available: the 16 legal pawn moves for White, and the 4 legal knight moves for White.
Indeed. And 20 < 218.
So your agree with the article so far.
When you use small context LLM, you get completion like this.
It’s not 218 possibilities it’s 218 moves.
No, there are only 20 moves in the initial position.