Sprouts

Sprouts is a pencil-and-paper strategy game for two players, invented by mathematicians John Conway and Michael Paterson. Players take turns drawing curves between dots and adding new dots on those curves. Each dot can have at most three lines connected to it, and lines cannot cross. The last player able to make a valid move wins (in normal play) or loses (in misere play). Despite its simple materials — just a pen and paper — Sprouts produces remarkably complex strategic situations.

Rules

1. Start with a small number of dots (spots) on a piece of paper — typically 2 to 6.
2. Players alternate turns.
3. On each turn, a player draws a curve connecting two dots (or a dot to itself, forming a loop).
4. The curve must not cross any existing curve or pass through any existing dot.
5. After drawing the curve, the player adds a new dot somewhere on the curve they just drew.
6. Each dot can have at most three curves (lines) connected to it. A dot with three connections is "dead" and can no longer be used.
7. The player who makes the last valid move wins (normal convention).

Strategies

• Count Lives: Each dot starts with 3 "lives" (possible connections). Drawing a line uses one life from each endpoint, and the new dot is born with one life already used (the curve passes through it), leaving it with 2 lives. Track the total remaining lives to estimate how many moves remain.
• Game Length: A game starting with N dots always lasts between 2N and 3N-1 moves. Knowing this helps determine whether you want to extend or shorten the game.
• Regions: Curves divide the paper into regions. Dots in the same region can connect, but dots in different regions cannot (since curves can't cross). Creating regions that isolate your opponent's options is key.
• Boundary Control: Try to leave your opponent with only dead dots in their accessible regions.
• Pharisees and Survivors: A "pharisee" is a dot that can't be used anymore. Track which dots are alive and how many connections they have left.
• Parity: Since you know the game length is bounded, you can sometimes determine who will make the last move and play accordingly.

Sprouts was invented on February 21, 1967, in the mathematics department of the University of Cambridge. John Horton Conway and Michael Stewart Paterson were having afternoon tea when they began experimenting with the game. Conway later described it as "one of the best games to come out of Cambridge since the invention of cricket."

The game immediately captured the attention of mathematicians. Martin Gardner featured Sprouts in his "Mathematical Games" column in Scientific American in July 1967, bringing it to a worldwide audience. Gardner reported that the game had "sprouted" a minor craze among mathematicians and computer scientists, with players discovering that what seemed like a simple doodling game contained surprising strategic depth.

The mathematical analysis of Sprouts is extremely complex. While games starting with few dots (1-7) have been completely analyzed by hand and computer, the difficulty grows rapidly. The game is related to graph theory and topology — specifically, it can be analyzed using concepts from planar graph theory, since the game is played on a surface where curves cannot cross. Computer analysis by David Applegate, Guy Jacobson, and Daniel Sleator in the 1990s extended the known results to games starting with up to 11 dots.

An important open question is whether the first player wins or loses for each starting number of dots. Computer analysis has shown a pattern: the first player loses when starting with 0, 1, or 2 dots, but wins with 3, 4, or 5 dots. The pattern appears to be that the first player loses when the number of dots is 0, 1, or 2 modulo 6, but this conjecture remains unproven for all starting positions.

Conway, one of the most celebrated mathematicians of the 20th century, went on to create many other mathematical games and contributed fundamental work to group theory, number theory, and coding theory. He passed away in 2020, but Sprouts remains one of his most accessible and beloved creations.