[Math Lair] Tic-tac-toe

Math Lair Home > Topics > Tic-tac-toe

[The Traditional Game | Variations | Generalized Tic-Tac-Toe | Other Stuff]

A game of tic-tac-toe in a parkTic-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.

The Traditional Game

Second player's drawing moves when the first player chooses the centre square Second player's drawing moves when the first player chooses a corner square Second player's drawing moves when the first player chooses a side square

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.

Variations

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:

Your Choice Tic-Tac-Toe
Each player may put down either an X or an O on each of their turns, and may change their mind from turn to turn. The winner is the one who finishes any row, column, or diagonal of all X's or all O's.
Magic Square Tic-Tac-Toe
Instead of X's and O's, the numbers 1 through 9 are used. Each number may be used only once. The winner is the one to get the numbers in any row, column, or diagonal to add up to 15. Question: Can you determine a winning strategy for this variant?
Last One Wins
On a player's turn, that player marks as many non-empty spaces as they like, as long as they are in the same row or column (not diagonal). Whoever fills in the last space wins.
Avoidance Tic-Tac-Toe (also known as Misère Tic-Tac-Toe or Toe-Tac-Tic)
Same order of play as the standard game, except that a player who completes three in a row loses.
Drawbridge
Same order of play as the standard game, only one player wins if the game is a draw, while the other wins if either completes three in a row.
Movable Markers
Players have three counters each and take turns placing them on the grid. If neither has won after all six counters are down, players may move one of their counters somewhere else as their move.
Hot
Each of the words HOT, HEAR, TIED, FORM, WASP, BRIM, TANK, SHIP, and WOES is printed on a card. Players take turns withdrawing cards from the pile. The first to hold three cards containing the same letter wins. An alternate version of this game uses the cards FISH, SOUP, HORN, KNIT, VOTE, ARMY, CHAT, SWAN, and GIRL. Question: Why is this listed under tic-tac-toe variants? Think about it.
The Numbers Game (or Fifteen)
Players take turns selecting a number between 1 and 9. Each number may be selected only once. The first person to accumulate three numbers whose sum is 15 is the winner. Question: Why is this listed under tic-tac-toe variants? The magic squares page may provide a hint.
Multi-Player Tic-Tac-Toe
For three to six people, try a giant board, one that is at least 10×10, perhaps infinite. Four in a row wins this variant.
Ultimate Tic-Tac-Toe
Ultimate tic-tac-toe is played on a 3×3 board, but each square contains a 3×3 board of its own. Players alternate turns marking individual squares on one of the small boards. If you win one of the little boards, you can mark the big square as X or O. What makes this game interesting is that you can't simply choose any of the nine boards to play on; you must choose the board located in the large square corresponding to the small square that your opponent just marked. So, for example, if your opponent just marked the upper left corner in the middle board, you must play somewhere in the upper left board.
3-D Tic-Tac-Toe
Play on a 4×4×4 board; the goal is to get 4 in a row. There are a lot of computer games of this version of tic-tac-toe. One of the earliest was a video game for the Atari 2600.

Generalized Tic-Tac-Toe

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.

[Animals of 1 cell through 3 cells][Tetrominoes]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:

[Winning Pentominoes and Hexominoes]

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!

Other Thoughts

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.