computer-go: Search heuristics

[Daniel Bump <bump@xxxxxxxxxxxxxxxxxx>]

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