Here's a fairly intuitive 16-bit encoding: Use 9-bits to store positions of either blanks or Xs, depending on which there are more of. 1 extra bit to indicate

Here's a fairly intuitive 16-bit encoding: Use 9-bits to store positions of either blanks or Xs, depending on which there are more of. 1 extra bit to indicate which case it is. Then you have at most 6 remaining cells, so 6 more bits to indicate which of the two remaining options each contains. 16 bits total. This also has the benefit that you can use fewer bits for many game states, e.g. a blank board can be represented in 10 bits.