RE: computer-go: Live or Die

[Tim Klinger <klinger@xxxxxxxxxx>]

At 07:28 AM 12/6/99 -0500, you wrote:
>> The algorithm is correct under the following two assumptions:
>>
>>1. The set of eye patterns is complete and the attributes for center,
>> border, etc. are correct.
>>2. If there is some attacking or defending move that works, then there is a
>>pattern that suggests one that works.
>
>Thanks for the algorithm, Tim.
>
>Can you tell us the "degree of correctness" of these two assumptions, both
>within your program as it stands today and in the theoretical limit of your
>current approach?

Hi Brian,

In theory the correctness of this appproach is only limited by the quality
and completeness of the knowledge. If your patterns don't indicate a
possible attack on an eye when there is one, your results may be erroneous
(your reasoning certainly will be).  Or, if you make a mistake in the
labeling of the center and border points of an eye you may think there is
one eye when there are in fact two.  On the other hand, if you have a
promiscuous pattern that matches too often (imagine for instance a simple
pattern that suggested filling a liberty as a good way to kill stones), you
increase the work to be done possibly making the problem intractable.

We have about 500 or so eye patterns right now.  In the tests that we've
run most of the errors were due to missing patterns, and only a few were
caused by incorrectly entered patterns.

We've been training and testing our program on Kano's graded go problem
series.  We train on the odd problems, test on the even ones.  After
training on the odd numbered problems in volume 3, it correctly solved(*)
about 85% of problems in volume 1 with no additional training.  With
training on the odd numbered problems in volumes 1 and 2, it is solving the
even numbered problems in volumes 1 and  2 in the > 85% range.  We're still
training and testing on volumes 3 and 4. (**)

So, to get back to your question, I think it probably still needs quite a
few more patterns but we are encouraged by its performance on Kano with the
basic ones it has now.

Tim


(*) "Solved" here means that it generates  a set of moves at each ply which
includes among them an expert-suggested move to correctly solve the
problem, if such a move exists.  We give it the problem, it suggests moves
and solves each of the subproblems resulting from playing those moves,
recursively.  Each ply is checked to make sure that the program is
generating the right result for the right reason.  We call it correct only
if it correctly solves all the subproblems considered to the satisfaction
of a 6-dan player (David Mechner).  We allow it to cut-off at a given ply
if a successful move is found.

(**) We only give it the problems that can be formulated as life or death
problems for a particular block.  eg.  "Black has a move to save his four
stones."