Game Description: Sprouts

Sprouts is a nice impartial game that two people can compete at using a piece of paper or chalkboard. This is true with lots of games, except that this game is extremely easy to set up.

Just draw a handful of dots on the paper at a reasonable distance from each other.

Each turn, a player chooses two dots and connects them with a line. In the middle of that line, the player draws a new dot. Then their turn is over. There are some restrictions here: the line may not cross any other lines (or go through any other dots) and, when finished, the dots cannot have more than three lines coming out of them. A player may choose just one dot and draw a looping line, but then this counts as two lines connected to that dot; the new dot drawn separates the line into two pieces.

In lieu of diagrams, here is a nice Java Sprouts applet.

Notice that the new dots drawn already have two lines coming out of them, so they can only be connected to one new line.

Sprouts is an extremely popular game in the Netherlands, with tournaments with large numbers of initial dots held.

As far as I am aware, the computational complexity of playing Sprouts is unknown. There is an interesting conjecture about the winnability from the starting position using a period of 6. The Sprouts Conjecture says that if the game begins with n dots and n is equivalent to 0, 1 or 2 modulo 6, then the second player has a winning strategy. Otherwise, the first player has a winning move. This seems like a high number for periodicity, especially for a game where there is no quick-trick to evaluate. Lots of effort has been put into supporting this conjecture, however. All starting positions up to n = 32 have been confirmed, including a few higher scattered cases!

Need a simple-to-play game? Pull out some paper, draw a few dots, and you're ready for Sprouts!