The game is played by two players, starting with a few dots drawn on a sheet of paper. To make a move, a player draws a curve between two dots or a loop from a dot to itself. The curve may not cross any other curve. The player makes a new dot on the curve, dividing it in two. Each dot can have at most three curves connected to it. The player who makes the last move wins.
Sprouts has been studied from the perspectives of graph theory and topology. It can be proven that a game started with n dots will last at least 2n moves and at most 3n - 1 moves. By enumerating all possible moves, one can show that the first player is guaranteed a win in games involving three, four, or five dots, while the second player can always win a game started with one, two, or six dots. At Bell Labs in 1990, [David Applegate]?, [Guy Jacobson]?, and [Daniel Sleator]? used a lot of computer power to push the analysis out to eleven dots. They conjectured that the first player has a winning strategy? when the number of dots divided by six leaves a remainder of three, four, or five.
The game of sprouts played an important role in the first part of the Piers Anthony book Macroscope?.
See also:
References:
![[Home]](wikipedia.png)