Live data from Hacker News

No reachable chess position with more than 218 moves

lichess.org

21–30 of 195 posts

Re: No reachable chess position with more than 218 moves

#21

Now I wonder how Nenad Petrović and Jenő Bán came up with the optimal solutions to the problems in the 60s.

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.

Re: No reachable chess position with more than 218 moves

#22
post #2

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…

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

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.

Re: No reachable chess position with more than 218 moves

#23
Am 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.

Re: No reachable chess position with more than 218 moves

#24

Now I wonder how Nenad Petrović and Jenő Bán came up with the optimal solutions to the problems in the 60s.

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.

Re: No reachable chess position with more than 218 moves

#25

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

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

Re: No reachable chess position with more than 218 moves

#26

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

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.

Re: No reachable chess position with more than 218 moves

#29

They dont really spell it out but they mean "from this position the player has 218 possible legal moves to choose from"

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

Re: No reachable chess position with more than 218 moves

#30
post #29

They dont really spell it out but they mean "from this position the player has 218 possible legal moves to choose from"

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

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.
Post reply on HN