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

81–90 of 204 posts

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

#81

Post by HALtheWise »

Scene_Cast2 wrote: post #42
HALtheWise wrote: post #31

For what it's worth, this definitely isn't the theoretical limit for compressing a chess board position, which I would probably resort to calculating mathematically. In particular, (simplifying to boards with no pieces captured) this scheme uses 24 bytes for representing piece positions, but the constraint that no two pieces are in the same square means you should actually need only log2(64!/32!) = 22.3 bytes for tha…

Couldn't you make it practical by assuming all possible positions (64) for the first piece, then 63 for the second, and so on, and encode one piece at a time? (Arithmetic coding piece by piece)

Yes, although

1. You'd definitely want to deduplicate positions of identical pieces for even more savings 2. That only handles the case where no pieces have been captured, and the full arithmetic coding would probably need separate "sections" of the integer range for different cases, and the number of sections is also quite high. 3. There's extra nuanced things you might want to handle in the coding, like that pawns can't be on their own back row. That is significantly harder.

It looks to me like https://github.com/tromp/ChessPositionRanking has resolved these sorts of issues, but I haven't dug into exactly how.

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

#82

Post by bewaretheirs »

thurn wrote: post #69
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.

But in those cases you're missing the pawn that was promoted, so the location of the second dark-square bishop would be encoded in a 6-bit pawn slot rather than a 5-bit or base-33 bishop slot.

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

#83

Post by aimor »

What about bishops?

The bishops are limited to half the board so only need 5 bits for position. This frees up 4 bits, but you lose the capture state (can't use King's position for capture state). Well, you CAN use the king's position for capture state for two of the bishops at any given time. Then for the other two bishops use a bit to store their capture state. This saves 2 bits overall, bringing the total down to exactly 26 bytes.

Gonna have to think that through for awhile, not sure if it works out.

Update: I see a comment below that does this but uses 21 bits (instead of 22) by storing bishop position and capture state as a base-33 number.

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

#84

Post by thechao »

TylerE wrote: post #50
Scarblac wrote: post #10

Storing a chess position in 26 bytes. Storing a game is also interesting. The number of legal moves varies depending on the position. You could try to define a variable length encoding by giving more likely moves a shorter encoding, but the ordering would need to be deterministic so it could be decoded (running Stockfish for a second isn't).

I suspect it would be hard to beat pgn run through a good compression algorithmn. Or similarly essentially a binary version of pgn. Probably the optimalist of optimal is a binary specifying the starting square (6 bits), and then a minimal-width for the specified piece number that indexes against a standard set of move offsets. So, for instance, a knight has (ignoring potential exposed checks, board boundaries, etc, 8…

You only need 5b to encode the piece to move: you know whose turn it is. Also, as the game progresses, you can reindex to reduce the number of bits to define which piece is moving.

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

#85

Post by omoikane »

This reminds me of how Oscar Toledo disassembled Video Chess, which ran in just 128 bytes of memory:

https://news.ycombinator.com/item?id=36431917

It uses lower 4 bits of 64 bytes to store the board positions (upper 4 bits is used to store other data). 64 nibbles is 32 bytes, not too far off from the 26 bytes here.

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

#86

Post by devit »

tromp wrote: post #73
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 position, as stored in FEN notation, also includes side-to-move.

There's a simple trick to encode it: if there are less than 32 pieces, invert the bitboard (easily decoded since boards can't have more than 32), while if there are 32 pieces flip the board vertically (easily decoded because white pawns can't be after black pawns with no captures).

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

#87

Post by timerol »

sufianrhazi wrote: post #70
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 d…

I like the bitboard inversion idea. (Requires flipping logic as well from https://news.ycombinator.com/item?id=37526484, since 32 is a special case.) Note that the en-passantable pawns and castle-able rooks came from options that were unused in my first pass (linked comment). I could use 0x1 as "castleable rook or en-passantable pawn, determined from where it is" and then store 32 integers with 13 options in 119 bits[1], saving 9 bits. But I'm kinda attached to the simplicity here.

(The 16->32 was edited as you wrote this comment.)

[1] log(13^32)/log(2) = 118.4

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

#88

Post by penteract »

sufianrhazi wrote: post #70
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 d…

> 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.

This doesn't quite work because if there are exactly 32 bits set, inverting it leaves 32 bits set. You could fix this by marking all pawns belonging to the player who's turn it is as capturable via en-passant (if a player has no pawns left, at least 1 piece has been captured, so inverting the bitboard works).

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

#90

Post by 6510 »

sufianrhazi wrote: post #70
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 d…

There is never a pawn at the 8th row, one might "insert" an en-passant row into the board.
Post reply on HN