Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.
|
|
|
|
Speaking of Sprouts...
Posted:
May 19, 1999 1:58 PM
|
|
Move by move analysis of Sprouts can only explore the shoreline of an
infinite ocean, but it is a lot of fun. For the purposes of this type
of analysis, I propose the following naming conventions.
A. If the first move of a game is an encircling move, the second
player can immediately make another encircling move, going from one of
the partially filled dots to the other. If this second move has
separated n dots from m dots, where n >= m, I propose that the
formation of the n dots plus the partially filled dot plus the m dots
be called nPm. (P stands for "pivot".) If an nPm is to serve as a
starting position for the purposes of analysis, I propose numbering
the n dots first, then the partially filled dot (the pivot), then the
m dots.
B. If X is a position and Y is a possible move from that position,
let X*Y be the position obtained by taking the position X and making
the move Y.
Combinatorial richness is to be found in so simple a formation as 2P1.
2P1 is transparently a switch: (I've been using the following
terminology, which I pulled out of a hat. I would love it if someone
would give me alternatives with deeper roots. Switch - a game which
yields the first player's choice of an even or odd number of
survivors. Trap - a game which yields the second player's choice of
an even or odd number of survivors. Null - a game containing p dots
with 0 or 2 lines attached and yielding q survivors where p and q are
of even parity. Inverter - a game where p and q are of odd parity.)
2P1+ 3(5)4 I (The final position is a trap.)
2P1- 3(5)4 I (See above.)
So far so good. But what is the Sprague-Grundy number of 2P1? The
only way to determine this, that I know of, is to look at every
position which 2P1 can go to after one move. These positions are:
(A) 2P1*1(5)1 - another switch! Sprague-Grundy number = ?
(B) 2P1*1(5)1[2] - another switch! SGN = ?
(C) 2P1*1(5)2 - another switch! SGN = ?
(D) 2P1*1(5)3 - another switch! SGN = ?
(E) 2P1*3(5)4 - a trap. SGN = 0
(F) 2P1*4(5)4 - a null. SGN = 0
Now it will be necessary to look at every position which can be
reached in one move from A,B,C and D above. (There are a lot of
these. As the total number of moves decreases, the percentage of
these which are unique tends to increase.) If any of these positions
are in turn switches, more analysis will be called for.
I wonder if anyone knows the Sprague-Grundy number of 2P1 or if there
is a less laborious way to find it than I have outlined?
Fortunately, it is possible to play Sprouts skillfully without knowing
Sprague-Grundy numbers. Sprague-Grundy numbers only come into play in
positions with 2 or more switches, and a player can often steer around
these.
|
|
|
|
