Posted by: Alexander Ellis | April 15, 2008

Topological Tic Tac Toe 1: The Torus

(This post is inspired by one of my favorite books. Also, there really should be pictures in this post; I apologize for their absence.)

I’m going to describe a bit of “recreational topology.”

Hopefully you already know the rules of tic tac toe (“noughts and crosses” for the Brits). And if you’ve played it a few times, you may have figured out that if both players play with perfect strategy, the game will always end in a draw. Now imagine playing on a board which behaves like a Pacman game—that is, the right (respectively, top) edge of the board is identified with the left (respectively, bottom) edge. This is, of course, equivalent to taking a square tic tac toe board and shaping it into a (2-dimensional) torus; we’ll call this game Torus-TTT.

Let’s make this more precise. Recall that one construction of the torus is as a square with opposite sides identified with the same orientation. Then given a tic tac toe board, we imagine it wrapped onto the torus via this construction. Of course we can view the nine resulting boxes on the torus $\mathbb{T}^2$ as a square with any of the nine as the upper-left box. Thus we define a winning pattern in Torus-TTT to be any pattern on the usual 3×3 board which, when sent to the torus and then put back onto a 3×3 board with some possibly different choice of upper-left box, is a winning pattern in ordinary tic tac toe (which from now on we’ll call $\mathbb{R}^2$TTT).

Before reading on, grab a friend and play Torus-TTT a few times. Try and picture each position as on the torus itself, embedded in $\mathbb{R}^3$.

In practice, it’ll be useful to have a handy way of looking at a 3×3 pattern and telling if it’s a winning pattern in Torus-TTT. Luckily, this is easy! Label the nine boxes of a 3×3 board as $(i,j)$, where the box is the one in the $i$-th row and $j$-th column. (Take $i,j=0,1,2$ mod 3.) Then the transformation which shifts every symbol one box to the right (mod 3) is clearly equivalent to sending the board to the torus, then taking the box which was formerly $(0,2)$ as the new $(0,0)$. That is, it preserves winning patterns! More generally, the transformations of the form “send the contents of $(i,j)$ to $(i+a,j+b)$” (for fixed $a,b$ mod 3) realize all possible changes-of-origin. Call this transformation $F(a,b)$. Then we have verified the following:

Easy Criterion: A Torus-TTT pattern is a winning pattern if and only if applying some $F(a,b)$ to it yields a winning pattern in $\mathbb{R}^2$-TTT.

At this point, there are several obvious exercises. A few are listed below. Cheaters can highlight the text following an exercise to see its solution.

1. Enumerate all winning patterns in Torus-TTT. Answer: the usual rows, columns, and diagonals, as well as the following: {(0,0),(1,2),(2,1)} and its image under rotation by 90, 180, and 270 degrees.

2. What is the best opening move? Answer: Anywhere—they’re all equivalent!

3. If both players play with perfect strategies, who wins? And in how many moves? Answer: First player, in 4 moves.

If you’ve completed those three (simple) exercises, then you’ve “solved” Torus-TTT. Of course, different identifications of the edges of the 3×3 board yield different games. There are six possible games: $\mathbb{R}^2$, the torus, real projective space ($\mathbb{RP}^2$), the Klein bottle, the cylinder, and the Möbius band. (We don’t allow identifications of adjacent edges.) In the sequel post, we’ll take a look at and solve the remaining cases. Until then, try the following:

4. Prove that Torus-TTT and Cylinder-TTT are the same game.

5. Interpret the solution to Exercise 2 above in terms of a suitable finite group acting on $\mathbb{T}^2$.