Does reversing boundaries yield an equivalent position? (Was: Re: Dan Hoey's ideas on Sprouts position representation)

[Josh Purinton]

On Mon, Dec 8, 2008 at 5:46 PM, <lap...@tuxfamily.org> wrote:

Le Fri, 5 Dec 2008 17:05:01 -0500,
"Josh Purinton" <josh.p...@gmail.com> a écrit :
"Here's an idea for improving the Applegate-Jacobson-Sleator sprouts
program. In the set representation of a sprouts position there is a
set of regions, and each of these is a set of boundaries. Each
boundary is a sequence of spots encountered as you walk around the
boundary with your right hand touching the boundary. Suppose you
reversed the sequence defining one of these boundaries. Is this an
equivalent position?"

Here's the answer, with a counterexample :

1222A.12B.}2A.}2B.}]! is a misere losing position (the second player
can force 5 survivors)

1222A.B21.}2A.}2B.}]! is a misere winning position (the first player
must play 122a1AaB.}2A.}2B.}]! and then he can force 4 survivors).

 

Brilliant! How did you find that?

 

In October 2006, Dan Hoey constructed a normal-mode position whose nim value depends on the order of one of its boundaries. See here and here.

[lap...@tuxfamily.org]

Le Tue, 9 Dec 2008 00:03:37 -0500,

"Josh Purinton" <josh.p...@gmail.com> a écrit :

> In October 2006, Dan Hoey constructed a normal-mode position whose

> nim value depends on the order of one of its boundaries. See

> here<http://groups.google.com/group/sprouts-theory/browse_thread/thread/9721323bf772ff86>
> and
> here<http://groups.google.com/group/sprouts-theory/browse_thread/thread/04e64ff104f47b23>

Oops ! Sorry, I hadn't read these messages yet.

> Brilliant! How did you find that?

Well, first we tried to find the smallest counterexample we could
imagine.

You need at least one region, with two boundaries. The boundaries must
be asymmetric, so they must have at least 3 alive spots each, and of
different kinds. So, with Glop notation, we chose a "1" spot, a "2"
spot and a pivot (A for the first boundary, B for the second).

Then you get 12A.12B.}2A.}2B.}]! and 12A.1B2.}2A.}2B.}]!

With a development version of Glop, we could see that those 2 regions
haven't got the same game tree, which is encouraging, even if they have
the same nimbers and win/loss.

Then, we tried to modify a little bit each boundary, until we found a
position that had the needed property.

--
Julien Lemoine