11 views

Skip to first unread message

Jan 22, 2009, 8:34:06 PM1/22/09

to sprouts...@googlegroups.com

I've already discussed a notation for partial positions such as

^xy:xy.0!, which refers to the pivot-loop fragment ...L0. Also, in

the "Algorithms for planar graph canonization" thread I discussed some

ideas on partial positions that lead to a proof that ^x:x.0! = ^x:x2!

in normal or misere games. However, I am going have to extend my

analysis somewhat to deal with partial positions that have more than

one parameter.

^xy:xy.0!, which refers to the pivot-loop fragment ...L0. Also, in

the "Algorithms for planar graph canonization" thread I discussed some

ideas on partial positions that lead to a proof that ^x:x.0! = ^x:x2!

in normal or misere games. However, I am going have to extend my

analysis somewhat to deal with partial positions that have more than

one parameter.

A _partial position (of order K)_ is a set of regions that share K

pivots with other regions of the game. I will not now require that

the pivots link to a single exterior region. If P is such a partial

position, we call p1(P) the set of parameters of P, and p2(P) the set

of (unordered) pairs of parameters of P.

The interaction of P with the rest of the game is determined by the

functions E*(P) and I*(P), defined below. E*(P) defines the result of

moves exterior to P, and I*(P) defines the result of moves interior to

P.

Define E*(P) to be a function from p1(P) union p2(P) to the set of

partial positions that arise from removing one or two parameters from

P, as follows. For each pivot x in p1(P), E*(P)(x) = E_x(P) is the

partial position of order K-1 formed by removing the parameter x from

P. For each pair {x,y} in p2(P), E*(P)({x,y}) = E_xy(P) is the

partial position of order K-2 formed by removing the parameter x and y

from P.

Define I*(P) to be a function from {{}} union p1(P) union p2(P) to the

set of partial positions that arise from moving within P, as follows.

I*(P)({}) = I(P) is the set of partial positions of order K that arise

from moves not involving any parameters of P. For x in p1(P),

I*(P)(x) = I_x(P) is the set of partial positions of order K-1 that

arise from moves connecting the pivot x to a non-parameter of P. For

{x,y} in p2(P), I*(P)({x,y}) = I_xy(P) is the set of partial positions

of order K-2 that arise from connecting pivots x and y in a region of

P.

Now we define what it means for a partial position to be reducible to

another. Suppose P and Q are partial positions of order K. I will

consider that the parameters of P and Q are given the same names in

the same order, though in practice we may need to use a bijection

between the parameter sets. I will say that P and Q are coreducible

if P'=Q', where P' is either P or a partial position to which P is

reducible, and Q' is either Q or a partial position to which Q is

reducible. Suppose in addition

1. Every E_x(P) and E_x(Q) are coreducible.

2. Every E_xy(P) and E_xy(Q) are coreducible.

3. Every element of I(Q) is coreducible with an element of I(P),

and for every partial position S in I(P) not coreducible with

an element of I(Q), I(S) has an element coreducible with Q.

4. Every element of I_a(Q) is coreducible with an element of

I_a(P), and for every partial position S in I_a(P) not

coreducible with an element of I_a(Q), I(S) has an element

coreducible with Q.

5. Every element of I_ab(Q) is coreducible with an element of

I_ab(P), and for every partial position S in I_ab(P) not

coreducible with an element of I_ab(Q), I(S) has an element

coreducible with Q.

Then we say P is reducible to Q.

Theorem: Suppose P, Q, and S are three partial positions of order K,

such that P and Q have the same parameter set r...s, while S has the

parameter set x...y. Then the positions PS=r...s=x....y! and

QS=r...s=x...y! have the same outcome in normal play, and have the

same outcome in misere play except possibly when QS=r...s=x...y! is

the endgame.

The proof is a straightforward exercise in Sprague-Grundy theory. The

exception in misere play accounts for the proviso. [QED]

I'll now describe an important result of the theorem, which may have

immediate application in Sprouts play. I have already mentioned that

^x:x.0! is reducible to ^x:x2! . I haven't mentioned that ^x:x<1>!

and ^x:x2.1! are also reducible to ^x:x2! . (It is notable that

^x:x12! is _not_ reducible to ^x:x2! . The nonequivalence can be

demonstrated by joining the positions to ^x:xAB/A2/B2!.)

The important result is that ^xy:xy.0! is reducible to ^xy:xy2! . The

demonstration is as follows:

1. E_x(^xy:xy.0!) = ^x:x.0!; E_x(^xy:xy2!) = ^x:x2! . These

