Re: saving state & patterns & GP

[Jeffrey Greenberg <jeffg@xxxxxxxxxx>]

As I am using GP at this time, each pattern is an executable expression
containing constants and functions.  The functions can be divided into a set of
mathematical functions and a set of Go functions.  Now, I've been trying to keep
the amount of information in the Go functions small, but with little success.
So I need to add go-knowledgable functions to the function set.  But I'm looking
for a principled way to add this information, instead of just willy-nilly.  The
first set of functions I'm thinking to add are those neccessary to score a game
once it has been played out completely.  (That is to the point past where a
human would already know that the game has been decided, namely to where all
points have been played out.)  I will see what kind of success I get from this.

Note that it is unlikely to be able to evaluate ladders, or do anything else
requiring a great deal of lookahead/search.  That sort of information, which is
very computer/time expensive would be very costly to evolve with.  And while
there are areas to explore there with search & GP, I'm not ready for that yet.
And there are some interesting models that include both economics and GP that
might work in that case.
I'm also considering using heirarchical planning and GP mix, riffing on
Willmott's MsC. as a framework for adding knowledge e.g. with an hierarchical
goal-planning organization.  But this and the other methods I'm aware of all
suffer for a lack of methodology for adding or creating knowledge for the system
-- in GP and in goal-planning, someone has to add/create the function set or the
atomic goals & methods.  Finding, an effective way to create this knowledge is
what I'm after.

So to answer your question, the information used to score a game when played to
the end seems to be knowledge of: ko, strings or blocks, liberty counts, and the
ability to detect the 'end'.  Detecting the 'end' seems to require: seki-cycles
(which I've not added), knowledge about enclosures/simple eyes.  This knowledge
is there, but I've not yet added it to the function set -- I'm considering other
technology as well (other than GP).

Past this bit of knowledge, it depends on the goal of implementation phase of
ones program; to add the ability to create or detect connections and join or cut
them, you need information about linkages: 1 jump, 2 jump, knight, etc.  You
might want to deal with ladders, joseki, etc.  The question of what to add
suddenly becomes an ocean of sub-questions, an explosion of implementation goals
to go after, and who knows what kind of program organization?  Rather than just
getting something to play, I'm still holding to trying to find ways to
synthesize these steps.

There are further details as well.  If you evolve one pattern per GP expression,
then you have to manage a pool of patterns and find an automatic way of ordering
the expressions or creating dependencies between them, and at the other extreme,
you could go after the mother of all expressions that best captures the playable
points on any given board.  The latter is not tractable with our current
technology, so the former is to be investigated.  Probably along the lines of
smaller expression trees that capture a set of moves, together with either fixed
relations and orderings between trees by using ADFs or by ordering/relation
trees (which I just made up).  This problem is akin to those that
multi-objective GP goes after -- and there are other schemes.

jeffrey

Gary Boos wrote:

> Sharing patterns.  Do you (or is it common to) have related data along
> with the pattern, such as:  eye, wall, false eye, etc. ?
> Determining pattern size seems to be a hurdle too.
>                 Gary
>
> ----------
> > From: Jeffrey Greenberg <jeffg@xxxxxxxxxxxxxxxxx>
> > To: Tim Klinger <klinger@xxxxxxxxxxxxxxxxx>
> > Cc: Computer Go Mailing List <computer-go@xxxxxxxxxxxxxxxxx>
> > Subject: Re:
> > Date: Monday, August 24, 1998 2:57 PM
> >
> > Hmm,
> > This idea of saving state in component-based pattern-speak is known as a
> Memento
> > pattern.  It bothers me that your solutions are all inheritance based.  I
> have
> > objects that are already of a type and this solution will drive me to
> multiple
> > inheritance which has other problems.  A component based solution along
> the
> > Memento line frees me of these constraints.  Comments on this?
> >
> > The alerting described below is known as an 'Observer' and 'Subject'
> behavior in
> > which a set of subjects register with the observer as being 'observable'.
>  On a
> > change the 'Observer' is used to notify the subjects.   (This too is a
> component
> > solution, not an inheritance one.)
> >
> > How about patterns related to Go?  Maybe then, so code other than wally
> might be
> > shared!?!  (At this point, I might actually post some...)
> >
> > To Tim's interesting point that they designed the 'revertable' data
> structures so
> > as not to incur the psychological barrier of not trying algorithms
> because they
> > might take too long, I can add that in my experience the boredom of
> actually
> > getting the incremental computing right was enough to put me off.  8-)
> But in my
> > case, I'm not so concerned with the compute time as my goal is to derive
> or learn
> > knowledge.  As the state-of-the-art for machine learning is rather low,
> I'm not
> > bounding myself to the constraints of a game to be played in 1 hours'
> time.
> >
> > jeffrey
> >
> > Tim Klinger wrote:
> >
> > > >In Indigo, most of objects inherits the Relying_object class
> (Objet_pose
> > > >in french). This class has the slot 'intersections' which is the set
> > > >of intersections on which the objet relies.
> > > >
> > > >The slot 'intersections' of a relying object is a reference to the
> relying
> > > >object that is very useful in Indigo.
> > > >
> > > >For incremental data structure, the Relying_object class has the
> 'track' slot
> > > >that is the set of intersections from which the existence of the
> object
> > > >depends. When a move is played ouside the track of an object, the
> object
> > > >remains and, conversely, when a move is played inside the track then
> the
> > > >object
> > > >is deleted (or saved in a cache).
> > > >
> > > >Bruno
> > >
> > > We have something sort of similar.  Objects can 'depend' on other
> objects
> > > causing them to be alerted when the dependency changes.  They can then
> > > alert any objects that depend on them, recursively.  Using this as the
> > > basic structure we built a truth maintenance system (TMS) which
> monitors
> > > changes in board occupancy, liberties, and other terms of interest.
> Any
> > > object that needs to can request a constraint that it can 'depend' on.
> For
> > > instance, our pattern matcher works incrementally this way.  When a
> pattern
> > > matches, a constraint of the form: color(p1) == c1 and color(p2) == c2
> etc.
> > > is constructed and registered with the TMS.  If later the constraint is
> > > violated the TMS sends an alert to the pattern match letting it know
> that
> > > it is no longer valid.  The match will then send an alert to a database
> to
> > > let it know that any assertions about the state made by the match
> should
> > > now be revoked.
> > >
> > > Tim
> >
> >
> >
> > --
> > Jeffrey Greenberg
> > Mgr. Aegis Adv. Dev.
> > Acuson Corp.
> > www.ultrasound.com
> > www.acuson.com
> > 650-694-5422
> >



--
Jeffrey Greenberg
Mgr. Aegis Adv. Dev.
Acuson Corp.
www.ultrasound.com
www.acuson.com
650-694-5422