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.
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).
"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
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!
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.
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.
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.
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'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
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.
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)
Readit News
This is not so interesting then…
> In 1964 Petrović constructed a position with 218 possible moves for White.
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.
Why does black have two pawns but no king?
I don’t understand any of this
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.)
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
> 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?
Yes, if you do a naive programme only, it would be a massive search space.
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!
"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.
(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.
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
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)
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.
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 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 ^^
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)