[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: life and death
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.
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.
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.
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.
I was surprised at how much knowledge it took to get even half of volume
two correct. These
are very easy problems. Looking at your examples it seemed that you were
focusing on
move generation, without very much static partial eye evaluation. At least
in the example
that your program got wrong (fig 4.5), there is one clear 1/2 eye on the
edge, one clear full eye near
the edge, and one clear false eye in the middle, and one clear no-eye near
the center. Very
straightforward analysis of the diagonals gives these eye values. So the
move to make the 1/2 eye false
stands out as the obvious first candidate, and after it is made, the group
is statically dead. Many Faces
examines the correct move first, and then statically evaluates the group as
very likely to be dead. It continues
to read around the no-eye near the center for a few ply to make sure there
is no tactic to make a second eye there.
David
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
> >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
David Fotland