4 spots = {*3,{*1,*2,{*3,{*2}}}}

[Josh Jordan]

According to http://www.wgosa.org/SproutsMisereGrundy2007-4.htm (oddly, currently reachable by through a link on www.wgosa.org that reads "Playing Sprouts with Misere Grundy Tables, by Jeff Peltier (June 8, 2008)"),

"[4 spots is] 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."

As it turns out, 4 spots is not half-tame, but the pattern does continue: 4+4+4....+4  (with n 4s) seems to be a misere losing position for n >= 3 (verified by Aunt Beast for 1 <= n <= 10). There should be a direct way to prove that this losing trend continues indefinitely, since 4 spots is equivalent to the game {*3,{*1,*2,{*3,{*2}}}}, as I will show below.

First, recall some standard definitions:

*A means a nim-pile of size A. For example, *1 is a nim-pile with 1 counter, and *0 is an empty nim-pile.

{G,H,I,...} denotes a game from which the valid moves are to one of G,H,I,....  For instance, 2 spots = {A2,1L0}.

From a nim pile, the valid moves are to any smaller nim pile:

*0 = {}

*1 = {*0}

*2 = {*0,*1}

*3 = {*0,*1,*2}

*n = {*0,*1,*2,...,*(n-1)}

G+H+...+I denotes the "sum" of the games G,H,...,I; that is, the game in which a legal move is in one of G,H,...,I, leaving the rest unchanged. For example, *3+*4+*5 denotes a game of nim with 3 piles. Another example is 8 1(9)1[2-5] 1(10)9[2], the resulting game can be regarded as 3P1+3 spots, which, as we will see below, has the same outcome in misere and normal play as 3P1+*1.

G = H ("G is equivalent to H") means that G can be replaced by H in any sum of games without changing the outcome in misere or normal play. More precisely, G = H means that for any impartial finite combinatorial game X, we have:

1. o+(X+G) = o+(X+H), and

2. o-(X+G) = o-(X+H),

Where o+(G) is the normal-play outcome of G, and o-(G) is the misere-play outcome of G. 

Examples of equivalences:

1 spot = *0

1P1 = *1

A2 = *2

1L0 = *2

2 spots = {A2,1L0} = {*2,*2} = {*2}

A3 = *0

A4 = *3

3 spots = *1

3L0 = 2L1 = {*1,*2,{*3,{*2}}}

With the above facts in hand, we can see that 4 spots = {A4,3L0,2L1} = {*3,{*1,*2,{*3,{*2}}}}. This is a wild game of length 6 with nim-values 1^0, according to Lemoine & Viennot's database of reduced canonical trees for all sprouts positions reachable from an initial position of 6 spots.

It clear from the above that 4 spots is not half-tame. According to Winning Ways, p 415, "A wild game is half-tame provided that (1) all options of H are tame or half-tame, (2) if H has an option 0^1, it has an option 0^0, and (3) if H has an option 1^0, it has an option 1^1." It is easy to show that {*1,*2,{*3,{*2}}}, restive with nim-values 0^3, is not tame. Furthermore, {*1,*2,{*3,*2}}} is not half-tame since it has an option 1^0 (*1) but no 1^1 option. Since 4 spots has {*1,*2,{*3,{*2}}} as an option, 4 spots itself is not half-tame.

I am grateful to Julien Lemoine and Simon Viennot for providing me with a pre-release version of misere Glop and the above-mentioned database of reduced canonical trees. This database, when it is made public, should greatly advance the state of the art of sprouts analysis.

[Josh Jordan]

[The formatting got messed up on my earlier post, so I'm trying again
in plain text.]

[Josh Jordan]

In my earlier message, I wrote that 4 isn't half-tame, but in fact it
is. (It's nice how publishing my thoughts helps me notice errors in my
thinking.) My mistake was overlooking the fact that {*3,{*2}} is tame
with nim-values 1^1.

Here's how to show that 4 spots is half-tame:

- 2 spots = {*2} is tame with nim-values 0^0.

- 2P1 = {*3,{*2}} is tame with nim-values 1^1.

- 3L0 = 2L1 = {*1,*2,{*3,{*2}}} is restive with nim-values 0^3, and is
also half-tame since every option is tame, and it has an option with
nim-values 1^0 (*1) and an option with nim-values 1^1 ({*3,{*2}}).

- 4 spots = {*3,{*1,*2,{*3,{*2}}}} is wild (because its tame option *3
doesn't suffice to determine its nim-values) with nim-values 1^0, and
is also half-tame since every option is either tame or half-tame, and
it has no option with nim-values 0^1 or 1^0.

Since 4 spots is half-tame, we can conclude, by the Half-Tame theorem,
that 4 spots + 4 spots is tame of genus 0^0.

[Jean-François Peltier]

Hi Josh,

Thanks for this very nice work, I wanted to do for a long time!

How did you find out that 3L0 is equivalent to 2L1 ? (I was worried about the 0P3 option of 0L3 which is a 1¹ known to Roman for a long time, is 0.0.}]0.2.}]! option of 2L1 the equivalent option (it seems right for the {*3,{*2}} option)?

Also how do you get rid of some wild options in the sub-tree of A4 ?

