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

[Gunnar Farneback]

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

Thanks. Please be aware that some of the comments below are directly
related to Inge's proposal while others are general reflections on the
state of of the move valuation scheme.

> 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.

In some sense maybe, but there are very big differences in the
valuation and handling of these. I'll make comments on the specific
move reasons:

ATTACK_MOVE            
ATTACK_MOVE_GOOD_KO    
ATTACK_MOVE_BAD_KO     
DEFEND_MOVE            
DEFEND_MOVE_GOOD_KO    
DEFEND_MOVE_BAD_KO     

These are straightforward, except that there's a lot of testing
required to decide whether they are meaningful. Threats make sense and
are available today (except for ko status).


OWL_ATTACK_MOVE        
OWL_ATTACK_MOVE_GOOD_KO
OWL_ATTACK_MOVE_BAD_KO 
OWL_DEFEND_MOVE        
OWL_DEFEND_MOVE_GOOD_KO
OWL_DEFEND_MOVE_BAD_KO 

These are also quite straightforward and simpler than the ones before
in that it's not necessary to test whether they are meaningful.
Threats make sense and are available today (except for ko status),
although sometimes of a questionable quality.


VITAL_EYE_MOVE         

This is only used as a hint for where to search for additional owl
moves and is not used for actual valuation at all. Threats make only
little sense since it would be better to search for owl threats
directly.


CONNECT_MOVE           
CUT_MOVE               

These are used as hints for where to find additional owl moves and in
the move valuation to give strategic bonuses when life and death is
not directly involved. Threats make sense but we don't have sufficient
machinery to generate them yet. Cut threats are particularly difficult
with the current dragon amalgamation paradigm.


SEMEAI_MOVE

These are not really different from owl attacks/defenses of pairs of
dragons. The best way to evaluate them is probably to convert them
into owl moves at an early time, possibly when they are first
generated. Threats make sense but shouldn't really be distinguished
from (pairs of) owl threats.


BLOCK_TERRITORY_MOVE   
EXPAND_TERRITORY_MOVE  
EXPAND_MOYO_MOVE       

Today these are all identical from the move valuation point of view
and they only convey the information that the move is supposed to be
safe. The meaning of a threat is very unclear.


> MY_ATARI_ATARI_MOVE    
> YOUR_ATARI_ATARI_MOVE  

These are special in that we don't know beforehand exactly what is
attacked or defended. The reasonable way to valuate these is to try to
determine what is effectively attacked/defended and convert it into a
plain attack/defend move. Threats make sense but we don't yet have
machinery to compute them.


ATTACK_EITHER_MOVE     
DEFEND_BOTH_MOVE

These are essentially special cases of the ATARI_ATARI move reasons,
though computed in a different way. There are unsolved issues related
to the fact that if one move has a DEFEND_BOTH reason while another
move only has separate DEFEND reasons for both strings, the latter
move probably doesn't really defend both strings against a combination
attack.


STRATEGIC_ATTACK_MOVE  
STRATEGIC_DEFEND_MOVE  
UNCERTAIN_OWL_ATTACK   
UNCERTAIN_OWL_DEFENSE  
ANTISUJI_MOVE          

These are all very special. Threats are either meaningless or of
limited value.


> 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.

I only think it's meaningful to be able to handle cut/connect and
atari_atari.

> 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.

I don't understand your last claim. First I don't see exactly why you
need an OWL_DEFEND_OR_CONNECT. It seems to me that having both
OWL_ATTACK_THREAT and CONNECT_THREAT reasons for the move would be
equivalent. And if you really would need an OWL_DEFEND_OR_CONNECT, how
could it possibly help to split off the threat status from the reason
names and store it separately as an attribute?

As argued above I don't see a need for very many additional threats.

> 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).

What you really need is to modify the internal data structures in
move_reasons.c. It is not necessary to change the external interface,
i.e. the add_* calls, at this time. There are no additional threats
that we are anywhere close to being able to add now.

> 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.

The code to handle separate ko values also becomes more complex than
what we have today, but when we want to extend the ko handling in the
move valuation in some way we should certainly take that hit.

> 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.

This would be okay if it had less impact on the rest of the code. I
see essentially three problems:
1. The annoying is_threat parameter in all add_*_move calls from the
rest of the engine.
2. The switch statements become less effective when a real move and a
threat are forced into the same case. Only in list_move_reasons() I
can see that this has positive effects.
3. There is a lot of extra code to test the is_threat field everywhere
in move_reasons.c.

Further discussion of this at the end.

> 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.

The current valuation of ATTACK_EITHER and DEFEND_BOTH is not very
satisfying. How do you more exactly propose to valuate EITHER and ALL?

How do you plan to represent the information for those operators?

> 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. 

Do you have any suggestions how to get this valuation right?

> 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.

The last example indicates that you might be overestimating the
potential of this approach. The owl code already knows about the trick
of living by simultaneously threatening to make two eyes and connect
out.

> I hope this is what you wanted in the way of explanation.

It's a good start, but it will take a bit more before I can see
whether this is likely to work in practice or not.

> Now, can you please enter my patch into CVS?  :-)

Not without revisions. My current opinion is

1. Don't change the external interface to move_reasons.c. That's easy
to do later when and if it turns out that we need more generality
there.

2. I can accept separating the threat property from the main move
reason, but I'd like to have a solution which avoids the switch
problem and reduces the amount of testing of the is_threat property.
I'm starting to think that Arend's proposal makes a lot of sense.
Inge's patch adds a new field "is_threat" in struct move_reason. This
only takes the values 0 and 1 so it would not be very different to
encode it as a bit in the "type" field of the same struct, which is
what Arend proposed. This would clearly solve the switch problem and
likely simplify some of the other code (compared to a separate
is_threat field). What do you think about this solution, Inge?

3. For later changes in this scheme, try to keep the modifications as
small as possible and be prepared to work within an
EXPERIMENTAL_WHATEVER conditional if the changes risk to become
disruptive in some way. Should this approach turn out to be a dead end
for some reason I'd like to be able to revert it without too much
trouble.

4. No TRUE and FALSE.

/Gunnar