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 (2022)

ezzeriesa.notion.site

Post reply on HN
Print view View original

81–90 of 108 posts

Re: How to store a chess position in 26 bytes (2022)

#81

Post by 01092026 »

nurettin wrote: post #79
01092026 wrote: post #74

Earlier quoted context omitted.

You're proving my point. Yes, 495 possibilities CAN be stored in 9 bits. But the article shows STRING '00000034' (64 bits) as an example, not the actual 9-bit binary encoding. That's exactly the problem - claiming bit-level compression while showing byte-level examples. And if you look at article, nothing is binary encoded, they are all integer representations all the way down. Please someone show me a BIT implementa…

Yes 9 bits is 2 bytes. The article confusingly says 18 bits = ~2 bytes. It is the "about 2 bytes" that is confusing. They probably mean that an extra bit won't matter too much since we are bit packing the games in a contiguous stream. BUT In the article they don't mean that 00000034 is a bit or a byte. It is one of the possibilities and there are 495 of them and if you index each possibly in a 2 byte integer, you can…

You understand me, this is most important. And thank you for explaining this exercise - but to be honest, if the article says "How to store a chess position in 26 bytes"

And you actually cannot store this in 26 bytes based on your implementation, and then you show integer bits and bytes that aren't even binary...eh.

And to be honest, like how about we store the chess position in 1 bit.

I will execute some chess position program in 1 bit, ON / 1. How about that for ultra compression? Lets just pretend those other random bits and bytes don't exist I mean (...but they do...) - it's stored somewhere else, but "HOW TO STORE A CHESS POSITION IN 1 BIT" - but ok, fine I will play "pretend" |How to store a chess position in 26 bytes (2022)|

You know what I mean? lol

Re: How to store a chess position in 26 bytes (2022)

#82

Post by 01092026 »

nurettin wrote: post #79
01092026 wrote: post #74

Earlier quoted context omitted.

You're proving my point. Yes, 495 possibilities CAN be stored in 9 bits. But the article shows STRING '00000034' (64 bits) as an example, not the actual 9-bit binary encoding. That's exactly the problem - claiming bit-level compression while showing byte-level examples. And if you look at article, nothing is binary encoded, they are all integer representations all the way down. Please someone show me a BIT implementa…

Yes 9 bits is 2 bytes. The article confusingly says 18 bits = ~2 bytes. It is the "about 2 bytes" that is confusing. They probably mean that an extra bit won't matter too much since we are bit packing the games in a contiguous stream. BUT In the article they don't mean that 00000034 is a bit or a byte. It is one of the possibilities and there are 495 of them and if you index each possibly in a 2 byte integer, you can…

[flagged]

Re: How to store a chess position in 26 bytes (2022)

#83

Post by jstanley »

> Since each position takes up 6 bits ($2^6 = 64$), multiplying 6 bits by 32 pieces gives us 192 bits / 24 bytes (1 byte = 8 bits).

But each position can only be used once, so you really only have 64*63*62*61*...*33 possibilities = 64!/32! = ~2^53, so you could encode this with less than 7 bytes, and then use the basic 12-byte encoding for captures, castling, en-passant, and promotions, and you are below 19 bytes in total. (Did I miscalculate this?)

Also pawns can never be on the 1st or 8th rank so you can subtract those possibilities from each of the numbers that represents a pawn.

You also don't care about the order of bishops, rooks, knights, and especially pawns - so you should be able to do even better.

Re: How to store a chess position in 26 bytes (2022)

#84

Post by tromp »

jstanley wrote: post #83

> Since each position takes up 6 bits ($2^6 = 64$), multiplying 6 bits by 32 pieces gives us 192 bits / 24 bytes (1 byte = 8 bits). But each position can only be used once, so you really only have 64*63*62*61*...*33 possibilities = 64!/32! = ~2^53, so you could encode this with less than 7 bytes, and then use the basic 12-byte encoding for captures, castling, en-passant, and promotions, and you are below 19 bytes in…

Multiplying 32 numbers each over 5 bits long obviously results in more than 160 bits. 64!/32! > 2^178.3

Re: How to store a chess position in 26 bytes (2022)

#85

Post by wedog6 »

Dylan16807 wrote: post #70
fallingfrog wrote: post #68

Earlier quoted context omitted.

Sorry I was in the car and read the headline and tried to see how I would do it as an exercise. I actually think I undercounted because for the king and rooks you have to store whether they have been moved yet, and for the pawns whether they just jumped two spaces (so you know if en passant is a valid move). So I wasn't saying the article is wrong, just engaging in a bit of intellectual exercise. My count was: there…

You have a good starting point, but using 6+1 bits is a bad way to encode 65 possibilities. If you use base 65, you'll see that 65^32 possibilities only require one more bit to store than 64^32. And four promotion possibilities wouldn't be 4 bits, it would be 2. But even better is 5^16 squeezing into 38 bits. Combining those cuts your strategy down to 192.7+37.2+4+6 bits which is 30 bytes. The main savings the articl…

Heuristic: (65/64)^64 is extremely close to e. This comes from a classic formula for e as the limit of (1+1/n)^n.

Therefore (65/64)^32 is roughly sqrt(e). Since 1 < e < 4, 1 < sqrt(e) < 2. So 65^32 < 2 * 64^32.

