Re: [gnugo-devel] Semeai code redesign

[bump]

Gunnar wrote:

> I think the semeai code needs an immediate redesign. The current code
> works well for the basic problems at the start of semeai.tst but runs
> into trouble in real positions, in particular when the surroundings
> are less than solid. It's not uncommon that large parts of the
> variation tree doesn't make much sense.

The semeai code clearly has problems. I don't think writing
a strong semeai module will be easy. I had been assuming this
task would be post 3.4 but if Gunnar wants to try I have no objection
and will try to help.

> 1. The semeai code needs to be ko aware.
> 
> Currently ko is not considered by the semeai code. This is problematic
> because ko situations are rather frequent in semeais, in particular
> with two opposing dragons on the second line. Additionally we need an
> active komaster scheme to avoid double ko repetitions.

and:

> 1. The current scheme has results consisting of two status (or safety)
>    values, e.g. "DEAD ALIVE" or "ALIVE_IN_SEKI ALIVE_IN_SEKI" where
>    the first is the status of dragon A and the second is the status of
>    dragon B when dragon A moves first.
> 
>    I propose replacing these with two "read results", i.e. 0, KO_A,
>    KO_B, WIN, with the interpretation that these are the results of
>    simultaneous owl_defense of dragon A and owl_attack on dragon B
>    (for a semeai aware owl attack/defense that is). Thus we would have
>    the following translation between old codes and new codes
> 
>    DEAD ALIVE                  -  0   0
>    ALIVE DEAD                  -  WIN WIN
>    ALIVE ALIVE                 -  WIN 0
>    ALIVE_IN_SEKI ALIVE_IN_SEKI -  WIN 0
> 
>    It should be obvious how this extends to ko semeai results and the
>    same approaches as in do_owl_attack() and do_owl_defend() would
>    apply to the computation of ko results.
> 
>    The main weakness of this scheme is that it doesn't differ between
>    mutual life in seki and mutual independent life. Most of the time
>    this is unimportant or makes a difference of a few points only but
>    occasionally it makes a huge difference. How significant a problem
>    is this in practice? Can we live with the weakness? Notice that a
>    complete solution would not only need to distinguish between
>    independent life and life in seki, but also between ko for seki and
>    ko for independent life.

This scheme sounds workable. If I understand correctly this will
not require more room in the hash nodes.

Regarding your last point I think we can ignore the
distinction between life in seki and independent life.
If we can get a better semeai module, this is a small
price to pay.

> 2. Premature optimizations get in the way.
> 
> The semeai code includes various tricks to speed up the analysis,
> including early decisions about life and death (has been discussed
> before) and switching over to tactical analysis after a while to avoid
> running the optics code and pattern matching. Both these are error
> prone in real positions. In the short term it's more urgent to improve
> robustness than to gain speed.

and:

> 2. The problem with early life and death decisions can be solved by
>    removing most of that code. The semeai code should only be allowed
>    to admit defeat voluntarily or identify both dragons as alive (i.e.
>    it is not allowed to declare the opponent as dead unless it says so
>    when asked). On the other hand, if one of the dragons is clearly
>    alive, no moves should be generated to maybe attack or defend it.
>    The meaning of "clearly alive" would naturally be similar to the
>    owl code and its use of "pessimistic number of eyes".
> 
>    The concept of tactical semeai had better be skipped. It's too
>    common that there's a need to reinforce the perimeter or find a
>    vital eye move after some rounds of liberty filling. As a
>    consequence we would have to permanently retire the small_semeai()
>    function, which depends on tactical semeai reading, but it has
>    already been disabled for a while without apparent problems.

If we intend to remove the distinction between the owl phase
and the tactical phase I'd suggest either developing an alternative
module in parallel and swapping it in when it's working right
(as was done with the connection code) or putting this change
off until the ko revision is already done. 

The reason is that I'm not convinced it will will be so easy
to remove the distinction between an owl phase and a tactical
and get a working module.

The ko change is going to require changes in semeai.c as well
as owl.c and would clearly benefit the existing semeai
module. I'd prefer a revision path that makes this change
first, then see if you can remove the tactical phase.

The third change that Gunnar proposes seems less significant
than the other two.

Dan