Neutral tic tac toe - MathOverflow

Neutral tic tac toe

2010-05-15T04:01:26Z

I heard this puzzle from Bob Koca. Suppose we play misere tic-tac-toe (a.k.a. noughts and crosses) where both players are X. Who wins?

That particular puzzle is easy to solve, but more generally, has $n \times n$ impartial tic tac toe, in both normal and misere forms, been studied before?

Answer by gowers for Neutral tic tac toe

2010-05-15T16:14:38Z

OK, let's first consider an even board and a straightforward strategy steal where the second player rotates the first player's moves by 180 degrees about the centre of the board. This works fine for horizontal and vertical lines, since if the second player completes such a line then the first player must have completed the 180-degree rotation of that line in the previous move. However, it runs into problems with diagonals.

The problem is that if you rotate a diagonal through 180 degrees you get the same diagonal, so the above proof that the strategy works breaks down.

What can we do about this? One idea is to try a slightly more complicated strategy steal. We'd like to choose a transformation that takes lines to lines such that no line is invariant. All the obvious transformations of order 2 -- reflections and half turns -- have invariant lines. So we could try a rotation through 90 degrees. Unfortunately, this doesn't work, since, denoting this rotation by R, if the first player plays point x and then point R^{-1}x, player 2 cannot play R(R^{-1}(x)).

But we could at least partition all the points on the board into quadruples of the form {x,Rx,R^2x,R^3x} and try to use this partition. What happens if the second player plays Rx if possible and R^{-1}x if it is not possible to play Rx? (It is easy to check that this strategy can be implemented.)