positions have already been shown to be reducible. The

demonstration for E_y is identical.

2. E_xy(^xy:xy.0!) = 0! = *[0]; E_xy(^xy:xy2!) = 2! = *[0] .

3. I(^xy:xy.0!) = {^xy:xy.AB/AB!}, and I(^xy:xy.AB/AB!) contains

^xy:xy2. The remainder of I(^xy:xy.0!) is {}, which is

equal to I(^xy:xy2!).

4. I_x(^xy:xy.0!) = {^x:x<1>}; I_x(^xy:xy2!) = {^x:x2!} .

These positions have already been shown to be reducible.

The demonstration for E_y is identical.

5. I_xy(^xy:xy.0!) = 0.2! = *[1]; I_xy(^xy:xy2!) = 22! = *[1].

Therefore ^xy:xy.0! is reducible to ^xy:xy2! . [QED]

This reducibility result allows us to shorten the game tree by two

moves when L1 is a good move.

Dan

Jan 24, 2009, 3:37:14 AM1/24/09

to sprouts...@googlegroups.com

The important result is that ^xy:xy.0! is reducible to ^xy:xy2! . The

demonstration is as follows:

I haven't thoroughly read all your posts about notation. Is this

^xy:xy.0! is reducible to ^xy:xy2!

equivalent to the (GLOP) notation? :

}0.AB.} == }2AB.}

Ypercube

}0.AB.} == }2AB.}

Ypercube

........

Jan 24, 2009, 9:54:15 AM1/24/09

to sprouts...@googlegroups.com

Yper Cube wrote:

> I haven't thoroughly read all your posts about notation. Is this

>

> ^xy:xy.0! is reducible to ^xy:xy2!

>

> equivalent to the (GLOP) notation? :

>

> }0.AB.} == }2AB.}

Yes, that's what it means.

Dan

Jan 24, 2009, 12:36:10 PM1/24/09

to sprouts...@googlegroups.com

I can't remember if I had found this equivalence or if someone else (Jeff, Josh?) had told me about it, but it was surely known long ago. It's good that we now have a formal proof.

But the proofs for bigger equivalences (with more liberties) may get cumbersome in this notation. Reading this proof gives me haedaches to be honest :)

ypercube

But the proofs for bigger equivalences (with more liberties) may get cumbersome in this notation. Reading this proof gives me haedaches to be honest :)

ypercube

Jan 24, 2009, 12:53:19 PM1/24/09

to sprouts...@googlegroups.com

Yper Cube wrote:

> I can't remember if I had found this equivalence or if someone else (Jeff,

> Josh?) had told me about it, but it was surely known long ago. It's good

> that we now have a formal proof.

> I can't remember if I had found this equivalence or if someone else (Jeff,

> Josh?) had told me about it, but it was surely known long ago. It's good

> that we now have a formal proof.

I'm surprised. We all knew that }0.A.} == }2.A.} . Did you know that

}2.A.} == }0.1aAa.} == }1.2A.} != }12A.} ?

> But the proofs for bigger equivalences (with more liberties) may get

> cumbersome in this notation. Reading this proof gives me haedaches to be

> honest :)

I agree it's long and tedious, but I want to make sure it's correct.

In the end, I'm more interested in having a program do the proof.

Dan

Jan 24, 2009, 6:24:09 PM1/24/09

to sprouts...@googlegroups.com

I wrote:

> I'm surprised. We all knew that }0.A.} == }2.A.} . Did you know that

> }2.A.} == }0.1aAa.} == }1.2A.} != }12A.} ?

> I'm surprised. We all knew that }0.A.} == }2.A.} . Did you know that

> }2.A.} == }0.1aAa.} == }1.2A.} != }12A.} ?

Sorry, I mistranscribed that. I meant to say

}2.A.} == }1aAa.} = }1.2A.} != }12A.}

Dan

Jan 25, 2009, 11:07:49 AM1/25/09

to sprouts...@googlegroups.com

at 9-Dec-08, Julien Lemoine said:

I've already tried this, and I wasn't able to find other equivalences

than those you put on this page. They may exist, but they must be quite

rare. Your work seems very complete !

at 10-Dec-08, ypercube replied:

I fear I've only scratched the surface of equivalences. I'm pretty sure many more can be found.

Even more, some of them, like the (somehow escaped from being posted last time)

}0.AB.} = }2AB.} can have great impact on fast computing as it lowers the number of lives by 2 (gain-2). Is the partial position }0.AB.} rare?

