Sprouts

Sprouts

Sprouts is a paper and pencil game with interesting mathematical properties. It was invented by the mathematicians John Horton Conway and Michael E. Peterson at Cambridge University in 1967.

Sprouts could be played by several players, but normally is played by two. At the beginning one has a number of points on a sheet of paper or balck-board, depending on a coice by the players. From each point three curves may be drawn, either linking one point to another or to itself. After drawing the desired curve, a new point is placed along the curve just traced.

While drawing a curve it is not allowed to cross another already drawn curve. In the figure below, we considere a simple game with two initial points. On the left is the original situation. To its right, A has drawn his first curve, linking a point to itself and generating a new point in its middle. To the right on the second line B responds, linking two more points. Notice that the two points she linked both have three curves leaving them – in short they have “died”. The number of curves that may still be drwan from a point is called its number of lives. Thus, on the left of the second line two points have no lives, one has just one and the other has three.

Further below we have the continuation of this match, won by B (red). The reason behind this is that there is only one move left after the figure on the right of the line above! Notice that the point up above (on the red line) cannot be linked to any other point, even though there still are points with lives.

At the beginning of a game with n points there are 3n lives. At each move, two lives are consumed and one is created, so that with each move there occurs the total loss of one life.

The simplest analysis of Sprouts is the following. If initially there are an odd number n of points on the paper, there will be 3n lives, also an odd number. After As first move there will remain one less life – an even number. Then B plays consuming one more life, and there remain an odd total number of lives. We see that after each of A's moves there will remain an even number of lives and that after each of B's moves an odd number. Therefore, A's and B's strategies is to play so that at the end of the game there will remain (with no possibilty of links) an even (A) or odd (B) number of lives.

If on the contrary there is initially an even number n of points, there will be an even number (3n) of lives.

After each of A's moves the remaining number will be odd, and after each of B's moves, an even number of lives. Therefore in this case their strategies are inverted between them.

The game of Sprouts has been well analysed already and there is quite a lot of material about it on the Internet. Until a few years ago, it has been simulated on the computer with up to 32 initial points in the normal form and up to 15 for misère play. The general conclusions are that the first to play has a certain advantage and can guarantee victory if the number of initial points is of the form 6k+3, 6k+4 or 6k+5 for some whole number k. We recommend as an exercize to show that in fact the first to play can surely win in the game with 3, 4 or 5 initial points.