That part is easy.

1. store the oldest full board you care about

2. for each turn, record either:

2A. two 6-bit coordinates

2B. 1-8 bits to say which move they picked out of the full list of legal options

You could actually run a small chess engine a few moves ahead to sort the full list of legal options into the order of obviousness.

Then you can use a variable length encoding (Huffman coding?) to encode the moves, with more obvious moves taking fewer bits. You could even encode multiple moves into a single code point, and it might be possible to encode an entire sequence of obvious moves (like a complex exchange) into a single code point, which might be encoded as just a single bit.

You would definitely use arithmetic encoding at that point. Then you can directly use fractional bits to encode moves.