I fear that we can find more like this, with even higher gains. (how about a gain-18 equivalence ?)

at 12-Dec-08, Julien replied (in private mail):

I knew this equivalence, but I have again reasons to think that

it's probably impossible to find other equivalences of this kind

(except those you already posted). But I would be pleased if you were

able to show me that I'm wrong.

The equivalences that Julien mentions are the ones posted last March at the wgosa site, at this address: http://www.geocities.com/chessdp/Equivalences.htm

The }0.AB.} = }2AB.} somehow escaped from being posted at that time. The }2.A.} == }1aAa.}is not there either (somehow this escaped from being posted too), here's what realtive to }0.A.} :

> }2.A.} == }2.2.2.A.} == }2.2.2.2.2.A.}} == ... == }2.2.2....2.A.} (odd number of 2. s)

> == }0.A.} == }22.2A.} == }1.2A.} == }2A.BC.}2BC.} == }2AB.}22B.}

> (the above is from Sprouts theory group discussions, just converted to GLOP notation)

There are also a lot of equivalences of type 3 (meaning: partial positions) that have 2, 3 or more parameters, like:

}A.B.C.D.} == }AB.CD.} == }AC.BD.} == }AD.BC.} and

}2.2.2.AB.} == }2.2.2.2.2.AB.} == ... == }2.2.2....2.AB.} (odd, three or more, number of 2. s)

Writing a program to prove them or even better, writing a program that will discover more of them would be a great progress!

ypercube

Jan 25, 2009, 11:18:58 AM1/25/09

to sprouts...@googlegroups.com

Jan 25, 2009, 12:16:29 PM1/25/09

to sprouts...@googlegroups.com

At 10-Dec-08, ypercube replied:

> I fear I've only scratched the surface of equivalences. I'm pretty

> sure many more can be found.

> Even more, some of them, like the (somehow escaped from being posted

> last time)

> }0.AB.} = }2AB.} can have great impact on fast computing as it lowers

> the number of lives by 2 (gain-2).

> I fear I've only scratched the surface of equivalences. I'm pretty

> sure many more can be found.

> Even more, some of them, like the (somehow escaped from being posted

> last time)

> }0.AB.} = }2AB.} can have great impact on fast computing as it lowers

> the number of lives by 2 (gain-2).

I had looked at your Equivalences notes, and I'm very impressed,

but I'm afraid I haven't gotten them down well enough that I recognize

them all the time. So please excuse me if I fail to notice that you've

sent them out first.

One thing I don't recall seeing is the case where two partial positions

differ by *[1]. The new misere Glop uses the fact that *[1]+*[1]=*[0]

to gain two ply, so these may be useful in situations where there is

another odd component:

}1A.} = *[1] + }2A.}

}AB.}BC.}1C.} = *[1] + }ABC.}BC.}

The first is pretty obvious, but I don't know if the second has been

noticed before.

Dan

Jan 25, 2009, 2:57:22 PM1/25/09

to sprouts...@googlegroups.com

On Sun, Jan 25, 2009 at 7:16 PM, Dan Hoey <hao...@aol.com> wrote:

One thing I don't recall seeing is the case where two partial positions

differ by *[1]. The new misere Glop uses the fact that *[1]+*[1]=*[0]

to gain two ply, so these may be useful in situations where there is

another odd component:

}1A.} = *[1] + }2A.}

}AB.}BC.}1C.} = *[1] + }ABC.}BC.}

Both of these equivalences are just amazing! I think we need a name for this (new to me) type.

ypercube

Jan 25, 2009, 4:18:20 PM1/25/09

to sprouts...@googlegroups.com

With regard to

}1A.} = *[1] + }2A.}

}AB.}BC.}1C.} = *[1] + }ABC.}BC.}

}1A.} = *[1] + }2A.}

}AB.}BC.}1C.} = *[1] + }ABC.}BC.}

Yper Cube wrote:

> Both of these equivalences are just amazing! I think we need a name for

> this (new to me) type.

I don't think they are really different in kind. For instance,

we could write them as

}1A.} = }2A.}1.}

}AB.}BC.}1C.} = }ABC.}BC.}1.}

Dan

Jan 26, 2009, 5:26:49 AM1/26/09

to sprouts...@googlegroups.com

You are right, off course. Do you have any more of these? Or any with *2 ?

If not, i'm offering 2 euros for the first to find partial positions P1 and P2 such as :

P1 = P2 + x , where x = *2

and 3 euros for any other x, different from *0, *1 and *2.

Dan

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu