Sprouts is a fair paper-and-pencil game that can be studied for its math features. It was created by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in the early 1960s. The setup is even easier than the popular game dots and boxes, but the gameplay grows in a more creative and natural way.

Rules

The game is played by two players, beginning with a few spots drawn on a sheet of paper. Players take turns by drawing a line between two spots (or from a spot to itself) and placing a new spot along the line. The following rules apply:

• The line can be straight or curved, but it must not touch or cross itself or any other line.
• The new spot cannot be placed on the endpoints of the line. This splits the line into two shorter lines.
• No spot can have more than three lines connected to it. A line drawn from a spot to itself counts as two connections. New spots already have two lines connected to them.
• A line cannot use the same spot twice in one move and then connect it to another spot.

In 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 the only misère combinatorial game played competitively in organized settings.

The diagram on the right shows a 2-spot game of normal-play Sprouts. After the fourth move, most spots are "dead" because they have three lines connected to them and cannot be used as endpoints for new lines. Two spots (shown in green) are still "alive" because they have fewer than three lines connected. However, no fifth move is possible: a line from a live spot to itself would create four connections, and a line between the two live spots would cross existing lines. Since no moves remain, the first player loses. Live spots at the end of the game are called survivors and are important for analyzing Sprouts.

Analysis of the game

Even though more spots are added with each move, the game of Sprouts cannot continue forever. It has been shown through math that a game starting with n spots must end in no more than 3n − 1 moves, and no fewer than 2n moves. The reason the game ends is that the number of available connection points, or "lives," decreases with every turn.

A spot is "dead" when it has three lines connected to it and cannot be used for another move. Each spot starts with three "lives." Every move uses two lives (one at each end of the new line) but adds a new spot that has one life left. Therefore, a game with n spots begins with 3n total lives. After m moves, the number of remaining lives is 3n − m.

The game ends when no more moves are possible. At this point, any spot that still has lives is called a survivor. A survivor must have only one life left (if it had more, a move could still be made). There must be at least one survivor—the spot added during the final move. Since the number of survivors equals the number of remaining lives, and there must be at least one survivor, the number of moves m must be less than 3n. This means the maximum number of moves is 3n − 1. This maximum often happens when players keep all spots connected in one group.

The minimum number of moves is 2n. This happens when a player divides the game area into many separate regions, ending the game quickly. Each enclosed region has at least one survivor, and each survivor has two "dead" neighbors that cannot be used by other survivors. In the minimum-move game, the board is filled with these small groups, and no extra dead spots remain. These leftover dead spots, which are not near any survivor, are sometimes called "pharisees." The total number of moves depends on how many pharisees are created.

Because the number of moves is limited by these rules, much of the strategy in Sprouts focuses on controlling the game's length. One player may try to create enclosed regions to shorten the game, while the other tries to keep the game open and create pharisees to extend it. Real games often depend on whether the final number of moves will be even or odd.

Winning strategies

Sprouts is a game that ends when there are no more moves, and no game ends in a tie. A perfect strategy exists for either the first or second player, depending on how many starting spots are used. The main question for any starting position is to find out which player can force a win if both play perfectly.

If the first player can force a win, the position is called a "win." If the second player can force a win, the position is called a "loss" because it means the first player cannot win.

To determine the outcome, people study the game tree of the starting position. This is only possible by hand for small numbers of spots. Since 1990, most new results have been found using computers.

A book called Winning Ways for your Mathematical Plays states that Denis Mollison proved the 6-spot game is a loss for the first player. He did this with a detailed hand analysis that took 47 pages. For many years, this was the largest position solved without a computer.

In 1990, David Applegate, Guy Jacobson, and Daniel Sleator at Carnegie Mellon University created a program that used a special method to analyze Sprouts positions. Their program found the outcomes for all positions up to 11 spots. Based on their results, they proposed the Sprouts conjecture, which suggests the first player wins when

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

Lemoine and Viennot later introduced a method using nimbers (Grundy numbers) to break down Sprouts positions. In 2007, they solved all positions up to 32 spots. By 2010–2011, they solved positions up to 44 spots, and three more positions at 46, 47, and 53 spots.

