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

151–160 of 195 posts

Re: No reachable chess position with more than 218 moves

#151

Post by fsckboy »

unkulunkulu wrote: post #53
BrenBarn wrote: post #20

Earlier quoted context omitted.

Yes, very strange that the phrase "possible moves" never occurs in the article. The key word is "possible". The article consistently just uses the phrasing "have moves" but this is not an obvious way of phrasing things to the average person (although I think it's more common in chess lingo).

in chess lingo the most common is “legal moves”

in chess lingo, most common is "moves"; only in a weird circumstance (beginners?) would you need to say "legal".

the "possible" qualifier would probably be used for an "english" reason rather than a "chess" reason, to suggest "future" moves as opposed to the moves already made to get to a position. it would be more likely for whatever reason to say "how many possible moves" than "how many future/hypothetical moves", i.e. the use of possible is not to rule out the idea of impossible, simply to mean how many "could you make now from a particular position" and/or i guess to suggest "possible initial moves" as opposed to future follow-on moves.

the ambiguity is not really in chess, it's in english (and probably every other language also)

Re: No reachable chess position with more than 218 moves

#152

Post by hyperpape »

salt4034 wrote: post #108
dbatten wrote: post #104

Earlier quoted context omitted.

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!

The article was interesting, but this bit felt a bit like "and then a miracle occurred".

Re: No reachable chess position with more than 218 moves

#153

Post by Tobs40 »

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…

Hi, author of the Lichess article here.

relaxing and omitting chess rules also changed the choice of variables. I did try lazy constraints etc. before diving into the math, but they did not yield a significant speedup. For example, not considering the white king as being in check simplified A LOT.

Best regards, Tobi

Re: No reachable chess position with more than 218 moves

#154

Post by Tobs40 »

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…

Author here!

Yes, if Gurobi and my code run as intended and I did not mess up any thinking while simplifying my chess model, then what I did is proof that the maximum number of legal moves available in a chess position reachable by a sequence of legal moves from the starting position is 218 (upper and lower bound). Gurobi proved the entire search space as "at most as good" using bounds, basically.

Re: No reachable chess position with more than 218 moves

#155

Post by electroly »

jibal wrote: post #74
electroly wrote: post #35

Earlier quoted context omitted.

No, they do mean possible moves and they don't mean maximum length game. There are on the order of 10^45 reachable chess positions . The article did not say that was the number of moves from one position. The article says 218 is the maximum number of moves from one reachable position--it's the whole point of the article!

The person you responded to knows that.

Their post was edited to remove the part I was responding to; the "do" in my post was directly correcting the "don't" in their original post, and vice versa.

Re: No reachable chess position with more than 218 moves

#156

Post by Tobs40 »

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…

Author here.

The position is White to move, so even if the b2 pawn was not pinned by a white queen to the black king, it could not move. The b2 pawn is necessary to shield the black king from checks as this position is White to move - otherwise it would be illegal.

Also, rest assured, I checked everything thoroughly. There is indeed no way to squeeze out more than 218 legal moves for White here, but it's fun to try and I'm glad that people actually care about my article, didn't expect that, haha ^^

Re: No reachable chess position with more than 218 moves

#157

Post by Tobs40 »

dooglius wrote: post #78

I'm confused, what did he change after the 271-move model to get it to produce the optimal solutions? It just says "With this improved model"...

Author here!

Did you read the entire article?

It's 271.666... moves, not 271.0 :) This bound comes from model where whole decisions (0 or 1) are relaxed to continuous ones (0.0 to 1.0 and anything in between), e.g. a piece can only be 0.23 there and only be 0.843 able to make a particular move. The advantage of this black magic is that it is way faster to compute and only overestimates the number of moves - hence we can use that to prove away bad partial solutions. Without a technique of this kind, searching the solution space would be absolutely intractable!

Re: No reachable chess position with more than 218 moves

#158

Post by Tobs40 »

kryptiskt wrote: post #9

Now I wonder how Nenad Petrović and Jenő Bán came up with the optimal solutions to the problems in the 60s.

Author here!

Composing such a position is much easier than mathematically proving that there isn't a better one. Perhaps there is an elegant proof. Perhaps they had reasoning that proved that they couldn't do better while composing it. Probably involves plenty of case distinctions. So I decided to just let a computer reason through it, also because human minds are fallible ^^

Re: No reachable chess position with more than 218 moves

#160

Post by kelipso »

refulgentis wrote: post #130
kelipso wrote: post #84

Earlier quoted context omitted.

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

It’s also rare to have one with more than 50 moves. I’m curious if this class of observation will help establish a true bounds. Especially because we don’t have a definition of what it means - my instinct is to first do that, so “infinity” isn’t the obvious upper bound.

Proving this feels more difficult than proving what’s in the OP article, because here you have to show path lengths between original position and all possible positions have a max length, while OP article had to show all positions have a max degree. Path length just seems like a harder problem compared to node degree.
Post reply on HN