rec.puzzles Archive

The game is played on a piece of paper, initially with a number of points drawn on it, and is a two player turn-taking game.

competition/games/sprouts

Problem

The game is played on a piece of paper, initially with a number of
points drawn on it, and is a two player turn-taking game.  At each
turn, a player must connect two existing points with a line, and add a
new point on that line.  The only restriction on the endpoints used for
a line is that no point may have more than 3 lines extending from it.
Also, no line drawn may cross any other line.  A player loses when he
cannot draw a "legal" line.

Can anybody suggest any good strategies for playing this game with
varying numbers of initial points?  Clearly things become increasingly
complicated as the number of points rises.

-- Mathew Hendry <scampi@dial.pipex.com> (May 1996)
Show solution
The game is Sprouts, invented in 1967 by John H. Conway and Michael S.
Paterson at Cambridge and made famous by Martin Gardner's "Mathematical
Games" column in Scientific American (July 1967).  In the standard
rules a line may also join a point to itself (a loop), as long as the
point ends with at most 3 lines; the posting's wording allows only
lines between two different points.  What follows is for the standard
rules.

What is known.  With n starting points:

- Counting lives.  Call 3 minus the number of lines at a point its
  "lives".  The game starts with 3n lives.  Each move uses two lives
  at its ends and creates a point with one life (it already has two
  lines), so every move removes exactly one life.  The game cannot end
  with no lives left (the last new point always has one), so it lasts
  at most 3n - 1 moves; it can also be shown to last at least 2n moves.
  Whoever makes the last move wins, so the game is decided by the
  parity of the number of moves, i.e. by how many lives are left,
  stranded, at the end.

- Who wins with perfect play.  n = 1: the first move must be a loop;
  the second player joins the two points and wins.  n = 2: the second
  player wins.  n = 3, 4, 5: the first player wins.  n = 6: the second
  player wins; this was first shown by a long hand analysis (Denis
  Mollison) and confirmed by computer.  D. Applegate, G. Jacobson and
  D. Sleator ("Computer analysis of Sprouts", 1991) solved the game up
  to n = 11 and conjectured:

     The first player wins exactly when n is 3, 4 or 5 mod 6.

  J. Lemoine and S. Viennot later confirmed this by computer for every
  n up to several dozen (their programs use the Sprague-Grundy values
  of independent parts of the position).  No proof is known; the
  conjecture is open.

Strategy.  No simple winning strategy is known for any n beyond the
smallest, but the practical method is the one above: count lives.  The
first player wants an odd number of moves, i.e. (3n - 1) minus the
number of stranded lives at the end to be odd.  Each "trapping" move
that seals a live point inside a region no other live point can reach
changes how many lives will be stranded, and good play is a fight over
the parity of those trapped lives.  Late in the game the paper splits
into regions that no longer interact; analyse each separately (as a sum
of games, in the sense of Sprague-Grundy theory) and combine them.
The fullest discussion is in E. R. Berlekamp, J. H. Conway and R. K.
Guy, "Winning Ways for Your Mathematical Plays", volume 2, chapter 17
("Spots and Sprouts").
-- Claude (rec.puzzles Oracle, 2026-11-02)

[ Editor: the material collected earlier follows. ]

This game reminds me of one I remember reading about in a book by
Piers Anthony (I forget the name of the book; it may have been
_Macroscope_).  In the book this game was called "Sprouts".

-- Mathew Hendry <scampi@dial.pipex.com>