/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* 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. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* If nonzero, attack() and find_defense() write all results to
* stderr. Use this to if you have deviations in results, but cannot
* find where they come from.
* Redirect results to a file. Take dumps of two versions and
* (assuming GNU tools) do `sort -t= -s' on both. Then join the
* join -t= sorted-first-dump sorted-second-dump \
* | sed -e "s/^[^=]\+=\([^=]\+\)=\1$//" | tr -s "\n" | tr = "\t" \
* to get a nice list of deviations. This is only meaningful if you
* dump results of a single test (or at least tests originating at a
#define DUMP_ALL_RESULTS 0
/* Size of array where candidate moves are stored. */
/* Please notice that message had better be a fixed string. Only the
* pointer to it is saved and there is no attempt to free up any
#define ADD_CANDIDATE_MOVE(move, this_score, moves, this_message) \
for (u = 0; u < (moves).num; u++) \
if ((moves).pos[u] == (move)) { \
(moves).score[u] += this_score; \
if ((u == (moves).num) && ((moves).num < MAX_MOVES)) { \
(moves).pos[(moves).num] = move; \
(moves).score[(moves).num] = this_score; \
(moves).message[(moves).num] = this_message; \
#define REMOVE_CANDIDATE_MOVE(move, moves) \
for (u = (moves).num_tried; u < (moves).num; u++) { \
if ((moves).pos[u] == (move)) { \
(moves).pos[u] = (moves).pos[(moves).num - 1]; \
(moves).score[u] = (moves).score[(moves).num - 1]; \
(moves).message[u] = (moves).message[(moves).num - 1]; \
/* This macro checks whether the reported result is a loss, so we have won
* and can exit, or else if it is the best result so far.
* Note that SGFTRACE must have been setup.
#define CHECK_RESULT(savecode, savemove, code, move_pos, move_ptr, \
*(move_ptr) = (move_pos); \
SGFTRACE(move_pos, WIN, trace_message); \
else if (REVERSE_RESULT(code) > savecode) { \
savecode = REVERSE_RESULT(code); \
/* Reverse of CHECK_RESULT, for results passed from a helper function. */
#define CHECK_RESULT_UNREVERSED(savecode, savemove, code, move_pos, \
move_ptr, trace_message) \
CHECK_RESULT(savecode, savemove, REVERSE_RESULT(code), move_pos, \
#define RETURN_RESULT(savecode, savemove, move_ptr, trace_message) \
*(move_ptr) = (savemove); \
SGFTRACE(savemove, savecode, trace_message); \
/* Play a collected batch of moves and see if any of them works. This
#define DEFEND_TRY_MOVES(no_deep_branching, attack_hint) \
for (k = moves.num_tried; k < moves.num; k++) { \
int dpos = moves.pos[k]; \
if (komaster_trymove(dpos, color, moves.message[k], str, &ko_move,\
stackp <= ko_depth && savecode == 0)) { \
int acode = do_attack(str, (attack_hint)); \
CHECK_RESULT(savecode, savemove, acode, dpos, move, \
if ((no_deep_branching) && stackp >= branch_depth) \
RETURN_RESULT(savecode, savemove, move, "branching limit"); \
moves.num_tried = moves.num; \
/* Attack version of the macro above. This one is a bit more
* complicated, because when defender fails to defend, attacker has to
* prove that he can capture the string before claiming victory.
#define ATTACK_TRY_MOVES(no_deep_branching, defense_hint) \
for (k = moves.num_tried; k < moves.num; k++) { \
int apos = moves.pos[k]; \
if ((board_ko_pos != NO_MOVE || !send_two_return_one(apos, other))\
&& komaster_trymove(apos, other, moves.message[k], \
stackp <= ko_depth && savecode == 0)) { \
int dcode = do_find_defense(str, (defense_hint)); \
if (REVERSE_RESULT(dcode) > savecode \
&& do_attack(str, NULL)) { \
RETURN_RESULT(WIN, apos, move, "attack effective"); \
savecode = REVERSE_RESULT(dcode); \
if ((no_deep_branching) && stackp >= branch_depth) \
RETURN_RESULT(savecode, savemove, move, "branching limit"); \
moves.num_tried = moves.num; \
const char *message
[MAX_MOVES
];
* The functions in reading.c are used to read whether groups
* can be captured or not. See the Texinfo documentation
* (Reading) for more information.
* NULL POINTERS: Many functions in this file can use pointers
* to return the locations of recommended plays. These can be
* set NULL in which case these values are not returned.
static int do_find_defense(int str
, int *move
);
static int defend1(int str
, int *move
);
static int defend2(int str
, int *move
);
static int defend3(int str
, int *move
);
static int defend4(int str
, int *move
);
static void special_rescue_moves(int str
, int lib
,
struct reading_moves
*moves
);
static void bamboo_rescue_moves(int str
, int num_libs
, int libs
[],
struct reading_moves
*moves
);
static void special_rescue2_moves(int str
, int libs
[2],
struct reading_moves
*moves
);
static void special_rescue3_moves(int str
, int libs
[3],
struct reading_moves
*moves
);
static void special_rescue4_moves(int str
, int libs
[2],
struct reading_moves
*moves
);
static void hane_rescue_moves(int str
, int libs
[4],
struct reading_moves
*moves
);
static void special_rescue5_moves(int str
, int libs
[3],
struct reading_moves
*moves
);
static void special_rescue6_moves(int str
, int libs
[3],
struct reading_moves
*moves
);
static void set_up_snapback_moves(int str
, int lib
,
struct reading_moves
*moves
);
static void edge_clamp_moves(int str
, struct reading_moves
*moves
);
static int do_attack(int str
, int *move
);
static int attack1(int str
, int *move
);
static int attack2(int str
, int *move
);
static int attack3(int str
, int *move
);
static int attack4(int str
, int *move
);
static void find_cap_moves(int str
, struct reading_moves
*moves
);
static void special_attack2_moves(int str
, int libs
[2],
struct reading_moves
*moves
);
static void special_attack3_moves(int str
, int libs
[2],
struct reading_moves
*moves
);
static void special_attack4_moves(int str
, int libs
[2],
struct reading_moves
*moves
);
static void draw_back_moves(int str
, struct reading_moves
*moves
);
static void edge_closing_backfill_moves(int str
, int apos
,
struct reading_moves
*moves
);
static void edge_block_moves(int str
, int apos
,
struct reading_moves
*moves
);
static void propose_edge_moves(int str
, int *libs
, int liberties
,
struct reading_moves
*moves
, int color
);
static void break_chain_moves(int str
, struct reading_moves
*moves
);
static int defend_secondary_chain1_moves(int str
, struct reading_moves
*moves
,
static void defend_secondary_chain2_moves(int str
, struct reading_moves
*moves
,
static void break_chain2_efficient_moves(int str
,
struct reading_moves
*moves
);
static void do_find_break_chain2_efficient_moves(int str
, int adj
,
struct reading_moves
*moves
);
static void break_chain2_moves(int str
, struct reading_moves
*moves
,
int require_safe
, int be_aggressive
);
static void break_chain2_defense_moves(int str
, struct reading_moves
*moves
,
static void break_chain3_moves(int str
, struct reading_moves
*moves
,
static void break_chain4_moves(int str
, struct reading_moves
*moves
,
static void superstring_moves(int str
, struct reading_moves
*moves
,
int liberty_cap
, int does_attack
);
static void squeeze_moves(int str
, struct reading_moves
*moves
);
static void superstring_break_chain_moves(int str
, int liberty_cap
,
struct reading_moves
*moves
);
static void double_atari_chain2_moves(int str
,
struct reading_moves
*moves
,
int generate_more_moves
);
static void order_moves(int str
, struct reading_moves
*moves
,
int color
, const char *funcname
, int killer
);
static int simple_ladder_defend(int str
, int *move
);
static int in_list(int move
, int num_moves
, int *moves
);
static int reading_node_counter
= 0;
static int nodes_when_called
= 0;
/* ================================================================ */
/* ================================================================ */
* These functions define goals for the reading process. They use
* the rest of the reading machinery to evaluate whether the goal
* The simplest goals are defined by attack() and find_defense(),
* namely to see if it is possible to capture or defend a single
* string. More complex goals are defined by e.g. attack_either()
* The functions in this section and the next are the only ones which are
* callable from outside this file.
/* attack(str, *move) determines if the string at (str) can be
* captured, and if so, (*move) returns the attacking move, unless
* (move) is a null pointer. Use a null pointer if you are interested
* in the result of the attack but not the attacking move itself.
* Return WIN if the attack succeeds unconditionally, 0 if it doesn't.
* Returns KO_A or KO_B if the result depends on ko:
* - Returns KO_A if the attack succeeds provided attacker is willing to
* ignore any ko threat (the attacker makes the first ko capture).
* - Returns KO_B if attack succeeds provided attacker has a ko threat
* which must be answered (the defender makes the first ko capture).
attack(int str
, int *move
)
int liberties
= countlib(str
);
nodes_when_called
= reading_node_counter
;
/* Don't even spend time looking in the cache if there are more than
* enough liberties. We need this before the persistent cache lookup
* to avoid results inconsistent with find_defense().
|| (liberties
== 4 && stackp
> fourlib_depth
)
|| (liberties
== 3 && stackp
> depth
))
origin
= find_origin(str
);
if (search_persistent_reading_cache(ATTACK
, origin
, &result
, &the_move
)) {
memset(shadow
, 0, sizeof(shadow
));
result
= do_attack(str
, &the_move
);
nodes
= reading_node_counter
- nodes_when_called
;
if (debug
& DEBUG_READING_PERFORMANCE
) {
if (reading_node_counter
- nodes_when_called
>= MIN_READING_NODES_TO_REPORT
) {
gprintf("%oattack %1m(%1m) = %d %1M, %d nodes ", str
, origin
, result
,
gprintf("%oattack %1m(%1m) = %d, %d nodes ", str
, origin
, result
,
store_persistent_reading_cache(ATTACK
, origin
, result
, the_move
, nodes
);
gprintf("%oattack %1m (%d)=%d %1m\n", str
, depth
, result
, the_move
);
/* find_defense(str, *move) attempts to find a move that will save
* the string at (str). It returns WIN if such a move is found, with
* (*move) the location of the saving move, unless (move) is a
* null pointer. It is not checked that tenuki defends, so this may
* give an erroneous answer if !attack(str).
* Returns KO_A or KO_B if the result depends on ko. Returns KO_A if the
* string can be defended provided the defender is willing to ignore
* any ko threat. Returns KO_B if the defender wins by having a ko threat
* which must be answered.
find_defense(int str
, int *move
)
int liberties
= countlib(str
);
nodes_when_called
= reading_node_counter
;
/* Don't even spend time looking in the cache if there are more than
|| (liberties
== 4 && stackp
> fourlib_depth
)) {
origin
= find_origin(str
);
if (search_persistent_reading_cache(FIND_DEFENSE
, origin
,
memset(shadow
, 0, sizeof(shadow
));
result
= do_find_defense(str
, &the_move
);
nodes
= reading_node_counter
- nodes_when_called
;
if (debug
& DEBUG_READING_PERFORMANCE
) {
if (reading_node_counter
- nodes_when_called
>= MIN_READING_NODES_TO_REPORT
) {
gprintf("%odefend %1m(%1m) = %d %1M, %d nodes ", str
, origin
, result
,
gprintf("%odefend %1m(%1m) = %d, %d nodes ", str
, origin
, result
,
store_persistent_reading_cache(FIND_DEFENSE
, origin
, result
,
gprintf("%odefend %1m (%d)=%d %1m\n", str
, depth
, result
, the_move
);
/* attack_and_defend(str, &acode, &attack_point,
* &dcode, &defense_point)
* is a frontend to the attack() and find_defense() functions, which
* guarantees a consistent result. If a string cannot be attacked, 0
* is returned and acode is 0. If a string can be attacked and
* defended, WIN is returned, acode and dcode are both non-zero, and
* (attack_point), (defense_point) both point to vertices on the board.
* If a string can be attacked but not defended, 0 is again returned,
* acode is non-zero, dcode is 0, and (attack_point) points to a vertex
* This function in particular guarantees that if there is an attack,
* it will never return (defense_point) = NO_MOVE, which means the string is
* safe without defense. Separate calls to attack() and find_defense()
* may occasionally give this result, due to irregularities introduced
* by the persistent reading cache.
attack_and_defend(int str
,
int *attack_code
, int *attack_point
,
int *defend_code
, int *defense_point
)
acode
= attack(str
, &apos
);
dcode
= find_defense(str
, &dpos
);
ASSERT1(!(acode
!= 0 && dcode
== WIN
&& dpos
== NO_MOVE
), str
);
return acode
!= 0 && dcode
!= 0;
* attack_either(astr, bstr) returns true if there is a move which
* guarantees that at least one of the strings (astr) and (bstr)
* can be captured. A typical application for this is in connection
* patterns, where after a cut it suffices to capture one of the cutting
* FIXME: The current implementation only looks for uncoordinated
* attacks. This is insufficient to find double ataris or
* moves such as 'a' in positions like
* where neither of the threatened X stones can be captured right
* out. Still either can be captured by a move down to a.
attack_either(int astr
, int bstr
)
ASSERT1(IS_STONE(color
) , astr
);
ASSERT1(color
== board
[bstr
], bstr
);
/* Start by attacking the string with the fewest liberties. On
* average this seems to be slightly more efficient.
if (countlib(astr
) > countlib(bstr
)) {
asuccess
= attack(astr
, NULL
);
bsuccess
= attack(bstr
, NULL
);
if (asuccess
|| bsuccess
) {
return (asuccess
> bsuccess
) ? asuccess
: bsuccess
;
/* Try (a little) harder */
int alib
= findlib(astr
, 2, alibs
);
int other
= OTHER_COLOR(color
);
/* Let's just try the case where the group with the fewest liberties
* has only 2, and try each atari in turn.
if (trymove(alibs
[0], other
, "attack_either-A", astr
)) {
defended0
= defend_both(astr
, bstr
);
&& trymove(alibs
[1], other
, "attack_either-B", astr
)) {
defended1
= defend_both(astr
, bstr
);
/* The second string is possibly also short in liberties.
* Let's try to improve the result.
if (defended0
> 0 && defended1
> 0
&& findlib(bstr
, 2, blibs
) == 2) {
defended0
= gg_min(defended0
, defended1
);
/* We may get here even if alib==1, in case there is a snapback.
* To avoid referencing uninitialized memory in this case we
* explicitly set alibs[1] to NO_MOVE.
if (blibs
[0] != alibs
[0] && blibs
[0] != alibs
[1]
&& trymove(blibs
[0], other
, "attack_either-C", bstr
)) {
int defended
= defend_both(astr
, bstr
);
defended0
= gg_min(defended0
, defended
);
&& blibs
[1] != alibs
[0] && blibs
[1] != alibs
[1]
&& trymove(blibs
[1], other
, "attack_either-D", bstr
)) {
int defended
= defend_both(astr
, bstr
);
defended1
= gg_min(defended1
, defended
);
return REVERSE_RESULT(gg_min(defended0
, defended1
));
* defend_both(astr, bstr) returns true if both the strings (astr)
* and (bstr) can be defended simultaneously or if there is no attack.
* A typical application for this is in connection patterns, where
* after a cut it's necessary to defend both cutting stones.
* FIXME: The current implementation only makes halfhearted
* attempts to find coordinated defense moves. A proper implementation
* would require some serious reading.
defend_both(int astr
, int bstr
)
ASSERT1(IS_STONE(color
) , astr
);
ASSERT1(color
== board
[bstr
], bstr
);
/* This probably helps here too...
if (countlib(astr
) > countlib(bstr
)) {
attack_and_defend(astr
, &acode
, NULL
, &dcode
, &a_savepos
);
return 0; /* (astr) already lost */
attack_and_defend(bstr
, &acode
, NULL
, &dcode
, &b_savepos
);
return 0; /* (bstr) already lost */
/* Neither string can be attacked or only one of them, in which case
* we have time to save it.
if (!a_threatened
|| !b_threatened
)
/* If both strings are threatened we assume that one will become lost,
* unless find_defense() happened to return the same defense point for
* both (which e.g. may happen if they are in fact the same string).
* This is still a bit too pessimistic, as there may be one move which
* saves both strings. To do this right we should try each move which
* defends either string and see if it also defends the other string.
if (a_savepos
== b_savepos
)
return WIN
; /* Both strings can be attacked but also defended
/* We also try each of the returned defense points and see whether
* the other string can still be attacked. This still gives a
* somewhat pessimistic estimation.
if (trymove(a_savepos
, color
, "defend_both-A", astr
)) {
if (board
[bstr
] && !attack(bstr
, NULL
)) {
if (trymove(b_savepos
, color
, "defend_both-B", bstr
)) {
if (board
[astr
] && !attack(astr
, NULL
)) {
/* The next improvement is to try to attack a common adjacent string. */
neighbors1
= chainlinks(astr
, adjs1
);
neighbors2
= chainlinks(bstr
, adjs2
);
for (r
= 0; r
< neighbors1
; r
++) {
&& (epos
!= b_savepos
)) {
/* Is (epos) also adjacent to (bstr)? */
for (s
= 0; s
< neighbors2
; s
++) {
if (adjs2
[s
] == adjs1
[r
])
continue; /* No, it wasn't. */
if (attack(epos
, &fpos
)) {
if (trymove(fpos
, color
, "defend_both-C", astr
)) {
if (board
[astr
] && board
[bstr
]
&& !attack(bstr
, NULL
)) {
/* Both strings can be attacked but we have only time to defend one. */
* break_through(apos, bpos, cpos) returns WIN if a position can
* succesfully be broken through and CUT if it can be cut. The position
* is assumed to have the shape (the colors may be reversed)
* It is X to move and try to capture at least one of a, b, and c. If
* this succeeds, X is said to have broken through the position.
* Otherwise X may try to cut through the position, which means
* keeping F safe and getting a tactically safe string at either d or
* Important notice: a, b, and c must be given in the correct order.
* FIXME: The reading involved here can most likely be improved.
* FIXME: We need to take ko results properly into account.
break_through_helper(int apos
, int bpos
, int cpos
,
int dpos
, int epos
, int Fpos
,
break_through(int apos
, int bpos
, int cpos
)
int other
= OTHER_COLOR(color
);
/* Basic sanity checking. */
ASSERT1(IS_STONE(color
) , apos
);
ASSERT1(color
== board
[bpos
], bpos
);
ASSERT1(color
== board
[cpos
], cpos
);
/* Construct the rest of the points in the pattern. */
Fpos
= (apos
+ cpos
) / 2; /* F midpoint between a and c. */
dpos
= apos
+ bpos
- Fpos
; /* Use diagonal relation a+b = d+F. */
epos
= bpos
+ cpos
- Fpos
; /* Use diagonal relation b+c = e+F. */
/* More sanity checking. */
ASSERT1(board
[dpos
] == EMPTY
, dpos
);
ASSERT1(board
[epos
] == EMPTY
, epos
);
/* F might already have been captured. (play_break_through_n() can't
if (board
[Fpos
] == EMPTY
)
ASSERT1(board
[Fpos
] == other
, Fpos
);
/* First X tries to play at d. */
success
= break_through_helper(apos
, bpos
, cpos
, dpos
, epos
, Fpos
,
success2
= break_through_helper(cpos
, bpos
, apos
, epos
, dpos
, Fpos
,
/* If we haven't been lucky yet, we might need to start by
* FIXME: The function would probably be considerably faster if we
* start by checking whether F needs defense. Beware of ko potential
if (attack_and_defend(Fpos
, NULL
, NULL
, NULL
, &gpos
)) {
if (trymove(gpos
, other
, "break_through-A", Fpos
)) {
/* Now we let O defend his position by playing either d or e.
* FIXME: There may be other plausible moves too.
if (trymove(dpos
, color
, "break_through-B", Fpos
)) {
/* O connects at d, so X cuts at e. */
if (safe_move(epos
, other
)) {
if (!board
[cpos
] || attack(cpos
, NULL
))
if (success2
> 0 && trymove(epos
, color
, "break_through-C", Fpos
)) {
/* O connects at e, so X cuts at d. */
if (safe_move(dpos
, other
)) {
/* success2 is already WIN or CUT. */
if (board
[apos
] && !attack(apos
, NULL
))
/* Helper function for break_through(). Since we can symmetrically
* start by cutting at d or e, we use the same code for both attacks,
* simply switching positions between the two calls.
break_through_helper(int apos
, int bpos
, int cpos
,
int dpos
, int epos
, int Fpos
,
if (trymove(dpos
, other
, "break_through_helper-A", Fpos
)) {
/* If F can be attacked we can't start in this way. */
if (!attack(Fpos
, NULL
)) {
/* If d is safe too, we have at least managed to break through. */
if (!attack(dpos
, &gpos
))
/* Too bad, d could be attacked. We let O play the attack and
* then try to make a second cut at e. But first we must test if
* O at e is sufficient to capture d.
if (trymove(epos
, color
, "break_through_helper-E", Fpos
)) {
if (!board
[dpos
] || !find_defense(dpos
, NULL
)) {
if (trymove(gpos
, color
, "break_through_helper-F", Fpos
)) {
if (trymove(epos
, other
, "break_through_helper-G", Fpos
)) {
if (!attack(epos
, NULL
)) {
/* Make sure b and c are safe. If not, back up & let O try
* to defend in a different way. */
&& defend_both(bpos
, cpos
)) {
/* Can't do better than CUT. */
/* Lost everything. (Note we ignore ko at the moment.) */
/* Failed to cut at all. */
/* By now, we're sure a cut works, so now we can try
if (!board
[apos
] || !board
[bpos
] || !defend_both(apos
, bpos
))
/* Both a and b could be defended, or didn't need to be.
* Let's see if a move at e is sufficient for O.
if (trymove(epos
, color
, "break_through_helper-B", Fpos
)) {
else if (attack(apos
, NULL
))
/* Let O find a defense and play it. */
if (attack_on_a
|| attack_on_b
) {
if (((attack_on_a
&& find_defense(apos
, &hpos
))
|| (attack_on_b
&& find_defense(bpos
, &hpos
)))
&& trymove(hpos
, color
, "break_through_helper-C", Fpos
)) {
/* Now we make a second cut at e, trying to capture
if (trymove(epos
, other
, "break_through_helper-D", Fpos
)) {
|| !defend_both(bpos
, cpos
))
success
= WIN
; /* This should have been covered by
* defend_both(), so probably unnecessary. */
/* ---------------------------------------------------------------- */
/* ---------------------------------------------------------------- */
/* Return up to max_threats threats to capture the string at str.
* If the string is directly attackable the number of threats
* NOTE: You can call attack_threats with moves[] and codes[]
* already partly filled in. So if you want to get the
* threats from scratch, you have to set them to 0
* FIXME: Shall we report upgrades, like we can capture in ko but
* have a threat to capture unconditionally?
attack_threats(int str
, int max_points
, int moves
[], int codes
[])
ASSERT1(IS_STONE(board
[str
]), str
);
other
= OTHER_COLOR(board
[str
]);
/* Only handle strings with no way to capture immediately.
* For now, we treat ko the same as unconditionally. */
if (attack(str
, NULL
) != 0)
/* This test would seem to be unnecessary since we only threaten
* strings with attack_code == 0, but it turns out that single
* stones with one liberty that can be captured, but come to
* live again in a snap-back get attack_code == 0.
* The test against 6 liberties is just an optimization.
liberties
= findlib(str
, MAXLIBS
, libs
);
if (liberties
> 1 && liberties
< 6) {
for (k
= 0; k
< liberties
; k
++) {
/* Try to threaten on the liberty. */
if (trymove(aa
, other
, "attack_threats-A", str
)) {
int acode
= attack(str
, NULL
);
movelist_change_point(aa
, acode
, max_points
, moves
, codes
);
/* 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
, other
, "attack_threats-B", str
)) {
int acode
= attack(str
, NULL
);
movelist_change_point(bb
, acode
, max_points
, moves
, codes
);
/* Threaten to attack by saving weak neighbors. */
num_adj
= chainlinks(str
, adjs
);
for (k
= 0; k
< num_adj
; k
++) {
int dd
; /* Defense point of weak neighbor. */
attack_and_defend(adjs
[k
], &acode
, NULL
, &dcode
, &dd
);
if (acode
== 0 || dcode
== 0)
/* The strange code using r == -1 below is only avoid duplication
* of the code starting with "if (trymove..)" below.
* If r == -1 and stackp == 0 then use the defense point what we got from
* attack_and_defend above. Otherwise step through all defense points.
for (r
= -1; r
< max_points
; r
++) {
if (worm
[adjs
[k
]].defense_codes
[r
] == 0)
bb
= worm
[adjs
[k
]].defense_points
[r
];
/* Test the move and see if it is a threat. */
if (trymove(bb
, other
, "attack_threats-C", str
)) {
acode
= attack(str
, NULL
);
movelist_change_point(bb
, acode
, max_points
, moves
, codes
);
/* Return actual number of threats found regardless of attack code. */
if (codes
[max_points
- 1] > 0)
for (num_threats
= 0; num_threats
< max_points
; num_threats
++)
if (codes
[num_threats
] == 0)
/* ================================================================ */
/* Defensive functions */
/* ================================================================ */
/* Like find_defense, but takes the komaster argument. If the
* opponent is reading functions will not try
do_find_defense(int str
, int *move
)
SETUP_TRACE_INFO("find_defense", str
);
/* We first check if the number of liberties is larger than four. In
* that case we don't cache the result and to avoid needlessly
* storing the position in the hash table, we must do this test
* before we look for cached results.
liberties
= countlib(str
);
|| (liberties
== 4 && stackp
> fourlib_depth
)
|| (liberties
== 3 && stackp
> depth
)) {
/* No need to cache the result in these cases. */
SGFTRACE(0, WIN
, "too many liberties or stackp > depth");
/* Set "killer move" up. This move (if set) was successful in
* another variation, so it is reasonable to try it now. However,
* we only do this if the string has at least 3 liberties -
* otherwise the situation changes too much from variation to
if (liberties
> 2 && move
)
&& tt_get(&ttable
, FIND_DEFENSE
, str
, NO_MOVE
, depth
- stackp
, NULL
,
&retval
, NULL
, &xpos
) == 2) {
/* Note that if return value is 1 (too small depth), the move will
* still be used for move ordering.
TRACE_CACHED_RESULT(retval
, xpos
);
SGFTRACE(xpos
, retval
, "cached");
dcode
= defend1(str
, &xpos
);
dcode
= defend2(str
, &xpos
);
dcode
= defend3(str
, &xpos
);
dcode
= defend4(str
, &xpos
);
READ_RETURN(FIND_DEFENSE
, str
, depth
- stackp
, move
, xpos
, dcode
);
READ_RETURN0(FIND_DEFENSE
, str
, depth
- stackp
);
/* Determine if a `move' by `color' allows under-the-stones tesuji
* a.k.a. "big snapback". Here is an example:
* Even though the move at '*' allows black to capture four white
* stones, white can later recapture black stones and create a second
* eye. This is very similar to a snapback.
* This function returns true if a move creates a string of with two
* liberties, which can, however, be instantly recaptured by opponent.
* It is actually not required that the move captures something. If
* the caller needs captures, it should check for them itself.
allows_under_the_stones_tesuji(int move
, int color
)
SGFTree
*save_sgf_dumptree
;
int save_count_variations
;
if (accuratelib(move
, color
, 3, NULL
) != 2)
save_sgf_dumptree
= sgf_dumptree
;
save_count_variations
= count_variations
;
if (trymove(move
, color
, "allows_under_the_stones_tesuji", NO_MOVE
)) {
if ((!is_self_atari(libs
[0], color
)
&& accuratelib(libs
[1], OTHER_COLOR(color
), 3, NULL
) <= 2)
|| (!is_self_atari(libs
[1], color
)
&& accuratelib(libs
[0], OTHER_COLOR(color
), 3, NULL
) <= 2))
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* Called by the defendN functions. Don't think too much if there's
* an easy way to get enough liberties.
fast_defense(int str
, int liberties
, int *libs
, int *move
)
int goal_liberties
= (stackp
< fourlib_depth
? 5 : 4);
/* We would like to initialize liberty_mark to -1, but some
* compilers warn, quite correctly, that -1 is not an unsigned
static unsigned liberty_mark
= ~0U;
static unsigned lm
[BOARDMAX
];
ASSERT1(libs
!= NULL
, str
);
ASSERT1(move
!= NULL
, str
);
for (k
= 0; k
< liberties
; k
++) {
/* accuratelib() seems to be more efficient than fastlib() here,
* probably because it catches more cases.
if (accuratelib(libs
[k
], color
, goal_liberties
, NULL
) >= goal_liberties
) {
/* Check the cases where an opponent neighbor string is in
adj
= chainlinks2(str
, adjs
, 1);
for (j
= 0; j
< adj
; j
++) {
int missing
= goal_liberties
- liberties
;
int adj2
, adjs2
[MAXCHAIN
];
int alib
, alibs
[MAXLIBS
];
findlib(adjs
[j
], 1, &lib
);
/* We aren't interested in ko (at this stage). And playing
* our own last liberty to capture is prone to snapbacks,
* so better let the 'normal' reading routines do the job.
if ((liberties
== 1 && lib
== libs
[0]
&& countstones(adjs
[j
]) <= 2)
|| is_ko(lib
, color
, NULL
))
/* Would the capture already gain enough liberties ?
* No need to test the case if the move is one of our liberties,
* it has already been done in the first loop of this function.
num_adjacent_stones
= count_adjacent_stones(adjs
[j
], str
, missing
);
if (!liberty_of_string(lib
, str
)
&& num_adjacent_stones
>= missing
) {
ASSERT1(num_adjacent_stones
>= 1, str
);
/* What is the total number of liberties of the friendly strings around
if (++liberty_mark
== 0) {
memset(lm
, 0, sizeof(lm
));
/* Loop over all neighbors of the lunch. */
adj2
= chainlinks(adjs
[j
], adjs2
);
for (k
= 0; k
< adj2
; k
++) {
/* Loop over all liberties of the neighbor. */
alib
= findlib(adjs2
[k
], MAXLIBS
, alibs
);
for (l
= 0; l
< alib
; l
++) {
if (lm
[alibs
[l
]] != liberty_mark
) {
lm
[alibs
[l
]] = liberty_mark
;
/* The captured string is treated as common liberties, and
* some adjustements are made :
* - we're adding a stone for capturing the lunch (-1)
* - opponent might be able to remove a liberty (-1)
* - and possibly force us to connect (-1)
* - reduce us by one more liberty with a throw-in; this
* is only possible if there is only one adjacent stone in the
* lunch to the string (-1)
* Probably there are more damezumari-type cases, but as a heuristic,
total
+= countstones(adjs
[j
]) - 2;
if (lm
[lib
] == liberty_mark
)
if (num_adjacent_stones
== 1)
if (total
>= goal_liberties
) {
/* One case when this code can give a false defense is an
* under-the-stones tesuji or "big snapback." See reading:199
* for an example. While this position is probably very rare,
* it is nice to make GNU Go understand "neat" tesujis.
if (liberties
== 1 && lib
== libs
[0]
&& allows_under_the_stones_tesuji(lib
, color
)) {
/* This is a bad "fast defense". */
/* If str points to a string with exactly one liberty, defend1
* determines whether it can be saved by extending or capturing
* a boundary chain having one liberty. The function returns WIN if the string
* can be saved, otherwise 0. It returns KO_A or KO_B if it can be saved,
* conditioned on ko. Returns KO_A if it can be saved provided (color) is
* willing to ignore any ko threat. Returns KO_B if it can be saved if (color)
* has a ko threat which must be answered.
* The pair defend1-attack2 call each other recursively to
* read situations such as ladders. They read all ladders to the end.
* If the reading ply (stackp) is deeper than the deep-reading cutoff
* parameter depth, whose default value DEPTH is defined in gnugo.h, then a
* string is assumed alive if it can get 3 liberties. When
* fourlib_depth < stackp < depth, a string is considered alive if it can get
* four liberties. When stackp < fourlib_depth, it is considered alive
* if it can get 5 liberties.
defend1(int str
, int *move
)
int other
= OTHER_COLOR(color
);
struct reading_moves moves
;
SETUP_TRACE_INFO("defend1", str
);
ASSERT1(IS_STONE(board
[str
]), str
);
ASSERT1(countlib(str
) == 1, str
);
/* lib will be the liberty of the string. */
liberties
= findlib(str
, 1, &lib
);
ASSERT1(liberties
== 1, str
);
if (fast_defense(str
, liberties
, &lib
, &xpos
))
RETURN_RESULT(WIN
, xpos
, move
, "fast defense");
/* Collect moves to try in the first batch.
* 1. First order liberty.
* 2. Chain breaking moves.
* 3. Moves to set up a snapback.
moves
.message
[0] = "liberty";
break_chain_moves(str
, &moves
);
set_up_snapback_moves(str
, lib
, &moves
);
order_moves(str
, &moves
, color
, read_function_name
, *move
);
DEFEND_TRY_MOVES(0, NULL
);
/* If the string is a single stone and a capture would give a ko,
* try to defend it with ko by backfilling.
* FIXME: What is an example of this? Is it correct that the
* return value is WIN and not KO_A or KO_B?
if (stackp
<= backfill_depth
&& is_ko(lib
, other
, NULL
)) {
liberties
= approxlib(lib
, color
, 6, libs2
);
for (k
= 0; k
< liberties
; k
++) {
if ((liberties
== 1 || !is_self_atari(apos
, other
))
&& trymove(apos
, color
, "defend1-C", str
)) {
int acode
= do_attack(str
, NULL
);
CHECK_RESULT(savecode
, savemove
, acode
, apos
, move
, "backfilling");
RETURN_RESULT(savecode
, savemove
, move
, "saved move");
/* If str points to a group with two liberties, defend2 determines
* whether the group can be saved by extending, or by capturing part of
* its surrounding chain. A group is considered safe if either part of
* the surrounding chain may be captured, or if it can get 3
* liberties. It is presumed that the opponent could kill if tenuki.
* If both extensions work, it prefers the one which maximizes
* *move returns the move to save the stones.
defend2(int str
, int *move
)
struct reading_moves moves
;
int suggest_move
= NO_MOVE
;
SETUP_TRACE_INFO("defend2", str
);
other
= OTHER_COLOR(color
);
ASSERT1(IS_STONE(board
[str
]), str
);
ASSERT1(countlib(str
) == 2, str
);
liberties
= findlib(str
, 2, libs
);
if (fast_defense(str
, liberties
, libs
, &xpos
))
RETURN_RESULT(WIN
, xpos
, move
, "fast defense");
/* Collect moves to try in the first batch.
* 1. First order liberties.
* 2. Chain breaking moves.
* 3. Second order liberties moving up from first line to second.
/* We don't want to play self-atari liberties, unless the string is a
* single stone (in which case it might be a snapback move). Sacrifices
* might be good moves, but not in tactical reading.
string_size
= countstones(str
);
if (string_size
== 1 || !is_self_atari(libs
[0], color
))
ADD_CANDIDATE_MOVE(libs
[0], 0, moves
, "liberty");
if (string_size
== 1 || !is_self_atari(libs
[1], color
))
ADD_CANDIDATE_MOVE(libs
[1], 0, moves
, "liberty");
break_chain_moves(str
, &moves
);
break_chain2_efficient_moves(str
, &moves
);
propose_edge_moves(str
, libs
, liberties
, &moves
, color
);
edge_clamp_moves(str
, &moves
);
for (k
= 0; k
< liberties
; k
++)
special_rescue_moves(str
, libs
[k
], &moves
);
bamboo_rescue_moves(str
, liberties
, libs
, &moves
);
if (stackp
<= backfill_depth
)
special_rescue2_moves(str
, libs
, &moves
);
order_moves(str
, &moves
, color
, read_function_name
, *move
);
DEFEND_TRY_MOVES(0, &suggest_move
);
/* Look for backfilling moves. */
for (k
= 0; k
< liberties
; k
++) {
if (is_self_atari(libs
[k
], other
)) {
liberties2
= approxlib(libs
[k
], color
, 6, libs2
);
/* Note: liberties2 must be smaller than 5, otherwise libs[k] had been
for (r
= 0; r
< liberties2
; r
++) {
/* If the newly placed stone would be in atari, but not a single
* stone, we don't even try.
if (!is_self_atari(xpos
, color
)
&& has_neighbor(xpos
, color
))
ADD_CANDIDATE_MOVE(xpos
, 0, moves
, "backfill-A");
liberties2
= approxlib(libs
[k
], other
, 3, libs2
);
for (r
= 0; r
< liberties2
; r
++) {
if (!is_self_atari(xpos
, color
))
ADD_CANDIDATE_MOVE(xpos
, 0, moves
, "backfill-B");
special_rescue4_moves(str
, libs
, &moves
);
/* Only order and test the new set of moves. */
order_moves(str
, &moves
, color
, read_function_name
, *move
);
DEFEND_TRY_MOVES(0, &suggest_move
);
/* If we haven't found any useful moves in first batches, be more
* aggressive in break_chain[23]_moves().
be_aggressive
= (moves
.num
== 0);
if (stackp
<= superstring_depth
)
superstring_break_chain_moves(str
, 4, &moves
);
/* If nothing else works, we try playing a liberty of the
if (stackp
<= superstring_depth
) {
superstring_moves(str
, &moves
, 3, 0);
squeeze_moves(str
, &moves
);
break_chain2_defense_moves(str
, &moves
, be_aggressive
);
if (stackp
<= backfill_depth
)
special_rescue5_moves(str
, libs
, &moves
);
if (stackp
<= break_chain_depth
|| (be_aggressive
&& stackp
<= backfill_depth
))
break_chain3_moves(str
, &moves
, be_aggressive
);
if (be_aggressive
&& stackp
<= backfill_depth
)
break_chain4_moves(str
, &moves
, be_aggressive
);
/* Only order and test the new set of moves. */
order_moves(str
, &moves
, color
, read_function_name
, *move
);
DEFEND_TRY_MOVES(0, &suggest_move
);
RETURN_RESULT(savecode
, savemove
, move
, "saved move");
/* defend3(str, *move) attempts to find a move rescuing the
* string at (str) with 3 liberties. If such a move can be found,
* it returns true and the saving move in *move.
defend3(int str
, int *move
)
struct reading_moves moves
;
int suggest_move
= NO_MOVE
;
SETUP_TRACE_INFO("defend3", str
);
ASSERT1(IS_STONE(board
[str
]), str
);
ASSERT1(countlib(str
) == 3, str
);
liberties
= findlib(str
, 3, libs
);
if (fast_defense(str
, liberties
, libs
, &xpos
))
RETURN_RESULT(WIN
, xpos
, move
, "fast defense");
/* Collect moves to try in the first batch.
* 1. First order liberties.
* 2. Chain breaking moves.
* 3. Second order liberties moving up from first line to second.
for (k
= 0; k
< liberties
; k
++) {
moves
.message
[k
] = "liberty";
break_chain_moves(str
, &moves
);
break_chain2_efficient_moves(str
, &moves
);
propose_edge_moves(str
, libs
, liberties
, &moves
, color
);
edge_clamp_moves(str
, &moves
);
if (stackp
<= backfill2_depth
)
hane_rescue_moves(str
, libs
, &moves
);
order_moves(str
, &moves
, color
, read_function_name
, *move
);
DEFEND_TRY_MOVES(1, &suggest_move
);
/* This looks a little too expensive. */
/* Look for backfilling moves. */
if (stackp
<= backfill_depth
) {
int other
= OTHER_COLOR(color
);
for (k
= 0; k
< liberties
; k
++) {
if (is_self_atari(libs
[k
], other
)) {
liberties2
= approxlib(libs
[k
], color
, 6, libs2
);
for (r
= 0; r
< liberties2
; r
++) {
/* Don't reconsider previously tested moves. */
for (s
= 0; s
< moves
.num
; s
++)
if (xpos
== moves
.pos
[s
])
if (trymove(xpos
, color
, "defend3-D", str
)) {
/* If the newly placed stone is in atari, we give up
acode
= do_attack(str
, NULL
);
CHECK_RESULT(savecode
, savemove
, acode
, xpos
, move
,
liberties2
= approxlib(libs
[k
], other
, 3, libs2
);
for (r
= 0; r
< liberties2
; r
++) {
/* Don't reconsider previously tested moves. */
for (s
= 0; s
< moves
.num
; s
++)
if (xpos
== moves
.pos
[s
])
if (!is_self_atari(xpos
, color
)
&& trymove(xpos
, color
, "defend2-G", str
)) {
int acode
= do_attack(str
, NULL
);
CHECK_RESULT(savecode
, savemove
, acode
, xpos
, move
/* If nothing else works, try to defend with second order liberties. */
if (stackp
<= backfill_depth
)
special_rescue3_moves(str
, libs
, &moves
);
for (k
= 0; k
< liberties
; k
++)
special_rescue_moves(str
, libs
[k
], &moves
);
bamboo_rescue_moves(str
, liberties
, libs
, &moves
);
if (get_level() >= 8 && stackp
<= backfill2_depth
)
superstring_break_chain_moves(str
, 4, &moves
);
if (stackp
<= break_chain_depth
)
break_chain2_defense_moves(str
, &moves
, 0);
if (stackp
<= backfill_depth
) {
special_rescue5_moves(str
, libs
, &moves
);
special_rescue6_moves(str
, libs
, &moves
);
/* Only order and test the new set of moves. */
order_moves(str
, &moves
, color
, read_function_name
, *move
);
DEFEND_TRY_MOVES(1, &suggest_move
);
/* If nothing else works, we try playing a liberty of the
if (get_level() >= 8 && stackp
<= backfill2_depth
) {
superstring_moves(str
, &moves
, 3, 0);
squeeze_moves(str
, &moves
);
if (stackp
<= break_chain_depth
)
break_chain3_moves(str
, &moves
, 0);
/* Only order and test the new set of moves. */
order_moves(str
, &moves
, color
, read_function_name
, *move
);
DEFEND_TRY_MOVES(1, &suggest_move
);
RETURN_RESULT(savecode
, savemove
, move
, "saved move");
/* defend4(str, *move) attempts to find a move rescuing the
* string at (str) with 4 liberties. If such a move can be found,
* it returns true, and if the pointer move is not NULL,
* then it returns the saving move in *move.
defend4(int str
, int *move
)
struct reading_moves moves
;
int suggest_move
= NO_MOVE
;
SETUP_TRACE_INFO("defend4", str
);
ASSERT1(IS_STONE(board
[str
]), str
);
ASSERT1(countlib(str
) == 4, str
);
liberties
= findlib(str
, 4, libs
);
if (fast_defense(str
, liberties
, libs
, &xpos
))
RETURN_RESULT(WIN
, xpos
, move
, "fast defense");
/* Collect moves to try in the first batch.
* 1. First order liberties.
* 2. Chain breaking moves.
for (k
= 0; k
< liberties
; k
++) {
moves
.message
[k
] = "liberty";
break_chain_moves(str
, &moves
);
break_chain2_efficient_moves(str
, &moves
);
if (stackp
<= backfill_depth
) {
break_chain2_defense_moves(str
, &moves
, 0);
break_chain3_moves(str
, &moves
, 0);
break_chain4_moves(str
, &moves
, 0);
hane_rescue_moves(str
, libs
, &moves
);
if (stackp
<= superstring_depth
)
superstring_moves(str
, &moves
, 4, 0);
squeeze_moves(str
, &moves
);
order_moves(str
, &moves
, color
, read_function_name
, *move
);
DEFEND_TRY_MOVES(1, &suggest_move
);
for (k
= 0; k
< liberties
; k
++)
special_rescue_moves(str
, libs
[k
], &moves
);
bamboo_rescue_moves(str
, liberties
, libs
, &moves
);
order_moves(str
, &moves
, color
, read_function_name
, *move
);
DEFEND_TRY_MOVES(1, &suggest_move
);
RETURN_RESULT(savecode
, savemove
, move
, "saved move");
* special_rescue_moves(str, lib, *move) is called with (str) a
* string having a liberty at (lib).
* This adds moves on a second order liberty to the list of candidate
* moves in the struct *moves; e.g. in shapes like:
* O.* or ..* or O.* or XOOXO
* This will occasionally save a string where no other move will. To
* reduce the branching caused by these moves, we require that the
* opponent can be trivially captured when trying to intercept on the
* corresponding first order liberty.
special_rescue_moves(int str
, int lib
, struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
/* Use approxlib() to test for trivial capture. */
otherlib
= approxlib(lib
, other
, 3, NULL
);
/* Loop over the four neighbours of the liberty, (lib + d). */
for (k
= 0; k
< 4; k
++) {
if (board
[lib
+ d
] == EMPTY
) {
/* Don't play into a self atari unless we have a potential snapback. */
if (is_self_atari(lib
+ d
, color
) && otherlib
> 1)
/* Be more demanding when the string has four liberties. (Mostly
* because attack4() otherwise would need more move generators.)
* More precisely we require not only the first order liberty to
* become a self atari for the opponent but also one more of the
* neighbors of the proposed move. See reading:144 for a
* position where we otherwise would try to defend at D9 and
* attack4() then lacks move generators to stop black from
* continuing towards the top left corner.
int number_protected
= 0;
for (r
= 0; r
< 4; r
++) {
if (board
[lib
+ d
+ delta
[r
]] == EMPTY
&& approxlib(lib
+ d
+ delta
[r
], other
, 3, NULL
) < 3)
if (number_protected
== 2)
if (number_protected
< 2)
ADD_CANDIDATE_MOVE(lib
+ d
, 0, *moves
, "special_rescue");
* playing at * is the correct rescue move, although the opponent cannot
* be captured at the respective first-order liberty.
bamboo_rescue_moves(int str
, int num_libs
, int libs
[],
struct reading_moves
*moves
)
for (l1
= 0; l1
< num_libs
; l1
++)
for (l2
= 0; l2
< num_libs
; l2
++) {
if (libs
[l1
] == WEST(libs
[l2
]) || libs
[l1
] == EAST(libs
[l2
])) {
if (board
[SOUTH(libs
[l1
])] == EMPTY
&& board
[SOUTH(libs
[l2
])] == color
&& !is_self_atari(SOUTH(libs
[l1
]), color
))
ADD_CANDIDATE_MOVE(SOUTH(libs
[l1
]), 0, *moves
, "bamboo_rescue");
if (board
[NORTH(libs
[l1
])] == EMPTY
&& board
[NORTH(libs
[l2
])] == color
&& !is_self_atari(NORTH(libs
[l1
]), color
))
ADD_CANDIDATE_MOVE(NORTH(libs
[l1
]), 0, *moves
, "bamboo_rescue");
else if (libs
[l1
] == NORTH(libs
[l2
]) || libs
[l1
] == SOUTH(libs
[l2
])) {
if (board
[WEST(libs
[l1
])] == EMPTY
&& board
[WEST(libs
[l2
])] == color
&& !is_self_atari(WEST(libs
[l1
]), color
))
ADD_CANDIDATE_MOVE(WEST(libs
[l1
]), 0, *moves
, "bamboo_rescue");
if (board
[EAST(libs
[l1
])] == EMPTY
&& board
[EAST(libs
[l2
])] == color
&& !is_self_atari(EAST(libs
[l1
]), color
))
ADD_CANDIDATE_MOVE(EAST(libs
[l1
]), 0, *moves
, "bamboo_rescue");
/* In a situation like this:
* OOXXXX the following code can find the
* .OXOOX defensive move at 'c'.
* OOXXXX It also can find more general moves like 'c' here.
special_rescue2_moves(int str
, int libs
[2], struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
for (r
= 0; r
< 2; r
++) {
/* Let alib be one of the liberties and require it to be suicide
if (!is_suicide(alib
, other
))
for (k
= 0; k
< 4; k
++) {
if (board
[alib
+ delta
[k
]] == color
&& !same_string(alib
+ delta
[k
], str
)) {
newstr
= alib
+ delta
[k
];
liberties
= findlib(newstr
, 4, newlibs
);
for (s
= 0; s
< liberties
&& s
< 4; s
++) {
if (!is_self_atari(newlibs
[s
], color
))
ADD_CANDIDATE_MOVE(newlibs
[s
], 0, *moves
, "special_rescue2");
break_chain_moves(newstr
, moves
);
break_chain2_efficient_moves(newstr
, moves
);
edge_clamp_moves(newstr
, moves
);
/* In a situation like this:
* XXOO.OXO the following code can find the
* .O..X.*. defensive move at '*'.
special_rescue3_moves(int str
, int libs
[3], struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
int apos
, bpos
, cpos
, dpos
, epos
, fpos
, gpos
;
ASSERT1(countlib(str
) == 3, str
);
for (r
= 0; r
< 3; r
++) {
/* Let (apos) be one of the three liberties. */
/* Try to find the configuration above. */
for (k
= 0; k
< 4; k
++) {
if (board
[cpos
] != color
)
if (!same_string(cpos
, str
))
for (l
= 0; l
< 2; l
++) {
int normal
= delta
[(k
+1)%4];
if (board
[dpos
] != other
)
if (board
[epos
] != color
)
if (board
[fpos
] != EMPTY
)
if (board
[gpos
] != EMPTY
)
/* Configuration found. Now require an X move at 'a' not
* getting too many liberties.
if (approxlib(apos
, other
, 4, NULL
) > 3)
/* Try to play at (fpos). */
ADD_CANDIDATE_MOVE(fpos
, 0, *moves
, "special_rescue3");
/* This code can find moves to counter attack moves generated by
* special_attack3_moves(). In case such an attack move has only two
* liberties, this function finds the liberty which is not common with
* For a typical example, see reading:198 where black L7 is generated
* by special_attack3_moves() and the response at L8 is generated by
special_rescue4_moves(int str
, int libs
[2], struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
ASSERT1(countlib(str
) == 2, str
);
for (k
= 0; k
< 2; k
++) {
if (apos
== SOUTH(bpos
) || apos
== NORTH(bpos
)) {
if (board
[WEST(apos
)] == other
)
else if (board
[EAST(apos
)] == other
)
else if (apos
== WEST(bpos
) || apos
== EAST(bpos
)) {
if (board
[SOUTH(apos
)] == other
)
else if (board
[NORTH(apos
)] == other
)
return; /* Incorrect configuration, give up. */
if (findlib(xpos
, 2, libs2
) == 2) {
if (libs2
[r
] != apos
&& libs2
[r
] != bpos
&& !is_self_atari(libs2
[r
], color
))
ADD_CANDIDATE_MOVE(libs2
[r
], 0, *moves
, "special_rescue4");
/* In a situation like this:
* X.OX.. the following code can find the
* ...... defensive move at '*'.
* The only requirement is that d has at most as many liberties as b,
* and as the newly placed stone at c.
hane_rescue_moves(int str
, int libs
[4], struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
int apos
, bpos
, cpos
, dpos
;
int num_libs
= countlib(str
);
ASSERT1(num_libs
<= 4, str
);
for (r
= 0; r
< num_libs
; r
++) {
/* Let (apos) be one of the three liberties. */
/* Try to find the configuration above. */
for (k
= 0; k
< 4; k
++) {
if (board
[bpos
] != color
)
if (!same_string(bpos
, str
))
for (l
= 0; l
< 2; l
++) {
int normal
= delta
[(k
+1)%4];
if (board
[cpos
] != EMPTY
)
if (board
[dpos
] != other
)
/* Configuration found. Now check liberty constraint. */
int dlibs
= countlib(dpos
);
|| dlibs
> accuratelib(cpos
, color
, dlibs
, NULL
))
if (0 && !in_list(cpos
, moves
->num
, moves
->pos
)) {
gprintf("hane_rescue_move added for %1m at %1m\n", str
, cpos
);
ADD_CANDIDATE_MOVE(cpos
, 0, *moves
, "hane_rescue");
/* In situations like these
* the smaller of the O strings can be defended by *. The property
* they have in common is that the defended string has (at least) two
* liberties in common with an X string and it's effective to play on
* an exterior liberty of this string. Similarly it may be worth
* defending a weak neighbor of the X string.
* This function may be called for strings with 2 or 3 liberties and
* returns moves which are potentially useful in these positions.
special_rescue5_moves(int str
, int libs
[3],
struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
int liberties
= countlib(str
);
ASSERT1(liberties
== 2 || liberties
== 3, str
);
for (r
= 0; r
< liberties
; r
++) {
for (k
= 0; k
< 4; k
++) {
if (board
[bpos
] != other
)
/* Don't bother if it has too many liberties. */
if (countlib(bpos
) > liberties
+ 1)
if (count_common_libs(str
, bpos
) < 2)
liberties2
= findlib(bpos
, 4, libs2
);
for (s
= 0; s
< liberties2
; s
++)
if (!liberty_of_string(libs2
[s
], str
)
&& !is_self_atari(libs2
[s
], color
))
ADD_CANDIDATE_MOVE(libs2
[s
], 0, *moves
, "special_rescue5-A");
/* Reinforce the second order chain. */
if (liberties2
<= liberties
) {
adj
= chainlinks2(bpos
, adjs
, 1);
for (t
= 0; t
< adj
; t
++) {
break_chain_moves(adjs
[t
], moves
);
findlib(adjs
[t
], 1, &cpos
);
if (!is_self_atari(cpos
, color
))
ADD_CANDIDATE_MOVE(cpos
, 0, *moves
, "special_rescue5-B");
/* Defend against double atari in the surrounding chain early. */
double_atari_chain2_moves(bpos
, moves
, 0);
/* In situations like this
* the lower O string can often be defended at a or b.
* This function may be called for strings with 3 or 4 liberties and
* returns the * moves in the configuration below:
* It also adds the * move in these configurations:
* Provided that * is not a self atari and that the X strings have
* sufficiently few liberties.
special_rescue6_moves(int str
, int libs
[3], struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
int liberties
= countlib(str
);
ASSERT1(liberties
== 3 || liberties
== 4, str
);
for (r
= 0; r
< liberties
; r
++) {
for (k
= 0; k
< 4; k
++) {
if (ON_BOARD(apos
- right
))
if (board
[bpos
] != color
|| !same_string(str
, bpos
))
for (l
= 0; l
< 2; l
++) {
if (board
[cpos
] != other
)
if (board
[apos
+ up
] != EMPTY
)
if (board
[cpos
+ right
] != EMPTY
)
if (board
[apos
+ up
+ up
] == EMPTY
&& board
[cpos
+ up
] == EMPTY
&& board
[cpos
+ up
+ right
] == color
) {
ADD_CANDIDATE_MOVE(cpos
+ right
, 0, *moves
, "special_rescue6-A");
ADD_CANDIDATE_MOVE(cpos
+ up
, 0, *moves
, "special_rescue6-B");
else if (countlib(cpos
) <= 3
&& (board
[bpos
+ right
] == EMPTY
|| (board
[bpos
+ right
] == other
&& countlib(bpos
+ right
) <= 4))
&& !is_self_atari(cpos
+ right
, color
)) {
ADD_CANDIDATE_MOVE(cpos
+ right
, 0, *moves
, "special_rescue6-C");
* set_up_snapback_moves() is called with (str) a string having a
* single liberty at (lib).
* This adds moves which may defend a string in atari by capturing a
* neighbor in a snapback. One example is this position:
* This code also finds the move * to defend the lone O stone with ko
set_up_snapback_moves(int str
, int lib
, struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
ASSERT1(countlib(str
) == 1, str
);
/* This can only work if our string is a single stone and the
* opponent is short of liberties.
if (stackp
<= backfill_depth
&& approxlib(lib
, other
, 2, libs2
) == 1
&& (!is_self_atari(libs2
[0], color
)
|| is_ko(libs2
[0], color
, NULL
)))
ADD_CANDIDATE_MOVE(libs2
[0], 0, *moves
, "set_up_snapback");
/* This function adds liberties of the superstring as candidate moves.
* For performance, this is restricted to strings with liberty_cap
* liberties, and to cases where at most 5 liberties would get considered.
* When attacking, we also try backfilling in case the direct approach
* When defending, we also try second order liberties.
superstring_moves(int str
, struct reading_moves
*moves
,
int liberty_cap
, int does_attack
)
int ss_libs
[MAX_LIBERTIES
+ 4];
int other
= OTHER_COLOR(color
);
find_superstring_liberties(str
, &ss_liberties
, ss_libs
, liberty_cap
);
for (k
= 0; k
< ss_liberties
; k
++) {
int alib
= accuratelib(apos
, other
, 2, alibs
);
if (liberty_of_string(apos
, str
))
ADD_CANDIDATE_MOVE(apos
, 0, *moves
, "superstring liberty");
&& board
[alibs
[0]] == EMPTY
&& approxlib(alibs
[0], other
, 3, NULL
) >= 3)
ADD_CANDIDATE_MOVE(alibs
[0], 0, *moves
, "superstring backfill");
special_rescue_moves(str
, apos
, moves
);
/* This function is somewhat related to superstring_moves() but tries
* to find moves to squeeze out liberties from the superstring, aiming
* to capture the main string in a shortage of liberties.
* For a typical example, see the move E9 in reading:203,204. It is
* assumed that the same move is effective both for attack and
squeeze_moves(int str
, struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
int potential_move
= NO_MOVE
;
num_libs
= findlib(str
, 4, libs
);
gg_assert(num_libs
<= 4);
for (k
= 0; k
< num_libs
; k
++) {
if (!is_suicide(libs
[k
], other
))
num_libs2
= approxlib(libs
[k
], color
, 4, libs2
);
if (num_libs2
!= num_libs
)
for (r
= 0; r
< num_libs2
; r
++)
if (!liberty_of_string(libs2
[r
], str
)) {
potential_move
= libs2
[r
];
previous_liberty
= libs
[k
];
while (is_suicide(potential_move
, other
)) {
num_libs2
= approxlib(potential_move
, color
, 3, libs2
);
potential_move
= NO_MOVE
;
if (libs2
[0] == previous_liberty
) {
previous_liberty
= potential_move
;
potential_move
= libs2
[1];
previous_liberty
= potential_move
;
potential_move
= libs2
[0];
if (liberty_of_string(potential_move
, str
)) {
potential_move
= NO_MOVE
;
if (potential_move
== NO_MOVE
|| !is_self_atari(potential_move
, other
))
approxlib(potential_move
, other
, 1, libs2
);
num_libs2
= approxlib(libs2
[0], color
, MAXLIBS
, NULL
);
&& num_libs2
< approxlib(potential_move
, color
, MAXLIBS
, NULL
))
ADD_CANDIDATE_MOVE(potential_move
, 0, *moves
, "squeeze move");
* the O stones to the left are best defended by the move at *.
* This function tries to find an adjacent string (apos) with exactly
* three liberties. One of the liberties (bpos) must be on the edge
* (but not in the corner). Diagonal to this liberty must be one stone
* of the attacked string (cpos) and another liberty (dpos) of the
* adjacent string. The third liberty (epos) must be adjacent to
* (dpos). Furthermore must an O stone at (dpos) get at least three
* liberties and and X stone at (epos) must get at most three
* The defense move at (dpos) is proposed if the above conditions
edge_clamp_moves(int str
, struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
/* Pick up neighbors with three liberties. */
adj
= chainlinks2(str
, adjs
, 3);
for (r
= 0; r
< adj
; r
++) {
/* Find a liberty at the edge. */
for (k
= 0; k
< 3; k
++) {
if (is_edge_vertex(libs
[k
])) {
/* Edge liberty found. Establish up and right directions. */
for (k
= 0; k
< 4; k
++) {
if (board
[bpos
+ up
] != other
)
for (l
= 0; l
< 2; l
++) {
int right
= delta
[(k
+1)%4];
cpos
= bpos
+ up
- right
;
dpos
= bpos
+ up
+ right
;
if (board
[cpos
] != color
|| !same_string(cpos
, str
))
if (board
[dpos
] != EMPTY
|| !liberty_of_string(dpos
, apos
))
if (board
[epos
] != EMPTY
|| !liberty_of_string(epos
, apos
))
if (approxlib(dpos
, color
, 3, NULL
) < 3)
if (approxlib(epos
, other
, 4, NULL
) > 3)
/* (dpos) looks like a good move. Add it to the list with a
* substantial initial score.
ADD_CANDIDATE_MOVE(dpos
, 10, *moves
, "edge_clamp");
* This function handles some special cases on the edge.
* 1. If (str) points to a string and 'a' an edge liberty of it,
* there is no point of trying to defend the string by crawling
* along the edge if there is no hope of ever getting more liberties.
* This is of course if the blocking enemy group has enough liberties
* This function searches the edge towards the corner and sees if there
* is a friendly stone on one of the two first lines. If not, the move
* is removed from the list of moves.
* 2. If (str) points to a string and 'a' an edge liberty of it,
* the drawing back/climbing up move 'b' is often correct attack or
* defense. Another good move to try is 'c' (but usually not for
* defense of a 2 liberty string).
* This function adds the points configured like 'b' and 'c' relative to
* (str) to the list of moves.
* color is the color to move.
propose_edge_moves(int str
, int *libs
, int liberties
,
struct reading_moves
*moves
, int to_move
)
int other
= OTHER_COLOR(color
);
for (r
= 0; r
< liberties
; r
++) {
for (k
= 0; k
< 4; k
++) {
for (l
= 0; l
< 2; l
++) {
if (board
[apos
+ up
] == other
/* other on top of liberty */
&& countlib(apos
+ up
) > 4 /* blocking group must be secure */
&& color
== to_move
) { /* only applicable as defense */
/* Case 1: other above the liberty (crawl along the edge). */
|| board
[xpos
+ up
] == color
)
/* If no friendly stone found, then it is pointless and we
* can just as well remove the move.
REMOVE_CANDIDATE_MOVE(apos
, *moves
);
else if (board
[apos
+ up
] == EMPTY
/* empty above the liberty */
&& board
[apos
- right
+ up
] == other
&& board
[apos
+ right
] == EMPTY
) { /* empty to the right */
/* Case 2: Try to escape or contain. */
* If adjacent X stone in atari, boost the initial score of this
if (countlib(apos
+ up
- right
) == 1)
ADD_CANDIDATE_MOVE(apos
+ up
, 10, *moves
, "propose_edge-A");
ADD_CANDIDATE_MOVE(apos
+ up
, 0, *moves
, "propose_edge-B");
if (board
[apos
+ right
+ up
] == EMPTY
&& (liberties
!= 2 || color
!= to_move
))
ADD_CANDIDATE_MOVE(apos
+ right
+ up
, 0, *moves
,
/* ================================================================ */
/* Attacking functions */
/* ================================================================ */
/* Like attack. If the opponent is komaster reading functions will not try
do_attack(int str
, int *move
)
SETUP_TRACE_INFO("attack", str
);
ASSERT1(color
!= 0, str
);
if (color
== 0) /* if assertions are turned off, silently fails */
liberties
= countlib(str
);
|| (liberties
== 4 && stackp
> fourlib_depth
)
|| (liberties
== 3 && stackp
> depth
)) {
/* No need to cache the result in these cases. */
sprintf(buf
, "got 4 liberties (stackp:%d>%d)",
/* Set "killer move" up. This move (if set) was successful in
* another variation, so it is reasonable to try it now. However,
* we only do this if the string has 4 liberties - otherwise the
* situation changes too much from variation to variation.
if (liberties
> 3 && move
)
/* Note that if return value is 1 (too small depth), the move will
* still be used for move ordering.
&& tt_get(&ttable
, ATTACK
, str
, NO_MOVE
, depth
- stackp
, NULL
,
&retval
, NULL
, &xpos
) == 2) {
TRACE_CACHED_RESULT(retval
, xpos
);
SGFTRACE(xpos
, retval
, "cached");
/* Treat the attack differently depending on how many liberties the
result
= attack1(str
, &xpos
);
else if (liberties
== 2) {
result
= simple_ladder(str
, &xpos
);
result
= attack2(str
, &xpos
);
result
= attack3(str
, &xpos
);
result
= attack4(str
, &xpos
);
ASSERT1(result
>= 0 && result
<= WIN
, str
);
READ_RETURN(ATTACK
, str
, depth
- stackp
, move
, xpos
, result
);
READ_RETURN0(ATTACK
, str
, depth
- stackp
);
/* If (str) points to a group with exactly one liberty, attack1
* determines whether it can be captured by playing at this liberty.
* If successful, (*move) is the killing move. move may be NULL if
* caller is only interested in whether it can be captured.
* The attack may fail for two different reasons. The first one is
* that the attack may be an illegal ko capture, in this case KO_B is
* returned (need to play a ko threat before the attack can be
* The second cause for failure is that the attack is caught in a
* snapback. We must require that it is a proper snapback, though. By
* proper snapback we mean a position like
* where capture by O and recapture by X leaves the X stone intact
* with at least two liberties:
* There are a number of different kinds of improper snapbacks, which
* have in common that the attacked string ends up captured. We don't
* consider these as failures to attack. Three examples are given below.
* XXOOOOO (X can recapture but loses most of the string.)
* XXXOOOOOOOO (Like the previous example, except O loses one more stone)
* XXXOO (After three captures, the lone X stone is gone.)
* This function is fast and never branches. There's little point in
attack1(int str
, int *move
)
int other
= OTHER_COLOR(color
);
SETUP_TRACE_INFO("attack1", str
);
/* Pick up the position of the liberty. */
/* If the attacked string consists of more than one stone, the
* attack never fails. (This assumes simple ko rule. With superko
* rule it could still be a ko violation.)
if (countstones(str
) > 1) {
RETURN_RESULT(WIN
, xpos
, move
, "last liberty");
/* Try to play on the liberty. This fails if and only if it is an
if (trymove(xpos
, other
, "attack1-A", str
)) {
/* Is the attacker in atari? If not the attack was successful. */
if (countlib(xpos
) > 1) {
RETURN_RESULT(WIN
, xpos
, move
, "last liberty");
/* If the attacking string is also a single stone, a possible
* recapture would be a ko violation, so the defender has to make
else if (countstones(xpos
) == 1) {
if (get_komaster() != other
) {
/* If the defender is allowed to take the ko the result is KO_A. */
CHECK_RESULT_UNREVERSED(savecode
, savemove
, KO_A
, xpos
, move
,
/* But if the attacker is the attack was successful. */
RETURN_RESULT(WIN
, xpos
, move
, "last liberty");
/* Otherwise, do recapture. Notice that the liberty must be
* at (str) since we have already established that this string
else if (trymove(str
, color
, "attack1-B", str
)) {
/* If this was a proper snapback, (str) will now have more
/* Proper snapback, attack fails. */
RETURN_RESULT(WIN
, xpos
, move
, "last liberty");
else {/* Illegal ko capture. */
if (get_komaster() != color
) {
CHECK_RESULT_UNREVERSED(savecode
, savemove
, KO_B
, xpos
, move
,
/* If not yet successful, try backfilling and back-capturing.
* An example of back-capturing can be found in reading:234.
* Backfilling is maybe only meaningful in positions involving ko.
liberties
= approxlib(xpos
, color
, 6, libs
);
for (k
= 0; k
< liberties
; k
++) {
if (!is_self_atari(apos
, other
)
&& trymove(apos
, other
, "attack1-C", str
)) {
int dcode
= do_find_defense(str
, NULL
);
if (dcode
!= WIN
&& do_attack(str
, NULL
)) {
RETURN_RESULT(WIN
, apos
, move
, "backfilling");
UPDATE_SAVED_KO_RESULT(savecode
, savemove
, dcode
, apos
);
adj
= chainlinks2(str
, adjs
, 1);
for (r
= 0; r
< adj
; r
++) {
if (liberty_of_string(xpos
, adjs
[r
])) {
adj2
= chainlinks2(adjs
[r
], adjs2
, 1);
for (k
= 0; k
< adj2
; k
++) {
findlib(adjs2
[k
], 1, &apos
);
if (komaster_trymove(apos
, other
, "attack1-D", str
,
&ko_move
, stackp
<= ko_depth
&& savecode
== 0)) {
int dcode
= do_find_defense(str
, NULL
);
&& do_attack(str
, NULL
)) {
CHECK_RESULT(savecode
, savemove
, dcode
, apos
, move
,
if (do_find_defense(str
, NULL
) != WIN
&& do_attack(str
, NULL
) != 0) {
RETURN_RESULT(0, 0, move
, NULL
);
RETURN_RESULT(savecode
, savemove
, move
, "saved move");
/* If str points to a group with exactly two liberties
* attack2 determines whether it can be captured in ladder or net.
* If yes, *move is the killing move. move may be null if caller
* is only interested in whether it can be captured.
* Returns KO_A or KO_B if it can be killed conditioned on ko. Returns
* KO_A if it can be killed provided (other) is willing to ignore any
* ko threat. Returns KO_B if (other) wins provided he has a ko threat
* which must be answered. Can give a return code KO_B yet *move=0 if
* the winning move is an illegal ko capture. In this case, making a
* ko threat and having it answered should transform the position to
* one where the return code is KO_A.
* See the comment before defend1 about ladders and reading depth.
attack2(int str
, int *move
)
int other
= OTHER_COLOR(color
);
struct reading_moves moves
;
int adjacent_liberties
= 0;
int suggest_move
= NO_MOVE
;
SETUP_TRACE_INFO("attack2", str
);
ASSERT1(IS_STONE(board
[str
]), str
);
ASSERT1(countlib(str
) == 2, str
);
for (pass
= 0; pass
< 4; pass
++) {
/* The attack may fail if a boundary string is in atari and cannot
* be defended. First we must try defending such a string.
* We start by trying to defend the boundary string by looking for an
* adjacent string which is in atari.
adj
= chainlinks2(str
, adjs
, 1);
for (r
= 0; r
< adj
; r
++) {
/* If stackp > depth and any boundary chain is in atari, assume safe.
* However, if the captured chain is only of size 1, there can still
* be a working ladder, so continue if that is the case.
* Also if the string in atari shares its liberty with the
* attacked string, drawing it out may enable the ladder to
&& countstones(adjs
[r
]) > 1
&& !have_common_lib(str
, adjs
[r
], NULL
)) {
RETURN_RESULT(0, 0, move
, "boundary in atari");
/* Pick up moves breaking the second order chain. */
break_chain_moves(adjs
[r
], &moves
);
findlib(adjs
[r
], 1, &hpos
);
ADD_CANDIDATE_MOVE(hpos
, 0, moves
, "save_boundary");
/* Get the two liberties of (str). */
liberties
= findlib(str
, 2, libs
);
ASSERT1(liberties
== 2, str
);
if (DIRECT_NEIGHBORS(libs
[0], libs
[1]))
for (k
= 0; k
< 2; k
++) {
if (!is_self_atari(apos
, other
))
/* We only want to consider the move at (apos) if:
* stackp <= backfill_depth
* -or- stackp <= depth and it is an isolated stone
* -or- it is not in immediate atari
if (stackp
<= backfill_depth
|| ((stackp
<= depth
|| adjacent_liberties
)
&& !has_neighbor(apos
, other
))
|| !is_self_atari(apos
, other
))
ADD_CANDIDATE_MOVE(apos
, 0, moves
, "liberty");
/* Try backfilling if atari is impossible. */
if (stackp
<= backfill_depth
&& approxlib(apos
, other
, 2, libs2
) == 1) {
ADD_CANDIDATE_MOVE(libs2
[0], 0, moves
, "backfill");
/* If there is a neighbor in atari, we also try back-capturing. */
for (r
= 0; r
< 4; r
++) {
int bpos
= libs2
[0] + delta
[r
];
if (board
[bpos
] == other
&& chainlinks2(bpos
, adjs
, 1) > 0) {
/* FIXME: If there is more than one neighbor in atari, we
* currently just take one randomly. This is maybe not good
* enough. We might also want to check against snapback.
* FIXME: What is the purpose of this? It produces some
* completely irrelevant moves (e.g. if bpos is a huge string
* with many liberties and adjs[0] is somewhere else on the
findlib(adjs
[0], 1, &xpos
);
ADD_CANDIDATE_MOVE(xpos
, 0, moves
, "back-capture");
/* If we can't make a direct atari, look for edge blocking moves. */
edge_block_moves(str
, libs
[k
], &moves
);
/* If one of the surrounding chains have only two liberties, which
* coincide with the liberties of the attacked string, we try to
adj
= chainlinks2(str
, adjs
, 2);
for (r
= 0; r
< adj
; r
++) {
if (liberty_of_string(libs
[0], apos
)
&& liberty_of_string(libs
[1], apos
))
break_chain_moves(apos
, &moves
);
propose_edge_moves(str
, libs
, liberties
, &moves
, other
);
if (stackp
<= backfill_depth
) {
special_attack2_moves(str
, libs
, &moves
);
special_attack3_moves(str
, libs
, &moves
);
special_attack4_moves(str
, libs
, &moves
);
find_cap_moves(str
, &moves
);
/* If it is not possible to make a direct atari, we try filling
* a liberty of the superstring.
&& stackp
<= backfill_depth
&& (stackp
<= superstring_depth
|| !atari_possible
)) {
if (stackp
<= backfill2_depth
)
superstring_moves(str
, &moves
, liberty_cap
, 1);
squeeze_moves(str
, &moves
);
order_moves(str
, &moves
, other
, read_function_name
, *move
);
ATTACK_TRY_MOVES(0, &suggest_move
);
RETURN_RESULT(savecode
, savemove
, move
, "saved move");
/* attack3(str, *move) is used when (str) points to a group with
* three liberties. It returns true if it finds a way to kill the group.
* Return code is KO_A if the group can be killed if the attacker is
* willing to ignore any ko threat.
* Return code is KO_B if the group can be killed if the attacker is
* able to find a ko threat which must be answered.
* If non-NULL (*move) will be set to the move which makes the
attack3(int str
, int *move
)
int other
= OTHER_COLOR(color
);
struct reading_moves moves
;
int suggest_move
= NO_MOVE
;
SETUP_TRACE_INFO("attack3", str
);
ASSERT1(IS_STONE(board
[str
]), str
);
ASSERT1(stackp
<= depth
, str
);
for (pass
= 0; pass
< 4; pass
++) {
adj
= chainlinks2(str
, adjs
, 1);
for (r
= 0; r
< adj
; r
++) {
break_chain_moves(adjs
[r
], &moves
);
findlib(adjs
[r
], 1, &hpos
);
ADD_CANDIDATE_MOVE(hpos
, 0, moves
, "save_boundary");
/* Defend against double atari in the surrounding chain early. */
double_atari_chain2_moves(str
, &moves
, stackp
<= superstring_depth
);
/* Get the three liberties of (str). */
liberties
= findlib(str
, 3, libs
);
ASSERT1(liberties
== 3, str
);
for (k
= 0; k
< 3; k
++) {
/* We only want to consider the move at (apos) if:
* stackp <= backfill_depth
* -or- stackp <= depth and it is an isolated stone
* -or- it is not in immediate atari
if (stackp
<= backfill_depth
&& !has_neighbor(apos
, other
))
|| !is_self_atari(apos
, other
))
ADD_CANDIDATE_MOVE(apos
, 0, moves
, "liberty");
edge_closing_backfill_moves(str
, apos
, &moves
);
/* Try backfilling if atari is impossible. */
if (stackp
<= backfill_depth
&& approxlib(apos
, other
, 2, libs2
) == 1) {
ADD_CANDIDATE_MOVE(libs2
[0], 0, moves
, "backfill");
/* Look for edge blocking moves. */
edge_block_moves(str
, apos
, &moves
);
/* Pick up some edge moves. */
propose_edge_moves(str
, libs
, liberties
, &moves
, other
);
/* The simple ataris didn't work. Try something more fancy. */
if (stackp
<= backfill_depth
)
find_cap_moves(str
, &moves
);
if (stackp
<= fourlib_depth
)
draw_back_moves(str
, &moves
);
/* Try to defend chain links with two liberties. */
if (stackp
<= backfill2_depth
) {
adj
= chainlinks2(str
, adjs
, 2);
for (r
= 0; r
< adj
; r
++) {
findlib(adjs
[r
], 2, libs2
);
if (approxlib(libs2
[0], other
, 4, NULL
) > 3
&& approxlib(libs2
[1], other
, 4, NULL
) > 3)
break_chain_moves(adjs
[r
], &moves
);
break_chain2_moves(adjs
[r
], &moves
, 1, 0);
ADD_CANDIDATE_MOVE(libs2
[k
], 0, moves
, "save_boundary-2");
/* If nothing else works, we try filling a liberty of the
if (get_level() >= 8 && stackp
<= backfill2_depth
) {
superstring_moves(str
, &moves
, 3, 1);
squeeze_moves(str
, &moves
);
order_moves(str
, &moves
, other
, read_function_name
, *move
);
ATTACK_TRY_MOVES(1, &suggest_move
);
RETURN_RESULT(savecode
, savemove
, move
, "saved move");
/* attack4 tries to capture a string with 4 liberties. */
attack4(int str
, int *move
)
int other
= OTHER_COLOR(color
);
struct reading_moves moves
;
int suggest_move
= NO_MOVE
;
SETUP_TRACE_INFO("attack4", str
);
ASSERT1(IS_STONE(board
[str
]), str
);
SGFTRACE(0, 0, "stackp > depth");
for (pass
= 0; pass
< 2; pass
++) {
adj
= chainlinks2(str
, adjs
, 1);
for (r
= 0; r
< adj
; r
++) {
break_chain_moves(adjs
[r
], &moves
);
findlib(adjs
[r
], 1, &hpos
);
ADD_CANDIDATE_MOVE(hpos
, 0, moves
, "save_boundary");
/* Defend against double atari in the surrounding chain early. */
double_atari_chain2_moves(str
, &moves
, stackp
<= superstring_depth
);
/* Give a score bonus to the chain preserving moves. */
for (k
= 0; k
< moves
.num
; k
++)
/* Get the four liberties of (str). */
liberties
= findlib(str
, 4, libs
);
ASSERT1(liberties
== 4, str
);
for (k
= 0; k
< 4; k
++) {
/* We only want to consider the move at (apos) if:
* stackp <= backfill_depth
* -or- stackp <= depth and it is an isolated stone
* -or- it is not in immediate atari
if (stackp
<= backfill_depth
&& !has_neighbor(apos
, other
))
|| !is_self_atari(apos
, other
))
ADD_CANDIDATE_MOVE(apos
, 0, moves
, "liberty");
edge_closing_backfill_moves(str
, apos
, &moves
);
/* Look for edge blocking moves. */
edge_block_moves(str
, apos
, &moves
);
/* Pick up some edge moves. */
propose_edge_moves(str
, libs
, liberties
, &moves
, other
);
if (stackp
<= backfill_depth
)
find_cap_moves(str
, &moves
);
order_moves(str
, &moves
, other
, read_function_name
, *move
);
ATTACK_TRY_MOVES(1, &suggest_move
);
RETURN_RESULT(savecode
, savemove
, move
, "saved move");
/* If (str) points to a string with 2 - 4 liberties,
* find_cap_moves(str, &moves)
* looks for a configuration of the following type:
* where X are elements of the string in question and a and b are
* For larger strings, this can find moves like
* even though they are not capping moves.
find_cap_moves(int str
, struct reading_moves
*moves
)
numlibs
= findlib(str
, 4, libs
);
if (numlibs
> 4 || numlibs
< 2)
for (i
= 0; i
< numlibs
- 1; i
++) {
for (j
= i
+ 1; j
< numlibs
; j
++) {
/* Check if the two liberties are located like the figure above. */
if (!DIAGONAL_NEIGHBORS(alib
, blib
))
/* Which of the two corner points should we use? One of them is
* always occupied by the string at (str), the other one is either
* free or occupied by something else.
if (BOARD(bi
, aj
) == EMPTY
)
ADD_CANDIDATE_MOVE(POS(bi
, aj
), 10, *moves
, "find_cap");
else if (BOARD(ai
, bj
) == EMPTY
)
ADD_CANDIDATE_MOVE(POS(ai
, bj
), 10, *moves
, "find_cap");
/* In a situation like this:
* XXOOX the attacking move
* The name of the function corresponds to special_rescue2, which is
* fairly similar to this situation.
special_attack2_moves(int str
, int libs
[2], struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
for (k
= 0; k
< 2; k
++) {
if (is_suicide(libs
[k
], other
)
&& (approxlib(libs
[k
], color
, 3, newlibs
) == 2)) {
if (newlibs
[0] != libs
[1-k
])
if (!is_self_atari(xpos
, other
)) {
ADD_CANDIDATE_MOVE(xpos
, 0, *moves
, "special_attack2");
/* In situations like these:
* the code that follows can find the attacking move at c.
special_attack3_moves(int str
, int libs
[2], struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
ASSERT1(countlib(str
) == 2, str
);
for (k
= 0; k
< 2; k
++) {
if (apos
== SOUTH(bpos
) || apos
== NORTH(bpos
)) {
if (board
[WEST(apos
)] == EMPTY
)
else if (board
[EAST(apos
)] == EMPTY
)
else if (apos
== WEST(bpos
) || apos
== EAST(bpos
)) {
if (board
[SOUTH(apos
)] == EMPTY
)
else if (board
[NORTH(apos
)] == EMPTY
)
return; /* Incorrect configuration, give up. */
if (!is_self_atari(xpos
, other
))
ADD_CANDIDATE_MOVE(xpos
, 0, *moves
, "special_attack3");
/* In situations like these:
* the code that follows can find the attacking move at *.
* Also for situations in which c has three liberties, one of which in common
* with b, the respective attacking move is found (see reading:52 for an
special_attack4_moves(int str
, int libs
[2], struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
int adj2
, adjs2
[MAXCHAIN
];
ASSERT1(countlib(str
) == 2, str
);
/* To avoid making this too general, we require that both
* liberties are self ataris for X.
if (!is_self_atari(libs
[0], other
)
|| !is_self_atari(libs
[1], other
))
/* Pick up chain links with 2 liberties. */
adj
= chainlinks2(str
, adjs
, 2);
for (k
= 0; k
< 2; k
++) {
/* Check that (apos) also is a liberty of one of the two liberty
for (s
= 0; s
< adj
; s
++)
if (liberty_of_string(apos
, adjs
[s
])) {
/* Now require that (bpos) has a chain link, different from (str),
* also with two liberties, or with three liberties, but one in common
adj2
= chainlinks3(bpos
, adjs2
, 3);
for (s
= 0; s
< adj2
; s
++) {
if (same_string(cpos
, str
))
/* Pick up the liberties of (cpos). */
clibs
= findlib(cpos
, 3, libs2
);
/* No need to do something fancy if it is in atari already. */
/* (cpos) has three liberties, none of which in commmon with (bpos)
* attacking it seems too difficult. */
bc_common_lib
= have_common_lib(bpos
, cpos
, NULL
);
if (clibs
> 2 && !bc_common_lib
)
/* Try playing at a liberty. Before doing this, verify that
* (cpos) cannot get more than three liberties by answering on
* another liberty and that we are not putting ourselves in atari.
* We also should only allow ourselves to get fewer liberties than
* the defender in case (bpos) and (cpos) have a common liberty.
for (t
= 0; t
< clibs
; t
++) {
if (is_self_atari(dpos
, other
))
for (u
= 0; u
< clibs
; u
++) {
elibs
= approxlib(epos
, color
, 4, NULL
);
dlibs
= approxlib(dpos
, other
, 3, NULL
);
if (elibs
> dlibs
&& !bc_common_lib
)
if (u
>= clibs
) /* No break occurred. */
ADD_CANDIDATE_MOVE(dpos
, 0, *moves
, "special_attack4");
* If (str) points to a string, draw_back(str, &moves)
* looks for a move in the following configuration which attacks
* X* X=attacker, O=defender
* In the initial implementation we consider cases
* where X has exactly 2 liberties.
draw_back_moves(int str
, struct reading_moves
*moves
)
adj
= chainlinks2(str
, adjs
, 2);
for (r
= 0; r
< adj
; r
++) {
findlib(adjs
[r
], 2, libs
);
for (k
= 0; k
< 2; k
++) {
if (!liberty_of_string(libs
[k
], str
)
&& ((ON_BOARD1(SOUTH(libs
[k
]))
&& liberty_of_string(SOUTH(libs
[k
]), str
))
|| (ON_BOARD1(WEST(libs
[k
]))
&& liberty_of_string(WEST(libs
[k
]), str
))
|| (ON_BOARD1(NORTH(libs
[k
]))
&& liberty_of_string(NORTH(libs
[k
]), str
))
|| (ON_BOARD1(EAST(libs
[k
]))
&& liberty_of_string(EAST(libs
[k
]), str
)))) {
ADD_CANDIDATE_MOVE(libs
[k
], 0, *moves
, "draw_back");
/* In the following position the reading is much simplifed if we start
* with the edge closing backfilling move at *.
* This function identifies the situation
* where a is a liberty of the attacked string, t is the proposed move,
* and b and c do not contain more O stones than X stones.
edge_closing_backfill_moves(int str
, int apos
, struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
for (k
= 0; k
< 4; k
++) {
int right
= delta
[(k
+1)%4];
if (board
[apos
+ up
] != color
)
if (board
[apos
+ right
] == EMPTY
&& (!ON_BOARD(apos
- right
)
|| board
[apos
- right
] == color
))
; /* Everything ok so far. */
else if (board
[apos
- right
] == EMPTY
&& (!ON_BOARD(apos
+ right
)
|| board
[apos
+ right
] == color
)) {
/* Negate right direction. */
if (board
[apos
+ up
+ right
] != other
)
bpos
= apos
+ up
+ 2 * right
;
if (board
[bpos
] == color
)
else if (board
[bpos
] == other
)
if (board
[cpos
] == color
)
else if (board
[cpos
] == other
)
ADD_CANDIDATE_MOVE(apos
+ right
, 0, *moves
, "edge_closing_backfill");
/* The first version of this function seemed to induce too many
* variations and has therefore been replaced by a much more limited
* where the X stones to the left are being attacked, it is often a
* good idea to first consider either or both of the moves marked by *
* in the diagram. Notice that propose_edge_moves() doesn't help with
* this, since the rightmost X stone is not part of the attacked
* string, only the corresponding superstring.
* This function identifies the situation
* where a is a liberty of the attacked string, b is a stone of the
* attacked string, and e and f are the considered moves. Also
* considered is the situation where the conditions to the right are
* not correct but c has only two liberties anyway. If safe, the move
* to make atari on c is proposed.
* Notice, this code is disabled, as commented above.
edge_block_moves(int str
, int apos
, struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
/* Search for the right orientation. */
for (k
= 0; k
< 4; k
++) {
if (board
[apos
+ up
] != color
|| !same_string(apos
+ up
, str
))
for (l
= 0; l
< 2; l
++) {
int right
= delta
[(k
+1)%4];
dpos
= apos
+ right
+ up
;
if (board
[cpos
] != color
|| board
[dpos
] != other
)
if (board
[epos
] == EMPTY
&& board
[fpos
] == EMPTY
&& (board
[gpos
] != color
)) {
/* Everything is set up, suggest moves at e and f. */
if (!ON_BOARD(hpos
) || board
[hpos
] == color
)
ADD_CANDIDATE_MOVE(epos
, score
, *moves
, "edge_block-A");
ADD_CANDIDATE_MOVE(fpos
, score
, *moves
, "edge_block-B");
else if (countlib(cpos
) == 2 && countlib(dpos
) > 1) {
if (!is_self_atari(move
, other
))
ADD_CANDIDATE_MOVE(move
, 0, *moves
, "edge_block-C");
* where the X stones to the left are being attacked, it is usually
* important to start by considering the move at *. Thus we propose
* the move at * with a high initial score.
* Also, it is often needed to prevent "crawling" along first line
* which can eventually give defender more liberties, like here:
* This function identifies the situation
* where a is a liberty of the attacked string, b is a stone of the
* attacked string, and e and f are the considered moves.
edge_block_moves(int str
, int apos
, struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
/* Search for the right orientation. */
for (k
= 0; k
< 4; k
++) {
if (board
[apos
+ up
] != color
|| !same_string(apos
+ up
, str
))
for (l
= 0; l
< 2; l
++) {
int right
= delta
[(k
+1)%4];
dpos
= apos
+ right
+ up
;
if (board
[cpos
] == color
&& board
[dpos
] == other
&& board
[epos
] == EMPTY
&& board
[fpos
] == EMPTY
) {
if (countlib(dpos
) == 1) {
/* Check if we have the first situation. */
if (board
[gpos
] != color
)
ADD_CANDIDATE_MOVE(fpos
, 30, *moves
, "edge_block-A");
/* Look along board edge to see if the defender's string can
for (edge_scan
= epos
; ; edge_scan
+= right
) {
if (board
[edge_scan
] == color
|| board
[edge_scan
+ up
] == color
) {
ADD_CANDIDATE_MOVE(epos
, 10, *moves
, "edge_block-B");
if (board
[edge_scan
] != EMPTY
|| board
[edge_scan
+ up
] != EMPTY
)
/* ================================================================ */
/* Defending by attacking surrounding strings */
/* ================================================================ */
/* Add the chainbreaking moves relative to the string (str) to the
break_chain_moves(int str
, struct reading_moves
*moves
)
/* Find links in atari. */
adj
= chainlinks2(str
, adjs
, 1);
for (r
= 0; r
< adj
; r
++) {
findlib(adjs
[r
], 1, &xpos
);
ADD_CANDIDATE_MOVE(xpos
, 1, *moves
, "break_chain");
/* defend_secondary_chain1_moves() tries to break a chain by defending
* "secondary chain", that is, own strings surrounding a given
* opponent string (which is in turn a chainlink for another own
* string, phew... :). It only defends own strings in atari.
* When defending is done by stretching, it is required that the defending
* stone played gets at least `min_liberties', or one less if it is
* adjacent to the opponent chainlink.
* Returns true if there where any secondary strings that needed defence
* (which does not imply they actually where defended).
defend_secondary_chain1_moves(int str
, struct reading_moves
*moves
,
int color
= OTHER_COLOR(board
[str
]);
/* Find links in atari. */
adj
= chainlinks2(str
, adjs
, 1);
for (r
= 0; r
< adj
; r
++) {
findlib(adjs
[r
], 1, &xpos
);
if (approxlib(xpos
, color
, min_liberties
, NULL
)
+ neighbor_of_string(xpos
, str
) >= min_liberties
)
ADD_CANDIDATE_MOVE(xpos
, 0, *moves
, "defend_secondary_chain1-A");
/* Capture adjacent stones in atari, if any. */
adj2
= chainlinks2(adjs
[r
], adjs2
, 1);
for (s
= 0; s
< adj2
; s
++) {
findlib(adjs2
[s
], 1, &xpos
);
if (!is_self_atari(xpos
, color
))
ADD_CANDIDATE_MOVE(xpos
, 0, *moves
, "defend_secondary_chain1-B");
/* defend_secondary_chain2_moves() tries to break a chain by defending
* "secondary chain", that is, own strings surrounding a given
* opponent string (which is in turn a chainlink for another own
* string, phew... :). It only defends own strings in
* When defending is done by stretching, it is required that the defending
* stone played gets at least `min_liberties', or one less if it is
* adjacent to the opponent chainlink. Defence can also be done by capturing
* opponent stones or trying to capture them with an atari.
defend_secondary_chain2_moves(int str
, struct reading_moves
*moves
,
int color
= OTHER_COLOR(board
[str
]);
/* Find links with two liberties. */
adj
= chainlinks2(str
, adjs
, 2);
for (r
= 0; r
< adj
; r
++) {
if (!have_common_lib(str
, adjs
[r
], NULL
))
findlib(adjs
[r
], 2, libs
);
for (t
= 0; t
< 2; t
++) {
if (approxlib(xpos
, color
, min_liberties
, NULL
)
+ neighbor_of_string(xpos
, str
) >= min_liberties
)
ADD_CANDIDATE_MOVE(xpos
, 0, *moves
, "defend_secondary_chain2-A");
/* Capture adjacent stones in atari, if any. */
adj2
= chainlinks2(adjs
[r
], adjs2
, 1);
for (s
= 0; s
< adj2
; s
++) {
findlib(adjs2
[s
], 1, &xpos
);
if (!is_self_atari(xpos
, color
))
ADD_CANDIDATE_MOVE(xpos
, 0, *moves
, "defend_secondary_chain2-B");
/* Look for neighbours we can atari. */
adj2
= chainlinks2(adjs
[r
], adjs2
, 2);
for (s
= 0; s
< adj2
; s
++) {
findlib(adjs2
[s
], 2, libs
);
for (t
= 0; t
< 2; t
++) {
/* Only atari if target has no easy escape with his other liberty. */
if (approxlib(libs
[1-t
], OTHER_COLOR(color
), 3, NULL
) < 3
&& !is_self_atari(libs
[t
], color
)) {
ADD_CANDIDATE_MOVE(libs
[t
], 0, *moves
, "defend_secondary_chain2-C");
* Find moves which immediately capture chain links with 2
* liberties, in the sense that the links cannot escape atari.
* The used heuristics are slightly sloppy, so useless moves may
* appear occasionally. This should, however, only lead to slightly
* worse performance but not to incorrect results.
break_chain2_efficient_moves(int str
, struct reading_moves
*moves
)
/* Find links with 2 liberties. */
adj
= chainlinks2(str
, adjs
, 2);
for (r
= 0; r
< adj
; r
++)
do_find_break_chain2_efficient_moves(str
, adjs
[r
], moves
);
/* Helper function for break_chain2_efficient_moves(). */
do_find_break_chain2_efficient_moves(int str
, int adj
,
struct reading_moves
*moves
)
int other
= OTHER_COLOR(color
);
int adj2
, adjs2
[MAXCHAIN
];
ASSERT1(countlib(adj
) == 2, adj
);
adj2
= chainlinks2(adj
, adjs2
, 1);
if (adj2
== 1 && countlib(str
) > 2) {
break_chain_moves(adjs2
[0], moves
);
findlib(adjs2
[0], 1, &apos
);
if (!is_self_atari(apos
, color
))
ADD_CANDIDATE_MOVE(apos
, 0, *moves
, "break_chain2_efficient-A");
if (approxlib(libs
[k
], other
, 3, NULL
) <= 2
&& !is_self_atari(libs
[1 - k
], color
))
ADD_CANDIDATE_MOVE(libs
[1 - k
], 0, *moves
, "break_chain2_efficient-B");
/* A common special case is this kind of edge position
* where a move at * is most effective for saving the two stones
* The code below tries to identify this case. We use the crude
* heuristic that the two liberties of the X stone we want to
* capture should be placed diagonally and that one liberty should
* be on the edge. Then we propose to play the other liberty.
* Notice that both moves may be proposed when attacking a stone
* Update: This was too crude. Also require that the X stone is on
* the second line and that the proposed move is not a self-atari.
if (!DIAGONAL_NEIGHBORS(libs
[0], libs
[1]))
/* Since we know that the two liberties are diagonal, the following
* construction gives the two vertices "between" the liberties.
pos1
= NORTH(gg_max(libs
[0], libs
[1]));
pos2
= SOUTH(gg_min(libs
[0], libs
[1]));
if ((board
[pos1
] != other
|| !same_string(pos1
, adj
))
|| !same_string(pos2
, adj
)))
if (is_edge_vertex(libs
[0]) && !is_self_atari(libs
[1], color
))
ADD_CANDIDATE_MOVE(libs
[1], 1, *moves
, "break_chain2_efficient-C");
if (is_edge_vertex(libs
[1]) && !is_self_atari(libs
[0], color
))
ADD_CANDIDATE_MOVE(libs
[0], 1, *moves
, "break_chain2_efficient-C");
/* (str) points to a string with two or more liberties. break_chain2_moves()
* tries to defend this string by attacking a neighbouring string with
* This is done by playing on either of its liberties
* (if (require_safe) is true these are only used if they are not
* self-ataris), taking a neighbour out of atari or by backfilling if
* both liberties are self-ataris.
break_chain2_moves(int str
, struct reading_moves
*moves
, int require_safe
,
int other
= OTHER_COLOR(color
);
adj
= chainlinks2(str
, adjs
, 2);
for (r
= 0; r
< adj
; r
++) {
int dummy_adjs
[MAXCHAIN
];
/* If stackp > backfill_depth, don't bother playing liberties of
* 2-liberty strings if those also have at least one neighbor in
* atari. This is intended to solve reading:171 and generally reduce
if (stackp
> backfill_depth
&& chainlinks2(apos
, dummy_adjs
, 1) > 0)
for (k
= 0; k
< 2; k
++) {
unsafe
[k
] = is_self_atari(libs
[k
], color
);
|| is_ko(libs
[k
], color
, NULL
)
&& approxlib(libs
[k
], other
, 5, NULL
) < 5))
ADD_CANDIDATE_MOVE(libs
[k
], 0, *moves
, "break_chain2-A");
if (stackp
<= break_chain_depth
|| (be_aggressive
&& stackp
<= backfill_depth
)) {
/* If the chain link cannot escape easily, try to defend all adjacent
* friendly stones in atari (if any). If there are none, defend
* adjacent friendly stones with only two liberties.
if (approxlib(libs
[0], other
, 4, NULL
) < 4
&& approxlib(libs
[1], other
, 4, NULL
) < 4) {
if (!defend_secondary_chain1_moves(adjs
[r
], moves
, 2))
defend_secondary_chain2_moves(adjs
[r
], moves
, 2);
if (unsafe
[0] && unsafe
[1]
&& (stackp
<= backfill2_depth
|| have_common_lib(str
, apos
, NULL
))) {
/* Find backfilling moves. */
for (k
= 0; k
< 2; k
++) {
if (approxlib(libs
[k
], other
, 3, libs2
) == 2) {
if (!is_self_atari(libs2
[0], color
))
ADD_CANDIDATE_MOVE(libs2
[0], 0, *moves
, "break_chain2-B");
if (!is_self_atari(libs2
[1], color
))
ADD_CANDIDATE_MOVE(libs2
[1], 0, *moves
, "break_chain2-B");
/* Consider this case (reading:188):
* We cannot atari the corner X string immediatly, so we need to
* backfill. However, to avoid generating too many variations,
* we require that the opponent string is well restrained.
* Otherwise it could just run away while we backfill.
if (approxlib(libs
[0], other
, 3, NULL
) <= 2
&& approxlib(libs
[1], other
, 3, NULL
) <= 2) {
if (approxlib(libs
[0], color
, 1, &lib
) == 1
&& approxlib(lib
, color
, 3, NULL
) >= 3)
ADD_CANDIDATE_MOVE(lib
, 0, *moves
, "break_chain2-C");
if (approxlib(libs
[1], color
, 1, &lib
) == 1
&& approxlib(lib
, color
, 3, NULL
) >= 3)
ADD_CANDIDATE_MOVE(lib
, 0, *moves
, "break_chain2-C");
* (str) points to a group to be defended.
* break_chain2_defense_moves is a wrapper around break_chain2_moves.
* It devalues all entries by 2.
* Rationale: Otherwise, these moves get overvalued by order_moves. In
* particular, if there is both a direct and a break_chain2 defense,
* then the latter one might be just an irrelevant intermediate forcing
* move. Hence, we should rather return the direct defense.
break_chain2_defense_moves(int str
, struct reading_moves
*moves
,
int saved_num_moves
= moves
->num
;
break_chain2_moves(str
, moves
, !(stackp
<= backfill_depth
), be_aggressive
);
for (k
= saved_num_moves
; k
< moves
->num
; k
++)
/* Helper function for break_chain3_moves() and
* superstring_break_chain_moves().
do_find_break_chain3_moves(int *chain_links
, int num_chain_links
,
struct reading_moves
*moves
, int be_aggressive
,
const char *caller_function_name
)
int other
= board
[chain_links
[0]];
int color
= OTHER_COLOR(other
);
signed char move_added
[BOARDMAX
];
int possible_moves
[MAX_MOVES
];
int num_possible_moves
= 0;
gg_assert(num_chain_links
> 0);
memset(move_added
, 0, sizeof move_added
);
for (r
= 0; r
< num_chain_links
; r
++) {
/* We make a list in the (adjs) array of the liberties
* of boundary strings having exactly three liberties. We mark
* each liberty in the mw array so that we do not list any
findlib(chain_links
[r
], 3, libs
);
/* If the 3 liberty chain easily can run away through one of the
* liberties, we don't play on any of the other liberties.
lib1
= approxlib(libs
[0], other
, 4, NULL
);
lib2
= approxlib(libs
[1], other
, 4, NULL
);
if (lib1
>= 4 && lib2
>= 4)
lib3
= approxlib(libs
[2], other
, 4, NULL
);
if ((lib1
>= 4 || lib2
>= 4) && lib3
>= 4)
if (!move_added
[libs
[0]]) {
possible_moves
[num_possible_moves
++] = libs
[0];
if (!move_added
[libs
[1]]) {
possible_moves
[num_possible_moves
++] = libs
[1];
if (!move_added
[libs
[2]]) {
possible_moves
[num_possible_moves
++] = libs
[2];
/* No easy escape, try all liberties. */
for (k
= 0; k
< 3; k
++) {
if (!move_added
[libs
[k
]]) {
possible_moves
[num_possible_moves
++] = libs
[k
];
if (stackp
<= backfill2_depth
|| (be_aggressive
&& stackp
<= backfill_depth
))
defend_secondary_chain1_moves(chain_links
[r
], moves
, 3);
for (k
= 0; k
< num_possible_moves
; k
++) {
/* We do not wish to consider the move if it can be immediately
* recaptured, unless stackp < backfill2_depth. Beyond
* backfill2_depth, the necessary capturing move might not get
* generated in follow-up for the attacker. (This currently only
* makes a difference at stackp == backfill2_depth.)
int move
= possible_moves
[k
];
if (stackp
<= break_chain_depth
|| (be_aggressive
&& stackp
<= backfill_depth
)
|| approxlib(move
, color
, 2, NULL
) > 1)
/* We use a negative initial score here as we prefer to find
ADD_CANDIDATE_MOVE(move
, -2, *moves
, caller_function_name
);
* (str) points to a group.
* If there is a string in the surrounding chain having
* exactly three liberties whose attack leads to the rescue of
* (str), break_chain3_moves(str, *moves) adds attack moves against
* the surrounding string as candidate moves.
break_chain3_moves(int str
, struct reading_moves
*moves
, int be_aggressive
)
int chain_links
[MAXCHAIN
];
int num_chain_links
= chainlinks2(str
, chain_links
, 3);
if (num_chain_links
> 0) {
do_find_break_chain3_moves(chain_links
, num_chain_links
,
moves
, be_aggressive
, "break_chain3");
* (str) points to a group.
* If there is a string in the surrounding chain having
* exactly four liberties whose attack leads to the rescue of
* (str), break_chain4_moves(str, *moves) adds attack moves against
* the surrounding string as candidate moves.
break_chain4_moves(int str
, struct reading_moves
*moves
, int be_aggressive
)
int other
= OTHER_COLOR(color
);
int possible_moves
[MAX_MOVES
];
memset(mw
, 0, sizeof(mw
));
adj
= chainlinks2(str
, adjs
, 4);
for (r
= 0; r
< adj
; r
++) {
int lib1
= 0, lib2
= 0, lib3
= 0, lib4
= 0;
/* We make a list in the (adjs) array of the liberties
* of boundary strings having exactly four liberties. We mark
* each liberty in the mw array so that we do not list any
/* If the 4 liberty chain easily can run away through one of the
* liberties, we don't play on any of the other liberties.
lib1
= approxlib(libs
[0], other
, 5, NULL
);
lib2
= approxlib(libs
[1], other
, 5, NULL
);
if (lib1
>= 5 && lib2
>= 5)
lib3
= approxlib(libs
[2], other
, 5, NULL
);
if ((lib1
>= 5 || lib2
>= 5) && lib3
>= 5)
lib4
= approxlib(libs
[3], other
, 5, NULL
);
if ((lib1
>= 5 || lib2
>= 5 || lib3
>= 5) && lib4
>= 5)
if (lib1
>= 5 && !mw
[libs
[0]]) {
possible_moves
[u
++] = libs
[0];
if (lib2
>= 5 && !mw
[libs
[1]]) {
possible_moves
[u
++] = libs
[1];
if (lib3
>= 5 && !mw
[libs
[2]]) {
possible_moves
[u
++] = libs
[2];
if (lib4
>= 5 && !mw
[libs
[3]]) {
possible_moves
[u
++] = libs
[3];
/* No easy escape, try all liberties. */
for (k
= 0; k
< 4; k
++) {
possible_moves
[u
++] = libs
[k
];
if (stackp
<= backfill2_depth
|| (be_aggressive
&& stackp
<= backfill_depth
))
defend_secondary_chain1_moves(adjs
[r
], moves
, 4);
for (v
= 0; v
< u
; v
++) {
/* We do not wish to consider the move if it can be
* immediately recaptured, unless stackp < backfill2_depth.
* Beyond backfill2_depth, the necessary capturing move might not
* get generated in follow-up for the attacker.
* (This currently only makes a difference at stackp == backfill2_depth.)
int xpos
= possible_moves
[v
];
if (stackp
<= break_chain_depth
|| (be_aggressive
&& stackp
<= backfill_depth
)
|| approxlib(xpos
, color
, 2, NULL
) > 1)
/* We use a negative initial score here as we prefer to find
ADD_CANDIDATE_MOVE(xpos
, -2, *moves
, "break_chain4");
/* This function looks for moves attacking those components
* of the surrounding chain of the superstring (see find_superstring
* for the definition) which have fewer than liberty_cap liberties,
* and which are not adjacent to the string itself, since those
* are tested by break_chain_moves.
superstring_break_chain_moves(int str
, int liberty_cap
,
struct reading_moves
*moves
)
int chain_links3
[MAXCHAIN
];
int num_chain_links3
= 0;
proper_superstring_chainlinks(str
, &adj
, adjs
, liberty_cap
);
for (k
= 0; k
< adj
; k
++) {
int liberties
= countlib(adjs
[k
]);
findlib(adjs
[k
], 1, &apos
);
ADD_CANDIDATE_MOVE(apos
, 0, *moves
, "superstring_break_chain");
do_find_break_chain2_efficient_moves(str
, adjs
[k
], moves
);
chain_links3
[num_chain_links3
++] = adjs
[k
];
if (num_chain_links3
> 0) {
do_find_break_chain3_moves(chain_links3
, num_chain_links3
,
moves
, 0, "superstring_break_chain-3");
* If `str' points to a group, double_atari_chain2_moves() adds all
* moves which make a double atari on some strings in the surrounding
* chain to the moves[] array. In addition, if `generate_more_moves'
* is set, it adds moves that make atari on a string in the
* surrounding chain and are adjacent to another string with 3
double_atari_chain2_moves(int str
, struct reading_moves
*moves
,
memset(mw
, 0, sizeof(mw
));
adj
= chainlinks2(str
, adjs
, 2);
for (r
= 0; r
< adj
; r
++) {
findlib(adjs
[r
], 2, libs
);
for (k
= 0; k
< 2; k
++) {
/* Found a double atari, but don't play there unless the move
* is safe for the defender.
if (!is_self_atari(libs
[k
], board
[str
]))
ADD_CANDIDATE_MOVE(libs
[k
], 1, *moves
, "double_atari_chain2-A");
if (generate_more_moves
) {
adj3
= chainlinks2(str
, adjs3
, 3);
for (r
= 0; r
< adj3
; r
++) {
findlib(adjs3
[r
], 3, libs
);
for (k
= 0; k
< 3; k
++) {
if (!is_self_atari(libs
[k
], board
[str
]))
ADD_CANDIDATE_MOVE(libs
[k
], -3, *moves
, "double_atari_chain2-B");
/* ================================================================ */
/* Restricted Attack and Defense */
/* ================================================================ */
/* These functions try to attack and defend a string, avoiding moves
* from a certain set. It is assumed that as soon as the string gets
* three liberties, it is alive.
* These functions can be used to generate backfilling moves as
* follows: Suppose that we would like to make atari on a
* string, but the atari is not safe until we make a backfilling
* move. To find the backfilling move, we make a list of the
* liberties of the string under attack, declaring these moves
* forbidden. Neither player will play them while the restricted
* functions are in effect. We fill the liberty, creating a
* string which is under attack, and look for a defensive move
* which avoids the forbidden moves. This is the backfilling
* These are minimalist functions capable of reading a ladder
/* Given a list of moves, restricted_defend1 tries to find a
* move that defends the string (str) with one liberty,
* not considering moves from the list.
restricted_defend1(int str
, int *move
,
int num_forbidden_moves
, int *forbidden_moves
)
int other
= OTHER_COLOR(color
);
struct reading_moves moves
;
SETUP_TRACE_INFO("restricted_defend1", str
);
ASSERT1(IS_STONE(board
[str
]), str
);
ASSERT1(countlib(str
) == 1, str
);
/* (lib) will be the liberty of the string. */
liberties
= findlib(str
, 1, &lib
);
ASSERT1(liberties
== 1, str
);
/* Collect moves to try in the first batch.
* 1. First order liberty.
* 2. Chain breaking moves.
* 3. Moves to set up a snapback.
moves
.message
[0] = "liberty";
break_chain_moves(str
, &moves
);
set_up_snapback_moves(str
, lib
, &moves
);
order_moves(str
, &moves
, color
, read_function_name
, NO_MOVE
);
for (k
= 0; k
< moves
.num
; k
++) {
if (in_list(xpos
, num_forbidden_moves
, forbidden_moves
))
/* To avoid loops with double ko, we do not allow any ko captures,
* even legal ones, if the opponent is komaster.
if (is_ko(xpos
, color
, NULL
))
if ((get_komaster() != other
|| !ko_capture
)
&& trymove(xpos
, color
, moves
.message
[k
], str
)) {
int libs
= countlib(str
);
SGFTRACE(xpos
, WIN
, "defense effective");
acode
= restricted_attack2(str
, NULL
,
num_forbidden_moves
, forbidden_moves
);
acode
= restricted_attack2(str
, NULL
,
num_forbidden_moves
, forbidden_moves
);
SGFTRACE(xpos
, WIN
, "defense effective");
/* if the move works with ko we save it, then look for something
UPDATE_SAVED_KO_RESULT(savecode
, savemove
, acode
, xpos
);
&& (get_komaster() == EMPTY
|| (get_komaster() == color
&& get_kom_pos() == xpos
))
&& is_ko(xpos
, color
, &ko_pos
)
&& tryko(xpos
, color
, "restricted_defend1-B")) {
int libs
= countlib(str
);
UPDATE_SAVED_KO_RESULT(savecode
, savemove
, 2, xpos
);
acode
= restricted_attack2(str
, NULL
,
num_forbidden_moves
, forbidden_moves
);
UPDATE_SAVED_KO_RESULT(savecode
, savemove
, acode
, xpos
);
SGFTRACE(savemove
, savecode
, "saved move");
/* Given a list of moves, restricted_attack2 tries to find a
* move that attacks the string (str) with two liberties,
* not considering moves from the list.
restricted_attack2(int str
, int *move
,
int num_forbidden_moves
, int *forbidden_moves
)
int other
= OTHER_COLOR(color
);
SETUP_TRACE_INFO("restricted_attack2", str
);
ASSERT1(IS_STONE(board
[str
]), str
);
ASSERT1(countlib(str
) == 2, str
);
/* The attack may fail if a boundary string is in atari and cannot
* be defended. First we must try defending such a string.
/* Get the two liberties of (str). */
liberties
= findlib(str
, 2, libs
);
ASSERT1(liberties
== 2, str
);
for (k
= 0; k
< 2; k
++) {
if (in_list(apos
, num_forbidden_moves
, forbidden_moves
))
/* To avoid loops with double ko, we do not allow any ko captures,
* even legal ones, if the opponent is komaster.
if (is_ko(apos
, other
, &ko_pos
))
if ((get_komaster() != color
|| !ko_capture
)
&& trymove(apos
, other
, "restricted_attack2", str
)) {
&& !restricted_defend1(str
, NULL
,
num_forbidden_moves
, forbidden_moves
))
&& !restricted_defend1(str
, NULL
,
num_forbidden_moves
, forbidden_moves
))) {
SGFTRACE(apos
, WIN
, "attack effective");
&& (get_komaster() == EMPTY
|| (get_komaster() == other
&& get_kom_pos() == apos
))
&& tryko(apos
, other
, "restricted_attack2")) {
if (!restricted_defend1(str
, NULL
,
num_forbidden_moves
, forbidden_moves
)) {
SGFTRACE(savemove
, savecode
, "saved move");
* Returns true if the move is in a given list of moves.
in_list(int move
, int num_moves
, int *moves
)
for (k
= 0; k
< num_moves
; k
++)
/* ================================================================ */
/* ================================================================ */
/* Parameters used in the ordering of moves to try in the tactical
static int defend_lib_score
[6] = {-5, -4, 0, 3, 5, 50};
static int defend_not_adjacent_lib_score
[5] = { 0, 0, 2, 3, 5};
static int defend_capture_score
[6] = { 0, 6, 9, 13, 18, 24};
static int defend_atari_score
[6] = { 0, 2, 4, 6, 7, 8};
static int defend_save_score
[6] = { 0, 3, 6, 8, 10, 12};
static int defend_open_score
[5] = { 0, 1, 2, 3, 4};
static int attack_own_lib_score
[5] = {10, -4, 2, 3, 4};
static int attack_string_lib_score
[6] = {-5, 2, 3, 7, 10, 19};
static int attack_capture_score
[6] = {-4, 4, 10, 15, 20, 25};
static int attack_save_score
[6] = { 0, 10, 13, 18, 21, 24};
static int attack_open_score
[5] = { 0, 0, 2, 4, 4};
static int defend_not_edge_score
= 5;
static int attack_not_edge_score
= 1;
static int attack_ko_score
= -15;
static int cannot_defend_penalty
= -20;
static int safe_atari_score
= 8;
sgf_dumpmoves(struct reading_moves
*moves
, const char *funcname
)
sprintf(buf
, "Move order for %s: %n", funcname
, &chars
);
for (i
= moves
->num_tried
; i
< moves
->num
; i
++) {
sprintf(pos
, "%c%d (%d) %n",
J(moves
->pos
[i
]) + 'A' + (J(moves
->pos
[i
]) >= 8),
board_size
- I(moves
->pos
[i
]), moves
->score
[i
], &chars
);
sgftreeAddComment(sgf_dumptree
, buf
);
/* The string at (str) is under attack. The moves.num moves in
* (moves) for color have been deemed interesting in
* the attack or defense of the group. Most of these moves will be
* immediate liberties of the group.
* This function orders the moves in the order where the move most
* likely to succeed to attack or defend the string will be first and
* Currently, this is defined as:
* 1) Moves which let the defending string get more liberties are more
* 2) Moves adjacent to the most open liberties are more
* interesting than those with fewer open liberties.
* 3) Moves on the edge are less interesting.
* Moves below first_move are ignored and assumed to be sorted already.
order_moves(int str
, struct reading_moves
*moves
, int color
,
const char *funcname
, int killer
)
int string_color
= board
[str
];
int string_libs
= countlib(str
);
/* Don't bother sorting if only one move, or none at all. */
if (moves
->num
- moves
->num_tried
< 2) {
/* But let's still have a single candidate in the sgf output */
if (sgf_dumptree
&& moves
->num
> moves
->num_tried
)
sgf_dumpmoves(moves
, funcname
);
/* Assign a score to each move. */
for (r
= moves
->num_tried
; r
< moves
->num
; r
++) {
int move
= moves
->pos
[r
];
/* Look at the neighbors of this move and count the things we
* find. Friendly and opponent stones are related to color, i.e.
* the player to move, not to the color of the string.
int number_edges
= 0; /* outside board */
int number_same_string
= 0; /* the string being attacked */
int number_own
= 0; /* friendly stone */
int number_opponent
= 0; /* opponent stone */
int captured_stones
= 0; /* number of stones captured by this move */
int threatened_stones
= 0; /* number of stones threatened by this move */
int saved_stones
= 0; /* number of stones in atari saved */
int number_open
= 0; /* empty intersection */
/* We let the incremental_board code do the heavy work. */
incremental_order_moves(move
, color
, str
, &number_edges
,
&number_same_string
, &number_own
,
&number_opponent
, &captured_stones
,
&threatened_stones
, &saved_stones
, &number_open
);
gprintf("%o %1m values: %d %d %d %d %d %d %d %d\n", move
, number_edges
,
number_same_string
, number_own
, number_opponent
, captured_stones
,
threatened_stones
, saved_stones
, number_open
);
/* Different score strategies depending on whether the move is
* attacking or defending the string.
if (color
== string_color
) {
* 1) Add twice the number of liberties the group receives by
* extending to the intersection of the move, if more than one.
* Only applicable if the move is adjacent to the group.
int libs
= approxlib(move
, color
, 10, NULL
);
if (number_same_string
> 0) {
if (libs
> 5 || (libs
== 4 && stackp
> fourlib_depth
))
moves
->score
[r
] += defend_lib_score
[5] + (libs
- 4);
moves
->score
[r
] += defend_lib_score
[libs
];
/* Add points for the number of liberties the played stone
* obtains when not adjacent to the attacked string.
moves
->score
[r
] += defend_not_adjacent_lib_score
[4];
moves
->score
[r
] += defend_not_adjacent_lib_score
[libs
];
/* 2) Add the number of open liberties near the move to its score. */
gg_assert(number_open
<= 4);
moves
->score
[r
] += defend_open_score
[number_open
];
/* 3) Add a bonus if the move is not on the edge.
if (number_edges
== 0 || captured_stones
> 0)
moves
->score
[r
] += defend_not_edge_score
;
/* 4) Add thrice the number of captured stones. */
if (captured_stones
<= 5)
moves
->score
[r
] += defend_capture_score
[captured_stones
];
moves
->score
[r
] += defend_capture_score
[5] + captured_stones
;
/* 5) Add points for stones put into atari, unless this is a
if (libs
+ captured_stones
> 1) {
if (threatened_stones
<= 5)
moves
->score
[r
] += defend_atari_score
[threatened_stones
];
moves
->score
[r
] += defend_atari_score
[5] + threatened_stones
;
/* 6) Add a bonus for saved stones. */
moves
->score
[r
] += defend_save_score
[saved_stones
];
moves
->score
[r
] += defend_save_score
[5];
* 1) Add the number of liberties the attacker gets when playing
* there, but never more than four.
int libs
= approxlib(move
, color
, 4, NULL
);
moves
->score
[r
] += attack_own_lib_score
[libs
];
if (libs
== 0 && captured_stones
== 1)
moves
->score
[r
] += attack_ko_score
;
/* 2) If the move is not a self atari and adjacent to the
* string, add the number of liberties the opponent would
* gain by playing there. If the string has two liberties,
* self-ataris are also ok since they may be snapbacks, but
* only if a single stone is sacrificed.
if ((libs
+ captured_stones
> 1 || (string_libs
<= 2 && number_own
== 0))
&& number_same_string
> 0) {
int liberties
= approxlib(move
, string_color
, 5, NULL
);
if (liberties
> 5 || (liberties
== 4 && stackp
> fourlib_depth
))
moves
->score
[r
] += attack_string_lib_score
[liberties
];
safe_atari
= (string_libs
<= 2 && libs
+ captured_stones
> 1);
/* The defender can't play here without getting into atari, so
* we probably souldn't either.
if (liberties
== 1 && saved_stones
== 0 && !safe_atari
)
moves
->score
[r
] += cannot_defend_penalty
;
/* Bonus if we put the attacked string into atari without
* ourselves getting into atari.
moves
->score
[r
] += safe_atari_score
;
/* 3) Add the number of open liberties near the move to its score. */
gg_assert(number_open
<= 4);
moves
->score
[r
] += attack_open_score
[number_open
];
/* 4) Add a bonus if the move is not on the edge. */
moves
->score
[r
] += attack_not_edge_score
;
/* 5) Add twice the number of captured stones. */
if (captured_stones
<= 5)
moves
->score
[r
] += attack_capture_score
[captured_stones
];
moves
->score
[r
] += attack_capture_score
[5];
/* 6) Add a bonus for saved stones. */
moves
->score
[r
] += attack_save_score
[saved_stones
];
moves
->score
[r
] += attack_save_score
[5];
if (moves
->pos
[r
] == killer
)
/* Now sort the moves. We use selection sort since this array will
* probably never be more than 10 moves long. In this case, the
* overhead imposed by quicksort will probably overshadow the gains
* given by the O(n*log(n)) behaviour over the O(n^2) behaviour of
for (i
= moves
->num_tried
; i
< moves
->num
-1; i
++) {
int maxscore
= moves
->score
[i
];
int max_at
= 0; /* This is slightly faster than max_at = i. */
/* Find the move with the biggest score. */
for (j
= i
+ 1; j
< moves
->num
; j
++) {
if (moves
->score
[j
] > maxscore
) {
maxscore
= moves
->score
[j
];
/* Now exchange the move at i with the move at max_at.
* Don't forget to exchange the scores as well.
int temp
= moves
->pos
[max_at
];
const char *temp_message
= moves
->message
[max_at
];
moves
->pos
[max_at
] = moves
->pos
[i
];
moves
->score
[max_at
] = moves
->score
[i
];
moves
->message
[max_at
] = moves
->message
[i
];
moves
->score
[i
] = maxscore
;
moves
->message
[i
] = temp_message
;
gprintf("%oVariation %d:\n", count_variations
);
for (i
= moves
->num_tried
; i
< moves
->num
; i
++)
gprintf("%o %1M %d\n", moves
->pos
[i
], moves
->score
[i
]);
sgf_dumpmoves(moves
, funcname
);
/* Set new values for the move ordering parameters. */
tune_move_ordering(int params
[MOVE_ORDERING_PARAMETERS
])
for (k
= 0; k
< 6; k
++) {
defend_lib_score
[k
] = params
[k
];
defend_not_adjacent_lib_score
[k
] = params
[k
+ 6];
defend_capture_score
[k
] = params
[k
+ 11];
defend_atari_score
[k
] = params
[k
+ 17];
defend_save_score
[k
] = params
[k
+ 23];
defend_open_score
[k
] = params
[k
+ 29];
attack_own_lib_score
[k
] = params
[k
+ 34];
attack_string_lib_score
[k
] = params
[k
+ 39];
attack_capture_score
[k
] = params
[k
+ 45];
attack_save_score
[k
] = params
[k
+ 51];
attack_open_score
[k
] = params
[k
+ 57];
defend_not_edge_score
= params
[62];
attack_not_edge_score
= params
[63];
attack_ko_score
= params
[64];
cannot_defend_penalty
= params
[65];
safe_atari_score
= params
[66];
gprintf("static int defend_lib_score[6] = {%d, %d, %d, %d, %d, %d};\n",
defend_lib_score
[0], defend_lib_score
[1],
defend_lib_score
[2], defend_lib_score
[3],
defend_lib_score
[4], defend_lib_score
[5]);
gprintf("static int defend_not_adjacent_lib_score[5] = {%d, %d, %d, %d, %d};\n",
defend_not_adjacent_lib_score
[0], defend_not_adjacent_lib_score
[1],
defend_not_adjacent_lib_score
[2], defend_not_adjacent_lib_score
[3],
defend_not_adjacent_lib_score
[4]);
gprintf("static int defend_capture_score[6] = {%d, %d, %d, %d, %d, %d};\n",
defend_capture_score
[0], defend_capture_score
[1],
defend_capture_score
[2], defend_capture_score
[3],
defend_capture_score
[4], defend_capture_score
[5]);
gprintf("static int defend_atari_score[6] = {%d, %d, %d, %d, %d, %d};\n",
defend_atari_score
[0], defend_atari_score
[1],
defend_atari_score
[2], defend_atari_score
[3],
defend_atari_score
[4], defend_atari_score
[5]);
gprintf("static int defend_save_score[6] = {%d, %d, %d, %d, %d, %d};\n",
defend_save_score
[0], defend_save_score
[1],
defend_save_score
[2], defend_save_score
[3],
defend_save_score
[4], defend_save_score
[5]);
gprintf("static int defend_open_score[5] = {%d, %d, %d, %d, %d};\n",
defend_open_score
[0], defend_open_score
[1],
defend_open_score
[2], defend_open_score
[3],
gprintf("static int attack_own_lib_score[5] = {%d, %d, %d, %d, %d};\n",
attack_own_lib_score
[0], attack_own_lib_score
[1],
attack_own_lib_score
[2], attack_own_lib_score
[3],
attack_own_lib_score
[4]);
gprintf("static int attack_string_lib_score[6] = {%d, %d, %d, %d, %d, %d};\n",
attack_string_lib_score
[0], attack_string_lib_score
[1],
attack_string_lib_score
[2], attack_string_lib_score
[3],
attack_string_lib_score
[4], attack_string_lib_score
[5]);
gprintf("static int attack_capture_score[6] = {%d, %d, %d, %d, %d, %d};\n",
attack_capture_score
[0], attack_capture_score
[1],
attack_capture_score
[2], attack_capture_score
[3],
attack_capture_score
[4], attack_capture_score
[5]);
gprintf("static int attack_save_score[6] = {%d, %d, %d, %d, %d, %d};\n",
attack_save_score
[0], attack_save_score
[1],
attack_save_score
[2], attack_save_score
[3],
attack_save_score
[4], attack_save_score
[5]);
gprintf("static int attack_open_score[5] = {%d, %d, %d, %d, %d};\n",
attack_open_score
[0], attack_open_score
[1],
attack_open_score
[2], attack_open_score
[3],
gprintf("static int defend_not_edge_score = %d;\n", defend_not_edge_score
);
gprintf("static int attack_not_edge_score = %d;\n", attack_not_edge_score
);
gprintf("static int attack_ko_score = %d;\n", attack_ko_score
);
gprintf("static int cannot_defend_penalty = %d;\n", cannot_defend_penalty
);
gprintf("static int safe_atari_score = %d;\n", safe_atari_score
);
/* ================================================================ */
/* ================================================================ */
static int safe_move_cache
[BOARDMAX
][2];
static int safe_move_cache_when
[BOARDMAX
][2];
static void clear_safe_move_cache(void);
clear_safe_move_cache(void)
for (k
= BOARDMIN
; k
< BOARDMAX
; k
++) {
safe_move_cache_when
[k
][0] = -1;
safe_move_cache_when
[k
][1] = -1;
/* safe_move(move, color) checks whether a move at (move) is illegal
* or can immediately be captured. If stackp==0 the result is cached.
* If the move only can be captured by a ko, it's considered safe.
* This may or may not be a good convention.
* For performance reasons, the result of this function is cached.
safe_move(int move
, int color
)
static int initialized
= 0;
/* If we have this position cached, use the previous value.
* Only use cached values when stackp is 0 and reading is not being done
&& safe_move_cache_when
[move
][color
== BLACK
] == position_number
)
return safe_move_cache
[move
][color
== BLACK
];
/* Otherwise calculate the value... */
if (komaster_trymove(move
, color
, "safe_move", 0, &ko_move
, 1)) {
safe
= REVERSE_RESULT(attack(move
, NULL
));
if (ko_move
&& safe
!= 0)
/* ...and store it in the cache.
* FIXME: Only store result in cache when we're working at
* Comment: This is currently not a problem since no reduced depth
if (stackp
== 0 && depth_offset
== 0) {
gprintf("Safe move at %1m for %s cached when depth=%d, position number=%d\n",
move
, color_to_string(color
), depth
, position_number
);
safe_move_cache_when
[move
][color
== BLACK
] = position_number
;
safe_move_cache
[move
][color
== BLACK
] = safe
;
/* Checks if a move by color makes an opponent move at pos a self atari.
does_secure(int color
, int move
, int pos
)
if (trymove(move
, color
, NULL
, NO_MOVE
)) {
if (is_self_atari(pos
, OTHER_COLOR(color
)))
/* ===================== Statistics ============================= */
reset_reading_node_counter()
reading_node_counter
= 0;
/* Retrieve statistics. */
get_reading_node_counter()
return reading_node_counter
;
/* ============ Reading shadow =============== */
/* Draw the reading shadow, for debugging purposes */
for (i
= 0; i
< board_size
; i
++) {
fprintf(stderr
, "\n%2d", board_size
- i
);
for (j
= 0; j
< board_size
; j
++) {
if (!shadow
[pos
] && board
[pos
] == EMPTY
)
else if (!shadow
[pos
] && board
[pos
] == WHITE
)
else if (!shadow
[pos
] && board
[pos
] == BLACK
)
if (shadow
[pos
] && board
[pos
] == EMPTY
)
else if (shadow
[pos
] && board
[pos
] == WHITE
)
else if (shadow
[pos
] && board
[pos
] == BLACK
)
fprintf(stderr
, " %c", c
);
fprintf(stderr
, " %d", board_size
- i
);
/* ================================================================ */
/* Code for special purposes. */
/* ================================================================ */
/* simple_ladder(str, &move) tries to capture a string (str)
* with exactly two liberties under simplified assumptions, which are
* adequate in a ladder. The rules are as follows:
* 1. The attacker is allowed to play at each of the two liberties,
* but no other move. If the move was legal, the string now has
* 2. The defender must move out of atari. This can only be done by
* either extending at the liberty or capturing a neighboring
* string which was in atari. All such moves may be tested.
* 3. Depending on the resulting number of liberties of the string
* after the defender's move, we value each node as follows:
* 3 or more liberties: the attack has failed
* 1 liberty: the attack has succeeded
* illegal move for the defender: successful attack
* illegal move for the attacker: failed attack
* Return codes are as usual 0 for failure, WIN for success, KO_A for
* a ko where the defender must make the first ko threat and KO_B for
* a ko where the attacked has to make the first threat. If the attack
* was successful, (*move) contains the attacking move, unless it is a
* The differences compared to the attack2()/defend1() combination for
* reading ladders is that this one is a strict ladder reader which
* never allows the defender to have more than one liberty when it's
* in turn to move. This has a number of consequences.
* 1. This function will miss tactical captures involving other
* techniques than the ladder.
* 2. This function is faster because it gives up faster when the
* ladder doesn't work. In particular it can't branch out in a huge
* tree of exotic variations.
* 3. This function always reads ladders to the very end. There are no
* depth limits or other assumptions to stop reading prematurely.
* 4. If this function returns WIN, it is guaranteed that the defender
* has no way whatsoever to escape, all possibilities are tried.
* The converse is definitely not true.
simple_ladder(int str
, int *move
)
int other
= OTHER_COLOR(color
);
struct reading_moves moves
;
SETUP_TRACE_INFO("simple_ladder", str
);
ASSERT1(IS_STONE(board
[str
]), str
);
ASSERT1(countlib(str
) == 2, str
);
/* Give up if we attacked depending on ko for too long. */
if (stackp
> depth
+ 20 && get_komaster() == OTHER_COLOR(board
[str
])) {
/* Get the two liberties of (str). */
/* If the defender can get enough liberties by playing one of these
* two, then we have no choice but to block there and consequently,
* it is unnecesary to try the other liberty.
if (approxlib(libs
[0], color
, 4, NULL
) <= 3)
ADD_CANDIDATE_MOVE(libs
[1], 0, moves
, "simple_ladder");
if (approxlib(libs
[1], color
, 4, NULL
) <= 3)
ADD_CANDIDATE_MOVE(libs
[0], 0, moves
, "simple_ladder");
order_moves(str
, &moves
, other
, read_function_name
, NO_MOVE
);
for (k
= 0; k
< moves
.num
; k
++) {
if (komaster_trymove(apos
, other
, moves
.message
[k
], str
,
&ko_move
, savecode
== 0)) {
dcode
= simple_ladder_defend(str
, NULL
);
SGFTRACE(apos
, WIN
, "attack effective");
UPDATE_SAVED_KO_RESULT(savecode
, savemove
, dcode
, apos
);
if (simple_ladder_defend(str
, NULL
) != WIN
) {
RETURN_RESULT(savecode
, savemove
, move
, "saved move");
simple_ladder_defend(int str
, int *move
)
struct reading_moves moves
;
SETUP_TRACE_INFO("simple_ladder_defend", str
);
ASSERT1(IS_STONE(board
[str
]), str
);
ASSERT1(countlib(str
) == 1, str
);
/* lib will be the liberty of the string. */
moves
.message
[0] = "liberty";
break_chain_moves(str
, &moves
);
order_moves(str
, &moves
, color
, read_function_name
, NO_MOVE
);
for (k
= 0; k
< moves
.num
; k
++) {
if (komaster_trymove(xpos
, color
, moves
.message
[k
], str
,
&ko_move
, savecode
== 0)) {
int new_libs
= countlib(str
);
acode
= simple_ladder(str
, NULL
);
CHECK_RESULT(savecode
, savemove
, acode
, xpos
, move
,
RETURN_RESULT(savecode
, savemove
, move
, "saved move");