A new equivalence
Dan Hoey
^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
Yper Cube
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!
}0.AB.} == }2AB.}
Ypercube
........
Dan Hoey
> 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
Yper Cube
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
Dan Hoey
> 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
Dan Hoey
> 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
Yper Cube
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
Yper Cube
Dan Hoey
> 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
Yper Cube
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
Dan Hoey
}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
Yper Cube
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