You could use a divider and just encode it in log(9!)/log(2) ~ 19b? I think the point of the article is you can encode every game in something like a kilobyte of data, though, right?
To be able to represent arbitrary game states, do you need 3 more bits to indicate the turn number? 19 bits works only if represent complete finished games, but not for in-progress games? So we are back to 22 bits
I'm fairly certain the entire game can be encoded in 16 bits. Thinking through this now. There are much less than 9! Games if you only include valid moves and actually end games that have three in a row. This is also before any symmetries are used.