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

111–120 of 204 posts

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

#111

Post by hinkley »

seanhunter wrote: post #100
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.

I don’t think that’s true. Or rather, it’s only true for storing board position not for storing the move history. If you have the entire move history you know that status of each piece.

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

#112

Post by timerol »

penteract wrote: post #97
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 pa…

A Huffman code like this can also represent knights (or any single other piece) in 3 bits.

  000 - black pawn
  001 - black knight
  0100 - black bishop
  0101 - black rook
  0110 - black king
  0111 - black queen
  100 - white pawn 
  101 - white knight
  1100 - white bishop
  1101 - white rook
  1110 - white king
  1111 - white queen
Going with "a pawn in the first row is actually en-passantable, and should be swapped with the piece in the appropriate position if it exists", and "kings are represented as knights when they can castle in either direction, bishops when they can only castle kingside, and rooks when they can only castle queenside", that gets the initial representation down to 64 + 16 * 3 (pawns) + 6 * 3 (knights and kings) + 10 * 4 = 170 bits, with a worst case of 172 bits (when kings lose some castling rights), if I understand it correctly.

Huffman encoding for 21.5 bytes seems to win the day.

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

#113

Post by [deleted] »

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.

[deleted]

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

#114

Post by gowld »

ThomasCM wrote: post #48
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).

Surprisingly, storing a game (with all moves) can take less space than encoding a single board. This is because you can effectively encode a move in a single byte (as there are less than 255 moves possible in each position). Applying compression to the resulting binary string will allow you to reduce the space even more. Check out this great blog post of Lichess for more information: https://lichess.org/blog/Wqa7GiAA…

Are you saying that, to encode a valid position, ignoring the cost to encode both the starting position and the move definitions, you can encode the move sequence using less information than encoding a single position?

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

#115

Post by hinkley »

jade-cat wrote: post #12

There are two more things that should be considered. Both of them unlikely to influence a position, but they can matter - just like the en passant target. The fifty move rule[0] is quite simple, just store a number, fits in five bits. But the threefold repetition rule[1] is quite a pickle - it basically means that to know everything about a position you need to know every position that occurred before it. [0] https:/…

I prefer the Ko rule of Go.

You can’t repeat the last position. But repeating a pattern of part of the board every two turns can force progress to resolution. The entire board never repeats, but it also stops the loop earlier.

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

#116

Post by hinkley »

Scarblac wrote: post #29
pfooti wrote: post #15

An interesting cognitive phenomenon: if you ask chess experts and novices to memorize and recall an arbitrary chessboard, the experts are significantly better than the novices _only if_ the board is a legal board that can be arrived at during play. If it is not a legal board, there's no particular difference between novices and experts. Original ref: Chase & Simon 1973, Perception in Chess. This is usually taken to m…

It's not really about whether it's legal, but whether it looks normal . Very bizarre positions can easily be legal, but they're hard to remember for everyone.

I’ve heard this corroborated by exhibition players who play ten or fifteen opponents at once. They do better with moderately skilled opponents than random people.

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

#117

Post by alexb_ »

Dylan16807 wrote: post #109
alexb_ wrote: post #106

Earlier quoted context omitted.

> 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. Can you explain this in more detail? Curious as to how you could save space with this.

You read the piece data bit by bit. If you see 100 or 000 then you stop right there. You have a pawn, and the next piece starts with the next bit. There's no ambiguity. Here's a good example image for huffman coding: https://i.ytimg.com/vi/hOabRMHzpo8/hqdefault.jpg So before any captures are made, you have 32 pieces, half of which use 3 bits and half of which use 4 bits. 14 bytes, plus the 8 bytes storing the bitboar…

I see - so you can use the bits you saved by not having separate rook pieces to denote En Passant pawns.

I like the "no kings" idea for castleable kings - though I think with smaller pawn sizes, that gives another opportunity for compression:

- king that can't castle: king

- king that can castle queenside: any other piece in king's position, no king of that color on board

- king that can castle kingside: black pawn on 1st or 8th rank

- king that can castle: white pawn on 1st or 8th rank

Because you are often going to have positions where the king can castle kingside and positions where the king can castle either way, this should maximize how often you manage to save space w/ the pawns.

Another thought I had (which might contain other problems, not sure yet) is to use pawns on the 1st or 8th rank to denote pieces which are in their starting position - the decompression algorithm can then derive what piece it is based on the known starting position. Once we start having data saving because of pawns taking less bits, we want to be able to use them as much as possible to save space.

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

#118

Post by jenscow »

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…

small shavings:

* If there are less than 32 bits set in the bitboard, the item list is shorter (rather than ignored).

* Probably not worth it, but: When there are 32 bits set on the bitboard, stop processing the bit-board.. however, if you adjusted the ordering of the lines (0,7,1,2,...), it's optimised for the first 1 or 2 positions

* Maybe this is cheating, but if the size of the game data will be known ahead of processing, then you could leave off the last item in the list if it's a king or a rook

* Starting the item list with 2 white kings can be a special case for "starting position", and if the items are listed before the board then only 1 byte is needed :)

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

#119

Post by omoikane »

ThomasCM wrote: post #48
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).

Surprisingly, storing a game (with all moves) can take less space than encoding a single board. This is because you can effectively encode a move in a single byte (as there are less than 255 moves possible in each position). Applying compression to the resulting binary string will allow you to reduce the space even more. Check out this great blog post of Lichess for more information: https://lichess.org/blog/Wqa7GiAA…

ChessMonitor looks very nice, I like how you can link to a particular opening:

https://www.chessmonitor.com/u/XqaFNTHcR61WpiMfOhEY/games?po...

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

#120

Post by Dylan16807 »

alexb_ wrote: post #117
Dylan16807 wrote: post #109

Earlier quoted context omitted.

You read the piece data bit by bit. If you see 100 or 000 then you stop right there. You have a pawn, and the next piece starts with the next bit. There's no ambiguity. Here's a good example image for huffman coding: https://i.ytimg.com/vi/hOabRMHzpo8/hqdefault.jpg So before any captures are made, you have 32 pieces, half of which use 3 bits and half of which use 4 bits. 14 bytes, plus the 8 bytes storing the bitboar…

I see - so you can use the bits you saved by not having separate rook pieces to denote En Passant pawns. I like the "no kings" idea for castleable kings - though I think with smaller pawn sizes, that gives another opportunity for compression: - king that can't castle: king - king that can castle queenside: any other piece in king's position, no king of that color on board - king that can castle kingside: black pawn o…

> I see - so you can use the bits you saved by not having separate rook pieces to denote En Passant pawns.

You could do it that way, but the particular comment was suggesting two entirely separate ways to save bits, one for pawns and one for rooks.

Specifically, the suggestion in that post is to use 1st/8th rank to show en passant, and to show castling by replacing an unmoved king with a different piece. But there's lots of ways to cleverly encode that information.

Post reply on HN