0
$\begingroup$

How would one find the number of unique tic tac toe states taking into account rotational equivalence between states?

$\endgroup$
  • $\begingroup$ First of all, compute the number of possible outcomes without taking into account the rotational equivalences. Look at symmetrical cases as a separate case, because they are not counted multiple times. Then divide the case of the non-symmetrical outcomes by 4 because you can rotate the board 4 times 90 degrees until it's in it's original state. Finally, add those two numbers you got. $\endgroup$ – Algebear Apr 27 '18 at 15:14
  • $\begingroup$ @GuusPalmer so that's what I was thinking at first, but does this take into account the two positions of having an X or O in the center? $\endgroup$ – Dylan Hume Apr 27 '18 at 15:16
  • $\begingroup$ Sorry, I noticed it at the moment I posted the comment:-] $\endgroup$ – Algebear Apr 27 '18 at 15:17
  • $\begingroup$ There are cases when finishing in 5, 6, 7, 8 or 9 moves. When not considering symmetry it actually becomes bit more difficult because e.g. starting a game in the upper left could give the same outcome as starting in the mid right. Also, if you only consider best games, where each player is only performing the best possible moves, you get way less possibilities. Btw, do you consider endgames or also mid-states where there's only a circle and a cross for example? $\endgroup$ – Algebear Apr 27 '18 at 15:23
  • $\begingroup$ Related to math.stackexchange.com/q/2476469/265466, which takes all symmetries into account. $\endgroup$ – amd Apr 27 '18 at 17:31
1
$\begingroup$

This question can be understood in many different ways. There are a lot of ways to define a "tic tac toe-game". Below is a little summary of possible assumptions you can make. $$\text{What is a unique move?}$$ (1) Choice of first player is distinct and every board position is distinct. (2) Choice of first player is arbitrary and every board position is distinct. (3) Choice of first player is arbitrary and board orientation is arbitrary, but once the board is oriented every position is distinct (4) Choice of first player is arbitrary and only distinct player choices are distinct moves. $$\text{What moves are allowed?}$$ (1) Any open square. (2) Players must make three in a row if possible. (3) Players must make three in a row if possible, otherwise must make a blocking move if possible. $$\text{When is a game over?}$$ (1) When either player makes three in a row or the board is full. (2) When the outcome of the game is fully determined. $$\text{The most logical answer would be 23,129 possibilities.}$$ For this is the number of games if two games are the same when the players faced the same choices at each move of the game; i.e. considering symmetry at each step of the game. Also, the players don't take meaningless steps and the game is ended when 3 in a row is achieved by one of them. Look at http://www.mathrec.org/old/2002jan/solutions.html if you want to see the full explanation of the computations and the game outcomes overall.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.