Sprouts
| Sprouts | |
| Art | Paper and pencil game |
| Commerce. | Free game |
| year | 1967 |
| author | John Horton Conway |
| # Player | 2 |
| Age | unlimited |
| Duration | 2-10 minutes |
| All about games: Portal: Games | |
Sprouts ( Engl. Rungs ) is the name of 1967 by the mathematicians John Horton Conway and Michael S. Paterson invented the game for two players. Both players connect dots with lines on a piece of paper. Whoever places the last line wins. Aside from passing the time, the game is a great introduction to topology . Another name for the game is Peruvian Mole (ger .: Peruvian mole ).
The connection with the topology is that all sprouts parts are invariant under homeomorphisms : A sprouts part can be drawn on a blanket and then the blanket can be distorted as desired. Due to this deformation, all the essential characteristics of the game are retained, especially who wins the game.
history
Sprouts was invented in 1967 by math students John Conway and Michael Paterson at Princeton University as a pastime. According to Conway, the share of the two inventors is divided in a ratio of 2/5 (Conway) to 3/5 (Paterson), because Paterson had the idea of drawing a new point on the newly drawn lines. It got its name from its early, lively distribution on campus, which was reminiscent of the edible sprouts - it literally "sprout" everywhere and within a short time a large number of variants and proposed solutions emerged.
regulate
In the original version, Princeton sprouts , you start with any number of dots on paper - the more, the more complex and longer the game becomes. In turn, each player draws a line that begins in one point and ends in one point (another, or as a loop in the same). He draws a new point on the connecting line. The line must not touch or cross any existing lines or other points. There can be a maximum of three ends of a line in each point (if it is a loop, it counts as two ends). Whoever can draw a line last wins.
analysis
Although the game sounds quite simple, every player develops a feeling for his complexity after the first few games. However, the length of a game is always limited, as can be easily shown:
We consider a game with n starting points that takes m moves. At the beginning each point has 3 lives because a maximum of three lines can go out from it. So the game starts with 3n lives. Each turn consumes 2 lives (at the start and end of the line) and brings a new one (the new point drawn has exactly one free life), therefore reducing the number of lives by one. Since the last move still creates a free life (with the last drawn move), the following applies: 3n - m ≥ 1 , or vice versa: m ≤ 3n - 1 .
The game is therefore over after 3n - 1 moves at the latest .
At the end of the game, every still living point has exactly two dead neighbors (see diagram on the left). A dead point always has three neighbors, of which one or even none can be a survivor : no dead point can be the neighbor of two or even three different survivors , otherwise there would be a train connecting two of the survivors. All dead spots that have no surviving neighbors are called Pharisees ( Hebrew for the departed ).
The following applies:
- n + m = 3 n - m + 2 (3 n - m ) + p
because n + m is the total number of points at the end (initial points + number of moves, one point is added with each move), this in turn results from the number of survivors (3 n - m ) plus the number of neighbors 2 (3 n - m ) plus the number of Pharisees ( p ). By rearranging and combining you get:
- m = 2 n + p / 4
So a game takes at least 2 n moves, and the number of Pharisees is always divisible by 4.
notation
The official notation of the WGOSA , the so-called Conway notation , was created around 1999 in a discussion forum. This version was accepted for a long time until Dan Hoey found out that it could not describe all parts clearly. Hoey then developed his own notation, while the standard notation was added.
The standard notation starts with the number of starting points, followed by a “+” for a normal game or a “-” for a misère game , see below. Then the names of the players are listed in brackets, first the player who has the first move, then the second player. The inviting player is marked with an asterisk "*".
- Example: 3+ (Müller, Schmitz *) is a normal 3-point game between Müller and Schmitz, Schmitz has invited, it is Müller's turn.
In the standard notation, the starting points are numbered consecutively in the order in which they are used, new points are given consecutive numbers as they arise. Each move consists of at least one triple number of the form f (g) h , where f and h mark the endpoints of the line and g the newly drawn point. If a move creates a new region, the points that are separated from all others by this move are listed in square brackets.
- Example: 1 (10) 3 [2, 5, 7−9] is a move from 1 to 3, point 10 is newly created, points 2, 5 and 7 to 9 are separated from the rest.
As you can see in the picture opposite, there are at least two (topologically different) ways of connecting two points in certain situations.
- Example: The illustration shows a 5-point game, so far 1 (6) 2 3 (7) 4 has been drawn . For the next move 6 (8) 7 there are four topologically different move options.
The so-called Hoey-Exclam , an exclamation mark, is used to distinguish between the four possible moves . To understand how the Hoey Exclam works , imagine an ant crawling from point 8 towards points 6 or 7. When she arrives at point 6 or 7, she sees the neighbors of these points. The point with the higher number is either right or left. If the point with the higher number is on the left, the Hoey-Exclam is used.
-
Example: Variants A to D are noted as follows:
- A: 1 (6) 2 3 (7) 4 6 (8) 7
- B: 1 (6) 2 3 (7) 4 6! (8)! 7
- C: 1 (6) 2 3 (7) 4 6 (8)! 7
- D: 1 (6) 2 3 (7) 4 6! (8) 7
Who wins?
By fully analyzing all possible game courses one can show that the first player can win a game with 3, 4 or 5 points. The second player can win any game by one, two or six points.
David Applegate, Guy Jacobson and Daniel Sleator from Bell Labs solved all games in 1990 with a maximum of 11 points. They found that if the number of points divided by 6 results in a remainder of 3, 4, or 5, the first player has a winning strategy . A more in-depth analysis from 2007 shows that this applies to all games with up to 32 points. It is assumed that the rule mentioned applies to any number of points.
variants
Sprouts can be played misère - in contrast to normal sprouts, the player who draws the last line loses. Compared to the original, Misère Sprouts proves to be more difficult to analyze. The current guess is that if the number of points divided by 6 equals 0, 4, and 5, the player wins on move first - the games being an exception to this rule for a point total of 1 or 4.
In black-and-white sprouts , the drawing player has the choice of whether or not to place a point on the line he has just drawn. This version has been solved, the beginning player wins if the game is perfect. In Brussels sprouts (jokingly named after the English translation for Brussels sprouts ) you don't play with dots, but with crosses, the four arms of which have to be connected. So each point has four “lives”, but the lines are given. This version is much simpler than the original version, solved, and just meant for fun. Each game lasts 5n-2 moves.
In Antwerp sprouts , the game is also played with colors.
literature
Martin Gardner : Mathematical Carnival. Penguin, 1976 (German Mathematical Carnival . Ullstein, 1977)
Individual evidence
- ↑ Topic: Sprouts Notation ( Memento from March 6, 2010 on WebCite ) on The Math Forum @ Drexel (in the WebCite archive)
- ^ Article by Danny Purvis in the newsgroup geometry.research
- ↑ Lemoine, Viennot, A further computer analysis of Sprouts (PDF; 180 kB), 2007
- ↑ Julien Lemoine, Simon Viennot, Analysis of misere Sprouts game with reduced canonical trees , 2009
- ↑ Black and White Sprouts ( Memento from March 6, 2010 on WebCite ) on World Game Of Sprout Association (in the WebCite archive)