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

101–110 of 195 posts

Re: No reachable chess position with more than 218 moves

#101

Post by jfengel »

mcherm wrote: post #43
cabirum wrote: post #41

Earlier quoted context omitted.

Piece type and color fit in 4 bits. So, either a fixed-length encoding of the whole board, 64 * (4 bits) = 256 bits = 32 bytes. Or, sparse variable length encoding of pieces only, 6 bits to index each of 64 squares, = 10 bits * piece count. E.g. initial position takes 32*10 = 320 bits or 40 bytes.

That's a fine upper bound, but it doesn't minimize but usage since it also can represent illegal positions.

The vast majority of the positions are illegal. There is only 1 black king on the board; practically all of the represented positions have more than one. And there are over a dozen kinds of pieces to repeat that for. A better upper bound is almost 100 orders of magnitude smaller.

Re: No reachable chess position with more than 218 moves

#103

Post by hibikir »

aqme28 wrote: post #97
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 thought they meant that no game could go more than 218 moves. I can imagine some upper limit since three-fold repetition ends the game. But it’s a lot higher than 218.

Another relevant rule is a draw after 50 moves without a capture or a pawn move. But yes, the maximum number of moves would be extremely large when both players are trying. Just think of a first 2 moved allowing the king out, an outrageous king march, followed by another pawn move...

Re: No reachable chess position with more than 218 moves

#104

Post by dbatten »

salt4034 wrote: post #100
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 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...

Re: No reachable chess position with more than 218 moves

#105

Post by salt4034 »

eru wrote: post #2

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…

The most commonly used term for this is lazy constraints (https://support.gurobi.com/hc/en-us/articles/360013197972-Ho...).

Re: No reachable chess position with more than 218 moves

#106

Post by LegionMammal978 »

amelius wrote: post #38

What is the least number of bits that can describe any reachable chess board? 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)

The 8.7e45 "restricted" number in that repo rules out certain patterns of pawn promotions. It looks like the 5.68e50 "general" number is the true upper bound, allowing any promotions possible.

Re: No reachable chess position with more than 218 moves

#107

Post by nhumrich »

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.

Re: No reachable chess position with more than 218 moves

#108

Post by salt4034 »

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

I think that was an intermediate model. The author updated it, then Gurobi solved the new model to optimality (i.e., the bound became equal to the value of the best solution found).

> With this improved model, I tried again and after ~23 000 seconds, Gurobi solved it to optimality!

Re: No reachable chess position with more than 218 moves

#109

Post by nhumrich »

tromp wrote: post #18

> There is no reachable chess position with more than 218 moves. "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.

One is "legal" the other is "total problem space" From a computing point of view, the total problem space is what matter because you still have to "compute" if it's legal or not before moving on. There isn't a straightforward way to only iterate over legal positions.

Re: No reachable chess position with more than 218 moves

#110

Post by Scarblac »

unkulunkulu wrote: post #63
weinzierl wrote: post #61

Earlier quoted context omitted.

But this an interesting problem too. More specifically is there an upper bound for the number of moves in a legal chess game?

there certainly is if you consider 50 moves rule. And you can derive an easy upper bound from that as 50x8x8x2 (basically each 50 moves you make a pawn move) if you only consider 3 moves repetition and not 50 move rule then this is harder and the number becomes one of those crazy combinatorical numbers.

The 50 moves rule doesn't have be considered as it is optional. The players may claim, but they don't have to. So the game can continue.

The 75 move rule is the exact same thing but mandatory. That has to be considered.

(same thing is true for 5 times repetition vs 3 times).

Captures also reset the counter, not only pawn moves.

Post reply on HN