/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* 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. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
* Change the status of all the stones in the dragon at (dr).
change_dragon_status(int dr
, enum dragon_status status
)
int origin
= dragon
[dr
].origin
;
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (dragon
[pos
].origin
== origin
)
dragon
[pos
].status
= status
;
* Check whether a move at (move) stops the enemy from playing at (apos).
defend_against(int move
, int color
, int apos
)
if (trymove(move
, color
, "defend_against", NO_MOVE
)) {
if (safe_move(apos
, OTHER_COLOR(color
)) == 0) {
* Returns true if color can cut at (pos), or if connection through (pos)
* is inhibited. This information is collected by find_cuts(), using the B
* patterns in the connections database.
cut_possible(int pos
, int color
)
return (cutting_points
[pos
] & OTHER_COLOR(color
)) != 0;
* does_attack(move, str) returns the result code for an attack on the
* string 'str' by the move 'move'. However, if the move does not
* improve the attack result compared to tenuki, 0 is returned. In
* particular if the string is already captured, does_attack() always
does_attack(int move
, int str
)
int other
= OTHER_COLOR(color
);
attack_and_defend(str
, &acode
, NULL
, &dcode
, &spos
);
if (acode
!= 0 && dcode
== 0)
if (trymove(move
, other
, "does_attack-A", str
)) {
result
= REVERSE_RESULT(find_defense(str
, NULL
));
if (spos
!= NO_MOVE
&& trymove(spos
, color
, "does_attack-B", str
)) {
int new_result
= attack(str
, NULL
);
* does_defend(move, str) returns true if the move at (move)
* defends (str). This means that it defends the string, and that
* (str) can be captured if no defense is made.
* FIXME: Make does_defend() ko aware like does_attack().
does_defend(int move
, int str
)
int other
= OTHER_COLOR(color
);
gg_assert(spos
!= NO_MOVE
);
if (trymove(move
, color
, "does_defend-A", str
)) {
if (!attack(str
, NULL
)) {
if (trymove(spos
, other
, "does_defend-B", str
)) {
if (!board
[str
] || !find_defense(str
, NULL
))
* Example: somewhere(WHITE, 2, apos, bpos, cpos).
* Returns true if one of the vertices listed
* satisfies board[pos]==color. Here num_moves is the
* number of moves. If check_alive is true, the dragon is not allowed
* to be dead. This check is only valid if stackp==0.
somewhere(int color
, int check_alive
, int num_moves
, ...)
gg_assert(stackp
== 0 || !check_alive
);
for (k
= 0; k
< num_moves
; k
++) {
&& (!check_alive
|| dragon
[pos
].status
!= DEAD
)) {
/* Search along the edge for the first visible stone. Start at apos
* and move in the direction of bpos. Return 1 if the first visible
* stone is of the given color. It is required that apos and bpos are
* at the same distance from the edge.
* FIXME: The detection of the first visible stone is quite crude and
* probably needs to be improved.
visible_along_edge(int color
, int apos
, int bpos
)
ASSERT1((ai
== bi
) ^ (aj
== bj
), apos
);
pos
= POS(board_size
- 1, bj
);
pos
= POS(bi
, board_size
- 1);
for (; ON_BOARD(pos
); pos
+= forward
) {
for (k
= 4; k
>= 0; k
--) {
ASSERT_ON_BOARD1(pos
+ k
* up
);
if (board
[pos
+ k
* up
] == color
)
else if (board
[pos
+ k
* up
] == OTHER_COLOR(color
))
/* Is the board symmetric (or rather antisymmetric) with respect to
* mirroring in tengen after a specific move has been played? If the
* move is PASS_MOVE, check the current board.
* If strict is set we require that each stone is matched by a stone
* of the opposite color at the mirrored vertex. Otherwise we only
* require that each stone is matched by a stone of either color.
test_symmetry_after_move(int move
, int color
, int strict
)
if (board
[move
] != EMPTY
)
if (!trymove(move
, color
, "find_mirror_move", NO_MOVE
))
for (pos
= BOARDMIN
; pos
< MIRROR_MOVE(pos
); pos
++) {
sum
= board
[pos
] + board
[MIRROR_MOVE(pos
)];
if (sum
!= EMPTY
+ EMPTY
&& sum
!= BLACK
+ WHITE
) {
if (strict
|| sum
== EMPTY
+ WHITE
|| sum
== EMPTY
+ BLACK
) {
/* The function play_break_through_n() plays a sequence of moves,
* alternating between the players and starting with color. After
* having played through the sequence, the three last coordinate pairs
* gives a position to be analyzed by break_through(), to see whether
* either color has managed to enclose some stones and/or connected
* his own stones. If any of the three last positions is empty, it's
* assumed that the enclosure has failed, as well as the attempt to
* If one or more of the moves to play turns out to be illegal for
* some reason, the rest of the sequence is played anyway, and
* break_through() is called as if nothing special happened.
* Like break_through(), this function returns 1 if the attempt to
* break through was succesful and 2 if it only managed to cut
play_break_through_n(int color
, int num_moves
, ...)
/* Do all the moves with alternating colors. */
for (i
= 0; i
< num_moves
; i
++) {
&& (trymove(apos
, mcolor
, "play_break_through_n", NO_MOVE
)
|| tryko(apos
, mcolor
, "play_break_through_n")))
mcolor
= OTHER_COLOR(mcolor
);
/* Now do the real work. */
/* Temporarily increase the depth values with the number of explicitly
modify_depth_values(played_moves
);
success
= break_through(xpos
, ypos
, zpos
);
modify_depth_values(-played_moves
);
/* Pop all the moves we could successfully play. */
for (i
= 0; i
< played_moves
; i
++)
/* The function play_attack_defend_n() plays a sequence of moves,
* alternating between the players and starting with color. After
* having played through the sequence, the last coordinate pair gives
* a target to attack or defend, depending on the value of do_attack.
* If there is no stone present to attack or defend, it is assumed
* that it has already been captured. If one or more of the moves to
* play turns out to be illegal for some reason, the rest of the
* sequence is played anyway, and attack/defense is tested as if
* nothing special happened.
* A typical use for these functions is to set up a ladder in an
* autohelper and see whether it works or not.
play_attack_defend_n(int color
, int do_attack
, int num_moves
, ...)
/* Do all the moves with alternating colors. */
for (i
= 0; i
< num_moves
; i
++) {
&& (trymove(apos
, mcolor
, "play_attack_defend_n", NO_MOVE
)
|| tryko(apos
, mcolor
, "play_attack_defend_n")))
mcolor
= OTHER_COLOR(mcolor
);
/* Now do the real work. */
/* Temporarily increase the depth values with the number of explicitly
* This improves the reading of pattern constraints but
* unfortunately tends to be too expensive. For the time being it is
modify_depth_values(played_moves
);
if (board
[zpos
] == EMPTY
)
success
= attack(zpos
, NULL
);
if (board
[zpos
] == EMPTY
)
int dcode
= find_defense(zpos
, NULL
);
if (dcode
== 0 && !attack(zpos
, NULL
))
modify_depth_values(-played_moves
);
/* Pop all the moves we could successfully play. */
for (i
= 0; i
< played_moves
; i
++)
/* The function play_attack_defend2_n() plays a sequence of moves,
* alternating between the players and starting with color. After
* having played through the sequence, the two last coordinate pairs
* give two targets to simultaneously attack or defend, depending on
* the value of do_attack. If there is no stone present to attack or
* defend, it is assumed that it has already been captured. If one or
* more of the moves to play turns out to be illegal for some reason,
* the rest of the sequence is played anyway, and attack/defense is
* tested as if nothing special happened.
* A typical use for these functions is to set up a crosscut in an
* autohelper and see whether at least one cutting stone can be
play_attack_defend2_n(int color
, int do_attack
, int num_moves
, ...)
/* Do all the moves with alternating colors. */
for (i
= 0; i
< num_moves
; i
++) {
&& (trymove(apos
, mcolor
, "play_attack_defend_n", NO_MOVE
)
|| tryko(apos
, mcolor
, "play_attack_defend_n")))
mcolor
= OTHER_COLOR(mcolor
);
/* Now do the real work. */
/* Temporarily increase the depth values with the number of explicitly
modify_depth_values(played_moves
);
/* FIXED: tm - returns ko results correctly (3.1.22) */
if (board
[ypos
] == EMPTY
|| board
[zpos
] == EMPTY
)
success
= attack_either(ypos
, zpos
);
if (board
[ypos
] == EMPTY
|| board
[zpos
] == EMPTY
)
success
= defend_both(ypos
, zpos
);
modify_depth_values(-played_moves
);
/* Pop all the moves we could successfully play. */
for (i
= 0; i
< played_moves
; i
++)
/* The function play_connect_n() plays a sequence of moves,
* alternating between the players and starting with color. After
* having played through the sequence, the two last coordinates
* give two targets that should be connected or disconnected, depending on
* the value of do_connect. If there is no stone present to connect or
* disconnect, it is assumed that the connection has failed. If one or
* more of the moves to play turns out to be illegal for some reason,
* the rest of the sequence is played anyway, and connection/disconnection
* is tested as if nothing special happened.
play_connect_n(int color
, int do_connect
, int num_moves
, ...)
/* Do all the moves with alternating colors. */
for (i
= 0; i
< num_moves
; i
++) {
&& (trymove(apos
, mcolor
, "play_connect_n", NO_MOVE
)
|| tryko(apos
, mcolor
, "play_connect_n")))
mcolor
= OTHER_COLOR(mcolor
);
/* Now do the real work. */
/* Temporarily increase the depth values with the number of explicitly
* This improves the reading of pattern constraints but
* unfortunately tends to be too expensive. For the time being it is
modify_depth_values(played_moves
);
/* See if ypos and zpos can be connected (or disconnected). */
if (board
[ypos
] == EMPTY
|| board
[zpos
] == EMPTY
)
success
= string_connect(ypos
, zpos
, NULL
);
if (board
[ypos
] == EMPTY
|| board
[zpos
] == EMPTY
)
success
= disconnect(ypos
, zpos
, NULL
);
modify_depth_values(-played_moves
);
/* Pop all the moves we could successfully play. */
for (i
= 0; i
< played_moves
; i
++)
/* The function play_lib_n() plays a sequence of moves, alternating
* between the players and starting with color. After having played
* through the sequence, the last coordinate gives a target for liberty
* counting. The number of liberties is returned.
* If only one move is to be played and that stone is the target,
* accuratelib (or approxlib if appropriate) is more efficient.
play_lib_n(int color
, int num_moves
, ...)
/* Do all the moves with alternating colors. */
for (i
= 0; i
< num_moves
; i
++) {
&& (trymove(apos
, mcolor
, "play_connect_n", NO_MOVE
)
|| tryko(apos
, mcolor
, "play_connect_n")))
mcolor
= OTHER_COLOR(mcolor
);
/* Now do the real work. */
if (board
[ypos
] == EMPTY
)
/* Pop all the moves we could successfully play. */
for (i
= 0; i
< played_moves
; i
++)
* It is assumed in reading a ladder if stackp >= depth that
* as soon as a bounding stone is in atari, the string is safe.
* It is used similarly at other places in reading.c to implement simplifying
* assumptions when stackp is large. DEPTH is the default value of depth.
* Unfortunately any such scheme invites the ``horizon effect.'' Increasing
* DEPTH will make the program stronger and slower.
/* Tactical reading using C functions */
#define BACKFILL_DEPTH 12
#define BACKFILL2_DEPTH 5
#define BREAK_CHAIN_DEPTH 7
#define SUPERSTRING_DEPTH 7
/* Pattern based reading */
#define OWL_DISTRUST_DEPTH 6
#define OWL_BRANCH_DEPTH 8
#define OWL_READING_DEPTH 20
#define SEMEAI_BRANCH_DEPTH 12
#define SEMEAI_BRANCH_DEPTH2 6
#define CONNECT_NODE_LIMIT 2000
#define CONNECT_DEPTH2 20
#define BREAKIN_NODE_LIMIT 400
/* Set the various reading depth parameters. If mandated_depth_value
* is not -1 that value is used; otherwise the depth values are
* set as a function of level. The parameter mandated_depth_value
* can be set at the command line to force a particular value of
* depth; normally it is -1.
set_depth_values(int level
, int report_levels
)
static int node_limits
[] = {500, 500, 450, 400, 400, 325, 275,
* Other policies depending on level:
* owl.c: >= 9: use vital attack pattern database
* >= 8: increase depth values in owl_substantial
* >= 8: don't turn off owl_phase in semeai reading
* reading.c: >= 8: Use superstrings and do more backfilling.
* value_moves.c: >= 6: try to find more owl attacks/defenses
* breakin.c: >= 10: try to find break-ins. (*)
* worm.c: >= 10: detect unconditionally meaningless moves
* The break-in code (*) is particularly expensive.
* Speedups between levels 9 and 10 and between levels 7 and 8
* are obtained by turning off services, and between these
* levels no changes are made in the depths. The parameter
* depth_level is the correction compared to the default settings at level
* 10 for most reading depths.
depth_level
= level
- 10;
depth
= gg_max(6, DEPTH
+ depth_level
);
branch_depth
= gg_max(3, BRANCH_DEPTH
+ depth_level
);
backfill_depth
= gg_max(2, BACKFILL_DEPTH
+ depth_level
);
backfill2_depth
= gg_max(1, BACKFILL2_DEPTH
+ depth_level
);
break_chain_depth
= gg_max(2, BREAK_CHAIN_DEPTH
+ depth_level
);
owl_distrust_depth
= gg_max(1, (2 * OWL_DISTRUST_DEPTH
+ depth_level
) / 2);
owl_distrust_depth
= gg_max(1, (2 * OWL_DISTRUST_DEPTH
- 1
owl_branch_depth
= gg_max(2, (2 * OWL_BRANCH_DEPTH
+ depth_level
) / 2);
owl_reading_depth
= gg_max(5, (2 * OWL_READING_DEPTH
+ depth_level
) / 2);
/* Atari-atari depth levels are unchanged only between levels 7/8, 9/10: */
aa_depth
= gg_max(0, AA_DEPTH
+ (level
- 10));
aa_depth
= gg_max(0, AA_DEPTH
);
aa_depth
= gg_max(0, AA_DEPTH
- 1);
aa_depth
= gg_max(0, AA_DEPTH
- (8 - level
));
* fourlib_depth: This is constant from levels 7 to 10.
* superstring_depth: set to 0 below level 8.
ko_depth
= gg_max(1, KO_DEPTH
+ (level
- 10));
ko_depth
= gg_max(1, KO_DEPTH
);
ko_depth
= gg_max(1, KO_DEPTH
- 1);
ko_depth
= gg_max(1, KO_DEPTH
+ (level
- 8));
fourlib_depth
= gg_max(1, FOURLIB_DEPTH
+ (level
- 10));
fourlib_depth
= gg_max(1, FOURLIB_DEPTH
);
fourlib_depth
= gg_max(1, FOURLIB_DEPTH
+ (level
- 7));
superstring_depth
= gg_max(1, SUPERSTRING_DEPTH
);
owl_node_limit
= OWL_NODE_LIMIT
* pow(1.5, depth_level
);
owl_node_limit
= (OWL_NODE_LIMIT
* node_limits
[10 - level
] /
owl_node_limit
= gg_max(20, owl_node_limit
);
semeai_branch_depth
= gg_max(2, (2*SEMEAI_BRANCH_DEPTH
+ depth_level
) / 2);
semeai_branch_depth2
= gg_max(2, (2*SEMEAI_BRANCH_DEPTH2
+ depth_level
) / 2);
semeai_node_limit
= SEMEAI_NODE_LIMIT
* pow(1.5, depth_level
);
connect_depth
= gg_max(2, CONNECT_DEPTH
+ 2 * depth_level
);
connect_depth2
= gg_max(2, CONNECT_DEPTH2
+ 2 * depth_level
);
connection_node_limit
= CONNECT_NODE_LIMIT
* pow(1.45, depth_level
);
breakin_depth
= gg_max(2, BREAKIN_DEPTH
+ 2 * depth_level
);
breakin_node_limit
= BREAKIN_NODE_LIMIT
* pow(1.5, depth_level
);
if (mandated_depth
!= -1)
if (mandated_backfill_depth
!= -1)
backfill_depth
= mandated_backfill_depth
;
if (mandated_backfill2_depth
!= -1)
backfill2_depth
= mandated_backfill2_depth
;
if (mandated_break_chain_depth
!= -1)
break_chain_depth
= mandated_break_chain_depth
;
if (mandated_superstring_depth
!= -1)
superstring_depth
= mandated_superstring_depth
;
if (mandated_branch_depth
!= -1)
branch_depth
= mandated_branch_depth
;
if (mandated_fourlib_depth
!= -1)
fourlib_depth
= mandated_fourlib_depth
;
if (mandated_ko_depth
!= -1)
ko_depth
= mandated_ko_depth
;
if (mandated_aa_depth
!= -1)
aa_depth
= mandated_aa_depth
;
if (mandated_owl_distrust_depth
!= -1)
owl_distrust_depth
= mandated_owl_distrust_depth
;
if (mandated_owl_branch_depth
!= -1)
owl_branch_depth
= mandated_owl_branch_depth
;
if (mandated_owl_reading_depth
!= -1)
owl_reading_depth
= mandated_owl_reading_depth
;
if (mandated_owl_node_limit
!= -1)
owl_node_limit
= mandated_owl_node_limit
;
if (mandated_semeai_node_limit
!= -1)
semeai_node_limit
= mandated_semeai_node_limit
;
fprintf(stderr
, "at level %d:\n\n\
owl_distrust_depth: %d\n\
semeai_branch_depth: %d\n\
semeai_branch_depth2: %d\n\
connection_node_limit: %d\n\
breakin_node_limit: %d\n\n",
level
, depth
, branch_depth
, backfill_depth
, backfill2_depth
,
break_chain_depth
, owl_distrust_depth
, owl_branch_depth
,
owl_reading_depth
, aa_depth
, ko_depth
, fourlib_depth
,
superstring_depth
, owl_node_limit
, semeai_branch_depth
,
semeai_branch_depth2
, semeai_node_limit
, connect_depth
,
connect_depth2
, connection_node_limit
, breakin_depth
,
static int depth_modification
= 0;
* Modify the various tactical reading depth parameters. This is
* typically used to avoid horizon effects. By temporarily increasing
* the depth values when trying some move, one can avoid that an
* irrelevant move seems effective just because the reading hits a
* depth limit earlier than it did when reading only on relevant
modify_depth_values(int n
)
increase_depth_values(void)
decrease_depth_values(void)
get_depth_modification(void)
return depth_modification
;
static int detect_owl_blunder(int move
, int color
, int *defense_point
,
signed char safe_stones
[BOARDMAX
], int liberties
,
float *return_value
, int save_verbose
);
static void detect_tactical_blunder(int move
, int color
, int *defense_point
,
signed char safe_stones
[BOARDMAX
],
int liberties
, int *libs
,
float *return_value
, int save_verbose
);
/* Check that the move at color doesn't involve any kind of blunder,
confirm_safety(int move
, int color
, int *defense_point
,
signed char safe_stones
[BOARDMAX
])
return (blunder_size(move
, color
, defense_point
, safe_stones
) == 0.0);
/* This function will detect some blunders. If the move reduces the
* number of liberties of an adjacent friendly string, there is a
* danger that the move could backfire, so the function checks that no
* friendly worm which was formerly not attackable becomes attackable,
* and it checks that no opposing worm which was not defendable
* It returns the estimated size of the blunder, or 0.0 if nothing
* The array safe_stones[] contains the stones that are supposedly
* safe after (move). It may be NULL.
* For use when called from fill_liberty, this function may optionally
* return a point of defense, which, if taken, will presumably make
* the move at (move) safe on a subsequent turn.
blunder_size(int move
, int color
, int *defense_point
,
signed char safe_stones
[BOARDMAX
])
int liberties
= accuratelib(move
, color
, 5, libs
);
int save_verbose
= verbose
;
float return_value
= 0.0;
signed char defense_moves
[BOARDMAX
];
*defense_point
= NO_MOVE
;
TRACE("Checking safety of a %s move at %1m\n", color_to_string(color
), move
);
/* We start by checking whether we have accidentally killed an own
trouble
= detect_owl_blunder(move
, color
, defense_point
,
&return_value
, save_verbose
);
/* Next we see whether the move has caused tactical complications.
* The trouble variable is set if a string next to the move with few
* liberties has not gained liberties by the move.
detect_tactical_blunder(move
, color
, defense_point
, safe_stones
,
liberties
, libs
, &return_value
, save_verbose
);
/* FIXME: We would also need a detect_semeai_blunder() to check
* against moves which make the outcome of a semeai worse, e.g. by
* letting the opponent live in seki.
/* Finally we call the atari-atari code to see whether the move has
* set up some combination attack that didn't exist before. We do
* this last to avoid duplicate blunder reports.
atari
= atari_atari_blunder_size(color
, move
, defense_moves
, safe_stones
);
/* FIXME: Choose defense point more systematically. */
*defense_point
= NO_MOVE
;
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (ON_BOARD(pos
) && defense_moves
[pos
]) {
TRACE("Combination attack appears.\n");
return_value
+= (float) atari
;
/* Check whether we have accidentally killed an own dragon adjacent to
* move. If this happens, we mark its stones as no longer safe, and
* remember the dragon's size.
detect_owl_blunder(int move
, int color
, int *defense_point
,
signed char safe_stones
[BOARDMAX
], int liberties
,
float *return_value
, int save_verbose
)
int dragon_analyzed
[4] = {0, 0, 0, 0};
int current_verbose
= verbose
;
for (k
= 0; k
< 4; k
++) {
int bpos
= move
+ delta
[k
];
/* We get worried if there is a liberty problem (and in this case
* there might also be tactical trouble), or if we play inside
* our eye space and the dragon is only just alive.
if (board
[bpos
] != color
)
if (liberties
<= worm
[bpos
].liberties
if (min_eyes(&(DRAGON2(bpos
).genus
)) > 2
|| !is_proper_eye_space(move
))
/* Don't test the same dragon twice. */
if (dragon_analyzed
[j
] == dragon
[bpos
].origin
)
dragon_analyzed
[k
] = dragon
[bpos
].origin
;
/* Don't reanalyze if (move) is an owl defense for (bpos). */
if (safe_stones
&& safe_stones
[bpos
] == OWL_SAVED_STONE
)
if ((dragon
[bpos
].status
== ALIVE
&& DRAGON2(bpos
).safety
!= INVINCIBLE
&& DRAGON2(bpos
).safety
!= STRONGLY_ALIVE
) {
int acode
= owl_confirm_safety(move
, bpos
, defense_point
, &kworm
);
/* If owl couldn't confirm safety, maybe semeai can. */
for (r
= 0; r
< DRAGON2(bpos
).neighbors
; r
++) {
int neighbor
= dragon2
[DRAGON2(bpos
).adjacent
[r
]].origin
;
if (board
[neighbor
] == color
)
owl_analyze_semeai_after_move(move
, color
, neighbor
, bpos
,
NULL
, &resultb
, NULL
, 1, NULL
, 0);
TRACE("Dragon at %1m becomes attackable.\n", bpos
);
verbose
= current_verbose
;
*return_value
+= 2.0 * dragon
[bpos
].effective_size
;
mark_dragon(bpos
, safe_stones
, 0);
else if (acode
== LOSS
) {
TRACE("Dragon at %1m becomes attackable.\n", bpos
);
verbose
= current_verbose
;
/* the worm origin was messed by our own move */
for (l
= 0; l
< 4; l
++) {
int kworm
= move
+ delta
[l
];
if (board
[kworm
] == color
) {
*return_value
+= 2.0 * worm
[kworm
].effective_size
;
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
if (ON_BOARD(ii
) && worm
[ii
].origin
== worm
[kworm
].origin
)
*return_value
+= 2.0 * worm
[kworm
].effective_size
;
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
if (ON_BOARD(ii
) && worm
[ii
].origin
== worm
[kworm
].origin
)
/* Check whether a move causes any unexpected and unwelcome changes in
* the tactical status of worms all over the board.
detect_tactical_blunder(int move
, int color
, int *defense_point
,
signed char safe_stones
[BOARDMAX
],
int liberties
, int *libs
,
float *return_value
, int save_verbose
)
int other
= OTHER_COLOR(color
);
int current_verbose
= verbose
;
if (!trymove(move
, color
, NULL
, NO_MOVE
))
/* Need to increase the depth values during this reading to avoid
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!IS_STONE(board
[pos
])
|| worm
[pos
].origin
!= pos
/* First, we look for a new tactical attack.
* FIXME: Verify that the tactically attacked stone matters. See
* e.g. the D6 move in filllib:51 which invites a harmless
&& ((safe_stones
&& safe_stones
[pos
])
|| (!safe_stones
&& worm
[pos
].attack_codes
[0] == 0))
/* A safe worm of ours has become attackable. */
find_defense(pos
, defense_point
);
/* Check that this move is legal and effective also on the
* original board, otherwise find a tactical defense there
if (!is_legal(*defense_point
, color
)
|| play_attack_defend_n(color
, 1, 1, *defense_point
, pos
))
find_defense(pos
, defense_point
);
/* Redo the move, we know that it won't fail. */
trymove(move
, color
, NULL
, NO_MOVE
);
TRACE("After %1m Worm at %1m becomes attackable.\n", move
, pos
);
verbose
= current_verbose
;
*return_value
+= worm
[pos
].effective_size
;
if (safe_stones
) /* Can't use mark_string. */
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
if (worm
[ii
].origin
== worm
[pos
].origin
)
else if (board
[pos
] == other
&& worm
[pos
].origin
== pos
&& worm
[pos
].attack_codes
[0] != 0
&& worm
[pos
].defense_codes
[0] == 0
&& find_defense(pos
, NULL
)) {
/* A dead opponent's worm has become defendable.
* Also ask the owl code whether the string can live
* strategically. To do this we need to temporarily undo
int defense_effective
= 0;
owl_attacks
= owl_does_attack(move
, pos
, NULL
);
if (owl_attacks
!= WIN
) {
*return_value
+= 2 * worm
[pos
].effective_size
;
TRACE("After %1m worm at %1m becomes defendable - A.\n", move
, pos
);
verbose
= current_verbose
;
else if (dragon
[pos
].status
!= ALIVE
) {
/* Before redoing the trymove we also check whether the worm now
* has a semeai defense. See blunder:26 for an example.
* If the worm already was alive in seki, it is generally okay
* that it also becomes tactically safe when the outer
* liberties are filled, see e.g. blunder:32,34. Thus the
num_adj
= extended_chainlinks(pos
, adj
, 0);
for (k
= 0; k
< num_adj
; k
++) {
owl_analyze_semeai_after_move(move
, color
, pos
, neighbor
,
&resulta
, NULL
, NULL
, 1, NULL
, 1);
*return_value
+= 2 * worm
[pos
].effective_size
;
TRACE("After %1m worm at %1m becomes defendable - B.\n",
verbose
= current_verbose
;
trymove(move
, color
, NULL
, NO_MOVE
);
if (defense_effective
&& defense_point
) {
if (attack(pos
, &dpos
)) {
/* Check that this move is legal and effective also on the
* original board, otherwise find a tactical attack there
if (!is_legal(dpos
, color
)
|| play_attack_defend_n(color
, 0, 1, dpos
, pos
))
attack(pos
, defense_point
);
/* Redo the move, we know that it won't fail. */
trymove(move
, color
, NULL
, NO_MOVE
);
TRACE("No attack found (unexpectedly) on %1m after move at %1m.\n",
verbose
= current_verbose
;
/* Look for double atari style complications of the move.
* FIXME: Since we have an atari_atari check in blunder_size(), do
* we still need to do this step?
if (double_atari(libs
[0], other
, &d_a_blunder_size
, safe_stones
)) {
if (defense_point
&& safe_move(libs
[0], color
) == WIN
)
*defense_point
= libs
[0];
*return_value
+= d_a_blunder_size
;
TRACE("Double threat appears at %1m.\n", libs
[0]);
verbose
= current_verbose
;
else if (double_atari(libs
[1], other
, &d_a_blunder_size
, safe_stones
)) {
if (defense_point
&& safe_move(libs
[1], color
) == WIN
)
*defense_point
= libs
[1];
*return_value
+= d_a_blunder_size
;
TRACE("Double threat appears at %1m.\n", libs
[1]);
verbose
= current_verbose
;
/* Reset the depth values. */
/* Returns true if a move by (color) fits the following shape:
* capturing one of the two X strings. The name is a slight
* misnomer since this includes attacks which are not necessarily
* double ataris, though the common double atari is the most
* important special case.
* If safe_stones != NULL, then only attacks on stones marked as safe are
* The value of the double atari attack is returned in *value (unless
* value is NULL), and the attacked stones are marked unsafe.
double_atari(int move
, int color
, float *value
,
signed char safe_stones
[BOARDMAX
])
int other
= OTHER_COLOR(color
);
/* Loop over the diagonal directions. */
for (k
= 4; k
< 8; k
++) {
/* because (m, n) and (m+dm, n+dn) are opposite
* corners of a square, ON_BOARD2(m, n) && ON_BOARD2(m+dm, n+dn)
* implies ON_BOARD2(m+dm, n) and ON_BOARD2(n, n+dn)
* Only try to attack supposedly safe stones.
if (BOARD(m
+dm
, n
+dn
) == color
&& BOARD(m
, n
+dn
) == other
&& BOARD(m
+dm
, n
) == other
|| (safe_stones
[POS(m
, n
+dn
)] && safe_stones
[POS(m
+dm
, n
)]))
&& trymove(move
, color
, "double_atari", NO_MOVE
)) {
&& (BOARD(m
, n
+dn
) == EMPTY
|| BOARD(m
+dm
, n
) == EMPTY
|| !defend_both(POS(m
, n
+dn
), POS(m
+dm
, n
)))) {
if (worm
[POS(m
, n
+dn
)].effective_size
> worm
[POS(m
+dm
, n
)].effective_size
) {
*value
= 2.0 * worm
[POS(m
, n
+dn
)].effective_size
;
mark_string(POS(m
, n
+dn
), safe_stones
, 0);
*value
= 2.0 * worm
[POS(m
+dm
, n
)].effective_size
;
mark_string(POS(m
+dm
, n
), safe_stones
, 0);
/* Returns true if a move by (color) plays into a snapback. */
playing_into_snapback(int move
, int color
)
if (approxlib(move
, color
, 1, NULL
) != 0
|| accuratelib(move
, color
, 2, libs
) != 1)
if (board
[move
+ delta
[k
]] == color
&& adjacent_strings(libs
[0], move
+ delta
[k
]))
/* Score the game and determine the winner */
who_wins(int color
, FILE *outfile
)
silent_examine_position(EXAMINE_DRAGONS
);
if (color
!= BLACK
&& color
!= WHITE
)
/* Use the aftermath code to compute the final score. (Slower but
result
= aftermath_compute_score(color
, NULL
);
result
= (white_score
+ black_score
)/2.0;
fprintf(outfile
, "Result: jigo ");
fprintf(outfile
, "Result: %c+%.1f ",
(result
> 0.0) ? 'W' : 'B', gg_abs(result
));
/* Find the stones of an extended string, where the extensions are
* through the following kinds of connections:
* 1. Solid connections (just like ordinary string).
* 2. Diagonal connection or one space jump through an intersection
* where an opponent move would be suicide or self-atari.
* 4. Diagonal connection where both adjacent intersections are empty.
* 5. Connection through adjacent or diagonal tactically captured stones.
* Connections of this type are omitted when the superstring code is
* called from reading.c, but included when the superstring code is
do_find_superstring(int str
, int *num_stones
, int *stones
,
int *num_lib
, int *libs
, int maxlibs
,
int *num_adj
, int *adjs
, int liberty_cap
,
superstring_add_string(int str
,
int *num_my_stones
, int *my_stones
,
int *num_stones
, int *stones
,
int *num_libs
, int *libs
, int maxlibs
,
int *num_adj
, int *adjs
, int liberty_cap
,
signed char mx
[BOARDMAX
],
signed char ml
[BOARDMAX
],
signed char ma
[BOARDMAX
],
find_superstring(int str
, int *num_stones
, int *stones
)
do_find_superstring(str
, num_stones
, stones
,
/* This is the same as find_superstring, except that connections of
* type 5 are omitted. This is used in semeai analysis.
find_superstring_conservative(int str
, int *num_stones
, int *stones
)
do_find_superstring(str
, num_stones
, stones
,
/* This function computes the superstring at (str) as described above,
* but omitting connections of type 5. Then it constructs a list of
* liberties of the superstring which are not already liberties of
* If liberty_cap is nonzero, only liberties of substrings of the
* superstring which have fewer than liberty_cap liberties are
find_superstring_liberties(int str
,
int *num_libs
, int *libs
, int liberty_cap
)
do_find_superstring(str
, NULL
, NULL
,
num_libs
, libs
, MAX_LIBERTIES
,
/* This function is the same as find_superstring_liberties, but it
* omits those liberties of the string (str), presumably since
* those have already been treated elsewhere.
* If liberty_cap is nonzero, only liberties of substrings of the
* superstring which have at most liberty_cap liberties are
find_proper_superstring_liberties(int str
,
int *num_libs
, int *libs
,
do_find_superstring(str
, NULL
, NULL
,
num_libs
, libs
, MAX_LIBERTIES
,
/* This function computes the superstring at (str) as described above,
* but omitting connections of type 5. Then it constructs a list of
* liberties of the superstring which are not already liberties of
* If liberty_cap is nonzero, only liberties of substrings of the
* superstring which have fewer than liberty_cap liberties are
find_superstring_stones_and_liberties(int str
,
int *num_stones
, int *stones
,
int *num_libs
, int *libs
,
do_find_superstring(str
, num_stones
, stones
,
num_libs
, libs
, MAX_LIBERTIES
,
/* analogous to chainlinks, this function finds boundary chains of the
* superstring at (str), including those which are boundary chains of
* (str) itself. If liberty_cap != 0, only those boundary chains with
* <= liberty_cap liberties are reported.
superstring_chainlinks(int str
,
int *num_adj
, int adjs
[MAXCHAIN
],
do_find_superstring(str
, NULL
, NULL
,
num_adj
, adjs
, liberty_cap
,
/* analogous to chainlinks, this function finds boundary chains of the
* superstring at (str), omitting those which are boundary chains of
* (str) itself. If liberty_cap != 0, only those boundary chains with
* <= liberty_cap liberties are reported.
proper_superstring_chainlinks(int str
,
int *num_adj
, int adjs
[MAXCHAIN
],
do_find_superstring(str
, NULL
, NULL
,
num_adj
, adjs
, liberty_cap
,
/* Do the real work finding the superstring and recording stones,
* liberties, and/or adjacent strings.
do_find_superstring(int str
, int *num_stones
, int *stones
,
int *num_libs
, int *libs
, int maxlibs
,
int *num_adj
, int *adjs
, int liberty_cap
,
int my_stones
[MAX_BOARD
* MAX_BOARD
];
signed char mx
[BOARDMAX
]; /* stones */
signed char ml
[BOARDMAX
]; /* liberties */
signed char ma
[BOARDMAX
]; /* adjacent strings */
int other
= OTHER_COLOR(color
);
memset(mx
, 0, sizeof(mx
));
memset(ml
, 0, sizeof(ml
));
memset(ma
, 0, sizeof(ma
));
/* Include the string itself in the superstring. Only record stones,
* liberties, and/or adjacent strings if proper==0.
superstring_add_string(str
, &num_my_stones
, my_stones
,
num_adj
, adjs
, liberty_cap
,
/* Loop over all found stones, looking for more strings to include
* in the superstring. The loop is automatically extended over later
for (r
= 0; r
< num_my_stones
; r
++) {
for (k
= 0; k
< 4; k
++) {
/* List of relative coordinates. (pos) is marked by *.
int bpos
= pos
+ right
+ up
;
int cpos
= pos
+ 2*right
;
int dpos
= pos
+ right
- up
;
int fpos
= pos
+ right
+ 2*up
;
/* Case 1. Nothing to do since stones are added string by string. */
if (board
[apos
] == EMPTY
) {
unsafe_move
= (approxlib(apos
, other
, 2, NULL
) < 2);
unsafe_move
= is_self_atari(apos
, other
);
if (unsafe_move
&& type
== 1 && is_ko(apos
, other
, NULL
))
if (board
[bpos
] == color
&& !mx
[bpos
])
superstring_add_string(bpos
, &num_my_stones
, my_stones
,
num_adj
, adjs
, liberty_cap
,
if (board
[cpos
] == color
&& !mx
[cpos
])
superstring_add_string(cpos
, &num_my_stones
, my_stones
,
num_adj
, adjs
, liberty_cap
,
if (board
[dpos
] == color
&& !mx
[dpos
])
superstring_add_string(dpos
, &num_my_stones
, my_stones
,
num_adj
, adjs
, liberty_cap
,
/* Notice that the order of these tests is significant. We must
* check bpos before fpos and epos to avoid accessing memory
* outside the board array. (Notice that fpos is two steps away
* from pos, which we know is on the board.)
if (board
[apos
] == color
&& board
[bpos
] == EMPTY
&& board
[fpos
] == color
&& board
[epos
] == color
&& !mx
[epos
]
superstring_add_string(epos
, &num_my_stones
, my_stones
,
num_adj
, adjs
, liberty_cap
,
/* Don't bother with f, it is part of the string just added. */
if (board
[bpos
] == color
&& !mx
[bpos
]
&& board
[apos
] == EMPTY
&& board
[gpos
] == EMPTY
)
superstring_add_string(bpos
, &num_my_stones
, my_stones
,
num_adj
, adjs
, liberty_cap
,
for (l
= 0; l
< 2; l
++) {
if (board
[upos
] != other
)
upos
= find_origin(upos
);
/* Only do the reading once. */
&& !find_defense(upos
, NULL
)) {
int lunch_stones
[MAX_BOARD
*MAX_BOARD
];
int num_lunch_stones
= findstones(upos
, MAX_BOARD
*MAX_BOARD
,
for (m
= 0; m
< num_lunch_stones
; m
++)
for (n
= 0; n
< 8; n
++) {
int vpos
= lunch_stones
[m
] + delta
[n
];
if (board
[vpos
] == color
&& !mx
[vpos
])
superstring_add_string(vpos
,
&num_my_stones
, my_stones
,
num_adj
, adjs
, liberty_cap
,
if (num_libs
&& maxlibs
> 0 && *num_libs
>= maxlibs
)
/* Add a new string to a superstring. Record stones, liberties, and
* adjacent strings as asked for.
superstring_add_string(int str
,
int *num_my_stones
, int *my_stones
,
int *num_stones
, int *stones
,
int *num_libs
, int *libs
, int maxlibs
,
int *num_adj
, int *adjs
, int liberty_cap
,
signed char mx
[BOARDMAX
],
signed char ml
[BOARDMAX
],
signed char ma
[BOARDMAX
],
ASSERT1(mx
[str
] == 0, str
);
/* Pick up the stones of the new string. */
new_stones
= findstones(str
, board_size
* board_size
,
&(my_stones
[*num_my_stones
]));
for (k
= 0; k
< new_stones
; k
++) {
stones
[*num_stones
] = my_stones
[*num_my_stones
+ k
];
(*num_my_stones
) += new_stones
;
/* Pick up the liberties of the new string. */
/* Get the liberties of the string. */
num_my_libs
= findlib(str
, MAXLIBS
, my_libs
);
/* Remove this string from the superstring if it has too many
if (liberty_cap
> 0 && num_my_libs
> liberty_cap
)
(*num_my_stones
) -= new_stones
;
for (k
= 0; k
< num_my_libs
; k
++) {
if (do_add
&& (liberty_cap
== 0 || num_my_libs
<= liberty_cap
)) {
libs
[*num_libs
] = my_libs
[k
];
if (*num_libs
== maxlibs
)
/* Pick up adjacent strings to the new string. */
num_my_adj
= chainlinks(str
, my_adjs
);
for (k
= 0; k
< num_my_adj
; k
++) {
if (liberty_cap
> 0 && countlib(my_adjs
[k
]) > liberty_cap
)
adjs
[*num_adj
] = my_adjs
[k
];
/* Internal timers for assessing time spent on various tasks. */
#define NUMBER_OF_TIMERS 4
static double timers
[NUMBER_OF_TIMERS
];
gg_assert(n
>= 0 && n
< NUMBER_OF_TIMERS
);
timers
[n
] = gg_cputime();
/* Report time spent and restart the timer. Make no report if elapsed
* time is less than mintime.
time_report(int n
, const char *occupation
, int move
, double mintime
)
gg_assert(n
>= 0 && n
< NUMBER_OF_TIMERS
);
gprintf("%s", occupation
);
fprintf(stderr
, ": %.2f sec\n", dt
);
stats
.read_result_entered
= 0;
stats
.read_result_hits
= 0;
stats
.trusted_read_result_hits
= 0;
gprintf("Nodes: %d\n", stats
.nodes
);
gprintf("Read results entered: %d\n", stats
.read_result_entered
);
gprintf("Read result hits: %d\n", stats
.read_result_hits
);
gprintf("Trusted read result hits: %d\n", stats
.trusted_read_result_hits
);
/* Set up a compiled in pattern database for use by the Monte Carlo
* code. If name is NULL, the first pattern database is used.
* The reason why this function and the next are placed here rather
* than in montecarlo.c is to keep that file free from dependency on
choose_mc_patterns(char *name
)
for (k
= 0; mc_pattern_databases
[k
].name
; k
++) {
if (!name
|| strcmp(name
, mc_pattern_databases
[k
].name
) == 0) {
mc_init_patterns(mc_pattern_databases
[k
].values
);
/* List compiled in Monte Carlo pattern databases. */
printf("Available builtin Monte Carlo local patterns:\n\n");
for (k
= 0; mc_pattern_databases
[k
].name
; k
++) {
printf("* %s (default)\n", mc_pattern_databases
[k
].name
);
printf("* %s\n", mc_pattern_databases
[k
].name
);
printf("\nUse \"--mc-patterns name\" to choose one of these.\n");
printf("Use \"--mc-load-patterns filename\" to directly load a pattern database.\n");