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

31–40 of 204 posts

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

#31

Post by HALtheWise »

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 that case, with 13 bits of savings. The scheme proposed here reclaims some of that overhead by granting special meaning when a piece's location overlaps with the king, but still is capable of representing other illegal positions where non-king pieces occupy the same square.

Unfortunately, decoding a mathematically optimal encoding quickly devolves to making a list of all possible board configurations and indexing into it, so I'd definitely believe that the proposal here is close to the smallest practically useful representation.

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

#32

Post by catapart »

Timon3 wrote: post #19
x86x87 wrote: post #13

Earlier quoted context omitted.

Iy's not meant for humans to read directly. The compact representation helps performance amd storage a lot when it comes to looking at a lot of positions. If you were to store it as a json most of your time would be spent parsing.

This is illustrated very well in Sebastian Lague's video "Coding Adventure: Making a Better Chess Bot" ( https://www.youtube.com/watch?v=_vqlIPDR2TU ).

Awesome video and, I'll admit, the timing makes me curious to know if that video maybe inspired some devs to either pick up this kind of encoding work, or maybe just to finish up some encoding work that they had already started.

Most likely unrelated, I know! Just a wondering in passing.

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

#33

Post by [deleted] »

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…

[deleted]

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

#34

Post by dmurray »

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…

Not a "legal" board, but a typical board. Both this and the original de Groot study picked positions from real games played by strong players. Experts don't do retrograde analysis on the positions, but they do recognise typical patterns that often occur in real play.

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

#36

Post by thdc »

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:/…

Yeah, it seems like the author is storing more information than just the position but not enough to figure out all of the possible next states of the game.

Another straightforward thing missing is the player's turn; this could determine whether the position is a stalemate or not.

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

#37

Post by IshKebab »

petters wrote: post #6
OJFord wrote: post #4

Original title is: > Compressing chess positions for fun and profit Which unlike that here is correct: you can store a board , the positions, in 26B; not an arbitrary length game!

Most games could possibly be encoded in less than 26 bytes. There are not that many legal moves each time and if you sort them by probability it may not require many bits to describe which one the players chose.

I doubt it. You could maybe get as low as 1 bit per move, but how many games are only 26 moves? Would be interesting to find out though!

Maybe this paper says. I didn't read it.

https://www.researchgate.net/figure/Entropy-and-distribution...

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

#38

Post by hutzlibu »

cylon13 wrote: post #28
solardev wrote: post #23

Earlier quoted context omitted.

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?

Is your assertion that it takes more time for a CPU to read values out of a 30 byte struct and do a couple shifts and branches than to parse a JSON representation?

The JSON needs to be parsed only once. Then it is (or can be) just any object to your liking.

JSON is for storing data as text. Not work with that text all the time.

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

#39

Post by drivers99 »

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:/…

They'd also need to store whose turn it is, so I'm guessing the article is strictly about "positions" and not game state.

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

#40

Post by timerol »

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 there are less than 16 bits set in the bitboard, ignore the last items in the list.

  0000 - 0x0 - black pawn 
  0001 - 0x1 - black pawn (can be en-passant'd)
  0010 - 0x2 - black knight
  0011 - 0x3 - black bishop
  0100 - 0x4 - black rook (castling unavailable)
  0101 - 0x5 - black rook (castling available)
  0110 - 0x6 - black king
  0111 - 0x7 - black queen
  1000 - 0x8 - white pawn 
  1001 - 0x9 - white pawn (can be en-passant'd)
  1010 - 0xA - white knight
  1011 - 0xB - white bishop
  1100 - 0xC - white rook (castling unavailable)
  1101 - 0xD - white rook (castling available)
  1110 - 0xE - white king
  1111 - 0xF - white queen
I think that covers all possibilities to store a chess position in 64 + 32 * 4 = 192 bits, or 24 bytes exactly.

The starting position would be represented with a bitboard of 0xFFFF00000000FFFF, with a list of [0xD, 0xA, 0xB, 0xF, 0xE, 0xB, 0xA, 0xD, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x5, 0x2, 0x3, 0x7, 0x6, 0x3, 0x2, 0x5], using the same position-to-number scheme in the blog post

Edit: 32 pieces, not 16. Thanks to the peanut gallery for catching it quickly

Edit2: To store which player is next: do nothing for white. For black, if there are 32 pieces, flip the bitboard upside down. (To check if it's black's turn, verify that black pawns are "below" white pawns, which is illegal before captures are made.) If there are less than 32 pieces and it's black's turn, invert the bitboard. (To check, count the number of set bits.) This is entirely taken from https://news.ycombinator.com/item?id=37526484

Post reply on HN