Sprouts

Sprouts is a two-person game invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in 1967.

The game begins with a number of spots:

Players take turns drawing a line -straight or curved – between existing spots, and adding a new spot in the middle of the new line:

The rules are:

• Lines must not touch or cross any line except at a designated spot.
• No spot may have more than three lines attached to it. A line from a spot to itself counts as two attached lines and new spots are counted as having two lines already attached to them.
• The player who makes the last move wins.

The problem, for a given number of spots is to determine when the first player has a winning strategy, and when the second player has a winning strategy.

It is conjectured that that the first player has a winning strategy when the number of spots is congruent to 3, 4, or 5, modulo 6.

The complexity of analysis grows very rapidly with the initial number of spots.

The misère form of the game is when the last player to move loses.

References and readings

• Applegate, David, Guy Jacobson, and Daniel Sleator. 1991. Computer analysis of sprouts. Carnegie Mellon University Computer Science Technical Report No. CMU-CS-91-144, May. (computer_analysis_of_sprouts_1991)
• Copper, Mark. 1993. Graph theory and the game of sprouts. American Mathematical Monthly 100 (May):478-482. (graph_theory_and_the_game_of_sprouts)
• Lam, T.K. 1997. Connected sprouts. American Mathematical Monthly 104(February):116-119. (connected_sprouts)
• R. Focardi & F.L. Luccio (2001), A new analysis technique for the Sprouts Game, Convegno International Conference Fun with Algorithms 2 (FUN 2001), Isola d’Elba, Italy, MAY 29-31, Ed. Carleton Scientific, pp. 117-132. (a_new_analysis_technique_for_the_sprouts_game)
• Julien Lemoine & Simon Viennot (2006) A further computer analysis of sprouts. (a_further_computer_analysis_of_sprouts)
• GLOP.

The “GLOP” program is useful both for mathematical research and for playing Sprouts. It creates graphs that can be drawn using Graphviz. Linux and Windows versions are available.

• World Game of Sprouts Association
• Khorkov Announces Startling Findings.
• Winning ways for Your Mathematical Plays, vols 1 – 4.
• Games of No Chance (Mathematical Sciences Research Institute)

Advertisement