Winning Player Conjectures

The game Sprouts has a very interesting conjecture associated with it:

If the game starts off with n dots, then the first player has a winning strategy exactly when n mod 6 = 3, 4, or 5.

This seems strange. Why 6? How is this number inherent to the rules of Sprouts? Well, it's not clear that it is, because the conjecture has not been proven.

Nevertheless, supporting cases continue to be found. Somehow I am comforted by the idea that somewhere, there is a computer working to check cases for Sprouts. (Probably I feel the same way about the Collatz Conjecture. Someone is running that right now, right?) Sprouts is also studied in the misere version, with other cases being checked.

Along these same lines, there is a conjecture for Atropos:

If the game starts with n open circles along a side, then the first player has a winning strategy exactly when n mod 4 = 0 or 3.

This has a bit of intuition behind it: if the losing player can enforce that the game drags out to the last circle, then that last circle will cause the loss. Since the number of open circles at the beginning game are 1 + 2 + ... + n = n (n + 1)/2, this is even exactly when n mod 4 = 0 or 3.

Naturally, there is lots known about starting positions. Hex and Chomp both are wins for the first player, though the proof is non-constructive.

What about other games, such as Amazons? Which conjectures exist for the winning player from starting positions?

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!