27 views

Skip to first unread message

May 31, 2010, 12:31:02 PM5/31/10

to sprouts...@googlegroups.com

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)"),

*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.

*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:*

As it turns out, 4 spots is not half-tame, but the pattern does continue: 4+4+4....+4 (with"[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."

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)}

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.

May 31, 2010, 2:11:25 PM5/31/10

to sprouts...@googlegroups.com

[The formatting got messed up on my earlier post, so I'm trying again

in plain text.]

in plain text.]

May 31, 2010, 7:59:07 PM5/31/10

to sprouts...@googlegroups.com

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.

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.

Jun 1, 2010, 11:24:36 AM6/1/10

to sprouts...@googlegroups.com

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

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

Jun 1, 2010, 11:53:33 AM6/1/10

to sprouts...@googlegroups.com

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.

Jun 1, 2010, 12:40:06 PM6/1/10

to sprouts...@googlegroups.com

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

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

Jun 1, 2010, 8:05:37 PM6/1/10

to sprouts...@googlegroups.com

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

though:

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

Jun 2, 2010, 9:03:50 AM6/2/10

to sprouts...@googlegroups.com

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

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

- 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

--

Jeff

--

Jean-François

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu