Re: computer-go: Search heuristics

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

Many Faces uses a similar heuristic.  For each cantidate
liberty, I count the number of adjacent empty points to that
liberty (Daniel's 2nd order liberties), then make a small
correction for nearby enemy stones and playing on a libety farther
from the edge, which captures some sense of the 3rd order liberties.

Since the enemies key point is often your own, when one of
your moves is refuted I change the order and try the move that
the enemy used to refute it next.

David

At 08:41 AM 11/22/99 -0800, Daniel Bump wrote:
>
>Consider the problem of determining whether a string
>can be capture. Different classes of attacking moves
>must be considered:
>
>(1) filling a liberty;
>(2) defending a boundary string which is under attack;
>(3) certain moves at a distance such as capping moves.
>   
>The search tree can be pruned if the candidate
>moves are considered in an intelligent order. Often
>the best attacking move is also the best defensive move.
>
>Considering only moves of type (1), I want to suggest
>a simple heuristic which often finds the best move.
>
>Define an n-th order liberty to be an empty vertex
>at distance n from the string. Define a word
>(abc) where a is the number of liberties, b the number
>of second order liberties and c the number of third
>order liberties.
>
>The heuristic is that this word gives a good measure
>of the escape potential of the string. The words are
>ordered lexicographically.
>
>Let us consider the following problem:
>
>......
>...X..    The question is how the O string is to
>.XXO..    be attacked. 
>...... 
>......
>------
>
>....3..  
>...X23.   After this attacking move there there
>.XXO123   are 3 second order liberties, 5 third
>...X23.   order ones. The resulting word is
>....3..   (135).
>-------
>
>......
>...X..    This attacking move results in the
>.XXOX.    word (134). This is smaller than
>.32123    (135) in the lexicographical ordering
>..323.    so this attacking move is better.
>------
>
>......    After O extends X has three attacking
>...X..    moves at a, b and c. The associated words:
>.XXOX.   
>..cOa.    a: (233)   The heuristic shows a to be the
>...b..    b: (245)   best attacking move. This is
>------    c: (234)   correct.
>
>The heuristic is not always correct but it is often
>a good guide. GNU Go does not use this exact heuristic
>but does use similar ideas to order the moves at each
>node during reading.
>
>Daniel Bump
>http://www.gnu.org/software/gnugo/devel.html
>
>