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

71–80 of 108 posts

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

#71

Post by nvader »

efitz wrote: post #23

There's a logic error from assuming that because the rook is in its original position that the rook has not moved. Also I'm not sure if en passant is available if the pawn has moved from its home file, even if it subsequently moved back - so you can't assume either of these just by looking at the piece's position. I think that you need one extra bit, that can contextually encode "rook has moved" or "en passant availa…

At the start of the game, qRook - king - kRook all store the location e1.

If the king moves (say we're playing the Bongcloud), qR and kR get set back to their original squares, a1 and h1. Now if the King slides back, castling is off the board.

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

#72

Post by fallingfrog »

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…

Yes, I made a few mistakes and I did realize I didn't need the whole extra bit to store 65 possible locations- I just was being a bit lazy. Ba dum tiss.

Hmm as a bit field followed by piece order- that would be 8 bytes followed by a variable number of pieces, perhaps you could do a sort of compression where 0c means pawn and 1xxxc is any other piece. (c stands for a color bit). So thats another 14 bytes. Thats 22 bytes!

The xxx by the way is one of 8 things: k, k not moved, r, r not moved, n, b, q, en passant pawn

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

#73

Post by Dylan16807 »

fallingfrog wrote: post #72
Dylan16807 wrote: post #70

Earlier quoted context omitted.

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…

Yes, I made a few mistakes and I did realize I didn't need the whole extra bit to store 65 possible locations- I just was being a bit lazy. Ba dum tiss. Hmm as a bit field followed by piece order- that would be 8 bytes followed by a variable number of pieces, perhaps you could do a sort of compression where 0c means pawn and 1xxxc is any other piece. (c stands for a color bit). So thats another 14 bytes. Thats 22 byt…

From the previous HN discussion, 00c for pawn and xxxc for other pieces is probably the optimal way to encode pieces into whole bits. Because you can sacrifice 1 pawn to enable 3 promotions, so you need to handle up to 28 non-pawns. With 2/5 you start at 14 bytes but can need up to 17.5. With 3/4 you start at 14 bytes and never need more than 14.

With 6 xxx states instead of 8, you can merge "king not moved", "rook not moved", and "en passant pawn" into a single state since those can never overlap. (Though if you're encoding one pawn the long way that means you need 14.125 bytes, oh well.)

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

#74

Post by 01092026 »

vntok wrote: post #60
01092026 wrote: post #46

"The 'bit-level magic' here is misleading. They're using integer representations and calling them bits. A true bit-level approach would encode positions as pure binary streams. For example, their promotion string '00000034' is 8 bytes (64 bits), not the claimed 9 bits. Has anyone implemented this with actual bitwise operations instead of integer packing? TLDR: You stupi...lovely folks, need learn what a bit is. What…

Your mental model is wrong. Read the post again, slowly, and it will probably make more sense to you. Here are the relevant bits > This gives us the string `00000034` to uniquely represent this specific set of promotions, without information loss. > How many possible strings are there? Generating this by brute force, we end up with 495 distinct strings > This can be stored in 9 bits for each side Hint: 2^9 is 512 and…

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 implementation of this - THESE ARE BITS 0 1 0 1 1 0 - It's called BINARY. There are no 9, or 5, or 3 or 4.....That isn't how logic gates work.

A 3 / INT is 8 BITS...1 BYTE.

HINT: I'm right.

And you never answered my question:

"Has anyone implemented this with actual bitwise operations instead of integer packing?"

Still waiting to see these "9-bit" "bytes"."00000034".

Again, show me. There is no such thing as a 9-bit byte, that isn't how CPUs or computation work. ITS 8 BITS 1 BYTE, that is transistor / gate design architecture.

This is how computers work.

If you have 9 bits, you have 2 BYTES!!!!!

BYTE 1: 00100011 (8 bits) BYTE 2: 10000000 (9th - 7 wasted bits)

= 16 bits, 2 BYTES THANK YOU GOODBYEEEEEEEEE

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

#75

Post by nurettin »

btilly wrote: post #15

Either we have to say that the position does not dictate the possible moves, or that this does not fully capture the position. The problem here is that drawing can become an option or a requirement based on information that this representation doesn't capture. First the simpler version of this problem. After 50 full moves without a capture or pawn move, a draw MAY be claimed. After 75 moves, a draw MUST be claimed. T…

> third time, then a draw MAY be claimed. If it repeats exactly for a fifth time, then a draw MUST be claimed

Wow I don't know any online or offline platform which draws on five fold repetition. Didn't know that was a thing at all!

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

#76

Post by nurettin »

Scarblac wrote: post #52
addaon wrote: post #43

Earlier quoted context omitted.

You only need the piece type for pawns (that can be upgraded), and a bit on the king to track if castling is possible; otherwise a single bit for on-board/captured is sufficient, since the types of the other pieces are implicit in the array index. (You can shave single bits in a few places -- if the state represents a game in progress the king-captured bit isn't needed; natural bishops only need 5 bits for position o…

Two bits on the king for castling, queenside and kingside.

Why not just one bit "castled"?

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

#77

Post by kazinator »

I would do it like this. There are 32 pieces, any of which may be missing. So let's use four bytes (32 bits) as a mask of what pieces are present. Then, coordinates can be given for each piece that is present. The board is 8x8, so coordinates can be encoded as pairs of 3 bits, e.g. A3 is 000:011. The worst case is that we need 32 of these pairs, which requires 24 bytes. That brings us to a worst case of 28.

How can we eliminate two bytes?

We can more cleverly encode the mask so that two bytes are used to express the all-pieces-present, and certain other cases. A fully decoded mask is only used for boards that have too few pieces to break over 26 bytes.

For instance suppose we have a two-bit header encoding several cases:

00 - no piece are missing (32 six-bit coordinates follow)

01 - one piece is missing, followed by 5 bit ID of that piece

10 - two pieces are missing, followed by two 5 bit IDs of the two pieces

11 - three or more pieces missing, full mask follows.

In case 11, we need a 32 bit mask, followed by as many as 29 coordinate pairs.

So 2 + 32 + 6 * 29 = 208 bits.

And hey look, by dumb luck, 208 / 8 = 26.

I will check the article later.

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

#78

Post by jfaat »

I have a lot more to optimize before I'm crunching down the positions but I just made a chess platform[0] with the intention of tracking your play style over many games (integrated with chess.com only for now) because the other ones I've used (including chess.com somehow) only really analyze a game at a time. It was a lot of fun to build and it's been really useful for me to identify some weaknesses and have a 'coach' to talk through them with and replay positions. I'd love feedback from any chess players! (email is in my bio)

[0] https://chessfiend.com

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

#79

Post by nurettin »

01092026 wrote: post #74
vntok wrote: post #60

Earlier quoted context omitted.

Your mental model is wrong. Read the post again, slowly, and it will probably make more sense to you. Here are the relevant bits > This gives us the string `00000034` to uniquely represent this specific set of promotions, without information loss. > How many possible strings are there? Generating this by brute force, we end up with 495 distinct strings > This can be stored in 9 bits for each side Hint: 2^9 is 512 and…

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 decode it back to that string and get a representation of the promotions that happened in any game.

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

#80

Post by toast0 »

nurettin wrote: post #76
Scarblac wrote: post #52

Earlier quoted context omitted.

Two bits on the king for castling, queenside and kingside.

Why not just one bit "castled"?

You can only castle if neither the king nor the rook have been moved (and none of the three squares the king uses may be under attack, and all the squares between the rook and the king must be empty).

Since you could move either rook somewhere and then back to their starting squares, you have to track their eligibility separately. If the king moves, both rooks lose eligibility.

Post reply on HN