Posted by: Alexander Ellis | April 17, 2008

Topological Tic Tac Toe 2: Other Surfaces

In my last post we saw how to play and win Torus-TTT, the game of tic tac toe on a torus. Recall that we constructed the game by identifying two pairs of sides of the usual tic tac toe board and defining the winning patterns to be patterns which are the usual tic tac toe winning patterns, viewed via a different identification of the torus with the square. Then our “Easy Criterion” stated that this was equivalent to taking all usual winning patterns and translating them mod 3 in both directions the nine possible ways. In other words, we let G_T=\mathbb{Z}_3\times\mathbb{Z}_3 act on the usual tic tac toe board by translations mod 3, and defined the Torus-TTT winning patterns to be G_T-translates of the usual winning patterns.

More generally suppose A is some 3×3 tic tac toe board with one or two pairs of sides identified, each identification either parallel or anti-parallel. Then the winning patterns of tic tac toe on A are defined to be those which can be made into a standard tic tac toe (\mathbb{R}^2-TTT) winning position by translating in directions where sides are identified, along with the appropriate reflection in the anti-parallel case (more on this reflection below). Our general plan of attack will be to construct a group G_A of symmetries acting on the A-TTT board by transformations which preserve the set of winning patterns.

To be clear (and again, I apologize for the lack of pictures in this post) consider M-TTT, tic tac toe on the Möbius band M. This surface is formed by identifying the two vertically oriented sides in an anti-parallel fashion and leaving the horizontally oriented sides unidentified. Then winning patterns are those obtained by left or right translations of \mathbb{R}^2-TTT winning patterns; here, a translation moves the contents of (i,0) to (i,1) and that of (i,1) to (i,2), but when wrapping around there is a reflection: the contents of (i,2) is sent to (2-i,0). So translation by one or two squares in either direction has order six—that is, performing a translation six times is the identity but no fewer number of iterations yields the identity. So we have an action of G_M=\mathbb{Z}_6 on M-TTT which leaves winning patterns invariant.

Note that the action of G_M on M-TTT has two orbits: the first is the central row and the second is the union of the two other rows. Observe that an opening move is only well-defined up to which orbit it is placed in, so in effect, there are really only two possible opening moves in M-TTT! (The solution to exercise 2 of my previous post is then clear: G_T acts transitively on Torus-TTT, so all opening moves are equivalent.) However, once an opening move is chosen, the symmetry is broken—second moves within the same orbit will generally be inequivalent, since their position relative to the first move is part of the data of the game.

Equipped with this action, it isn’t hard to check that M-TTT has 16 winning patterns, and that the first player will always win (assuming, as always, perfect strategy). If the opening play is to the six-element orbit, the first player can force a win in three moves.

Of course the use of the groups G_M=\mathbb{Z}_6 and G_T=\mathbb{Z}_3\times\mathbb{Z}_3 isn’t exploiting the maximum amount of symmetry; for instance, rotation by \pi about the center of the board is a symmetry of both these games, but is contained in neither of these groups. But the groups G_M and G_T do capture the full orbit structure, since it is clear that central-strip and outer-strip moves in M-TTT really are inequivalent.

We have now solved tic tac toe on \mathbb{R}^2, the torus \mathbb{T}^2, the cylinder (since Cylinder-TTT is equivalent to Torus-TTT by exercise 4 of the previous post), and the Möbius strip M. There are two cases left to consider. In the following exercises, highlight for hints and answers.

1. Consider K-TTT, tic tac toe on the Klein bottle K. This is a square with both pairs of sides identified; one identification is parallel and the other is anti-parallel. Who wins? How many winning patterns are there? (Draw them!) Hint 1: Although you may not want to write down the group acting on the Klein bottle explicitly, note that the symmetries do act transitively. Hint 2: The standard winning patterns are three across, three vertical, and diagonals. How do the translations on the Klein bottle board affect the number of symbols in a given column for a given winning pattern? Answer: The first player always wins, with perfect strategy. There are 30 winning patterns.

2. The real projective plane is the last remaining possibility: both pairs identified, both anti-parallel. Solve this one as well: find the winning patterns and figure out who wins. Hint: Keep playing with it! Answer: Any three-square subset of the board is a winning pattern. Thus there are 9 choose 3 = 84 winning patterns, and the first player trivially wins in 3 with any strategy.

3. Try all six patterns with 4×4 boards. To start, are Torus-TTT and Cylinder-TTT still equivalent?

Advertisements

Responses

  1. […] course attentively since. So in this post, which is sort of an appendix to my previous posts (1, 2) on topological tic-tac-toe (henceforth called T4 for short), I will discuss the wider context of […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: