Growing Sprouts

The game of sprouts has a way of growing on you.

This two-person, pencil-and-paper game is simple enough that children can play it. Yet its intricacies provide much food for mathematical thought.

The players start with a number of dots scattered across a sheet of paper. A move consists of drawing either a line connecting two dots or a loop starting and ending at the same dot. With each move, the player then places an additional dot somewhere along the new line or loop.

The line (or loop) may be of any shape, but it must not cross itself, cross a previously drawn line, or pass through a previously made dot. Furthermore, no dot may have more than three lines emanating from it. Indeed, a new dot placed on a line starts off with two connections already made.

Players take turns drawing curves. The winner is the last person able to play.

At first glance, it may seem that a game could keep sprouting forever. However, because each turn makes two connections to dots and opens up only one new opportunity for a link, the number of moves has a definite limit. In fact, you can prove that a game starting with n dots must end after a maximum of 3n − 1 moves.

Initially, there are no lines, so the dots have a total of 3n possible links. Each move uses up two of those openings, at the beginning and end of the drawn curve, but also adds a new dot with one opening. Thus, each move decreases the number of openings by one. Because a move requires filling two openings, the game can't continue when only one opening remains. Hence, no game can last beyond 3n − 1 moves.

You can also show that every game must go at least 2n moves. Thus, a game starting with three dots must end on or before the eighth move and must last at least six moves.

A typical three-dot sprouts game.

For a small number of dots, one can diagram all the possible moves and determine which player is guaranteed a win. The second player can always win a game starting with two or six dots. The first player is guaranteed a win in games involving three, four, or five dots.

In 1991, David Applegate, Guy Jacobson, and Daniel Sleator used a lot of computer power to push the analysis of sprouts out to 11 dots. They found that the second player wins in games involving seven or eight dots, while the first player wins in games involving nine, 10, or 11 dots.

There's an interesting pattern here. The researchers conjectured that the first player has a winning strategy if the number of dots divided by six produces a remainder of three, four, or five. Hence, their prediction for a game involving 12 dots is a win for the second player (the remainder is zero after dividing 12 by six).

Games can sprout all sorts of unexpected growth patterns, making formulation of a winning strategy a tricky proposition. Toward the end of a game, however, you can often see how to draw closed curves that divide the plane into regions in such a way as to lead to a win.

The game has also attracted the attention of mathematicians, who have investigated the game in terms of graph theory and topology. It's possible to try sprouts, for example, on a doughnut-shaped surface or in higher dimensions.

Sprouts was invented in 1967 by mathematicians John H. Conway and Michael S. Paterson, when both Conway and Paterson were at the University of Cambridge. "The day after sprouts sprouted, it seemed that everyone was playing it," Conway once wrote. "At coffee or tea times, there were little groups of people peering over ridiculous to fantastic sprout positions."

Piers Anthony picked up on the sprouts craze in his science-fiction novel Macroscope (Avon, 1969). "Sprouts is an intellectual game that has had an underground popularity with scientists for a number of years," one character in the novel noted. "The rules are simple. All you do is connect the dots."

Anthony then proceeded to illustrate with a sample three-dot game that runs for six moves, with a win for the first player.

"It's not a game," protested another character in Macroscope. "There's no element of chance or skill."

Nonetheless, the possibilities are sufficiently vast that sprouts and its variants offer a great of deal of enjoyment for both player and mathematician.

Original version posted April 7, 1997