SwirlyMyself

2013-07-16T10:59:21+00:00

Ultimate Tic Tac Toe is always won by X

The blog Math with Bad Drawings recently featured an article about Ultimate Tic Tac Toe, a variant of Tic Tac Toe where each of the nine fields is a separate game of Tic Tac Toe. To mark a field of the large game as your, you have to win the small game therein. If you chose a field in the small game, this position determines the small field that the other play may play next. See the linked article for a full explanation.

As far as I know, the question of who wins this game was open; at least nothing definite was known on Hacker News or on the Board Games StackExchange site. We discussed this a bit in our office, and my coworker Denis Lohner came up with what seems to be a winning strategy.

Update: Not surprising, but with these variants of the rule, the winning strategy was already known.

Strategy

Assume Denis (⨯) plays against me (○). Like most suggestions for a winning strategy for the first player, Denis (X) starts with the middle:

   │   │   
   │   │   
   │   │   
───┼───┼───
   │   │   
   │ ⨯ │   
   │   │   
───┼───┼───
   │   │   
   │   │   
   │   │   

Now I have to put my ○ in the center field of the center game. No matter where I place it, Denis will send me back ot the middle, until one field of the center game is free. Doing this eight times inevitably puts us in a position like this:

   │   │   
   │ ⨯ │ ⨯ 
   │   │   
───┼───┼───
   │○○○│   
 ⨯ │○⨯○│ ⨯ 
   │○○○│
───┼───┼───
   │   │   
 ⨯ │ ⨯ │ ⨯ 
   │   │   

The only way I can influence the game is by chosing which ○ I place last; this determines where Denis goes now. But (and please verify that carefully) it will not matter: The only thing required from that field is that there is a second field that, together with the center, forms a row (or column or diagonal); all fields satisfy that. Assume I placed the top-left ○ last, and Denis has to go there. He will send me to that field:

⨯  │   │   
   │ ⨯ │ ⨯ 
   │   │   
───┼───┼───
   │○○○│   
 ⨯ │○⨯○│ ⨯ 
   │○○○│
───┼───┼───
   │   │   
 ⨯ │ ⨯ │ ⨯ 
   │   │   

Now the game of the first field is repeated: Whereever I send him, he will send me back. This works great for all fields but the middle field. The middle field is special: When I send him there, he has the free choice. He will pick the bottom-right game.

  • If I send him to the center field before I send him to bottom-right, he will put the ⨯ in the top-left corner of that field, sending me back. Once I send him to bottom-right then, he will put the ⨯ in the bottom-right corner of that field.
  • If I send him to the center field after I sent him to bottom-right, he will put the ⨯ in the bottom-right corner of that field.

In any case we will end up in this situation: I won the center game; I likely have a few ○ in the top-left game. To be precise: I have a ○ there if and only if the he has a ⨯ in the top-left corner of the corresponding game. He also has the diagonal of the lower-right game. For example:

⨯○○│⨯  │⨯  
 ○○│ ⨯ │ ⨯ 
  ○│   │   
───┼───┼───
   │○○○│⨯  
 ⨯ │○⨯○│ ⨯ 
   │○○○│
───┼───┼───
   │   │⨯  
 ⨯ │ ⨯ │ ⨯ 
   │   │  ⨯

I have to put my mark in the lower-right game now. From now on, whereever I go, he will send me to either to the top-left or bottom-right game. I can do nothing about it (I cannot send him to the diagonal any more, and whereever I send him there is at least one of the top-left or bottom-right fields fee), so he wil easily win all the other games by getting the diagonal. Eventually, he wins the whole game with the bottom row or the right column:

⨯○○│⨯  │⨯  
 ○○│ ⨯ │ ⨯ 
○○○│   │   
───┼───┼───
⨯  │○○○│⨯  
 ⨯ │○⨯○│ ⨯ 
   │○○○│
───┼───┼───
⨯  │⨯  │⨯  
 ⨯ │ ⨯ │○⨯ 
  ⨯│  ⨯│○○⨯

This is not a formal proof yet, but hopefully close enough to convince you, or alternatively allow you to precisely describe how you can prevent losing against Denis’ strategy.

Comments

But I thought that, if a square was won, it couldn't be used; therefore you can't be sent back to the middle 8 times because you'll have won it after 3 iterations.
#1 Peter am 2013-07-16T12:26:56+00:00
That is a variant later added, precisely because of the known winning strategy without.
#2 Joachim Breitner (Homepage) am 2013-07-16T13:26:59+00:00
Nice write-up! I also suspected that such a strategy would always win but haven't thought it through thoroughly. Now I have to play the variant Peter alludes to next :-)
#3 Konrad Voelkel (Homepage) am 2013-07-16T15:28:06+00:00

Have something to say? You can post a comment by sending an e-Mail to me at <mail@joachim-breitner.de>, and I will include it here.