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 SpragueGrundy 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! SpragueGrundy 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 SpragueGrundy 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 SpragueGrundy numbers. SpragueGrundy numbers only come into play in positions with 2 or more switches, and a player can often steer around these.



