Editing Sprouts (game)

{{Short description|Paper-and-pencil mathematical game}}
{{technical|date=October 2018}}
'''Sprouts''' is an [[Impartial game | impartial]] [[paper-and-pencil game]] which can be analyzed for its [[mathematics|mathematical]] properties. It was invented by mathematicians [[John Horton Conway]] and [[Michael S. Paterson]]<ref name="sciamerican">{{cite journal |last1=Gardner |first1=Martin |title=Mathematical Games - The fantastic combinations of John Conway's new solitaire game 'Life' |journal=Scientific American |date=October 1970 |volume=223 |pages=120–123 |url=http://www.dbs.informatik.uni-muenchen.de/Lehre/Programmierpraktikum/WS0708/material/MathematicalGames.pdf |access-date=30 January 2019|doi=10.1038/scientificamerican1070-120 }}</ref> at [[University of Cambridge|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.

==Rules==
[[File:Sprouts-2spot-game.png|right|300px|thumb|A 2-spot game of Sprouts. The game ends when the first player is unable to draw a connecting line between the only two free points, marked in green.]]

The game is played by two players,<ref>{{cite journal |last1=Lam |first1=T. K. |title=Connected Sprouts |journal=The American Mathematical Monthly |date=10 April 2018 |volume=104 |issue=2 |pages=116–119 |doi=10.1080/00029890.1997.11990609}}</ref> starting with a few spots drawn on a sheet of paper. Players take turns, where each turn consists of drawing a line between two spots (or from a spot to itself) and adding a new spot somewhere along the line. The players are constrained by the following rules:
* The line may be straight or curved, but must not touch or cross itself or any other line.
* The new spot cannot be placed on top of one of the endpoints of the new line. Thus the new spot splits the line into two shorter lines.
* No spot may have more than three lines attached to it. For the purposes of this rule, a line from the spot to itself counts as two attached lines and new spots are counted as having two lines already attached to them.
* You cannot touch a dot twice with one line then connect it to another.

In so-called ''normal play'', the player who makes the last move wins. In ''[[misère|misère play]]'', the player who makes the last move loses. Misère Sprouts is perhaps the only misère combinatorial game that is played competitively in an organized forum.<ref>{{cite arXiv |last=Plambeck |first=Thane E. |eprint=math/0603027v1 |title=Advances in losing |date=2006 |page=21}}</ref>

The diagram on the right shows a 2-spot game of normal-play Sprouts. After the fourth move, most of the spots are ''dead''&ndash;they have three lines attached to them, so they cannot be used as endpoints for a new line. There are two spots (shown in green) that are still ''alive'', having fewer than three lines attached. However, it is impossible to make another move, because a line from a live spot to itself would make four attachments, and a line from one live spot to the other would cross lines. Therefore, no fifth move is possible, and the first player loses. Live spots at the end of the game are called ''survivors'' and play a key role in the analysis of Sprouts.

==Number of moves==
The game of Sprouts always terminates, although this fact is not evident from the game rules, since the number of spots increases at each move.  The approach to understand why the game always terminates is to consider the number of ''lives'' (opportunities to connect a line) instead of the number of spots. Then, it can be shown that if the game starts with ''n'' spots, it will end in no more than 3''n''&nbsp;−&thinsp;1 moves and no fewer than 2''n'' moves.

In the following [[mathematical proof|proofs]], it is assumed that a game starts with ''n'' spots and lasts for exactly ''m'' moves.

===Maximum number of moves===
[[File:Sprouts-max-moves.png|thumb|300px|A game of sprouts with ''n'' initial spots (in blue) that ends in 3''n''&nbsp;−&thinsp;1 moves]]

Each spot starts with three ''lives'' and each move reduces the total number of lives in the game by one (two lives are lost at the ends of the line, but the new spot has one life). So at the end of the game there are {{nowrap|3''n'' − ''m''}} remaining lives. Each surviving spot has only one life (otherwise there would be another move joining that spot to itself), so there are exactly {{nowrap|3''n'' − ''m''}} survivors. There must be at least one survivor, namely the spot added in the final move. So {{nowrap|3''n'' − ''m'' ≥ 1}}; hence a game can last no more than 3''n''&nbsp;−&thinsp;1 moves.

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. For instance, the game on the right has one survivor and 3''n''&nbsp;−&thinsp;1 moves.

[[File:Sprouts-analysis.png|right|framed|Live spots (green) and their dead neighbors (black)]]

===Minimum number of moves===
At the end of the game, a dead spot is called the ''neighbor''  of a survivor if it is either adjacent to that survivor or, if the survivor has a loop, it is adjacent to a spot adjacent to the survivor. This is illustrated in the diagram to the right.  Each survivor has exactly two dead neighbors. No dead spot can be the neighbor of two different survivors, for otherwise there would be a move joining the survivors. All other dead spots (not neighbors of a survivor) are called ''pharisees'' (from the [[Hebrew language|Hebrew]] for "[[Pharisees|separated ones]]"). Suppose there are ''p'' pharisees. Then

:<math>n + m = 3n - m + 2(3n - m) + p</math>

since initial spots + moves = total spots at end of game = survivors + neighbors + pharisees. Rearranging gives:

:<math> m = 2n + p/4</math>

Consequently, a game lasts for at least 2''n'' moves, and the number of pharisees is [[divisible]] by 4.

[[File:Game of sprouts with n initial vertices, ending in minimum number of moves.png|thumb|300px|A game of sprouts with ''n'' initial spots that ends in 2''n'' moves]]
This lower bound on the length of a game is actually the minimum. The diagram on the right shows a completed game of 2''n'' moves. It has ''n'' survivors, 2''n'' neighbors and 0 pharisees.

===Importance in real games===
Real games seem to turn into a battle over whether the number of moves will be ''k'' or ''k''&nbsp;+&thinsp;1 with other possibilities being quite unlikely.<ref>{{cite web |url=http://mathforum.org/kb/message.jspa?messageID=1091005&tstart=0 |title=Math Forum Discussions |publisher=Mathforum.org |access-date=2012-09-26 |archive-date=2012-03-16 |archive-url=https://web.archive.org/web/20120316135329/http://mathforum.org/kb/message.jspa?messageID=1091005&tstart=0 |url-status=dead }}</ref> One player tries to create enclosed regions containing survivors (thus reducing the total number of moves that will be played) and the other tries to create pharisees (thus increasing the number of moves that will be played).

==Winning strategies==
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.

When the [[winning strategy]] is for the first player, it is said that the ''outcome'' of the position is a "win", and when the winning strategy is for the second player, it is said that the outcome of the position is a "loss" (because it is a loss from the point of view of the first player).

The outcome is determined by developing the [[game tree]] of the starting position. 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.

===Normal version===
''[[Winning Ways for your Mathematical Plays]]'' reports that the 6-spot normal game was proved to be a win for the second player by Denis Mollison, with a hand-made analysis of 47 pages. 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]].<ref>{{cite web|url=https://www.cs.cmu.edu/~sleator/papers/Sprouts.htm |title=David Applegate, Guy Jacobson, and Daniel Sleator, ''Computer Analysis of Sprouts'', 1991 |publisher=Cs.cmu.edu |access-date=2012-09-26}}</ref> They reached up to 11 spots with some of the best hardware available at the time.

Applegate, Jacobson and Sleator observed a pattern in their results, and [[conjecture]]d 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.

{| border="1" cellspacing="0"
|-
|&thinsp;'''Spots'''
|&thinsp;0
|&thinsp;1
|&thinsp;2
|&thinsp;3
|&thinsp;4
|&thinsp;5
|&thinsp;6
|&thinsp;7
|&thinsp;8
|&thinsp;9
|&thinsp;10
|&thinsp;11
|&thinsp;...
|-
|&thinsp;'''Normal Outcome'''&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;Win&thinsp;
|&thinsp;Win&thinsp;
|&thinsp;Win&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;Win&thinsp;
|&thinsp;Win&thinsp;
|&thinsp;Win&thinsp;
|&thinsp;...&thinsp;
|}

In 2001, Riccardo Focardi and Flamina Luccio described a method to prove by hand that the normal 7-spot game is a loss.<ref>{{cite web| first1 = Riccardo |last1 = Focardi | first2 = Flamina | last2 = Luccio | title = A new analysis technique for the Sprouts Game | date = 2001| citeseerx = 10.1.1.21.212|s2cid = 18947864 }}</ref>

Then, the computation results were extended in 2006 by Josh Jordan up to 14 spots. In 2007, Julien Lemoine and Simon Viennot introduced an algorithm based on the concept of [[nimber]]s to accelerate the computation, reaching up to 32 spots.<ref>{{cite arXiv|first1=Lemoine|last1=Julien|first2= Viennot|last2=Simon|title=Computer analysis of Sprouts with nimbers|year=2010|eprint=1008.2320 |class=math.CO}}</ref> They have extended the computation up to 44 spots in 2011, and three isolated starting positions, with 46, 47 and 53 spots.<ref name="sproutsWiki">[http://sprouts.tuxfamily.org/wiki/doku.php?id=records Computation records of normal and misère Sprouts], Julien Lemoine and Simon Viennot web site</ref>

The normal-play results so far are all consistent with the conjecture of Applegate, Jacobson, and Sleator.

===Misère version===
The computation history of the misère version of Sprouts is very similar to that of the normal version, with the same people involved. However, the misère version is more difficult to compute, and progress has been significantly slower.

In 1990, Applegate, Jacobson and Sleator reached up to nine spots. Based on their results, they conjectured that the outcome follows a regular pattern of period five. However, this conjecture was invalidated in 2007 when Josh Jordan and Roman Khorkov extended the misère analysis up to 12 spots: the 12-spot misère game is a win, and not the conjectured loss. The same team reached up to 16 spots in 2009.<ref>{{Cite web|title=A New Verified Misere Outcome|url=http://www.wgosa.org/article2009001.htm|access-date=2023-02-12|website=www.wgosa.org}}</ref> The same year, Julien Lemoine and Simon Viennot reached 17 spots with complicated algorithms.<ref>{{cite arXiv|first1=Lemoine|last1=Julien|first2= Viennot|last2=Simon|title=Analysis of misere Sprouts game with reduced canonical trees|year=2009|eprint=0908.4407 |class=math.CO}}</ref> They were able to extend their analysis up to 20 points in 2011.<ref name="sproutsWiki" />

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 ([[modulo operation|mod]] 6) is zero, four, or five, except that the first player wins the one-spot game and loses the four-spot game. The table below shows the pattern, with the two irregular values in bold.

{| border="1" cellspacing="0"
|-
|&thinsp;'''Spots'''
|&thinsp;0
|&thinsp;1
|&thinsp;2
|&thinsp;3
|&thinsp;4
|&thinsp;5
|&thinsp;6
|&thinsp;7
|&thinsp;8
|&thinsp;9
|&thinsp;10
|&thinsp;11
|&thinsp;12
|&thinsp;13
|&thinsp;14
|&thinsp;15
|&thinsp;...
|-
|&thinsp;'''Misère Outcome'''&thinsp;
|&thinsp;Win&thinsp;
|&thinsp;'''Win'''&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;'''Loss'''&thinsp;
|&thinsp;Win&thinsp;
|&thinsp;Win&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;Win&thinsp;
|&thinsp;Win&thinsp;
|&thinsp;Win&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;Loss&thinsp;
|&thinsp;...&thinsp;
|}

==Brussels Sprouts==
[[File:Brussel Sprouts Game.png|thumb|A 2-cross game of Brussels Sprouts always lasts exactly eight moves]]
A variant of the game, named '''Brussels Sprouts''' after [[Brussels sprout|the cruciferous vegetable]], starts with a number of crosses, i.e. spots with four free ends. Each move involves joining two free ends with a curve, again not crossing any existing line, and then putting a short stroke across the line to create two new free ends. This game is finite, and the total number of moves (and thus the game's winner) is predetermined by the initial number of crosses: the players cannot affect the result by their play. Thus, this variant may be termed, after Conway's categorisation of mathematics itself, a "one player game".

Each move removes two free ends and introduces two more. Nonetheless, the game is bound to end as some free ends become isolated. With ''n'' initial crosses, the number of moves will, remarkably, always be 5''n''&nbsp;−&nbsp;2. Consequently, a game starting with an [[parity (mathematics)|odd]] number of crosses will be a first player win, while a game starting with an [[parity (mathematics)|even]] number will be a second player win regardless of the moves.

To prove this, first, we argue the game must end. Then, we will calculate precisely how many moves it needs to end. The game outcome is then implied, as already described.

Treat each cross as a [[graph (discrete mathematics)|graph]] with 5 vertices and 4 edges. In the starting position with ''n'' crosses, we have a [[planar graph]] with ''v'' = 5''n'' vertices, ''e'' = 4''n'' edges, ''f'' = 1 face, and ''k'' = ''n'' [[component (graph theory)|connected components]]. The [[Euler characteristic#Planar graphs|Euler characteristic for connected planar graphs]] is 2. In a [[connectivity (graph theory)|disconnected]] planar graph, we get 

{{Equation|1=1+k = f-e+v}}

After ''m'' moves, we have:
* ''e'' = 4''n'' + 4''m'' since at each move, the player adds 4 edges.
* ''v'' = 5''n'' + 3''m'' since at each move, the player adds 3 vertices.

Then by the above, we have

* ''f'' − ''k'' = 1 + ''e'' − ''v'' = 1 − ''n'' + ''m''

Next, note that every time we add a cross, we are ensuring that each side of this cross ends up with a [[degree (graph theory)|degree]] 1 vertex. Thus, throughout the game, every face has at least one degree 1 vertex. Yet, the number of degree 1 vertices is invariant throughout the game, and remains at 4''n''. Hence, ''f'' is at most 4''n''. 

From this, we see ''m'' = ''f'' − ''k'' − 1 + ''n'' is at most {{nowrap|5''n'' − 2}} (since ''k'' is at least 1 and ''f'' is at most 4''n''). So the game must terminate, and it must terminate in at most {{nowrap|5''n'' − 2}} moves. Now, we argue it must terminate in exactly {{nowrap|5''n'' − 2}} moves.

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. Every face has at least one such vertex, so it must end with exactly one such vertex. So in the final configuration, ''f'' is exactly 4''n''.

Similarly, in the final configuration, the graph must be connected, since the outer face gets at least one degree 1 vertex per connected component, and cannot have more than one such vertex. So, in the final configuration, ''k'' is exactly 1.

Thus, to obtain the final configuration, we must have had ''m'' = ''f''−''k''−1+''n'' = 4''n''−1−1+''n'' = 5''n''−2.

A combination of standard Sprouts and Brussels Sprouts can also be played. The game starts with an arbitrary number (''n'') of dots or crosses. 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 (2''n'') and ({{nowrap|5''n'' − 2}}), depending on the number of dots or crosses having been added.

For ''n'' = 1, starting with a dot, the game will end after 2 moves. Starting with a cross, it will end after 2 moves if the first player adds a dot, after 3 moves if they add a cross: hence the first player has a winning strategy for both the normal and the misère version. For ''n'' > 1, the analysis is not completed.

==References==
{{reflist}}

'''Bibliography'''
{{refbegin}}
* [[Elwyn R. Berlekamp]], [[John Horton Conway|John Conway]] and [[Richard K. Guy]], ''[[Winning Ways for your Mathematical Plays]]'', 1992.
* {{Citation |url = http://www.sciencenews.org/sn_arc97/4_5_97/mathland.htm |title = Sprouts for Spring |publisher=Science News Online |archive-url = https://web.archive.org/web/20120716184402/http://www.sciencenews.org/sn_arc97/4_5_97/mathland.htm |archive-date = 16 July 2012 }}.
*{{cite book
 |last=Pritchard
 |first=D. B.
 |author-link=David Pritchard (chess player)
 |title=Brain Games
 |publisher=[[Penguin Books|Penguin Books Ltd]]
 |year=1982
 |chapter=Sprouts
 |pages=169–71
 |isbn=0-14-00-5682-3}}
{{refend}}
*[[Mackenzie, Dana]], "Answers to Sprouts", Cornell University Math Department, 2003-2004, {{cite web |url=https://pi.math.cornell.edu/~mec/2003-2004/graphtheory/sprouts/answerstosprouts3.html.}}

==External links==
* [http://gameofsprouts.com/refs.html The Complete (?) List of References for the Game of Sprouts]
* [http://www.wgosa.org/ ''World Game of Sprouts Association.''], Danny Purvis, association of Sprouts players
* [http://www.math.utah.edu/~alfeld/Sprouts/ The Game of Sprouts] at [[University of Utah]], with an interactive applet for human-vs-human play. (Requires Java)
* [http://sprouts.tuxfamily.org SproutsWiki], web site of Julien Lemoine and Simon Viennot, with the source code and binaries of their program

[[Category:Mathematical games]]
[[Category:Paper-and-pencil games]]
[[Category:John Horton Conway]]