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 it was "How many moves in a game does it take to reach this position"

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

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!

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.

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

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.

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.

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.

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

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

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.

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.

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.

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.

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)

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)

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.

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)

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.

Black pawns start on the 7th rank, not the 2nd rank.

Here's a general rule of thumb: If the options are

a) you're not missing something and the article in question is absurdly wrong and stupid but no one else is saying so, and

b) you're missing something

Assume (b) and put all your effort into figuring out what.

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

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.

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

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

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.