I wonder if you could store them as a trie, I feel like that would give you quite good savings given the commonality of openings. Or at least use a trie for the openings and then apply the Huffman coding to the rest of the game and store that separately.
Right. Every possible chess game as a sequence of legal positions can be uniquely enumerated. Per Wikipedia the game-tree complexity is around 10^123, so you'll need about a 124 digit number to represent them. This is as dense as it can possibly get.
On the other hand, lichess supports alternative chess modes and starting boards that may or may not be reachable from the standard initial configuration and legal moves, so this won't work for those use cases.
