/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* 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 int find_backfilling_move(int move
, int color
, int *backfill_move
,
int forbidden_moves
[BOARDMAX
]);
static int filllib_confirm_safety(int move
, int color
, int *defense_point
);
/* Determine whether a point is adjacent to at least one own string which
living_neighbor(int pos
, int color
)
for (k
= 0; k
< 4; k
++) {
if (board
[pos
+ delta
[k
]] == color
&& dragon
[pos
+ delta
[k
]].status
!= DEAD
)
/* Determine whether (pos) effectively is a black or white point.
* The test for inessentiality is to avoid filling the liberties
* around a killing nakade string.
analyze_neighbor(int pos
, int *found_black
, int *found_white
)
&& living_neighbor(pos
, BLACK
)
&& safe_move(pos
, WHITE
) != WIN
)
&& living_neighbor(pos
, WHITE
)
&& safe_move(pos
, BLACK
) != WIN
)
if (!worm
[pos
].inessential
&& DRAGON2(pos
).safety
!= INESSENTIAL
) {
if (dragon
[pos
].status
== ALIVE
|| dragon
[pos
].status
== UNKNOWN
)
if (!worm
[pos
].inessential
&& DRAGON2(pos
).safety
!= INESSENTIAL
) {
if (dragon
[pos
].status
== ALIVE
|| dragon
[pos
].status
== UNKNOWN
)
/* If no move of value can be found to play, this seeks to fill a
* common liberty, backfilling or back-capturing if necessary. When
* backfilling we take care to start from the right end, in the case
* that several backfilling moves are ultimately necessary.
* If a move for color is found, return 1, otherwise return 0.
* The move is returned in (*move).
fill_liberty(int *move
, int color
)
int other
= OTHER_COLOR(color
);
int potential_color
[BOARDMAX
];
/* We first make a fast scan for intersections which are potential
* candidates for liberty filling. This is not very accurate, but it
* does filter out intersections which could never pass the real
* tests below but might still require a lot of tactical reading in
memset(potential_color
, 0, sizeof(potential_color
));
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!IS_STONE(board
[pos
]))
if (worm
[pos
].inessential
|| DRAGON2(pos
).safety
== INESSENTIAL
)
if (dragon
[pos
].status
!= ALIVE
) {
for (k
= 0; k
< 4; k
++) {
int pos2
= pos
+ delta
[k
];
if (board
[pos2
] == EMPTY
)
potential_color
[pos2
] |= OTHER_COLOR(board
[pos
]);
if (dragon
[pos
].status
!= DEAD
) {
for (k
= 0; k
< 12; k
++) {
if (board
[pos
+ d
] != EMPTY
)
if (board
[pos
+ d
] == EMPTY
)
potential_color
[pos
+ d
] |= board
[pos
];
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
/* It seems we can't trust an empty liberty to be gray-colored
* either as a cave or as a cavity. Instead we look for empty
* intersections with at least one neighbor of each color, where
* dead stones count as enemy stones. We also count empty
* neighbors to either color if the opponent can't play there.
/* Quick rejection based on preliminary test above. */
if (potential_color
[pos
] != GRAY
)
/* Loop over the neighbors. */
for (k
= 0; k
< 4; k
++) {
analyze_neighbor(pos
+ d
, &found_black
, &found_white
);
/* Do we have neighbors of both colors? */
if (!(found_white
&& found_black
))
/* Ok, we wish to play here, but maybe we can't. The following
* 1. Move is legal and safe.
* 2. Move is legal but not safe because it's in the middle of a seki.
* 3. Move is legal but not safe, can be played after backfilling.
* 4. Move is an illegal ko recapture.
* 5. Move is illegal but can be played after back-captures.
* 6. Move would violate confirm_safety.
DEBUG(DEBUG_FILLLIB
, "Filllib: Considering move at %1m.\n", pos
);
/* Legal and tactically safe, play it if it passes
* confirm_safety test, i.e. that it isn't a blunder which
* causes problems for other strings.
if (safe_move(pos
, color
) == WIN
) {
DEBUG(DEBUG_FILLLIB
, "Filllib: Tactically safe.\n");
if (filllib_confirm_safety(pos
, color
, &defense_point
)) {
DEBUG(DEBUG_FILLLIB
, "Filllib: Safety confirmed.\n");
else if (defense_point
!= NO_MOVE
&& is_legal(defense_point
, color
)) {
/* Safety not confirmed because the move at (pos) would set
* up a double threat. (defense_point) is assumed to defend
* FIXME: We should verify that (defense_point) really is effective.
"Filllib: Safety not confirmed, but %1m defends.\n",
/* The move causes problems somewhere else on the board, so
* we have to discard it. If everything works right this
* should not happen at this time.
DEBUG(DEBUG_FILLLIB
, "Filllib: Safety not confirmed, discarded.\n");
TRACE("Warning: Blunder detected in fill_liberty().\n");
/* Try to play the move. */
if (trymove(pos
, color
, "fill_liberty", NO_MOVE
)) {
int forbidden_moves
[BOARDMAX
];
/* Legal, but not safe. Look for backfilling move. */
"Filllib: Legal but not safe, looking for backfilling move.\n");
memset(forbidden_moves
, 0, sizeof(forbidden_moves
));
while (find_backfilling_move(pos
, color
, move
, forbidden_moves
)) {
/* Mark as forbidden in case we need another turn in the loop. */
forbidden_moves
[*move
] = 1;
DEBUG(DEBUG_FILLLIB
, "Filllib: Backfilling move at %1m.\n", *move
);
/* In certain positions it may happen that an illegal move
* is found. This probably only can happen if we try to play
* a move inside a lost semeai. Anyway we should discard the
if (!is_legal(*move
, color
)) {
DEBUG(DEBUG_FILLLIB
, "Filllib: Was illegal, discarded.\n");
/* If the move turns out to be strategically unsafe, or
* setting up a double threat elsewhere, also discard it.
if (!filllib_confirm_safety(*move
, color
, &defense_point
)) {
"Filllib: Safety not confirmed, discarded.\n");
/* No acceptable backfilling move found.
* If we captured some stones, this move should be ok anyway.
if (does_capture_something(pos
, color
)) {
"Filllib: Not tactically safe, but captures stones.\n");
if (!filllib_confirm_safety(pos
, color
, &defense_point
)) {
"Filllib: Safety not confirmed, discarded.\n");
/* Move is illegal. Look for an attack on one of the neighbor
* worms. If found, return that move for back-capture.
DEBUG(DEBUG_FILLLIB
, "Filllib: Illegal, looking for back-capture.\n");
for (k
= 0; k
< 4; k
++) {
if (board
[pos
+ d
] == other
&& worm
[pos
+ d
].attack_codes
[0] == WIN
) {
*move
= worm
[pos
+ d
].attack_points
[0];
DEBUG(DEBUG_FILLLIB
, "Filllib: Found at %1m.\n", *move
);
"Filllib: Nothing found, looking for ko back-capture.\n");
for (k
= 0; k
< 4; k
++) {
if (board
[pos
+ d
] == other
&& worm
[pos
+ d
].attack_codes
[0] != 0
&& is_legal(worm
[pos
+ d
].attack_points
[0], color
)) {
*move
= worm
[pos
+ d
].attack_points
[0];
DEBUG(DEBUG_FILLLIB
, "Filllib: Found at %1m.\n", *move
);
"Filllib: Nothing found, looking for threat to back-capture.\n");
for (k
= 0; k
< 4; k
++) {
if (board
[pos
+ d
] == other
&& worm
[pos
+ d
].attack_codes
[0] != 0) {
/* Just pick some other liberty. */
/* FIXME: Something is odd about this code. */
if (findlib(pos
+ d
, 2, libs
) > 1) {
if (is_legal(libs
[0], color
))
else if (is_legal(libs
[1], color
))
DEBUG(DEBUG_FILLLIB
, "Filllib: Found at %1m.\n", *move
);
DEBUG(DEBUG_FILLLIB
, "Filllib: No move found.\n");
/* The strategy for finding a backfilling move is to first identify
* 1. defends the position obtained after playing (move).
* 2. captures a stone adjacent to our neighbors to (move), before
* Then we check which of these are legal before (move) is played. If
* there is at least one, we take one of these arbitrarily as a
* Now it may happen that (move) still isn't a safe move. In that case
* we recurse to find a new backfilling move. To do things really
* correctly we should also give the opponent the opportunity to keep
* up the balance of the position by letting him do a backfilling move
* of his own. Maybe this could also be arranged by recursing this
* function. Currently we only do a half-hearted attempt to find
* The purpose of the forbidden_moves[] array is to get a new
* backfilling move if the first one later was found to be unsafe,
* like backfilling for J5 at F9 in filllib:45. With F9 marked as
* forbidden the correct move at G9 is found.
static int adjs
[MAXCHAIN
];
static int libs
[MAXLIBS
];
find_backfilling_move(int move
, int color
, int *backfill_move
,
int forbidden_moves
[BOARDMAX
])
int saved_move
= NO_MOVE
;
DEBUG(DEBUG_FILLLIB
, "find_backfilling_move for %C %1m\n", color
, move
);
if (debug
& DEBUG_FILLLIB
)
/* Play (move) and identify all liberties and adjacent strings. */
if (!trymove(move
, color
, "find_backfilling_move", move
))
return 0; /* This shouldn't happen, I believe. */
/* The move wasn't safe, so there must be an attack for the
* opponent. Save it for later use.
acode
= attack(move
, &apos
);
gg_assert(acode
!= 0 && apos
!= NO_MOVE
);
liberties
= findlib(move
, MAXLIBS
, libs
);
neighbors
= chainlinks(move
, adjs
);
/* Remove (move) again. */
/* It's most fun to capture stones. Start by trying to take some
* neighbor off the board. If the attacking move does not directly
* reduce the number of liberties of the attacked string we don't
* trust it but keep it around if we don't find anything else. (See
* filllib:17 for a position where this matters.)
* It is also necessary to take care to first attack the string with
* the fewest liberties, which can probably be removed the fastest.
* See filllib:37 for an example (J5 tactically attacks K7 but the
* FIXME: It seems we have to return immediately when we find an
* attacking move, because recursing for further backfilling might
* lead to moves which complete the capture but cannot be played
* before the attacking move itself. This is not ideal but probably
* In order to avoid losing unnecessary points while capturing dead
* stones, we try first to capture stones in atari, second defending
* at a liberty, and third capture stones with two or more
* liberties. See filllib:43 for a position where capturing dead
* stones (B10 or C8) loses a point compared to defending at a
for (opponent_libs
= 1; opponent_libs
<= 1; opponent_libs
++) {
for (k
= 0; k
< neighbors
; k
++) {
if (opponent_libs
< 5 && countlib(adjs
[k
]) != opponent_libs
)
if (attack(adjs
[k
], &bpos
) == WIN
) {
if (forbidden_moves
[bpos
])
if (liberty_of_string(bpos
, adjs
[k
])) {
/* Otherwise look for a safe move at a liberty. */
for (k
= 0; k
< liberties
; k
++) {
if (!forbidden_moves
[libs
[k
]] && safe_move(libs
[k
], color
) == WIN
) {
*backfill_move
= libs
[k
];
for (opponent_libs
= 2; opponent_libs
<= 5; opponent_libs
++) {
for (k
= 0; k
< neighbors
; k
++) {
if (opponent_libs
< 5 && countlib(adjs
[k
]) != opponent_libs
)
if (attack(adjs
[k
], &bpos
) == WIN
) {
if (forbidden_moves
[bpos
])
if (liberty_of_string(bpos
, adjs
[k
])) {
/* If no luck so far, try with superstring liberties. */
trymove(move
, color
, "find_backfilling_move", move
);
find_proper_superstring_liberties(move
, &liberties
, libs
, 0);
for (k
= 0; k
< liberties
; k
++) {
if (!forbidden_moves
[libs
[k
]] && safe_move(libs
[k
], color
) == WIN
) {
*backfill_move
= libs
[k
];
/* If no luck so far, try attacking superstring neighbors. */
trymove(move
, color
, "find_backfilling_move", move
);
superstring_chainlinks(move
, &neighbors
, adjs
, 4);
for (k
= 0; k
< neighbors
; k
++) {
if (attack(adjs
[k
], &bpos
) == WIN
) {
if (!forbidden_moves
[bpos
] && liberty_of_string(bpos
, adjs
[k
])) {
ASSERT1(!forbidden_moves
[*backfill_move
], *backfill_move
);
if (!trymove(*backfill_move
, color
, "find_backfilling_move", move
))
return 0; /* This really shouldn't happen. */
/* Allow opponent to get a move in here. */
if (trymove(apos
, OTHER_COLOR(color
), "find_backfilling_move", move
))
/* If still not safe, recurse to find a new backfilling move. */
if (safe_move(move
, color
) == WIN
)
success
= find_backfilling_move(move
, color
, backfill_move
,
/* Pop move(s) and return. */
if (!success
&& saved_move
!= NO_MOVE
) {
ASSERT1(!forbidden_moves
[saved_move
], saved_move
);
*backfill_move
= saved_move
;
*backfill_move
= NO_MOVE
;
/* Confirm that (move) is a safe move for color. In addition to
* calling the global confirm_safety(), this function also calls the
* owl code to verify the strategical viability of the move.
filllib_confirm_safety(int move
, int color
, int *defense_point
)
gg_assert(defense_point
!= NULL
);
*defense_point
= NO_MOVE
;
/* Before we can call the owl code, we need to find a neighbor of
if (board
[move
+ delta
[k
]] == color
) {
/* If none found, look for a neighbor of an attacked adjacent string. */
for (k
= 0; k
< 4; k
++) {
int pos2
= move
+ delta
[k
];
if (board
[pos2
] == OTHER_COLOR(color
)
&& !play_attack_defend_n(color
, 0, 1, move
, pos2
)) {
adj
= chainlinks(pos2
, adjs
);
/* It seems unlikely that we would ever get no adjacent strings
* here, but if it should happen we simply give up and say the
/* Next attempt are diagonal neighbors. */
if (board
[move
+ delta
[k
]] == color
) {
/* And two steps away. */
if (board
[move
+ 2 * delta
[k
]] == color
) {
apos
= move
+ 2 * delta
[k
];
/* We should have found something by now. If not something's
* probably broken elsewhere. Declare the move unsafe if it happens.
/* Ask the owl code whether this move is strategically viable. */
if (!owl_does_defend(move
, apos
, NULL
))
return confirm_safety(move
, color
, defense_point
, NULL
);