There is no reachable chess position with more than 218 moves.

@everythin4daLOLZ said in #59:

You could also reduce your search space by always making sure that queens are on spots reachable by knights (since otherwise, they would overlap greatly) and I have a suspicion for knights they must also follow a similar line of thought. I think that should give it a speed boost, if you would like to try it again.

I did have that idea but my gut feeling was, that this is something which Gurobi would figure out on its own. That it gives you a small speedup at best while being some effort to prove and implement correctly.

You've got the right intuition, I suggest that you study Computer Science and prove/crack some chess records ^^

@Tobs40 said in #60:

Regarding the LP relaxation: I don't turn it into anything! In fact, I don't even create it.

I model the problem with variables that are either 1 or 0, a linear objective (e.g. 3x+4y-2z) to maximize, and a lot of linear constraints (2x-7y+8z ≤ -3). I omit some difficult constraints for speed. This leads to some illegal solutions, but I just filter them out later.

This is a so-called integer linear program. Integer variables, linear constraints and objectives. Very hard to solve. I pass it to Gurobi, a commercial solver, and it uses a branch-and-bound algorithm. Which means that it branches on an integer variable, creating two new subproblems, then repeats recursively, ... until it can stop. For this, it uses the LP relaxation, which is the same as the original problem, but with the integer variables (either 0 or 1) being relaxed to 0 to 1. This extends the solution space by looots of fractional solutions, lots of them far better than the actual solution - but it is astronomically faster to solve. And it gives an upper bound since if a solution is the best of an LP, it's also the best of the corresponding ILP.
Thank you! So if I understand correctly, you don't compute the LP relaxation yourself, this is just how Gurobi works internally, and you did compute the actual ILP (not LP) exactly?

Good Fantastic

@strawberry_queen said in #62:

Thank you! So if I understand correctly, you don't compute the LP relaxation yourself, this is just how Gurobi works internally, and you did compute the actual ILP (not LP) exactly?

Yep, I specify the ILP (Integer Linear Program) using the Gurobi Python library and call Gurobi to solve it. The magic is in formulating the model so it finishes before the universe.

@Tobs40 said in #61:

I did have that idea but my gut feeling was, that this is something which Gurobi would figure out on its own. That it gives you a small speedup at best while being some effort to prove and implement correctly.

You've got the right intuition, I suggest that you study Computer Science and prove/crack some chess records ^^

Thanks! I am currently really getting into algorithms and coding, and it seems super fun! (I am mainly using C++, but had some fun playing and trying to dissect the transformers on HuggingFace using Python!) It's super cool what you are doing, and honestly I hope I can do something similar one day!

Very interesting, thanks for your work!

The upper limit you gave for the maximum number of moves while in check (120) seems much higher than the real number. I quickly found a position with 39 moves, and I wonder, is it possible to do more?

@Yosha87 said in #66:

Very interesting, thanks for your work!

The upper limit you gave for the maximum number of moves while in check (120) seems much higher than the real number. I quickly found a position with 39 moves, and I wonder, is it possible to do more?

Sure, it's quite possible that my upper bound on the number of moves while being in check is far from the true maximum. I wasn't trying to get a good bound here, I just needed to quickly prove with 100% certainty that removing all positions where the white king is in check does not exclude positions with 218 or more moves.

Maybe this one can be proven by hand even. In any case, I'm gonna add it to my list of things to prove next. Although I might not get to it for some months to even a few years, sadly.

Someone please grab my code and solve this, this should be an easy one! :D

@Tobs40 really awesome and well-written post!
From the FAQ:

If Gurobi, your code and your thinking do not have a bug
I wrote my own script from scratch to try reproducing your results independently. It took about half an hour to prove to optimality - I ended up with the same conclusion!

@Yosha87 I found solutions with 40 moves each.
If I did not make a mistake (and I probably did - I hacked it into my code), it doesn't get better than that:

(I know I'm a bit late to the party)

@Toberon said in #68:

@Tobs40 really awesome and well-written post!
From the FAQ:

I wrote my own script from scratch to try reproducing your results independently. It took about half an hour to prove to optimality - I ended up with the same conclusion!

@Yosha87 I found solutions with 40 moves each.
If I did not make a mistake (and I probably did - I hacked it into my code), it doesn't get better than that:

lichess.org/analysis/r6K/QPPPPP2/nNNNNNRB/8/7k/8/8/8_w_--0_1?color=white
lichess.org/analysis/6K1/8/5B1Q/4NB1Q/3kNQ1Q/4NQ1Q/5Q1Q/5RrR_w--_0_1?color=white

(I know I'm a bit late to the party)

Hey ^__^

many thanks for reproducing and confirming my main result!
May you find lots of records using this technique, haha.

And what a coincidende that your Lichess name starts with "Tob" too - is your first name Tobi as well? xD

Best regards,
Tobi

amazing - u conbined chess and maths