No reachable chess position with more than 218 moves
1–10 of 195 posts
Re: No reachable chess position with more than 218 moves
#2https://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
#3https://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…
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
#4Isn't the very first move of any chess game a reachable chess position with more than 218 moves?
Re: No reachable chess position with more than 218 moves
#5Isn't the very first move of any chess game a reachable chess position with more than 218 moves?
It’s not 218 possibilities it’s 218 moves.
Re: No reachable chess position with more than 218 moves
#6Isn't the very first move of any chess game a reachable chess position with more than 218 moves?
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.
Re: No reachable chess position with more than 218 moves
#7Isn't the very first move of any chess game a reachable chess position with more than 218 moves?
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.
Re: No reachable chess position with more than 218 moves
#8Isn't the very first move of any chess game a reachable chess position with more than 218 moves?
[deleted]
Re: No reachable chess position with more than 218 moves
#9Now I wonder how Nenad Petrović and Jenő Bán came up with the optimal solutions to the problems in the 60s.
Re: No reachable chess position with more than 218 moves
#10They dont really spell it out but they mean "from this position the player has 218 possible legal moves to choose from"