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

91–100 of 195 posts

Re: No reachable chess position with more than 218 moves

#91

Post by tromp »

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]

[1] https://tromp.github.io/go/legal.html

[2] https://tromp.github.io/go.html

Re: No reachable chess position with more than 218 moves

#92

Post by qsort »

NickC25 wrote: post #89

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.

It's free, it has the same features as commercial servers, it's open source, developer-friendly, with no ads (not even on free accounts) and a transparent corporate structure under French law.

It's almost ridiculously good. Donate if you can!

Re: No reachable chess position with more than 218 moves

#93

Post by mtremsal »

tromp wrote: post #91

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

Then white plays 1 stone, capturing all the black stones at once, essentially resetting the game with a 360 points lead.

(black goes first, white has Komi, so really a 260+komi points lead)

Re: No reachable chess position with more than 218 moves

#94

Post by GabrielBen »

tromp wrote: post #91

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

A game of Go can be legally infinite due to recaptures. (player passes 360 times, then eats the entire board and it starts over).

It's also a natural infinite game due to Kos which can be the best move to play. This requires a set of extra rules to prevent. (Ko, superKo, triple kos, etc)

Re: No reachable chess position with more than 218 moves

#95

Post by ojo-rojo »

leoff wrote: post #75
unkulunkulu wrote: post #50

Earlier quoted context omitted.

I thought “there is no chess problem that is both reachable from starting position and requires more than 218 moves to solve”

I seriously thought they meant "it's not possible to have a chess game with more than 218 moves"

Yeah, I'm still confused.

Re: No reachable chess position with more than 218 moves

#96

Post by Sharlin »

sverhagen wrote: post #37
WithinReason wrote: post #15

Earlier quoted context omitted.

Thanks, I misunderstood the entire article. Great writing!

How can those two things be true at the same time? Unless you appreciate misunderstanding what you read...?

How could someone ever write something while intending to convey the exact opposite meaning?

Re: No reachable chess position with more than 218 moves

#97

Post by aqme28 »

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.

Re: No reachable chess position with more than 218 moves

#98

Post by tromp »

mtremsal wrote: post #93
tromp wrote: post #91

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

Then white plays 1 stone, capturing all the black stones at once, essentially resetting the game with a 360 points lead. (black goes first, white has Komi, so really a 260+komi points lead)

White cannot play on the last empty point as this would be suicide, which is prevented by the (assumed) superko rule forbidding repetition of the empty position.

Re: No reachable chess position with more than 218 moves

#99

Post by tromp »

GabrielBen wrote: post #94
tromp wrote: post #91

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

A game of Go can be legally infinite due to recaptures. (player passes 360 times, then eats the entire board and it starts over). It's also a natural infinite game due to Kos which can be the best move to play. This requires a set of extra rules to prevent. (Ko, superKo, triple kos, etc)

I assume superko as is standard in several rulesets to prevent infinite play.

Re: No reachable chess position with more than 218 moves

#100

Post by salt4034 »

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.
Post reply on HN