[Math] A non-losing strategy for tic-tac-toe $\times$ tic-tac-toe

algorithmic-game-theorygame theorytic tac toe

Consider a $9 \times 9$ matrix that consists of $9$ block matrices of $3 \times 3$. Let each $3 \times 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 $\times$ tic-tac-toe.

Now question:

We know tic-tac-toe has a non-losing strategy. Does tic-tac-toe $\times$ 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.

Best 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 = $P_1$, Player 2 = $P_2$): Suppose there is a non-losing strategy $S$ for $P_2$. Then $P_1$ will start the game with a random move $X$, and for whatever $P_2$ will do, follow strategy $S$ (thus $P_1$ takes on the role of being the second player). Since $S$ is a non-losing strategy, $P_1$ will not lose, which means $S$ is a non-losing strategy for $P_1$.

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

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