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.
And shameless plug: Using this encoding, I'm storing millions of games on https://www.chessmonitor.com/ There you can link your Chess.com or Lichess account and view all kind of statistics of your games.
That is a beautifully designed website. I don't think I've ever used an OAuth authentication flow as smooth as the one that your site uses to access my Lichess credentials (same as my HN name, btw, in case you want to beat me at a correspondence game).
Heh, I guess there are board states that are not possible to reach through a valid sequence of moves, but I guess otherwise it's not possible that games are more compressable by definition, since any valid board state could be represented as a sequence of moves.
This does raise the question of the efficiency of reverse engineering a series of minimal moves for some board state.
Are you saying that, to encode a valid position, ignoring the cost to encode both the starting position and the move definitions, you can encode the move sequence using less information than encoding a single position?
I'd expect that ordering moves by popularity at each half move index, using say the above dataset, would allow you to select lower indexed values at each step, allowing a nice context based arithmetic compression to really shrink them well.
Yes, in contrast to storing the board (which can be a fixed size), this depends on the length of the game of course.
That said, there are some optimizations you can apply that will compress moves even further (for example the order of the moves as explained in the Lichess blog post is important). In the end it's a tradeoff between (de)serializing the game fast and reducing the size (even more).
It seems, then, if you wanted to efficiently store lots of positions, it would be smart to store a large list of openings, a large list of following sequences, and then your positions can be stored as a list of sequence ids.
That suggestion seems very reminiscent of the notion that optimally compressing wikipedia is the same problem as what generative LLMs are doing, by virtue of predicting the next letter/word/segment with high precision lets you compress it extremely well.
I think for chess you could get most of the benefit with a relatively naive engine; chessbase has a weak engine built in where you can hit space bar and it does a move which is incredibly useful since there's just one obvious move for a lot of positions anyway; if the move was especially tricky/nonobvious than it's also not what you would want when hitting spacebar to just predictably proceed anyway).
I suspect it would be hard to beat pgn run through a good compression algorithmn.
Or similarly essentially a binary version of pgn. Probably the optimalist of optimal is a binary specifying the starting square (6 bits), and then a minimal-width for the specified piece number that indexes against a standard set of move offsets.
So, for instance, a knight has (ignoring potential exposed checks, board boundaries, etc, 8 possible moves, so to fully encode a knight move you need 6+3=9 bits. 8 also works for pawns (and annoying due to e.p. 4 doesn't). Bishops, queens, and rooks would need a 4/5 bit field. Encode castling as starting from the rook as they have 'spare' moves in their bit set, and kings don't. Encode the end state at the begining.
This is going to use 2 bits for the end state, and then either 9, 10, or 11 bits per move.
> Bishops, queens, and rooks would need a 4/5 bit field.
Ignoring board boundaries, a queen has 56 possible moves requiring 6 bits. At any given position on the board, most of those aren't possible because the board is too small, but cramming that into 5 bits will make the encoding much more annoying.
Same thing goes for rooks; ignoring board boundaries there are 28 possible moves, but including the board boundaries there are 14. You can fit that in four bits, but you pick up some context sensitivity.
> 8 also works for pawns (and annoying due to e.p. 4 doesn't)
I don't see the problem? A pawn can move forward two spaces, it can move forward one space, it can capture diagonally to the left, or it can capture diagonally to the right. Those are the only possibilities and they fit into two bits.
En passant enables a pawn to capture a piece that isn't located on the space being captured, and you need to know the state of the board on the previous turn (or, equivalently, what the previous move was) in order to know whether en passant is a legal move... but to encode that it happened, you don't need anything you didn't already have.
You only need 5b to encode the piece to move: you know whose turn it is. Also, as the game progresses, you can reindex to reduce the number of bits to define which piece is moving.
> You only need 5b to encode the piece to move: you know whose turn it is.
If you want to encode the piece (rather than the square), and you're comfortable not counting "whose turn is it?" against the information requirement, you don't need 5 bits. Each player has only 16 pieces, so you can give them all four-bit names.
You won't know what kind of piece they are, though.
A standard archiver like 7zip is probably a loss due to the metadata/format headers etc. When your plain text is only a few hundred bytes to start with...
I suspect the winner would be something like an LZMA derivative with a fixed dictionary. I doubt not using an adaptive encoder would be a big loss as PGN (exlcuding the metadata) is quite far from random bytes.
It was in jest because blockchain is a solution looking for a problem, but as others have pointed out what you say isn't really the case. I'm glad it generated some discussion. Hashing previous steps for verification isn't blockchain.
IIUC a blockchain is a structure where each node has a content addressable hash that includes the hash of the previous node in the chain. If you change any historical node, every subsequent hash is updated.
This structure is used inside your .git directory, your docker manifest, etc.
That's a Merkle tree. Blockchains are a Merkle tree plus some form of consensus algorithm, often a trustless one. It's the usefulness of the consensus algorithm which is usually called into question by critics (generally because it's often expensive and cannot reference anything outside the system).
IIUC a merkle tree is a data structure where the leaf nodes are the hashes of data. The inner nodes of the tree are hashes of the child hashes up to a root hash.
Merkle trees are helpful for quickly validating the integrity of a chunked file. Both IPFS and BitTorrent use merkle trees to validate files.
I do not understand how git could represent its history using a merkle tree.
git commits themselves are merkle trees (or more like, DAGs) that contain filesystem trees, a set of parent commits, and metadata
each parent commit in turn contains their own parents etc, until you reach an initial commit
the funny thing here is that parent commits don't have references to children, it's children that have references to parents (like the union find data structure) so the relationship here is inverted. that's because git objects are immutable
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 there are less than 16 bits set in the bitboard, ignore the last items in the list.
0000 - 0x0 - black pawn
0001 - 0x1 - black pawn (can be en-passant'd)
0010 - 0x2 - black knight
0011 - 0x3 - black bishop
0100 - 0x4 - black rook (castling unavailable)
0101 - 0x5 - black rook (castling available)
0110 - 0x6 - black king
0111 - 0x7 - black queen
1000 - 0x8 - white pawn
1001 - 0x9 - white pawn (can be en-passant'd)
1010 - 0xA - white knight
1011 - 0xB - white bishop
1100 - 0xC - white rook (castling unavailable)
1101 - 0xD - white rook (castling available)
1110 - 0xE - white king
1111 - 0xF - white queen
I think that covers all possibilities to store a chess position in 64 + 32 * 4 = 192 bits, or 24 bytes exactly.
The starting position would be represented with a bitboard of 0xFFFF00000000FFFF, with a list of [0xD, 0xA, 0xB, 0xF, 0xE, 0xB, 0xA, 0xD, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x5, 0x2, 0x3, 0x7, 0x6, 0x3, 0x2, 0x5], using the same position-to-number scheme in the blog post
Edit: 32 pieces, not 16. Thanks to the peanut gallery for catching it quickly
Edit2: To store which player is next: do nothing for white. For black, if there are 32 pieces, flip the bitboard upside down. (To check if it's black's turn, verify that black pawns are "below" white pawns, which is illegal before captures are made.) If there are less than 32 pieces and it's black's turn, invert the bitboard. (To check, count the number of set bits.) This is entirely taken from https://news.ycombinator.com/item?id=37526484
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 pawn with the piece in the 1st or last rank as mentioned https://news.ycombinator.com/item?id=37526523 ).
2 rook representations aren't needed (encode a king with castling opportunities as a knight, bishop or rook, and when decoding, if there are no kings of a given color, look at the piece in the king's starting position) so another 4 bits could be saved by making rook, bishop or knight representations shorter.
A Huffman code like this can also represent knights (or any single other piece) in 3 bits.
000 - black pawn
001 - black knight
0100 - black bishop
0101 - black rook
0110 - black king
0111 - black queen
100 - white pawn
101 - white knight
1100 - white bishop
1101 - white rook
1110 - white king
1111 - white queen
Going with "a pawn in the first row is actually en-passantable, and should be swapped with the piece in the appropriate position if it exists", and "kings are represented as knights when they can castle in either direction, bishops when they can only castle kingside, and rooks when they can only castle queenside", that gets the initial representation down to 64 + 16 * 3 (pawns) + 6 * 3 (knights and kings) + 10 * 4 = 170 bits, with a worst case of 172 bits (when kings lose some castling rights), if I understand it correctly.
Huffman encoding for 21.5 bytes seems to win the day.
> 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.
You read the piece data bit by bit. If you see 100 or 000 then you stop right there. You have a pawn, and the next piece starts with the next bit. There's no ambiguity.
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.
I see - so you can use the bits you saved by not having separate rook pieces to denote En Passant pawns.
I like the "no kings" idea for castleable kings - though I think with smaller pawn sizes, that gives another opportunity for compression:
- king that can't castle: king
- king that can castle queenside: any other piece in king's position, no king of that color on board
- king that can castle kingside: black pawn on 1st or 8th rank
- king that can castle: white pawn on 1st or 8th rank
Because you are often going to have positions where the king can castle kingside and positions where the king can castle either way, this should maximize how often you manage to save space w/ the pawns.
Another thought I had (which might contain other problems, not sure yet) is to use pawns on the 1st or 8th rank to denote pieces which are in their starting position - the decompression algorithm can then derive what piece it is based on the known starting position. Once we start having data saving because of pawns taking less bits, we want to be able to use them as much as possible to save space.
> I see - so you can use the bits you saved by not having separate rook pieces to denote En Passant pawns.
You could do it that way, but the particular comment was suggesting two entirely separate ways to save bits, one for pawns and one for rooks.
Specifically, the suggestion in that post is to use 1st/8th rank to show en passant, and to show castling by replacing an unmoved king with a different piece. But there's lots of ways to cleverly encode that information.
For what piece to replace the unmoved king with, you can actually use both white AND black pieces, since the starting rank can decode what color the king is:
- White Knight on E1 and no king: Replace with white king that can castle both ways, E4 pawn can be taken En Passant
- White Bishop on E1 and no king: Replace with white king that can castle kingside, E4 pawn can be taken En Passant
- White Rook on E1 and no king: Replace with white king that can castle queenside, E4 pawn can be taken En Passant
- Black Knight on E1 and no king: Replace with white king that can castle both ways, E4 pawn cannot be taken En Passant
- Black Bishop on E1 and no king: Replace with white king that can castle kingside, E4 pawn cannot be taken En Passant
- Black Rook on E1 and no king: Replace with white king that can castle queenside, E4 pawn cannot be taken En Passant
It's the same for E8, just put a black king and not a white king. Sorry if this is repetitive, I could have probably just explained it and let you figure it out, but I put the cases down here for clarity. This should also be combined with the Knight huffman encoding that was talked about here https://news.ycombinator.com/item?id=37527350
I'm actually realizing - you can simply have a case where if a white/black pawn is on the 4th/5th rank, have the next bit be a flag for en passant. This makes all en passant rules stored in 8 bits at max. Since only 1 pawn can be in a status of "en passantable" at a time, we can make it stop assigning a flag bit for future pawns if the answer is ever "yes".
You can have only one en passant situation on the board at once. This means you can use 3 bits to encode the column for en passant, you check the board to evaluate the legality of the solution and discard if it isn't legal (this means you don't have to use a bit to encode whether it's possible as the encoder is guaranteed to be able to pick a column that it's not possible.)
I think we are both wrong. En passant only exists for one move, whatever has happened from captures is irrelevant. However, now I realize you can have two possible en passant captures at once--a pawn moves to 4th rank between two opposing pawns on the 4th rank.
Yes for each color. That means two pawns for each column can be in position to be captured en passant. And also two pawns can be in capturing position.
Edit: Column combined with whose turn it is will work, but not just column.
8 flag bits is a lot though when we're trying to shave down 20-ish bytes! And we're only worried about the worst case scenario, so assume it's the last pawn in the list. Also you can have at least 10 pawns visibly at risk of en passant at once. If you base it on rank alone, you can have all 16 pawns in position at the same time, wasting 16 bits.
If you're going to explicitly store it, at least squeeze down to 4 bits to pick a specific pawn (and picking one visibly not at risk if no pawn is at risk).
But using clever piece rearrangements is a lot better than spending flag bits.
Nice! Though there are max 32 pieces on a board, not 16; so this scheme is 64 + 32 * 4 = 192 bits, or 24 bytes.
The bit to indicate whose turn it is isn't accounted for here. But it probably could probably represented by the binary negation of the bitboard -- if there are 32 or fewer bits set, then it is white's turn; if there are 33 or more bits set, then it is black's turn and you can negate the bitboard prior to determining which squares are occupied.
Taking things further, it probably can be compressed even more with (much) more complex logic, as the castling available bit must only be present on the corner positions, and the pawn en-passant capabilities are only available on the middle rows, so those bits are meaningless in other positions.
I like the bitboard inversion idea. (Requires flipping logic as well from https://news.ycombinator.com/item?id=37526484, since 32 is a special case.) Note that the en-passantable pawns and castle-able rooks came from options that were unused in my first pass (linked comment). I could use 0x1 as "castleable rook or en-passantable pawn, determined from where it is" and then store 32 integers with 13 options in 119 bits[1], saving 9 bits. But I'm kinda attached to the simplicity here.
(The 16->32 was edited as you wrote this comment.)
> if there are 32 or fewer bits set, then it is white's turn; if there are 33 or more bits set, then it is black's turn and you can negate the bitboard prior to determining which squares are occupied.
This doesn't quite work because if there are exactly 32 bits set, inverting it leaves 32 bits set. You could fix this by marking all pawns belonging to the player who's turn it is as capturable via en-passant (if a player has no pawns left, at least 1 piece has been captured, so inverting the bitboard works).
You can use duplicate king identifiers to represent castling available, and replace the extra rook identifiers with "black king (my turn)" and "white king (my turn)" to store the turn in the same amount of space.
edit: You can then use the inverted/flipped board trick to store one bit of your piece list, down to 191 bits.
edit2: You only need one "king (my turn)" ID, which represents the whichever color you didn't use for the other king. You can use the extra value for another "my turn" piece that also sets a bit. 190 bits!
I rhink the concept is: in the initial position you have three kings: in a1, e1 and h1. Once the left rook is moved, it will be encoded as rook and not as a king anymore. Same for the right one. If you move the king, both rooks will be encoded as rooks and not as king anymore.
Decoding is easy: if there's more than one king, one must be in e1: that's the real one, the others are actually rooks.
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.
I don’t think that’s true. Or rather, it’s only true for storing board position not for storing the move history. If you have the entire move history you know that status of each piece.
Of course it depends on what you're doing with the information. If you're compressing it in order to sort 100 million board positions for a minmax algorithm, it might make sense to use a representation that makes queries cheaper at the cost of size.
If instead you're trying to store every competition chess game in history, then it depends on what you're trying to do with them. Look for similar board positions?
If you're trying to allow inmates in a Dumas-inspired prison secretly play chess against each other over a covert channel, then detection is the problem. Which might mean compression (fewer signals to hear) or masking the signal as random noise.
My thought was to have additional schemes depending on the length of the byte array. For example, if the position is an empty array it is the beginning position, if it is 1 byte it represents the most common positions.
"" is the beginning position
"0" is E4
"1" is D4
"2" is C4
"3" is E4 E5
"4" is D4 D5
"5" is G3
One could do a multi byte version where the order of popular positions is replaced with a crappy chess computer.
If there is no en-passant, no promoted pawn and castling is allowed you can use representations slightly shorter than 24.
OP here. I'm not sure how I overlooked this comment earlier, but this is elegant and it works! It's amazing how you need exactly 4 bits for each bit. Thank you for sharing!
* If there are less than 32 bits set in the bitboard, the item list is shorter (rather than ignored).
* Probably not worth it, but: When there are 32 bits set on the bitboard, stop processing the bit-board.. however, if you adjusted the ordering of the lines (0,7,1,2,...), it's optimised for the first 1 or 2 positions
* Maybe this is cheating, but if the size of the game data will be known ahead of processing, then you could leave off the last item in the list if it's a king or a rook
* Starting the item list with 2 white kings can be a special case for "starting position", and if the items are listed before the board then only 1 byte is needed :)
There's a simple trick to encode it: if there are less than 32 pieces, invert the bitboard (easily decoded since boards can't have more than 32), while if there are 32 pieces flip the board vertically (easily decoded because white pawns can't be after black pawns with no captures).
There are two more things that should be considered.
Both of them unlikely to influence a position, but they can matter - just like the en passant target.
The fifty move rule[0] is quite simple, just store a number, fits in five bits. But the threefold repetition rule[1] is quite a pickle - it basically means that to know everything about a position you need to know every position that occurred before it.
Yeah, it seems like the author is storing more information than just the position but not enough to figure out all of the possible next states of the game.
Another straightforward thing missing is the player's turn; this could determine whether the position is a stalemate or not.
Fair enough. Still up to 50 board states that can influence the current one (the 50 move rule is coming to help here)
FEN doesn't store previous states, but EPD can. It just goes to show how meanings and requirements change depending on context, which is super interesting in and of itself :P
Also, database software gets so clever with storing games that they often can't save games that have illegal moves in them. But there are plenty real games from real tournaments that had illegal moves in them that nobody noticed...
Yeah, I was trying to send a chess puzzle to someone on Gameknot.com. White to mate in 1--except there was no black king. (The objective was to mate anyway--find the move that would mate the black king no matter where it was.) Their encoder created the king.
No black king--in other words, you don't know where the black king is since it must exist. The puzzle was to find the move that would mate the king no matter what square it was in.
That's a very good point. Similar issues affect file systems that has to store files with invalid filenames and parsers that have to gracefully handle invalid parse trees.
You can’t repeat the last position. But repeating a pattern of part of the board every two turns can force progress to resolution. The entire board never repeats, but it also stops the loop earlier.
An interesting cognitive phenomenon: if you ask chess experts and novices to memorize and recall an arbitrary chessboard, the experts are significantly better than the novices _only if_ the board is a legal board that can be arrived at during play. If it is not a legal board, there's no particular difference between novices and experts. Original ref: Chase & Simon 1973, Perception in Chess.
This is usually taken to mean that the brains (or whatever) of experts see structure that can be used for compression that novices don't, but that compression has assumed invariants you cannot break.
This isn't just for chess -- it's practically any knowledge task that you can build expertise in.
E.g. take programming. Suppose I sat down an experienced programmer and a novice and gave them the same small (~10-20 line) function to reproduce from memory. If the function is a "reasonably written function" I'm willing to bet that the experienced programmer could reproduce the function with just one or two "peeks" -- once you have enough experience, you can better recognize patterns / chunk your knowledge. A novice doesn't have this ability, so it would likely take them many more peeks.
On the other hand, if the function is some random gibberish with little structure, you could imagine that it's probably equally difficult for both the experienced programmer and the novice to reproduce the function from memory.
For chess, one reason why masters can better recall positions is because they know what typical positions look like (e.g. a position typical of the "London" opening). Then, they only need to store a "diff" of the given position and a typical position. ("It's a typical London setup for White, except White also played a3 and b4.") A novice doesn't have this knowledge, so they have to store the whole position.
Not a "legal" board, but a typical board. Both this and the original de Groot study picked positions from real games played by strong players. Experts don't do retrograde analysis on the positions, but they do recognise typical patterns that often occur in real play.
It's not really about whether it's legal, but whether it looks normal. Very bizarre positions can easily be legal, but they're hard to remember for everyone.
I’ve heard this corroborated by exhibition players who play ten or fifteen opponents at once. They do better with moderately skilled opponents than random people.
I don't know what you mean with "exhibition" precisely; I'd expect that to be true for blindfold chess (where you have to keep all the games in memory the whole time), but not for normal simultaneous as the strong player hardly has to think to find moves good enough to beat random players.
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 that case, with 13 bits of savings. The scheme proposed here reclaims some of that overhead by granting special meaning when a piece's location overlaps with the king, but still is capable of representing other illegal positions where non-king pieces occupy the same square.
Unfortunately, decoding a mathematically optimal encoding quickly devolves to making a list of all possible board configurations and indexing into it, so I'd definitely believe that the proposal here is close to the smallest practically useful representation.
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.
> Recent results improve that estimate, by proving an upper bound of 8.7x10^45, and showing an upper bound 4×10^37 in the absence of promotions. - Wikipedia (link above)
You can save 28 bits!... Use log2(4e37) = 124.9 bits for games without piece promotions. Then switch to log2(8.7e45) = 152.6 bits for games with them.
Couldn't you make it practical by assuming all possible positions (64) for the first piece, then 63 for the second, and so on, and encode one piece at a time? (Arithmetic coding piece by piece)
1. You'd definitely want to deduplicate positions of identical pieces for even more savings
2. That only handles the case where no pieces have been captured, and the full arithmetic coding would probably need separate "sections" of the integer range for different cases, and the number of sections is also quite high.
3. There's extra nuanced things you might want to handle in the coding, like that pawns can't be on their own back row. That is significantly harder.
But the major point of this project is to allow for random sampling of positions with a decent likelihood of getting a legal one, which allows for accurate estimation of the number of legal positions.
I consider any reduction past the cache-line size (32B) to have diminishing returns as far as processing is concerned. unless of course if you can fit 2 of these in one.
When I was building my multiplayer Sudoku app, I had fun experimenting with how small I could pack a sudoku grid into a URL. I came up with a scheme combining bit packing with the knowledge of how the grid works. So as you move through the grid, based on the knowledge of what's been placed where and the remaining digits you have a fewer options.
Was fun, I was playing code golf with myself. Sadly seem to have lost the code and I didn't use it in the end.
It would probably have been possible to go smaller than I got it by combining it with a sudoku solver, so stop packing positions once it's solvable. But life moved on.
I think for Sudoku there are a lot fewer legal board configs than there are arrangements of the numbers. There’s probably a way to store the solved state as a single number and then just use 27 bits to specify which numbers are revealed. I don’t know what that single number looks like, though, and you’d have to check that there was only one legal solution to the revealed numbers.
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.
You could probably do something to compress algebraic chess notation in such a way, and even without it as GP says it might cover a decent number of games. My point was you couldn't guarantee a fixed length in 26B, afaik.
(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.)
You can get this even lower, without the need for the extra promotion bits, if you make a note of a few things:
1. There is still redundancy in that there are multiple pieces of the same type, and if you permute their locations you get another representation of the same state.
2. You don't need to say that some pawn's location is the king if it's en passant. You can just use the back row, which pawns can't get to.
Using this, you can use the permutations of the pawns to store extra information. For instance, all of the pawns will be on the board at squares #a, #b, ... . Since pawns themselves have numerical indices, you could say that the "canonical" representation of the board state has all of the pawn locations sorted in ascending order. Then, different permutations of that can carry information about promotions and which of the "pawns" are really queens, etc.
OP here. Thanks for the suggestion! I really like the idea of there being redundancy for pieces of the same type. If I understand correctly, when a knight is in a particular square say it's not relevant whether it's the king-side or queen-side knight. I believe you still need to keep the ordering for the rooks due to castling, but for the knight and bishop you can store 1-bit each in the ordering. With this we end up with 7 bits for each side, thus below 26 bytes overall!
Let me ponder a bit more on the pawn locations. We do need the pawn ordering since the we've encoded the string representing the promotions in sorted order. In the case of en passant we know exactly where the pawn would be, and while we can use the back row, I haven't quite figured out how to use this to encode reliably.
> In the case of en passant we know exactly where the pawn would be, and while we can use the back row, I haven't quite figured out how to use this to encode reliably.
If a white pawn in x4 (for x between a and h) can be captured en passant, you encode its position as x1. When decoding, if you see a white pawn in rank 1, you know it can't be there, so you place it in x4 and flags it e.p. Black pawns are analogous.
What I meant to say was "I haven't quite figured out how to use this to encode reliably and get an improvement vs simply using own king's position".
If we can guarantee that the pawn stays in its own file then I see a path for improvement (by having the actual position vs back row usage as a 1-bit toggle), but this is not broadly the case due to movement across files on pawn captures.
My method doesn't require any additional bits for the e.p. and is compatible with all the other techniques listed in TFA.
Using own king's position loses the info of the file. Iff you guarantee that the pawns are listed in order, this is not a problem. But later in TFA a permutation or sorting of pawns is suggested, which would then mess things up.
Please note that a slightly modified version of my method, where a pawn that can be captured e.p. is swapped (not merely moved) with whatever is in its corresponding back rank before any other encoding takes place, is compatible with all the other clever techniques suggested in the comments.
OK I see what you mean, I admit this wasn't made completely clear in the post. For en passant using the own king's position, the file where the pawn can be captured en passant is NOT reordered whereas other pawns, captures and promotions are reordered.
Yes using the back row works too! I was trying to see if we can get an improvement on the 18 additional bits needed from the post (or 14 additional bits by taking advantage of knight and bishop ordering).
These discussions have been great, very much enjoying seeing the incremental improvements!
Edit: I did another pass, item 4 in the notes did mention this.
> [4] For en passant we need the pawn to remain on its home file. Hence we exclude the pawn from this step if it can be captured en passant. Captures can appear on any file.
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 exactly 26 bytes.
Gonna have to think that through for awhile, not sure if it works out.
Update: I see a comment below that does this but uses 21 bits (instead of 22) by storing bishop position and capture state as a base-33 number.
Trying to strike a balance between raw enumerations of all valid states and practicality:
Rooks and Knights are identical, so their positions fall into [64 choose 2] states + 1 state for when both are captured (only one can occupy the King's location) + 3 states for when both are in the starting position and castling is available for one or the other or both
And captured pawns can be 'unpromoted' and placed on an empty spot in the top row since unpromoted pawns will never be there.
And 1 bit for whose turn it is
1 bit
Total = 176 bits or 22 bytes
Started out thinking about ways to use more of the duplicate pieces, rediscovered the idea of ranking and unranking, started to understand what the person with a limit of 19.2 bytes was doing, tried out just treating position state as [64 choose 32] and only got to 194 bits, then finally worked through this approach.
Meanwhile the non-comp-sci dev in me is like, "why not just store every position in a simple JSON so everyone can read it and everything can parse it". Yeah, it might be half a kB, but you don't have to run through mental gymnastics just to render the pieces...
I feel like we have an interesting tragedy of the commons situation of software engineering.
On the one hand, storing positions on JSON is quick to implement, easy to understand, easy to read, easy to hack on, and junior engineers and the people who have to deal with your code later will be able to pick it up and run with it easily.
On the other hand, when just about everyone is making this same ease-of-use/performance tradeoff, software bloat happens. Our computers are so much faster and beefier, but we never actually seem to be able to enjoy the benefits of that, in part because software engineers keep optimizing for quick and easy.
Maybe we shouldn't dogmatically reach for the easy no-nonsense solution every time, and instead consider whether maybe a little nonsense might, over time, save people a lot of time.
“This Kafka queue collects the zstd-compressed BSON chess messages encoded as base-64 and distributes it to the chess engine VM scale set worker pool for processing… what? Everyone knows chess AIs need large scale and programmer time is expensive! Anyway, the Databricks cluster for move analysis is over here, and…”
Iy's not meant for humans to read directly. The compact representation helps performance amd storage a lot when it comes to looking at a lot of positions. If you were to store it as a json most of your time would be spent parsing.
Awesome video and, I'll admit, the timing makes me curious to know if that video maybe inspired some devs to either pick up this kind of encoding work, or maybe just to finish up some encoding work that they had already started.
Most likely unrelated, I know! Just a wondering in passing.
In the early 90ies, we used to have pocket electronic chess games. I used to have myself one that was about the size of a pocket calculator (it actually was also a pocket calculator), which included a tiny board with tiny, tiny chess pieces. Not a strong opponent and quite slow, but good enough for casual games on the road.
I doubt you could fit that JSON file in its NVRAM. Sometimes I wonder how much sooner we could have had what smartphones offer us today if some technical choices had been made more... wisely.
But that's the endless conundrum Worse is better [1].
Well, this is arguably a kind of compression, right? So you'd be trading CPU time for fewer bytes? Is that a desirable tradeoff at chess engine scales?
Bit packing/mapping et c. isn’t compression the way you’re thinking. What it is, is concise. It requires that the program know what each bit means, rather than telling the program what a value means (as a json structure might), so it shifts where meaning is assigned strictly to the program—a convention must be encoded in the program, not figured out at runtime, though technically you could turn this back into a form of config if you wanted, it just wouldn’t be jumbled up with your data—but it doesn’t really compress the data itself. It’s just efficient at representing it.
[edit] shorter version of the above: it stores the values, but doesn’t store what they mean.
It's not compression in the normal sense of the word. Most parsing is directly to data. So e.g. you know the square of some piece is the next 5 bits. In languages that allow it you can cast directly from the next bit offset to an e.g. byte. This is going to dramatically faster than parsing much more loosely structured JSON. As database sizes increase you also get worse performance there, so it's a double hit. So with these sort of representations you get orders of magnitude faster and smaller. Sometimes there really is a free lunch!
Also I'd add the sizes involved here are kind of insane. I wrote a database system that was using a substantially better compression that averaged out to ~19 bytes per position IIRC. And I was still getting on the order of 15 gigabytes of data per million games. Ideally you want to support at least 10 million games for a modern chess database, and 150 gigabytes is already getting kind of insane - especially considering you probably want it on an SSD. But if that was JSON, you'd be looking at terrabytes of data, which is just completely unacceptable.
To give you an example, the Syzygy tablebase for all endgame positions with 7 pieces remaining is 18.4 TB. The estimated size for 8 pieces is 2 PB.
There are different applications for different things: If you want to host a website with real-world tournament results involving only humans, you probably can get away with using more bytes. But if you're writing an engine that uses pre-computed positions, you want to be as compact as possible.
I did laugh a bit at this bit because "conventional server" and "64 TB RAM" is hilarious to think about in 2023, but will probably be the base config in a Raspberry Pi in 2035 or so:
> In 2020, Ronald de Man estimated that 8-man tablebases would be economically feasible within 5–10 years, as just 2 PB of disk space would store them in Syzygy format, and they could be generated using existing code on a conventional server with 64 TB of RAM
Is your assertion that it takes more time for a CPU to read values out of a 30 byte struct and do a couple shifts and branches than to parse a JSON representation?
Mostly for automation. Bots don't need to read and they are very happy to parse data.
People like to use bots to run thousands or millions of simulated games to test how good their bot is at chess and have it ranked.
Other people like to use the bots that were created to play chess as practice toward a certain skill level. Beginners can pick bots that are proven to be beginner level, through thousands or millions of simulated games.
The smaller the data footprint for the games, the faster and more efficiently the bots can play, which reduces cost and time. In a more practical sense, AI/ML algorithms can be more efficient with tiny data sizes for a bunch of complicated reasons.
So, overall, this is "nerd sniping" to develop better chess players, both human and automated. It's not the most extensible presentation, I'll grant you, but I'm sure it's as fun as Regex Golf, or any other data-packing stuff.
P.S. I'm sure the comp-sci dev in you already knew all this; this is just a bill in case anyone read your comment and truly didn't already know all of this.
in C/C++ code you dont really need to do mental gymnastics either. I can imagine writing a struct with some clever unions to decode this all in one shot. the main benefit as others have point out is 1) to store large number (think billions) of such game positions & searching through them. Also if you are developing for cloud deployment you probably want to use minimal storage needed for space & egress b/w reasons. last reason is something that may not be obvious but if you have some algos that can run efficiently on gpus then you probably want to lay the data out such that its easy(ier) to load in SIMD engines. overall not a bad idea.
Now try building a chess site to store millions of games with hundreds of millions of game states to search over. It's nice that you can very cheaply fit a board into a fixed size column on a database and store the entire game history into around a kilobyte.
You'd write a wrapper to extract our the dense form to something with a nice interface.
My lazy brain says "just take the FENs, remove the slashes etc that are just for human readability, and compress the result with Gzip or do. Bound to be smaller in practice."
It took me a moment to see your point: it might take less information to store the entire game using a chess engine by entropy coding than a single position
The initial board takes 176 bits (22 bytes) to describe. In most games, the definition length would decrease. A game position is self-delimiting as it always has exactly 64 entries (no need to store the variable length)
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.
static arithmetic encoding appears to store the initial board, "black to move" and 4 rook "can castle" flags and a 1-of-9 "can en passant" value in 22 bytes. "4 pawns taken + 12 pawns promoted to queens", which I still think is the "complex-est" configuration that might actually be reachable in a valid game, fits in 25 bytes. A board with just 2 kings left on it encodes in 10 bytes (en passant and can castle flags are not needed).
People have pointed out that due to rules about no repeats, the full state requires storing previous moves.
I’m fairly convinced that the most efficient encoding would be keeping only the move history and then playing that forward to obtain the board state.
E.g.: there are only 32 distinct pieces so a 5-bit number can select one uniquely. Each piece has a maximum of about 32 positions it can move to. Then the encoding is just 10 bits per ply. Typical games are 40 moves (80 ply) and hence require just 800 bits or 100 bytes for the whole game history.
Then you could get clever with Huffman coding or the like, since some moves are more common than others.
Replying to my own post: it seems each move can be packed into 8 bits in all but a few rare scenarios such as having many promoted pawns as queens on the board.
The problem is that the encoding of a position by the previous moves is not unique. For example, 1.a2-a3,a7-a6; 2.h2-h3 represents the same position as 1.h2-h3,a7-a6; 2.a2-a3... Chess engines need to remember evaluated positions to avoid reevaluating them, and this scheme doesn't work well for that purpose.
As the game goes on the space needed to store the list of moves increases while space needed to store a snapshot of the board decreases. It would be interesting to figure out where on average the strategies meet.
Bishops move on the diagonal and so can only stay on squares of their original color; you could thus encode the positions of the 4 bishops with 5 bits each instead of 6 each, saving a total of 4 bits, but this would preclude the use of the "store our/their king's location" hack to encode things. But you can encode bishop positions as a 4-digit base-33 number (digits 0..31 indicate the square, digit 32 is captured), which can be stored in binary as a 21-bit number. Net savings ~3 bits.
The "no two pieces on the same square" constraint could similarly be used more aggressively.
But in those cases you're missing the pawn that was promoted, so the location of the second dark-square bishop would be encoded in a 6-bit pawn slot rather than a 5-bit or base-33 bishop slot.
For my chess tactics trainer at https://www.checkmatechamp.net/ , I tried a lot of different techniques to compress a small set of positions (about 800).
I was not concerned with storing the positions in a fixed size, so I was mainly trying things that would make the entropy of each compressed position smaller. I eventually fit these into a file that is about 14 KB in size when gzipped. Each position takes about 17.5 bytes, excluding the HTTP headers. If you go to the page and scroll through the positions, you'll see that each position loads instantly. That's because all the positions are in that 14 KB file which is loaded initially. I didn't include the castling or en passant info in that file, but I suspect it wouldn't add more than one byte per position on average.
I only considered techniques that would not cause the decoder to become overly complicated. One "non-standard" technique that I used was inverting the color of all the pieces on one side of the board. Specifically, on the lower half of the board, I change all the white pieces to black and vice versa. This greatly lowers the average entropy of a typical position, since for most of the game, each player keeps most of his pieces on his side of the board. It is also easy to handle in the decoder in one line (if row < 4, then piece = -piece).
I have meaning to write a blog post about it, but I haven't gotten around to it yet. If you are interested in hearing more, let me know, and I will move it up my to-do list.
If the colors are symmetrical, then it's just "my pieces" and "opponent's pieces". You could encode who has the move by how the board is ordered, and predict it from the king and queen position, then just encode the differences.
Oh, no encoding of the turns? Then the encoding I came up with after following in the link to Forsyth–Edwards Notation is even better.
Version 1: For each position on the board, store if it has a piece or not. 8 bytes for that. Then for each piece in order, 4 bits can encode color and type. 16 bytes for that. Then you can spend 4 bits on castle ability, and 4 bits to pick the pawn that is able to be captured en passant (If there isn't one, pick a pawn that isn't in position. It's impossible for all the pawns to be in a vulnerable rank and have an enemy pawn in position.) So that's 25 bytes, no sweat.
Version 2: Instead of 4 bits per piece, store color|0 for a pawn, and color|1|type for anything else. Encode castle-eligible rooks and castle-ineligible rooks as separate types. This costs 14 bytes at the start of the game, and if you promote a piece at least one pawn has to die so the cost increases by 1 bit at most, up to 8 times. So 15 bytes, and you can always squeeze the bits for en passant eligibility into the 15th byte, because more promotions means fewer pawns to keep track of. You can even say whose turn it is by encoding "active turn king" and "inactive turn king" as different types. That's 23 bytes for the entire board state.
Either way you can add the turn counters with 2 more bytes.
Edit: Okay, this version beats mine solidly: https://news.ycombinator.com/item?id=37526804 I was thinking wrong about the number of captures versus promotions, and you can get much more clever with encoding en passant. So 22 bytes or less is enough for this sort of method.
Your version 1 is similar to my top level comment. Note that 4 bits is enough to encode color, type, and include special types for en passantable pawn and castleable rook, so you keep a clean 24 bytes. (Compressing the two special types into one special option, decodable based on position, can get just under 23 bytes.)
For version 2, note that 12 promotions can happen, since one capture (white's B pawn taking black's A pawn) can open up the promotion path for 3 pawns (white's B pawn, white's A pawn, and black's B pawn). Two bits per pawn and 5 bits per other piece start at 14 bytes, but can go as high as 17.5 bytes. (Promoting 12 pawns with 0 other captures would be pretty ridiculous as a game, but technically possible...)
The state of an individual chess piece can be stored in 6 bits. 3 bits for the X coordinate, 3 bits for the Y coordinate.
A captured piece can use the same coordinates as the King, which would indicate that it's captured.
For promoted pieces, you can use 3 bits per promoted piece type (Bishop, Rook, Knight, Queen) to indicate how many exist. For the case of 8 promoted pawns, you'd need one more bit to indicate that all pawns have been promoted and to treat a 7 as an 8.
You need 1 bit to indicate who's turn it is. You need 1 bit per player to indicate if castling is still possible, and 1 bit to indicate if the last pawn move was two squares.
What gets tricky is tracking for the draw rules.
There's '50 moves with no pawn or capture', '3 move repetition', '5 move repetition', '75 moves with no capture or pawn move'. 50 or 75 are simple enough to count, but tracking identical boards from a previous state would be hard to do with limited bits.
So then we have:
6 bits for piece coordinates of 32 pieces (192 bits)
13 bits for pawn promotion status for each player (26 bits)
1 bit per player for castling allowed (2 bits)
1 bit for whose turn
1 bit for en-passant possible
7 bits for move counter with no pawn movement or captures
That works out to 29 bytes.
Edit: Article did promotions much better by removing impossible promoted piece counts.
'Castling allowed' flag could be tied to 'both rooks in their original positions'. If the pieces look like they're in their original positions, but a king or rook moved, swap the two rooks so they're not in the original position anymore.
En-passent check by swapping pawn order is neat, but pawn order could instead be used to eliminate the 'promoted' flag per pawn instead.
I wonder if you could shave off some more bits by considering the specific movement restrictions of some pieces:
Bishops can only ever occupy squares of their respective colour, so you'd only have to encode ~32 possible positions instead of 64.
Pawns (before promotion) can only move straight forward and diagonally forward, which makes their range of valid positions a sort of upside-down triangle shape, with the "tip" of the triangle at the respective pawn's starting position. (e.g. it's impossible to move the pawn from A2 to H2 - or even to H8 - without a promotion)
Haven't made the exact calculations, but it might be possible to encode both positions with 5 bits each instead of 6 bits.
Reading this I realized chess is not fully Markovian (you cannot know everything about the game by just looking at the board at any point), specifically because whether determining if castling and en passant are valid moves depend on the history of the board.
Any scheme that does not make allowance for illegal moves or invalid positions is not suitable for purpose, IMO. In OTB situations players can make mistakes that no one catches. These illegalities become part of the official record of the game.
> 9.2 The game is drawn, upon a correct claim by a player having the move, when the same position for at least the third time (not necessarily by a repetition of moves) [happens and a draw is claimed]
> 9.3 The game is drawn, upon a correct claim by a player having the move, if: ... 9.3.2 the last 50 moves by each player have been completed without the movement of any pawn and without any capture.
> ...
> 9.6 If one or both of the following occur(s) then the game is drawn:
> 9.6.1 the same position has appeared, as in 9.2.2 at least five times.
> 9.6.2 any series of at least 75 moves have been made by each player without the movement of any pawn and without any capture. If the last move resulted in checkmate, that shall take precedence.
This means that, in order to store a full chess game-state, you also need to keep track of how many moves since the last pawn move or capture (for the 50 and 75 move rule (9.3.2 and 9.6.2 respectively)) and also what positions have previously occurred (for the 3 / 5 position repeats, (9.2 and 9.6.1 respectively)).
The maximum number of moves from any chess position is 218 according to this post[2], so each move in the history can be uniquely identified by a single byte. You only need to store the moves since the last capture (since you can't repeat an earlier position), and you _definitely_ can't have more than 112 pawn moves without a capture (because there are only 16 pawns and they can only move forward, except in the case of en-passant which requires a different pawn to move forward twice).
But that gives an upper bound of 8400 moves -- this bound is probably much higher than it needs to be though.
If a pawn moves then you can't repeat a state either, can you? So track the last 75 "moves".
> they can only move forward, except in the case of en-passant
En passant still attacks forward, into the space the enemy pawn just moved through.
> 112 pawn moves without a capture (because there are only 16 pawns and they can only move forward
But pawns can't move through pawns. ~~At most I think you can have 4 of the pawns march all the way forward and get captured, leaving you with with 4 pawns that can move 6 spaces and 8 pawns that can move 7 spaces, for a total of 80 pawn moves without a capture.~~
Okay, if you sacrifice a bunch of other pieces to pawns, then you can get them to pair up without losing any. So that's 8 pawns moving 6 spaces, and 8 pawns moving 7 spaces. 104 pawn moves in a row without a capture.
It uses lower 4 bits of 64 bytes to store the board positions (upper 4 bits is used to store other data). 64 nibbles is 32 bytes, not too far off from the 26 bytes here.
It’s been a minute since I did this seriously so maybe my magic is out of date but I don’t think this is how bits to bytes works:
> 100 bits / ~12 bytes
> 18 bits / ~2 bytes
I didn’t want to spend a whole lot of effort tracking the arithmetic after this. Was it actually 28 bytes? 27 because I can squeeze those extras into one shared byte?
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).