[gnugo-devel] My plans for generalized handling of threats

[Inge Wallin]

Here is a description of what I plan to do with threats and the
combination module.

First, let's take a look at what we have today.  We have move reasons
that cover:
 - attacks and defenses for strings (including those with different
   levels of success: GOOD_KO, etc)
 - connections and cuts
 - semeais
 - eye moves
 - taking and defending territory
 - attacking and defending whole groups
 - combination attacks (atari_atari)

These work outright.  We also have a few vaguer move reasons
(strategic attack and defense) and combination move reasons
(attack_either, defend_both). Last, we have the antisuji move reason
as a special case.

Of the move reasons in the list above, only attacks and defenses of
strings and groups and semeais have variants with threats
(ATTACK_THREAT_MOVE, DEFEND_THREAT_MOVE, OWL_ATTACK_THREAT,
OWL_DEFENSE_THREAT and SEMEAI_THREAT).  I would like to extend this so
that all the move reasons have similar threat variants.

Now, let's look at attack_either and defend_both.  These are very
special move reasons that combine other, more simple, move reasons
into one.  You can say that attack_either is a special case of what I
plan to do: generalization of combinations of threats.

Ok that's the analysis of what we have. How should we extend this?  I
would like to do two things:
1. Make the engine handle threats for anything that is worthwhile.  To
   me that would be the same as making it handle threats for the move
   reasons in the list above.
2. Combine the threats in a general way so that we can use threats for
   sente, and for creating moves that combine threats against several
   different targets and take advantage of the fact that the opponent
   can't defend against them all at the same time.  Of course we also
   want to avoid making moves that opens ourselves against such
   combination attacks (like YOUR_ATARI_ATARI_MOVE does today). 

Now to the implementation.

First, we have to make the engine ready to store threats in general.
We can do this in two ways:
1. Create special move reasons for each and every combination of
   threat.  This will give us move reasons like CUT_THREAT,
   EXPAND_TERRITORY_THREAT and so on.  It would also have to include
   ATTACK_OR_WIN_SEMAI, OW_DEFEND_OR_CONNECT and so on.
2. Treat threats as a property of every move that can have that
   property (e.g. by introducing a parameter to appropriate
   add_move_reason calls).

I think that the way to go is number 2.  Number 1 is certainly
possible, but it is difficult to combine with the fact that move
reasons are also used to keep information about how well a move
succeeds.  This can be seen in the move reason
OWL_ATTACK_MOVE_GOOD_KO. In the end we will end up with move reasons
like ATTACK_WITH_TWO_STEP_APPROACH_MOVE_GOOD_KO_THREAT, which is not
the way I think we want to go.  If nothing else, the code to evaluate
such moves will be extremely complex.

So how can we use this to implement more general handling of
combinations?  First, we will look at the ATTACK_EITHER move
reason. What it actually says is that there are two treats, each one
to capture one string and that both can't be defended simultaneously.
That is certainly useful knowledge.  More formally it can be written
as (using a LISP-like notation): 

  (EITHER (ATTACK_THREAT aa)
          (ATTACK_THREAT bb))

where the EITHER operator means that at least one of the treats will
be allowed to be carried out no matter what defense the opponent
tries.

This can be generalized in at least two ways:
1. Permit more than two threats to be used.
2. Permit other types of threats than attacks on strings.

Similarly the DEFEND_BOTH move reason can be written:

  (ALL (DEFEND_THREAT aa)
       (DEFEND_THREAT bb))

where the ALL operator means that all threats can be carried out.  The
same generalizations as for the EITHER operator can be performed for
the ALL operator.

So what I plan is to introduce exactly this in a number of steps:

1. Introduce threats as a general property of the move reasons in the
   list above.  Antisujis and vague threats (STRATEGIC_ATTACK/DEFEND)
   are excluded here, of course.  This is what my original patch that
   started the discussion did.

2. Introduce the EITHER and ALL operators into the move valuation.
   First I will just switch the handling of the special cases
   ATTACK_EITHER and DEFEND_BOTH for the more general code and if it
   works correctly there will be no changes to any regression tests. I
   will start with exactly two operands. More general handling will
   come later.

3. Enhance find_double_threats with code that combines attack and
   defense threats of strings like "this move threatens to attack
   string A and defend string B at the same time". It is possible to
   do using the threat generators that exist today and will provide a
   good foundation for future work.  Especially it will highlight the
   difficulty of valuation when the defense against one threat
   influences the valuation of the threat that is actually carried
   out. 

4. Make find_double_threats handle owl threats and semeai threats as
   well.  I don't expect that there will be very many cases where
   semeai threats can be combined with other threats since semeais are
   often fought out in enclosed spaces.  Nevertheless they should be
   included into the general scheme of things.

5. Enhance some move generators to generate other types of threats.  I
   am not really sure where to do it first, but a good start would
   probably be eye threats and threats to cut and connect.  Here I
   would like to get help from other people. 

  I think that here is where we will really see increased strength
  from this scheme.  Combinations of threats to connect and threats to
  live with two eyes would be particularly powerful.

Somewhere here, my plans start to get a bit fussy around the edges but
natural next steps would be to enhance the atari_atari scheme with what
we have learnt so far. I also expect others to step in with their own
ideas and maybe even code.

I hope this is what you wanted in the way of explanation.  Now, can
you please enter my patch into CVS?  :-)

    -Inge