> I have my Finite Math class studying tournament graphs. > Yesterday we had a tournament using "The Game of Sprouts", > invented by John H. Conway (hello John!) and Michael Paterson. > I found out about this game in an article in the Amer. Math. > Monthly, May 1993. It really provided a fun way to teach > some graph concepts. > > Anyway, I was wondering if any work has been done on strategies > for this game. Is there a winning strategy for the first (or > second) player? I've worked out a few rules of thumb based on > parity of exposed vertices. The article cited above just deals > with what graphs can arise. > > Thanks in advance for any help. My students expect me to play > the winner. Guess I had better win, huh? The efficacy of > mathematical training hangs in the balance.... ;+) > > Bill Haloupek > U of Wisconsin-Stout > email@example.com > I think I mentioned the fact that a team of people at Bell Labs a few years ago used a lot of computing to force the analysis of sprouts out to 11 spots?
In practice, the fight is about whether the game will last precisely m moves, as against m+1 or m-1.
Now the number of moves is 3n minus the number of spots that remain live at the end of the game, so you want to control THAT.
If you can divide the board into k regions bounded by curves already drawn, in such a way that each region has a live spot in its interior, then the number of spots that are still live at the end of the game will be at least k.
[This is because any move will be in just one of those regions, and will leave a live spot in that region.]
This provides a lower bound for the number of ultimate live spots.
A lower bound is provided by the "Pharisee theorem". At the end of the game, the two nearest neighbors of any live spot will be dead. A Pharisee is any ultimately dead spot that's NOT one of these two neighbors of a live one. The Pharisee theorem is that the total number of moves is 2n + P/4, where P is the number of Pharisees. Another way to say it is that the number of live spots at the end of the game will be at MOST n - P/4.
You can use this by deliberately ensuring that some spot will be a Pharisee, by killing off all spots reasonably close to it.
[I must confess that this isn't all that much use.]
If you want to learn how to play Sprouts reasonably well, I recommend that you play a few games while paying particular attention to the number of spots left alive at the end of the game - let's call them "survivors" - why did I never do that before? Once you've seen how the fight is really about the number of survivors, you'll be able to watch the "live region" method working for you (or maybe your opponent!). When you get really good at that, you can start looking out for Pharisees.