4 ms·
https://lichess.org/@/Tobs40/blog/there-is-no-reachable-chess-position-with-more-than-218-moves/a5xdxeqs#checking-more-positions-to-make-things-less-slow https:
by eru 1y ago
https://lichess.org/@/Tobs40/blog/there-is-no-reachable-chess-position-with-more-than-218-moves/a5xdxeqs#checking-more-positions-to-make-things-less-slow 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 https://en.wikipedia.org/wiki/Column_generation but nothing on row generation.)
- LeGrosDadai 1y agoI'm quite curious to see if the MILP solver would terminate (given the massive search space), my guess is not.
- eru 1y agoWell, 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.
- salt4034 1y agoThe most commonly used term for this is lazy constraints (https://support.gurobi.com/hc/en-us/articles/360013197972-How-do-I-implement-lazy-constraints-in-Gurobi https://support.gurobi.com/hc/en-us/articles/360013197972-Ho...).
- Tobs40 1y agoHi, 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
- eru 1y agoThanks! > 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?