Taking into account symmetry, how many possible games of tic-tac-toe are there?

Question

Same as this other question (Game combinations of tic-tac-toe), but taking into account symmetry.

Answer 1

In one sense, you could just take the answer of $255\,168$ to the previous problem and divide it by $8$, getting $31\,896$. If you care about the order in which the pieces were played, then a description of one complete tic-tac-toe might look like the board below: \begin{array}{c|c|c} \times_1 & \bigcirc_2 & \times_3 \\ \hline & \times_7 & \bigcirc_4 \\ \hline \bigcirc_6 & & \times_5 \end{array} and all such descriptions with a three-in-a-row in them are asymmetric: so, because the tic-tac-toe board has eightfold symmetry (four possible rotations which may or may not be followed by a reflection), we can take symmetry into account just by dividing by $8$.

But you might also consider this game to be identical to the game represented by \begin{array}{c|c|c} \times_1 & \bigcirc_2 & \times_3 \\ \hline \bigcirc_4 & \times_7 & \\ \hline \times_5 & & \bigcirc_6 \end{array} because the only distinguishing trait is that on $\bigcirc$'s second move, they played next to $\times$'s first mark, not next to their second mark, even though the two positions created in this way are symmetrical. In other words, after every move these two games were in identical positions up to symmetry - it's just that which symmetry this is changes over the course of the game.

This page lists the answer to possible variants of this question. The difference between the two notions of symmetry described above is board symmetry (which considers the two games above to be different) and game symmetry (which considers them to be the same).

Under game symmetry, the number of possible tic-tac-toe games is only $26\,830$.

The page I linked to above also lists several other possible answers we could give, under additional constraints:

• We could stop the game once the winner has been determined (or once it's been determined that the game is a draw).
• We could forbid the players from making "obviously stupid" moves, for different notions of "obviously stupid" (e.g., not making winning moves when they're available, or not blocking winning moves when the other player threatens to win).

Answer 2

This question is a good introduction to symmetries because there are two symmetries of the board - both reflections and rotations - and we need to disentangle the two.

This is easy to do because although the board can be reflected on any of 4 axes (two central axes and two diagonals), all of these reflections are the same once we permit rotation since a flip of the board on any one choice of axis can easily be translated to be equivalent to having flipped on any of the other 3 axes, by an appropriate choice of rotation.

There are 4 rotational positions which leave the board itself unchanged, multiplied by one flipping axis (i.e. two possibilities) so there are 8 symmetries.

Dividing $255168$ by $8$ gives $31896$ possible games.

...This simple answer would count the $2$ games given in Misha's answer as different.

Answer 3

Just thought I would throw this out there, I counted 46910 total game states including non-win non-draw situations like the empty board. #pyhtonFTW

EDIT: If you assume that players will block if the opponent will win next turn and also that players will win if they can I found a decision tree with 6355 nodes, of the leaves, 488 are X wins, 1278 are draw and, 164 are O wins. (X goes first.)

That said I think I actually over did it with my checking board transformations... For each possible move I check 16 possible board orientations, and apparently I only need to check 8...

I think I could just comment out lines; 8, 9, 58, 59. https://github.com/Krewn/TicTacToe/blob/master/ttt.py