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. Each spot starts with three lives opportunities to connect a line 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. There must be at least one survivor, namely the spot added in the final move. At the end of the game each survivor has exactly two dead neighbors , in a technical sense of "neighbor"; 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 Hebrew for " separated ones ". Suppose there are p pharisees. Rearranging gives:. The normal-play results are all consistent with the pattern observed by Applegate et al.
A variant of the game, called Brussels Sprouts , starts with a number of crosses, i. 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. Suppose there are p pharisees. Rearranging gives:. Consequently, a game lasts for at least 2 n moves, and the number of pharisees is divisible by 4.
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.
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 or she 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 of the starting position. This can be done by hand only for a small number of spots, and all the new results since have been obtained by extensive search with computers.
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 , by David Applegate , Guy Jacobson , and Daniel Sleator. 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 , 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 by Josh Jordan up to 14 spots. In , Julien Lemoine and Simon Viennot introduced an algorithm based on the concept of nimbers to accelerate the computation, reaching up to 32 spots. The normal-play results so far are all consistent with the conjecture of Applegate, Jacobson, and Sleator.
In , 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.
The same team reached up to 16 spots in The table below shows the pattern, with the two irregular values in bold. A variant of the game, named Brussels Sprouts after the cruciferous vegetable , starts with a number of crosses, i. 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. Each move removes two free ends and introduces two more.
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. 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 he has just drawn. The duration of the game lays between 2n and 5n - 2 , depending on the number of dots or crosses having been added. Copyright The image is from Wikipedia Commons. Wikipedia Page.
0コメント