7 ms·
No reachable chess position with more than 218 moves
- eru 1y agohttps://lichess.org/@/Tobs40/blog/there-is-no-reachable-chess-position-with-more-than-218-moves/a5xdxeqs#checking-more-positions-to-make-things-less-slow 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 https://en.wikipedia.org/wiki/Column_generation but nothing on row generation.)
- LeGrosDadai 1y agoI'm quite curious to see if the MILP solver would terminate (given the massive search space), my guess is not.
- eru 1y agoWell, 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.
- salt4034 1y agoThe most commonly used term for this is lazy constraints (https://support.gurobi.com/hc/en-us/articles/360013197972-How-do-I-implement-lazy-constraints-in-Gurobi https://support.gurobi.com/hc/en-us/articles/360013197972-Ho...).
- Tobs40 1y agoHi, 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
- eru 1y agoThanks! > 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?
- reader9274 1y agoIsn't the very first move of any chess game a reachable chess position with more than 218 moves?
- reed1234 1y agoIt’s not 218 possibilities it’s 218 moves.
- electroly 1y agoMaybe 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.
- Tobs40 1y agoAuthor 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.
- clintonc 1y agoThe 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.
- ted_dunning 1y agoIndeed. And 20 < 218. So your agree with the article so far.
- 1y ago
- kryptiskt 1y agoNow I wonder how Nenad Petrović and Jenő Bán came up with the optimal solutions to the problems in the 60s.
- Eji1700 1y agoGlancing 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.
- codeulike 1y agoThey dont really spell it out but they mean "from this position the player has 218 possible legal moves to choose from"
- WithinReason 1y agoThanks, I misunderstood the entire article. Great writing!
- sverhagen 1y agoHow can those two things be true at the same time? Unless you appreciate misunderstanding what you read...?
- burnished 1y agoWhat other reason would a person have for juxtaposing two statements?
- Sharlin 1y agoHow could someone ever write something while intending to convey the exact opposite meaning?
- absoflutely 1y agoYou hit the nail on the head. They aren't both true which is why the second sentence is sarcasm.
- wodenokoto 1y agoI thought it was "How many moves in a game does it take to reach this position"
- coolness 1y agoI also thought this but OP is right: https://dev.timenote.info/de/Nenad-Petrovic https://dev.timenote.info/de/Nenad-Petrovic > In 1964 Petrović constructed a position with 218 possible moves for White.
- renewiltord 1y agoThis is pretty cool. Would have been neat to see some descriptive text about encoding to integer programming problem.
- Tobs40 1y agoAuthor 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 .__.
- renewiltord 1y agoHaha 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.
- Tobs40 1y agoOh no, I forgot to rename that variable before publishing, haha
- tromp 1y ago> 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 https://github.com/tromp/ChessPositionRanking accurately estimates the number of legal chess positions at ~4.8x10^44.
- XCSme 1y agoIsn't that estimate just 20x bigger? Which is not a big difference considering the magnitude.
- nhumrich 1y agoOne 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.
- TZubiri 1y agoI'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.
- Scarblac 1y ago> 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).
- TZubiri 1y ago>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.
- margalabargala 1y agoAm 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.
- KK7NIL 1y agoThe black pawns are on white's side of the board.
- margalabargala 1y agoThat's what I missed. Thank you :-)
- Eji1700 1y agoProof is provided here for one of them: https://lichess.org/study/PLtuv3v5/zWPNxbSA 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.
- margalabargala 1y agoYep that's what I was missing. Thank you for the link.
- jibal 1y ago[flagged]
- margalabargala 1y agoThanks 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.
- pmontra 1y agoHow can a position with more than 9 white queens be legal? The limit seems to be one queen plus 8 promoted pawns.
- codeulike 1y agoThere are only 9 queens on the board
- pmontra 1y agoThe 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.
- contravariant 1y agoThat'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.
- systoll 1y agoIf 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?
- zuminator 1y agoLegality 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.
- amelius 1y agoWhat 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 https://github.com/lechmazur/ChessCounter says this is an upper bound. (this would correspond to about 153 bits)
- cabirum 1y agoPiece 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.
- mcherm 1y agoThat's a fine upper bound, but it doesn't minimize but usage since it also can represent illegal positions.
- jfengel 1y agoThe 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.
- mormegil 1y agoWhile 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 :-)
- tromp 1y agoThat'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.
- huflungdung 1y ago[dead]
- p_zuckerman 1y agoGreat article! Thanks for sharing
- Tobs40 1y agoThanks for appreciating my article ^__^
- a3w 1y agoBlue is of course the color of math, his primary school is doing it wrong.
- dooglius 1y agoI'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"...
- Tobs40 1y agoAuthor 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!
- dooglius 1y agoI 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.
- salt4034 1y agoThis 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?
- Tobs40 1y agoAh, 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.
- dbatten 1y agoGenuinely 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.
- salt4034 1y agoIn 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.
- dbatten 1y agoUnless 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...
- salt4034 1y agoI 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!
- dbatten 1y ago> 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...
- jobigoud 1y agoThe 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.
- tromp 1y agoThe 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.
- Scarblac 1y agoIt'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)
- NooneAtAll3 1y agoI 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"
- Tobs40 1y agoAuthor 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 ^^
- NickC25 1y agoJust 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.
- tromp 1y agoMeanwhile, 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 https://tromp.github.io/go/legal.html [2] https://tromp.github.io/go.html https://tromp.github.io/go.html
- mtremsal 1y agoThen 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)
- tromp 1y agoWhite 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.
- GabrielBen 1y agoA 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)
- tromp 1y agoI assume superko as is standard in several rulesets to prevent infinite play.
- isagues 1y ago> I inserted this picture for the sole purpose of making this article look less text-heavy. Taking care of the short attention span readers
- Tobs40 1y agoHi 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
- cubefox 1y agoI interpreted this as: "There is no chess position which is only reachable in more than 218 consecutive moves"
- quuxplusone 1y agoLots 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.
- Nevermark 1y agoI 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.
- xoroshiro 1y agoI guess the next low hanging fruit would be to prove (or disprove!) the same for chess960