101–110 of 204 posts
What about bishops? The bishops are limited to half the board so only need 5 bits for position. This frees up 4 bits, but you lose the capture state (can't use King's position for capture state). Well, you CAN use the king's position for capture state for two of the bishops at any given time. Then for the other two bishops use a bit to store their capture state. This saves 2 bits overall, bringing the total down to e…
For what it's worth, this definitely isn't the theoretical limit for compressing a chess board position, which I would probably resort to calculating mathematically. In particular, (simplifying to boards with no pieces captured) this scheme uses 24 bytes for representing piece positions, but the constraint that no two pieces are in the same square means you should actually need only log2(64!/32!) = 22.3 bytes for tha…
The upper bound on the number of legal chess positions given in https://en.wikipedia.org/wiki/Shannon_number is 8.7 * 10^45, which gives a lower bound of ln(8.7 * 10^45) = ~106 bits or 14 bytes.
I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…
As the article discusses, there's a bit more than that to store in a position. Specifically you have to store whether or not castling is available for the two sides and also whether any pawns are en passant targets, since both of those moves are available (or not) conditionally in a given position based on previous moves in the game.
0 - empty (1*32=32)
10y - pawn (color) (3*16=48)
11xxxy - piece (color) (6*16=96)
one of the extra 3 non-pawn piece values can be used to encode 'rook (castling unavailable)' without spending extra bits. a scheme for storing en passant without any additional bits is less clear (but doing it with 3 extra bits is, so 22.375 bytes for positions that would regularly be reached in play).
I think it COULD increase in at least one specific circumstances: two promoted pawns (+6 bits total) with only 1 taken pawn (-3 bits). I think the maximum is 12 promoted pawns and 4 taken pawns which would make some hypothetical board take 204 bits (25.5 bytes) in this encoding.
A static arithmetic encoding (rather than a huffman encoding) of the same values should take a hair less space.
Storing a chess position in 26 bytes. Storing a game is also interesting. The number of legal moves varies depending on the position. You could try to define a variable length encoding by giving more likely moves a shorter encoding, but the ordering would need to be deterministic so it could be decoded (running Stockfish for a second isn't).
Surprisingly, storing a game (with all moves) can take less space than encoding a single board. This is because you can effectively encode a move in a single byte (as there are less than 255 moves possible in each position). Applying compression to the resulting binary string will allow you to reduce the space even more. Check out this great blog post of Lichess for more information: https://lichess.org/blog/Wqa7GiAA…
ChessMonitor is practically a work of art!
I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…
To cut 2 bytes off (while making it much less elegant), huffman coding could be used to store pawns in 3 bits - to guarantee a space reduction, this relies on the fact that if there are n promoted pawns, there must have been at least ceil(n/3) captures, freeing up space for the longer representation of promoted pawns. It is necessary to find another way to represent en-passant opportunities (swap an en-passantable pa…
Can you explain this in more detail? Curious as to how you could save space with this.
Earlier quoted context omitted.
The upper bound on the number of legal chess positions given in https://en.wikipedia.org/wiki/Shannon_number is 8.7 * 10^45, which gives a lower bound of ln(8.7 * 10^45) = ~106 bits or 14 bytes.
You need the 2-logarithm rather than the natural logarithm. That gives ~ 152.6 bits, or ~ 19.1 bytes.
Earlier quoted context omitted.
Most games could possibly be encoded in less than 26 bytes. There are not that many legal moves each time and if you sort them by probability it may not require many bits to describe which one the players chose.
I doubt it. You could maybe get as low as 1 bit per move, but how many games are only 26 moves? Would be interesting to find out though! Maybe this paper says. I didn't read it. https://www.researchgate.net/figure/Entropy-and-distribution...
Earlier quoted context omitted.
To cut 2 bytes off (while making it much less elegant), huffman coding could be used to store pawns in 3 bits - to guarantee a space reduction, this relies on the fact that if there are n promoted pawns, there must have been at least ceil(n/3) captures, freeing up space for the longer representation of promoted pawns. It is necessary to find another way to represent en-passant opportunities (swap an en-passantable pa…
> To cut 2 bytes off (while making it much less elegant), huffman coding could be used to store pawns in 3 bits - to guarantee a space reduction, this relies on the fact that if there are n promoted pawns, there must have been at least ceil(n/3) captures, freeing up space for the longer representation of promoted pawns. Can you explain this in more detail? Curious as to how you could save space with this.
Here's a good example image for huffman coding: https://i.ytimg.com/vi/hOabRMHzpo8/hqdefault.jpg
So before any captures are made, you have 32 pieces, half of which use 3 bits and half of which use 4 bits. 14 bytes, plus the 8 bytes storing the bitboard.
When you promote a piece it goes up in size from 3 to 4 bits, but you can guarantee there have been enough captures to offset that, so you never need more space than you started with.
Earlier quoted context omitted.
Most games could possibly be encoded in less than 26 bytes. There are not that many legal moves each time and if you sort them by probability it may not require many bits to describe which one the players chose.
A Huffman code ...? The starting board is 0, 1.e4 is 1, etc...
(That was the article I expected from the malformed title here: a combination of an efficient encoding and it can it can only get longer than this by repetition so here's a very clever thing we can do, or something.)
