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

41–50 of 204 posts

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

#41

Post by hotnfresh »

solardev wrote: post #23
awegio wrote: post #17

Earlier quoted context omitted.

You need a compact encoding for chess engines that explore billions of states as fast as possible to plan the best move.

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?

Bit packing/mapping et c. isn’t compression the way you’re thinking. What it is, is concise. It requires that the program know what each bit means, rather than telling the program what a value means (as a json structure might), so it shifts where meaning is assigned strictly to the program—a convention must be encoded in the program, not figured out at runtime, though technically you could turn this back into a form of config if you wanted, it just wouldn’t be jumbled up with your data—but it doesn’t really compress the data itself. It’s just efficient at representing it.

[edit] shorter version of the above: it stores the values, but doesn’t store what they mean.

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

#42

Post by Scene_Cast2 »

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)

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

#43

Post by MenhirMike »

solardev wrote: post #23
awegio wrote: post #17

Earlier quoted context omitted.

You need a compact encoding for chess engines that explore billions of states as fast as possible to plan the best move.

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?

To give you an example, the Syzygy tablebase for all endgame positions with 7 pieces remaining is 18.4 TB. The estimated size for 8 pieces is 2 PB.

There are different applications for different things: If you want to host a website with real-world tournament results involving only humans, you probably can get away with using more bytes. But if you're writing an engine that uses pre-computed positions, you want to be as compact as possible.

https://en.wikipedia.org/wiki/Endgame_tablebase#Computer_che...

I did laugh a bit at this bit because "conventional server" and "64 TB RAM" is hilarious to think about in 2023, but will probably be the base config in a Raspberry Pi in 2035 or so:

> In 2020, Ronald de Man estimated that 8-man tablebases would be economically feasible within 5–10 years, as just 2 PB of disk space would store them in Syzygy format, and they could be generated using existing code on a conventional server with 64 TB of RAM

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

#44

Post by DesiLurker »

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 C/C++ code you dont really need to do mental gymnastics either. I can imagine writing a struct with some clever unions to decode this all in one shot. the main benefit as others have point out is 1) to store large number (think billions) of such game positions & searching through them. Also if you are developing for cloud deployment you probably want to use minimal storage needed for space & egress b/w reasons. last reason is something that may not be obvious but if you have some algos that can run efficiently on gpus then you probably want to lay the data out such that its easy(ier) to load in SIMD engines. overall not a bad idea.

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

#45

Post by jprete »

samwillis wrote: post #8

When I was building my multiplayer Sudoku app, I had fun experimenting with how small I could pack a sudoku grid into a URL. I came up with a scheme combining bit packing with the knowledge of how the grid works. So as you move through the grid, based on the knowledge of what's been placed where and the remaining digits you have a fewer options. Was fun, I was playing code golf with myself. Sadly seem to have lost th…

I think for Sudoku there are a lot fewer legal board configs than there are arrangements of the numbers. There’s probably a way to store the solved state as a single number and then just use 27 bits to specify which numbers are revealed. I don’t know what that single number looks like, though, and you’d have to check that there was only one legal solution to the revealed numbers.

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

#46

Post by about3fitty »

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

Yep, everyone’s happy until the cosmic rays hit

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

#47

Post by WithinReason »

calvinmorrison wrote: post #9
soamv wrote: post #3

A chess position , not a game (still very interesting though!)

Storing the game would give you the position though

It took me a moment to see your point: it might take less information to store the entire game using a chess engine by entropy coding than a single position

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

#48

Post by ThomasCM »

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/Wqa7GiAAAOIpBLoY/developer-update-2...

And shameless plug: Using this encoding, I'm storing millions of games on https://www.chessmonitor.com/ There you can link your Chess.com or Lichess account and view all kind of statistics of your games.

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

#49

Post by r3trohack3r »

zeagle wrote: post #30
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).

Finally, a good use case for blockchain technology!

I can't tell if this is in jest or not but blockchains are prolific in software.

Nearly every company uses them to prove the authenticity of deployments in production at one or more layers.

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

#50

Post by TylerE »

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 possible moves, so to fully encode a knight move you need 6+3=9 bits. 8 also works for pawns (and annoying due to e.p. 4 doesn't). Bishops, queens, and rooks would need a 4/5 bit field. Encode castling as starting from the rook as they have 'spare' moves in their bit set, and kings don't. Encode the end state at the begining.

This is going to use 2 bits for the end state, and then either 9, 10, or 11 bits per move.

Post reply on HN