Joachim Breitner's Homepage

Categories

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.

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.

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

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.