Disregarding simplifications from symmetry, the first three moves comprise 9 * 8 * 7 = 504 possible combinations. Surely you can enumerate at least that. So y

Disregarding simplifications from symmetry, the first three moves comprise 9 * 8 * 7 = 504 possible combinations. Surely you can enumerate at least that. So you'd only need 9 bits, saving you a bit. And I'm not sure why you'd need to mark whether X or O starts: X always starts.