# Neutral tic tac toe

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?

-
For even $n$ and the normal rules, player two has a winning strategy by reflecting (across say the horizontal axis) whatever player one does. Using this strategy, P2 can't play the second-to-last X in a column, and if he were to play the second-to-last X in a row, that would imply the opposite row already has only one open spot left, so he can play to win. The same argument works for the diagonal. – Kevin Ventullo May 15 '10 at 7:17
In the odd case player one plays in the middle and then plays (i,j) when player two plays (n+1-i,n+1-j), unless there is a winning move. PLayer one can then not be the first to create a winning move for his opponent. If the move (i,j) creates a winning move along row i then there is a winning move along row n-i before that, and the winning move can not be along a line trough the center since player two can never be last to play along such lines by parity). – Patrik May 15 '10 at 8:54
If I understand the terminology correctly, Kevin and Patrik have analysed the normal version of the game, where the objective is to form a line of Xs, whereas in the misere version, the first player to form a line of Xs loses. – Reid Barton May 15 '10 at 14:17
I asked Thane Plambeck if he had heard of this problem before, and he said no, but it reminded him of the game Treblecross. madras.fife.sch.uk/maths/games/treblecross.html – Timothy Chow May 17 '10 at 4:02
To Kevin Ventullo: I don't get it (your strategy for the normal game on an even length board), why can't the first player complete a row? – Zsbán Ambrus May 19 '10 at 6:43

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.

-
You're not going to find a P2 strategy stealing argument for a general even board---consider the 2x2 case! – Kevin Buzzard May 16 '10 at 7:50

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)

-

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

-
The reason any move other than the centre loses for P1 in the 3x3 game is that P2 can respond with a move diametrically opposite P1's initial move. This makes the centre square unplayable, and then P2 just plays the "180 degree rotation" strategy which clearly wins. – Kevin Buzzard May 19 '10 at 17:47

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.

http://arxiv.org/abs/math/0501315

http://arxiv.org/abs/math/0609825

http://www.miseregames.org

It's possible to build a dictionary that assigns an element of Q to each of the conceivable 102 non-isomorphic positions in 3x3 single-board neutral tic-tac-toe. (I mean "non-isomorphic" under a reflection or rotation of the board. In making this count, I'm including positions that couldn't be reached in actuality because they have too many completed rows of X's, but that doesn't matter since all those elements are assigned the identity element of Q). To determine the outcome of a multi-board position (ie, whether the position is an N-position -- a Next player to move wins in best play, or alternatively, a P-position-- second player to move wins), what a person does is multiply the corresponding elements of Q from the dictionary together, and reduce them via the relations in the presentation Q that I started with above, arriving at a word in the alphabet a,b,c,d.

If that word ends up being one of the four words {a, b^2, bc, c^2 }, the position is P-position; otherwise, it's an N-position.

I'm guessing the the 4x4 game does not have a finite misere quotient, but I don't know for sure.

If people want more details, I'm happy to send them. Google my name for my email address.

Best wishes

Thane Plambeck

Postscript (added 8 Jan 2013) Here's a paper http://arxiv.org/abs/1301.1672 I just put up in the arXiv that has more details.

-

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.

-
No, in the 3x3 misere game, the first player wins by playing in the center and then wherever the second player plays, the first player plays a knight's move away from that. I think that in your analysis you confused the misere and normal forms in the middle somewhere. – Timothy Chow May 16 '10 at 2:01
Yes what I had before was in error. I corrected it and it follows your analysis. – Kristal Cantwell May 16 '10 at 3:36

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.

-