Sprouts (game)

Sprouts is a pencil-and-paper game with interesting mathematical properties. It was invented by mathematicians John Conway and Michael S. Paterson at Cambridge University in 1967.

The game is played by two players, starting with a few spots drawn on a sheet of paper. Players take turns drawing a line between two spots or from a spot to itself. The line may not cross any other line. The player adds a new spot on the line. A spot with three lines connected to it (counting a loop from a spot to itself as two lines) is dead and may not have any more lines connected to it. The player who makes the last move wins.

The diagram on the right shows a 2-spot game of sprouts. After the fourth move, it is impossible to make another move, so the second player wins. The final diagram shows that there are two spots (shown in green) that are still alive: that is, they are only connected to two lines. But since these two survivors are in separate regions, they cannot be joined together.

Analysis

Suppose that a game starts with n spots and lasts for exactly m moves.

Each spot starts with three lives (opportunities to connect a line) and each move reduces the total number of lives in the game by one (two lives are lost at the ends of the line, but the new spot has one life). So at the end of the game there are 3n−m remaining lives. Each surviving spot has only one life (otherwise there would be another move joining that spot to itself), so there are exactly 3n−m survivors. There must be at least one survivor, namely the spot added in the final move. So 3n−m ≥ 1; hence a game can last no more than 3n−1 moves.

At the end of the game each survivor has exactly two dead neighbors, in a technical sense of "neighbor"; see the diagram on the right. No dead spot can be the neighbor of two different survivors, for otherwise there would be a move joining the survivors. All other dead spots (not neighbors of a survivor) are called pharisees (from the Hebrew for "separated ones"). Suppose there are p pharisees. Then

n+m = 3n−m + 2(3n−m) + p

since initial spots + moves = total spots at end of game = survivors + neighbors + pharisees. Rearranging gives:

m = 2n + p/4

So a game lasts for at least 2n moves, and the number of pharisees is divisible by 4.

Real games seem to turn into a battle over whether the number of moves will be M or M+1 with other possibilities being quite unlikely. One player tries to create enclosed regions containing survivors (thus reducing the total number of moves that will be played) and the other tries to create pharisees (thus increasing the number of moves that will be played).

Who has the win?

By enumerating all possible moves, one can show that the first player is guaranteed a win in games involving three, four, or five spots. The second player can always win a game started with one, two, or six spots.

At Bell Labs in 1990, David Applegate, Guy Jacobson, and Daniel Sleator used a lot of computer power to push the analysis out to eleven spots. They found that the first player has a winning strategy when the number of spots divided by six leaves a remainder of three, four, or five, and conjectured that this pattern continues beyond eleven spots.

References

• Elwyn R. Berlekamp, John Conway and Richard K. Guy, Winning Ways for your Mathematical Plays, 1992.
• Madras College Mathematics Department, "Mathematical Games: Sprouts." (http://www.madras.fife.sch.uk/maths/games/sprouts.html)
• Ivars Peterson, "Sprouts for Spring," Science News Online. (http://www.sciencenews.org/sn_arc97/4_5_97/mathland.htm)
• Danny Purvis, World Game of Sprouts Association. (http://www.geocities.com/chessdp/)
• Sprouts played an important role in the first part of Piers Anthony's novel Macroscope.
• The Game of Sprouts (http://www.math.utah.edu/~alfeld/Sprouts/) at University of Utah (with an interactive applet).de:Sprouts