[gnugo-devel] the owl looks for escape

[Arend Bayer]

 *                             (|__|)
 *                            (@)(@))
 *                            |:v:: |
 *                           (       )
 *                            \|   |/
 *                            =#===#=
 *                            /___/
 *
 *                The owl is noted for its keen vision
 *                       and (purported) wisdom.

(In owl.c).
(Who made all this nice ascii art btw?)

Given its keen vision, owl should certainly try to use it to guard the
dragon out into escape...


I've put up a still experimental patch at
www.uni-bonn.de/~uzsxtn/arend_3_20.5 which completely revises the
escape influence computation and escape move generation.

It makes a refined (i.e., floating point) computation of the owl escape
values, and tries to replace the pattern based escape move generation
with a systematic one.

This would, IMHO, also allow pattern tuning to be more focussed on
what it can do well, namely building (eye) shape.

It currently has a breakage of s.th. like 90 FAILs vs 130 PASSes. Partly
that shows some more work that has to be done with the patch, but partly I
think it's also to be expected, as the patterns have been tuned for a
long time explicitly against this test set.
(My, of course a little biased, impression is that many of the former
passes are extremely lucky, where patterns matched in completely
unintended ways, but stumbling owl into the right result -- because
otherwise, some tuning would have been done towards this.)

Anyway, my impression is that within reasonable effort this can be
turned into to a definite improvement.

The patch doesn't try to do anything fancy, but just to make sure that
all obvious escape possibilities are used.

The new owl escape values are simply "1.0 + territory_value".

The function dragon_escape() has been replaced by a function based on
the computation of connection distances in readconnect.c. For this,
the core of compute_connection_distances has been split off into a
separate function spread_connection_distances().

The algorithm I use might be best described by the comments in owl.c:

First, we call compute_escape_potential():

/* This function:
 * - Calls spread_connection_distances() to compute the distances to the
 *   goal dragon for all vertices not too far away.
 * - Looks for escape potential on all these vertices, and traces them
 *   back to the goal stone that is closest (setting
 *   escape_coming_from[])
 * - For goal stones, effective_escape[pos] is a weighted sum of the
 *   escape values of all nearby vertices that are traced back to (pos).
 * - For non-goal stones, effective_escape[pos] is set to a (weighted)
 *   sum over the escape values on the path leading from the goal dragon
 *   to (pos).

Then we look for the best candidate pair (origin, target) of a goal stone
(origin) and a point (target) nearby with worthwile escape value, which
gets traced back to (origin) under above rules.
With this pair we call try_to_escape(from=origin, to=target):

/* Try to escape by connectings the string (from) outwards towards (to).
 * If (to) is EMPTY, we play there and check whether the move is
 * connected
 * to (from). If (to) is a string of our color, we first check whether
 * it
 * is already connected to (from) -- if so, we enlarge the owl goal, set
 * (*goal_extended) to 1 and return --, and otherwise we look for a
 * connecting move.

If we find a move there, we value it according to a crude heuristic, and
return that (plus an escape measure) to do_owl_defend().

To make this performance-wise feasible, I introduced new functions in
readconnect.c: fast_connect(), fast_disconnect() with obvious
characteristics.

Since I had to fit that move somewhere in into the move generation in
do_owl_defend(), didn't wanted to put it in disguise under the
shape move, but also didn't want to always put it after or always before
the shape moves, I also ended up reorganizing do_owl_defend() to allow
a more flexible move ordering.

I.e., no strict "pass"es, but instead we prepare all move suggestions
from the different move generators, and select the highest scoring one
each time.

This all needs tuning, of course, needless to say.

I didn't care about semeai stuff so far, this needs to get adressed, of
course.

The changes to readconnect.c contain some fine tuning of
spread_connection_distances that I believe to be worthwile, and which
could be merged separately after testing.

Arend