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

71–80 of 195 posts

Re: No reachable chess position with more than 218 moves

#71

Post by jibal »

davedx wrote: post #55
electroly wrote: post #32

Earlier quoted context omitted.

Look again. It's at A1. You may be confusing that symbol with a different piece.

Ugh. Sigh, I see it now - I thought that was the white king, because it has quite some white in it. I will allocate 50% blame to my brain and eyes, and 50% to whoever designed a black king to have so much white in it :P Thanks!

No, it's 100% on you. If the piece on a1 is a white king, then what's the piece on f1? And why would there be no black king, when the subject is reachable (and thus legal) positions?

Re: No reachable chess position with more than 218 moves

#72

Post by sim7c00 »

dmurray wrote: post #64
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?

I believe 8848.5 under modern rules (with the 75-move rule, as in FIDE rules since 2014). There's a reasonably rigorous demonstration here: https://wismuth.com/chess/longest-game.html

how can the longest game have half a move???

Re: No reachable chess position with more than 218 moves

#73

Post by jibal »

amelius wrote: post #40
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"

If only they had appended "to choose from" to the article headline, it would have been clear from the start.

The caption on the first position is "Reachable chess position with 218 moves for White, published by Petrović in 1964."

And the title is unambiguous: "There is no reachable chess position with more than 218 moves" -- that cannot possibly mean "There is no reachable chess position that it takes more than 218 moves to reach". Also, lichess is a chess site, where people are certain to know that chess games can go way beyond 218 moves.

Re: No reachable chess position with more than 218 moves

#74

Post by jibal »

electroly wrote: post #35
nabla9 wrote: post #33

Earlier quoted context omitted.

It should be obvious that there are no 8.7 × 10^45 possible chess moves from any chess position. All pieces have less than 32 moves per piece and 19 pieces means less than 608 moves.

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.

Re: No reachable chess position with more than 218 moves

#75

Post by leoff »

unkulunkulu wrote: post #50
winternewt wrote: post #47

Earlier quoted context omitted.

I thought it was "there's no position in chess that requires more than 218 moves to reach."

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"

Re: No reachable chess position with more than 218 moves

#76

Post by jibal »

margalabargala wrote: post #23

Am I missing something, or is the configuration shown initially not actually reachable? It's white to move, yet the black pawns are in their starting location and the black king has no adjacent empty square, it's entombed by its pawns and the white bishop so the configuration could not have been reached.

[flagged]

Re: No reachable chess position with more than 218 moves

#77

Post by kevindamm »

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.

I didn't know it required a player to invoke it, I was basing the statement on chess implementations I've read (and written) where it kicks in automatically... but the 5-time limit you mention still supports my case that there's an upper limit. As long as the number of pieces remains the same, there are a finite number of arrangements for them so eventually (after a finite number of moves) a position would be repeated enough times. If a piece is captured (or converted) it resets this but still yields a finite number of new arrangements. Eventually you either cannot avoid the repetition, or a win condition is met, or a draw for insufficient material.

Compare this to, say, the L game, where the number of moves is unbounded.

Re: No reachable chess position with more than 218 moves

#80

Post by dbatten »

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 asking whether it's possible that Gurobi got trapped in a local maximum, or whether this can be considered a definitive universal solution.

Post reply on HN