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

141–150 of 204 posts

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

#141

Post by LorenPechtel »

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

Yeah, I was trying to send a chess puzzle to someone on Gameknot.com. White to mate in 1--except there was no black king. (The objective was to mate anyway--find the move that would mate the black king no matter where it was.) Their encoder created the king.

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

#142

Post by jiggawatts »

tylerhou wrote: post #126
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…

This isn't just for chess -- it's practically any knowledge task that you can build expertise in. E.g. take programming. Suppose I sat down an experienced programmer and a novice and gave them the same small (~10-20 line) function to reproduce from memory. If the function is a "reasonably written function" I'm willing to bet that the experienced programmer could reproduce the function with just one or two "peeks" --…

The opposite of this is non-expert customers demanding detailed documentation for common patterns in industry.

“Can you please provide more content to explain what a load balancer does?”

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

#143

Post by SideQuark »

ThomasCM wrote: post #136
gowld wrote: post #114

Earlier quoted context omitted.

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?

Yes, ignoring compression each (half-)move takes up one byte. So if you want to store a sequence of 10 (half-)moves it would take only 10 bytes.

Average game length seems to be around 80 half moves though.

https://chess.stackexchange.com/questions/2506/what-is-the-a...

I'd expect that ordering moves by popularity at each half move index, using say the above dataset, would allow you to select lower indexed values at each step, allowing a nice context based arithmetic compression to really shrink them well.

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

#144

Post by Dylan16807 »

LorenPechtel wrote: post #138
alexb_ wrote: post #132

Earlier quoted context omitted.

I'm actually realizing - you can simply have a case where if a white/black pawn is on the 4th/5th rank, have the next bit be a flag for en passant. This makes all en passant rules stored in 8 bits at max. Since only 1 pawn can be in a status of "en passantable" at a time, we can make it stop assigning a flag bit for future pawns if the answer is ever "yes".

You can have only one en passant situation on the board at once. This means you can use 3 bits to encode the column for en passant, you check the board to evaluate the legality of the solution and discard if it isn't legal (this means you don't have to use a bit to encode whether it's possible as the encoder is guaranteed to be able to pick a column that it's not possible.)

You can have two pawns in the same column in plausible en passant position after pawns cross over via capture.

Of course after a capture you have more bits free, but you need to do something more complex than encoding the column.

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

#145

Post by ThomasCM »

SideQuark wrote: post #143
ThomasCM wrote: post #136

Earlier quoted context omitted.

Yes, ignoring compression each (half-)move takes up one byte. So if you want to store a sequence of 10 (half-)moves it would take only 10 bytes.

Average game length seems to be around 80 half moves though. https://chess.stackexchange.com/questions/2506/what-is-the-a... I'd expect that ordering moves by popularity at each half move index, using say the above dataset, would allow you to select lower indexed values at each step, allowing a nice context based arithmetic compression to really shrink them well.

Yes, in contrast to storing the board (which can be a fixed size), this depends on the length of the game of course.

That said, there are some optimizations you can apply that will compress moves even further (for example the order of the moves as explained in the Lichess blog post is important). In the end it's a tradeoff between (de)serializing the game fast and reducing the size (even more).

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

#146

Post by jiggawatts »

thriftwy wrote: post #125
VyseofArcadia wrote: post #56

Earlier quoted context omitted.

I feel like we have an interesting tragedy of the commons situation of software engineering. On the one hand, storing positions on JSON is quick to implement, easy to understand, easy to read, easy to hack on, and junior engineers and the people who have to deal with your code later will be able to pick it up and run with it easily. On the other hand, when just about everyone is making this same ease-of-use/performan…

You can compress that JSON with a pre-trained dictionary and get a massive discount.

“This Kafka queue collects the zstd-compressed BSON chess messages encoded as base-64 and distributes it to the chess engine VM scale set worker pool for processing… what? Everyone knows chess AIs need large scale and programmer time is expensive! Anyway, the Databricks cluster for move analysis is over here, and…”

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

#147

Post by alexb_ »

Dylan16807 wrote: post #144
LorenPechtel wrote: post #138

Earlier quoted context omitted.

You can have only one en passant situation on the board at once. This means you can use 3 bits to encode the column for en passant, you check the board to evaluate the legality of the solution and discard if it isn't legal (this means you don't have to use a bit to encode whether it's possible as the encoder is guaranteed to be able to pick a column that it's not possible.)

You can have two pawns in the same column in plausible en passant position after pawns cross over via capture. Of course after a capture you have more bits free, but you need to do something more complex than encoding the column.

That's just not true. Pawns can only be captured en passant on one rank for each color.

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

#148

Post by jiggawatts »

People have pointed out that due to rules about no repeats, the full state requires storing previous moves.

I’m fairly convinced that the most efficient encoding would be keeping only the move history and then playing that forward to obtain the board state.

E.g.: there are only 32 distinct pieces so a 5-bit number can select one uniquely. Each piece has a maximum of about 32 positions it can move to. Then the encoding is just 10 bits per ply. Typical games are 40 moves (80 ply) and hence require just 800 bits or 100 bytes for the whole game history.

Then you could get clever with Huffman coding or the like, since some moves are more common than others.

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

#149

Post by Dylan16807 »

alexb_ wrote: post #147
Dylan16807 wrote: post #144

Earlier quoted context omitted.

You can have two pawns in the same column in plausible en passant position after pawns cross over via capture. Of course after a capture you have more bits free, but you need to do something more complex than encoding the column.

That's just not true. Pawns can only be captured en passant on one rank for each color.

Yes for each color. That means two pawns for each column can be in position to be captured en passant. And also two pawns can be in capturing position.

Edit: Column combined with whose turn it is will work, but not just column.

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

#150

Post by hinkley »

kpozin wrote: post #121
hinkley wrote: post #111

Earlier quoted context omitted.

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.

If you have the entire move history, then you probably don't need to store partial board positions.

Of course it depends on what you're doing with the information. If you're compressing it in order to sort 100 million board positions for a minmax algorithm, it might make sense to use a representation that makes queries cheaper at the cost of size.

If instead you're trying to store every competition chess game in history, then it depends on what you're trying to do with them. Look for similar board positions?

If you're trying to allow inmates in a Dumas-inspired prison secretly play chess against each other over a covert channel, then detection is the problem. Which might mean compression (fewer signals to hear) or masking the signal as random noise.

Post reply on HN