Haha yeah, I saw the code and it is pretty comprehensible but some things are curious. I thought some of the naming was amusing "ENABLE_ROYAL_CUDDLING" etc.
Thanks for the writeup.
Oh no, I forgot to rename that variable before publishing, haha
Readit NewsTobs40 commented on No reachable chess position with more than 218 moves lichess.org/@/Tobs40/blog... · Posted by u/emporas
Tobs40 commented on No reachable chess position with more than 218 moves lichess.org/@/Tobs40/blog... · Posted by u/emporas
This part is unclear; what exactly did you change? Are you saying that the LP relaxation has value 271.666, but, when you enforce integrality, Gurobi can actually find and prove optimality of a solution with value 218?
Were you really just solving LPs up to this point in the article? How can these intermediate LPs be so slow to solve (6+ years) and yet Gurobi is able to solve the integer-restricted problem?
Ah, I see the misunderstanding.
I've always been solving the integer problem of course. But throughout the article, I improve the model formulation again and again through insights, which makes the LP relaxation tighter. Initially, it gave 305.0 as upper bound, but after tightening the model (addind constraints that cut off that 305 solution and others) it gives 271.666...
- which leads to insanely faster search. It's like brute-forcing through all passwords of length 20 and a wizard telling you that you're wrong when you reach character 7 instead of 13.
Tobs40 commented on No reachable chess position with more than 218 moves lichess.org/@/Tobs40/blog... · Posted by u/emporas
so just to be clear: for every board position there are no more than 218 moves available? is that the understanding?
It's your turn and you have 218 moves to choose from. This is the best possible and the article proves this (assuming no bugs in machine or mind).
Tobs40 commented on No reachable chess position with more than 218 moves lichess.org/@/Tobs40/blog... · Posted by u/emporas
I'm not sure but I think the original utility and motivation for this mathematical puzzle is how to represent possible legal moves when programming chess, and this would be evidence that an 8bit unsigned integer is sufficient for the worst case scenario, 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.
Practically I think I'll stay with a fixed-length encoding for each of the starting pieces and their movements assuming maximum freedom, while adding a variable length variable in case of promotions.
Although nowadays with OOP and classes and superfast CPUs you probably have entirely variable length encodings, you know, an array of piece objects each with their own legal_moves function. But back in the day, when chess engines were written in C, these things were managed globally with all kinds of hack to save space, not due to space reasons, but to improve locality by reducing cache sizes.
For example, even though the chess board is 8x8, a common trick is to make the board 12x12 to account for knight moves that go off the board (and mark them as ilegal of course.) Which goes to show that even with efficiency as the upmost consideration, a terse representation is not ideal, so I doubt we are going to see 8bit variables to represent moves.
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.
Tobs40 commented on No reachable chess position with more than 218 moves lichess.org/@/Tobs40/blog... · Posted by u/emporas
This is pretty cool. Would have been neat to see some descriptive text about encoding to integer programming problem.
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 .__.
Tobs40 commented on No reachable chess position with more than 218 moves lichess.org/@/Tobs40/blog... · Posted by u/emporas
Great article! Thanks for sharing
Thanks for appreciating my article ^__^
Tobs40 commented on No reachable chess position with more than 218 moves lichess.org/@/Tobs40/blog... · Posted by u/emporas
Now I wonder how Nenad Petrović and Jenő Bán came up with the optimal solutions to the problems in the 60s.
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 ^^
Tobs40 commented on No reachable chess position with more than 218 moves lichess.org/@/Tobs40/blog... · Posted by u/emporas
I'm confused, what did he change after the 271-move model to get it to produce the optimal solutions? It just says "With this improved model"...
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!
Tobs40 commented on No reachable chess position with more than 218 moves lichess.org/@/Tobs40/blog... · Posted by u/emporas
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.
Author here.
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 ^^
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.
You are correct! It's White to move and White has 218 moves to choose from as their next move. My article proves that you can't do better than 218.