projects / sgk-go / blob
? search:
summary | tags | clone url | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Initial commit of GNU Go v3.8.
[sgk-go] / engine / combination.c
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* 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. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* This file contains functions that deals with threats and,
* especially, combinations of threats.
*/
#include "gnugo.h"
#include <string.h>
#include "liberty.h"
#include "gg_utils.h"
#include "patterns.h"
static void find_double_threats(int color);
/* Generate move reasons for combination attacks and defenses against
* them.
*
* This is one of the move generators called from genmove().
*/
void
combinations(int color)
{
int save_verbose;
int attack_point;
signed char defense_points[BOARDMAX];
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, &attack_point, NULL, save_verbose);
if (aa_val > 0) {
if (save_verbose)
gprintf("Combination attack for %C with size %d found at %1m\n",
color, aa_val, attack_point);
add_my_atari_atari_move(attack_point, aa_val);
}
aa_val = atari_atari(other, &attack_point, defense_points, save_verbose);
if (aa_val > 0) {
int pos;
if (save_verbose)
gprintf("Combination attack for %C with size %d found at %1m\n",
other, aa_val, attack_point);
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (ON_BOARD(pos) && defense_points[pos]) {
add_your_atari_atari_move(pos, aa_val);
if (save_verbose)
gprintf("- defense at %1m\n", pos);
}
}
}
verbose = save_verbose;
}
#define MAX_THREATENED_STRINGS 10 /* Should be enough for one intersection */
static void
find_double_threats(int color)
{
int ii;
int k;
int l;
for (ii = BOARDMIN; ii < BOARDMAX; ii++) {
int num_a_threatened_groups;
int a_threatened_groups[MAX_THREATENED_STRINGS];
#if 0
int num_d_threatened_groups;
int d_threatened_groups[MAX_THREATENED_STRINGS];
#endif
if (!ON_BOARD(ii))
continue;
/* Generate an EITHER_MOVE move reasons for each pair of the
* threatened strings. We must also remove the threats, because
* otherwise we would get followup points for them as well.
*
* 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.
* - 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)) {
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.
*
* The call to attack() is intended to detect the case
* where the move at ii is a snapback capture.
*/
if (board[a_threatened_groups[k]] == EMPTY
|| board[a_threatened_groups[l]] == EMPTY) {
if (!attack(ii, NULL)) {
TRACE("Double threat at %1m, either %1m or %1m attacked.\n",
ii, a_threatened_groups[k], a_threatened_groups[l]);
add_either_move(ii, ATTACK_STRING, a_threatened_groups[k],
ATTACK_STRING, a_threatened_groups[l]);
remove_attack_threat_move(ii, a_threatened_groups[k]);
remove_attack_threat_move(ii, a_threatened_groups[l]);
}
}
else if (!defend_both(a_threatened_groups[k],
a_threatened_groups[l])) {
TRACE("Double threat at %1m, either %1m or %1m attacked.\n",
ii, a_threatened_groups[k], a_threatened_groups[l]);
add_either_move(ii, ATTACK_STRING, a_threatened_groups[k],
ATTACK_STRING, a_threatened_groups[l]);
remove_attack_threat_move(ii, a_threatened_groups[k]);
remove_attack_threat_move(ii, 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
*/
}
/* ================================================================ */
/* Combination attacks */
/* ================================================================ */
/* 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
* string involved individually can be rescued, but nevertheless
* one of them can be caught. The simplest example is a double
* atari. The return value is the size of the smallest opponent
* worm.
*
* One danger with this scheme is that the first atari
* tried might be irrelevant to the actual combination.
* To detect this possibility, once we've found a combination,
* we mark that first move as forbidden, then try again. If
* no combination of the same size or larger turns up, then
* the first move was indeed essential.
*
* For the purpose of the move generation, returns the
* size of the smallest of the worms under attack.
*/
/* Local struct to keep track of atari_atari attack moves and what
* they threat.
*/
#define AA_MAX_TARGETS_PER_MOVE 4
#define MAX_AA_DIST 5
struct aa_move {
int move;
int target[AA_MAX_TARGETS_PER_MOVE];
};
#define AA_MAX_MOVES MAX_BOARD * MAX_BOARD
static int aa_status[BOARDMAX]; /* ALIVE, DEAD or CRITICAL */
static int forbidden[BOARDMAX];
static int aa_values[BOARDMAX];
static void compute_aa_status(int color,
const signed char safe_stones[BOARDMAX]);
static void compute_aa_values(int color);
static int get_aa_status(int pos);
static int do_atari_atari(int color, int *attack_point, int *defense_point,
signed char all_potential_defenses[BOARDMAX],
int last_friendly, int save_verbose, int minsize,
signed char goal[BOARDMAX]);
static int atari_atari_succeeded(int color, int *attack_point,
int *defense_point, int last_friendly,
int save_verbose, int minsize);
static void atari_atari_find_attack_moves(int color, int minsize,
struct aa_move attacks[AA_MAX_MOVES],
signed char goal[BOARDMAX]);
static void atari_atari_attack_patterns(int color, int minsize,
struct aa_move attacks[AA_MAX_MOVES],
signed char goal[BOARDMAX]);
static void atari_atari_attack_callback(int anchor, int color,
struct pattern *pattern,
int ll, void *data);
static int atari_atari_find_defense_moves(int targets[AA_MAX_TARGETS_PER_MOVE],
int moves[AA_MAX_MOVES]);
static int get_aa_value(int str);
static int update_aa_goal(signed char goal[BOARDMAX],
signed char new_goal[BOARDMAX],
int apos, int color);
static void aa_init_moves(struct aa_move attacks[AA_MAX_MOVES]);
static void aa_add_move(struct aa_move attacks[AA_MAX_MOVES],
int move, int target);
static int aa_move_known(struct aa_move attacks[AA_MAX_MOVES],
int move, int target);
static void aa_sort_moves(struct aa_move attacks[AA_MAX_MOVES]);
/* Set to 1 if you want verbose traces from this function. */
int
atari_atari(int color, int *attack_move, signed char defense_moves[BOARDMAX],
int save_verbose)
{
int other = OTHER_COLOR(color);
int apos;
int dpos;
int aa_val;
signed char saved_defense_moves[BOARDMAX];
/* Collect worm statuses of opponent's worms. We need to
* know this because we only want to report unexpected
* results. For example, we do not want to report success
* if we find we can kill a worm which is already dead.
* The worm status of empty points is set to UNKNOWN to signal
* that stones added along the way need special attention.
*/
if (aa_depth < 2)
return 0;
memset(forbidden, 0, sizeof(forbidden));
compute_aa_status(color, NULL);
compute_aa_values(color);
if (defense_moves)
memset(defense_moves, 0, BOARDMAX);
aa_val = do_atari_atari(color, &apos, &dpos, defense_moves, NO_MOVE,
save_verbose, 0, NULL);
if (aa_val == 0)
return 0;
/* We try excluding the first atari found and see if the
* combination still works. Repeat until failure.
*/
while (1) {
int new_aa_val;
if (attack_move)
*attack_move = apos;
forbidden[apos] = 1;
if (defense_moves) {
memcpy(saved_defense_moves, defense_moves, BOARDMAX);
memset(defense_moves, 0, BOARDMAX);
}
new_aa_val = do_atari_atari(color, &apos, &dpos, defense_moves, NO_MOVE,
save_verbose, aa_val, NULL);
/* The last do_atari_atari call fails. When do_atari_atari fails,
* it does not change the value of (apos), so these correspond
* to a move that works and is necessary.
*/
if (new_aa_val == 0)
break;
else
aa_val = new_aa_val;
}
if (defense_moves) {
int pos;
memcpy(defense_moves, saved_defense_moves, BOARDMAX);
/* defense_moves[] contains potential defense moves. Now we
* examine which of them really work.
*/
forbidden[apos] = 0;
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (!ON_BOARD(pos) || !defense_moves[pos])
continue;
if (!trymove(pos, other, "atari_atari", NO_MOVE)) {
defense_moves[pos] = 0;
if (save_verbose)
gprintf("%1m deleted defense point, illegal\n", pos);
continue;
}
if (attack(pos, NULL)) {
defense_moves[pos] = 0;
popgo();
if (save_verbose)
gprintf("%1m deleted defense point, unsafe\n", pos);
continue;
}
if (do_atari_atari(color, &apos, &dpos, NULL, NO_MOVE,
save_verbose, aa_val, NULL) > 0) {
if (save_verbose)
gprintf("%1m deleted defense point, didn't work\n", pos);
defense_moves[pos] = 0;
}
popgo();
}
}
return aa_val;
}
/* Wrapper around atari_atari_blunder_size. Check whether a
* combination attack of size at least minsize appears after move
* at (move) has been made.
* The arrays saved_dragons[] and saved_worms[] should be one for
* stones belonging to dragons or worms respectively, which are
* supposedly saved by (move).
*
* FIXME: We probably want to change the calling convention of this
* function to return all defense moves.
*/
int
atari_atari_confirm_safety(int color, int move, int *defense, int minsize,
const signed char saved_dragons[BOARDMAX],
const signed char saved_worms[BOARDMAX])
{
signed char safe_stones[BOARDMAX];
signed char defense_moves[BOARDMAX];
int pos;
int blunder_size;
mark_safe_stones(color, move, saved_dragons, saved_worms, safe_stones);
blunder_size = atari_atari_blunder_size(color, move, defense_moves,
safe_stones);
if (defense) {
/* Return one arbitrary defense move. */
*defense = NO_MOVE;
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(pos) && defense_moves[pos]) {
*defense = pos;
break;
}
}
return blunder_size >= minsize;
}
/* This function checks whether any new combination attack appears after
* move at (move) has been made, and returns its size (in points).
* safe_stones marks which of our stones are supposedly safe after this move.
*/
int
atari_atari_blunder_size(int color, int move,
signed char defense_moves[BOARDMAX],
const signed char safe_stones[BOARDMAX])
{
int apos;
int defense_point = NO_MOVE;
int aa_val, after_aa_val;
int other = OTHER_COLOR(color);
signed char defense_points[BOARDMAX];
int last_forbidden = NO_MOVE;
/* If aa_depth is too small, we can't see any combination attacks,
* so in this respect the move is safe enough.
*/
if (aa_depth < 2)
return 0;
memset(forbidden, 0, sizeof(forbidden));
memset(defense_points, 0, sizeof(defense_points));
compute_aa_status(other, safe_stones);
compute_aa_values(other);
/* Accept illegal ko capture here. */
if (!tryko(move, color, NULL))
/* Really shouldn't happen. */
abortgo(__FILE__, __LINE__, "trymove", move);
increase_depth_values();
aa_val = do_atari_atari(other, &apos, &defense_point, defense_points,
NO_MOVE, 0, 0, NULL);
after_aa_val = aa_val;
if (aa_val == 0 || defense_point == NO_MOVE) {
/* 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.
*/
popgo();
decrease_depth_values();
return 0;
}
while (aa_val >= after_aa_val && defense_point != NO_MOVE) {
/* Try dropping moves from the combination and see if it still
* works. What we really want is to get the proper defense move
* into (*defense).
*/
forbidden[apos] = 1;
last_forbidden = apos;
aa_val = do_atari_atari(other, &apos, &defense_point, NULL,
NO_MOVE, 0, aa_val, NULL);
}
popgo();
decrease_depth_values();
/* We know that a combination exists, but we don't know if
* the original move at (aa) was really relevant. So we
* try omitting it and see if a combination is still found.
*/
compute_aa_status(other, NULL);
compute_aa_values(other);
forbidden[last_forbidden] = 0;
aa_val = do_atari_atari(other, NULL, NULL, NULL, NO_MOVE, 0, 0, NULL);
if (aa_val >= after_aa_val)
return 0;
/* Try the potential defense moves to see which are effective. */
if (defense_moves) {
int pos;
/* defense_points[] contains potential defense moves. Now we
* examine which of them really work.
*/
/* FIXME: Maybe these should be moved after the tryko() below? */
compute_aa_status(other, safe_stones);
compute_aa_values(other);
memcpy(defense_moves, defense_points, sizeof(defense_points));
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (!ON_BOARD(pos) || !defense_moves[pos] || pos == move)
continue;
if (!trymove(pos, color, "atari_atari", NO_MOVE)) {
defense_moves[pos] = 0;
continue;
}
increase_depth_values();
if (attack(pos, NULL)) {
defense_moves[pos] = 0;
decrease_depth_values();
popgo();
continue;
}
/* Accept illegal ko capture here. */
if (!tryko(move, color, NULL))
/* Really shouldn't happen. */
abortgo(__FILE__, __LINE__, "trymove", move);
increase_depth_values();
if (do_atari_atari(other, &apos, &defense_point, NULL, NO_MOVE,
0, after_aa_val, NULL) >= after_aa_val)
defense_moves[pos] = 0;
decrease_depth_values();
popgo();
decrease_depth_values();
popgo();
}
}
return after_aa_val - aa_val;
}
/* ---------------------------------------------------------------- */
/* Helper functions for atari_atari. */
/* ---------------------------------------------------------------- */
/* Helper function for computing the aa_status for all opponent's strings.
* If safe_stones is given, we just copy the information from there.
* If called at stackp > 0, safe_stones must be provided since the
* dragon_data is not valid then.
*/
static void
compute_aa_status(int color, const signed char safe_stones[BOARDMAX])
{
int other = OTHER_COLOR(color);
int pos;
SGFTree *save_sgf_dumptree = sgf_dumptree;
int save_count_variations = count_variations;
int save_verbose = verbose;
gg_assert(safe_stones || stackp == 0);
sgf_dumptree = NULL;
count_variations = 0;
if (verbose)
verbose--;
/* Collect worm statuses of opponent's worms. We need to
* know this because we only want to report unexpected
* results. For example, we do not want to report success
* if we find we can kill a worm which is already dead.
* The worm status of empty points is set to UNKNOWN to signal
* that stones added along the way need special attention.
*/
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (board[pos] == other) {
if (safe_stones) {
if (safe_stones[pos])
aa_status[pos] = ALIVE;
else
aa_status[pos] = DEAD;
}
else {
if (dragon[pos].status == DEAD)
aa_status[pos] = DEAD;
else if (dragon[pos].status == CRITICAL)
aa_status[pos] = CRITICAL;
else if (worm[pos].attack_codes[0] != 0) {
if (worm[pos].defense_codes[0] != 0)
aa_status[pos] = CRITICAL;
else
aa_status[pos] = DEAD;
}
else
aa_status[pos] = ALIVE;
}
}
else if (ON_BOARD(pos))
aa_status[pos] = UNKNOWN;
}
/* reclassify a worm with 2 liberties as INSUBSTANTIAL if capturing
* it does not result in a live group.
*/
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (board[pos] == other
&& find_origin(pos) == pos
&& countlib(pos) == 2
&& aa_status[pos] == ALIVE) {
int libs[2];
findlib(pos, 2, libs);
/* Don't waste time running owl_substantial() if we can't safely
* atari anyway.
*/
if (is_self_atari(libs[0], color)
&& is_self_atari(libs[1], color))
continue;
if (!owl_substantial(pos)) {
int pos2;
for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++)
if (board[pos2] == other && find_origin(pos2) == pos)
aa_status[pos2] = INSUBSTANTIAL;
}
}
}
if (debug & DEBUG_ATARI_ATARI) {
gprintf("compute_aa_status() for %C\n", color);
gprintf("aa_status: (ALIVE worms not listed)\n");
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (board[pos] == other && is_worm_origin(pos, pos)) {
const char *status = "UNKNOWN (shouldn't happen)";
if (aa_status[pos] == DEAD)
status = "DEAD";
else if (aa_status[pos] == CRITICAL)
status = "CRITICAL";
else if (aa_status[pos] == INSUBSTANTIAL)
status = "INSUBSTANTIAL";
if (aa_status[pos] != ALIVE)
gprintf("%1M: %s\n", pos, status);
}
}
}
sgf_dumptree = save_sgf_dumptree;
count_variations = save_count_variations;
verbose = save_verbose;
}
/* Helper function for retrieving the aa_status for a string. We can't
* 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
* the reading.
*/
static int
get_aa_status(int pos)
{
int stones[MAX_BOARD * MAX_BOARD];
int num_stones;
int k;
if (aa_status[pos] != UNKNOWN)
return aa_status[pos];
num_stones = findstones(pos, MAX_BOARD * MAX_BOARD, stones);
for (k = 0; k < num_stones; k++)
if (aa_status[stones[k]] != UNKNOWN)
return aa_status[stones[k]];
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
* with the forbidden array are not tried. If no move is found,
* the values of *attack_point and *defense_point are not changed.
*
* If not NULL, *attack_point is left pointing to the location of the
* attacking move, and *defense_point points to a move defending the
* combination. In rare cases a defensive move might not be found. If
* a non-static function calling do_atari_atari gets a return value of
* 1 but NO_MOVE as the defense point, this should be treated as
* equivalent to a return value of 0.
*
* The goal array limits where we are allowed to consider threats.
* Only strings for which goal is set to 1 may be threatened. If goal
* is NULL, anything may be attacked. Thus goal is typically NULL when
* do_atari_atari() is called from an external function. After the
* first threat has been made, the goal array is set to one in a
* neighborhood of the move and after subsequent threats it is
* expanded with neighborhoods of those moves. The details of this can
* be found in the function update_aa_goal().
*/
static int
do_atari_atari(int color, int *attack_point, int *defense_point,
signed char all_potential_defenses[BOARDMAX], int last_friendly,
int save_verbose, int minsize, signed char goal[BOARDMAX])
{
int other = OTHER_COLOR(color);
int k;
struct aa_move attacks[AA_MAX_MOVES];
int num_defense_moves;
int defense_moves[AA_MAX_MOVES];
int pos;
SGFTree *save_sgf_dumptree;
int save_count_variations;
if (debug & DEBUG_ATARI_ATARI) {
gprintf("%odo_atari_atari: ");
dump_stack();
gprintf("%oforbidden moves: ");
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(pos) && forbidden[pos])
gprintf("%o%1m ", pos);
gprintf("\n");
gprintf("%ogoal: ");
if (!goal)
gprintf("none");
else {
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(pos) && goal[pos])
gprintf("%o%1m ", pos);
}
gprintf("\n");
}
/* First look for strings adjacent to the last friendly move played
* (or to another stone in the same string) which can be
* unexpectedly attacked. If so, the combination attack
* has succeeded.
*/
if (last_friendly != NO_MOVE) {
int retval;
save_sgf_dumptree = sgf_dumptree;
save_count_variations = count_variations;
sgf_dumptree = NULL;
count_variations = 0;
retval = atari_atari_succeeded(color, attack_point, defense_point,
last_friendly, save_verbose, minsize);
sgf_dumptree = save_sgf_dumptree;
count_variations = save_count_variations;
if (retval != 0) {
if (sgf_dumptree)
/* FIXME: Better message. */
sgftreeAddComment(sgf_dumptree, "attack found");
return retval;
}
}
if (stackp > aa_depth)
return 0;
/* Find attack moves. These are typically ataris but may also be
* more general.
*/
save_sgf_dumptree = sgf_dumptree;
save_count_variations = count_variations;
sgf_dumptree = NULL;
count_variations = 0;
atari_atari_find_attack_moves(color, minsize, attacks, goal);
sgf_dumptree = save_sgf_dumptree;
count_variations = save_count_variations;
/* Try the attacking moves and let the opponent defend. Then call
* ourselves recursively.
*/
for (k = 0; attacks[k].move != NO_MOVE; k++) {
int aa_val;
int str = attacks[k].target[0];
int apos = attacks[k].move;
int bpos;
int r;
if (!trymove(apos, color, "do_atari_atari-A", str))
continue;
if (all_potential_defenses) {
all_potential_defenses[apos] = 1;
if (countlib(apos) <= 2) {
int libs[2];
int num_libs = findlib(apos, 2, libs);
all_potential_defenses[libs[0]] = 1;
if (num_libs == 2)
all_potential_defenses[libs[1]] = 1;
}
}
if (!IS_STONE(board[str])) {
/* Error situation. This could be caused by a wrong matcher status. */
if (save_verbose || (debug & DEBUG_ATARI_ATARI))
gprintf("%oError condition found by atari_atari\n");
popgo();
return 0;
}
/* Try to defend the stone (str) which is threatened. */
aa_val = get_aa_value(str);
/* Pick up defense moves. */
save_sgf_dumptree = sgf_dumptree;
save_count_variations = count_variations;
sgf_dumptree = NULL;
count_variations = 0;
num_defense_moves = atari_atari_find_defense_moves(attacks[k].target,
defense_moves);
sgf_dumptree = save_sgf_dumptree;
count_variations = save_count_variations;
for (r = 0; r < num_defense_moves; r++) {
bpos = defense_moves[r];
if (all_potential_defenses)
all_potential_defenses[bpos] = 1;
if (trymove(bpos, other, "do_atari_atari-B", str)) {
int new_aa_val;
signed char new_goal[BOARDMAX];
/* These moves may have been irrelevant for later
* reading, so in order to avoid horizon problems, we
* need to temporarily increase the depth values.
*/
modify_depth_values(2);
update_aa_goal(goal, new_goal, apos, color);
new_aa_val = do_atari_atari(color, NULL, defense_point,
all_potential_defenses,
apos, save_verbose, minsize, new_goal);
modify_depth_values(-2);
if (new_aa_val < aa_val)
aa_val = new_aa_val;
popgo();
}
/* Defense successful, no need to try any further. */
if (aa_val == 0)
break;
}
/* Undo the attacking move. */
popgo();
if (aa_val == 0)
continue;
/* atari_atari successful */
if (num_defense_moves == 0) {
if (save_verbose || (debug & DEBUG_ATARI_ATARI)) {
gprintf("%oThe worm %1m can be attacked at %1m after ", str, apos);
dump_stack();
}
if (sgf_dumptree)
/* FIXME: Better message. */
sgftreeAddComment(sgf_dumptree, "attack found");
}
if (attack_point)
*attack_point = apos;
if (defense_point) {
save_sgf_dumptree = sgf_dumptree;
save_count_variations = count_variations;
sgf_dumptree = NULL;
count_variations = 0;
if (!find_defense(str, defense_point))
*defense_point = NO_MOVE;
/* If no defense point is known and (apos) is a safe
* move for other, it probably defends the combination.
*/
if ((*defense_point == NO_MOVE || !safe_move(*defense_point, other))
&& safe_move(apos, other))
*defense_point = apos;
sgf_dumptree = save_sgf_dumptree;
count_variations = save_count_variations;
}
DEBUG(DEBUG_ATARI_ATARI, "%oreturn value:%d (%1m)\n", aa_val, str);
return aa_val;
}
/* No atari_atari attack. */
return 0;
}
static int
atari_atari_succeeded(int color, int *attack_point, int *defense_point,
int last_friendly, int save_verbose, int minsize)
{
int pos;
int apos;
int other = OTHER_COLOR(color);
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (board[pos] != other)
continue;
if (pos != find_origin(pos))
continue;
if (minsize > 0
&& get_aa_value(pos) < minsize)
continue;
if (get_aa_status(pos) != ALIVE)
continue;
if (board[last_friendly] != EMPTY
&& !adjacent_strings(last_friendly, pos))
continue;
if (board[last_friendly] == EMPTY
&& !liberty_of_string(last_friendly, pos))
continue;
if (debug & DEBUG_ATARI_ATARI)
gprintf("Considering attack of %1m. depth = %d.\n", pos, depth);
if (attack(pos, &apos) && !forbidden[apos]) {
if (save_verbose || (debug & DEBUG_ATARI_ATARI)) {
gprintf("%oThe worm %1m can be attacked at %1m after ", pos, apos);
dump_stack();
}
if (attack_point)
*attack_point = apos;
/* We look for a move defending the combination.
* Normally this is found by find_defense but failing
* that, if the attacking move is a safe move for color,
* it probably defends.
*/
if (defense_point) {
if (!find_defense(pos, defense_point)) {
if (safe_move(apos, other))
*defense_point = apos;
else
*defense_point = NO_MOVE;
}
}
DEBUG(DEBUG_ATARI_ATARI, "%oreturn value:%d (%1m)\n",
get_aa_value(pos), pos);
return get_aa_value(pos);
}
}
return 0;
}
#define MAX_THREAT_MOVES MAX_TACTICAL_POINTS
static void
atari_atari_find_attack_moves(int color, int minsize,
struct aa_move attacks[AA_MAX_MOVES],
signed char goal[BOARDMAX])
{
int k;
int r;
aa_init_moves(attacks);
atari_atari_attack_patterns(color, minsize, attacks, goal);
/* Sort the attack moves. */
aa_sort_moves(attacks);
if (debug & DEBUG_ATARI_ATARI) {
gprintf("Attack moves:");
for (k = 0; k < AA_MAX_MOVES && attacks[k].move != NO_MOVE; k++) {
gprintf("%o %1m(", attacks[k].move);
for (r = 0; r < AA_MAX_TARGETS_PER_MOVE; r++) {
if (attacks[k].target[r] == NO_MOVE)
break;
gprintf("%o%s%1m", r == 0 ? "" : ",", attacks[k].target[r]);
}
gprintf("%o)");
}
gprintf("%o\n");
}
}
/* FIXME: Move these to a struct and pass to callback through the
* *data parameter.
*/
static int current_minsize;
static struct aa_move *current_attacks;
static int conditional_attack_point[BOARDMAX];
static void
atari_atari_attack_patterns(int color, int minsize,
struct aa_move attacks[AA_MAX_MOVES],
signed char goal[BOARDMAX])
{
signed char revised_goal[BOARDMAX];
current_minsize = minsize;
current_attacks = attacks;
memset(conditional_attack_point, 0, sizeof(conditional_attack_point));
/* If goal is NULL and there are forbidden moves we need to compute
* a new goal around the forbidden moves.
*/
if (goal == NULL && update_aa_goal(goal, revised_goal, NO_MOVE, color))
goal = revised_goal;
#if 0
if (goal != NULL) {
int pos;
gprintf("goal:");
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(pos) && goal[pos])
gprintf("%o %1m", pos);
gprintf("%o\n");
}
#endif
matchpat(atari_atari_attack_callback, color, &aa_attackpat_db, NULL, goal);
}
/* Try to attack every X string in the pattern, whether there is an attack
* before or not. Only exclude already known attacking moves.
*/
static void
atari_atari_attack_callback(int anchor, int color,
struct pattern *pattern, int ll, void *data)
{
int move;
int k;
UNUSED(data);
move = AFFINE_TRANSFORM(pattern->move_offset, ll, anchor);
if (forbidden[move])
return;
/* 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))
return;
/* If the pattern has a helper, call it to see if the pattern must
* be rejected.
*/
if (pattern->helper)
if (!pattern->helper(pattern, ll, move, color))
return;
/* Loop through pattern elements in search of X strings to
* threaten to attack.
*/
for (k = 0; k < pattern->patlen; ++k) { /* match each point */
if (pattern->patn[k].att == ATT_X) {
/* transform pattern real coordinate */
int str = find_origin(AFFINE_TRANSFORM(pattern->patn[k].offset,
ll, anchor));
if (current_minsize > 0
&& get_aa_value(str) < current_minsize)
continue;
if (aa_move_known(current_attacks, move, str))
continue;
if (get_aa_status(str) != ALIVE)
continue;
/* Usually we don't want to play self atari. However, if we
* capture in snapback it's okay. For s class patterns we don't
* have this requirement.
*/
if (!(pattern->class & CLASS_s) && is_self_atari(move, color)) {
if (countlib(str) > 2)
continue;
if (!safe_move(move, color))
continue;
}
/*
* Play (move) and see if there is an attack.
*/
if (trymove(move, color, "attack_callback", str)) {
int acode;
int attack_point = NO_MOVE;
if (!board[str])
acode = WIN;
else
acode = attack(str, &attack_point);
popgo();
if (acode != 0) {
if ((pattern->class & CLASS_c)
&& !aa_move_known(current_attacks, move, NO_MOVE)) {
/* Conditional pattern. */
DEBUG(DEBUG_ATARI_ATARI,
"aa_attack pattern %s+%d (conditional) found threat on %1m at %1m with code %d\n",
pattern->name, ll, str, move, acode);
if (conditional_attack_point[move] == NO_MOVE)
conditional_attack_point[move] = str;
else if (conditional_attack_point[move] != str) {
aa_add_move(current_attacks, move,
conditional_attack_point[move]);
aa_add_move(current_attacks, move, str);
}
}
else {
aa_add_move(current_attacks, move, str);
DEBUG(DEBUG_ATARI_ATARI,
"aa_attack pattern %s+%d found threat on %1m at %1m with code %d\n",
pattern->name, ll, str, move, acode);
}
}
}
}
}
}
static int
atari_atari_find_defense_moves(int targets[AA_MAX_TARGETS_PER_MOVE],
int moves[AA_MAX_MOVES])
{
int num_moves = 0;
int move;
int k;
int liberties;
int libs[4];
int neighbors;
int adjs[MAXCHAIN];
int mx[BOARDMAX];
int r, s;
memset(mx, 0, sizeof(mx));
for (r = 0; r < AA_MAX_TARGETS_PER_MOVE && targets[r] != NO_MOVE; r++) {
int str = targets[r];
/* If the attack move happened to remove (str), there's no defense. */
if (board[str] == EMPTY)
continue;
/* Because we know (str) is threatened there is an
* attack and we can be sure find_defense() will give a
* useful defense point if it returns non-zero. Usually we
* would need to call attack_and_defend() to be certain of
* this.
*/
if (!find_defense(str, &move))
continue;
moves[num_moves++] = move;
if (num_moves == AA_MAX_MOVES)
return num_moves;
mx[move] = 1;
/* Consider all moves to attack a neighbor or to play on a liberty. */
liberties = findlib(str, 4, libs);
for (k = 0; k < liberties; k++) {
if (!mx[libs[k]]
&& trymove(libs[k], board[str], "aa_defend-A", str)) {
if (attack(str, NULL) == 0) {
moves[num_moves++] = libs[k];
mx[libs[k]] = 1;
}
popgo();
if (num_moves == AA_MAX_MOVES)
return num_moves;
}
}
neighbors = chainlinks(str, adjs);
for (k = 0; k < neighbors; k++) {
int attack_point;
if (attack(adjs[k], &attack_point) == WIN
&& !mx[attack_point]) {
moves[num_moves++] = attack_point;
if (num_moves == AA_MAX_MOVES)
return num_moves;
mx[attack_point] = 1;
}
/* If the neighbor has at most three liberties, try all of them
* for defense, except self-ataris.
*/
liberties = findlib(adjs[k], 3, libs);
if (liberties <= 3) {
for (s = 0; s < liberties; s++) {
if (!mx[libs[s]]
&& !is_self_atari(libs[s], board[str])
&& trymove(libs[s], board[str], "aa_defend-B", str)) {
if (attack(str, NULL) == 0) {
moves[num_moves++] = libs[s];
mx[libs[s]] = 1;
}
popgo();
if (num_moves == AA_MAX_MOVES)
return num_moves;
}
}
}
}
if (debug & DEBUG_ATARI_ATARI) {
gprintf("Defense moves for %1m:", str);
for (k = 0; k < num_moves; k++)
gprintf("%o %1m", moves[k]);
gprintf("%o\n");
}
}
return num_moves;
}
/* Try to guess the value of the strings. We do this by adding twice
* the number of stones to the number of liberties and second order
* liberties within the moyo around the string. This is of course
* quite crude since it doesn't take into account any strategic
* effects, e.g. a string being cutting stones.
*/
static void
compute_aa_values(int color)
{
int other = OTHER_COLOR(color);
int pos;
int value;
int liberties;
int libs[MAXLIBS];
int mx[BOARDMAX];
int r, k;
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (board[pos] != other
|| pos != find_origin(pos)
|| aa_status[pos] != ALIVE) {
aa_values[pos] = 0;
continue;
}
memset(mx, 0, sizeof(mx));
liberties = findlib(pos, MAXLIBS, libs);
value = 2 * countstones(pos);
for (r = 0; r < liberties; r++) {
if (!mx[libs[r]]
&& (whose_moyo(&initial_black_influence, libs[r]) == other
|| whose_moyo(&initial_white_influence, libs[r]) == other)) {
mx[libs[r]] = 1;
value++;
}
for (k = 0; k < 4; k++) {
int librd = libs[r] + delta[k];
if (!ON_BOARD1(librd) || mx[librd])
continue;
mx[librd] = 1;
if (board[librd] == EMPTY
&& (whose_moyo(&initial_black_influence, librd) == other
|| (whose_moyo(&initial_white_influence, librd) == other)))
value++;
}
}
aa_values[pos] = value;
if (1)
DEBUG(DEBUG_ATARI_ATARI, "aa_value for %1m = %d\n", pos, value);
}
}
/* The aa_value for a string is the sum of the aa_values for all
* included strings in the original position. This will systematically
* overvalue strings which consist of multiple original strings, but
* this is okay since the defender very rarely should defend a string
* first and then sacrifice it later.
*/
static int
get_aa_value(int str)
{
int stones[MAX_BOARD * MAX_BOARD];
int k;
int num_stones = findstones(str, MAX_BOARD * MAX_BOARD, stones);
int value = 0;
for (k = 0; k < num_stones; k++)
value += aa_values[stones[k]];
return value;
}
/* update_aa_goal(goal, new_goal, apos, color) extends the goal array
* with vertices in a neighborhood of apos. The algorithm is that
* starting at apos, a distance measure is computed to nearby
* vertices. The distance increases with one for each step through
* empty vertices and by a liberty depending number when passing
* through strings of the attacked color. Strings with 3 or fewer
* liberties are free to pass through while strings with more
* liberties cost (libs - 3) to pass through. Stones with a distance
* of 5 or less are included in the goal.
*
* Additionally neighborhoods of the moves in the forbidden array are
* included in the goal, to make it possible to limit the goal to a
* specific area from the beginning. This is needed when trying to
* decide which moves are relevant to the combination.
*/
#define ENQUEUE(pos, dist) \
do { \
if ((dist) <= MAX_AA_DIST) { \
if (dists[pos] == 0) { \
queue[queue_end++] = (pos); \
dists[pos] = (dist); \
} \
else if (dists[pos] < (dist)) \
dists[pos] = (dist); \
} \
} while (0);
static int
update_aa_goal(signed char goal[BOARDMAX], signed char new_goal[BOARDMAX],
int apos, int color)
{
int other = OTHER_COLOR(color);
int dists[BOARDMAX];
int queue[MAX_BOARD * MAX_BOARD];
int queue_end = 0;
int k, r, s;
int pos;
if (goal == NULL)
memset(new_goal, 0, BOARDMAX);
else
memcpy(new_goal, goal, BOARDMAX);
memset(dists, 0, sizeof(dists));
if (apos != NO_MOVE) {
dists[apos] = 1;
queue[queue_end++] = apos;
}
#if 0
/* Disabled for now, since it does nothing but break atari_atari:16
* and trevorc:1540. It could be reactivated when the rest of the
* function would be modified in order to garanty that a forbidden
* move is strictly equivalent to a played move in terms of goal
* mapping. I doubt it would be anything worth though...
*/
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (ON_BOARD(pos) && forbidden[pos]) {
dists[pos] = 1;
queue[queue_end++] = pos;
}
}
#endif
if (queue_end == 0)
return 0;
for (r = 0; r < queue_end; r++) {
int smallest_dist = MAX_BOARD * MAX_BOARD;
int best_index = -1;
gg_assert(queue_end < MAX_BOARD * MAX_BOARD);
for (k = r; k < queue_end; k++) {
if (dists[queue[k]] < smallest_dist) {
smallest_dist = dists[queue[k]];
best_index = k;
}
}
if (best_index != r) {
int tmp = queue[r];
queue[r] = queue[best_index];
queue[best_index] = tmp;
}
pos = queue[r];
if (board[pos] == other)
new_goal[pos] = 1;
/* FIXME: We shouldn't let dead opponent stones stop the
* propagation of distance.
*
* As a partial fix we include pos == apos in a test below.
*/
for (k = 0; k < 4; k++) {
int pos2 = pos + delta[k];
if (!ON_BOARD(pos2))
continue;
if ((board[pos] != color || pos == apos) && board[pos2] == EMPTY) {
ENQUEUE(pos2, dists[pos] + 1);
}
else if (board[pos] != other && board[pos2] == other) {
int stones[MAX_BOARD * MAX_BOARD];
int size = findstones(pos2, MAX_BOARD * MAX_BOARD, stones);
int libs = countlib(pos2);
int deltadist = libs - 3;
if (deltadist < 0)
deltadist = 0;
for (s = 0; s < size; s++)
ENQUEUE(stones[s], dists[pos] + deltadist);
}
}
}
return 1;
}
/* Initialize an array with atari_atari attacks. The convention is that
* the array ends when a NO_MOVE is encountered in the move field.
*/
static void
aa_init_moves(struct aa_move attacks[AA_MAX_MOVES])
{
attacks[0].move = NO_MOVE;
}
/* Add an atari_atari attack move to a struct aa_move array. If the
* move already is included in the array, we check whether the target
* also is known for that move and add it if not.
*/
static void
aa_add_move(struct aa_move attacks[AA_MAX_MOVES], int move, int target)
{
int k;
int r;
for (k = 0; k < AA_MAX_MOVES; k++)
if (attacks[k].move == move || attacks[k].move == NO_MOVE)
break;
/* If the array is full, give up. */
if (k == AA_MAX_MOVES)
return;
target = find_origin(target);
/* New move. */
if (attacks[k].move == NO_MOVE) {
attacks[k].move = move;
attacks[k].target[0] = target;
if (AA_MAX_TARGETS_PER_MOVE > 0)
attacks[k].target[1] = NO_MOVE;
if (k < AA_MAX_MOVES - 1)
attacks[k+1].move = NO_MOVE;
return;
}
/* Known move, maybe new target. */
for (r = 0; r < AA_MAX_TARGETS_PER_MOVE; r++)
if (attacks[k].target[r] == target || attacks[k].target[r] == NO_MOVE)
break;
/* No place for more targets. */
if (r == AA_MAX_TARGETS_PER_MOVE)
return;
/* Target known. */
if (attacks[k].target[r] == target)
return;
/* Add target. */
attacks[k].target[r] = target;
if (r < AA_MAX_TARGETS_PER_MOVE - 1)
attacks[k].target[r + 1] = NO_MOVE;
}
/* Check whether an atari_atari attack move is included in an struct
* aa_move array. If target is not NO_MOVE, we also require that the
* target is known for the move.
*/
static int
aa_move_known(struct aa_move attacks[AA_MAX_MOVES], int move, int target)
{
int k;
int r;
for (k = 0; k < AA_MAX_MOVES; k++)
if (attacks[k].move == move || attacks[k].move == NO_MOVE)
break;
/* If the array is full, give up and claim the move to be known. */
if (k == AA_MAX_MOVES)
return 1;
/* Unknown move. */
if (attacks[k].move == NO_MOVE)
return 0;
/* Move known, but how about the target?
* If no target specified, just return 1.
*/
if (target == NO_MOVE)
return 1;
target = find_origin(target);
for (r = 0; r < AA_MAX_TARGETS_PER_MOVE; r++)
if (attacks[k].target[r] == target || attacks[k].target[r] == NO_MOVE)
break;
/* No place for more targets. Give up and claim the target to be known. */
if (r == AA_MAX_TARGETS_PER_MOVE)
return 1;
/* Target known. */
if (attacks[k].target[r] == target)
return 1;
/* Unknown target. */
return 0;
}
/* Auxiliary function for aa_sort_moves(). */
static int
target_comp_func(const void *a, const void *b)
{
int asize = get_aa_value(*((const int *) a));
int bsize = get_aa_value(*((const int *) b));
return asize - bsize;
}
/* Auxiliary function for aa_sort_moves(). */
static int
move_comp_func(const void *a, const void *b)
{
const struct aa_move *aa = a;
const struct aa_move *bb = b;
int asize = get_aa_value(aa->target[0]);
int bsize = get_aa_value(bb->target[0]);
return asize - bsize;
}
/* Sort the attack moves. For each move the targets are sorted in
* decreasing size. Then the moves are sorted with increasing size
* of their first target.
*/
static void
aa_sort_moves(struct aa_move attacks[AA_MAX_MOVES])
{
int k;
int r;
int number_of_attacks;
int number_of_targets;
for (k = 0; k < AA_MAX_MOVES && attacks[k].move != NO_MOVE; k++) {
for (r = 0; r < AA_MAX_TARGETS_PER_MOVE; r++)
if (attacks[k].target[r] == NO_MOVE)
break;
number_of_targets = r;
gg_sort(attacks[k].target, number_of_targets,
sizeof(attacks[k].target[0]), target_comp_func);
}
number_of_attacks = k;
gg_sort(attacks, number_of_attacks, sizeof(attacks[0]), move_comp_func);
}
#if 0
/* Returns true if a move by (color) at (pos) is atari on something.
* Currently unused.
*/
static int
is_atari(int pos, int color)
{
int other = OTHER_COLOR(color);
if (!is_legal(pos, color))
return 0;
if (board[SOUTH(pos)] == other
&& countlib(SOUTH(pos)) == 2)
return 1;
if (board[WEST(pos)] == other
&& countlib(WEST(pos)) == 2)
return 1;
if (board[NORTH(pos)] == other
&& countlib(NORTH(pos)) == 2)
return 1;
if (board[EAST(pos)] == other
&& countlib(EAST(pos)) == 2)
return 1;
return 0;
}
#endif
/*
* Local Variables:
* tab-width: 8
* c-basic-offset: 2
* End:
*/
Fork of GNU Go supporting Xeon Phi coprocessors (and other modifications).