/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* This is GNU Go, a Go program. Contact gnugo@gnu.org, or see *
* http://www.gnu.org/software/gnugo/ for more information. *
* Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, *
* 2008 and 2009 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 3 or *
* (at your option) any later version. *
* 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., 51 Franklin Street, Fifth Floor, *
* Boston, MA 02111, USA. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
static void compute_effective_worm_sizes(void);
static void do_compute_effective_worm_sizes(int color
,
int (*cw
)[MAX_CLOSE_WORMS
],
int *ncw
, int max_distance
);
static void compute_unconditional_status(void);
static void find_worm_attacks_and_defenses(void);
static void find_worm_threats(void);
static int find_lunch(int str
, int *lunch
);
static void change_tactical_point(int str
, int move
, int code
,
int points
[MAX_TACTICAL_POINTS
],
int codes
[MAX_TACTICAL_POINTS
]);
static void propagate_worm2(int str
);
static int genus(int str
);
static void markcomponent(int str
, int pos
, int mg
[BOARDMAX
]);
static int examine_cavity(int pos
, int *edge
);
static void cavity_recurse(int pos
, int mx
[BOARDMAX
],
int *border_color
, int *edge
, int str
);
static void ping_cave(int str
, int *result1
, int *result2
,
int *result3
, int *result4
);
static void ping_recurse(int pos
, int *counter
,
int mr
[BOARDMAX
], int color
);
static int touching(int pos
, int color
);
static void find_attack_patterns(void);
static void attack_callback(int anchor
, int color
,
struct pattern
*pattern
, int ll
, void *data
);
static void find_defense_patterns(void);
static void defense_callback(int anchor
, int color
,
struct pattern
*pattern
, int ll
, void *data
);
static void build_worms(void);
static void report_worm(int pos
);
/* A worm or string is a maximal connected set of stones of the same color,
* Cavities are sets of connected empty vertices.
/* make_worms() finds all worms and assembles some data about them.
* 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[ii].genus to keep track of
* black- or white-bordered cavities (essentially eyes) which are found.
* so this field must be zero'd now.
/* Build the basic worm data: color, origin, size, liberties. */
/* No point continuing if the board is completely empty. */
if (stones_on_board(BLACK
| WHITE
) == 0)
/* Compute effective sizes of all worms. */
compute_effective_worm_sizes();
/* Look for unconditionally alive and dead worms, and unconditional
compute_unconditional_status();
find_worm_attacks_and_defenses();
/* Count liberties of different orders and initialize cutstone fields. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (IS_STONE(board
[pos
]) && is_worm_origin(pos
, pos
)) {
int lib1
, lib2
, lib3
, lib4
;
ping_cave(pos
, &lib1
, &lib2
, &lib3
, &lib4
);
ASSERT1(worm
[pos
].liberties
== lib1
, pos
);
worm
[pos
].liberties2
= lib2
;
worm
[pos
].liberties3
= lib3
;
worm
[pos
].liberties4
= lib4
;
* There are two concepts of cutting stones in the worm array.
* A CUTTING STONE is one adjacent to two enemy strings,
* which do not have a liberty in common. The most common
* type of cutting string is in this situation.
* A POTENTIAL CUTTING STONE is adjacent to two enemy
* strings which do share a liberty. For example, X in:
* For cutting strings we set worm[m][n].cutstone=2. For potential
* cutting strings we set worm[m][n].cutstone=1. For other strings,
* Cutting points are identified by the patterns in the
* connections database. Proper cuts are handled by the fact
* that attacking and defending moves also count as moves
* cutting or connecting the surrounding dragons.
* The cutstone field will now be set. The cutstone2 field is set
* later, during find_cuts(), called from make_dragons().
* We maintain both fields because the historically older cutstone
* field is needed to deal with the fact that e.g. in the position
* the X stones are amalgamated into one dragon because neither cut
* works as long as the two O stones are in atari. Therefore we add
* one to the cutstone field for each potential cutting point,
* indicating that these O stones are indeed worth rescuing.
* For the time being we use both concepts in parallel. It's
* possible we also need the old concept for correct handling of lunches.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
/* Only work on each worm once. This is easiest done if we only
* work with the origin of each worm.
if (!IS_STONE(board
[pos
]) || !is_worm_origin(pos
, pos
))
/* Try to find two adjacent worms (w1) and (w2)
* of opposite colour from (pos).
for (pos2
= BOARDMIN
; pos2
< BOARDMAX
; pos2
++) {
/* Work only with the opposite color from (pos). */
if (board
[pos2
] != OTHER_COLOR(board
[pos
]))
for (k
= 0; k
< 4; k
++) {
if (!ON_BOARD(pos2
+ delta
[k
])
|| worm
[pos2
+ delta
[k
]].origin
!= pos
)
ASSERT1(board
[pos2
+ delta
[k
]] == board
[pos
], pos
);
/* If we have not already found a worm which meets the criteria,
* store it into (w1), otherwise store it into (w2).
else if (!is_same_worm(pos2
, w1
))
* We now verify the definition of cutting stones. We have
* verified that the string at (pos) is adjacent to two enemy
* strings at (w1) and (w2). We need to know if these
* strings share a liberty.
/* Only do this if we really found something. */
if (count_common_libs(w1
, w2
) > 0)
DEBUG(DEBUG_WORMS
, "Worm at %1m has w1 %1m and w2 %1m, cutstone %d\n",
pos
, w1
, w2
, worm
[pos
].cutstone
);
/* Set the genus of all worms. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (IS_STONE(board
[pos
]) && is_worm_origin(pos
, pos
)) {
worm
[pos
].genus
= genus(pos
);
/* Now we try to improve the values of worm.attack and worm.defend.
* If we find that capturing the string at str also defends the
* string at str2, or attacks it, then we add points of attack and
* defense. We don't add attacking point for strings that can't be
int moves_to_try
[BOARDMAX
];
memset(moves_to_try
, 0, sizeof(moves_to_try
));
/* Find which colors to try at what points. */
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++) {
if (IS_STONE(board
[str
]) && is_worm_origin(str
, str
)) {
moves_to_try
[worm
[str
].defense_points
[0]] |= color
;
moves_to_try
[worm
[str
].attack_points
[0]] |= OTHER_COLOR(color
);
/* Loop over the board and over the colors and try the moves found
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
for (color
= WHITE
; color
<= BLACK
; color
++) {
if (!(moves_to_try
[pos
] & color
))
/* Try to play color at pos and see what it leads to. */
if (!trymove(pos
, color
, "make_worms", NO_MOVE
))
/* We must read to the same depth that was used in the
* initial determination of worm.attack and worm.defend
* to avoid horizon effects. Since stackp has been
* incremented we must also increment depth values.
DEBUG(DEBUG_WORMS
, "trying %1m\n", pos
);
/* Now we try to find a group which is saved or attacked as well
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++) {
if (!IS_STONE(board
[str
])
|| !is_worm_origin(str
, str
))
/* If the worm is of the opposite color to the move,
* then we try to defend it. If there was a previous
* attack and defense of it, and there is no defense
if (worm
[str
].color
== OTHER_COLOR(color
)
&& worm
[str
].attack_codes
[0] != 0
&& worm
[str
].defense_codes
[0] != 0) {
int dcode
= find_defense(str
, NULL
);
if (dcode
< worm
[str
].defense_codes
[0]) {
/* Sometimes find_defense() fails to find a
* defense which has been found by other means.
* Try if the old defense move still works.
* However, we first check if the _attack_ still exists,
* because we could, for instance, drive the worm into
if (attack(str
, NULL
) >= worm
[str
].attack_codes
[0]) {
if (worm
[str
].defense_codes
[0] != 0
&& trymove(worm
[str
].defense_points
[0],
OTHER_COLOR(color
), "make_worms", 0)) {
int this_dcode
= REVERSE_RESULT(attack(str
, NULL
));
if (this_dcode
> dcode
) {
if (dcode
>= worm
[str
].defense_codes
[0])
/* ...then add an attack point of that worm at pos. */
"adding point of attack of %1m at %1m with code %d\n",
str
, pos
, REVERSE_RESULT(dcode
));
change_attack(str
, pos
, REVERSE_RESULT(dcode
));
/* If the worm is of the same color as the move we try to
* attack it. If there previously was an attack on it, but
* there is none now, then add a defense point of str at
else if (worm
[str
].color
== color
&& worm
[str
].attack_codes
[0] != 0) {
int acode
= attack(str
, NULL
);
if (acode
< worm
[str
].attack_codes
[0]) {
/* Sometimes attack() fails to find an
* attack which has been found by other means.
* Try if the old attack move still works.
if (worm
[str
].attack_codes
[0] != 0
&& trymove(worm
[str
].attack_points
[0],
OTHER_COLOR(color
), "make_worms", 0)) {
this_acode
= REVERSE_RESULT(find_defense(str
, NULL
));
if (this_acode
> acode
) {
if (acode
>= worm
[str
].attack_codes
[0])
/* ...then add an attack point of that worm at pos. */
"adding point of defense of %1m at %1m with code %d\n",
str
, pos
, REVERSE_RESULT(acode
));
change_defense(str
, pos
, REVERSE_RESULT(acode
));
/* Sometimes it happens that the tactical reading finds adjacent
* strings which both can be attacked but not defended. (The reason
* seems to be that the attacker tries harder to attack a string,
* than the defender tries to capture it's neighbors.) When this
* happens, the eyes code produces overlapping eye spaces and, still
* worse, all the nondefendable stones actually get amalgamated with
* their allies on the outside.
* To solve this we scan through the strings which can't be defended
* and check whether they have a neighbor that can be attacked. In
* this case we set the defense point of the former string to the
* attacking point of the latter.
* Please notice that find_defense() will still read this out
* incorrectly, which may lead to some confusion later.
/* First look for vertical neighbors. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
&& IS_STONE(board
[SOUTH(pos
)])
&& !is_same_worm(pos
, SOUTH(pos
))) {
if (worm
[pos
].attack_codes
[0] != 0
&& worm
[SOUTH(pos
)].attack_codes
[0] != 0) {
if (worm
[pos
].defense_codes
[0] == 0
&& does_defend(worm
[SOUTH(pos
)].attack_points
[0], pos
)) {
/* FIXME: need to check ko relationship here */
change_defense(pos
, worm
[SOUTH(pos
)].attack_points
[0], WIN
);
if (worm
[SOUTH(pos
)].defense_codes
[0] == 0
&& does_defend(worm
[pos
].attack_points
[0], SOUTH(pos
))) {
/* FIXME: need to check ko relationship here */
change_defense(SOUTH(pos
), worm
[pos
].attack_points
[0], WIN
);
/* Then look for horizontal neighbors. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
&& IS_STONE(board
[EAST(pos
)])
&& !is_same_worm(pos
, EAST(pos
))) {
if (worm
[pos
].attack_codes
[0] != 0
&& worm
[EAST(pos
)].attack_codes
[0] != 0) {
if (worm
[pos
].defense_codes
[0] == 0
&& does_defend(worm
[EAST(pos
)].attack_points
[0], pos
)) {
/* FIXME: need to check ko relationship here */
change_defense(pos
, worm
[EAST(pos
)].attack_points
[0], WIN
);
if (worm
[EAST(pos
)].defense_codes
[0] == 0
&& does_defend(worm
[pos
].attack_points
[0], EAST(pos
))) {
/* FIXME: need to check ko relationship here */
change_defense(EAST(pos
), worm
[pos
].attack_points
[0], WIN
);
/* Find adjacent worms that can be easily captured, aka lunches. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!IS_STONE(board
[pos
]) || !is_worm_origin(pos
, pos
))
if (find_lunch(pos
, &lunch
)
&& (worm
[lunch
].attack_codes
[0] == WIN
|| worm
[lunch
].attack_codes
[0] == KO_A
)) {
DEBUG(DEBUG_WORMS
, "lunch found for %1m at %1m\n", pos
, lunch
);
worm
[pos
].lunch
= NO_MOVE
;
if (!disable_threat_computation
)
/* Identify INESSENTIAL strings.
* These are defined as surrounded strings which have no life
* potential unless part of their surrounding chain can be captured.
* We give a conservative definition of inessential:
* - the genus must be zero
* - there can no second order liberties
* - there can be no more than two edge liberties
* - if it is removed from the board, the remaining cavity has
* border color the opposite color of the string
* - it contains at most two edge vertices.
* If we get serious about identifying seki, we might want to add:
* - if it has fewer than 4 liberties it is tactically dead.
* The last condition is helpful in excluding strings which are
* An inessential string can be thought of as residing inside the
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
&& worm
[pos
].origin
== pos
&& worm
[pos
].liberties2
== 0
&& worm
[pos
].lunch
== NO_MOVE
) {
int border_color
= examine_cavity(pos
, &edge
);
if (border_color
!= GRAY
&& edge
< 3) {
DEBUG(DEBUG_WORMS
, "Worm %1m identified as inessential.\n", pos
);
worm
[pos
].inessential
= 1;
* Clear all worms and initialize the basic data fields:
* color, origin, size, liberties
* This is a substep of make_worms().
/* Set all worm data fields to 0. */
memset(worm
, 0 , sizeof(worm
));
/* Initialize the worm data for each worm. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
worm
[pos
].origin
= NO_MOVE
;
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!ON_BOARD(pos
) || worm
[pos
].origin
!= NO_MOVE
)
worm
[pos
].color
= board
[pos
];
worm
[pos
].inessential
= 0;
worm
[pos
].invincible
= 0;
worm
[pos
].unconditional_status
= UNKNOWN
;
worm
[pos
].effective_size
= 0.0;
if (IS_STONE(board
[pos
])) {
worm
[pos
].liberties
= countlib(pos
);
worm
[pos
].size
= countstones(pos
);
/* Compute effective size of each worm.
* Effective size is the number of stones in a worm plus half the
* number of empty intersections that are at least as close to this
* worm as to any other worm. This is used to estimate the direct
* territorial value of capturing a worm. Intersections that are
* shared are counted with equal fractional values for each worm.
* We never count intersections further away than distance 3.
* This function is also used to compute arrays with information about
* the distances to worms of both or either color. In the latter case
* we count intersections up to a distance of 5.
compute_effective_worm_sizes()
do_compute_effective_worm_sizes(BLACK
| WHITE
, close_worms
,
do_compute_effective_worm_sizes(BLACK
, close_black_worms
,
number_close_black_worms
, 5);
do_compute_effective_worm_sizes(WHITE
, close_white_worms
,
number_close_white_worms
, 5);
do_compute_effective_worm_sizes(int color
, int (*cw
)[MAX_CLOSE_WORMS
],
int *ncw
, int max_distance
)
/* Distance to closest worm, -1 means unassigned, 0 that there is
* a stone at the location, 1 a liberty of a stone, and so on.
/* Pointer to the origin of the closest worms. A very large number of
* worms may potentially be equally close, but no more than
static int worms
[BOARDMAX
][2*(MAX_BOARD
-1)];
int nworms
[BOARDMAX
]; /* number of equally close worms */
int dist
; /* current distance */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
for (k
= 0; k
< 2*(board_size
-1); k
++)
if (board
[pos
] & color
) {
worms
[pos
][0] = worm
[pos
].origin
;
while (found_one
&& dist
<= max_distance
) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!ON_BOARD(pos
) || distance
[pos
] != -1)
continue; /* already claimed */
for (r
= 0; r
< 4; r
++) {
int pos2
= pos
+ delta
[r
];
if (ON_BOARD(pos2
) && distance
[pos2
] == dist
- 1) {
for (k
= 0; k
< nworms
[pos2
]; k
++) {
for (l
= 0; l
< nworms
[pos
]; l
++)
if (worms
[pos
][l
] == worms
[pos2
][k
]) {
ASSERT1(nworms
[pos
] < 2*(board_size
-1), pos
);
worms
[pos
][nworms
[pos
]] = worms
[pos2
][k
];
/* Compute the effective sizes but only when all worms are considered. */
if (color
== (BLACK
| WHITE
)) {
/* Distribute (fractional) contributions to the worms. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
for (k
= 0; k
< nworms
[pos
]; k
++) {
worm
[w
].effective_size
+= 0.5/nworms
[pos
];
worm
[w
].effective_size
+= 1.0;
/* Propagate the effective size values all over the worms. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (IS_STONE(board
[pos
]) && is_worm_origin(pos
, pos
))
/* Fill in the appropriate close_*_worms (cw) and
* number_close_*_worms (ncw) arrays.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (nworms
[pos
] > MAX_CLOSE_WORMS
)
for (k
= 0; k
< ncw
[pos
]; k
++)
cw
[pos
][k
] = worms
[pos
][k
];
/* Identify worms which are unconditionally uncapturable in the
* strongest sense, i.e. even if the opponent is allowed an arbitrary
* number of consecutive moves. Also identify worms which are
* similarly unconditionally dead and empty points which are
* unconditional territory for either player.
compute_unconditional_status()
int unconditional_territory
[BOARDMAX
];
for (color
= WHITE
; color
<= BLACK
; color
++) {
unconditional_life(unconditional_territory
, color
);
find_unconditionally_meaningless_moves(unconditional_territory
, color
);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!ON_BOARD(pos
) || !unconditional_territory
[pos
])
if (board
[pos
] == color
) {
worm
[pos
].unconditional_status
= ALIVE
;
if (unconditional_territory
[pos
] == 1)
worm
[pos
].invincible
= 1;
else if (board
[pos
] == EMPTY
) {
worm
[pos
].unconditional_status
= WHITE_TERRITORY
;
worm
[pos
].unconditional_status
= BLACK_TERRITORY
;
worm
[pos
].unconditional_status
= DEAD
;
* Analyze tactical safety of each worm.
find_worm_attacks_and_defenses()
static int libs
[MAXLIBS
];
/* 1. Start with finding attack points. */
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++) {
if (!IS_STONE(board
[str
]) || !is_worm_origin(str
, str
))
TRACE("considering attack of %1m\n", str
);
/* Initialize all relevant fields at once. */
for (k
= 0; k
< MAX_TACTICAL_POINTS
; k
++) {
worm
[str
].attack_codes
[k
] = 0;
worm
[str
].attack_points
[k
] = 0;
worm
[str
].defense_codes
[k
] = 0;
worm
[str
].defense_points
[k
] = 0;
acode
= attack(str
, &attack_point
);
DEBUG(DEBUG_WORMS
, "worm at %1m can be attacked at %1m\n",
change_attack(str
, attack_point
, acode
);
/* 2. Use pattern matching to find a few more attacks. */
/* 3. Now find defense moves. */
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++) {
if (!IS_STONE(board
[str
]) || !is_worm_origin(str
, str
))
if (worm
[str
].attack_codes
[0] != 0) {
TRACE("considering defense of %1m\n", str
);
dcode
= find_defense(str
, &defense_point
);
TRACE("worm at %1m can be defended at %1m\n", str
, defense_point
);
if (defense_point
!= NO_MOVE
)
change_defense(str
, defense_point
, dcode
);
/* If the point of attack is not adjacent to the worm,
* it is possible that this is an overlooked point of
* defense, so we try and see if it defends.
attack_point
= worm
[str
].attack_points
[0];
if (!liberty_of_string(attack_point
, str
))
if (trymove(attack_point
, worm
[str
].color
, "make_worms", NO_MOVE
)) {
int acode
= attack(str
, NULL
);
change_defense(str
, attack_point
, REVERSE_RESULT(acode
));
TRACE("worm at %1m can be defended at %1m with code %d\n",
str
, attack_point
, REVERSE_RESULT(acode
));
/* 4. Use pattern matching to find a few more defense moves. */
* 5. Find additional attacks and defenses by testing all immediate
* liberties. Further attacks and defenses are found by pattern
* matching and by trying whether each attack or defense point
* attacks or defends other strings.
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++) {
if (!IS_STONE(color
) || !is_worm_origin(str
, str
))
other
= OTHER_COLOR(color
);
if (worm
[str
].attack_codes
[0] == 0)
/* There is at least one attack on this group. Try the
liberties
= findlib(str
, MAXLIBS
, libs
);
for (k
= 0; k
< liberties
; k
++) {
if (!attack_move_known(pos
, str
)) {
/* Try to attack on the liberty. Don't consider
* send-two-return-one moves.
if (!send_two_return_one(pos
, other
)
&& trymove(pos
, other
, "make_worms", str
)) {
if (board
[str
] == EMPTY
|| attack(str
, NULL
)) {
dcode
= find_defense(str
, NULL
);
change_attack(str
, pos
, REVERSE_RESULT(dcode
));
/* Try to defend at the liberty. */
if (!defense_move_known(pos
, str
)) {
if (worm
[str
].defense_codes
[0] != 0)
if (trymove(pos
, color
, "make_worms", NO_MOVE
)) {
acode
= attack(str
, NULL
);
change_defense(str
, pos
, REVERSE_RESULT(acode
));
* Find moves threatening to attack or save all worms.
static int libs
[MAXLIBS
];
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++) {
if (!IS_STONE(color
) || !is_worm_origin(str
, str
))
/* 1. Start with finding attack threats. */
/* Only try those worms that have no attack. */
if (worm
[str
].attack_codes
[0] == 0) {
attack_threats(str
, MAX_TACTICAL_POINTS
,
worm
[str
].attack_threat_points
,
worm
[str
].attack_threat_codes
);
/* Threaten to attack by saving weak neighbors. */
num_adj
= chainlinks(str
, adjs
);
for (k
= 0; k
< num_adj
; k
++) {
if (worm
[adjs
[k
]].attack_codes
[0] != 0
&& worm
[adjs
[k
]].defense_codes
[0] != 0)
for (r
= 0; r
< MAX_TACTICAL_POINTS
; r
++) {
if (worm
[adjs
[k
]].defense_codes
[r
] == 0)
bb
= worm
[adjs
[k
]].defense_points
[r
];
if (trymove(bb
, other
, "threaten attack", str
,
acode
= attack(str
, NULL
);
change_attack_threat(str
, bb
, acode
);
/* FIXME: Try other moves also (patterns?). */
/* 2. Continue with finding defense threats. */
/* Only try those worms that have an attack. */
if (worm
[str
].attack_codes
[0] != 0
&& worm
[str
].defense_codes
[0] == 0) {
liberties
= findlib(str
, MAXLIBS
, libs
);
for (k
= 0; k
< liberties
; k
++) {
/* Try to threaten on the liberty. */
if (trymove(aa
, color
, "threaten defense", NO_MOVE
)) {
if (attack(str
, NULL
) == WIN
) {
int dcode
= find_defense(str
, NULL
);
change_defense_threat(str
, aa
, dcode
);
/* Try to threaten on second order liberties. */
for (l
= 0; l
< 4; l
++) {
int bb
= libs
[k
] + delta
[l
];
|| liberty_of_string(bb
, str
))
if (trymove(bb
, color
, "threaten defense", str
)) {
if (attack(str
, NULL
) == WIN
) {
int dcode
= find_defense(str
, NULL
);
change_defense_threat(str
, bb
, dcode
);
/* It might be interesting to look for defense threats by
* attacking weak neighbors, similar to threatening attack by
* defending a weak neighbor. However, in this case it seems
* probable that if there is such an attack, it's a real
* defense, not only a threat.
/* FIXME: Try other moves also (patterns?). */
/* find_lunch(str, &worm) looks for a worm adjoining the
* string at (str) which can be easily captured. Whether or not it can
* be defended doesn't matter.
* Returns the location of the string in (*lunch).
find_lunch(int str
, int *lunch
)
ASSERT1(IS_STONE(board
[str
]), str
);
ASSERT1(stackp
== 0, str
);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] != OTHER_COLOR(board
[str
]))
for (k
= 0; k
< 8; k
++) {
int apos
= pos
+ delta
[k
];
if (ON_BOARD(apos
) && is_same_worm(apos
, str
)) {
if (worm
[pos
].attack_codes
[0] != 0 && !is_ko_point(pos
)) {
* If several adjacent lunches are found, we pick the
* juiciest. First maximize cutstone, then minimize liberties.
* We can only do this if the worm data is available,
|| worm
[pos
].cutstone
> worm
[*lunch
].cutstone
|| (worm
[pos
].cutstone
== worm
[*lunch
].cutstone
&& worm
[pos
].liberties
< worm
[*lunch
].liberties
)) {
*lunch
= worm
[pos
].origin
;
* Test whether two worms are the same. Used by autohelpers.
* Before this function can be called, build_worms must have been run.
is_same_worm(int w1
, int w2
)
return worm
[w1
].origin
== worm
[w2
].origin
;
* Test whether the origin of the worm at (w) is (pos).
is_worm_origin(int w
, int pos
)
return worm
[w
].origin
== pos
;
* change_defense(str, move, dcode) is used to add and remove defense
* points. It can also be used to change the defense code. The meaning
* of the call is that the string (str) can be defended by (move) with
* defense code (dcode). If (dcode) is zero, the move is removed from
* the list of defense moves if it was previously listed.
change_defense(int str
, int move
, int dcode
)
change_tactical_point(str
, move
, dcode
,
worm
[str
].defense_points
, worm
[str
].defense_codes
);
* change_attack(str, move, acode) is used to add and remove attack
* points. It can also be used to change the attack code. The meaning
* of the call is that the string (str) can be attacked by (move) with
* attack code (acode). If (acode) is zero, the move is removed from
* the list of attack moves if it was previously listed.
change_attack(int str
, int move
, int acode
)
DEBUG(DEBUG_WORMS
, "change_attack: %1m %1m %d\n", str
, move
, acode
);
change_tactical_point(str
, move
, acode
,
worm
[str
].attack_points
, worm
[str
].attack_codes
);
* change_defense_threat(str, move, dcode) is used to add and remove
* defense threat points. It can also be used to change the defense
* threat code. The meaning of the call is that the string (str) can
* threaten to be defended by (move) with defense threat code (dcode).
* If (dcode) is zero, the move is removed from the list of defense
* threat moves if it was previously listed.
change_defense_threat(int str
, int move
, int dcode
)
change_tactical_point(str
, move
, dcode
,
worm
[str
].defense_threat_points
,
worm
[str
].defense_threat_codes
);
* change_attack_threat(str, move, acode) is used to add and remove
* attack threat points. It can also be used to change the attack
* threat code. The meaning of the call is that the string (str) can
* threaten to be attacked by (move) with attack threat code (acode).
* If (acode) is zero, the move is removed from the list of attack
* threat moves if it was previously listed.
change_attack_threat(int str
, int move
, int acode
)
change_tactical_point(str
, move
, acode
,
worm
[str
].attack_threat_points
,
worm
[str
].attack_threat_codes
);
/* Check whether (move) is listed as an attack point for (str) and
* return the attack code. If (move) is not listed, return 0.
attack_move_known(int move
, int str
)
return movelist_move_known(move
, MAX_TACTICAL_POINTS
,
/* Check whether (move) is listed as a defense point for (str) and
* return the defense code. If (move) is not listed, return 0.
defense_move_known(int move
, int str
)
return movelist_move_known(move
, MAX_TACTICAL_POINTS
,
worm
[str
].defense_points
,
worm
[str
].defense_codes
);
/* Check whether (move) is listed as an attack threat point for (str)
* and return the attack threat code. If (move) is not listed, return
attack_threat_move_known(int move
, int str
)
return movelist_move_known(move
, MAX_TACTICAL_POINTS
,
worm
[str
].attack_threat_points
,
worm
[str
].attack_threat_codes
);
/* Check whether (move) is listed as a defense threat point for (str)
* and return the defense threat code. If (move) is not listed, return
defense_threat_move_known(int move
, int str
)
return movelist_move_known(move
, MAX_TACTICAL_POINTS
,
worm
[str
].defense_threat_points
,
worm
[str
].defense_threat_codes
);
* This function does the real work for change_attack(),
* change_defense(), change_attack_threat(), and
* change_defense_threat().
change_tactical_point(int str
, int move
, int code
,
int points
[MAX_TACTICAL_POINTS
],
int codes
[MAX_TACTICAL_POINTS
])
ASSERT1(str
== worm
[str
].origin
, str
);
movelist_change_point(move
, code
, MAX_TACTICAL_POINTS
, points
, codes
);
* propagate_worm() takes the worm data at one stone and copies it to
* the remaining members of the worm.
* Even though we don't need to copy all the fields, it's probably
* better to do a structure copy which should compile to a block copy.
int stones
[MAX_BOARD
* MAX_BOARD
];
ASSERT1(IS_STONE(board
[pos
]), pos
);
num_stones
= findstones(pos
, MAX_BOARD
* MAX_BOARD
, stones
);
for (k
= 0; k
< num_stones
; k
++)
worm
[stones
[k
]] = worm
[pos
];
* propagate_worm2() is a relative to propagate_worm() which can be
* used when stackp>0 but not for the initial construction of the
ASSERT1(IS_STONE(worm
[str
].color
), str
);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (board
[pos
] == board
[str
] && is_same_worm(pos
, str
)
/* Report all known attack, defense, attack threat, and defense threat
* moves. But limit this to the moves which can be made by (color).
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!ON_BOARD(pos
) || board
[pos
] == EMPTY
)
if (!is_worm_origin(pos
, pos
))
if (board
[pos
] == OTHER_COLOR(color
)) {
for (k
= 0; k
< MAX_TACTICAL_POINTS
; k
++) {
if (worm
[pos
].attack_codes
[k
] != 0)
add_attack_move(worm
[pos
].attack_points
[k
], pos
,
worm
[pos
].attack_codes
[k
]);
if (worm
[pos
].attack_threat_codes
[k
] != 0)
add_attack_threat_move(worm
[pos
].attack_threat_points
[k
], pos
,
worm
[pos
].attack_threat_codes
[k
]);
if (board
[pos
] == color
) {
for (k
= 0; k
< MAX_TACTICAL_POINTS
; k
++) {
if (worm
[pos
].defense_codes
[k
] != 0)
add_defense_move(worm
[pos
].defense_points
[k
], pos
,
worm
[pos
].defense_codes
[k
]);
if (worm
[pos
].defense_threat_codes
[k
] != 0)
add_defense_threat_move(worm
[pos
].defense_threat_points
[k
], pos
,
worm
[pos
].defense_threat_codes
[k
]);
/* ping_cave(str, *lib1, ...) is applied when (str) points to a string.
* It computes the vector (*lib1, *lib2, *lib3, *lib4),
* where *lib1 is the number of liberties of the string,
* *lib2 is the number of second order liberties (empty vertices
* at distance two) and so forth.
* The definition of liberties of order >1 is adapted to the problem
* of detecting the shape of the surrounding cavity. In particular
* we want to be able to see if a group is loosely surrounded.
* A liberty of order n is an empty space which may be connected
* to the string by placing n stones of the same color on the board,
* but no fewer. The path of connection may pass through an intervening group
* of the same color. The stones placed at distance >1 may not touch a
* group of the opposite color. At the edge, also diagonal neighbors
* count as touching. The path may also not pass through a liberty at distance
* 1 if that liberty is flanked by two stones of the opposing color. This
* reflects the fact that the O stone is blocked from expansion to the
* left by the two X stones in the following situation:
* On the edge, one stone is sufficient to block expansion:
ping_cave(int str
, int *lib1
, int *lib2
, int *lib3
, int *lib4
)
int other
= OTHER_COLOR(color
);
memset(mse
, 0, sizeof(mse
));
/* Find and mark the first order liberties. */
*lib1
= findlib(str
, MAXLIBS
, libs
);
for (k
= 0; k
< *lib1
; k
++)
/* Reset mse at liberties which are flanked by two stones of the
* opposite color, or one stone and the edge.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
&& ((( !ON_BOARD(SOUTH(pos
)) || board
[SOUTH(pos
)] == other
)
&& ( !ON_BOARD(NORTH(pos
)) || board
[NORTH(pos
)] == other
))
|| (( !ON_BOARD(WEST(pos
)) || board
[WEST(pos
)] == other
)
&& (!ON_BOARD(EAST(pos
)) || board
[EAST(pos
)] == other
))))
memset(mrc
, 0, sizeof(mrc
));
ping_recurse(str
, lib2
, mse
, mrc
, color
);
memset(mrc
, 0, sizeof(mrc
));
ping_recurse(str
, lib3
, mse
, mrc
, color
);
memset(mrc
, 0, sizeof(mrc
));
ping_recurse(str
, lib4
, mse
, mrc
, color
);
/* recursive function called by ping_cave */
ping_recurse(int pos
, int *counter
,
int mx
[BOARDMAX
], int mr
[BOARDMAX
],
for (k
= 0; k
< 4; k
++) {
int apos
= pos
+ delta
[k
];
&& !touching(apos
, OTHER_COLOR(color
))) {
for (k
= 0; k
< 4; k
++) {
int apos
= pos
+ delta
[k
];
|| board
[apos
] == color
))
ping_recurse(apos
, counter
, mx
, mr
, color
);
/* touching(pos, color) returns true if the vertex at (pos) is
* touching any stone of (color).
touching(int pos
, int color
)
return (board
[SOUTH(pos
)] == color
|| board
[WEST(pos
)] == color
|| board
[NORTH(pos
)] == color
|| board
[EAST(pos
)] == color
);
/* The GENUS of a string is the number of connected components of
* its complement, minus one. It is an approximation to the number of
memset(mg
, 0, sizeof(mg
));
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
&& (board
[pos
] == EMPTY
|| !is_same_worm(pos
, str
))) {
markcomponent(str
, pos
, mg
);
/* This recursive function marks the component at (pos) of
* the complement of the string with origin (str)
markcomponent(int str
, int pos
, int mg
[BOARDMAX
])
for (k
= 0; k
< 4; k
++) {
int apos
= pos
+ delta
[k
];
&& (board
[apos
] == EMPTY
|| !is_same_worm(apos
, str
)))
markcomponent(str
, apos
, mg
);
/* examine_cavity(pos, *edge), if (pos) is EMPTY, examines the
* cavity at (m, n) and returns its bordercolor,
* which can be BLACK, WHITE or GRAY. The edge parameter is set to the
* number of edge vertices in the cavity.
* If (pos) is nonempty, it returns the same result, imagining
* that the string at (pos) is removed. The edge parameter is
* set to the number of vertices where the cavity meets the
* edge in a point outside the removed string.
examine_cavity(int pos
, int *edge
)
int border_color
= EMPTY
;
memset(ml
, 0, sizeof(ml
));
if (IS_STONE(board
[pos
]))
origin
= find_origin(pos
);
cavity_recurse(pos
, ml
, &border_color
, edge
, origin
);
if (border_color
!= EMPTY
)
/* We should have returned now, unless the board is completely empty.
* Verify that this is the case and then return GRAY.
* Notice that the board appears completely empty if there's only a
* single string and pos points to it.
gg_assert(border_color
== EMPTY
&& stones_on_board(BLACK
| WHITE
) == 0)
&& stones_on_board(BLACK
| WHITE
) == countstones(pos
))));
/* helper function for examine_cavity.
* border_color contains information so far : transitions allowed are
* BLACK/WHITE -> BLACK | WHITE
* mx[pos] is 1 if (pos) has already been visited.
* if (str) points to the origin of a string, it will be ignored.
* On (fully-unwound) exit
* *border_color should be BLACK, WHITE or BLACK | WHITE
* *edge is the count of edge pieces
* *border_color should be EMPTY if and only if the board
* is completely empty or only contains the ignored string.
cavity_recurse(int pos
, int mx
[BOARDMAX
],
int *border_color
, int *edge
, int str
)
ASSERT1(mx
[pos
] == 0, pos
);
if (is_edge_vertex(pos
) && board
[pos
] == EMPTY
)
/* Loop over the four neighbors. */
for (k
= 0; k
< 4; k
++) {
int apos
= pos
+ delta
[k
];
if (ON_BOARD(apos
) && !mx
[apos
]) {
if (board
[apos
] == EMPTY
)
/* Count the neighbor as empty if it is part of the (ai, aj) string. */
if (str
== find_origin(apos
))
*border_color
|= board
[apos
];
cavity_recurse(apos
, mx
, border_color
, edge
, str
);
/* Find attacking moves by pattern matching, for both colors. */
find_attack_patterns(void)
matchpat(attack_callback
, ANCHOR_OTHER
, &attpat_db
, NULL
, NULL
);
/* Try to attack every X string in the pattern, whether there is an attack
* before or not. Only exclude already known attacking moves.
attack_callback(int anchor
, int color
, struct pattern
*pattern
, int ll
,
move
= AFFINE_TRANSFORM(pattern
->move_offset
, ll
, anchor
);
/* If the pattern has a constraint, call the autohelper to see
* if the pattern must be rejected.
if (pattern
->autohelper_flag
& HAVE_CONSTRAINT
) {
if (!pattern
->autohelper(ll
, move
, color
, 0))
/* If the pattern has a helper, call it to see if the pattern must
if (!pattern
->helper(pattern
, ll
, move
, color
)) {
"Attack pattern %s+%d rejected by helper at %1m\n",
pattern
->name
, ll
, move
);
/* Loop through pattern elements in search of X strings to attack. */
for (k
= 0; k
< pattern
->patlen
; ++k
) { /* match each point */
if (pattern
->patn
[k
].att
== ATT_X
) {
/* transform pattern real coordinate */
int pos
= AFFINE_TRANSFORM(pattern
->patn
[k
].offset
, ll
, anchor
);
int str
= worm
[pos
].origin
;
/* A string with 5 liberties or more is considered tactically alive. */
if (attack_move_known(move
, str
))
/* No defenses are known at this time, so defend_code is always 0. */
/* If the string can be attacked but not defended, ignore it. */
if (worm
[str
].attack_codes
[0] == WIN
&& worm
[str
].defense_codes
[0] == 0)
/* FIXME: Don't attack the same string more than once.
* Play (move) and see if there is a defense.
if (trymove(move
, color
, "attack_callback", str
)) {
else if (!attack(str
, NULL
))
dcode
= find_defense(str
, NULL
);
/* Do not pick up suboptimal attacks at this time. Since we
* don't know whether the string can be defended it's quite
* possible that it only has a ko defense and then we would
* risk to find an irrelevant move to attack with ko.
if (dcode
!= WIN
&& REVERSE_RESULT(dcode
) >= worm
[str
].attack_codes
[0]) {
change_attack(str
, move
, REVERSE_RESULT(dcode
));
"Attack pattern %s+%d found attack on %1m at %1m with code %d\n",
pattern
->name
, ll
, str
, move
, REVERSE_RESULT(dcode
));
find_defense_patterns(void)
matchpat(defense_callback
, ANCHOR_COLOR
, &defpat_db
, NULL
, NULL
);
defense_callback(int anchor
, int color
, struct pattern
*pattern
, int ll
,
move
= AFFINE_TRANSFORM(pattern
->move_offset
, ll
, anchor
);
/* If the pattern has a constraint, call the autohelper to see
* if the pattern must be rejected.
if (pattern
->autohelper_flag
& HAVE_CONSTRAINT
) {
if (!pattern
->autohelper(ll
, move
, color
, 0))
/* If the pattern has a helper, call it to see if the pattern must
if (!pattern
->helper(pattern
, ll
, move
, color
)) {
"Defense pattern %s+%d rejected by helper at %1m\n",
pattern
->name
, ll
, move
);
/* Loop through pattern elements in search for O strings to defend. */
for (k
= 0; k
< pattern
->patlen
; ++k
) { /* match each point */
if (pattern
->patn
[k
].att
== ATT_O
) {
/* transform pattern real coordinate */
int pos
= AFFINE_TRANSFORM(pattern
->patn
[k
].offset
, ll
, anchor
);
int str
= worm
[pos
].origin
;
if (worm
[str
].attack_codes
[0] == 0
|| defense_move_known(move
, str
))
/* FIXME: Don't try to defend the same string more than once.
* FIXME: For all attacks on this string, we should test whether
* the proposed move happens to refute the attack.
* Play (move) and see if there is an attack.
if (trymove(move
, color
, "defense_callback", str
)) {
int acode
= attack(str
, NULL
);
if (acode
< worm
[str
].attack_codes
[0]) {
change_defense(str
, move
, REVERSE_RESULT(acode
));
"Defense pattern %s+%d found defense of %1m at %1m with code %d\n",
pattern
->name
, ll
, str
, move
, REVERSE_RESULT(acode
));
get_lively_stones(int color
, signed char safe_stones
[BOARDMAX
])
memset(safe_stones
, 0, BOARDMAX
* sizeof(*safe_stones
));
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (IS_STONE(board
[pos
]) && find_origin(pos
) == pos
) {
if ((stackp
== 0 && worm
[pos
].attack_codes
[0] == 0) || !attack(pos
, NULL
)
&& ((stackp
== 0 && worm
[pos
].defense_codes
[0] != 0)
|| find_defense(pos
, NULL
))))
mark_string(pos
, safe_stones
, 1);
signed char safe_stones
[BOARDMAX
];
get_lively_stones(BLACK
, safe_stones
);
compute_influence(BLACK
, safe_stones
, NULL
, &initial_black_influence
,
NO_MOVE
, "initial black influence");
get_lively_stones(WHITE
, safe_stones
);
compute_influence(WHITE
, safe_stones
, NULL
, &initial_white_influence
,
NO_MOVE
, "initial white influence");
/* ================================================================ */
/* ================================================================ */
/* For use in gdb, print details of the worm at (m, n).
* Add this to your .gdbinit file:
* set ascii_report_worm("$arg0")
* Now 'worm S8' will report the details of the S8 worm.
ascii_report_worm(char *string
)
int pos
= string_to_location(board_size
, string
);
if (board
[pos
] == EMPTY
) {
gprintf("There is no worm at %1m\n", pos
);
gprintf("*** worm at %1m:\n", pos
);
gprintf("color: %s; origin: %1m; size: %d; effective size: %f\n",
(worm
[pos
].color
== WHITE
) ? "White" : "Black",
worm
[pos
].origin
, worm
[pos
].size
, worm
[pos
].effective_size
);
gprintf("liberties: %d order 2 liberties:%d order 3:%d order 4:%d\n",
/* List all attack points. */
if (worm
[pos
].attack_points
[0] == NO_MOVE
)
gprintf("no attack point, ");
gprintf("attack point(s):");
while (worm
[pos
].attack_points
[i
] != NO_MOVE
) {
gprintf(" %1m: %s", worm
[pos
].attack_points
[i
],
result_to_string(worm
[pos
].attack_codes
[i
]));
/* List all defense points. */
if (worm
[pos
].defense_points
[0] == NO_MOVE
)
gprintf("no defense point, ");
gprintf("defense point(s):");
while (worm
[pos
].defense_points
[i
] != NO_MOVE
) {
gprintf(" %1m: %s", worm
[pos
].defense_points
[i
],
result_to_string(worm
[pos
].defense_codes
[i
]));
/* List all attack threat points. */
if (worm
[pos
].attack_threat_points
[0] == NO_MOVE
)
gprintf("no attack threat point, ");
gprintf("attack threat point(s):");
while (worm
[pos
].attack_threat_points
[i
] != NO_MOVE
) {
gprintf(" %1m: %s", worm
[pos
].attack_threat_points
[i
],
result_to_string(worm
[pos
].attack_threat_codes
[i
]));
/* List all defense threat points. */
if (worm
[pos
].defense_threat_points
[0] == NO_MOVE
)
gprintf("no defense threat point, ");
gprintf("defense threat point(s):");
while (worm
[pos
].defense_threat_points
[i
] != NO_MOVE
) {
gprintf(" %1m: %s", worm
[pos
].defense_threat_points
[i
],
result_to_string(worm
[pos
].defense_threat_codes
[i
]));
/* Report lunch if any. */
if (worm
[pos
].lunch
!= NO_MOVE
)
gprintf("lunch at %1m\n", worm
[pos
].lunch
);
gprintf("cutstone: %d, cutstone2: %d\n",
worm
[pos
].cutstone
, worm
[pos
].cutstone2
);
gprintf("genus: %d, ", worm
[pos
].genus
);
if (worm
[pos
].inessential
)
gprintf("inessential: YES, ");
gprintf("inessential: NO, ");
if (worm
[pos
].invincible
)
gprintf("invincible: YES, \n");
gprintf("invincible: NO, \n");
gprintf("unconditional status %s\n",
status_to_string(worm
[pos
].unconditional_status
));