So 4 spots + 4 spots is tame of genus 0^0 (and so is an even sum by pair-grouping and using the fact that sum of tame games is tame), did you try to pursue for an odd sum ?

I had a go with MisereSolver in Cgsuite with the canonical form you provided, here are the results :

C being 2L1 {*1,*2,{*3,{*2}}} and D being 4-Spots :

C is Restive, D is HalfTame
Phylum(D) -> "Wild"
Genus(D+D) = 0⁰
Genus(D+D+D) = 1⁰²... tested up to D+D+....+D (17 times)
IsHalfTame (D+D+D) -> true
Phylum(D+D) -> REVERSIBLY_TAME
IsRestive(D) -> false
IsRestless(D) -> false

Unfortunately, this release of Cgsuite does not seem to include MisereQuotient, so I can't check it is an infinite quotient.

Regards,

--
Jeff

--
--
Jean-François

[Josh Jordan]

Both 3L0 and 2L1 are the same game in Lemoine & Viennot's reduced canonical tree database, which gives the reduced game tree for every position that that can occur in a game starting with 6 initial spots.  In their paper <http://arxiv.org/abs/0908.4407>, Lemoine & Viennot mention that there are over 25,000 distinct game trees in this set, even after pruning reversible moves!  As you can imagine, this is an extraordinarily useful tool for analysis. As for A4, the only wild option shown in the database is 3L0/2L1, so the rest must be reversible. 

[Jean-François Peltier]

Thanks for this information!

I had a closer look at cgsuite and the plugin tab allows you to start MisereSolver, here are the results:

Surprisingly, 4-spots is in fact quite small (46 different elements only) with a P set of 11 elements, and converges at heap-7 (7 instances of the starting component 4-spots) :

The exponent means the number of copies of an element, so for example b2c means two copies of 'b' (usually *2) and one copy of c. You can see 'e' which must correspond to the 4-spots component is in P as well as e² which is equal to b², meaning that two copies of 4-spots is a P component. To derive e³, you use the Bendix reduction e³ = e².é = b²e = e is in P...
e⁵ = e³.e² = (e².e)e² = (b²e)e² = (e)b² = b²e = e

=== Presentation Changed at Heap 7 ===

Q = <a,b,c,d,e | a2=1,b3=b,b2c=c,c3=c2,b2d=d,c2d=c2,cd2=c2,d3=c2,b2e=e,c2e=ac2,e2=b2>; P = {a,b2,c,c2,abd,cd,d2,e,ace,abde,bcde}

|Q| = 46; |P| = 11

7 mutual divisibility classes.

Idempotent  |MaxSG| |Arch|  Lower Covers              MaxSG P-Pos
----------- ------- ------- ------------------------- -------------------------
1                2       2  b2                        a                       
b2               8       8  c2                        b2 e                    
c2 *             4      36                            c2                      

         1 <- 0
         a <- 1
         b <- 2
        ab <- 3
         c <- 2/
        ac <- 2[/1]
         d <- 2[/1]21
         e <- (2[/1]21)3

--
Jeff

--
--
Jean-François

[Dan Hoey]

Thanks for running cgsuite on this, Jean-François. One minor clarification,
though:

On 6/1/10 12:40 PM, Jean-François Peltier wrote:
> ... converges at heap-7 (7 instances of the starting component 4-spots)
Actually, the heap game is calculated by linearizing the game
*[(2[/1]21)3],
and defines only seven sizes of heaps:

heap-1 = *[1] (player may remove one token),
heap-2 = *[2] (player may remove one or two tokens),
heap-3 = *[3] (player may remove one, two, or three tokens),
heap-4 = *[2/] (player may remove two tokens),
heap-5 = *[2[/1]] (player may remove one or two tokens),
heap-6 = *[2[/1]21] (player may remove one, four, or five tokens), and
heap-7 = *[(2[/1]21)3] (player may remove one or four tokens).

So convergence at heap-7 actually means convergence at any number of copies
of heap-7, and is the only kind of convergence possible. That's what
happens when you calculate the misère quotient of a game (or a finite
number of games) rather than of a HeapRule that can apply to arbitrarily
large heaps.

Dan

[Jean-François Peltier]

Thanks Dan for making it right (I keep forgetting what heaps are in the context of directed graphs).

This settles an old question, so thanks to MisereSolver, here is the guide to playing the first moves for n copies of 4-spots components, n>=2.

- if 1st player plays the A4 option (*3) then answer by making this *3 a *0 (for example anago in the 2 other spots 1a1a.1b1b.}]) yielding e^(n-1) which is P.
- if 1st player plays the 0L3 or 1L2 option, then answer by playing the anago A4 in another e component yielding e^(n-2)+0L3+A4 or e^(n-2)+1L2+A4 which in Quotient terminology is ab.d.e^(n-2) as A4 is *3 and corresponds to ab (*1+*2) and 0L3 and 1L2 correspond to 'd'. If n is even, e^(n-2) is equivalent to b², so yielding position is ab³d = abd is in P. If n is odd, e^(n-2) is equivalent to e.b^(n-1) = eb² = b²e = e, so yielding position is equivalent to abde in P.

--
Jeff

--
--
Jean-François