4
$\begingroup$

I have recently been working out the full game tree for tic-tac-toe, just for fun. I am using the well known equivalence relation of rotations/reflections to simplify this tree in the standard way (which begins by noting that there are only 3 opening moves: edge, corner, and center). I actually could not find an image of the full game tree for tic-tac-toe, so if anyone can provide a link I'd appreciate that.

This work motivates the following;

Let there be given an N x N grid; and let $m$ be a natural number.

Let $I$ be the set of all possible ways to place $m$ copies of the letter $X$ in the grid, and $m$ copies of the letter $O$ in the grid (with the restriction that we can only place one letter per space of the grid; in other words, just imagine playing a game of tic-tac-toe on an N x N board for an even number of moves).

Problem:

How many ways are there to completely break the rotational/reflection symmetry of an N x N grid by placing $m$ copies of $X$ and $m$ copies of $O$?

  • 0
    I am having a bit of difficulty understanding your question, could you clarify a little what you mean by breaking the symmetry? As it stands, my current interpretation, is how many configurations of m X's and m O's are in their own equivalence class with respect to rotation and reflection.2010-10-01
  • 0
    I'm still trying to work this out, I should have thought it through more carefully before posting.2010-10-02

2 Answers 2

2

I think you're trying to ask: how many such grids admit a non-trivial symmetry (in the dihedral group)?

For fixed m≥1, asymptotically almost all (0,1,-1)-matrices with exactly m 1's and m -1's do not admit a non-trivial symmetry (rotation/reflection). For these matrices, we can consider the X's as the 1's and the (letter) O's as the -1's. The (number) 0's represent the empty cells.

Since m is fixed, there are ${{N^2} \choose {m,m,N^2-2m}}=N^{4m}/m!^2+o(N^{4m})$ (0,1,-1)-matrices in total with exactly m 1's and m -1's.

The number of such matrices that are preserved under transposition is \[\sum_{i,j} {N \choose {i,j,n-i-j}} {{N \choose 2} \choose (m-i)/2} {{{N \choose 2}-(m-i)/2} \choose (m-j)/2}\] where i is the number of 1's on the main diagonal, j is the number of -1's on the main diagonal. Therefore we require 0≤i+j≤m and m-i and m-j even. A crude upper bound to the above summand is $\mathrm{const} \cdot N^{i+j+2(m-i)/2+2(m-j)/2} \leq N^{3m}=o(N^{4m})$. Since m is fixed, there is only a finite number of pairs i,j which is summed over, so the overall result is $o(N^{4m})$.

The number of such matrices that admit any of the other non-trivial symmetries is bounded above by the above formula also. So asymptotically almost all (0,1,-1)-matrices with exactly m 1's and m -1's do not admit a non-trivial symmetry.

Actually, I suspect that this result would be true without the fixed m condition, but I can't think of how to prove it off-hand.

So in answer to the question, unless you're dealing with a very small case, and unless you're deliberately trying to create a symmetry, you're unlikely to create a matrix that has a non-trivial symmetry. For the search tree, most of the time you will be able to identify 8 nodes corresponding to equivalent games of naughts and crosses.

[PS: it would be messy (although possible) to find an exact formula along these lines for the number of such matrices that admit a non-trivial symmetry.]

  • 0
    I really like this answer! This is what I was trying to ask, and I should have thought about the matrix representation, it seems so obvious in hindsight.2010-10-17
1

This is not the full game tree, but the complete optimal tree for tic-tac-toe.