Sprouts is a pencil-and-paper game with interesting mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in 1967. Games that can be played with only pencil and paper: Battleship was played as a pencil and paper game, long before Hasbro came out with a board game version. ... Euclid, detail from The School of Athens by Raphael. ... This article is in need of attention from an expert on the subject. ... See John B. Conway for the functional analyst. ... The University of Cambridge (often called Cambridge University), located in Cambridge, England, is the second-oldest university in the English-speaking world. ... 1967 (MCMLXVII) was a common year starting on Sunday of the Gregorian calendar (the link is to a full 1967 calendar). ...

A 2-spot game of sprouts

The game is played by two players, starting with a few spots drawn on a sheet of paper. Play then proceeds according to the following rules: Image File history File links Sprouts-2spot-game. ... Image File history File links Sprouts-2spot-game. ...

• 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 then 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.

Live spots (green) and their dead neighbors (black).

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 Image File history File links Sprouts-analysis. ... Hebrew (עִבְרִית ‘Ivrit) is a Semitic language of the Afro-Asiatic language family spoken by more than seven million people in Israel with the West Bank, the United States, and Jewish communities around the world. ...

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. Bell Telephone Laboratories Inc. ... This article is about the year. ... Daniel Dominic Kaplan Sleator is a professor of computer science at Carnegie Mellon University. ... A computer is a machine for manipulating data according to a list of instructions known as a program. ...

A 2-cross game of Brussel Sprouts lasting eight moves

Image File history File links Brussel_Sprouts_Game. ... Image File history File links Brussel_Sprouts_Game. ...

Brussels Sprouts

A variant of the game, called Brussels Sprouts, starts with a number of crosses, i.e. points with four free ends. Each move involves joining two free ends with a curve (again not crossing any existing line) and then putting a short stroke across the line. Therefore you can think of Brussel Sprouts as the same game as Sprouts but with points "dead" after there are 4 lines on them.

So each move removes two free ends and introduces two more. Despite this, the game is finite, and indeed the total number of moves is predetermined by the initial number of crosses: the players cannot affect the result by their play. With n initial crosses, the number of moves will be 5n−2, so a game starting with an odd number of crosses will be a first player win, while a game starting with an even number will be a second player win (regardless of the moves).

References

• Elwyn R. Berlekamp, John Conway and Richard K. Guy, Winning Ways for your Mathematical Plays, 1992.
• Madras College Mathematics Department, "Mathematical Games: Sprouts."
• Ivars Peterson, "Sprouts for Spring," Science News Online.
• Danny Purvis, World Game of Sprouts Association.
• Sprouts played an important role in the first part of Piers Anthony's novel Macroscope.
• The Game of Sprouts at University of Utah (with an interactive applet).
• Riccardo Focardi and Flamina Luccio, A new analysis technique for the Sprouts Game, 2001
• David Applegate, Guy Jacobson, and Daniel Sleator, Computer Analysis of Sprouts, 1991