Counting the number of ways to break the symmetry of an N x N grid by placing one X and one O at a time 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$?
 A: 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.]
A: This is not the full game tree, but the complete optimal tree for tic-tac-toe.