Re: How to store a chess position in 26 bytes (2022)

#86

Post by bonzini »

jstanley wrote: post #83

> Since each position takes up 6 bits ($2^6 = 64$), multiplying 6 bits by 32 pieces gives us 192 bits / 24 bytes (1 byte = 8 bits). But each position can only be used once, so you really only have 64*63*62*61*...*33 possibilities = 64!/32! = ~2^53, so you could encode this with less than 7 bytes, and then use the basic 12-byte encoding for captures, castling, en-passant, and promotions, and you are below 19 bytes in…

(Former) pawns can be on the 1st or 8th rank if they've been promoted. You can place an unpromoted pawn on the 1st or 8th rank to encode en passant, too.

Also castling can be encoded as extra squares available to the rooks only ("queen side never moved" and "king side never moved"), and that is almost free.

But without a good encoding for promotions, I doubt you can beat the encoding of the article.

Re: How to store a chess position in 26 bytes (2022)

#87

Post by jstanley »

tromp wrote: post #84
jstanley wrote: post #83

> Since each position takes up 6 bits ($2^6 = 64$), multiplying 6 bits by 32 pieces gives us 192 bits / 24 bytes (1 byte = 8 bits). But each position can only be used once, so you really only have 64*63*62*61*...*33 possibilities = 64!/32! = ~2^53, so you could encode this with less than 7 bytes, and then use the basic 12-byte encoding for captures, castling, en-passant, and promotions, and you are below 19 bytes in…

Multiplying 32 numbers each over 5 bits long obviously results in more than 160 bits. 64!/32! > 2^178.3

Oops! Thanks, the issue was with DuckDuckGo's calculator which I mistakenly trusted:

https://duckduckgo.com/?q=log(64!%2F32!%2C+2)&t=ffab&ia=calc...

It misinterprets "log(64!/32!, 2)" as "log(((64!) / (32!)) .2, 10)" which seems absurd, why would you use the comma as both an argument separator and a decimal place??

(Why was I using DuckDuckGo as a calculator? I do in fact keep a Casio scientific calculator on my desk, but I recently bought a new one (a Casio fx-991cw) so that I wouldn't have to keep moving the first one between home and work, but the new one doesn't have an obvious factorial function and I gave up looking - it is much worse than my fx-991es in many other ways as well despite looking superficially newer and better, so I can not recommend the fx-991cw).

Re: How to store a chess position in 26 bytes (2022)

#88

Post by leothetechguy »

I remember asking myself this question years ago, and came to 162 bits. I was just a kid back then so the logic is probably wrong but I do wonder how simple the encoding could be under those constraints...

Edit: Here are the Notes

0 Empty

10 Pawn

1100 Knight

1101 Rook

1110 Bishop

1111 Queen

32 + 32 + 472

2 times 6 bits: position of the kings

30 bits: color mask

120 + 2*6 + 30 = 162 bits

We can store the rest using the methods from the blog post and add 18 bits for promotion, giving 180 bits.

I'm sure this isn't the most efficient way, and I think I had other methods and considered things like the bishops being able to occupy 32 squares, though special casing doesn't make sense because of promotions.

Technically if you got 8 bishops/queens/knights/rooks You would occupy another 16 bits, giving 196 bits

I think the upper limit can be reduced at the cost of increasing the lower limit

EDIT2: I think I made the assumption at the time that to promote one piece you needed to capture at least one enemy pawn, giving the space for the two bits, which means the upper bound is actually 180 bits

Would love to see other people try in the comment section

Re: How to store a chess position in 26 bytes (2022)

#89

Post by mrweasel »

jcalvinowens wrote: post #31

I wish these articles acknowledged that densely packed structures like that have significant overhead in terms of the instructions which must be generated to parse them. If that shit gets inlined all over the place, how much bigger is the binary now? Absolute minimalism is rarely the right choice, the size of .text matters too.

That would probably warrant a followup article. I did find myself wondering where the tipping point is between using a slightly less efficient storage method vs. computational overhead.

For example, you technically don't need to track castling availability. If you're storing the entire match as a set of positions, you can deduct that by replaying the previous positions. A quick search seems to indicate that an average chess match runs for about 40 moves, so replaying all previous positions isn't that bad, on average.

If you need to store millions of chess matches, being able to store them in ~1kb each might be more important, compared the overhead of unpacking each state. If you need to query for certain positions across all those matches, maybe less "compression" is desired.

I always enjoy articles about how people store data and how they think of capturing states, but I also like to know the context and how that data is use or queried.

Re: How to store a chess position in 26 bytes (2022)

#90

Post by mrpopo »

leothetechguy wrote: post #88

I remember asking myself this question years ago, and came to 162 bits. I was just a kid back then so the logic is probably wrong but I do wonder how simple the encoding could be under those constraints... Edit: Here are the Notes 0 Empty 10 Pawn 1100 Knight 1101 Rook 1110 Bishop 1111 Queen 32 + 32 + 4 7 2 2 times 6 bits: position of the kings 30 bits: color mask 120 + 2*6 + 30 = 162 bits We can store the rest using…

Considering at least half of all squares are empty, further compression is in order for the empty space.

Also if you're encoding the king as a position instead of a byte sequence you would have to encode their space as empty, that's an extra 2 bits

Post reply on HN