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).
Check out this great blog post of Lichess for more information: https://lichess.org/blog/Wqa7GiAAAOIpBLoY/developer-update-2...
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.
ChessMonitor is practically a work of art!
I guess OAuth is relatively fast as I don't have a middleman (like Auth0) in there. It's just Passport.js.
https://chess.stackexchange.com/questions/2506/what-is-the-a...
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.
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).
https://www.chessmonitor.com/u/XqaFNTHcR61WpiMfOhEY/games?po...
This does raise the question of the efficiency of reverse engineering a series of minimal moves for some board state.
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).
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.
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.
I once[0] tried to spread this message :)
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.
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.
Nearly every company uses them to prove the authenticity of deployments in production at one or more layers.
This structure is used inside your .git directory, your docker manifest, etc.
Blockchains are incredibly useful structures.
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.
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