owl improvements (Re: [gnugo-devel] Owl tuning)

[Arend Bayer]

Hi,


> I've spent a lot of time in the past weeks trying to better understand the
> owl code and more specifically, the owl pattern databases. My attempts at
> automated tunings were unfortunately not successful, but I gathered a lot
> of informations and statistics. The result is a first manual tuning based
> on these and a couple thoughts.

I like your approach. A couple of comments, + an opinionated list of
improvements needed for the owl code below.

> I'll start with the "thoughts". It is first to be noticed that there's a
> large performance (in terms of successes/failures) difference between the
> 2 main databases. While the defense database in average is achieving about
> 66% success rate ('success' here actually means 'non-failure', that is a
> move which doesn't give the opponent a WIN), the attacking one only gets
> a bit more than 26% (!)
>
> Some plausible explanations for this phenomenon :

Isn't the simplest explanation for this that most dragons (at least
those where you still get a lot of matches) occuring in games are alive?

> 1. the attacking database is less developped than the defense one
>
>   Here, I don't have much to say. Maybe we could try to locate positions
>   where the owl attacking code fails to suggest any move (I've seen some
>   cases in the past), and fill the holes...

> 2. defense is overvalued because of the escape potential overestimation
>
>   As said, the defense database performs at 66% globally, but the D13xx
>   patterns alone are way over 80%. I think there are 2 factors here,
>   related to points 3. et 4.
>
>   When a defense pattern is proposing a jump, it is not very well checked
>   that the stone is connected. I made an experiment with D1356 which led
>   to a PASS in lazarus:6 (see below)

That is definitely true. Many patterns lack the context to claim (which
they do) that the played move is connected to the goal dragon. I like
your experiment, but I fear that it is too expensive (judging from the
changes in nodes you give below). There are many patterns that would
need such a change.
What I think would be useful here is a "fast_disconnect()" that would be
the same as disconnect(), except with very low depth and node limits.
(And in doubt we can just assume that the stone is not yet connected,
and maybe amalgamate it later. Or we assume it is connected, once we
have the infrastructure to split a dragon later on.)
Most cases where the stone _is_ connected should be analyzable in less
than 10-20 conection nodes.

>   Also, I think we should maybe rethink the attacking scheme globally.
>   When I take some simple references, like in following :
>   http://senseis.xmp.net/?ApproachingALifeAndDeathProblemTheRightWay
>   it seems to me that we shouldn't generate any kind of placements /
>   vital moves, as long as there still is an escape route available.
>   Easier said than done, but I think we could try to work in this
>   direction.
In fact I have some ideas what to do about this, but unfortunately they
would require a lot of work. I'll try to explain them below.

> 3. defense is overvalued because of the lack of understanding cuts in the
>    goal dragon during the owl reading
>
>   I made some attempts at this a couple weeks ago. I failed to code a
>   proper re-build of the splitted goals. I intend to try again soon, with
>   a direct use of the connection code, and see what happens with the
>   performance...
>
> 4. attacks aren't very well planned
>
>   As said above, too many moves are tried before the dragon has been
>   properly confined. Any suggestions here to make a better job at this ?
>   Maybe differentiate WINs by escape from others, and stop trying vital
>   attack moves as soon as one of them failed because the goal escaped...

> 5. attacks are tried against obviously unkillable dragons
>
>   I was about to propose a couple changes in the current code to prevent
>   these wasteful attacks, but Arend's recent patch might very well change
>   things a lot here, so better wait and see.

I had hoped for that, but didn't achieve much. The net effect was
certainly almost zero. Anyway, I think the better way to solve this is
to make the owl code aware that a dragon is obviously unkillable
(because if a dragon becomes obviously unkillable during the owl
reading, we shouldn't waste owl nodes there either).

I'd still be interested to hear about the changes you wanted to propose.

I'll add:
6. Big dragons that have many places where owl defense patterns can
match will never be considered dead.

That is because when there are many patterns matching, the reading will
always go below OWL_DEPTH, and then the dragon is considered alive. This
is an important thing to fix, I believe.

> Breakage (compared to CVS before arend_3_13.7a) is rather light :
>  9 PASSes and 2 FAILures.

The breakage looks obviously good. Did you measure the performance
impact if you leave out the change to D1356?
[N.B.: The reading node increase is probably mostly in nodes in
simple_ladder_attack/defense, where we are spending, I think, around 20%
of reading nodes at the moment. They are, however, probably not very
expensive reading nodes.]


So here is a list of things we should IMO improve in the owl code. In order
of decreasing importance, according to my wild guesses:

1) Seriously improve eye space analysis.
2a) Better generation of escape moves. (This includes moves connecting
to another dragon. Of course same goes for attacking moves preventing escape.)
2b) Bettter analyis of escape value.
3) Better recognize weaknesses in the surrounding chains.
4) Recognize cuts in the dragon.
5) A better move ordering that uses more input than just hard-coded
pattern values.

I think Gunnar and Paul have ideas for 1). Once I've finished my big
influence cleanup, I want to make a serious try at 2b). It also seems to
me that escape moves might better be generated systematically than via
patterns. S.th. as "jump towards biggest source of escape value of the
dragon". Well that may work, or it may not. But I do think it's more
flexible.
[I have probably seen to many cases where owl was missing a trivial move
to prevent a connection to a neighboring dragon, so that I am a bit
skeptical that we can ever have a comprehensive pattern database for
these cases.]

Probably 3) is hard. 4) is hard to do without badly hurting performance.

As for 5), I think it would make a lot of sense to try iterative
deepening in the owl code. This means doing the same reading repeatedly with
increasing reading depth, until we have reached full depth. The previous
results then get used to select the move ordering.

When the reading has to stop early because of a depth limit in the
"preliminary runs", the code would then have to return a much more
fine-grained value than WIN or 0. This would be based on escape values
and probable eyes.
The net effect would be that moves get ordered by the resulting eye
and escape values one or several moves later. This seems to me a much
more reliable estimate than hard-coded pattern values.

This could also address the issues you bring up in 2. and 4., Nando.
When we miss an important move to confine the dragon, and in result a
straightforward move by the defender substantially increases the
dragon's escape value, then this move will immediately get valued down
for the next run (with higher depth).

In other words, make our owl less short-sighted!

        (In general I think we should try to slowly decrease the importance
        of patterns -- this does not mean replacing them, there is
        probably nothing that could select moves to generate eye space as
        good as patterns can.  But if the owl code doesn't take everything
        provided in the pattern for granted (such as connected-ness or the
        the move value), it should get a lot easier to tune and maintain
        these big databases.)

Ok this is probably a lot of opinions, and I am everywhere glad to be
proven wrong by better suggestions...

Arend