News for hackers. Stuff that matters.
Re:No reachable chess position with more than 218 moves by eru on Friday September 26, 2025 @02:23AM (#45383343)
https://lichess.org/@/Tobs40/blog/there-is-no-reachable-ches... describes how the author removed some more complicated rules in the first pass, and is willing to re-introduce them, if necessary. Ie if the solution found violates them.

Interestingly, mixed integer linear programming solvers already support these. The technical term for this is 'row generation'. It comes from the usually way these problems are written in matrix form, where rows correspond to constraints and columns correspond to variables.

(Dynamically) adding a row is equivalent to introducing a constraint only if it's violated.

This approach is often used for the traveling salesman problem.

(Weirdly enough, Wikipedia has https://en.wikipedia.org/wiki/Column_generation but nothing on row generation.)

Re:No reachable chess position with more than 218 moves by LeGrosDadai on Friday September 26, 2025 @02:30AM (#45383389)
I'm quite curious to see if the MILP solver would terminate (given the massive search space), my guess is not.
Re:No reachable chess position with more than 218 moves by eru on Friday September 26, 2025 @04:32AM (#45384186)
Well, my point is that you can encode the tricks described in the linked article directly in a modern MILP solver in a way that is legible to the solver. We'd expect similar behaviour in that case, or perhaps slightly better, because the solver can 'see' them better.

Yes, if you do a naive programme only, it would be a massive search space.

Re:No reachable chess position with more than 218 moves by salt4034 on Friday September 26, 2025 @10:01AM (#45386623)
The most commonly used term for this is lazy constraints (https://support.gurobi.com/hc/en-us/articles/360013197972-Ho...).
Re:No reachable chess position with more than 218 moves by Tobs40 on Friday September 26, 2025 @01:40PM (#45389056)
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

Re:No reachable chess position with more than 218 moves by eru on Saturday September 27, 2025 @04:40AM (#45394137)
Thanks!

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