Today we’re going to encode state of International Checkers game in as little as possible.
There are two players, each of them has at most 20 pieces, some are men, some are kings. The board is 10 by 10 big (so has 100 fields in total).
First solution we may have is to encode position using two integers, color with one byte, and state (man vs king) in another byte. This gives 10 bytes per piece, 400 bytes in total.
Next solution is to hold each field with information whether it’s occupied, by what piece (man vs king) and belonging to whom (color). This results in 100 fields multiplied by 3 bytes, so 300 bytes in total.
Next, we could encode state using bits. We have four longs per layer. Two longs for men, two longs for kings, each bit is set when a piece is in given field. This results in 8 longs so 64 bytes in total.
Now, we can encode position of a piece using 8 bits (4 for row, 4 for column) plus one additional bit for type. This results in 40 pieces multiplied by 9 bits so 360 bits or 45 bytes in total.
We can cut this even more. First, we don’t need to store whole board as checkers are played on black fields only. So we need to encode 50 fields only. For each we need to store three bits: is occupied, color and type. 150 bits in total or 19 bytes.