Tic-tac-toe (also spelled tictactoe, ticktacktoe, or tick-tack-toe, and also referred to as noughts and crosses or X's and O's) is one of the world's simplest games. It's also one of the most ubiquitous, with game boards found on toys, in graffiti, and even children's playground equipment (right). One could wonder how there could be any mathematical interest in it whatsoever. After all, everyone who is old enough knows that, with best play, neither player can force a win in standard tic-tac-toe (i.e. on a 3×3 grid). Still, looking at tic-tac-toe can be a useful introduction to combinatorial game theory. Furthermore, there are several variations that could be played, such as altering the board or the winning conditions, that could make the game interesting. For example, the first player has an easy win with three-in-a-row tic-tac-toe on a 4×4 (or larger) board.
Tic-Tac-Toe is a simple enough game that analyzing it could provide a good introduction to game theory. Since everyone already knows that, with best play, the game is a draw, this analysis won't be performed here. I will ask the question, though, if you are the second player, what first move should you make to help ensure a draw?
If the first player chooses the centre square to start, the second player, in order to not lose, must select one of the corner squares. If the first player plays first in the corner square, the second player must select the centre square. If the first player selects a side square, there are several possibilities. See the images on the left for more information.
If you're the first player, you might think that your probability of winning is better if you take the corner square, but that's not necessarily true unless your opponent is playing at random, because the only move that leads to a draw (take the centre square) is easier to ffind.
Here are some interesting variations of tic-tac-toe that you may want to try out. Think about whether one player or another has a winning strategy, a plan they can follow that guarantees that they will win every time:
Martin Gardner once wrote a Scientific American column (found in his book Fractal Music, Hypercards and More...; see the bibliography for more information on the book) on "Generalized Ticktacktoe". The generalization is as follows: Choose a polyomino (called "animals" by Frank Harary, who devised this generalization) and declare its formation to be the objective of the tic-tac-toe game. Each player tries to fill in cells that will form the desired animal. Rotations and reflections are okay.
An interesting idea is to look at each of the polyominoes and find two properties of that polyomino: The length of the side of the smallest square on which the first player can force a win (b), and the number of moves required on this board (m). Here are some "animals" of 1 to 4 cells (aside: polyominoes of four cells are called tetrominoes, and should be familiar to anyone who as played Tetris), their "names", and their b and m values.
Note that the 2×2 square, nicknamed "Fatty", is a "loser". That is, the first player can never force Fatty on a board of any size. Note that any polyomino containing any smaller loser is also a loser. This makes sense, since if you can never force a 2×2 square, for example, you can't force (say) a 3×3 square either, since to construct a 3×3 square you have to create a 2×2 square. As a matter of fact, most polyominoes of size 5 or greater are losers. There are only three pentominoes and (probably) one hexomino that are winners:
Since almost every heptomino (size 7) or larger will contain at least two different hexominoes, and there is no more than one winning hexomino, it is not too hard to show that all 107 order-7 animals contain a smaller loser and thus are losers themselves.
Another question: Is there ever a winning strategy for the second player? This is a pretty easy question to answer. Assume that, for some shape, the second player does have a strategy. Then the first player could win by starting with some irrelevant move and thereafter following the second player's winning strategy. Making an extra move is never a liability in tic-tac-toe, even generalized tic-tac-toe. We have reached a contradiction, so our assumption that the second player can ever have a winning strategy is false. The moral of the story is: go first!
One last tic-tac-toe item: If you play a normal game of tic-tac-toe with someone else and let him/her go first, what is the probability that s/he will start with an X? It is certainly greater than 50%. As a matter of fact, it's probably close to 100%. Interesting, eh?
However, I have seen a tic-tac-toe set in the toy section of a department store that contained five O's and four X's, which would require O to go first. Maybe at least one toy designer thinks differently than most people...