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.
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.
So your agree with the article so far.
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.
- 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 ^^
> In 1964 Petrović constructed a position with 218 possible moves for White.
[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."
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.
Compare this to, say, the L game, where the number of moves is unbounded.
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.
However there is a 75 move rule and a 5 time repetition rule that are both automatic (don't need to be claimed).
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.
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).
This is not high enough, because the 50 move rule also resets when a piece is captured.
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.
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.
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)
Sure, but the article is written in English. :-)
Why does black have two pawns but no king?
I don’t understand any of this
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!
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.
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
Thanks for note re: upper bound with 75 moves without pawn advancing constraint.
This is not so interesting then…
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 .__.
Thanks for the writeup.
"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.
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.
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).
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.
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.
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.
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?
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'.
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.
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)
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.
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.
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!
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.
(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.
> With this improved model, I tried again and after ~23 000 seconds, Gurobi solved it to optimality!
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...
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.
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.
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)
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 ^^
Even better, the level of play in those variants, like 960 or Crazyhouse, is MUCH higher on Lichess than on Chess.com.
It's almost ridiculously good. Donate if you can!
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]
(black goes first, white has Komi, so really a 260+komi points lead)
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)
Taking care of the short attention span readers
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
eru•4mo ago
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.)
LeGrosDadai•4mo ago
eru•4mo ago
Yes, if you do a naive programme only, it would be a massive search space.
salt4034•4mo ago
Tobs40•4mo ago
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•4mo ago
> 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?