Re: computer-go: Live or Die

["Gary Boos" <gboos@xxxxxxx>]

What is you program ?
        Gary
-------
-------
-----Original Message-----
From: Tim Klinger <klinger@xxxxxxxxxxxxxxxxx>
To: computer-go@xxxxxxxxxxxxxxxxx <computer-go@xxxxxxxxxxxxxxxxx>
Date: Friday, November 26, 1999 4:42 PM
Subject: Re: computer-go: Live or Die


>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
>
>