In 2025, Čížek, Balko, and Schmid created SPOTS, a computer program that uses a special search method and parallel processing. Their program found 42 new outcomes, solving positions from 47 to 89 spots.

All new results match the Sprouts conjecture: the first player wins when the number of spots is a "win," and loses when it is a "loss."

The history of solving the misère version of Sprouts is similar to the normal version, but it is harder to compute. In 1990, Applegate, Jacobson, and Sleator solved up to 9 spots and guessed the outcomes followed a pattern of five. However, in 2007, Josh Jordan and Roman Khorkov showed this guess was wrong by solving up to 12 spots. They later solved up to 16 spots in 2009. That same year, Julien Lemoine and Simon Viennot solved up to 17 spots using complex methods and reached 20 spots in 2011.

Now, it is believed that the outcomes for misère Sprouts follow a pattern of six, with some exceptions. The first player wins when the number of spots leaves a remainder of 0, 4, or 5 when divided by 6. However, the first player wins the 1-spot game and loses the 4-spot game. The table below shows this pattern, with the two exceptions in bold.

Brussels Sprouts

A variation of the game, called Brussels Sprouts after the vegetable, begins with several crosses, which are points with four open ends. Each move involves connecting two open ends with a curve that does not cross any existing lines. After drawing the curve, a short line is added across it to create two new open ends. This game ends after a fixed number of moves, and the winner is determined by how many crosses are used at the start. Players cannot change the outcome, so this version can be called a "one-player game," following Conway's classification of mathematics.

Each move removes two open ends and adds two new ones. However, the game must end eventually because some open ends will become isolated. If there are n crosses at the start, the total number of moves will always be 5n − 2. This means that if the starting number of crosses is odd, the first player will win. If it is even, the second player will win, no matter how the players play.

To explain this, first, we show the game must end. Then, we calculate the exact number of moves needed. The result is clear from this calculation.

Imagine each cross as a shape with 5 points and 4 lines. At the start, with n crosses, the game forms a planar graph with v = 5n points, e = 4n lines, f = 1 face, and k = n connected parts. For connected planar graphs, the Euler characteristic is 2. For disconnected planar graphs, the formula becomes:

1 + k = f − e + v

After m moves, the number of lines becomes e = 4n + 4m (each move adds 4 lines), and the number of points becomes v = 5n + 3m (each move adds 3 points). Using the formula:

f − k = 1 + e − v = 1 − n + m

Every time a cross is added, it creates a face with a point of degree 1 (a point connected to only one line). Throughout the game, the number of degree 1 points remains 4n. This means the number of faces (f) is at most 4n.

From this, the number of moves (m) is at most 5n − 2 (since k is at least 1 and f is at most 4n). This proves the game must end in at most 5n − 2 moves. To show it ends exactly in 5n − 2 moves, consider the final state:

• No face can have more than one degree 1 point, or a legal move would still be possible.
• Every face has at least one degree 1 point, so the final state has exactly 4n faces.
• The graph must be connected, as each connected part would require at least one degree 1 point on the outer face, but only one can exist. Thus, k = 1 in the final state.

Using the formula, m = f − k − 1 + n = 4n − 1 − 1 + n = 5n − 2.

A mix of standard Sprouts and Brussels Sprouts can also be played. The game starts with n dots or crosses. On each turn, a player chooses to add either a dot or a cross along the line they just drew. The game lasts between 2n and 5n − 2 moves, depending on how many dots or crosses are added.

For n = 1, starting with a dot, the game ends after 2 moves. Starting with a cross, it ends after 2 moves if the first player adds a dot, or after 3 moves if they add a cross. This means the first player can win in both the normal and misère versions. For n > 1, the analysis is incomplete.

In popular culture

The game of Sprouts is an important part of the story in the 1969 Nebula Award-nominated science fiction novel Macroscope by Piers Anthony. The main character, Ivo, is very skilled at playing Sprouts, and his talent is used to show his intelligence and creativity. In the book, the characters play Sprouts as a challenging mental activity. The novel includes drawings of games being played and explains how the game relates to the mind.