Sprouts is an impartial paper-and-pencil game which can be analyzed for its mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in the early 1960s. The setup is even simpler than the popular dots and boxes game, but gameplay develops much more artistically and organically.

Rules

right|300px|thumb|A 2-spot game of Sprouts. The game ends when the first player is unable to draw a connecting line between the only two free points, marked in green.

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.
  • You cannot touch a dot twice with one line then connect it to another.

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. Misère Sprouts is perhaps the only misère combinatorial game that is played competitively in an organized forum.

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 of the game

right|frame|Analysis of a finished game: a live spot (green) is called a survivor. Its two neighbors (black) are dead spots.

Though the number of spots increases with every move, the game of Sprouts cannot go on forever. It has been mathematically proven that for a game starting with n spots, it must end in no more than 3n−1 moves, and no fewer than 2n moves. The reason the game must end is that the number of available connection points, or "lives", decreases with every turn.

A spot is considered "dead" when it has three lines attached to it and can no longer be used to make a move. Each spot begins with three "lives". Each move reduces the total number of lives in the game by one. This is because the move uses up two lives (one at each end of the new line) but creates a new spot which itself has only one remaining life. Therefore, a game that starts with n spots has a total of 3n lives available. After m moves, the number of remaining lives is 3n−m.

The game ends when there are no more valid moves. At this point, any spot that still has lives is called a survivor. A survivor must have only one life remaining (if it had two or more, a line could be drawn from the spot to itself). There must be at least one survivor—the spot created in the final move. Since the total number of remaining lives equals the total number of survivors, and there must be at least one survivor, the number of moves m must be less than 3n. More precisely, a game can last no more than 3n−1 moves. This maximum is often reached when one player tries to keep all the spots in a single connected group.

left|thumb|300x300px|A game of sprouts with n initial spots (in blue) that ends in the maximum possible 3n−1 moves.

right|thumb|300x300px|A game of sprouts with n initial spots that ends in the minimum possible 2n moves.

The minimum number of moves is 2n. This lower bound is often the result of a player trying to divide the playing area into many separate regions, forcing the game to end more quickly. Each enclosed region will contain at least one survivor, and each survivor has two "dead" neighbors that cannot be used by any other survivor. In the minimum-move game, the board is filled with these small groups and there are no other dead spots left over. These leftover dead spots, which are not neighbors of any survivor, are sometimes called pharisees (from the Hebrew for "separated ones"). The total number of moves in a game is directly related to the number of pharisees created.

Because the total number of moves is limited by these bounds, much of the strategy in Sprouts revolves around trying to influence the game's length. One player will try to create enclosed regions to shorten the game, while the other will try to keep the game open and create "pharisees" to lengthen it. Real games often become a battle over whether the final number of moves will be an even or odd number.

Winning strategies

Since Sprouts is a finite game where no draw is possible, a perfect strategy exists either for the first or the second player, depending on the number of initial spots. The main question about a given starting position is then to determine which player can force a win if they play perfectly.

When the winning strategy is for the first player, it is said that the outcome of the position is a "win", and when the winning strategy is for the second player, it is said that the outcome of the position is a "loss" (because it is a loss from the point of view of the first player).

The outcome is determined by developing the game tree of the starting position. This can be done by hand only for a small number of spots, and all the new results since 1990 have been obtained by extensive search with computers.

Normal version

Winning Ways for your Mathematical Plays reports that the 6-spot normal game was proved to be a loss for the first player by Denis Mollison, who produced a 47-page hand analysis. For several decades this remained the largest position solved without computer assistance.

The first major computational advance was made in 1990 by David Applegate, Guy Jacobson, and Daniel Sleator at Carnegie Mellon University.

Their program, based on alpha–beta pruning with a string-based representation of Sprouts positions, determined the outcomes for all positions up to 11 spots. Based on these results, they formulated the Sprouts conjecture, stating that the first player wins exactly when

:<math>n \equiv 3,4,5 \pmod{6}</math>.

In 2001, Riccardo Focardi and Flamina Luccio described a method to prove by hand that the normal 7-spot game is a loss.

A second major leap came from Lemoine and Viennot, who introduced the use of nimbers (Grundy numbers) to exploit the natural decomposition of Sprouts positions. In 2007, they solved all positions up to 32 spots. In 2010–2011, they extended the record to all positions up to 44 spots, and three isolated cases at 46, 47, and 53 spots.

In 2025, Čížek, Balko, and Schmid introduced SPOTS, a massively parallel solver based on proof-number search with distributed-memory parallelism and nimber-based reductions.

Their solver established 42 previously unknown outcomes, raising the number of solved n-spot positions from 47 to 89.

All newly computed outcomes are consistent with the Sprouts conjecture (W = first-player win, L = loss):

{| style="width:100%"

| style="width:33%; vertical-align:top;" |

{| class="wikitable sortable"

! n !! Outcome !! Authors

|-

| 1 || L || Conway

|-

| 2 || L || Conway

|-

| 5 || W || Mollison

|-

| 13 || L || Purinton The same year, Julien Lemoine and Simon Viennot reached 17 spots with complicated algorithms. They were able to extend their analysis up to 20 points in 2011.

References

Bibliography

  • Elwyn R. Berlekamp, John Conway and Richard K. Guy, Winning Ways for your Mathematical Plays, 1992.
  • .
  • Mackenzie, Dana, "Answers to Sprouts", Cornell University Math Department, 2003-2004,
  • Sprouts+ an app for the iPhone/iPad and silicon Macs
  • The Complete (?) List of References for the Game of Sprouts
  • World Game of Sprouts Association., Danny Purvis, association of Sprouts players
  • The Game of Sprouts at University of Utah, with an interactive applet for human-vs-human play. (Requires Java)
  • SproutsWiki, web site of Julien Lemoine and Simon Viennot, with the source code and binaries of their program