Re: computer-go: life and death

[julianr@xxxxxxxxxxxx]

David, Tim,

Can I point you to the following paper:

"Applying Adversarial Planning Techniques to Go", Willmott, S.,
Richardson, J. D. C., Bundy, A., Levine, J. M., Journal of Theoretical
Computer Science, 252 (1-2) (2001) pp. 45-82.

You can get a copy from:

http://www.dai.ed.ac.uk/~julianr/adv_planning_go.ps.gz

It is an extension of a CG98 paper, which was based on Steve Willmott's
MSc thesis.
                  
I have not yet read Tim Klinger's PhD thesis in depth, but I believe
that the approaches of the two pieces of work are similar. Tim has a
larger knowledge base and a more formal approach.

As Tim says, it's surprising how far a little knowledge goes - our
knowledge base was quite small. Our results were improved somewhat by
the introduction of "critics" into the planning process. We used two
critics which could intervene in the planning process when vulnerable
groups appears, and opportunistically direct the planner to kill or save
those groups.

Our program (which was written in LISP) was tested on 85 problems from
Kano volume 1 and 11 from Kano volume 2 (time was short), achieving a
74% success rate for volume 1 and 54% for volume 2 (if I remember the
figures right - they're in the paper).

Julian
                      Tim Klinger writes:
> Hi David,
>
> Actually what I (literally) said was "Such an analysis is beyond current
> go-playing programs and is the focus of our research."  This doesn't mean
> that current programs can't get some of these problems right.  What it
> means is that they lack the ability to construct an analysis of situations
> like these in general.
>
> When you say that every strong program could get 90%+ on Kano volume 2, do
> you mean that they could completely solve 90% of those problems by
> hypothesizing moves for each player at each ply until the problem was
> statically solvable?  I doubt it, but I didn't try.
>
> I don't know whether knowledge acquisition is required for a strong life
> and death problem solver but I suspect that programs could do quite well
> with a decent human-supplied knowledge-base.  I was suprised at how far a
> little knowledge went in our experiments.
>
> Cheers,
> Tim
>
> David Fotland wrote:
>                              
>
> > In your introduction, in figure 1.1, you give two examples of positions
> > that you claim no current computer
> > go program can correctly evaluate.  This is not correct.  Did you
> actually
> > give this position to
> > any strong go programs and ask for their evaluation?  Many Faces' static
> > evaluation understands
> > both examples.  The group at a14 is particularly easy since the adjacent
> > white group you mention
> > has only 3 liberties, so the string tactics can read that the white
> group
> > is captured.
> >
> > I think every current strong go program will correctly statically
> evaluate
> > both of these fights.
> >
> > And I also think that every strong program can get the correct answer to
> > 90% or more of the
> > problems in Graded go problems volume 2.  These are still very easy
> problems.
> >                   
> > Still, your knowledge based approach is interesting, especially if can
> lead
> > to programs that
> > can expand their own knowledge without human intervention.  Without some
> > kind of automatic
> > knowledge acquisition, it seems that every new problem will need some
> new
> > knowledge, and the
> > program can never get very strong at life and death.
> >
> > David
> >
> > At 07:48 PM 5/27/2001 -0400, you wrote:
> >
> > >Some of you might be interested in my thesis titled "Adversarial
> > >Reasoning: A Logical Approach for Computer Go".  It's available for
> > >download from my homepage:  http://cs.nyu.edu/phd_students/klinger
> (under
> > >Research Interests).
> > >
> > >It's mostly about work that I did with David Mechner on a
> knowledge-based             
> >
> > >Some of you might be interested in my thesis titled "Adversarial
> > >Reasoning: A Logical Approach for Computer Go".  It's available for
> > >download from my homepage:  http://cs.nyu.edu/phd_students/klinger
> (under
> > >Research Interests).
> > >
> > >It's mostly about work that I did with David Mechner on a
> knowledge-based
> > >life and death problem solver. It uses a logical theory of life and
> > >death (expressed in a modal logic) coupled with pattern knowledge about
> > >"reasonable" moves to solve uncircumscribed, beginner life and death
> > >problems (from Kano I and II).  There's also some discussion of the
> logic
> > >itself and a formalization of some basic go concepts and rules.
> > >
> > >Tim Klinger
> >
> > David Fotland
>
>
>