A simple lemma is that whenever player 2 plays a point y, R^{-1}y is already on the board. Here is the proof. If player 2 plays y, then either player 1 has just played R^{-1}y, or player 1 has just played Ry and the point R^2y was already played. Now if the point R^2y was already played, then either it was played by player 1, in which case player 2 would have played R^3y (unless it was already played, but that's fine too and is probably not possible -- no need to check), or it was played by player 2, which again could only have happened if player 1 had played R^3y.

Let me try again with a much nicer proof. How do quadruples of the form {x,Rx,R^2x,R^3x} fill up? Without loss of generality the first point to be filled is x. Then the next point has to be Rx. After that, when player 2 next plays a point in the quadruple all four points are played. Done.

Therefore, if player 2 completes a line ... damn, this doesn't work.

Let me end by showing that that whole strategy fails, since even though it doesn't answer the question it provides some evidence that strategy stealing isn't going to work. If player 1 knows that player 2 is going to adopt the 90-degree strategy steal, then player 1 can fill up the top row, starting from the left. Then player 2 will fill the rightmost column, starting from the top. This continues until player 1 is blocked by the top right corner. Player 1 then fills the bottom left corner and player 2 completes a line.

Obviously, it's not surprising that it failed, since it was a fairly unlikely idea in the first place.

A better approach

Here's another idea. Suppose we have a board of width 4m. Consider the transformation that adds 2m to the x and y coordinates, mod 4m. This takes horizontal lines to horizontal lines and vertical lines to vertical lines. It also takes diagonals to diagonals and is self-inverse. Unfortunately, the two diagonals are still invariant.

We can remedy that last problem by reflecting in a vertical line through the centre of the board. And if I am not much mistaken, the result is a new transformation that is still self-inverse, takes lines to lines, and has no invariant lines. (For that last property I needed the width to be a multiple of 4.)

So we can do it by strategy stealing after all, at least in this case.

Extra remark: the transformation I define above can be described as follows. Take the left half and right half of the board and reflect each one about a vertical line through its centre. Then translate the whole board vertically by 2m (mod 4m). The result is to send all vertical/horizontal lines to different vertical/horizontal lines and to interchange the two diagonals. It's easy to see that doing this transformation twice gives the identity.

Answer by Kristal Cantwell for Neutral tic tac toe

2010-05-15T17:08:53Z

We can extend this problem to higher dimensions.

I think I can solve the normal form for all dimensions and lengths of sides. For n is odd for all dimensions the strategy in Patrik's comment can be extended to higher dimensions with the first player choosing the center cell and then playing (n+1-i,n+1-j,...) unless there is a win and then taking the cell to complete the win. In this case the odd player wins.

For n is even there is a modification of the same strategy by the second player. The second player plays (n+1-i,n+1-j,...) unless there is a winning move and in that case taking the winning move. The second player will win in all dimensions when there is an even number of sides.

Answer by Kristal Cantwell for Neutral tic tac toe

2010-05-15T20:25:48Z

In misere tic tac toe on a 3x3 board with each player being x the first player will win. the first player will play (2,2) then WLOG the second player will play (1,1) or (2,3) then if the second player has played (1,1) the first will play (2,3). And if the second player has played (2,3) the first will play (1,1). Now there are four squares in which the second player can move without losing: (1,2),(1,3),(3,2) and (3,1). If the second player plays (1,2) the first player plays (3,1) and on the next move the second player must form a line of three and the first player wins. If the second player plays (3,1) the first player plays (1,2) and on the next move the second player must form a line of three and the first player wins. If the second player plays (1,3) the first player plays (3,2) and on the next move the second player must form a line of three and the first player wins. If the second player plays (3,2) the first player plays (1,2) and on the next move the second player must form a line of three and the first player wins. But this exhausts all cases so the first player must win in this game.

Answer by Kevin Buzzard for Neutral tic tac toe

2010-05-16T08:01:22Z

For what it's worth, here are a summary of the answers so far for the Misere game:

1x1: P2 win (poisoned chalice)

2x2: P1 win (P1 makes an arbitrary move)

3x3: P1 win (P1 plays in the centre, and his 2nd move is a knight's move away from P2's first move, and then solve by hand: see Kristal Cantwell's answer).

4x4 and more generally 4n x 4n: P2 win (strategy stealing: see gowers' "better approach")

5x5: P1 win (TonyK brute force computer search)

Answer by TonyK for Neutral tic tac toe

2010-05-19T10:18:54Z

Updated for the 4m+2 x 4m+2 case

At the risk of stating the obvious, the strategies described here for the 3x3 and 4n x 4n games can be described by simple pairings. For instance, the 4x4 pairing is:

a b c d
e f g h
b a d c
f e h g

Whatever move P1 makes, P2 makes the move with the same letter.

The 3x3 pairing is:

a b c
c * d
d a b

P1 plays in the central point *, and then follows the same rule as P2 in the 4x4 game.

When does such a pairing lead to a winning strategy? We require that whenever a line is formed by playing the pairing of a point on the grid, there must already be a line on the grid somewhere (so that the other player has already lost). The pairing must satisfy the following condition:

Let L be any line in the grid (row, column, or diagonal). Mark all the points of L with an X, and mark all the pairings of those points too. If n is odd, mark the central point * (P1's first move). Then for each point in L (that is not the central point *), if we erase it from the grid, the grid must still contain a line of X's.

This is always true if L's pairings form another line, disjoint from L; such is the case with the 4n x 4n pairings resulting from gowers' Better Approach. But it is also true for the 3x3 pairing given above, as you can check for yourselves fairly easily.

But there is no such pairing on the 5x5 board! This is rather messy, so I might skim over some details. Feel free to ask for clarification. Here the 'map' of a line L is the set of pairings of the points in L; the central point * is considered as being paired with itself.

Claim 1: No line L can contain both a point and its pairing. For then there would only be at most three paired points outside L, together with the central point *; and these four points can't be enough to form a line whenever a point of L is erased.

Claim 2: Any line L going through the central point * must map to a line that also goes through . For the pairs of the four non- points in L would otherwise not be enough to form a line whenever a non-* point of L is erased. Thus, if we call the union of Row 3, Column 3, and the two diagonals the asterisk-set, then points in (resp. outside) the asterisk-set must pair with points in (resp. outside) the asterisk set.

Claim 3: Any line L not going through * must map to a disjoint (and therefore parallel) line. For there are at most 6 X's outside the line; if four of these form a line K, intersecting L at point p, say, then erasing point p will leave the grid without a line (because the two remaining points, together with at most one point from L and one point from K, are not enough to form a line).

Claim 4: Any line L not going through * must map to a disjoint parallel line not going through *. For Claim 2 tells us that lines going through * map to lines going through *, and the pairing function is its own inverse.

Now, consider Row 1 and the row that it maps to under the pairing: Row r, say. The vertical bisector of the grid (Column 3) intersects these rows at points p1 and pr, say. Points on Row 1 not equal to p1 pair with points on Row r not equal to pr; so p1 must map to pr. This contradicts Claim 1. So there can be no such pairing. QED

This proof works for any odd n >= 5. It doesn't work for n=3, because Claim 3 fails: the two remaining points, together with at most one point from L and one point from K, are indeed enough to form a line.

Well, but one player has to have a winning strategy! Which one? We can answer this fairly easily for n=5, by brute force computer search, working backwards from the filled board by flagging all positions as winning or losing. There are only $2^25$ positions to consider, and the search takes about 30 seconds on my laptop. It turns out that the 5x5 board is a win for P1, who can make any initial move. (By contrast, in the 3x3 board the only winning move is the central point *.) This tells us two things: (i) P1 wins; (ii) the winning strategy is not a simple pairing.

Update The n x n case, with n = 4m + 2

There is no simple pairing strategy in this case, either. The analysis is simpler for even-numbered grid sizes. We just need:

Claim 1: No line L can contain both a point and its pairing. For then there would only be at most n-2 paired points outside L; and these points can't be enough to form a line whenever a point of L is erased.

Claim 2: Every line L must map to a disjoint line. For there are at most n paired X's outside the line; if n-1 of these form a line K, intersecting L at point p, say, then erasing point p will leave the grid without a line (because the one remaining points, together with at most one point from L and one point from K, are not enough to form a line).

This means that rows map to rows, columns map to columns, and the two diagonals map to each other.

Now, consider the point (a,a) on the leading diagonal. Suppose Row a maps to Row b, and Column a maps to Column c. Then the point (a,a) must be paired with the point (b,c), and this point (b,c) must be on the trailing diagonal: b+c = n+1. So Column a maps to Column c = n+1-b. Thus we have the following implication:

Row a maps to Row b => Column a maps to Column n+1-b

We can interchange rows and columns in this implication, so that

Column n+1-b maps to Column a => Row n+1-b maps to Row n+1-a

Combining these:

Row a maps to Row b => Row n+1-b maps to Row n+1-a

Now, a can't be equal to n+1-a, because n is even. And if a is equal to n+1-b, then Column a maps to Column a, which is not allowed. So we can partition the n rows into groups of the form (a, b, n+1-b, n+1-a). But this is clearly impossible if n is not a multiple of 4. QED

Answer by Thane Plambeck for Neutral tic tac toe

2010-05-24T22:15:33Z

It's possible to give a complete theory of 3x3 misere "X-only" tic-tac-toe disjunctive sums by introducing the 18-element commutative monoid $Q$ given by the presentation

$Q = \langle\ a,b,c,d\ | \ a^2=1,\ b^3=b,\ b^2c=c,\ c^3=ac^2,\ b^2d=d,\ cd=ad,\ d^2=c^2 \rangle\ $.

Such a "disjunctive" game of 3x3 neutral tic-tac-toe is played not just with one tic-tac-toe board (as has been previously discussed in this thread), but more generally with an arbitrary (finite) number of such boards forming the start position. On a player's move, he or she selects a single one of the boards, and makes an X on it (a board that already has a three-in-a-row configuration of X's is considered out-of-play). Play ends when every board has a three-in-a-row configuration, and the player who completes the last three-in-a-row on the last available board is the loser.

The game analyzed already in this thread corresponds to play on a 3x3 single board.

The monoid Q arises as the misere quotient of the impartial game

G = 4 + {2+,0}

{2+,0} is the canonical form of the 3x3 single board start position, and "4" is the nim-heap of size 4, which also happens to occur as a position in this game. I'm using the notation of John Conway's On Numbers and Games, on page 141, Figure 32.

One way to think of Q is that it captures the misere analogue of the "nimbers" and "nim addition" that are used in normal play disjunctive impartial game analyses, localized to the play of this particular impartial game, neutral 3x3 tic-tac-toe.

I performed these calculations partly using Mathematica, and partly using Aaron N. Siegel's "MisereSolver" program.