Sprouts is a two-player impartial game invented by John Conway and Michael Paterson in 1967 (Lemoine and Viennot 2008). Play begins
with 
isolated spots drawn in the plane.
A move draws a curve joining two existing spots, possibly
the same spot, and places a new spot on that curve. The
curve must not cross itself or another curve,
pass through another spot, or leave any spot with more than three incident line ends.
A self-join uses two line ends. In a normal-form
game, the player making the last legal move wins.
The drawing represents a planar graph with vertex degree at most 3. Calling each available line end a life, the initial position
has 
lives. Each move uses two lives and
creates a spot with one life, decreasing the total by one. The last new spot retains
one life, giving the upper bound
 |
on the number 
of moves for 
.
The misère variant makes the last player to move lose. Play on other compact surfaces can change the possible moves and winning strategies (Lemoine and Viennot 2008).
