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, investigating 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.
Since everyone already knows that, with best play, Tic-Tac-Toe is a draw, I won't perform a detailed analysis of the best strategy for the game here. I will ask this 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 find.
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 (such polyominoes are 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...
Sources used (see bibliography page for titles corresponding to numbers): 44.