Prepare an empty chess board.
Empty square is represented as 0.
White piece is represented as +1 to +6 in the order of RNBQKP.
Black piece is represented as -1 to -6 in the order of RNBQKP.
Also prepare the reference chess board, which is same to initial positions except:
3rd and 4th ranks are filled with black pawns, like 2nd.
5th and 6th ranks are filled with white pawns, like 7th.
Somehow, f1 and f8 are filled with rooks, not bishops. (Is this a bug?)
Read the initial board. Start at a1 and continue until all squares are filled:
Read one byte as bit fields AAAABBBB.
Skip A squares. Wrap to the first file of the next rank on the last file.
If -5 <= B-7 <= 6,
The current square is set to B-7.
If the current square is on 1st--4th ranks, invert the piece's color (if any).
Skip to the next square.
Otherwise, let C be 1 if B-7 = -6 (normally a white pawn), or B-5 otherwise.
Repeat the following C times:
The current piece is taken from the same square in the reference board.
Skip to the next square.
Read one byte as bit fields AAAABBBB.
A indicates the current run. White if A = 1, black otherwise.
I don't know B, but only one half-move will be read unless B = 1.
Read one half-move or as many half-moves as possible:
Read two bytes A and B, which are interpreted as square indices 0..63 (a1..h8).
If A is on the 7th rank and a white pawn is at A,
B's rank is reinterpreted as the promoted piece index (0 = no promotion, 1..4 = RNBQ).
B's rank is then always reset to the 8th.
If A is on the 2nd rank and a black pawn is at B, do the similar adjustement.
Put a move from A to B, with the promotion indicated if any. But do NOT alter the board.
This format uses 1/3 to 1 byte to encode a single piece, unless there are 4 pieces or less in which case there may be some more overhead (since you can skip at most 15 squares at once). This is not particularly efficient; even a simple Huffman coding will be as efficient as that [1]. You should also make use of the fact that there are at most specific number of pieces per type, since once you've seen a black king, you won't see more so the corresponding representation is wasted. (Promotions make other pieces more complicated though.) I guess 10 bytes might be possible without a very complicated scheme.This format also uses two bytes to encode a single turn. This again is hardly efficient, especially because there are much smaller number of legal (half-)moves given a particular position. (218 is believed to be the maximum, and the upper bound is not much larger than that [2].) So you can just enumerate legal moves and encode the index as a single byte. If the number of legal moves is far smaller, say 16, you can pack multiple moves into a single byte as well. A much involved scheme would then assign a smaller number of bits to a more likely move, using heuristics and neural networks and whatever else [3].
[1] https://stackoverflow.com/a/66345772
[2] https://old.reddit.com/r/chess/comments/o4ajnn/whats_the_mos...
[3] https://triplehappy.wordpress.com/2015/10/26/chess-move-comp...