computer-go: Searches

[Heikki Levanto <heikki@xxxxxx>]

> Not at all.  A ply of lookahead can't see the simplest tactics that a
> beginer can see, like an atari on the second line.  The capture is
> 4 ply deep.  A capture with atari on the third line is seen by someone
> only slightly better, and is over 10 ply deep.  Searches must be local 
> deep, not full width brute force.


I think you have a good point there, and I would like to take the discussion
further in that direction. So far we have been discussing global full-width
searches, and local deep searches. Could we get a bit more nyanced picture
of the various searches required?

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.
  - 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?)
  - 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)
  - 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.
 
Most of these local readers have to consider the possibility that the
opponent will not answer, and will play elsewhere. They may be able to
produce longer sequences that the global reader may consider as single
moves.

Also, since these readings are local, it may be possible to cache their
results, and reuse them later. When the situation changes, the affected
sequences will have to be removed from the cache, which may be more trouble
than it is worth.


Any comments from those who have actually written programs?

	- Heikki

-- 
Heikki Levanto     LSD Levanto Software Development   heikki@xxxxxxxxxxxxxxxxx
               "In Murphy we Turst"