Playing
Sprouts with Misere Grundy tables
|
Normal/Misere
i
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13
|
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
G(i) |
0/1 |
0/1 |
0/0 |
1/0 |
1/0* |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
Ppi |
|
0/1 |
3/3 |
3/0 |
1/2 |
4/3 |
4/1 |
0/3 |
3/0 |
3/3 |
1/4 |
4/1 |
4/4
|
0/3 |
3/0 |
3/3 |
1/1 |
4/1 |
4/4
|
0/3 |
3/0 |
3/3 |
1/1 |
4/1 |
4/4 |
0/3 |
3/0 |
An
|
|
|
2/2
|
0/1
|
3/3
|
3/0
|
1/2
|
2/1
|
2/1
|
0/2+
|
|
|
|
|
2/1
|
|
|
|
|
|
2/1
|
|
|
|
|
|
2/1
|
* Not the nimber 1, corresponding to the one-counter heap, but a
half-tame game as 4 + 4 game has value 0^0. News : in 2007 it was shown both by
Josh Purinton and Danny Purvis that the 4 + 4 + 4 game is a misere
losing position. There are strong evidences that this pattern continues
for any sum of 4 spots components.
Loop |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
0 |
1/0 |
2/2 |
2/1 |
0/3 |
2/2 |
2/0 |
1/2 |
2/1 |
2/2 |
0/2
|
2/2
|
2/2? |
1/2 |
2 |
2 |
0/2 |
2
|
2 |
1/2
|
2 |
2 |
0/2 |
2
|
2 |
1/2
|
2 |
2 |
1 |
2/2 |
0/1 |
0/3 |
2/0 |
1/0 |
1/2 |
2/1 |
2/1 |
0/2 |
2/0 |
3/3
|
1 |
2 |
2 |
0/2 |
2/0 |
2 |
1 |
2 |
2 |
0/2 |
2/0 |
2 |
1 |
2 |
2 |
0/2 |
2 |
2/1 |
0/3 |
0/0 |
2/0 |
1/1 |
1/1 |
2/1 |
2/2 |
0/0 |
2/0 |
2 |
1/1 |
2 |
2 |
0/0 |
2/0 |
2 |
1/1 |
2 |
2 |
0/0 |
2/0 |
2 |
1/1 |
2 |
2 |
0/0 |
3 |
0/3 |
2/0 |
2/0 |
1/1
|
2/1 |
2/1 |
0/0 |
2/0 |
2/2 |
1/1
|
2 |
2 |
0/0
|
2 |
2 |
1/1
|
2 |
2 |
0/0
|
2 |
2 |
1/1 |
2 |
2 |
0/0
|
2 |
2 |
4 |
2/2 |
1/0 |
1/1 |
2/1 |
0/1* |
0/2 |
2/0 |
2 |
2 |
2 |
2
|
0/0 |
2 |
2 |
2 |
2 |
2
|
0/0 |
2 |
2 |
2 |
2 |
2
|
0/0 |
2 |
2 |
2 |
5 |
2/0 |
1/2 |
1/1 |
2/1 |
0/2 |
0/0 |
2/0 |
2 |
1/1 |
2 |
2 |
0/0 |
2 |
2 |
1/1 |
2 |
2 |
0/0 |
2 |
2 |
1/1 |
2 |
2 |
0/0 |
2 |
2 |
1/1 |
6 |
1/2 |
2/1 |
2/1 |
0/0 |
2/0 |
2/0 |
1/1
|
2 |
2/2 |
0/0 |
2 |
2 |
1/1
|
2 |
2 |
0/0 |
2 |
2 |
1/1
|
2 |
2 |
0/0
|
2 |
2 |
1/1
|
2 |
2 |
7 |
2/1 |
2/1 |
2/2 |
2/0 |
2 |
2 |
2 |
2 |
2 |
2/0 |
2 |
2 |
2 |
2 |
2 |
2/0 |
2 |
2 |
2 |
2 |
2 |
2/0 |
2 |
2 |
2 |
2 |
2 |
8 |
2/2 |
0/2 |
0/0 |
2/2 |
2 |
1/1 |
2/2 |
2 |
0/0 |
2/0 |
2 |
1/1 |
2 |
2 |
0/0 |
2/0 |
2 |
1/1 |
2 |
2 |
0/0 |
2/0 |
2 |
1/1 |
2 |
2 |
0/0 |
9 |
0/2
|
2/0 |
2/0
|
1/1 |
2 |
2 |
0/0 |
2/0 |
2/0
|
1/1
|
2 |
2 |
0/0
|
2/0 |
2/0 |
1/1
|
2 |
2 |
0/0
|
2/0 |
2/0 |
1/1
|
2 |
2 |
0/0
|
2/0 |
2/0 |
10 |
2/2
|
3/3
|
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
11 |
2/2? |
1 |
1/1 |
2 |
0/0 |
0/0 |
2 |
2 |
1/1 |
2 |
2 |
0/0 |
2 |
2 |
1/1 |
2 |
2 |
0/0 |
2 |
2 |
1/1 |
2 |
2 |
0/0 |
2 |
2 |
1/1 |
If only one number is provided, it is for expected Normal
Spague-Grundy value.
3^0(0^1,1^1,2^1)+3^3(0^1,1^0,2^2)
3^0(0^1,1^1,2^1)+2^2(0^1,1^0)=(3^0,2^1,0^4,2^2,3^3)=1^5
2^1(0^0,1^0)+1^1(0^0)=(1^1,0^0,2^2)=3^3
(3^3,2^2,1^5,3^0,2^1,1^5)=0^4
3^3(0^1,1^0,2^2)+2^1(0^0,1^0)=(3^3,2^2,2^1,3^0,0^4)=1^5
3^0(0^1,1¨1,2^1)+0^0(2^2)=(0^0,1^1,2^2,1^5)=3^3
3^0(0^1,1^1,2^1)+1^1(0^0)=(1^1,0^0,3^3,2^2)=4^4
Pivot |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
0 |
0/1 |
1/0 |
1/0 |
1/1 |
0/1 |
0/1 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0
|
1/0 |
1/1 |
1 |
1/0 |
1/0 |
1/1 |
0/1 |
0/1 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
2 |
1/0 |
1/1 |
0/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1
|
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1
|
3 |
1/1 |
0/1 |
0/1 |
0/0 |
1/0 |
1/3 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
4 |
0/1 |
0/1 |
0/0 |
1/0 |
1/0 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
5 |
0/1 |
0/0 |
0/0 |
1/3 |
1/1 |
1/1 |
0/2? |
0/0 |
0/0 |
1/x? |
1/1 |
1/1 |
0/0 |
0/0 |
0/0 |
1/1 |
1/1 |
1/1 |
0/0 |
0/0 |
0/0 |
1/1 |
1/1 |
1/1 |
0/0 |
0/0 |
0/0 |
6 |
0/0 |
1/0 |
1/0 |
1/1 |
0/1 |
0/2? |
0/0
|
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0
|
1/0 |
1/1 |
1/1
|
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1
|
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
7 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
0/1 |
0/0 |
0/0 |
1/0 |
1/1 |
1/1 |
8 |
1/1 |
1/1 |
1/1 |
0/0 |
0/0 |
0/0 |
1/1 |
1/1 |
1/1 |
0/0 |
0/0 |
0/0 |
1/1 |
1/1 |
1/1
|
0/0 |
0/0 |
0/0 |
1/1 |
1/1 |
1/1 |
0/0 |
0/0 |
0/0 |
1/1 |
1/1 |
1/1
|
9
|
1/1 |
0/1
|
0/1
|
0/0
|
1/0
|
1/x?
|
1/1
|
0/1
|
0/0
|
0/0
|
1/0
|
1/1
|
1/1
|
0/1
|
0/0
|
0/0
|
1/0
|
1/1
|
1/1
|
0/1
|
0/0
|
0/0
|
1/0
|
1/1
|
1/1
|
0/1
|
0/0
|
You may remark there is no value of 2 in this
Pivot Table (5P6 to be confirmed)! This is compliant with the numerous
2 valued games in the
Loop
Table which do not have any 2 option.
Any real explanation of this fact is welcome.
Explanation of first table G(i) : it gives
the estimated Sprague-Grundy value
and Misere Grundy value of a position of just i spots :
for example,
the position below with three spots is a win on normal game G(3+)=1
with a possible move leading to a G0 : 1(4)1[2]
a loop with one spot inside and one spot outside 1L1 which value
can be found in Loop Table 0^1. It is a lost in misere game G(3-)=0
hence the notation 1/0 or 1^0 which is the start of genus sequence
notation 1^031... with every subsequent digit being the misere value of
the game when you add a new G2 position to it (a G2 or 2^2 is a game
with options of either a win or a lost at both normal and misere game :
0^1 and 1^0).
Another way of seeing it is that a 0^1 is a position with
same parity of cannibals and survivors : 4 cannibals and 2 survivors in
the example beneath ; whereas a 1^0 is a position leading opposite
parity of cannibals and survivors.
My conjecture is that amazingly, any Sprouts starting position has
either value 0 or value 1, both in Normal and Misere variants.
3 spots = 1^0
|
|
1L1, 4 cannibals give 2 survivors, same parity : 0^1 |
Explanation of first table PPi : after a looping
move, when connecting the two spots produced on the loop, you get to a
position with one spot belonging to two regions, it is called a pivot,
as in the example bellow left where you get a pivot belonging to the
external region with 0 spots and to the region with 3 spots : 0P3 of
value 1^1 ; read in the 'Pivot table' (see article of Roman about this
type of configuration).
When you connect this pivot to a spot in one of the two regions, this
region becomes what I call a PPi (Pivot Played to i spots region).
In the following example, the pivot is played to the 3 spots region
which becomes a PP3.
You should remark you get a position with the same life force as an i
spots region, namely 3xi liberties: two for the ghost, one for the pier
spot and three for each novice cannibal. But the Grundy value given in
second row of first table is often different of the one of the position
of just i spots : for example, this position PP3 is a 3^0 : G(PP3+) has
three options to 0^1, 1^1, 2^1 and none of
them is a misere lost x^0, so it is a lost in misere game G(PP3-)=0
hence the notation 3/0 or 3^0.
a
0P3 = 1^1
|
a
PP3 = 3^0 |
Here is a
novelty, the option 1^1 which is a win at both normal and misere game
because of the Universal Trap with value 0^0. With the G(i) and Ppi
table we can check two options : 7(9)8 which is the value of 2 spots
game : 0^0, and playing the pivot 8 to make a PP2 : 3^3. To get the
value of a position a^b from its options, you use the mex rule (minimum
excludent) both on the ais and the bis : mex (0,3)=1,
mex (0,3)=1. I leave you to check the other option connecting the two
spots is not a x^1 nor a 1^x but is the sum of a 2^2 with a 1^0...
a
position of value 1^1 because of its options right. The pier spots are
the magenta spots 7 and 8.
|
7(8)9, a position of value 0^0 (Universal Trap)
|
a
position with one external survivor and a PP2 of value 3^3
|
Table An or Anago n is for position you get after
first move in fianchetto (connecting a spot to another one). For
example A2 is for the position reached after :
2 1(3)2. So the Loop Table combined with An table gives you all the
values after Left first move.
Now just a few rules on how to calculate a
sum of positions to use these tables.
Despite normal impartial games where the sum of two positions of Grundy
numbers a and b is a XOR b (bitwise exclusive or), this is usually not
true in misere impartial games where there are a few cases depending on
the genus sequence, at least for tame games (nimbers of value 0^1, 1^0
and a^a) as is
explained in 'Winning Ways Vol.II':
- if one of the components is a firm compoonent a^a equivalent to a heap
of 'a' counters in the game of Nim, you can use normal nim arithmetic,
a^b+c^d=(a XOR c)^(a XOR c), the misere
value is not taken into account. It is the case in most games where a
universal trap is present because of its value 0^0.
- if every component is a 'fickle' componeent 0^1 (an empty nim heap) or
1^0 (a nim heap of just one counter) :
a^b+c^d=(a XOR c)^not(a XOR c).
You can think of the position as a sum of nim heaps of one counter
each,
for example three heaps of one counter each is a
win for next player in normal game but a losing position for next
player in misere game (NP) because 1^0+1^0+1^0=(1 XOR 1 XOR 1)^not(1
XOR 1 XOR 1)=1^0.
Thanks to Peter Alfeld for his nice
Sprouts java applet used for these drawings : http://www.math.utah.edu/~alfeld/Sprouts/
Thanks to Roman and Danny for their
patience and some useful corrections,
Thanks to Josh for giving me exact
normal grundy values for PPi up to PP5 and Pivots and Loops up to three
spots, computed by his AuntBeast program.
Back to World Game of Sprouts
Association Home Page