[phire]

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.

[Dylan16807]

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