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.

Players take turns, where each turn consists of drawing a line between two spots (or from a spot to itself) and adding a new spot somewhere along the line. The players are constrained by the following rules.

• The line may be straight or curved, but must not touch or cross itself or any other line.

• The new spot cannot be placed on top of one of the endpoints of the new line. Thus the new spot splits the line into two shorter lines.

• No spot may have more than three lines attached to it. For the purposes of this rule, a line from the spot to itself counts as two attached lines and new spots are counted as having two lines already attached to them. In so-called normal play, the player who makes the last move wins.

In misère play, the player who makes the last move loses. The diagram on the right shows a 2-spot game of normal-play Sprouts. After the fourth move, most of the spots are dead–they have three lines attached to them, so they cannot be used as endpoints for a new line.

There are two spots (shown in green) that are still alive, having fewer than three lines attached. However, it is impossible to make another move, because a line from a live spot to itself would make four attachments, and a line from one live spot to the other would cross lines. Therefore, no fifth move is possible, and the first player loses. Live spots at the end of the game are called survivors and play a key role in the analysis of Sprouts. 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. By enumerating all possible moves, one can show that the first player when playing with the best possible strategy will always win in normal-play games starting with n = 3, 4, or 5 spots. The second player wins when n = 0, 1, 2, or 6. 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 in normal play and nine spots in misère play.

Josh Purinton and Roman Khorkov have extended this analysis to sixteen spots in misère play. Julien Lemoine and Simon Viennot have calculated normal play outcomes up to thirty-two spots, plus five more games between thirty-four and forty-seven spots.

They have also announced a result for the seventeen-spot misère game. The normal-play results are all consistent with the pattern observed by Applegate et al. up to eleven spots and conjectured to continue indefinitely, that the first player has a winning strategy when the number of spots divided by six leaves a remainder of three, four, or five. The results for misère play do not follow as simple a pattern: up to seventeen spots, the first player wins in misère Sprouts when the remainder (mod 6) is zero, four, or five, except that the first player wins the one-spot game and loses the four-spot game.