Live data from Hacker News

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

ezzeriesa.notion.site

51–60 of 108 posts

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

#51
post #33
post #22

Earlier quoted context omitted.

If the rook has the king's position, it's never moved. As soon as it moves, it can have any position except the king's.

i think i just misunderstood the writing, it does explicitly say 4bits for castling. the prose around is just describing what castling is - i thought it was implying that you could determine whether castling is possible from the position of the pieces.

It starts off with 4 bits for castling, then optimizes it into a piece swap that takes 0 bits (though the piece swap as written might be flawed).

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

#52
post #43

Earlier quoted context omitted.

+ 3 bits for piece type?

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.

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

#53
post #32
post #9

Earlier quoted context omitted.

Given the current upper bound on legal chess positions is 7.7e45 ≈ 152.4 bits, you either have found a better upper bound or your memory doesn't serve.

Now I'm wondering if it is a "legal" chess position to get the pieces to swap sides ... a solver to find how to do it would be amusing.

Obviously not possible -- how would pawns pass each other without captures?

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

#54

"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…

[deleted]

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

#55

In my head I count 30 bytes, since all 16 pawns can be underpromoted to a bishop rook or knight.

Did you reach 30 by taking a number from the blog and adding to it? The first real size estimate in the post includes promoting to any piece, storing an entire 3 bits per pawn for all 16 pawns. This later gets optimized to 9 bits per side.

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

#56

Why not do it simpler? : Create an array with 16 elements, one element per piece, black + white. Every array element is 7 bits wide, 1 bit for captured or not, and 6 bits for the square number the piece is on (8 x 8). Then you need 16 * 7 = 112 bits = 14 bytes. (And the captured-bit can even be compressed further as a 65th square, but that makes it more calculation intensive to extract a position)

Each side has 16 pieces, so you need 32 elements.

Ah how silly of me, that woud make it 28 bytes. (I had the nagging feeling I was missing something :-) And promotions are also not covered by this...

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

#57
This nerd-sniped me. I think we should separate "chess board" and "chess game state" as two different problems. For "chess board", we don't consider any castling, en-passant or similar. We might store a bit for "who goes next". This is useful for chess puzzles where state shenanigans are rare (I think).

But if we store castling state, I think we are already trying to store the whole game state, and this is representable only by full history because of move repeating rules.

So, I think storing board state as a sequence of moves is more interesting. I would estimate that a number of possible actions on average is closer to 8 than to 16, so it would give as 3 bits for half-move and 6 bits for full move. 24-move game could be represented with 18 bytes, which is considerably lower than 26 bytes!

You can get close to average bit per move, if you reuse "spare" places for the next move. So, for instance, first move have 20 possibilities, which is representable by 5 bits, but you can reuse "spare" 32-20=12 possibilities as a bit for the next move.

This is a representation assuming you use only "move validator" thing that returns a list of possible moves. I think that if you use a chess engine that would output you a probability distribution of possible moves, you can compress noticeably better on average, but decoding would be slow.

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

#58
post #30
post #24

Earlier quoted context omitted.

If the rook has the king's position, it's never moved. As soon as it moves, it can have any position except the king's.

To make this work, the rook can only have the king's position, if neither the king nor that rook have moved.

How do you differentiate between "never moved" and "moved but moved back"?

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

#59
post #58
post #30

Earlier quoted context omitted.

To make this work, the rook can only have the king's position, if neither the king nor that rook have moved.

How do you differentiate between "never moved" and "moved but moved back"?

If the rook has not ever moved yet, it gets the king's positional value. As both pieces can't overlap, assume the king's positional value is correct and the rook is at starting position.

Then, as soon as the rook is moved, it gets its actual positional value. If it moves back later, the positional value will be that of the rook's starting position (guaranteed different from the king's current positional value as the two pieces can't overlap).

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

#60

"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 512 > 495

Post reply on HN