For what piece to replace the unmoved king with, you can actually use both white AND black pieces, since the starting rank can decode what color the king is: -

For what piece to replace the unmoved king with, you can actually use both white AND black pieces, since the starting rank can decode what color the king is: - White Knight on E1 and no king: Replace with white king that can castle both ways, E4 pawn can be taken En Passant - White Bishop on E1 and no king: Replace with white king that can castle kingside, E4 pawn can be taken En Passant - White Rook on E1 and no king: Replace with white king that can castle queenside, E4 pawn can be taken En Passant - Black Knight on E1 and no king: Replace with white king that can castle both ways, E4 pawn cannot be taken En Passant - Black Bishop on E1 and no king: Replace with white king that can castle kingside, E4 pawn cannot be taken En Passant - Black Rook on E1 and no king: Replace with white king that can castle queenside, E4 pawn cannot be taken En Passant It's the same for E8, just put a black king and not a white king. Sorry if this is repetitive, I could have probably just explained it and let you figure it out, but I put the cases down here for clarity. This should also be combined with the Knight huffman encoding that was talked about here https://news.ycombinator.com/item?id=37527350 https://news.ycombinator.com/item?id=37527350