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

41–50 of 195 posts

Re: No reachable chess position with more than 218 moves

#41

Post by cabirum »

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)

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.

Re: No reachable chess position with more than 218 moves

#42

Post by tromp »

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)

That's ceil(log2(~4.8x10^44)) = 149 bits. But to make it efficiently decodable you'd use the ceil(log2(8726713169886222032347729969256422370854716254)) = 153 bit representation of the ChessPositionRanking project linked to in my other comment. The ChessCounter project does not provide an efficiently decodable code.

Re: No reachable chess position with more than 218 moves

#43

Post by mcherm »

cabirum wrote: post #41
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)

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.

Re: No reachable chess position with more than 218 moves

#45

Post by XCSme »

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.

Isn't that estimate just 20x bigger? Which is not a big difference considering the magnitude.

Re: No reachable chess position with more than 218 moves

#47

Post by winternewt »

wodenokoto wrote: post #12
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 it was "How many moves in a game does it take to reach this position"

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

Re: No reachable chess position with more than 218 moves

#48

Post by pmontra »

codeulike wrote: post #28
pmontra wrote: post #27

How can a position with more than 9 white queens be legal? The limit seems to be one queen plus 8 promoted pawns.

There are only 9 queens on the board

The caption of the last diagram is "Legal but non-reachable position with 271 moves for White. Corner queens can be replaced with bishops." There are 24 white queens.

Re: No reachable chess position with more than 218 moves

#49

Post by contravariant »

pmontra wrote: post #48
codeulike wrote: post #28

Earlier quoted context omitted.

There are only 9 queens on the board

The caption of the last diagram is "Legal but non-reachable position with 271 moves for White. Corner queens can be replaced with bishops." There are 24 white queens.

That's the difference between illegal an unreachable. To reach that position you'd need to start from a different point (start both sides with 16 pawns or w/e), but you wouldn't need to break any other chess rules.

Re: No reachable chess position with more than 218 moves

#50

Post by unkulunkulu »

winternewt wrote: post #47
wodenokoto wrote: post #12

Earlier quoted context omitted.

I thought it was "How many moves in a game does it take to reach this position"

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