Wednesday, 12 June 2013

Tic Tac Toe Variation

In second grade math homework there was an interesting variation of Tic-Tac-Toe designed to teach addition and subtraction. Take a 3 x 3 grid and randomly give each square a different number between 2 and 18. We have two players X and O.

Play goes as follows:
  1. Player X chooses a number from 1 to 9.
  2. Player O chooses a number from 1 to 9 that she had not picked before.
  3. Player O adds that number and the last number picked from X and if that square is on the board and unmarked, that square is marked O.
  4. Player X chooses a number from 1 to 9 that he had not picked before.
  5. Player X adds that number and the last number picked from O and if that square is on the board and unmarked, that square is marked X.
  6. Go to step 2.
Play ends when either X or O has three in a row and is declared a winner or when all the numbers run out and the game is declared a draw.

Here is an example:
12 |  5 | 7
-----------
14 | 11 | 3
-----------
4  | 13 | 9
 
X: picks 1, O: picks 3 (to make 4), X: 8 (11), O: 4 (12), X: 3 (7), O: 6 (9). At the point the board looks like:

 O |  5 | X
-----------
14 |  X | O
-----------
 O | 13 | O
 
Defensively X plays 2, Y: 1, X; 1, Y:2 and whatever X plays next Y has a forced win by making 13 or 14.

Despite the simplicity this is quite a challenging game. For every initial configuration, is there always a forced draw like in real Tic-Tac-Toe or do some configurations have a forced win for X or O? How complicated is it to compute an optimal strategy?

I couldn't figure out the best strategy either. Amazing what complicated things can come out of a second-grade class.