.gif)
Sprouts (game)
Encyclopedia
Sprouts is a pencil-and-paper game with interesting mathematical
properties. It was invented by mathematician
s John Horton Conway
and Michael S. Paterson at Cambridge University
in 1967.
The game is played by two players, 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.
In so-called normal play, the player who makes the last move wins. In 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. http://www.arxiv.org/abs/math.CO/0603027, p. 21)
The diagram on the right shows a 2-spot game of normal-play Sprouts. After the fourth move, most of the spots are dead–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.
In the following proofs, we suppose that a game starts with n spots and lasts for exactly m moves.
for "separated ones
"). Suppose there are p pharisees. Then
since initial spots + moves = total spots at end of game = survivors + neighbors + pharisees. Rearranging gives:
So a game lasts for at least 2n moves, and the number of pharisees is divisible by 4.
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.
reports that the 6-spot normal game was proved to be a win for the first 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
. 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 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.
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.. They have extended the computation up to 44 spots in 2011, and three isolated starting position, with 46, 47 and 53 spots..
The normal-play results so far are all consistent with the conjecture of Applegate, Jacobson and Sleator.
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. The same year, Julien Lemoine and Simon Viennot reached 17 spots with complicated algorithms. They were able to extend their analysis up to 20 points in 2011.
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. The table below shows the pattern, with the two irregular values in bold.
So each move removes two free ends and introduces two more. Despite this, the game is finite, and indeed the total number of moves is predetermined by the initial number of crosses: the players cannot affect the result by their play. With n initial crosses, the number of moves will be 5n−2, so a game starting with an odd number of crosses will be a first player win, while a game starting with an even number will be a second player win regardless of the moves.
To prove this (assuming that the game ends), let m denote the number of moves and v,e,f denote the number of vertices, edges, and faces of the planar graph obtained at the end of the game, respectively. We have:
The Euler characteristic for planar graphs is 2, so 2 = f-e+v = 4n-2m+n+m = 5n-m , hence m = 5n-2.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
properties. It was invented by mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
s John Horton Conway
John Horton Conway
John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...
and Michael S. Paterson at Cambridge University
University of Cambridge
The University of Cambridge is a public research university located in Cambridge, United Kingdom. It is the second-oldest university in both the United Kingdom and the English-speaking world , and the seventh-oldest globally...
in 1967.
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.
In so-called normal play, the player who makes the last move wins. In 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. http://www.arxiv.org/abs/math.CO/0603027, p. 21)
The diagram on the right shows a 2-spot game of normal-play Sprouts. After the fourth move, most of the spots are dead–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
It is not evident from the rules of Sprouts that the game always terminates, since the number of spots increase at each move. The correct approach is to consider the number of lives (opportunities to connect a line) instead of the number of spots. Then, we can show that if the game starts with n spots, it will end in at most 3n−1 moves, and last at least 2n moves.In the following proofs, we suppose that a game starts with n spots and lasts for exactly m moves.
Maximum number of 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 3n−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 3n−m survivors. There must be at least one survivor, namely the spot added in the final move. So 3n−m ≥ 1; hence a game can last no more than 3n−1 moves.Minimum number of moves
At the end of the game each survivor has exactly two dead neighbors, in a technical sense of "neighbor", different from the ordinary graph notion of adjacency; see the diagram on the right. 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 HebrewHebrew language
Hebrew is a Semitic language of the Afroasiatic language family. Culturally, is it considered by Jews and other religious groups as the language of the Jewish people, though other Jewish languages had originated among diaspora Jews, and the Hebrew language is also used by non-Jewish groups, such...
for "separated ones
Pharisees
The Pharisees were at various times a political party, a social movement, and a school of thought among Jews during the Second Temple period beginning under the Hasmonean dynasty in the wake of...
"). Suppose there are p pharisees. Then
since initial spots + moves = total spots at end of game = survivors + neighbors + pharisees. Rearranging gives:
So a game lasts for at least 2n moves, and the number of pharisees is divisible by 4.
Importance in real games
Real games seem to turn into a battle over whether the number of moves will be k or k+1 (for some k, depending on the early moves in the game) with other possibilities being quite unlikely. http://mathforum.org/kb/message.jspa?messageID=1091005&tstart=0 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).Who has the win ?
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 he plays 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
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
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 PlaysWinning Ways for your Mathematical Plays
Winning Ways for your Mathematical Plays by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy is a compendium of information on mathematical games...
reports that the 6-spot normal game was proved to be a win for the first 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
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
, in 1990, by David Applegate, Guy Jacobson, and Daniel Sleator
Daniel Sleator
Daniel Dominic Kaplan Sleator is a professor of computer science at Carnegie Mellon University. He discovered amortized analysis and he invented many data structures with Robert Tarjan, such as splay trees, link/cut trees, and skew heaps. He also pioneered the theory of link grammars and developed...
. 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 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.
| Spots | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ... |
| Normal Outcome | Loss | Loss | Win | Win | Win | Loss | Loss | Loss | Win | Win | Win | ... |
In 2001, Riccardo Focardi and Flamina Luccio described a method to prove by hand that the normal 7-spot game is a Loss.
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
Nimber
In mathematics, the proper class of poo poo nimbers is introduced in combinatorial game theory, where they are defined as the values of nim heaps, but arise in a much larger class of games because of the Sprague–Grundy theorem...
s to accelerate the computation, reaching up to 32 spots.. They have extended the computation up to 44 spots in 2011, and three isolated starting position, with 46, 47 and 53 spots..
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. The same year, Julien Lemoine and Simon Viennot reached 17 spots with complicated algorithms. They were able to extend their analysis up to 20 points in 2011.
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
Modulo operation
In computing, the modulo operation finds the remainder of division of one number by another.Given two positive numbers, and , a modulo n can be thought of as the remainder, on division of a by n...
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.
| Spots | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ... |
| Misère Outcome | Win | Loss | Loss | Loss | Win | Win | Loss | Loss | Loss | Win | Win | Win | Loss | Loss | Loss | ... |
Brussels Sprouts
A variant of the game, called Brussels Sprouts, 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.So each move removes two free ends and introduces two more. Despite this, the game is finite, and indeed the total number of moves is predetermined by the initial number of crosses: the players cannot affect the result by their play. With n initial crosses, the number of moves will be 5n−2, so a game starting with an odd number of crosses will be a first player win, while a game starting with an even number will be a second player win regardless of the moves.
To prove this (assuming that the game ends), let m denote the number of moves and v,e,f denote the number of vertices, edges, and faces of the planar graph obtained at the end of the game, respectively. We have:
- e = 2m since at each move, the player adds 2 edges.
- v = n + m since at each move, the player adds one vertex (and the game starts with n vertices).
- f = 4n since there is exactly one free end in each face at the end of the game, (and the number of free ends does not change during the game).
The Euler characteristic for planar graphs is 2, so 2 = f-e+v = 4n-2m+n+m = 5n-m , hence m = 5n-2.
External links
- The Complete (?) List of References for the Game of Sprouts
- World Game of Sprouts Association., Danny Purvis, association of Sprouts players
- The Game of Sprouts at University of UtahUniversity of UtahThe University of Utah, also known as the U or the U of U, is a public, coeducational research university in Salt Lake City, Utah, United States. The university was established in 1850 as the University of Deseret by the General Assembly of the provisional State of Deseret, making it Utah's oldest...
, with an interactive applet for human-vs-human play. - SproutsWiki, web site of Julien Lemoine and Simon Viennot, with the source code and binaries of their program
- 3graph, a freeware Sprouts program (Windows)