Tuesday, March 30, 2010

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?

1 comment:

  1. I'm going to try to remember to bring this back so we can play. http://bit.ly/OthelloGame