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

171–180 of 195 posts

Re: No reachable chess position with more than 218 moves

#171

Post by dooglius »

Tobs40 wrote: post #157
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…

I did read the entire article yeah, and I was rounding down with "271", but it wasn't clear to me what change you made that got you to the finish line. Are you saying that the next improvement was to force Gurobi to use integer values? It's surprising to me that wouldn't kill performance since ILP is NP-hard whereas real LP can be solved in polynomial time.

Re: No reachable chess position with more than 218 moves

#172

Post by [deleted] »

tln wrote: post #162
refulgentis wrote: post #130

Earlier quoted context omitted.

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.

What? Lots of serious chess games last more than 50 moves Not sure if I'm reading your comment correctly The upper bound of moves is 8848.5 https://www.reddit.com/r/chess/comments/168qmk6/longest_poss... ... under the rule that after 75 moves without a capture or pawn advancement the game is drawn

[deleted]

Re: No reachable chess position with more than 218 moves

#173

Post by salt4034 »

Tobs40 wrote: post #157
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…

This part is unclear; what exactly did you change? Are you saying that the LP relaxation has value 271.666, but, when you enforce integrality, Gurobi can actually find and prove optimality of a solution with value 218?

Were you really just solving LPs up to this point in the article? How can these intermediate LPs be so slow to solve (6+ years) and yet Gurobi is able to solve the integer-restricted problem?

Re: No reachable chess position with more than 218 moves

#174

Post by refulgentis »

tln wrote: post #162
refulgentis wrote: post #130

Earlier quoted context omitted.

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.

What? Lots of serious chess games last more than 50 moves Not sure if I'm reading your comment correctly The upper bound of moves is 8848.5 https://www.reddit.com/r/chess/comments/168qmk6/longest_poss... ... under the rule that after 75 moves without a capture or pawn advancement the game is drawn

You read a comment saying it’s rare to have more than 200 moves, then a reply noting more than 50 is also rare, then suggested you were confused and maybe it was unreadable and asked “What?” because…some games have above 50 moves. shrugs

Thanks for note re: upper bound with 75 moves without pawn advancing constraint.

Re: No reachable chess position with more than 218 moves

#175

Post by tshaddox »

NooneAtAll3 wrote: post #141
AceyMan wrote: post #137

Earlier quoted context omitted.

The word 'available' inserted at the right spot would make all the difference in clarity here.

imo "possible" would be better

I'd go with "legal," which also implies possible.

Re: No reachable chess position with more than 218 moves

#176

Post by Tobs40 »

randall wrote: post #168
Tobs40 wrote: post #149

Hi all, 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

so just to be clear: for every board position there are no more than 218 moves available? is that the understanding?

It's your turn and you have 218 moves to choose from. This is the best possible and the article proves this (assuming no bugs in machine or mind).

Re: No reachable chess position with more than 218 moves

#177

Post by Tobs40 »

salt4034 wrote: post #173
Tobs40 wrote: post #157

Earlier quoted context omitted.

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…

This part is unclear; what exactly did you change? Are you saying that the LP relaxation has value 271.666, but, when you enforce integrality, Gurobi can actually find and prove optimality of a solution with value 218? Were you really just solving LPs up to this point in the article? How can these intermediate LPs be so slow to solve (6+ years) and yet Gurobi is able to solve the integer-restricted problem?

Ah, I see the misunderstanding.

I've always been solving the integer problem of course. But throughout the article, I improve the model formulation again and again through insights, which makes the LP relaxation tighter. Initially, it gave 305.0 as upper bound, but after tightening the model (addind constraints that cut off that 305 solution and others) it gives 271.666...

- which leads to insanely faster search. It's like brute-forcing through all passwords of length 20 and a wizard telling you that you're wrong when you reach character 7 instead of 13.

Re: No reachable chess position with more than 218 moves

#178

Post by Tobs40 »

renewiltord wrote: post #169
Tobs40 wrote: post #161

Earlier quoted context omitted.

Author here, I considered but decided against the complexity, haha. I added a Github link towards the bottom of the article though. Code might not be pretty though .__.

Haha yeah, I saw the code and it is pretty comprehensible but some things are curious. I thought some of the naming was amusing "ENABLE_ROYAL_CUDDLING" etc. Thanks for the writeup.

Oh no, I forgot to rename that variable before publishing, haha

Re: No reachable chess position with more than 218 moves

#179

Post by Tobs40 »

electroly wrote: post #6
reader9274 wrote: post #4

Isn'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…

Author here!

You are correct! It's White to move and White has 218 moves to choose from as their next move. My article proves that you can't do better than 218.

Re: No reachable chess position with more than 218 moves

#180

Post by jibal »

margalabargala wrote: post #123
jibal wrote: post #76

Earlier quoted context omitted.

[flagged]

Thanks for the condescension. It really helps me file your comment's suggestions appropriately. Here's a general rule of thumb: If the options are a) answer someone's question, and b) answer someone's question but also then spend triple the word count telling them it was a stupid question Then picking (b) makes you an asshole. If all you had written was your first sentence this could have been a pleasant interaction…

Pure defensive (and extremely rude and hostile) projection. (And the response is more of the same, and full of fallacies and false statements). There was no condescension in my comment, just an attempt to be helpful (speaking of "suppression", I will attempt that again with this person). I did not say your question was stupid (it wasn't), I said that you were projecting stupidity on the author of the article (I didn't say you think they are stupid, but apparently this distinction is too subtle for some), and that warrants a rethink.
Post reply on HN