Re: computer-go: Searches

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

At 11:50 AM 11/20/99 +0100, you wrote:
>
>I can think of a few different ("local") look-ahead procedures that 
>should exist in most programs:
>  - ladder reader: read as deep as it takes, but not very wide (terminate
>    when the running group has three liberties.

Many Faces reads until the group gets 5 liberties, two eyes, seki, or
is captured for each string/block.  Each is read 3 times to distinguish
unconditional vs kos, and interactions with nearby friendly groups.  
Results are cached to avoid rereading.  Search is deep but not wide.
Up to 80 ply deep.  Beyond the first few ply, only 1 or 2 cantidate
moves are tried, so the move generator is quite complex.  Each seach is
limited to about 120 unforced nodes.  I use alpha-beta depth first search
with a small transposition table per search.

>  - Contact fight reader: Not necessarily very deep, but reading has to be
>    stopped somewhere (enough liberties? stable string (what ever that
>    means), or something else). hard to define clear goals or to evaluate
>    end positions. (if I hane at the end of 2 or 3 stones, is the cutting
>    points how much more serious risk?)

Many Faces doesn't have one.  Contact fights are a weakness.  I rely on
the full board pattern database to suggest move sequences that will
be read out during the global full board search.  I have a few dozen
contact fight patterns.

>  - local life reader: May have to read pretty deep (and/or have good
>    heuristics on when to stop). Difficulties in limiting the read to the
>    local fight. Probably useful to use shape-based move generation and
>    ordering (try the vital-looking point first, then hane)

I use a best first search, expanding the node which has the most likelihood
of changing the value of the root.  When I expand a node, I generate
a complete line of play until the static life evaluator is confident of
the result.  At each node, I do a full board life and death evaluation,
(including all the ladder reading), so it is slow.  Usually doesn't
read very deep, perhaps 10 ply or so.  At deeper nodes I will stop with
less certainty from the static evaluator.  All nodes of every tree are
cached.

>  - Surrounding/running reader. Does not necessarily need to read the
>    exact sequences (running with 1-point jumps and diagonal moves may
>    be sufficient) to decide which way to run, or if at all.

Don't have one.  I depend on the full board pattern database to
suggest move sequences that are read during global lookahead.  I have
a few hundred surround/running patterns.

>
>Any comments from those who have actually written programs?
>
>	- Heikki

David Fotland