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.
How to store a chess position in 26 bytes (2022)
51–60 of 108 posts
Re: How to store a chess position in 26 bytes (2022)
#52Earlier 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…
Re: How to store a chess position in 26 bytes (2022)
#53Earlier 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.
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…
Re: How to store a chess position in 26 bytes (2022)
#55In my head I count 30 bytes, since all 16 pawns can be underpromoted to a bishop rook or knight.
Re: How to store a chess position in 26 bytes (2022)
#56Why 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.
Re: How to store a chess position in 26 bytes (2022)
#57But 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)
#58Earlier 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.
Re: How to store a chess position in 26 bytes (2022)
#59Earlier 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"?
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…
> 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