Computational Complexity

Thursday, November 14, 2002

 
Tic Tac Toe Variation

Posted by Lance

In my daughter's 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?

My daughter was frustrated at how hard it is to win this game but she shouldn't be ashamed--I couldn't figure out the best strategy either. Amazing what complicated things can come out of a second-grade class.

9:53 AM # 0 comments

Comment Feeds: This Post All