[gnugo-devel] Readconnect based dragon amalgamtion

[Arend Bayer]

On Fri, 26 Apr 2002, Gunnar Farneback wrote:

> Arend wrote:
> > 6. Replace dragon amalgamation by s.th. based on readconnect (and with it
> >    of course the connect/cutting move generator).
> > No. 6: To me it is not even obvious how the information from the connection
> > analysis should be represented. The current amalgamation of worms into
> > dragons cannot encode non-transitivity; and handling this is one of the
> > biggest potentials for improvement in my opinions.
>
> There is no question that major changes are required here. I have some
> ideas, but they are not very mature yet. I can try to give a rough
> description of my current thoughts:
>
> * All current amalgamation sources are thrown out.
> * The dragons are built one at a time.
> * The amalgamation process for a new dragon always starts with the
>   largest free worm.
> * The worms of the dragon are split into "core" and "tails" (these
>   names may require revision).
> * The first worm goes into the core.
> * The neighborhood of the dragon is scanned for potential free worms
>   to amalgamate with. When one is found which can't be disconnected
>   (as determined by readconnect), it is added to the dragon as a tail.
> * The neighborhood of the new tail is scanned for nearby free worms.
>   The ones which can't be disconnected from the tail are marked. Then
>   these are also tested whether they can be disconnected from the
>   (closest) core. If all of them are securely connected, the tail is
>   upgraded to core and the marked worms are added as tails.
> * Repeat until the dragon has grown as much as it can.
> * Repeat until there are no free worms left.
[snip]

I'd like to propose some additional ideas. I think we can start by
analyzing for each worm whether it is connected to its neighbours. Then
I would suggest to store all the results, together with
 - the number of nodes visited in each disconnect analysis
 - some sort of an active area (we have to compute that anyway as we
   we want to have persistent caching for readconnect some day)

(Note that this means we need a considerably larger persistent cache than
currently used in reading.c and owl.c, so that it might be worth
implementing some hashing for the persistent caches.)

Then we should look for interdependencies of such connections. The natural
candidate for these are pairs of connections that hold individually but
not both at a time, e.g. non-transitivity. We only need to test pairs
of connections that have overlapping active area (where we could maybe use
an area a little smaller than in persistent caching). If the connections
A-B and A-C have such a overlap, we test whether B and C are connected. If
not, then these two connection get marked.

All connections that don't get marked can safely be used for amalgamation.
(Which results in somewhat bigger "core"s than what Gunnar is
suggesting.)
Of the marked pairs, we could then use the more valuable of the two
connections (with s.th. like the amalgamate_most_valuable helper heuristic)
to make a core/tail type amalgamtion. I.e., if A is biggest and B bigger
than C in the above example, then A-B would become a dragon with A as core
and B as tail.

Currently it would probably be most safe to let owl run on the core and
the tail seperately -- otherwise owl will defend the connection A-C and
not notice that A-B gets broken. (This should of course be improved,
but this is unlikely to happen in the near future.)

> * It's probably also necessary to add amalgamation for links which can
>   be cut in a readconnect sense, but where the moyo situation
>   indicates that the cut is futile.

Or maybe pass some indication to the strategical evaluation that the
cut isn't good. In particular the iken tobi (without too many nearby enemies)
should be almost connected!

Arend