Symmetry plays an important role in tac-tac-toe. For example, there are only 3 first moves: center, corner, and side. (Let's say X plays first). We indicate the move by the square number (1-based indexing, for a change).
Starting from the center, there are 2 second moves, while from the corner or side, there are 5 second moves. That's because 16 = 18 and 12=14 and so on. A total of 12 positions:
I see that 12 and 21 look identical except that X and O are switched, but I will keep them distinct, to remember the difference in order of play between player 1 and player 2.
For the third move, it is still feasible to enumerate all the moves (although I'll admit it was quite tedious). Those starting positions with left-right (reflection) symmetry (51, 52, 15, 19, 25, 28) or rotational symmetry( ) have 4 additional possibilities. The rest have 7. We generate a total of 6 * 4 + 6 * 7 = 66 boards with 3 plays (but see below).
As you probably have noticed, some of these are the same, just reflected or rotated. Just considering the 5.. series, I found six duplicates:
And notice that the other permutation is not the same, for example:
It only works if we switch X's, the first and third positions. We would have expected 132 = 231, but 231 is not in our list because 23 is the same as 21. I found two more:
So it looks like we have 66 - 8 = 58 unique positions.
From this point, there are 6! positions possible for each, neglecting the chance that some of these may be rotational isomers. So there is at most a total of 58 * 720 = 41760 possible positions, which is almost an order of magnitude less than 9! = 362880.
Actually, there are significantly fewer than that, since a number of the 3-mers force the next move by 'O' in order to block the win by 'X'. Also, some have symmetry, allowing only 3 possibilities instead of 6.
From the summary below (D = duplicate, S = symmetric, F = forced), I count 8 duplicates (removed), 23 forced moves (1 each), 9 with symmetry admitting 3 moves, and 1 with special symmetry (159) admitting only 2 moves. That leaves 66 - (8 + 23 + 9 + 1) = 66 - 41 = 25 with 6 possible moves. That's a total of 23 + 9 * 3 + 2 + 25 * 6 = 23 + 27 + 2 + 150 = 202 positions at the 4-mer stage. And some of these may be duplicates.
It's about now that I start begging for a simulation. I'll see what I can do.
