15 views

Skip to first unread message

Oct 13, 2006, 3:09:18 PM10/13/06

to Josh Purinton, sprouts...@googlegroups.com, th...@best.com, aaron.n...@gmail.com

Josh Purinton recently asked a question about whether one boundary

in a sprouts region might be replaced by its mirror image, without

having to mirror-image all the boundaries. I believe the answer is

no, but in generating a counterexample I came up with a better

construction for Sprouts positions equivalent to positions in Dawson's

Kayles. (Thane and Aaron: I'm including you because I gave you the

clunky version of the construction.)

in a sprouts region might be replaced by its mirror image, without

having to mirror-image all the boundaries. I believe the answer is

no, but in generating a counterexample I came up with a better

construction for Sprouts positions equivalent to positions in Dawson's

Kayles. (Thane and Aaron: I'm including you because I gave you the

clunky version of the construction.)

Recall that in Sprouts we define a "portal" to be a spot that

connects two regions. It has two "sites", one in each region.

I will write D(k) for a "Dawson's site of depth k". D(1) is

defined as a site of a portal spot whose other site is in a dead

region. D(k+1) is defined to be a site of a portal spot whose other

site is accessible only to a D(k). We can also define a D(0) to

be a dead or nonexistent spot.

We can construct a D(k) from a D(k-1) and a degree-0 spot X with

the two moves:

Y : X-X > ; -- connect X to itself without

separating any boundaries. The new

spot is called Y.

D(k) : X-Y > D(k-1) ; -- connect X to Y, separating the D(k-1)

from the rest of the region. The

outer site of the new spot is a

D(k).

Given D(k) in an otherwise empty region, the only possible moves

are to connect two of its portal points, leaving isolated D(i) and

D(k-i-2) positions, for 0 <= i <= k-2. This is clearly equivalent to

Dawson's Kayles played with k pins.

Another use of Dawson's sites is to generate positions that tend

to have reasonably large game complexity, since Dawson's Kayles

produces nim-values up to *9.

The following moves will generate a boundary with sites D(i),

D(j), D(k) in clockwise order. Assume a region with D(i-1), D(j-1),

D(k-1), and three degree-zero spots X, Y, and Z.

n : X-X > ; -- connect X to itself without

separating any boundaries.

n+1 : n-Y ; -- connect the new spot to Y.

n+2 : Y-Z ; -- connect Y to Z

n+3 : n+1.X - n+2.Y > D(k-1) -- connect n+1 to n+2, enclosing

D(k-1) in a region bounded by

Y, n+1, n+3, n+2 in clockwise

order

n+4 : n+3-Z > D(j-1) -- connect n+3 to Z, enclosing D(j-1)

in a region bounded by Z, n+2, n+3,

n+4 in clockwise order.

D(i) : X-n+4 > D(i-1) -- enclose D(i-1), creating a new

D(i) site.

After these moves, spot Z is a D(j) site and spot Y is a D(k) site.

If we call such a boundary a D(i,j,k), then my program (a CGSuite

script) tells me that

1. A position consisting of D(2,3,5);D(1,2,6) has nim-value *11,

while

2. A position consisting of D(2,3,5);D(1,6,2) has nim-value *5.

where ";" means to put boundaries in the same region.

These positions can be constructed from 19 initial spots in 38 moves.

If Aunt Bee can confirm or refute these nim-values, I'd appreciate it

greatly. My program has not been seriously debugged, and has many

possibilities for error.

While I would not be surprised to find a bug, I would be quite

surprised if there were no counterexample among the D(i,j,k);D(l,m,n)

positions.

Dan

Oct 14, 2006, 2:35:13 AM10/14/06

to Dan Hoey, sprouts...@googlegroups.com, th...@best.com, aaron.n...@gmail.com

In AJS notation, any anonymous degree-2 spot is an a D(1) site, and

any other occurrence of spot (a) in a component containing the region

(2,a,;) is a D(2) site. For example, the second (a) in (2,a,;0,12a,;)

is a D(2) site. Likewise, any other occurrence of spot (a) in a

component containing the regions (2,z,;z,a,;) is a D(3) site, and so

on.

any other occurrence of spot (a) in a component containing the region

(2,a,;) is a D(2) site. For example, the second (a) in (2,a,;0,12a,;)

is a D(2) site. Likewise, any other occurrence of spot (a) in a

component containing the regions (2,z,;z,a,;) is a D(3) site, and so

on.

Let D'(k) stand for a position containing only a D(k) site in an

otherwise empty region. Aunt Beast calculates the following

normal-play nim-values:

D'(0) = (,;) = *0

D'(1) = (2,;) = *0

D'(2) = (2,a,;a,;) = *1

D'(3) = (2,b,;b,a,;a,;) = *1

D'(4) = (2,c,;c,b,;b,a,;a,;) = *2

D'(5) = (2,d,;d,c,;c,b,;b,a,;a,;) = *0

D'(6) = (2,e,;e,d,;d,c,;c,b,;b,a,;a,;) = *3

