## Wednesday, December 28, 2011

### 126: Tic Tac What?

Recently my daughter Sonia has become obsessed with the game of tic-tac-toe.  You know, the classic diversion where two players take turns marking squares in a 3x3 grid, one with Xs and the other with Os, and try to get 3 in a row.  The number of possible moves seems large:  since there are 9 possible squares to be first chosen, then 8 for the move after that, and so on, and the game has to last at least 5 turns for someone to make three marks and win, there are at least 9*8*7*6*5, or 15,120 possible games, and  significantly more if you take into account the possibility of longer games.  According to Wikipedia, the total comes to 255,168.  But on the other hand, the game board is very symmetrical, and if you start playing you realize the game quickly falls into a small number of standard patterns; Wikipedia calculates there are only 138 unique outcomes.  Everyone listening to this podcast has probably realized long ago that the key to playing is to try to create a situation where you have two possible threes-in-a-row, so your opponent will be unable to block-- but any player can always prevent their opponent from laying such a trap, so the optimal strategy will always lead to a tie.  Is there anything more to say about this game?
Recently Cambridge University Press has been re-releasing the many tomes of Mathematical Games essays written by Martin Gardner for Scientific American, and I was happy to see that the first volume contains an article on this topic.  One surprising point Gardner makes is that while it is true that an optimal opponent can always force a tie, what if you assume your opponent is not quite optimal?  For example, suppose you are playing someone who opens with a 'side move', putting an X in the middle bottom square, rather than the center or a corner.  Normally you have a choice of several squares to place your O in that will prevent a trap & eventually force a tie.  But what if you choose a seemingly silly move, and put your O in the upper right corner?  This leaves the X player a chance to set up an inevitable victory-- but only if he chooses the lower right.  Anywhere else, and he leaves you at worst with a tie; and there are several choices which will let you lay a trap for him, and win.  So if you take a chance that your opponent will mess up, you can give yourself a shot at victory, where otherwise you would at best have a tie! This lesson probably applies to other parts of life somehow as well.
Another amusing discussion in Gardner's essay is the many variants of tic-tac-toe that have arisen over the years.  Since ancient times, in cultures as diverse as Greece, China, and Rome, a version was played that became known in England as "Three Men's Morris".  In this variant, once 6 moves have been made, rather than placing additional marks in the last three squares, players take turns shifting an exiting mark from its current square to an adjacent one.  Apparently in Book III of Ovid's "Art of Love", he advises women to master this game in order to be more popular among men.  So, if your love life has been having trouble lately, you better get out that tic-tac-toe board and start practicing!
Some additional variants include the obvious extensions to 4x4 or 5x5 boards.  Naturally, these make the counter-moving versions of the game much more interesting, as your choices are much less restricted.  Other variants are a bit more creative:  one called "toetacktick" is the same game as standard tictactoe, except that the first person to get 3
in a row *loses*.  There are also 3-d variants, where you effectively have a 3x3x3 cubic board.  Surprisingly, the 3x3x3 board makes a very bad game, since unlike the 2-d version, the first player has an optimal strategy that will always lead to victory.  A 4x4x4 board is a little better, allowing for more variety.  Though in 1988 a complex computer program was developed which can always win this version as well.
Of course, there is no reason to limit yourself to three dimensions just because of pesky little properties of our universe, is there?  Another variation takes place on a four-dimensional hypercube.  To play it, you need to project it down to a set of three-dimensional or two-dimensional images, in order to diagram what moves you are making on the imagined four-dimensional object.  It can also get a little tricky to reverse your projection and remember which squares are adjacent to which, in order to figure out who won.  Gardner draws a nice diagram accompanying his essay, but I think most non-mathematicians would find this variant a bit challenging.  What makes it worse is that the size of the hypercube needs to be at least 5x5x5x5 to rule out simple strategies that would enable an inevitable victory for the first player.
Wikipedia also points out some more interesting variants.  One game that can be proven equivalent to tic tac toe is the following:  Take turns saying a number between 1 and 9 out loud.  You cannot repeat a number used by your opponent.  If you say three numbers that total 15, you win!  You can see this is equivalent by drawing a magic square, a 3x3 square with numbers from 1 to 9 such that 3 in a row always total 15-- in effect, each player is stating the number in the square of their next tic-tac-tow move.  More bizarrely, Quantum Tic Tac Toe combines the standard game with principles of quantum mechanics, where particles may be in a probablistic "superposition" of multiple locations:  each turn you label multiple squares, and each square can have multiple 'spooky marks'.  In certain cases, your quantum marks from multiple squares collapse into a single "classical" mark on one square, and you win if you cause the collapses in such a way as to get three in a row.  The wikipedia page in the show notes has a link to a java applet so you can try this game if you want.
Before I get around to teaching Sonia all these variants, though, I should probably try to teach her to complete the row of three Os and win the game when I leave her an obvious opening.
And this has been your math mutation for today.

• Tic Tac Toe at Wikipedia
• Quantum Tic Tac Toe at Wikipedia
• Martin Gardner at Wikipedia