Sprouts (game)

From Wikipedia, the free encyclopedia

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.

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:

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.

1 Analysis
2 Who has the win?
3 Brussels Sprouts
4 References

[edit] 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

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).

[edit] 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. Josh Purinton has extended this analysis to fourteen spots; the results are consistent with the pattern describe above.[1]

A 2-cross game of Brussel Sprouts lasting eight moves

[edit] 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.

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.