# Tic Tac Toe Recursive

Related: Connect 4 Recursive

We have a mega tic tac toe grid. Each of the nine cells of the mega grid has a smaller tic tac toe grid. In total we have 81 cells that can be filled. (Maybe imagine a Sudoku grid)

Alice starts by playing in any of the 81 squares. Now the grid in which the next player plays is determined by the previous move by the opponent. For example, suppose Alice plays in the top right corner cell of the grid at the top left corner of the mega grid. Now Bob has to play in the grid at the top right corner of the mega grid. He can play in any of the nine spaces there. If he, say, plays in the centre of that grid, Alice will have to play in the centre grid (but she choose which cell in it).

If a player gets three in a row in one of the nine grids, he/she is considered the winner of the grid and gains a point. Play however continues as per same rules. Any more three in a rows formed in the same grid are not counted or awarded points.

If a player is directed to a grid that already has all 9 cells filled, he/she can choose to play in any cell in any other grid (kind of the way Alice starts). Play continues as normal.

Play ends when all cells are filled (or the more likely instance when a player wins 5 points, and further play is pointless). Player with the most points wins.

If Alice and Bob play perfectly, who wins?

P.S. I spent some time on this, and while I feel the game is highly biased towards Alice, I wasn't able to find a simple enough strategy. Listing out of cases (maybe even by computer) may be required.

P.S.2 Computer programs are allowed, but it would be better to use them only as means to gain human-comprehendable insight.

There exists a simple no-computers solution, which has been posted.

• When I play this game you are allowed to play anywhere on an undecided board if you get sent to a won/drawn/lost board. – boboquack Jan 11 '17 at 23:04
• @boboquack The exact strategy for this game won't work there. You can always post that as a separate question. – ghosts_in_the_code Jan 12 '17 at 3:26
• The reason I said that is so that you can play a version without a definite winning strategy - it hasn't been solved yet. – boboquack Jan 12 '17 at 6:37

Alice wins.

She starts by playing in the center square of the center board (which we'll call board C). Bob sends Alice over to another board, and she plays in the center of that one. Eventually, Bob fills up the rest of the middle board, and Alice then has the center of all but one of the outer boards.

On that turn, Alice takes the "self-square" of the board Bob forced her to play on. (Let's call it "board X".) She keeps sending Bob back to board X, just like she did in the center board at the beginning.

The one exception is if Bob plays in the center of board X. In that case, Alice plays as if Bob had sent her to the board opposite board X - let's call it board Y.

Now, Alice will be sent to board Y twice: once from the "Y-square" of board X, and once from the center square of board X. The first time, she sends Bob back to board X as usual. The second time, she plays in the Y-square of board Y.

Now, Alice has board Y. She can now safely send Bob back to either X or Y on every turn, and he can't do anything about it. Since spaces X, C, and Y are all taken on the three boards, Bob can't escape the XY boards. Alice then claims the unclaimed X and Y squares on every unnamed board and wins the game.

To have this strategy tried against you, you can play here.

• Oh ok, so the game is not original. I didn't know that. I invented couple of rules such that rows in an already won grid are not counted, etc. but turns out even those are implemented. Anyways, thanks so much for the same. P.S. So that means you also copied the solution from the Khan academy site? – ghosts_in_the_code Jan 11 '17 at 14:49
• @ghosts_in_the_code: No, I'd heard parts of it before and used that to solve it myself. It's very similar to the Connect 4 question you asked earlier. (I'm honestly not sure if the code does exactly my strategy, but I tried it out and it seems to be pretty close.) – Deusovi Jan 11 '17 at 14:53
• @ghosts_in_the_code The main game is not original - I have heard somebody call it 'meta naughts and crosses' or 'meta tic-tac-toe' but this version is original-ish. The actual two player version (and the one that's not just a puzzle) has the rule that a mini board is won if there exists a three in a row on it. If you are sent to a board that's won then you can play anywhere (even if the won game has extra space on it). Three in a row on the big board wins. – Wen1now Jan 12 '17 at 6:12