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

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

#201

Post by kurinikku » Sun, Sep 17, 2023, 10:09 PM UTC

teo_zero wrote: post #200

kurinikku wrote: post #199

Earlier quoted context omitted.

What I meant to say was "I haven't quite figured out how to use this to encode reliably and get an improvement vs simply using own king's position". If we can guarantee that the pawn stays in its own file then I see a path for improvement (by having the actual position vs back row usage as a 1-bit toggle), but this is not broadly the case due to movement across files on pawn captures.

My method doesn't require any additional bits for the e.p. and is compatible with all the other techniques listed in TFA. Using own king's position loses the info of the file. Iff you guarantee that the pawns are listed in order, this is not a problem. But later in TFA a permutation or sorting of pawns is suggested, which would then mess things up. Please note that a slightly modified version of my method, where a pa…

OK I see what you mean, I admit this wasn't made completely clear in the post. For en passant using the own king's position, the file where the pawn can be captured en passant is NOT reordered whereas other pawns, captures and promotions are reordered.

This is detailed in the Python code. https://github.com/savarin/bitpacker/blob/239d68dcd3ec5db67e...

Yes using the back row works too! I was trying to see if we can get an improvement on the 18 additional bits needed from the post (or 14 additional bits by taking advantage of knight and bishop ordering).

These discussions have been great, very much enjoying seeing the incremental improvements!

Edit: I did another pass, item 4 in the notes did mention this.

> [4] For en passant we need the pawn to remain on its home file. Hence we exclude the pawn from this step if it can be captured en passant. Captures can appear on any file.

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

#202

Post by [deleted] » Sun, Sep 17, 2023, 10:24 PM UTC

teo_zero wrote: post #200

kurinikku wrote: post #199

Earlier quoted context omitted.

What I meant to say was "I haven't quite figured out how to use this to encode reliably and get an improvement vs simply using own king's position". If we can guarantee that the pawn stays in its own file then I see a path for improvement (by having the actual position vs back row usage as a 1-bit toggle), but this is not broadly the case due to movement across files on pawn captures.

My method doesn't require any additional bits for the e.p. and is compatible with all the other techniques listed in TFA. Using own king's position loses the info of the file. Iff you guarantee that the pawns are listed in order, this is not a problem. But later in TFA a permutation or sorting of pawns is suggested, which would then mess things up. Please note that a slightly modified version of my method, where a pa…

[deleted]

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

#203

Post by kurinikku » Mon, Sep 18, 2023, 12:00 AM UTC

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…

OP here. I'm not sure how I overlooked this comment earlier, but this is elegant and it works! It's amazing how you need exactly 4 bits for each bit. Thank you for sharing!

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

#204

Post by aimor » Tue, Sep 19, 2023, 10:28 PM UTC

aimor wrote: post #83

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

Trying to strike a balance between raw enumerations of all valid states and practicality:

Rooks and Knights are identical, so their positions fall into [64 choose 2] states + 1 state for when both are captured (only one can occupy the King's location) + 3 states for when both are in the starting position and castling is available for one or the other or both

  2020 states = 11 bits * 2 colors * 2 piece types = 44 bits

Bishops only occupy half the board (32 states) + 1 state to track captures

  33 states ^ (4 unique pieces) = 21 bits

Queens and Kings just store their location

  64 states = 6 bits * 4 pieces = 24 bits

Pawn promotions uses the same method as the article

  9 bits x 2 colors = 18 bits

En passant can be stored by the column + 1 state for none

  9 states = 4 bits

Pawns can be in, uh, [64 choose 8] position states. (It's only 4 billionish)

  [64 choose 8] states = 32 bits * 2 colors = 64 bits

And captured pawns can be 'unpromoted' and placed on an empty spot in the top row since unpromoted pawns will never be there.

And 1 bit for whose turn it is

  1 bit

Total = 176 bits or 22 bytes

Started out thinking about ways to use more of the duplicate pieces, rediscovered the idea of ranking and unranking, started to understand what the person with a limit of 19.2 bytes was doing, tried out just treating position state as [64 choose 32] and only got to 194 bits, then finally worked through this approach.