[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] Patch: New move generator
|
From: |
Inge Wallin |
|
Subject: |
[gnugo-devel] Patch: New move generator |
|
Date: |
Fri, 26 Oct 2001 23:10:21 +0200 (MET DST) |
As I see it, we can improve the strength of Gnu Go in two ways:
a) By digging up more information (tuning, etc)
b) Making more out of the information that we have.
This patch contain both:
It contains a new move generator, which will be a generalized version
of atari_atari. It is called combinations() and is contained in the
new file combinations.c (attached to this mail). Currently it
contains calls to a module that finds multiple attack threats. More
will come here.
I also plan to move much of atari_atari here and to generalize it to
try more threats than just simple ataris at low depths.
I have started to worki on the move valuation to make that more
accurate. The first step is to be more precis in valuation of
attacked worms. Not only the worm itself, but also our own worms and
dragons saved by attacking the worm are now included in the
valuation. I will carry the same ideas to defended worms and to
attacked/defended dragons.
I have only seen one regression difference: Test 215 in owl.tst now
PASSes.
Summary:
- New move generator: combinations() in new file combinations.c
- double attack threats detected
- better valuation of attacks on worms
- general cleanups
-Inge
================================================================
diff -ur gnugo-sync/engine/Makefile.am gnugo-iw/engine/Makefile.am
--- gnugo-sync/engine/Makefile.am Sun Oct 7 12:17:35 2001
+++ gnugo-iw/engine/Makefile.am Fri Oct 26 22:14:30 2001
@@ -20,6 +20,7 @@
board.c \
cache.c \
clock.c \
+ combination.c \
dragon.c \
filllib.c \
fuseki.c \
diff -ur gnugo-sync/engine/Makefile.in gnugo-iw/engine/Makefile.in
--- gnugo-sync/engine/Makefile.in Fri Oct 26 21:05:48 2001
+++ gnugo-iw/engine/Makefile.in Fri Oct 26 22:14:30 2001
@@ -89,7 +89,7 @@
# preconfigured settings for various configurations
noinst_LIBRARIES = libengine.a libboard.a
-libengine_a_SOURCES = aftermath.c board.c cache.c
clock.c dragon.c filllib.c fuseki.c genmove.c
globals.c hash.c influence.c interface.c life.c
matchpat.c move_reasons.c optics.c owl.c printutils.c
readconnect.c reading.c score.c semeai.c
sgfdecide.c sgffile.c shapes.c showbord.c utils.c
worm.c
+libengine_a_SOURCES = aftermath.c board.c cache.c
clock.c combination.c dragon.c filllib.c fuseki.c
genmove.c globals.c hash.c influence.c interface.c
life.c matchpat.c move_reasons.c optics.c owl.c
printutils.c readconnect.c reading.c score.c semeai.c
sgfdecide.c sgffile.c shapes.c showbord.c utils.c
worm.c
libboard_a_SOURCES = board.c cache.c globals.c hash.c
printutils.c sgffile.c showbord.c
@@ -105,7 +105,7 @@
LDFLAGS = @LDFLAGS@
LIBS = @LIBS@
libengine_a_LIBADD =
-libengine_a_OBJECTS = aftermath.o board.o cache.o clock.o dragon.o \
+libengine_a_OBJECTS = aftermath.o board.o cache.o clock.o combination.o
dragon.o \
filllib.o fuseki.o genmove.o globals.o hash.o influence.o interface.o \
life.o matchpat.o move_reasons.o optics.o owl.o printutils.o \
readconnect.o reading.o score.o semeai.o sgfdecide.o sgffile.o shapes.o \
@@ -128,7 +128,7 @@
TAR = tar
GZIP_ENV = --best
DEP_FILES = .deps/aftermath.P .deps/board.P .deps/cache.P .deps/clock.P \
-.deps/dragon.P .deps/filllib.P .deps/fuseki.P .deps/genmove.P \
+.deps/combination.P .deps/dragon.P .deps/filllib.P .deps/fuseki.P
.deps/genmove.P \
.deps/globals.P .deps/hash.P .deps/influence.P .deps/interface.P \
.deps/life.P .deps/matchpat.P .deps/move_reasons.P .deps/optics.P \
.deps/owl.P .deps/printutils.P .deps/readconnect.P .deps/reading.P \
diff -ur gnugo-sync/engine/genmove.c gnugo-iw/engine/genmove.c
--- gnugo-sync/engine/genmove.c Thu Oct 18 19:56:53 2001
+++ gnugo-iw/engine/genmove.c Fri Oct 26 22:14:30 2001
@@ -277,6 +277,11 @@
start_timer(1);
examine_position(color, EXAMINE_ALL);
time_report(1, "examine position", -1, -1, 1.0);
+
+ /* Make a score estimate. This can be used in later stages of the
+ * move generation. If we are ahead, we can play safely and if
+ * we are behind, we have to play more daringly.
+ */
if (level >= 8) {
estimate_score(&lower_bound, &upper_bound);
if (verbose || showscore) {
@@ -298,7 +303,8 @@
else
score = upper_bound;
}
- else score = 0.;
+ else
+ score = 0.;
/*
* Print some of the information if the user wants to.
@@ -335,33 +341,16 @@
fuseki(color);
gg_assert(stackp == 0);
- /* Pattern matcher. */
+ /* The general pattern database. */
start_timer(1);
shapes(color);
time_report(1, "shapes", -1, -1, 1.0);
gg_assert(stackp == 0);
- /* Look for combination attacks. */
- {
- int apos;
- int other = OTHER_COLOR(color);
- int aa_val;
-
- int save_verbose = verbose;
- if (verbose > 0)
- verbose--;
-
- if (save_verbose)
- gprintf("\nlooking for combination attacks ...\n");
- aa_val = atari_atari(color, &apos, save_verbose);
- if (aa_val)
- add_my_atari_atari_move(apos, aa_val);
- aa_val = atari_atari(other, &apos, save_verbose);
- if (aa_val && safe_move(apos, color))
- add_your_atari_atari_move(apos, aa_val);
- verbose = save_verbose;
- }
- time_report(1, "atari atari", -1, -1, 1.0);
+ /* Look for combination attacks and defenses against them. */
+ combinations(color);
+ time_report(1, "combinations", -1, -1, 1.0);
+ gg_assert(stackp == 0);
/* Review the move reasons and estimate move values. */
if (review_move_reasons(i, j, &val, color,
diff -ur gnugo-sync/engine/liberty.h gnugo-iw/engine/liberty.h
--- gnugo-sync/engine/liberty.h Fri Oct 26 21:06:35 2001
+++ gnugo-iw/engine/liberty.h Fri Oct 26 22:16:22 2001
@@ -287,6 +287,8 @@
void add_defense_move(int pos, int ww, int code);
void add_attack_threat_move(int pos, int ww, int code);
void add_defense_threat_move(int pos, int ww, int code);
+int get_attack_threats(int pos, int max_strings, int strings[]);
+int get_defense_threats(int pos, int max_strings, int strings[]);
void add_connection_move(int pos, int dr1, int dr2);
void add_cut_move(int pos, int dr1, int dr2);
void add_antisuji_move(int pos);
@@ -357,6 +359,7 @@
void shapes(int color);
void endgame_shapes(int color);
+void combinations(int color);
int atari_atari(int color, int *move, int save_verbose);
int atari_atari_confirm_safety(int color, int tpos, int *move,
int minsize);
diff -ur gnugo-sync/engine/move_reasons.c gnugo-iw/engine/move_reasons.c
--- gnugo-sync/engine/move_reasons.c Fri Oct 26 21:06:52 2001
+++ gnugo-iw/engine/move_reasons.c Fri Oct 26 22:17:04 2001
@@ -525,6 +525,55 @@
}
+/* Report, or up to max_strings all the strings that are threatened
+ * at (pos).
+ */
+int
+get_attack_threats(int pos, int max_strings, int strings[])
+{
+ int k;
+ int num_strings;
+
+ num_strings = 0;
+ for (k = 0; k < MAX_REASONS; k++) {
+ int r = move[pos].reason[k];
+ if (r < 0)
+ break;
+
+ if (move_reasons[r].type == ATTACK_THREAT_MOVE)
+ strings[num_strings++] = worms[move_reasons[r].what];
+
+ if (num_strings == max_strings)
+ break;
+ }
+
+ return num_strings;
+}
+
+/* Report all, or up to max_strings, the strings that might be defended
+ * at (pos).
+ */
+int get_defense_threats(int pos, int max_strings, int strings[])
+{
+ int k;
+ int num_strings;
+
+ num_strings = 0;
+ for (k = 0; k < MAX_REASONS; k++) {
+ int r = move[pos].reason[k];
+ if (r < 0)
+ break;
+
+ if (move_reasons[r].type == DEFEND_THREAT_MOVE)
+ strings[num_strings++] = worms[move_reasons[r].what];
+
+ if (num_strings == max_strings)
+ break;
+ }
+
+ return num_strings;
+}
+
/*
* Add to the reasons for the move at (pos) that it connects the
* dragons at (dr1) and (dr2). Require that the dragons are
@@ -1937,7 +1986,7 @@
/* Find the stones which are tactically defended by the move by color
- * at (i, j). This is used to stop opponent influence from passing
+ * at (pos). This is used to stop opponent influence from passing
* through strings that we have saved. However, the saved strings do
* not generate influence by themselves, because that would upset the
* current evaluation of saved strings.
@@ -2183,8 +2232,77 @@
return impact * 2.0 * dragon[dragona].effective_size;
}
+
+/* The value attacking a worm at (ww) is twice its effective size,
+ * with the following adjustments:
+ *
+ * If the worm has an adjacent (friendly) dead dragon we add its
+ * value. At least one of the surrounding dragons must be alive.
+ * If not, the worm must produce an eye of sufficient size, and that
+ * should't be accounted for here. As a guess, we suppose that
+ * a critical dragon is alive for our purpose here.
+ *
+ * On the other hand if it has an adjacent critical worm, and
+ * if (pos) does not defend that worm, we subtract the value of the
+ * worm, since (pos) may be defended by attacking that worm. We make at
+ * most one adjustment of each type.
+ */
+
+static float
+attacked_worm_value(int ww)
+{
+ int color;
+ int num_adj;
+ int adjs[MAXCHAIN];
+ int has_live_neighbor = 0;
+ int adjusted_value = 2 * worm[ww].effective_size;
+ float adjustment_up = 0.0;
+ float adjustment_down = 0.0;
+ int s;
+
+ color = OTHER_COLOR(board[ww]);
+ num_adj = chainlinks(ww, adjs);
+ for (s = 0; s < num_adj; s++) {
+ int adj = adjs[s];
+
+ if (dragon[adj].matcher_status == ALIVE
+ || dragon[adj].matcher_status == CRITICAL)
+ has_live_neighbor = 1;
+
+ if (dragon[adj].color == color
+ && dragon[adj].matcher_status == DEAD
+ && 2*dragon[adj].effective_size > adjustment_up)
+ adjustment_up = 2*dragon[adj].effective_size;
+
+ if (dragon[adj].color == color
+ && attack(adj, NULL)
+ && 2*worm[adj].effective_size > adjustment_down)
+ adjustment_down = 2*worm[adj].effective_size;
+ }
+
+ if (has_live_neighbor)
+ adjusted_value += adjustment_up;
+ adjusted_value -= adjustment_down;
+
+ return adjusted_value;
+
+ /*
+ * FIXME: It might be possible that parts of the dragon
+ * can be cut in the process of capturing the (ww)
+ * worm. In that case, not the entire size of the
+ * adjacent dead dragon should be counted as a positive
+ * adjustment. However, it seems difficult to do this
+ * analysis, and in most cases it won't apply, so we
+ * leave it as it is for now.
+ *
+ * TODO:
+ * - cache the result?
+ */
+}
+
+
/*
- * Estimate the direct territorial value of a move at (m,n).
+ * Estimate the direct territorial value of a move at (pos).
*/
static void
estimate_territorial_value(int pos, int color,
@@ -2237,8 +2355,11 @@
break;
}
+#if 0
this_value = 2 * worm[aa].effective_size;
-
+#else
+ this_value = attacked_worm_value(aa);
+#endif
/* If the stones are dead, there is only a secondary value in
* capturing them tactically as well.
*/
@@ -2272,7 +2393,6 @@
TRACE(" %1m: %f - attack on worm %1m with bad ko\n",
pos, this_value, aa);
}
-
tot_value += this_value;
break;
@@ -2373,15 +2493,30 @@
break;
}
- /* The followup value of a move threatening to attack (ai,aj)
+ /* The followup value of a move threatening to attack (aa)
* is twice its effective size, with adjustments. If the
* worm has an adjacent (friendly) dead dragon we add its
* value. On the other hand if it has an adjacent critical
- * worm, and if (m,n) does not defend that worm, we subtract
- * the value of the worm, since (ai,aj) may be defended by
+ * worm, and if (pos) does not defend that worm, we subtract
+ * the value of the worm, since (aa) may be defended by
* attacking that worm. We make at most one adjustment
* of each type.
- */
+ *
+ * FIXME: It might be possible that parts of the dragon
+ * can be cut in the process of capturing the (aa)
+ * worm. In that case, not the entire size of the
+ * adjacent dead dragon should be counted as a positive
+ * adjustment. However, it seems difficult to do this
+ * analysis, and in most cases it won't apply, so we
+ * leave it as it is for now.
+ *
+ * FIXME: The same analysis should be applied to
+ * DEFEND_THREAT_MOVE, ATTACK_MOVE, DEFEND_MOVE;
+ * ATTACK_EITHER_MOVE, DEFEND_BOTH_MOVE, and possibly
+ * the owl attack/defend move reasons. It should be
+ * broken out as separate functions and dealt with in
+ * a structured manner.
+ */
if (trymove(pos, color, "estimate_territorial_value",
NO_MOVE, EMPTY, NO_MOVE)) {
@@ -2732,7 +2867,7 @@
/*
- * Estimate the influence value of a move at (m,n).
+ * Estimate the influence value of a move at (pos).
*
* FIXME: This is much too simplified.
*/
@@ -2788,7 +2923,7 @@
}
/*
- * Estimate the strategical value of a move at (m,n).
+ * Estimate the strategical value of a move at (pos).
*/
static void
estimate_strategical_value(int pos, int color, float score)
@@ -2846,8 +2981,8 @@
&& !move[pos].move_safety)
break;
- /* This is totally ad hoc, just guessing the value of
- * potential cutting points.
+ /* FIXME: This is totally ad hoc, just guessing the value of
+ * potential cutting points.
*/
if (worm[aa].cutstone2 > 1) {
this_value = 10.0 * (worm[aa].cutstone2 - 1);
@@ -2939,15 +3074,26 @@
&& move_reason_known(pos, YOUR_ATARI_ATARI_MOVE, -1))
break;
- this_value = 2 * gg_min(worm[aa].effective_size,
- worm[bb].effective_size);
- if (move_reasons[r].type == ATTACK_EITHER_MOVE)
- TRACE(" %1m: %f - attacks either %1m or %1m\n",
- pos, this_value, aa, bb);
- else
- TRACE(" %1m: %f - defends both %1m and %1m\n",
- pos, this_value, aa, bb);
+ {
+ float aa_value;
+ float bb_value;
+
+ if (move_reasons[r].type == ATTACK_EITHER_MOVE) {
+ aa_value = attacked_worm_value(aa);
+ bb_value = attacked_worm_value(bb);
+ this_value = gg_min(aa_value, bb_value);
+ TRACE(" %1m: %f - attacks either %1m (%f) or %1m (%f)\n",
+ pos, this_value, aa, aa_value, bb, bb_value);
+ }
+ else {
+ this_value = 2 * gg_min(worm[aa].effective_size,
+ worm[bb].effective_size);
+
+ TRACE(" %1m: %f - defends both %1m and %1m\n",
+ pos, this_value, aa, bb);
+ }
+ }
tot_value += this_value;
break;
@@ -3184,7 +3330,7 @@
}
-/* Look through the move reasons to see whether (m, n) is an antisuji move. */
+/* Look through the move reasons to see whether (pos) is an antisuji move. */
static int
is_antisuji_move(int pos)
{
@@ -3277,7 +3423,7 @@
/*
- * Combine the reasons for a move at (m, n) into an old style value.
+ * Combine the reasons for a move at (pos) into an old style value.
* These heuristics are now somewhat less ad hoc but probably still
* need a lot of improvement.
*/
diff -ur gnugo-sync/engine/printutils.c gnugo-iw/engine/printutils.c
--- gnugo-sync/engine/printutils.c Sun Oct 14 17:53:04 2001
+++ gnugo-iw/engine/printutils.c Fri Oct 26 22:14:30 2001
@@ -118,7 +118,7 @@
int pos = va_arg(ap, int);
int m = I(pos);
int n = J(pos);
- if (pos == 0)
+ if (pos == NO_MOVE)
fputs("PASS", outputfile);
else if (!ON_BOARD1(pos))
fprintf(outputfile, "[%d]", pos);
diff -ur gnugo-sync/engine/reading.c gnugo-iw/engine/reading.c
--- gnugo-sync/engine/reading.c Fri Oct 26 21:07:09 2001
+++ gnugo-iw/engine/reading.c Fri Oct 26 22:25:30 2001
@@ -178,6 +178,7 @@
/* Statistics. */
static int reading_node_counter = 0;
+
/* ================================================================ */
/* Goal functions */
/* ================================================================ */
@@ -324,7 +325,7 @@
* is returned and acode is 0. If a string can be attacked and
* defended, WIN is returned, acode and dcode are both non-zero, and
* (attack_point), (defense_point) both point to vertices on the board.
- * If a stringcan be attacked but not defended, 0 is again returned,
+ * If a string can be attacked but not defended, 0 is again returned,
* acode is non-zero, dcode is 0, and (ai, aj) point to a vertex
* on the board.
*
@@ -420,7 +421,8 @@
{
int a_threatened = 0;
int b_threatened = 0;
- int cpos, dpos;
+ int a_savepos;
+ int b_savepos;
int acode = 0;
int dcode = 0;
@@ -428,14 +430,14 @@
ASSERT1(IS_STONE(color) , astr);
ASSERT1(color == board[bstr], bstr);
- attack_and_defend(astr, &acode, NULL, &dcode, &cpos);
+ attack_and_defend(astr, &acode, NULL, &dcode, &a_savepos);
if (acode != 0) {
a_threatened = 1;
if (dcode == 0)
return 0; /* (astr) already lost */
}
- attack_and_defend(bstr, &acode, NULL, &dcode, &dpos);
+ attack_and_defend(bstr, &acode, NULL, &dcode, &b_savepos);
if (acode != 0) {
b_threatened = 1;
if (dcode == 0)
@@ -456,7 +458,7 @@
* defends either string and see if it also defends the other string.
*/
- if (cpos == dpos)
+ if (a_savepos == b_savepos)
return WIN; /* Both strings can be attacked but also defended
* by one move. */
@@ -465,7 +467,7 @@
* somewhat pessimistic estimation.
*/
- if (trymove(cpos, color, "defend_both-A", astr, EMPTY, NO_MOVE)) {
+ if (trymove(a_savepos, color, "defend_both-A", astr, EMPTY, NO_MOVE)) {
if (board[bstr] && !attack(bstr, NULL)) {
popgo();
return WIN;
@@ -473,7 +475,7 @@
popgo();
}
- if (trymove(dpos, color, "defend_both-B", bstr, EMPTY, NO_MOVE)) {
+ if (trymove(b_savepos, color, "defend_both-B", bstr, EMPTY, NO_MOVE)) {
if (board[astr] && !attack(astr, NULL)) {
popgo();
return WIN;
@@ -498,8 +500,8 @@
for (r = 0; r < neighbors1; r++) {
epos = adjs1[r];
if (countlib(epos) <= 4
- && (epos != cpos)
- && (epos != dpos)) {
+ && (epos != a_savepos)
+ && (epos != b_savepos)) {
/* Is (epos) also adjacent to (bstr)? */
for (s = 0; s < neighbors2; s++) {
if (adjs2[s] == adjs1[r])
@@ -764,7 +766,7 @@
/* Global reading functions */
/* ================================================================ */
-/* atari_atari(color, *i, *j) looks for a series of ataris on
+/* atari_atari(color, *move) looks for a series of ataris on
* strings of the other color culminating in the capture of
* a string which is thought to be invulnerable by the reading
* code. Such a move can be missed since it may be that each
@@ -913,7 +915,7 @@
}
/* Helper function for retrieving the aa_status for a string. We can't
- * reliably do this simply by looking up aa_status[m][n] since this is
+ * reliably do this simply by looking up aa_status[pos] since this is
* only valid at vertices which were non-empty at the start of the
* reading. For later added stones, we need to find their aa_status by
* locating a part of the string which was a worm at the beginning of
@@ -937,6 +939,7 @@
return UNKNOWN;
}
+
/* Helper function for atari_atari. Here worms is the number of
* opponent worms involved in the combination, and (last_friendly) is
* the location of the last friendly move played. Moves marked
@@ -1202,7 +1205,7 @@
/* No sufficiently large combination attack, so the move is safe from
* this danger.
- *
+ *
* On rare occasions do_atari_atari might find a combination
* but no defense. In this case we assume that the combination
* is illusory.
@@ -1227,7 +1230,7 @@
popgo();
decrease_depth_values();
/* We know that a combination exists, but we don't know if
- * the original move at (ai, aj) was really relevant. So we
+ * the original move at (aa) was really relevant. So we
* try omitting it and see if a combination is still found.
*/
if (do_atari_atari(other, NULL, NULL, NO_MOVE, 0, minsize) >= after_aa_val)
@@ -1272,8 +1275,6 @@
verbose = save_verbose;
return aa_val;
}
-
-
/* ================================================================ */
diff -ur gnugo-sync/engine/worm.c gnugo-iw/engine/worm.c
--- gnugo-sync/engine/worm.c Fri Oct 26 21:07:14 2001
+++ gnugo-iw/engine/worm.c Fri Oct 26 22:14:30 2001
@@ -75,14 +75,13 @@
/* make_worms() finds all worms and assembles some data about them.
*
- * Each worm is marked with an origin, having coordinates (origini, originj).
- * This is an arbitrarily chosen element of the worm, in practice the
- * algorithm puts the origin at the first element when they are given
- * the lexicographical order, though its location is irrelevant for
- * applications. To see if two stones lie in the same worm, compare
- * their origins.
+ * Each worm is marked with an origin. This is an arbitrarily chosen
+ * element of the worm, in practice the algorithm puts the origin at
+ * the first element when they are given the lexicographical order,
+ * though its location is irrelevant for applications. To see if two
+ * stones lie in the same worm, compare their origins.
*
- * We will use the field dragon[m][n].genus to keep track of
+ * We will use the field dragon[ii].genus to keep track of
* black- or white-bordered cavities (essentially eyes) which are found.
* so this field must be zero'd now.
*/
@@ -112,7 +111,6 @@
gg_assert(stackp == 0);
/* Count liberties of different orders and initialize cutstone fields. */
-
for (m = 0; m < board_size; m++)
for (n = 0; n < board_size; n++) {
int pos = POS(m, n);
@@ -805,7 +803,7 @@
if (board[pos] == EMPTY || !is_worm_origin(pos, pos))
continue;
- TRACE ("considering attack of %m\n", m, n);
+ TRACE ("considering attack of %1m\n", pos);
/* Initialize all relevant fields at once. */
for (k = 0; k < MAX_TACTICAL_POINTS; k++) {
worm[pos].attack_codes[k] = 0;
@@ -817,7 +815,7 @@
acode = attack(pos, &tpos);
if (acode) {
- DEBUG(DEBUG_WORMS, "worm at %m can be attacked at %1m\n", m, n, tpos);
+ DEBUG(DEBUG_WORMS, "worm at %1m can be attacked at %1m\n", pos, tpos);
change_attack(pos, tpos, acode);
}
}
================================================================
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* This is GNU GO, a Go program. Contact address@hidden, or see *
* http://www.gnu.org/software/gnugo/ for more information. *
* *
* Copyright 1999, 2000, 2001 by the Free Software Foundation. *
* *
* This program is free software; you can redistribute it and/or *
* modify it under the terms of the GNU General Public License *
* as published by the Free Software Foundation - version 2. *
* *
* This program is distributed in the hope that it will be *
* useful, but WITHOUT ANY WARRANTY; without even the implied *
* warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR *
* PURPOSE. See the GNU General Public License in file COPYING *
* for more details. *
* *
* You should have received a copy of the GNU General Public *
* License along with this program; if not, write to the Free *
* Software Foundation, Inc., 59 Temple Place - Suite 330, *
* Boston, MA 02111, USA. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* This file contains functions that deals with threats and,
* especially, combinations of threats.
*/
/* FIXME: Move much of atari_atari here. */
#include "liberty.h"
#include "gnugo.h"
#include "gg_utils.h"
static void find_double_threats(int color);
/* Generate move reasons for combination attacks and defenses against
* them.
*/
void
combinations(int color)
{
int save_verbose;
int aa;
int other = OTHER_COLOR(color);
int aa_val;
/* Find intersections with multiple threats. */
find_double_threats(color);
save_verbose = verbose;
if (verbose > 0)
verbose--;
if (save_verbose)
gprintf("\nlooking for combination attacks ...\n");
aa_val = atari_atari(color, &aa, save_verbose);
if (aa_val)
add_my_atari_atari_move(aa, aa_val);
aa_val = atari_atari(other, &aa, save_verbose);
if (aa_val && safe_move(aa, color))
add_your_atari_atari_move(aa, aa_val);
verbose = save_verbose;
}
#define MAX_THREATENED_STRINGS 10 /* Should be enough for one intersection */
static void
find_double_threats(int color)
{
int i, j;
int ii;
int k;
int l;
for (i = 0; i < board_size; ++i)
for (j = 0; j < board_size; ++j) {
int num_a_threatened_groups;
int a_threatened_groups[MAX_THREATENED_STRINGS];
int num_d_threatened_groups;
int d_threatened_groups[MAX_THREATENED_STRINGS];
ii = POS(i, j);
/* Generate ATTACK_EITHER_MOVE move reasons for each pair of the
* threatened strings.
*
* FIXME:
* - This is perhaps not the best way to do it, but realistically
* it will be seldom that more than two strings are threatened
* at the same point. Still, we should find a better way.
* - attack_either_move should be generalized to more than two strings.
*/
num_a_threatened_groups = get_attack_threats(ii, MAX_THREATENED_STRINGS,
a_threatened_groups);
if (num_a_threatened_groups > 1) {
if (trymove(ii, color, "find_double_threats-A", ii, EMPTY, NO_MOVE)) {
for (k = 0; k < num_a_threatened_groups - 1; ++k)
for (l = k + 1; l < num_a_threatened_groups; ++l) {
/* Note: If we used attack_either() here instead of trymove()
* and !defend_both(), we would not make use of the fact
* that we already know of a common threat point for
* the two strings.
* Besides, attack_either is currently (3.1.11) not very good.
*/
if (!defend_both(a_threatened_groups[k], a_threatened_groups[l]))
add_attack_either_move(ii, a_threatened_groups[k],
a_threatened_groups[l]);
}
popgo();
}
}
}
/* FIXME:
* TODO:
* - defense threats
* - combinations of owl threats and other threats
* - combinations of threats to cut and connect
* - combinations of breakins into enemy territory
*/
}
/*
* Local Variables:
* tab-width: 8
* c-basic-offset: 2
* End:
*/