No Reachable Chess Position with More Than 218 Moves

I'm quite curious to see if the MILP solver would terminate (given the massive search space), my guess is not.

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

The most commonly used term for this is lazy constraints (https://support.gurobi.com/hc/en-us/articles/360013197972-Ho...).

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.

It’s not 218 possibilities it’s 218 moves.

No, there are only 20 moves in the initial position.

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 ^^

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.

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.

I thought it was "How many moves in a game does it take to reach this position"

Thanks, I misunderstood the entire article. Great writing!

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).

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

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.

If only they had appended "to choose from" to the article headline, it would have been clear from the start.

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.

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.

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.

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.

the word "possible" is missing

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.

Ah, thank you. I was confused reading this article, thinking it's about the unique position that takes the most moves to reach.

Yeah I gave up when I realized I didn’t understand what problem he was trying to solve

I had the same confusion, until they showed the existing 218 position and realized it was about maximizing white's legal moves.

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.

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 .__.

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.

Isn't that estimate just 20x bigger? Which is not a big difference considering the magnitude.

> 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).

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.

The black pawns are on white's side of the board.

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.

There are only 9 queens on the board

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 ?!

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.

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 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.

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.

Thanks for appreciating my article ^__^

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!

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.

In theory, it's not proof. In practice, it is.

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.

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.

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)

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.