58
$\begingroup$

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.

$\endgroup$
18
  • 5
    $\begingroup$ This game appears of recent invention, and has gained in popularity, probably because a winning or non-losing strategy is unknown. $\endgroup$
    – vadim123
    Jul 3, 2013 at 23:41
  • 11
    $\begingroup$ As this is a finite combinatorial game, unless I'm missing something, it's trivially true that at least one player has a non-losing strategy. Is there an obvious reason we should expect this game to be computationally difficult to solve? $\endgroup$
    – Nate Eldredge
    Jul 4, 2013 at 3:14
  • 2
    $\begingroup$ Is a game considered drawn when the board is full, when neither player has a winning strategy(!) or when there are no possible places to achieve 3 in a row? $\endgroup$
    – not all wrong
    Jul 4, 2013 at 9:12
  • 3
    $\begingroup$ @NateEldredge What symmetries are you thinking of? The 'must move in the named cell' rule seems to eliminate all but the simple global symmetries, and those don't reduce the solution space by more than a ($D_4$) factor of $8$... $\endgroup$
    – Steven Stadnicki
    Jul 7, 2013 at 3:32
  • 4
    $\begingroup$ One small thing that might be worth noting: since a placed move can 'block' a square and force a player to move in a cell that will let the opponent make a more advantageous move, it's not the case that a mark on the board is always to the benefit of the mark's owner (unlike regular tic-tac-toe); this means that there's no standard strategy-stealing argument to show an edge for the first player. $\endgroup$
    – Steven Stadnicki
    Jul 7, 2013 at 3:35

3 Answers 3

Reset to default
9
$\begingroup$

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?)

$\endgroup$
2
$\begingroup$

I think it is possible to "control" the board by having many sub-games "point" to a square that has already been won in the larger game, preventing your opponent from blocking you in that square, and driving you towards marking other squares, so eventually you have 2 in a row in many sub-games, eventually forcing your opponent to let you go on a sub-game-winning spree.

For example, taking square 3 on a number of boards will essentially give your opponent sub-game #3, but from there on, you could start taking squares 1 and 2, or 5 and 7, or 6 and 9; all of which "point" to square 3 in their respective games. Thus, in order to block you in a sub-game that already has such a "pointer", they must allow you to take a move wherever you want after their turn, forcing them to allow you to either take a square (at leisure) or continue to set yourself up for more "pointers". Opponents placing moves elsewhere tend to fall even further behind, as they cannot overtake your offensive lead, and can't block you efficiently.

There is also a "gambit" strategy, where you keep selecting the same block in each sub-game thereby sacrificing one sub-game for the sake of getting a head-start in many others.

EDIT: Elaborating on the strategy explanation

$\endgroup$
4
  • 3
    $\begingroup$ I'm a bit confused with your explanation, could you please expand on that? $\endgroup$
    – mez
    Jul 10, 2013 at 3:33
  • $\begingroup$ Does that help clarify? $\endgroup$
    – bythenumbers
    Jul 10, 2013 at 16:38
  • $\begingroup$ No. you opponent doesn't have to block you. he can simply not send you to the square where you have 1 and 2. And you can have too many 1 and 2, because that means you gave him too many chances in game 1 and game 2, which you don't want, since he already won game 3. This is far less than a strategy that I am talking about, merely an observation. $\endgroup$
    – mez
    Jul 11, 2013 at 14:51
  • $\begingroup$ I'm saying to do this in multiple sub-games, while varying the pointer you use. All pointers point to the sub-game you gave him, but they're varied. 1 and 2, 5 and 7, and 6 and 9 are all valid "pointers" if game 3 has already been won. It forces your opponent to be sent to different sub-games all the time, while you're getting 2/3 in a bunch of them. Eventually, you'll be able to start taking sub-games as he sends you to them, or he'll block one of your "pointers", allowing you to take whatever game you like. It's a vague strategy, but it should still be valid. $\endgroup$
    – bythenumbers
    Jul 17, 2013 at 12:37
0
$\begingroup$

You may find these observations helpful:

  • Throughout the play, each of the games becomes more advanced, meaning that it has more moves made in it. This might be obvious, but it's vital for the players to avoid pointing at the advanced games.
  • The advanced games are more valuable to play in, as all of the opponents moves made there are wasted when a game is lost.
  • A move in an advanced game has more defensive potential, especially when the opponent made it to the point where they could have had a winning move
  • From my experience, draws in games happen rarely and leading the entire board to a draw is nearly impossible without a draw in the central game

A winning strategy should involve forcing the opponent to let you play in the advanced games and sending them to the open ones.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .