7 views

Skip to first unread message

Dec 9, 2008, 12:03:37 AM12/9/08

to sprouts...@googlegroups.com

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?

Dec 9, 2008, 10:30:18 AM12/9/08

to sprouts...@googlegroups.com

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

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

"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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu