Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to store a chess position in 26 bytes using bit-level magic (2022)

ezzeriesa.com

Post reply on HN
Print view View original

61–70 of 204 posts

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#61

Post by timerol »

elteto wrote: post #53
timerol wrote: post #40

I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…

Maybe a silly question, how do you know which side of the board is white vs black?

Convention - use the same bit-to-number scheme in the blog post. Bit 0 is a1, bit 7 is h1, bit 8 is a2, bit 56 is a8, bit 63 is h8.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#62

Post by penteract »

timerol wrote: post #40

I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…

There are at most 32 pieces on a chessboard (16 of each color), so I think you need 24 bytes.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#63

Post by [deleted] »

timerol wrote: post #40

I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…

[deleted]

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#64

Post by l33t7332273 »

r3trohack3r wrote: post #49
zeagle wrote: post #30

Earlier quoted context omitted.

Finally, a good use case for blockchain technology!

I can't tell if this is in jest or not but blockchains are prolific in software. Nearly every company uses them to prove the authenticity of deployments in production at one or more layers.

I feel like signatures and maybe even Merkle trees are used, but not blockchain.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#65

Post by k1t »

timerol wrote: post #40

I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…

What if there are 32 pieces on the board?

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#66

Post by dekhn »

solardev wrote: post #23
awegio wrote: post #17

Earlier quoted context omitted.

You need a compact encoding for chess engines that explore billions of states as fast as possible to plan the best move.

Well, this is arguably a kind of compression, right? So you'd be trading CPU time for fewer bytes? Is that a desirable tradeoff at chess engine scales?

CPUs excel at decompression; more than one engineer has remarked to me that the fastest way to populate a cache is to decompress data in-line.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#67

Post by timerol »

penteract wrote: post #62
timerol wrote: post #40

I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…

There are at most 32 pieces on a chessboard (16 of each color), so I think you need 24 bytes.

... right. I thought 16 felt a little small. Thanks for the catch, updated

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#68

Post by bhelkey »

timerol wrote: post #40

I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…

A nitpic, to castle, the king AND the rook must not have moved from their starting squares.

Using this approach, you would need to store castling available/unavailable for the kings as well.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#69

Post by thurn »

bewaretheirs wrote: post #59

Bishops move on the diagonal and so can only stay on squares of their original color; you could thus encode the positions of the 4 bishops with 5 bits each instead of 6 each, saving a total of 4 bits, but this would preclude the use of the "store our/their king's location" hack to encode things. But you can encode bishop positions as a 4-digit base-33 number (digits 0..31 indicate the square, digit 32 is captured), w…

It is of course possible to break these rules via promotion, e.g. having two dark square bishops is entirely possible.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#70

Post by sufianrhazi »

timerol wrote: post #40

I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…

Nice! Though there are max 32 pieces on a board, not 16; so this scheme is 64 + 32 * 4 = 192 bits, or 24 bytes.

The bit to indicate whose turn it is isn't accounted for here. But it probably could probably represented by the binary negation of the bitboard -- if there are 32 or fewer bits set, then it is white's turn; if there are 33 or more bits set, then it is black's turn and you can negate the bitboard prior to determining which squares are occupied.

Taking things further, it probably can be compressed even more with (much) more complex logic, as the castling available bit must only be present on the corner positions, and the pawn en-passant capabilities are only available on the middle rows, so those bits are meaningless in other positions.

Post reply on HN