[blackboxlogic]

Don't forget to track if the rooks or kings have moved, for castling eligibility. And what the previous move was for en passant. And the full game history back to the most recent capture for draw by repetition.

[thrw21]

  And the full game history back to the most recent capture for draw by repetition.

Ouch, I will leave this as an exercise to reader

[Dylan16807]

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

[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.