Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: The Game of Sprouts
Posted:
Sep 25, 1995 9:23 AM
|
|
On Fri, 22 Sep 1995 Bill Haloupek wrote:
> 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
> haloupekb@uwstout.edu
>
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.
John Conway
|
|
|
|
