Re: computer-go:life and death

[Tim Klinger <klinger@xxxxxxxxxxxxxxxxx>]

David Fotland wrote:

> At 06:44 AM 5/28/2001 -0400, you wrote:
> >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.
>
> But such analysis is exactly what current programs do :)  I'd say that
most
> programs can correctly analyze 95% or more of situations like the two
you cite.
> This is not good enough of course for strong play.  This kind of
life/death
> analysis
> is needed at almost every move in the middle game, so every program gets
some
> of these situations wrong almost every game.  It's easy for me to
> understand that
> when you see one such failure in a game, you might conclude that the
programs
> have little understanding.   But walk though a game with a strong
program
> and ask
> it life and death status, and you will be surprised.
>

I don't think that what current programs do is what I am loosely calling
"analysis."  They may get many problems right but my point is that they
lack the facility to represent and make inferences from the logical
relationships between strategic goals of interest in a way that is
independent of any specific domain knowledge -- something akin to the
"goal graphs" that I discuss in my thesis.  

For example, even in the problems that our program ultimately failed to
solve because of missing or incorrect domain knowledge, the "analysis" or
structure that represented the problem at hand -- the fact that
successfully capturing one block, would allow save another for example --
was still correct. My conclusion that current programs do not do this kind
of analysis comes from the lack of any published literature to the
contrary, my discussions with you and other authors of strong programs, as
well as the general conversation on this list.



> In a thesis, when you make such a strong statement, like the one you
quote
> above,
> I would expect that it was based on some testing.  But the two examples
you
> gave
> are both very easy for programs to understand, so I concluded that you
had
> made this
> statement with no real evidence.

I think our disagreement lies in our interpretation of the word
"understand."  The motivation for the point I made above is that I believe
that some sort of explicit representation of the problem logic is
important for programs to solve harder problems (ones that no program can
solve now) and current programs -- as far as I know -- lack such a
representation.


> >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.
>
> Yes.  Programs read these problems.  And after each ply the problem gets
> easier.  In the
> example you gave in your thesis, certainly today's programs do much
better
> move ordering.

So, every strong program can solve 90% of Kano II using the following
definition of correctness?

A life and death problem is *correctly solved* by a program iff the
program finds a tree of moves representing the program's moves and the
player's counter-moves, recursively, which leads to positions that are
statically solvable.  Such a tree is in effect a "proof" of the
correctness of the result under the assumption that the moves considered
at each ply include one that does indeed work when such a move exists.

I don't know of any such results except (I think) for Wilmott's thesis and
the subsequent paper by Willmott, Richardson, Bundy, and Levine (mentioned
in an earlier post).

Tim