Finding an invariant of equivalent Tic-Tac-Toe boards

computational complexitygame theoryinvariant-theory

Considering Tic-Tac-Toe boards (TTT), they are pretty much equivalent if they're rotations or symmetries of each other. Considering a specific board, I would like to be able to easily label its equivalence class, which would be the set of each rotation / symmetries of that board.

I do only have the first naive idea, and it's obviously not satisfying. I could compute all possible boards, check which of them are equivalent, sort them and label each equivalence class. That way, everything is pretty simple but it's computationally extremely expensive. Basically, I'm building arbitrarily a function that gives me a number depending on the input board by computing every possible board.

I do believe that there exists a heuristic I'm not able to find by myself. In a perfect world, what I would want would be to find an invariant of equivalence class, that would be computationally cheap. That way, I would be able to label each representative I computed with this invariant. When I present a new board to the program, the first thing I do is to compute the invariant, which directly gives me the label for the representative I computed, and find it directly. Basically, $f$ would remain unchanged by any rotation or symmetry over the input TTT board. However, it should change between two non-equivalent TTT boards. Does such an $f$ exists, or am I "forced" to build it arbitrarily by checking each possible board ?

If possible, I would like to be able to get a more general invariant, which would work with arbitrarily large matrices (not necessarily 3×3), and even with any numbers contained (and not a simple 3 possibilites encoding for TTT).

Best Answer

Community wiki answer so the question can be marked as answered:

I believe the standard way to do this sort of thing is the one Karl suggested in a comment: Produce all equivalent boards and choose a canonical representative by imposing some order, e.g. lexicographic order.

Computationally, you don’t actually have to produce all the boards – you can fetch the squares in the permuted order from the board you have, something like:

  • generate 8 functions $f_i(j)$ that map board index $j$ according to symmetry operation $i$
  • to canonicalize a board, compare $f_i(1)$ for all $i$, $f_i(2)$ for all remaining $i$, etc., in each step dropping all $i$ that don’t have the highest value, until only one $i$ remains
  • store the board together with $f_i$ as the canonical representation of the board
  • if you need to compare two boards with functions $f_k$ and $f_l$, instead of comparing square $j$ to square $j$, compare square $f_k(j)$ to square $f_l(j)$.
Related Question