Re: computer-go: Live or Die

[Tim Klinger <klinger@xxxxxxxxxx>]

At 11:10 AM 11/26/99 +0000, you wrote:
>
>> Many Faces does a very selective best-first search.  The current
>> version also has some major bugs in the static eye evaluation since
>> I'm part way through a major change.  Many Faces does not stop at
>> the first move that works.  It tries to find all moves that work,
>
>Can I ask the other people on this list who are working on L&D whether
>they also take an approach based on eyes ?
>
>I imagine the reason why ManyFaces does this is because its positions
>are open.. even then, it is probably possible to get by without a notion
>of eyes. My current brute force algorithm works on the concept of
>capture only (eyes are a heuristic for humans beings..)
>
>Anyone ?
>Christian
>(Btw. I imagine I would get about the same timings as the original
>poster of this message on his problems.. however, there is no depth
>limit, my algorithm runs until it "enough" has been captured to produce
>a loss for black (the defender))


We have a life and death problem solver that works in open positions to
determine the life and death of an object block.  It has eye patterns to
recognize shapes that have the potential to become eyes.  The patterns are
matched to determine where the object block's eyes are and to find for each
eye the border and center points of the eye.  Border points are the points
that may be filled in if the eye is attacked/defended.  Center points are
the points surrounded by (but not including) the border points.  For each
eye pattern we also have a set of patterns giving the reasonable moves for
attacking and defending it.  The pattern resulting from playing the
attacking or defending move is itself potentially an eye pattern.

We apply the following algorithm to estimate the minimum and maximum (up to
2) eyes for a block. 

Defn 1: A block b has an *eye* if an eye pattern matches for b.

Defn 2:  An eye is *unassailable* if there are no attacking moves suggested
against it.  Otherwise it's assailable.

Defn 3: Two eyes e1 and e2 are *disjoint* iff
1. border(e1) intersect center(e2) = emptyset
AND
2. center(e1) intersect border(e2) = emptyset

Note that our definition of unassailability means that *if* a block has an
eye which is unassailable then it really can't be collapsed.  We are not
assuming the converse, i.e. it is possible that an eye is considered
assailable but in fact is fine.  In this case further reading is required
to determine the outcome.


EstimateNumEyes(b, min, max)
// Conservatively estimate the minimum and maximum number of eyes for the
object block.
// If min = 2 then the block is really alive.  If max < 2 then the block is
really dead.
// In all other cases more reading is required to determine the outcome.

// There are six possibilities with min <= max:

If (b has two disjoint unassailable eyes)
   min = max = 2;
   return;

If b has two disjoint eyes exactly one of which is assailable
   min = 1;
   max = 2;
   return;

If b has two disjoint eyes both of which are assailable
   min = 0;
   max = 2;
   return;

If b has a (single) eye which is unassailable
   min = max = 1;
   return;

If b has a (single) eye which is assailable
   min = 0;
   max = 1;
   return;

// b has no eyes
min = max = 0;



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.

Tim