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.
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.
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 ^^
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!
I did read the entire article yeah, and I was rounding down with "271", but it wasn't clear to me what change you made that got you to the finish line. Are you saying that the next improvement was to force Gurobi to use integer values? It's surprising to me that wouldn't kill performance since ILP is NP-hard whereas real LP can be solved in polynomial time.
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?
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.
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 ^^
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.
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.
> relaxing and omitting chess rules also changed the choice of variables.
I wonder if you can recast some of that in terms of (dynamic) row generation?
> I did try lazy constraints etc. before diving into the math, but they did not yield a significant speedup.
Yes, I can believe that. My point wasn't so much that using heuristics like these is somehow bad, but more that the off-the-shelf solvers can be made to cooperate with (many of) your heuristics.
> For example, not considering the white king as being in check simplified A LOT.
I guess you could classify that as branch-and-bound, if you squinted really hard?
a friend of mine pointed out that my article is being discussed in this forum.
I am sorry for choosing a suboptimal title and I hope that it is unambiguous now. I am grateful for your feedback and kind words!
If you have any questions, also in regard to proving similar chess facts, I'd be happy to help ^^
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.