Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

No reachable chess position with more than 218 moves

lichess.org

Post reply on HN
Print view View original

111–120 of 195 posts

Re: No reachable chess position with more than 218 moves

#111

Post by Scarblac »

jibal wrote: post #66
kevindamm wrote: post #62

Earlier quoted context omitted.

Not explicitly, but when you consider the "cannot repeat the same board layout three times" rule, the number of moves possible in a game does have a limit.

The 3 repetition draw rule has no bearing on the number of possible chess positions. And for the number of possible moves in a game the 50 moves with no capture or pawn move rule is a much more stringent limit. BTW, the 3 repetition rule only comes into play is one of the players invokes it ... games can legally have more than 3 repetitions, but not more than 5 repetitions.

The 50 moves rule also needs to be claimed by one of the players.

However there is a 75 move rule and a 5 time repetition rule that are both automatic (don't need to be claimed).

Re: No reachable chess position with more than 218 moves

#112

Post by [deleted] »

dbatten wrote: post #104
salt4034 wrote: post #100

Earlier quoted context omitted.

In addition to the value of the best integer solution found so far, Gurobi also provides a bound on the value of the best possible solution, computed using the linear relaxation of the problem, cutting planes and other techniques. So, assuming there are no bugs in the solver, this is truly the optimal solution.

Unless I missed something, though, the highest bound the author reported for the relaxation was 271 2/3 moves, which is obviously significantly higher than 218...

[deleted]

Re: No reachable chess position with more than 218 moves

#113

Post by sigbottle »

nhumrich wrote: post #107
dbatten wrote: post #80

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 aski…

In theory, it's not proof. In practice, it is.

Well, if the solver isn't wrong and there were no bugs in impl, yes, the approach is rigorous. Allow strictly more "powerful" configurations yet still prove that the maximum is X, then achieve X through a construction, is standard math

Re: No reachable chess position with more than 218 moves

#114

Post by Scarblac »

jobigoud wrote: post #86

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 squar…

It's white to move. If black is in check with white to move, that makes the position illegal, and unreachable -- there's no possible legal move by black that led to this position where he is in check.

Replacing one of the black pawns by a white knight would add some moves, but there is no budget for that -- both knights are already on the board, and all pawns were promoted to queens. (And replacing both pawns would again make it impossible for black to have made the previous move)

Re: No reachable chess position with more than 218 moves

#115

Post by [deleted] »

kelipso wrote: post #84
stavros wrote: post #59

Earlier quoted context omitted.

Ah, wow, I read the article wrong all this time, thank you. I thought they meant "the maximum number of moves you can make to reach any chess position is 218", and I was wondering why the article made no sense to me.

Is that weird? I feel like it’s plausible though. Very rare to have chess games with more than 200 moves.

[deleted]

Re: No reachable chess position with more than 218 moves

#116

Post by Scarblac »

TZubiri wrote: post #19

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…

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

If you have an algorithm for generating the list of legal moves in a position that always generates them in the same order, you can just use the index at which the move is in the list.

Of course that would come at the cost of speed (you always need to generate that list to know what move was made is meant).

Re: No reachable chess position with more than 218 moves

#118

Post by zuminator »

systoll wrote: post #82
contravariant wrote: post #49

Earlier quoted context omitted.

That's the difference between illegal an unreachable. To reach that position you'd need to start from a different point (start both sides with 16 pawns or w/e), but you wouldn't need to break any other chess rules.

If you can start from any arbitrary different point, you can just start from the point you’re intending to reach, and don't need to break any other rules. As per FIDE rule 3.10.3 "A position is illegal when it cannot have been reached by any series of legal moves". The position isn't legal per FIDE rules. Beyond there being too many queens… black could not possibly have made the last move. For white to have any moves…

Legality is a long standing term of art used by chess problem creators. Essentially it means a position withtwo kings on the board, non touching, and not both in check. And no pawns on first or eighth ranks. It has nothing to do with whether the position is reachable from standard chess rules. Along came FIDE in 1999 with its standardized nomenclature but that doesn't invalidate the terminology used by chess problem creators in their own work.

Re: No reachable chess position with more than 218 moves

#119

Post by hx8 »

codeulike wrote: post #10

They dont really spell it out but they mean "from this position the player has 218 possible legal moves to choose from"

I had the same confusion, until they showed the existing 218 position and realized it was about maximizing white's legal moves.

Re: No reachable chess position with more than 218 moves

#120

Post by amenghra »

codeulike wrote: post #10

They dont really spell it out but they mean "from this position the player has 218 possible legal moves to choose from"

The confusion is perhaps caused by the word “reachable”. “No legal chess position with more than 218 possible moves” would have been more clear imho.
Post reply on HN