Tobs40

Author here!

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.

Oh no, I forgot to rename that variable before publishing, haha

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.

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

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.

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

Thanks for appreciating my article ^__^

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

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!

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

Author here!

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.

Hi, author of the Lichess article here.

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.

Best regards, Tobi

Hi all,

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

Best regards, Tobi