Editing Sprouts (game) (section)

==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;
|}