Dan Hoey's ideas on Sprouts position representation
Josh Purinton
lap...@tuxfamily.org
here are some Glopnews. I recently spent holidays in Corsica. There's a problem with Corsica : between 12h00 and 16h00, you can't do anything because it's too hot. So I brought my computer, and I programmed compact surfaces.
The result is a program that you can find on the website ( http://sprouts.tuxfamily.org/wiki/doku.php?id=compact_surfaces : for the moment, there are only sources, but you can compile them if you want to try the new GLOP), and an article on arxiv : http://arxiv.org/abs/0812.0081
About Dan Hoey's idea with parentheses : we explain on page 8 of this article that we forgot this idea, because it can't be used on compact surfaces - but if we limited the program to the plane, it would of course be a great idea.
Julien Lemoine.
danny purvis
From: Josh Purinton <josh.p...@gmail.com>
To: sprouts...@googlegroups.com
Sent: Friday, December 5, 2008 5:05:01 PM
Subject: Dan Hoey's ideas on Sprouts position representation
Josh Purinton
Jeff Peltier
This is a fantastic work you achieved!
I skipped through the article, thanks for citing Ypercube and me, (I did so little).
Ypercube intented to work on your program for the Spring "Compact surfaces Sprouts tournament", he'll be green... Will you participate as centaurs?
I'll compile and play with it soon, after how many initial Spots the -9/+9 limitation will be impacting?
I will tell what I think in a few days...
Thanks also for telling my 0-1 conjecture about Grundy values of initial positions is true on all surfaces for what you tested...
--
Jeff
--
Jean-François
Yper Cube
Thank you both for the wonderful program! As Jeff mentioned I had plans to work on extending GLOP to play at compact surface, but you got me (yes, Jeff, i'm a bit greenish now :). So, I guess, I'll have to start working on GLOP playing misere now and making other improvements. (see below)
I have to say that it was a real surprise to me that playing on surfaces with holes gives same results as playing in the plane, in usual start positions like 0*x.}]! . I would bet that we could find a position with different result. I'm still pretty sure we can find one, in misere if not in normal Sprouts !
Last year, when Jeff and I found the possible moves in compact surfaces, we had no idea that you had already had done work on this (thnx for citing us). The draft we have made with Jeff was left unfinished when you told us about your work. However, I can send it to whom may be interested. We have made some progress on notation that needs to be agreed if we are ever to play Sprouts on compact surfaces by mail.
We adopted three signs, $ % and ? to elaborate the 3 new types of loop moves.
So, in the position with 2 spots in a torus: 0.0.{1}]!
the move that loops one spot to itself (and kills the hole) producing the
position: 0.zy.zy.}]!
would be described as: 1$3$1
differentiated form the normal loop move 1(3)1 which would produce the
0.AB.{1}.AB.}]
The move 1(3)1[h] or the move 1(3)1[2] would produce the
0.AB.}AB.{1}]!
But this needs farther refinement, especially in the case of % and ? moves that appear in non-orientable surfaces.
Things that can be farther improved at GLOP are:
1) Notation
Parenthesis cannot be used in boundaries like .abcabc. or .abab. that appear in non-orientable surfaces as you correctly pointed out. But I have some thoughts on improving (and compacting) notation. I have to say I really like the use of 0*5 instaed of 0.0.0.0.0. (I's have used something like (.0.)^5 but ^ is merely a matter of style instead of *.
You can use the * for more patterns like this, e.g. use :
0*6.1a1a*5.} instead of
0.0.0.0.0.0.1a1a.1a1a.1a1a.1a1a.1a1a.}
or something like: {(.0.)^6(.1a1a.)^5}
This can be expanded for more boundaries (and even regions).
Examples:. instead of
0.0.0.AB.CD.EF.GH.}AB.}CD.}EF.}GH.}]
use
{(.0.)^3(.AB.{.AB.})^4}
2) Applying equivalences
In my published at the wgosa site "Equivalences" report, I have a collection of equivalences, where only some of them are used by GLOP. We can
a) add all of them (hard coded in the program) or
b) add a database of equivalences and change the program so it uses this small db. This will probably need
c) some more translation code so when a new line is added at this db, older result files are compressed taking note of the new line (equivalence)
(side note: in the published post, one of the equivalences was .1. = .22.
At that time, I did not include the .1. = .abab. equivalence, as the .abab. does not appear but only after playing in Projective plane :)
3) Saving databases
It would be great if GLOP saved the results database in a real database, like mysql.
Off course, using only a database and not a structure in memory would probably make calculations slower. I imply that besides using the structure in memory, all results be sent to the mysql database. This would result in :
- No need to save the main database in the end.
- When starting the program, one would be able to load the mysql database or part of it, for example load only positions with fewer than 24 liberties, if one plans to work on solving the 0.*8} position.
- The program can still ask from the mysql database if a position is there (while still move to calculate if not)
- Many PC's in a local network can cooperate and send their results in one which will have the mysql database.
- Having the position stored in a mysql database, can help asking queries faster,
e.g. how many positions do we know with liberties>=20 and nimber=8 or
find all positions of xLy type 0*x.AB.}0*y.AB.}] and their nimbers
4) Playing misere
5) More improvements by speeding up children calculations and position evaluation (some thoughts on this which need testing, I'll explain in a private mail, no need to clatter the sprouts theory group with this).
ypercube, turning green
P.S. Did I thank you for the great program ?
P.P.S In a mail to Jeff, Danny and Josh, about a year ago, I wrote:
>I'm preparing some articles on Sprouts stuff. One of them will be about equivalencies, hopefully
> with complete proofs of all these. Also:
>
> 1) "Alice finds Flowers in the Sprouts Garden"
> 2) "Element-ary theory" or "Periodic Table of Sprouts Elements"
> 3) "Alice plays Sprouts inside and through mirrors"
> 4) "Alice in the Doughnut land"
> 5) "Even more bizarre flowers, cactii and wild animals in the Sprouts Jungle"
>
> I hope that one or two will be ready before Christmas.
I didn't say which Christmas, though!
Feeling awfully late and pushed by Jeff, I've again taken my pencil and have almost ready the
2) "Element-ary theory" or "Periodic Table of Sprouts Elements"
(subtitle: "some light into the mystery of why rule n=n+6 works" )
which will now include a section on
"sub-atomic particles with zero mass and 1/2 spin"
Josh Purinton
From: Dan Hoey
Subject: Sprouts notation and ideas
To: Josh Purinton
I thought I should pass along some ideas I've had about notation that are relevant to our earlier discussion. I wrote the first publicly, on the Glop forum at http://sprouts.tuxfamily.org/wiki/doku.php?id=forum , and expanded in a message to Julien Lemoine. Recall that their notation uses lower-case letters for pier points, "}" for end-of-region, and "]" for end-of-land. I wrote:
> I have some suggestions for improvements. First on the agenda is to
> replace the lower-case letters with parentheses, so "abcdAdceBebaC"
> would be "((((A))(B)))C", relying on the fact that pier points nest.
> discuss them later. Il warn you, I like to see "}" and "]"
> replaced with something else, so more nesting notation is possible,
> though I may be able to get by on <>.
: Okay, suppose we consider a region (or as you call it, domain) like
: "0.1AB(2)C.}", where the matching A, B, and C appear together in one
: other region. A region like this could appear many times in a
: position, with different capital letters in the place of A and B. So
: let's write it with formal variables "a", "b", "c" as
: "#ab:0.1ab(2)c.}/", where I will use "/" as an end-of-partial-position
: character as well as an end-of-land character instead of "]". I want
: to use "[" "]" as the other nesting characters--I'd use < > except
: that they tend to get treated as HTML in e-mail. As long as we use
: different formal variables for each partial position, an appearance of
: "a" or "b" elsewhere in the position will refer to this sort of
: partial position.
: In order to show which "a" matches with each "b", we note that (1) The
: matching "a", "b", "c" will appear not only in the same region, but on
: the same boundary, and (2) The matching pairs nest, along with the
: parentheses for degree-two points on the boundary. So we place a left
: bracket before the first of a set of abc and a right bracket after the
: last, and we can have a boundary like "[a(2)b1[ba2c][d(2)e][f]c]1."
: where the parser can tell that the first a,b go with the last c, the
: b,a,c in "ba2c" go together, and there are references to two other
: partial positions with formal parameters "de", and "f", respectively.
: Internally, I expect each matching "[a", "b", and "c]" to be
: represented as a single character that indexes into a per-boundary
: table that specifies (1) a reference to the partial position with
: parameters a,b,c, and (2) the order of appearance, a,b,c. In "[ba2c]"
: the "[b", "a", and "c]" would use a different table index referring to
: the same partial position but a different order of arguments.
: It just occurred to me that we could use "(a", "b", and "c)" just as
: well, though it might get someone confused with the other use of
: parentheses.
: What this buys us is a convenient way to specify multiple references
: to the same partial position type, which ties in with doing a better
: job at finding the isomorphism type of a position. Construct the
: "region graph" of the position, which has one vertex for each region
: and an edge joining regions that share a "pivot" point. It's pretty
: easy to find the two-connected components of this graph (i.e. the
: maximal subgraphs that cannot be disconnected by removing a single
: edge). Using a half-hearted canonization of the
: two-connected-components, the connections between them (induced by
: edges in the region graph) form a tree, which can be canonized quickly
: with a leaf-up approach.
I also noticed something related to the question we discussed on whether the chirality of separate boundaries is significant:
: "stuff1".abc.}"stuff2".abc.}otherstuff" is identical to
: "stuff1".abc.}"stuff2".bca.}otherstuff"; that is that chirality does
: not propagate through a simple three-point boundary. In fact, I
: believe you need at least five lives on the boundary (of which at
: least three must be pivots, and the other two can be pivots or inside
: or outside) for chirality to propagate.
I don't consider these ideas in any way confidential, though I'd like to be mentioned as the originator if you end up using them (modulo someone already having had the idea).
Dan
lap...@tuxfamily.org
"Jeff Peltier" <jfpe...@gmail.com> a écrit :
> Ypercube intented to work on your program for the Spring "Compact
> surfaces Sprouts tournament", he'll be green... Will you participate
> as centaurs?
Probably not : we're not really interested in playing tournaments.
> I'll compile and play with it soon, after how many initial Spots the
> -9/+9 limitation will be impacting?
I don't think I completely understand the question ? The limitation is
on the genus of the surface (you can't play on a torus^10 for example),
not on the number of initial spots.
> I managed to compile and import an old database smoothly!
Yes, you can import and them use them to compute without any problem.
The only limitation is that the "check" computation may fail (which
doesn't mean that the computation is wrong).
We're happy that you are interested in our work ! There is still a lot
to do. For example, it's hard to find a conjecture about what happens
on non-orientable surfaces.
PS for yper : I will answer your email tomorrow, I'm don't have much time this evening.
--
Julien Lemoine
lap...@tuxfamily.org
"Josh Purinton" <josh.p...@gmail.com> a écrit :
> Note: I have made the archives of this group (sprouts-theory)
> publically-readable. I hope that's OK with everybody.
It's a nice decision. I have begun to read the archives, and I found
this message :
Reversing a single boundary within a region
"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).
(PS : I previously sent this message to the group with a wrong email. I hope you won't receive it 2 times).
--
Julien Lemoine
lap...@tuxfamily.org
tell you how Glop will be improved in the next months.
> Things that can be farther improved at GLOP are:
> 1) Notation
> Parenthesis cannot be used in boundaries like .abcabc. or .abab.
> that appear in non-orientable surfaces as you correctly pointed out.
and such boundaries can also appear with orientable surfaces (except
the plane).
> But I have some thoughts on improving (and compacting) notation. I
> have to say I really like the use of *0*5* instaed of *0.0.0.0.0.*
> (I's have used something like (.0.)^5 but ^ is merely a matter of
> style instead of *. You can use the * for more patterns like this,
> e.g. use : 0*6.1a1a*5.} instead of
> 0.0.0.0.0.0.1a1a.1a1a.1a1a.1a1a.1a1a.}
>
> or something like: {(.0.)^6(.1a1a.)^5}
>
> This can be expanded for more boundaries (and even regions).
> Examples:. instead of
> 0.0.0.AB.CD.EF.GH.}AB.}CD.}EF.}GH.}]
> use
> {(.0.)^3(.AB.{.AB.})^4}
We had similar thoughts, and we already implemented the compacting of
zeros in the development version of GLOP. We almost use the same
notation : 0*5 instead of 0.0.0.0.0.
But we hadn't thought to do this for other kind of boundaries. It's not
a high-priority task, because the zeros are the main cause for long
lines.
> 2) Applying equivalences
> In my published at the wgosa site "Equivalences" report, I have a
> collection of equivalences, where only some of them are used by GLOP.
> We can
>
> a) add all of them (hard coded in the program) or
> b) add a database of equivalences and change the program so it uses
> this small db. This will probably need
> c) some more translation code so when a new line is added at this db,
> older result files are compressed taking note of the new line
> (equivalence)
>
> (side note: in the published post, one of the equivalences was .1.
> = .22. At that time, I did not include the .1. = .abab. equivalence,
> as the .abab. does not appear but only after playing in Projective
> plane :)
Glop-dev is able to compute the "canonical game tree" (see section 5 of
our article) of a given position (but only for little positions,
because you need to compute the whole game tree).
It is useful to find new equivalences : for example, you compute the
whole game tree of the 5-spot game. When you see two positions with the
same canonical game tree, then you see an equivalence.
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 !
It isn't a high-priority task neither, because we believe that only a
limited fraction of the positions we meet during a computation would be
simplified.
> 3) Saving databases / mysql
This is an interesting idea. The point I prefer is the following :
> - Many PC's in a local network can cooperate and send their results
> in one which will have the mysql database.
Simon and I already evoked the idea of distributed computing. It's
likely that sooner or later, we'll program something in this way.
> - Having the position stored in a mysql database, can help asking
> queries faster,
> e.g. how many positions do we know with liberties>=20 and nimber=8 or
> find all positions of xLy type 0*x.AB.}0*y.AB.}] and their nimbers
The next release of Glop will have a tab in which you'll be able to
perform such operations on databases.
> 4) Playing misere
For the moment, nothing powerful is programmed. But, in at most 6
months, a first draft may come.
> Feeling awfully late and pushed by Jeff, I've again taken my pencil
> and have almost ready the
> 2) "Element-ary theory" or "Periodic Table of Sprouts Elements"
> (subtitle: "some light into the mystery of why rule n=n+6 works" )
> which will now include a section on
> "sub-atomic particles with zero mass and 1/2 spin"
Nice teaser ! It's already on the wishlist that we'll send to santa claus.
--
Julien Lemoine
Yper Cube
Long lines are cumbersome but long computations are even more. I think children evaluation can be fastened with with compact notation. And surely the size of the result files.
One more reson to adopt this notation for all boundaries is that sometimes GLOP runs out of letters. Example:
Lets say I want to compute the value of:
0.0.0.AB.CD.EF....WX.YZ.}AB.}CD.}....WX.}YZ.}]!
As soon as GLOP tries to make a loop from a 0. spot, it will run out of letters.
or of the position:
0.0.1abcd.....xyz1zyx...cba.}]!
similar problems when it connects the 0. to 1 or one 1 to another 1.
These positions may seem constructed and unnatural but they appear in my theoretic explorations.
If you think it's not a high-priority task for you to adopt such notation, i'll try to do it. We can this way not work on same aspects of the program and lose time doing double work.
Glop-dev is able to compute the "canonical game tree" (see section 5 of
> 2) Applying equivalences
> In my published at the wgosa site "Equivalences" report, I have a
> collection of equivalences, where only some of them are used by GLOP.
> We can
>
> a) add all of them (hard coded in the program) or
> b) add a database of equivalences and change the program so it uses
> this small db. This will probably need
> c) some more translation code so when a new line is added at this db,
> older result files are compressed taking note of the new line
> (equivalence)
>
> (side note: in the published post, one of the equivalences was .1.
> = .22. At that time, I did not include the .1. = .abab. equivalence,
> as the .abab. does not appear but only after playing in Projective
> plane :)
our article) of a given position (but only for little positions,
because you need to compute the whole game tree).
It is useful to find new equivalences : for example, you compute the
whole game tree of the 5-spot game. When you see two positions with the
same canonical game tree, then you see an equivalence.
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 !
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 ?)
It isn't a high-priority task neither, because we believe that only a
limited fraction of the positions we meet during a computation would be
simplified.
I think you are overly wrong here. Positions like
0.0.0.0.1.1.1.1.22.22.22.}]! are not common but they do appear too in theoretical searches. One can make the experimen to solve the above position and then the
0.0.0.0.1.1.1.1.1.1.1.}]! . It will probably take some long time. The two positions are equivalent though both in misere and normal games and in all surfaces., e.g.
0.0.0.0.1.1.1.1.22.22.22.{-7}]! is the same as
The .abab. = .1. = .22. equivalence I had skipped in the published equivalences will be quite common too, arising in games from non-orientable surfaces with one loop move (of the special kind) from starting positions 0.0......0.{-n}]!
> 3) Saving databases / mysql
This is an interesting idea. The point I prefer is the following :
Simon and I already evoked the idea of distributed computing. It's
> - Many PC's in a local network can cooperate and send their results
> in one which will have the mysql database.
likely that sooner or later, we'll program something in this way.
The next release of Glop will have a tab in which you'll be able to
> - Having the position stored in a mysql database, can help asking
> queries faster,
> e.g. how many positions do we know with liberties>=20 and nimber=8 or
> find all positions of xLy type 0*x.AB.}0*y.AB.}] and their nimbers
perform such operations on databases.
Great!
> 4) Playing misere
For the moment, nothing powerful is programmed. But, in at most 6
months, a first draft may come.
Great! Please let me know how I can help there.
Nice teaser ! It's already on the wishlist that we'll send to santa claus.
> Feeling awfully late and pushed by Jeff, I've again taken my pencil
> and have almost ready the
> 2) "Element-ary theory" or "Periodic Table of Sprouts Elements"
> (subtitle: "some light into the mystery of why rule n=n+6 works" )
> which will now include a section on
> "sub-atomic particles with zero mass and 1/2 spin"
:)
--
Julien Lemoine
P.S. early christmas gift
Santa visited me this afternoon and after a long talk, we came to the conclusion that the
.abab. = .1. = .22. equivalence
is in fact a lemma on a more general one. I won't wait until Christmas to announce that one more equivalence of the more general type (Type 1 - Branch Equivalencies) has been found!
(quite unexpectedly I must say, I thought we couldn't find more of this type)
Besides the already known and widely used
-aa- = -2-
we can now use the
-abab- = -a2a-
Examples of use:
0.0.121abab.}]! = 0.0.121a2a.}]!
0.1abab1cdcd1A.}ababA.}]! = 0.1a2a1b2b1A.}2A.}
and the lemma:
.abab. = .a2a.
= .2aa. (due to rotation)
= .22. (due to the first type 1 equiv.)
= .1. (already known equivalence of type 2)
enjoy :)
ypercube
Yper Cube
A correction on the previous post and an addition.
P.S. early christmas gift
Santa visited me this afternoon and after a long talk, we came to the conclusion that the
.abab. = .1. = .22. equivalence
is in fact a lemma on a more general one. I won't wait until Christmas to announce that one more equivalence of the more general type (Type 1 - Branch Equivalencies) has been found!
(quite unexpectedly I must say, I thought we couldn't find more of this type)
Besides the already known and widely used
-aa- = -2-
we can now use the
-abab- = -a2a-
Examples of use:
0.0.121abab.}]! = 0.0.121a2a.}]!
0.1abab1cdcd1A.}ababA.}]! = 0.1a2a1b2b1A.}2A.}
Correction. The above should be:
0.1abab1cdcd1A.}ababA.}]! = 0.1a2a1b2b1A.}a2aA.}]!
I should add that .abab. ( = .22. = .1. ) are quite common in non-orientable surfaces games that start with n spots.
Last minute addition to the set of equivalences:
(type-2) boundary equivalence
.abcabc. = .abacbc. = .abcacb.
ypercube