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

91–100 of 204 posts

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

#91

Post by kaashif »

astrobe_ wrote: post #80
solardev wrote: post #5

Meanwhile the non-comp-sci dev in me is like, "why not just store every position in a simple JSON so everyone can read it and everything can parse it". Yeah, it might be half a kB, but you don't have to run through mental gymnastics just to render the pieces...

In the early 90ies, we used to have pocket electronic chess games. I used to have myself one that was about the size of a pocket calculator (it actually was also a pocket calculator), which included a tiny board with tiny, tiny chess pieces. Not a strong opponent and quite slow, but good enough for casual games on the road. I doubt you could fit that JSON file in its NVRAM. Sometimes I wonder how much sooner we could…

> 90ies

I've only seen 90s (nineties), never 90ies (ninety-ies). I am imagining the second one pronounced differently.

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

#92

Post by duskwuff »

Scarblac wrote: post #71
jade-cat wrote: post #58

Earlier quoted context omitted.

Fair enough. Still up to 50 board states that can influence the current one (the 50 move rule is coming to help here) FEN doesn't store previous states, but EPD can. It just goes to show how meanings and requirements change depending on context, which is super interesting in and of itself :P

Also, database software gets so clever with storing games that they often can't save games that have illegal moves in them. But there are plenty real games from real tournaments that had illegal moves in them that nobody noticed...

What's the proper notation for "while White closes his eyes to think about his next move, Black quietly moves one of his pawns over a square"? :)

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

#93

Post by sufianrhazi »

penteract wrote: post #88
sufianrhazi wrote: post #70

Earlier quoted context omitted.

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

Oh you're right, nice catch!

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

#94

Post by Dylan16807 »

Oh, no encoding of the turns? Then the encoding I came up with after following in the link to Forsyth–Edwards Notation is even better.

Version 1: For each position on the board, store if it has a piece or not. 8 bytes for that. Then for each piece in order, 4 bits can encode color and type. 16 bytes for that. Then you can spend 4 bits on castle ability, and 4 bits to pick the pawn that is able to be captured en passant (If there isn't one, pick a pawn that isn't in position. It's impossible for all the pawns to be in a vulnerable rank and have an enemy pawn in position.) So that's 25 bytes, no sweat.

Version 2: Instead of 4 bits per piece, store color|0 for a pawn, and color|1|type for anything else. Encode castle-eligible rooks and castle-ineligible rooks as separate types. This costs 14 bytes at the start of the game, and if you promote a piece at least one pawn has to die so the cost increases by 1 bit at most, up to 8 times. So 15 bytes, and you can always squeeze the bits for en passant eligibility into the 15th byte, because more promotions means fewer pawns to keep track of. You can even say whose turn it is by encoding "active turn king" and "inactive turn king" as different types. That's 23 bytes for the entire board state.

Either way you can add the turn counters with 2 more bytes.

Edit: Okay, this version beats mine solidly: https://news.ycombinator.com/item?id=37526804 I was thinking wrong about the number of captures versus promotions, and you can get much more clever with encoding en passant. So 22 bytes or less is enough for this sort of method.

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

#95

Post by skupig »

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…

You can use duplicate king identifiers to represent castling available, and replace the extra rook identifiers with "black king (my turn)" and "white king (my turn)" to store the turn in the same amount of space.

edit: You can then use the inverted/flipped board trick to store one bit of your piece list, down to 191 bits.

edit2: You only need one "king (my turn)" ID, which represents the whichever color you didn't use for the other king. You can use the extra value for another "my turn" piece that also sets a bit. 190 bits!

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

#96

Post by 6510 »

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…

My thought was to have additional schemes depending on the length of the byte array. For example, if the position is an empty array it is the beginning position, if it is 1 byte it represents the most common positions.

"" is the beginning position

"0" is E4

"1" is D4

"2" is C4

"3" is E4 E5

"4" is D4 D5

"5" is G3

One could do a multi byte version where the order of popular positions is replaced with a crappy chess computer.

If there is no en-passant, no promoted pawn and castling is allowed you can use representations slightly shorter than 24.

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

#97

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…

To cut 2 bytes off (while making it much less elegant), huffman coding could be used to store pawns in 3 bits - to guarantee a space reduction, this relies on the fact that if there are n promoted pawns, there must have been at least ceil(n/3) captures, freeing up space for the longer representation of promoted pawns.

It is necessary to find another way to represent en-passant opportunities (swap an en-passantable pawn with the piece in the 1st or last rank as mentioned https://news.ycombinator.com/item?id=37526523 ).

2 rook representations aren't needed (encode a king with castling opportunities as a knight, bishop or rook, and when decoding, if there are no kings of a given color, look at the piece in the king's starting position) so another 4 bits could be saved by making rook, bishop or knight representations shorter.

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

#98

Post by astrobe_ »

kaashif wrote: post #91
astrobe_ wrote: post #80

Earlier quoted context omitted.

In the early 90ies, we used to have pocket electronic chess games. I used to have myself one that was about the size of a pocket calculator (it actually was also a pocket calculator), which included a tiny board with tiny, tiny chess pieces. Not a strong opponent and quite slow, but good enough for casual games on the road. I doubt you could fit that JSON file in its NVRAM. Sometimes I wonder how much sooner we could…

> 90ies I've only seen 90s (nineties), never 90ies (ninety-ies). I am imagining the second one pronounced differently.

I might have seen it somewhere, but probably written by a non-native as well ;-) Thanks for the correction.

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

#99

Post by timerol »

Dylan16807 wrote: post #94

Oh, no encoding of the turns? Then the encoding I came up with after following in the link to Forsyth–Edwards Notation is even better. Version 1: For each position on the board, store if it has a piece or not. 8 bytes for that. Then for each piece in order, 4 bits can encode color and type. 16 bytes for that. Then you can spend 4 bits on castle ability, and 4 bits to pick the pawn that is able to be captured en passa…

Your version 1 is similar to my top level comment. Note that 4 bits is enough to encode color, type, and include special types for en passantable pawn and castleable rook, so you keep a clean 24 bytes. (Compressing the two special types into one special option, decodable based on position, can get just under 23 bytes.)

For version 2, note that 12 promotions can happen, since one capture (white's B pawn taking black's A pawn) can open up the promotion path for 3 pawns (white's B pawn, white's A pawn, and black's B pawn). Two bits per pawn and 5 bits per other piece start at 14 bytes, but can go as high as 17.5 bytes. (Promoting 12 pawns with 0 other captures would be pretty ridiculous as a game, but technically possible...)

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

#100

Post by seanhunter »

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…

As the article discusses, there's a bit more than that to store in a position. Specifically you have to store whether or not castling is available for the two sides and also whether any pawns are en passant targets, since both of those moves are available (or not) conditionally in a given position based on previous moves in the game.
Post reply on HN