Dawson's sprouts

[Dan Hoey]

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

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

[Josh Purinton]

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.

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

[Jeff Peltier]

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