Thus, Aunt Beast finds that D'(n) has the same nim-value as a row of n

pins in Dawson's Kayles (at least for 0 <= n <= 6); this suggests that

I have faithfully represented Dan Hoey's D(n) construction in AJS

notation and that Aunt Beast is correctly evaluating the resulting

positions.

In AJS notation, a D(i,j,k) boundary is then a boundary (abc) where

a,b,c are D(i), D(j), and D(k) sites respectively. For example, in the

position (2ab,;2,a,;2,z,;z,b,;), the boundary (2ab) is a D(1,2,3)

boundary. According to Aunt Beast, this position has a normal-play

nim-value of *3.

To check Dan's examples, let Q stand for the following partial

position:

(2,a,;2,z,;z,b,;2,y,;y,x,;x,w,;w,c,;2,d,;2,v,;v,u,;u,t,;t,s,;s,e,;)

Note that in a component containing Q, any occurrences of the spots

a,b,c,d,e outside of Q will be D(2), D(3), D(5), D(1), and D(6) sites

respectively.

Therefore:

1. (abc,2de,;Q) is a position consisting of D(2,3,5);D(1,2,6).

2. (abc,2ed,;Q) is a position consisting of D(2,3,5);D(1,6,2).

According to Aunt Beast, both positions have nim-value *0.

--

Josh Purinton

Oct 19, 2006, 1:16:09 PM10/19/06

to sprouts...@googlegroups.com, Dan Hoey, th...@best.com, aaron.n...@gmail.com

About the partial-mirror image Sprouts equivalence, I believe the answer is yes.

What do you think of the following justification.

Let MB be the mirror image of a boundary B in a Sprouts game noted G = {B;g}

{MB;g} denotes the partial mirror of game G.

1. Take the partial order defined by G<H if the longest Sprouts game in G is shorter than the longest Sprouts game in H.

Any option of G is strictly smaller than G: G'<G

Suppose there exist a smaller game G including a boundary B such as the outcome of G = {B;g} is different from the outcome of Partial mirror {MB;g} ;

{MB;g} is a shorter game too.

2. Suppose G is in N while the Partial mirror is in P; take the winning move of G which is in P

The converse move in {MB;g} is an N-Position.

We will show that whether this move is a joining move (not creating a new region) or a looping move, it creates a smaller Partial Mirror differentiating game, hence a contradiction.

The same reasonning applies on the winning move of {MB;g} if it was in N.

As the game G is a smallest game it can include at most two regions, separated by the boundary B. Otherwise any move not affecting B will create a smaller differentiating game (nearer to the endgame). So G is B;O/B;I the "/" representing the region separation. (See 3. for more formal proof).

Consider the moves in the region B;O, the same applies to the moves in the region B;I :

Let B being composed of a0...x0 spots in the Outer region and x1...a1 in the Inner region (a0 and a1 are the two sides of spot a); MB can be thought of being composed of a0...x0 in the Outer and a1...x1 in the Inner region :

- outer looping move on B from a to i : we get a new spot y0 three regions : x1...j1,h1...b1/y0,b0...h0/y0,j0...x0

- outer looping move on MB (x0...a0/x1...a1) from a to i : we get a new spot y0 three regions :

b1...h1,j1...x1/y0,b0...h0/y0,j0...x0

For an inner looping move, first mirror inside and outside boundaries so that you get the same outcome : you get a swmaller partial mirror move.

- joining move between B and a boundary O of the outer region

let take spot "a" from B without loss of generality, let call O' the boudary O minus the spot linked

you get a new spot y and the game b0...x0,y,O',y/x1...b1

- joining move between MB and a boundary O of the outer region : as the outer boundary is the same as B's outer boundary you get a partial mirror : b0...x0,y,O',y/B1...x1

3. Proof that smaller G can not have a separated region :

consider a smaller partial mirror game {B;g/h} including a separated region h, suppose it is in N, it has an option in P which is either :

- {B';g/h} where {(MB)';g/h}={MB';g/h} is in N, so then {B';g/h} would be smaller

- {B;g'/h} where {MB,g'/h} is in N, so then {B;g'/h} would be smaller

- {B;g/h'} where {MB;g/h'} is in N, so then {B;g/h'} would be smaller

- {B'-g'/h} where corresponding joining move {(MB)'-g'/h} is in N is the same as {MB'-g'/h} because writing {B;g/h} as {a0...x0;g/x1...a1/h} , {MB;g/h} can be written either as {x0...a0;g/x1...a1/h} or by double mirroring {a0...x0;g/a1...x1/h} and taking this last writing we see that the joining move from a0 to any spot in g will be for B : {b0...x0y0g'y0/x1...b1/h} and for MB : {b0...x0y0g'y0/b1...x1/h} and they are partial mirror on boundary b1...x1. So contradiction.

There can not exist a smaller partial mirror game with a different outcome than the original game.

--

Jeff

--

Jean-François

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu