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.
I'm quite curious to see if the MILP solver would terminate (given the massive search space), my guess is not.
reader9274•18m ago
Isn't the very first move of any chess game a reachable chess position with more than 218 moves?
reed1234•13m ago
It’s not 218 possibilities it’s 218 moves.
electroly•12m ago
Maybe one of us is misunderstanding, but aren't there far fewer than 218 on the first move? The position in the article needed nine unobstructed queens to achieve 218 possible moves. For the first move, I think we could just enumerate the moves by hand, right? Eight pawns can move one or two spaces, that's 16 moves. The two knights have two moves, that's 4. Nothing else can move, can it? That's only 20 moves.
EDIT: I think I understand the confusion. A "move" in this case is a legal possibility for white's next turn. It's not talking about the number of moves in the game, but rather the number of legal choices for white in a single turn.
clintonc•11m ago
The initial board position is certainly reachable (and reached in every game!), but there are only 20 legal moves available: the 16 legal pawn moves for White, and the 4 legal knight moves for White.
kryptiskt•1m ago
Now I wonder how Nenad Petrović and Jenő Bán came up with the optimal solutions to the problems in the 60s.
eru•25m ago
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.)
LeGrosDadai•18m ago