Bishops move on the diagonal and so can only stay on squares of their original color; you could thus encode the positions of the 4 bishops with 5 bits each inst

Bishops move on the diagonal and so can only stay on squares of their original color; you could thus encode the positions of the 4 bishops with 5 bits each instead of 6 each, saving a total of 4 bits, but this would preclude the use of the "store our/their king's location" hack to encode things. But you can encode bishop positions as a 4-digit base-33 number (digits 0..31 indicate the square, digit 32 is captured), which can be stored in binary as a 21-bit number. Net savings ~3 bits. The "no two pieces on the same square" constraint could similarly be used more aggressively.