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 not sure but I think the original utility and motivation for this mathematical puzzle is how to represent possible legal moves when programming chess, and this would be evidence that an 8bit unsigned integer is sufficient for the worst case scenario, although you would need some complex kind of encoding mechanism to make the representation terse enough to represent the common moves along with 7 promoted queens in the same 256-moves space.
Practically I think I'll stay with a fixed-length encoding for each of the starting pieces and their movements assuming maximum freedom, while adding a variable length variable in case of promotions.
Although nowadays with OOP and classes and superfast CPUs you probably have entirely variable length encodings, you know, an array of piece objects each with their own legal_moves function. But back in the day, when chess engines were written in C, these things were managed globally with all kinds of hack to save space, not due to space reasons, but to improve locality by reducing cache sizes.
For example, even though the chess board is 8x8, a common trick is to make the board 12x12 to account for knight moves that go off the board (and mark them as ilegal of course.) Which goes to show that even with efficiency as the upmost consideration, a terse representation is not ideal, so I doubt we are going to see 8bit variables to represent moves.
Am I missing something, or is the configuration shown initially not actually reachable? It's white to move, yet the black pawns are in their starting location and the black king has no adjacent empty square, it's entombed by its pawns and the white bishop so the configuration could not have been reached.
Genuinely interested in being educated here: If Gurobi's integer programming solver didn't find a solution better than 218, is that a guarantee that there exists no solution better than 218? Is it equivalent to a mathematical proof?
(Let's assume, for the sake of argument, that there's no bugs in Gurobi's solver and no bugs in the author's implementation of the problem for Gurobi to solve.)
I guess I'm basically asking whether it's possible that Gurobi got trapped in a local maximum, or whether this can be considered a definitive universal solution.
The black pawn on b2 is eating a lot of possible moves for the other pieces…
It has only one legal move, take the Knight on c1. If that pawn wasn't there it would free that square for 4 white queens and a Knight. But of course the black king would already be in checkmate so these moves wouldn't really be available.
Tempting to put that e5 Queen elsewhere so that it doesn't immediately checkmate and leave the b2 square available for others.
edit: I imagine that pawn also needs to survive that far in order to avoid a stalemate.
Just want to give Lichess a shoutout here. They are fantastic, provide great content, have things for free that you need to pay for on Chess.com, and a fantastic amount of variants.
Even better, the level of play in those variants, like 960 or Crazyhouse, is MUCH higher on Lichess than on Chess.com.
Meanwhile, for the game of Go, as played on a standard 19x19 board, we have:
The maximum number of possible next moves is 361, which happens only in the initial empty position.
The 361 hardest-to-reach positions (assuming logical rules like [2]) are all the positions with 360 white stones and 1 empty point. these take 2*361 = 722 ply to reach, with black passing all their turns.
And these answers were found without checking all 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935 legal positions :-) [1]
a friend of mine pointed out that my article is being discussed in this forum.
I am sorry for choosing a suboptimal title and I hope that it is unambiguous now. I am grateful for your feedback and kind words!
If you have any questions, also in regard to proving similar chess facts, I'd be happy to help ^^
Lots of clarifications re what they mean by "number of moves"; but seems like they could productively have dropped the term "branching factor" in a couple places and thereby cleared the whole thing up.
I found a position that takes 78,352 moves and can't find a shorter combo. Both white bishops end up on dark squares. You have to castle at just the right moment. There is a race condition with a window far too narrow to be noticeable in any normal play, but a timing analysis uncovered it. There may be more.
24 comments
[ 5.1 ms ] story [ 45.3 ms ] threadInterestingly, 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.)
"no more than 218 possible next moves" would be a lot clearer...
> By checking all approximately 8.7x10^45 reachable chess positions?
That's a large overestimate.
https://github.com/tromp/ChessPositionRanking accurately estimates the number of legal chess positions at ~4.8x10^44.
Practically I think I'll stay with a fixed-length encoding for each of the starting pieces and their movements assuming maximum freedom, while adding a variable length variable in case of promotions.
Although nowadays with OOP and classes and superfast CPUs you probably have entirely variable length encodings, you know, an array of piece objects each with their own legal_moves function. But back in the day, when chess engines were written in C, these things were managed globally with all kinds of hack to save space, not due to space reasons, but to improve locality by reducing cache sizes.
For example, even though the chess board is 8x8, a common trick is to make the board 12x12 to account for knight moves that go off the board (and mark them as ilegal of course.) Which goes to show that even with efficiency as the upmost consideration, a terse representation is not ideal, so I doubt we are going to see 8bit variables to represent moves.
update: article says there are approximately 8.7x10^45 reachable chess positions and https://github.com/lechmazur/ChessCounter says this is an upper bound.
(this would correspond to about 153 bits)
(Let's assume, for the sake of argument, that there's no bugs in Gurobi's solver and no bugs in the author's implementation of the problem for Gurobi to solve.)
I guess I'm basically asking whether it's possible that Gurobi got trapped in a local maximum, or whether this can be considered a definitive universal solution.
It has only one legal move, take the Knight on c1. If that pawn wasn't there it would free that square for 4 white queens and a Knight. But of course the black king would already be in checkmate so these moves wouldn't really be available.
Tempting to put that e5 Queen elsewhere so that it doesn't immediately checkmate and leave the b2 square available for others.
edit: I imagine that pawn also needs to survive that far in order to avoid a stalemate.
Even better, the level of play in those variants, like 960 or Crazyhouse, is MUCH higher on Lichess than on Chess.com.
The maximum number of possible next moves is 361, which happens only in the initial empty position.
The 361 hardest-to-reach positions (assuming logical rules like [2]) are all the positions with 360 white stones and 1 empty point. these take 2*361 = 722 ply to reach, with black passing all their turns.
And these answers were found without checking all 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935 legal positions :-) [1]
[1] https://tromp.github.io/go/legal.html
[2] https://tromp.github.io/go.html
Taking care of the short attention span readers
a friend of mine pointed out that my article is being discussed in this forum. I am sorry for choosing a suboptimal title and I hope that it is unambiguous now. I am grateful for your feedback and kind words!
If you have any questions, also in regard to proving similar chess facts, I'd be happy to help ^^
Best regards, Tobi