The Complete (?) List of References for the Game of Sprouts

This is intended to be a complete list of all available information for the Game of Sprouts. If you are aware of anything missing, please send email.

This page has these four sections:

Discussion Forums

  1. Sprouts-Theory
    Discussions on the theory of Sprouts representations, analysis, etc.

  2. Geometry-Research (Math Forum)
    The above is a 1995 thread, which includes Conway describing a strategy for playing the game. The complete Math forum Geometry-Research (1992-present) is also available, and sometimes discusses Sprouts.

Software

  1. GLOP
    Program to search the game tree and find whether a given Sprouts position is a win for the first or second player. So far, it has determined the winner for all normal games of up to 44 spots (and for 46, 47, 53), and all misere games up to 20 spots.

  2. 3Graph
    Windows software allowing the user to play Sprouts against the computer.

  3. Aunt Beast and Small Beast are programs used by Sprouts competitors, but are not available on the Internet.

Websites

  1. Game of Sprouts References
    Currently, the most complete listing available of Sprouts publications, software, and sites.

  2. Wikipedia
    Wikipedia article on Sprouts, with rules, theorems, pictures, and references.

  3. World Game of Sprouts Association
    An organization that runs Sprouts tournaments, and discusses Sprouts strategies. (Was at http://www.geocities.com/chessdp/)

  4. Clash of the Titans, Game 1 and Game 2
    Interesting analysis by Josh Jordan of his Sprouts games with Roman Khorkov played in 2011 through the World Game of Sprouts Association.

  5. University of Utah Sprouts Applet
    This applet lets two humans play Sprouts. The computer does not play. The lines do not move.

  6. SproutsWiki
    The home page for GLOP, the program that has solved Sprouts for all normal games up to 32 spots, and all misere games up to 17 spots.

  7. Dan Hoey's Game Notation
    A Dec 2000 Geometry-Research thread on notation for representing Sprouts board positions.

  8. Madras College Brussels Sprouts
    Short introduction with pictures.

  9. Madras College Sprouts
    Short introduction to Sprouts, with pictures and links.

  10. Pencil and Paper Games
    List of rules and an animated image of a game.

  11. Sprouts
    Short introduction with references.

Publications

  1. Anthony, Piers (1969) Macroscope. New York: Avon.
    A science fiction book, in which Sprouts is described, many of the characters play Sprouts, and it plays some role in the plot.
  2. D. Applegate, G. Jacobson, and D. Sleator (1991) Computer Analysis of Sprouts, Tech. Report CMU-CS-91-144, Carnegie Mellon University Computer Science Technical Report, 1991. Also in The Mathemagician and the Pied Puzzler (1999) honoring Martin Gardener; E. Burlekamp and T. Rogers, eds, A K Peters Natick, MA, pp. 199-201.
    The classic paper on computationally solving Sprouts. Gives solutions up to 11 spots. Proposes the Sprouts Conjecture: the first player loses the n-spot game if n is 0, 1, or 2 modulo 6, and wins otherwise.
  3. Balyta, Peter, Keeble, Tracy, and McQuatty, Pat (1999) Routing Your Way Through Edgy Mathematics: Graph Theory, Mathematics 514 Programme M.E.Q. 568-514, June 1999 MAPCO implementation session on Graph Theory.
    Sprouts is used (pages 8-11) to teach graph theory to Secondary level 5 (11th grade) math students in Quebec as part of the Math 514 program.
  4. Edwyn Berkelamp, John Conway, and Richard Guy (1982) Winning Ways for your Mathematical Plays, vol. 2: Games in Particular, chapter 17, pp. 564-568, Academic Press, London, 1982. (Also see Vol. 1,1982, Vol. 1,, 2001, Vol. 2, 2003, Vol. 3., 2003, Vol. 4, 2004).
    The classic books from 1982, re-released 2001-2004, with a wealth of information about Sprouts and numerous other games.
  5. Baird, Leemon C. III & Schweitzer, Dino (2010) Complexity of the Game of Sprouts FCS'10 - 6th International Conference on Foundations of Computer Science, Las Vegas, Nevada, July 2010.)
    Proves the NP-completeness of two problems: given a Sprouts position and integer K, can the game continue for at least K more moves? And can it end in less than K moves?
  6. Brown, Wayne and Baird, Leemon C. III (2008) A graph drawing algorithm for the game of sprouts, The 2008 International Conference on Computer Graphics and Virtual Reality, Las V egas, Nevada, July 14-17.
    Describes algorithms for keeping curves spread out when drawing Sprouts positions
  7. Brown, Wayne and Baird, Leemon C. III (2008) A non- trigonometric, pseudo area preserving, polyline smoothing algorithm, Journal of Computing Sciences in Colleges, (Also in the Proceedings of the Consortium for Computing Sciences in Colleges Mid-South Conference).
    Describes algorithms for making the curves smooth when drawing Sprouts positions.
  8. Butler, Ralph M., Trimble, Selden Y., and Wilkerson, Ralph W. (1987) A logic programming model of the game of sprouts, ACM SIGCSE Bulletin, Volume 19, Issue 1 (February 1987), Pages: 319 - 323.
    Describes how Sprouts positions are encoded so a 700-line Prolog program could play sprouts, making random moves.
  9. Copper, M. (1993) Graph theory and the game of sprouts. American Mathematical Monthly 100(May):478.
    Proves bounds on the length of a game as a function of the number of initial spots, whether the final graph is connected, and whether the final graph is biconnected. Then proposes further questions, some of which were answered by Lam (A Math Monthly, 1997).
  10. Draeger, Joachim, Hahndel, Stefan, Koestler, Gerhard, and Rosmanith, Peter (1990). Sprouts: Formalisierung eines topologischen spiels. Technical Report TUM-I9015, Technische Universitaet Muenchen, March 1990.
  11. Eddins, Susan K. (1998) Networks and the game of sprouts. NCTM Student Math Notes (May/June).
  12. Eddins, Susan Krulik (2006) Sprouts: Analyzing a simple game, IMSA Math Journal.
    A simple analysis with questions and answers, as for teaching students..
  13. Focardi, Riccardo and Luccio, Flaminia L. (2004) A modular approach to sprouts, Discrete Applied Mathematics 144 (2004), no. 3, 303-319. (A preliminary version of this paper appeared as A new analysis technique for the Sprouts Game, proc. of the 2nd International Conference on FUN with Algorithms 2001, Carleton Scientific Press, Isola d'Elba, Italy, May 2001)
    From the abstract: We study some new topological properties of this game and we show their effectiveness by giving a complete analysis of the case x0=7 for which, to the best of our knowledge, no formal proof has been previously given.
  14. Fraenkel, Aviezri S. (2009) Combinatorial games: Selected biography with a succinct gourmet introduction The Electronic Journal of Combinatorics 2009.
    A survey of combinatorial games with a huge list of references, covering many related topics, including Sprouts.
  15. Gardner, Martin, Mathematical games: of sprouts and brussels sprouts, games with a topological flavor, Scientific American 217 (July 1967), 112-115.
  16. Gardner, Martin (1989) Sprouts and Brussels sprouts. In Mathematical Carnival. Washington, D.C.: Mathematical Association of America.
  17. Giganti, Paul Jr. (2009) Parent Involvement and Awareness: The Game of Sprouts, CMC ComMuniCator, Dec 2009.
    Advice on teaching math reasoning to kindergarten through middle school, using Sprouts.
  18. Lam, T.K. (1997) Connected sprouts. American Mathematical Monthly 104(February):116.
    Answers questions posed by Copper (American Mathematical Monthly, 1993), about the graph that is obtained at the end of the game. Gives the length of the shortest game for connected and biconnected graphs.
  19. Lemoine, Julien and Viennot, Simon (2007) A further computer analysis of Sprouts. (7 April 2007)
    The first paper since 1991 giving the results for large games. It describes the authors' pseudo-canonization techniques, and gives their results for all games of up to 35 spots, except those with 27,30,31,32,33 spots. It also proposes the Nimber Conjecture: the nimber of the n-spot game is floor((n mod 6)/3).
  20. Lemoine, Julien and Viennot, Simon (2010) Computer analysis of Sprouts with nimbers (13 August 2010) (first released as "A further computer analysis of Sprouts", listed above).
    Contains details about the representation of Sprouts positions, the algorithms based on the central idea of nimbers, and a description of some interesting features of the first version of Glop, like drawing the proof tree or interacting in real-time with the computation.
  21. Lemoine, Julien and Viennot, Simon (2009) Sprouts games on Compact surfaces (2 March 2009, original 29 November 2008)
    Extends Sprouts theory beyond the usual plane/sphere case to other surfaces.
  22. Lemoine, Julien and Viennot, Simon (2009) Analysis of misere Sprouts game with reduced canonical trees (30 August 2009)
    Describes how the authors were able to solve misere games up to 17 spots using reduced canonical trees, which are analogous to nimbers for normal Sprouts.
  23. Lemoine, Julien and Viennot, Simon (2010) Nimbers are inevitable (26 November 2010)
    Proves a theorem: from the proof tree for the outcome of a sum of impartial games, it is possible to deduce the nimber of one component. It implies that in some way nimbers are inevitable, even when trying to compute outcomes, and justifies the efficiency of the algorithms detailed at the end of the article. Also details the results obtained on two impartial games, Sprouts and Cram.
  24. Peterson, Ivar (1997) Sprouts For Spring, Science News, April 5.
    Short Science News article from 5 April 1997 article giving the rules, history Macroscope quotes, and a few references.
  25. Pritchett, Gordon (1976) The game of Sprouts, Two-Year College Mathematics Journal, 7, 7 (Dec 1976) pp. 21-25.
    Proves several Sprouts theorems.