[gnugo-devel] Semeai code redesign

[Gunnar Farneback]

Arend wrote:
> Dan wrote:
> > I don't think we can make the results of owl_analyze_semeai() as
> > reliable as owl_attack() and owl_defend() before 3.4 but we can
> > try.
> 
> I see the following low-hanging fruit that we should at least try
> before 3.4:
> 1. Make the decision about life and death completely parallel with that
> in owl_attack()/defend(). (And of course, share more code while doing
> that on the way.)
> 2. Treat the case where we run out of semeai nodes specially, probably
> using the global result_certain in owl.c (instead of declaring seki in
> these cases).

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.

More specifically I see the following problem areas to address:

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.

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.

3. The semeai code needs to correctly understand positions where "both
   dragons die".

In positions where one of the dragons is effectively inessential,
capturing it may not suffice to make life, see e.g. the new test cases
semeai:41,42:

 7 O O O 
 6 . . O O 
 5 X X . O O 
 4 . X X + O O O 
 3 O . X X . O O 
 2 O O . X . O O 
 1 . O . X . O O 
   A B C D E F G 

Here X can capture the O stones but still does not live if O plays A1
at the right moment. Thus it would look like both dragons die, but
obviously the most useful result to report is that O lives and X dies.
If this is solved, we should no longer need some of the exceptions
between lines 140 and 160 of semeai.c.


Proposed solutions:

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.

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.

3. This is mainly a question of modifying the handling of "semeai
   worms" in order not to claim victory too early and never admit
   defeat unless the opponent is either alive or captured(!). It would
   probably be a good idea to distinguish between critical semeai
   worms (e.g. worms neighboring the "outside" so that capturing them
   would connect out or worms too big to ever be part of a nakade) and
   noncritical semeai worms.

/Gunnar