Sprouts (game)
It was invented by mathematicians John Horton Conway and Michael S. Paterson[1] 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.
The game is played by two players,[2] starting with a few spots drawn on a sheet of paper.
Live spots at the end of the game are called survivors and play a key role in the analysis of Sprouts.
This upper bound is actually the maximum, and it can be attained in many ways by ensuring that there is only one survivor at the end of the game.
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.
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.
It stood as the record for a long time, until the first computer analysis, which was done at Carnegie Mellon University in 1990 by David Applegate, Guy Jacobson, and Daniel Sleator.
Applegate, Jacobson and Sleator observed a pattern in their results, and conjectured that the first player has a winning strategy when the number of spots divided by six leaves a remainder of three, four, or five.
This is a mathematical way of saying that the pattern displayed by the outcome in the table below repeats itself indefinitely, with a period of six spots.
In 2001, Riccardo Focardi and Flamina Luccio described a method to prove by hand that the normal 7-spot game is a loss.
In 2007, Julien Lemoine and Simon Viennot introduced an algorithm based on the concept of nimbers to accelerate the computation, reaching up to 32 spots.
[9] The same year, Julien Lemoine and Simon Viennot reached 17 spots with complicated algorithms.
[8] The results for misère play are now conjectured to follow a pattern of length six with some exceptional values: the first player wins in misère Sprouts when the remainder (mod 6) is zero, four, or five, except that the first player wins the one-spot game and loses the four-spot game.
A variant of the game, named Brussels Sprouts after the cruciferous vegetable, starts with a number of crosses, i.e. spots with four free ends.
In the starting position with n crosses, we have a planar graph with v = 5n vertices, e = 4n edges, f = 1 face, and k = n connected components.
In the final configuration, no face can have more than one degree 1 vertex, since otherwise, we could connect them with a cross and there would still be a legal move.
At each turn, the player chooses to add either a dot, or a cross, along the line they have just drawn.
The duration of the game lays between (2n) and (5n − 2), depending on the number of dots or crosses having been added.
