Swirly Mein Kopf

Tuesday, July 16. 2013

Ultimate Tic Tac Toe is always won by X

Digital World

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.

Trackbacks


No Trackbacks

Comments

Display comments as (Linear | Threaded)

*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 on 2013-07-16 14:26 (Reply)
*That is a variant later added, precisely because of the known winning strategy without.
#1.1 Joachim Breitner (Homepage) on 2013-07-16 15:26 (Reply)
*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 :-)
#2 Konrad Voelkel (Homepage) on 2013-07-16 17:28 (Reply)

Add Comment



To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA

Gravatar, Favatar, Identica author images supported.
What is the first name of the owner of this blog? / Wie heißt der Betreiber dieses Blogs mit Vornamen?
 
 
Nach oben