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.
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.
Have something to say? You can post a comment by sending an e-Mail to me at <email@example.com>, and I will include it here.