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

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.