121–130 of 195 posts
They dont really spell it out but they mean "from this position the player has 218 possible legal moves to choose from"
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.
Earlier quoted context omitted.
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 think that was an intermediate model. The author updated it, then Gurobi solved the new model to optimality (i.e., the bound became equal to the value of the best solution found). > 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...
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.
[flagged]
Here's a general rule of thumb: If the options are
a) answer someone's question, and
b) answer someone's question but also then spend triple the word count telling them it was a stupid question
Then picking (b) makes you an asshole. If all you had written was your first sentence this could have been a pleasant interaction for us both.
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.
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.
What is the least number of bits that can describe any reachable chess board? 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.
Earlier quoted context omitted.
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.
That's a fine upper bound, but it doesn't minimize but usage since it also can represent illegal 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 aski…
Earlier quoted context omitted.
I thought “there is no chess problem that is both reachable from starting position and requires more than 218 moves to solve”
There are no more than 218 ways to interpret this title
Earlier quoted context omitted.
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.
Is that weird? I feel like it’s plausible though. Very rare to have chess games with more than 200 moves.