A non-losing strategy for tic-tac-toe ×\times tic-tac-toe

Consider a 9×9 matrix that consists of 9 block matrices of 3×3. Let each 3×3 block be a game of tic-tac-toe. For each game, label the 9 cells of the game from 1 to 9 with order from left to right, from above to down, call this a cell number. Label the 9 games of the big matrix 1 to 9 with the same order, call this a game number.

The rule is the following:

1. Player 1 starts with any game number and any cell number.

2. Player 2 can make a move in the game whose game number is the cell number where player 1 made the last move

3. It continues like this, where player 1 then plays in the game whose game number is the cell number where player 2 made the last move.

4. Special case, when a player is supposed to play in game X, but game X is already won (may not be full)/lost (may not be full)/drawn (is full), then he may choose to play in any game he wants.

5. Winning: whenever a player has three winning games such that the three games line up either horizontally, vertically or across the diagonals, he wins.
Tic tac toe

It is easy to see why we call it tic-tac-toe × tic-tac-toe.

Now question:

We know tic-tac-toe has a non-losing strategy. Does tic-tac-toe × tic-tac-toe have a non-losing strategy? If so what is it? In general what is a good strategy?

PS: This is a fun game. Originally what was a ‘good move’ now sends your opponent to a ‘good game position’, so it is more complicated.

Answer

The first question, if there is a non-losing strategy, I have an answer for: Yes.

Since this is a finite two-person perfect information game without chance, at least one player must have a non-losing strategy, guaranteed by Zermelo’s theorem (of game theory).

For Tic-Tac-Toe related games, it can be proven that the first player has this non-losing strategy. (If it is a winning strategy depends on whether or not the second player has a non-losing strategy).

The argument goes something like this (Player 1 = P1, Player 2 = P2):
Suppose there is a non-losing strategy S for P2. Then P1 will start the game with a random move X, and for whatever P2 will do, follow strategy S (thus P1 takes on the role of being the second player). Since S is a non-losing strategy, P1 will not lose, which means S is a non-losing strategy for P1.

Note that, if strategy S ever calls for making the move X (which was the original random move), P1 may simply do another random move X2 and then keep following S as if X2 had been the original random move. This is further explained in page 12-13 here.

(EDIT: Since the first move P1 affects what move P2 can do (by rule 2) the latter argument may not apply to this game. Anyone?)

Attribution
Source : Link , Question Author : mez , Answer Author : naslundx

Leave a Comment