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  3 spots = 1^0
   
After one move 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.

0P3 a 0P3 = 1^1
PP3 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...

1^1 a position of value 1^1 because of its options right. The pier spots are the magenta spots 7 and 8.
PP3   7(8)9, a position of value 0^0 (Universal Trap)
3^3 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