[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] My plans for generalized handling of threats
[gnugo-devel] My plans for generalized handling of threats
Fri, 21 Dec 2001 10:40:24 +0100 (CET)
Here is a description of what I plan to do with threats and the
First, let's take a look at what we have today. We have move reasons
- attacks and defenses for strings (including those with different
levels of success: GOOD_KO, etc)
- connections and cuts
- 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
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)
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
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)
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
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
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? :-)
- [gnugo-devel] My plans for generalized handling of threats,
Inge Wallin <=