/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* 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. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* Size of array where candidate moves are stored. */
unsigned int bits
[1+BOARDMAX
/32];
static int recursive_connect2(int str1
, int str2
, int *move
,
static int recursive_disconnect2(int str1
, int str2
, int *move
,
static int recursive_break(int str
, const signed char goal
[BOARDMAX
],
int *move
, int has_passed
, Hash_data
*goal_hash
);
static int recursive_block(int str
, const signed char goal
[BOARDMAX
],
int *move
, int has_passed
, Hash_data
*goal_hash
);
static int add_array(int *array
, int elt
);
static int element_array(int *array
, int elt
);
static void intersection_array(int *array1
, int *array2
);
static int snapback(int str
);
static int connection_one_move(int str1
, int str2
);
static int prevent_connection_one_move(int *moves
, int str1
, int str2
);
static int connected_one_move(int str1
, int str2
);
static int moves_to_connect_in_two_moves(int *moves
, int str1
, int str2
);
static int connection_two_moves(int str1
, int str2
);
static int prevent_connection_two_moves(int *moves
, int str1
, int str2
);
static int connected_two_moves(int str1
, int str2
);
static int moves_to_connect_in_three_moves(int *moves
, int str1
, int str2
,
static int simple_connection_three_moves(int str1
, int str2
);
static int prevent_simple_connection_three_moves(int *moves
,
static int recursive_connect(int str1
, int str2
, int *move
);
static int recursive_disconnect(int str1
, int str2
, int *move
);
static int quiescence_connect(int str1
, int str2
, int *move
);
static int quiescence_capture(int str
, int *move
);
/* static int capture_one_move(int str); */
static int prevent_capture_one_move(int *moves
, int str1
);
static int recursive_transitivity(int str1
, int str2
, int str3
, int *move
);
static int recursive_non_transitivity(int str1
, int str2
, int str3
, int *move
);
static void order_connection_moves(int *moves
, int str1
, int str2
,
int color_to_move
, const char *funcname
);
static int nodes_connect
= 0;
/* Used by alternate connections. */
static signed char connection_shadow
[BOARDMAX
];
static signed char breakin_shadow
[BOARDMAX
];
static int global_connection_node_counter
= 0;
memset(zn
->bits
, 0, 1 + BOARDMAX
/ 8);
/* send back 1 if the intersection is in the zone
elt_zone(zone
*zn
, int elt
)
if ((zn
->bits
[elt
>> 5] >> (elt
& 31)) & 1)
/* Adds an intersection to a zone
add_zone(zone
*zn
, int elt
)
if (((zn
->bits
[elt
>> 5] >> (elt
& 31)) & 1) == 0) {
zn
->bits
[elt
>> 5] |= (1 << (elt
& 31));
zn
->array
[zn
->array
[0]] = elt
;
/* start to loop over a zone
/* continue to loop over a zone
if (zn
->i
> zn
->array
[0])
/* only keep the elements of zn1 which are also in zn2 */
intersection_zone(zone
*zn1
, zone
*zn2
)
for (r
= start_zone(zn1
); r
> -1; r
= next_zone(zn1
))
for (s
= r
; s
< zn1
->array
[0]; s
++)
zn1
->array
[s
] = zn1
->array
[s
+1];
zn1
->bits
[r
>> 5] &= ~ (1 << (r
& 31));
/* Adds an integer to an array of integers if it is not already there.
* The number of elements of the array is in array[0].
add_array(int *array
, int elt
)
for (r
= 1; r
< array
[0] + 1; r
++)
/* test if an element is part of an array */
element_array(int *array
, int elt
)
for (r
= 1; r
< array
[0] + 1; r
++)
/* only keep the elements of array1 which are also in array2 */
intersection_array(int *array1
, int *array2
)
for (r
= 1; r
< array1
[0] + 1; r
++)
if (!element_array(array2
, array1
[r
])) {
for (s
= r
; s
< array1
[0]; s
++)
/* verifies that capturing the stone at str is not a snapback */
int stones
, liberties
, lib
;
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
/* if more than one stone captured, not a snapback */
stones
= countstones(str
);
/* if more than one liberty, not a snapback */
liberties
= findlib(str
, 1, &lib
);
/* turn off the sgf traces
/* if only one liberty after capture */
if (trymove(lib
, OTHER_COLOR(board
[str
]), "snapback", str
)) {
if (IS_STONE(board
[lib
]))
liberties
= countlib(lib
);
sgf_dumptree
= save_sgf_dumptree
;
/* Turn the sgf traces back on. */
sgf_dumptree
= save_sgf_dumptree
;
/* connection by playing and finding a ponnuki after play */
ponnuki_connect(int *moves
, int str1
, int str2
, zone
*zn
)
int liberties
, libs
[MAXLIBS
];
int neighb
, neighbs
[MAXCHAIN
];
/* finds connection through two forbidden liberties for
liberties
= findlib(str1
, MAXLIBS
, libs
);
for (r
= 0; r
< liberties
; r
++)
if (is_self_atari(libs
[r
], OTHER_COLOR(board
[str1
])))
for (k
= 0; k
< 4; k
++) {
int pos
= libs
[r
] + delta
[k
];
if (board
[pos
] == board
[str1
]
&& !same_string(pos
, str1
)
&& !same_string(pos
, str2
)) {
/* try to connect pos to str2 in one move */
/* play a common liberty */
neighb
= findlib(pos
, MAXLIBS
, neighbs
);
for (s
= 0; s
< neighb
; s
++)
if (liberty_of_string(neighbs
[s
], str2
)) {
add_zone(zn
, neighbs
[s
]);
add_array(moves
, neighbs
[s
]);
/* or capture a common adjacent string */
adj
= chainlinks2(pos
, adjs
, 1);
for (s
= 0; s
< adj
; s
++)
if (adjacent_strings(adjs
[s
], str2
)
neighb
= findlib(adjs
[s
], 1, neighbs
);
add_zone(zn
, neighbs
[0]);
add_array(moves
, neighbs
[0]);
/* connection in one move, finds all moves and memorizes intersections
* involved in the connection.
moves_connection_one_move(int *moves
, int str1
, int str2
, zone
*zn
)
/* If one string is missing we have already failed. */
if (board
[str1
] == EMPTY
|| board
[str2
] == EMPTY
)
if (have_common_lib(str1
, str2
, NULL
))
/* Common adjacent string in atari, more than one stone, no snapback. */
adj
= chainlinks2(str1
, adjs
, 1);
for (r
= 0; r
< adj
; r
++)
if (adjacent_strings(adjs
[r
], str2
)
/* Connections through a ponnuki */
if (ponnuki_connect(moves
, str1
, str2
, zn
))
if (ponnuki_connect(moves
, str2
, str1
, zn
))
/* Verifies that the strings str1 and str2 can be connected
* directly by playing one move, either by playing a common liberty
* of the two strings, or by capturing a common adjacent string.
* This is the gi1 game function.
connection_one_move(int str1
, int str2
)
return moves_connection_one_move(moves
, str1
, str2
, &zn
);
/* If the two strings str1 and str2 can be connected sends back WIN fill the
* array moves with the only move that can prevent a connection in one move
* (common liberties, liberties of common adjacent strings in atari).
* This is the ip1 game function. */
prevent_connection_one_move(int *moves
, int str1
, int str2
)
int adjadj
, adjadjs
[MAXCHAIN
];
if (have_common_lib(str1
, str2
, libs
)) {
add_array(moves
, libs
[0]);
/* Save a common adjacent string in atari, more than one stone, no snapback.
adj
= chainlinks2(str1
, adjs
, 1);
for (r
= 0; r
< adj
; r
++)
if (adjacent_strings(adjs
[r
], str2
)
findlib(adjs
[r
], MAXLIBS
, libs
);
add_array(moves
, libs
[0]);
adjadj
= chainlinks2(adjs
[r
], adjadjs
, 1);
for (s
= 0; s
< adjadj
; s
++) {
findlib(adjadjs
[s
], MAXLIBS
, libs
);
add_array(moves
, libs
[0]);
/* Returns WIN if str1 and str2 are connected in at most
* one move even if the opponent plays first.
* Verify that the strings are connectable in one move
* and find the only possible moves that can prevent
* using prevent_connection_one_move. If none of these
* moves works, the two strings are connected.
* This is the g1 game function.
connected_one_move(int str1
, int str2
)
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
/* turn off the sgf traces
if (prevent_connection_one_move(moves
, str1
, str2
)) {
order_connection_moves(moves
, str1
, str2
, OTHER_COLOR(board
[str1
]),
for (r
= 1; ((r
< moves
[0] + 1) && res
); r
++) {
if (trymove(moves
[r
], OTHER_COLOR(board
[str1
]),
"connected_one_move", str1
)) {
if (!connection_one_move(str1
, str2
))
/* Turn the sgf traces back on. */
sgf_dumptree
= save_sgf_dumptree
;
/* Find the moves that might be able to connect in less than three plies.
* That is moves that can connect the strings if another move of the same
* color is played just after:
* - common liberties of the two strings;
* - moves on the liberties of an opponent string with less than two
* liberties adjacent to both strings, or adjacent to one string and
* that has a common liberty with the second string;
* - liberties of one string that are second order liberties of the
* Returns WIN if a direct connection has been found. Returns 0
moves_to_connect_in_two_moves(int *moves
, int str1
, int str2
)
int r
, s
, common_adj_liberty
;
int liberties
, libs
[MAXLIBS
];
int adjadj
, adjadjs
[MAXCHAIN
];
if (have_common_lib(str1
, str2
, libs
)) {
add_array(moves
, libs
[0]);
/* Capture a common adjacent string or an adjacent liberty of str1
* that has a common liberty with str2...
adj
= chainlinks3(str1
, adjs
, 2);
for (r
= 0; r
< adj
; r
++) {
liberties
= findlib(adjs
[r
], MAXLIBS
, libs
);
for (s
= 0; s
< liberties
; s
++)
if (liberty_of_string(libs
[s
], str2
))
if (common_adj_liberty
|| adjacent_strings(adjs
[r
], str2
)) {
for (s
= 0; s
< liberties
; s
++)
add_array(moves
, libs
[s
]);
adjadj
= chainlinks2(adjs
[r
], adjadjs
, 1);
for (s
= 0; s
< adjadj
; s
++) {
findlib(adjadjs
[s
], MAXLIBS
, libs
);
add_array(moves
, libs
[0]);
adj
= chainlinks3(str2
, adjs
, 2);
for (r
= 0; r
< adj
; r
++) {
liberties
= findlib(adjs
[r
], MAXLIBS
, libs
);
for (s
= 0; s
< liberties
; s
++)
if (liberty_of_string(libs
[s
], str1
))
if (common_adj_liberty
|| adjacent_strings(adjs
[r
], str1
)) {
for (s
= 0; s
< liberties
; s
++)
add_array(moves
, libs
[s
]);
adjadj
= chainlinks2(adjs
[r
], adjadjs
, 1);
for (s
= 0; s
< adjadj
; s
++) {
findlib(adjadjs
[s
], MAXLIBS
, libs
);
add_array(moves
, libs
[0]);
/* Liberties of str1 that are second order liberties of str2 and
liberties
= findlib(str1
, MAXLIBS
, libs
);
for (r
= 0; r
< liberties
; r
++) {
if (board
[SOUTH(libs
[r
])] == EMPTY
) {
if (liberty_of_string(SOUTH(libs
[r
]), str2
)) {
add_array(moves
, libs
[r
]);
add_array(moves
, SOUTH(libs
[r
]));
if (board
[WEST(libs
[r
])] == EMPTY
) {
if (liberty_of_string(WEST(libs
[r
]), str2
)) {
add_array(moves
, libs
[r
]);
add_array(moves
, WEST(libs
[r
]));
if (board
[NORTH(libs
[r
])] == EMPTY
) {
if (liberty_of_string(NORTH(libs
[r
]), str2
)) {
add_array(moves
, libs
[r
]);
add_array(moves
, NORTH(libs
[r
]));
if (board
[EAST(libs
[r
])] == EMPTY
) {
if (liberty_of_string(EAST(libs
[r
]), str2
)) {
add_array(moves
, libs
[r
]);
add_array(moves
, EAST(libs
[r
]));
/* Liberties of str1 which are adjacent to a friendly string with
* common liberty with str2.
liberties
= findlib(str1
, MAXLIBS
, libs
);
for (r
= 0; r
< liberties
; r
++) {
for (k
= 0; k
< 4; k
++) {
int pos
= libs
[r
] + delta
[k
];
&& !same_string(pos
, str1
)
&& quiescence_connect(pos
, str2
, &move
)) {
add_array(moves
, libs
[r
]);
liberties
= findlib(str2
, MAXLIBS
, libs
);
for (r
= 0; r
< liberties
; r
++) {
for (k
= 0; k
< 4; k
++) {
int pos
= libs
[r
] + delta
[k
];
&& !same_string(pos
, str2
)
&& quiescence_connect(pos
, str1
, &move
)) {
add_array(moves
, libs
[r
]);
/* Tests if the strings can be connected in three plies starts
* with finding the possible moves that can connect. If two
* moves in a row are played, then try them and stops at the
* first working move. The strings are connected in two moves
* if the function connected_one_move is verified after a move.
* This is the gi2 game function.
connection_two_moves(int str1
, int str2
)
int r
, res
= 0, moves
[MAX_MOVES
];
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
/* If one string is missing we have already failed. */
if (board
[str1
] == EMPTY
|| board
[str2
] == EMPTY
)
if (moves_to_connect_in_two_moves(moves
, str1
, str2
))
order_connection_moves(moves
, str1
, str2
, board
[str1
],
/* turn off the sgf traces
for (r
= 1; ((r
< moves
[0] + 1) && !res
); r
++) {
if (trymove(moves
[r
], board
[str1
], "connection_two_moves", str1
)) {
if (connected_one_move(str1
, str2
))
sgf_dumptree
= save_sgf_dumptree
;
/* Find the complete set of possible moves that can prevent
* a connection in three plies.
* The function is not yet written, but moves_to_connect_in_two_moves does
* a similar job, so it is called temporarly.
moves_to_prevent_connection_in_two_moves(int *moves
, int str1
, int str2
)
if (moves_to_connect_in_two_moves(moves
, str1
, str2
))
/* Find all the moves that prevent to connect in a three plies
* deep search and put them in the moves array. Returns 0 if
* there is no three plies connection, or else it tries all the
* possible preventing moves. If after a possible preventing
* moves, there no connection in one move and no connection in
* two moves, then the moves prevents a three plies deep
* connection, and it is added to the moves array.
* this is the ip2 game function */
prevent_connection_two_moves(int *moves
, int str1
, int str2
)
int possible_moves
[MAX_MOVES
];
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
/* turn off the sgf traces
if (connection_two_moves(str1
, str2
)) {
moves_to_prevent_connection_in_two_moves(possible_moves
, str1
, str2
);
order_connection_moves(possible_moves
, str1
, str2
,
OTHER_COLOR(board
[str1
]),
"prevent_connection_two_moves");
for (r
= 1; r
< possible_moves
[0] + 1; r
++) {
if (trymove(possible_moves
[r
], OTHER_COLOR(board
[str1
]),
"prevent_connection_two_moves", str1
)) {
if (!connection_one_move(str1
, str2
))
if (!connection_two_moves(str1
, str2
))
add_array(moves
, possible_moves
[r
]);
sgf_dumptree
= save_sgf_dumptree
;
/* Only partially written.
* Find all the moves than can connect if two subsequent
* moves of the same color are played after
* - liberties of common adjacent strings with 3 liberties or less;
* - liberties of adjacent strings with 2 liberties or less that have
* liberties that are second order liberties of the other string;
* - liberties of one string that are second order liberties of the
* - second order liberties of the first string that are second order
* liberties of the other string;
* A function that computes the second order liberties of a string is
* needed as well as a function that checks efficiently if an
* intersection is a second order liberty of a given string.
* If does_connect is 1, generate moves to connect, otherwise generate
moves_to_connect_in_three_moves(int *moves
, int str1
, int str2
,
int liberties
, libs
[MAXLIBS
];
int liberties2
, libs2
[MAXLIBS
];
int adjadj
, adjadjs
[MAXCHAIN
];
int secondlib1
[BOARDMAX
];
int secondlib2
[BOARDMAX
];
if (moves_to_connect_in_two_moves(moves
, str1
, str2
))
/* Find second order liberties of str1. */
memset(secondlib1
, 0, sizeof(secondlib1
));
liberties
= findlib(str1
, MAXLIBS
, libs
);
for (r
= 0; r
< liberties
; r
++)
for (k
= 0; k
< 4; k
++) {
pos
= libs
[r
] + delta
[k
];
else if (board
[pos
] == board
[str1
]) {
liberties2
= findlib(pos
, MAXLIBS
, libs2
);
for (s
= 0; s
< liberties2
; s
++)
secondlib1
[libs2
[s
]] = 1;
/* Find second order liberties of str2.
memset(secondlib2
, 0, sizeof(secondlib2
));
liberties
= findlib(str2
, MAXLIBS
, libs
);
for (r
= 0; r
< liberties
; r
++)
for (k
= 0; k
< 4; k
++) {
pos
= libs
[r
] + delta
[k
];
else if (board
[pos
] == board
[str2
]) {
liberties2
= findlib(pos
, MAXLIBS
, libs2
);
for (s
= 0; s
< liberties2
; s
++)
secondlib2
[libs2
[s
]] = 1;
/* Second order liberties of str1 that are second order liberties
* of str2 and vice versa.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (secondlib1
[pos
] && secondlib2
[pos
])
/* Capture a neighbor of str1 which is in atari. The captured string
* must in turn have a neighbor which can connect to str2 easily.
adj
= chainlinks2(str1
, adjs
, 1);
for (r
= 0; r
< adj
; r
++) {
adjadj
= chainlinks(adjs
[r
], adjadjs
);
for (s
= 0; s
< adjadj
; s
++) {
if (!same_string(adjadjs
[s
], str1
)
&& quiescence_connect(adjadjs
[s
], str2
, &move
)) {
findlib(adjs
[r
], 1, libs
);
add_array(moves
, libs
[0]);
adj
= chainlinks2(str2
, adjs
, 1);
for (r
= 0; r
< adj
; r
++) {
adjadj
= chainlinks(adjs
[r
], adjadjs
);
for (s
= 0; s
< adjadj
; s
++) {
if (!same_string(adjadjs
[s
], str2
)
&& quiescence_connect(adjadjs
[s
], str1
, &move
)) {
findlib(adjs
[r
], 1, libs
);
add_array(moves
, libs
[0]);
/* Liberties of neighbor of str1 with at most two liberties, which
* are second order liberties of str2.
adj
= chainlinks3(str1
, adjs
, 2);
for (r
= 0; r
< adj
; r
++) {
liberties
= findlib(adjs
[r
], 2, libs
);
for (s
= 0; s
< liberties
; s
++)
if (second_order_liberty_of_string(libs
[s
], str2
))
add_array(moves
, libs
[s
]);
adj
= chainlinks3(str2
, adjs
, 2);
for (r
= 0; r
< adj
; r
++) {
liberties
= findlib(adjs
[r
], 2, libs
);
for (s
= 0; s
< liberties
; s
++)
if (second_order_liberty_of_string(libs
[s
], str1
))
add_array(moves
, libs
[s
]);
/* Move in on a three liberty opponent string which is adjacent to
* str1 and has a liberty in common with str2.
adj
= chainlinks2(str1
, adjs
, 3);
for (r
= 0; r
< adj
; r
++) {
if (have_common_lib(adjs
[r
], str2
, NULL
)) {
liberties
= findlib(adjs
[r
], 3, libs
);
for (s
= 0; s
< liberties
; s
++) {
/* If generating a connecting move, require the liberty to be
* no further than diagonal to a second order liberty of one
for (k
= 0; k
< 8; k
++) {
|| (ON_BOARD(libs
[s
] + delta
[k
])
&& (secondlib1
[libs
[s
] + delta
[k
]]
|| secondlib2
[libs
[s
] + delta
[k
]]))) {
add_array(moves
, libs
[s
]);
adj
= chainlinks2(str2
, adjs
, 3);
for (r
= 0; r
< adj
; r
++) {
if (have_common_lib(adjs
[r
], str1
, NULL
)) {
liberties
= findlib(adjs
[r
], 3, libs
);
for (s
= 0; s
< liberties
; s
++) {
/* If generating a connecting move, require the liberty to be
* no further than diagonal to a second order liberty of one
for (k
= 0; k
< 8; k
++) {
|| (ON_BOARD(libs
[s
] + delta
[k
])
&& (secondlib1
[libs
[s
] + delta
[k
]]
|| secondlib2
[libs
[s
] + delta
[k
]]))) {
add_array(moves
, libs
[s
]);
* Find the complete set of possible moves that can prevent
* a connection in 5 plies.
moves_to_prevent_connection_in_three_moves(int *moves
, int str1
, int str2
)
if (moves_to_connect_in_three_moves(moves
, str1
, str2
, 0))
* The simplest depth 4 connection:
* If there are forced moves to prevent connection in one move,
* try them, and verify that they all lead to a depth 1 or
* This is the g211 game function.
simply_connected_two_moves(int str1
, int str2
)
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
/* turn off the sgf traces
/* If one string is missing we have already failed. */
if (board
[str1
] == EMPTY
|| board
[str2
] == EMPTY
)
if (prevent_connection_one_move(moves
, str1
, str2
)) {
order_connection_moves(moves
, str1
, str2
, OTHER_COLOR(board
[str1
]),
"simply_connected_two_moves");
for (r
= 1; ((r
< moves
[0] + 1) && res
); r
++) {
if (trymove(moves
[r
], OTHER_COLOR(board
[str1
]),
"simply_connected_two_moves", str1
)) {
if (!connection_one_move(str1
, str2
))
if (!connection_two_moves(str1
, str2
))
sgf_dumptree
= save_sgf_dumptree
;
/* Test if a move is a simple depth 5 connection.
* This is the gi311 game function.
simple_connection_three_moves(int str1
, int str2
)
int r
, res
= 0, moves
[MAX_MOVES
];
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
/* turn off the sgf traces
if (moves_to_connect_in_two_moves(moves
, str1
, str2
))
order_connection_moves(moves
, str1
, str2
, board
[str1
],
"simple_connection_three_moves");
for (r
= 1; ((r
< moves
[0] + 1) && !res
); r
++) {
if (trymove(moves
[r
], board
[str1
],
"simple_connection_three_moves", str1
)) {
if (simply_connected_two_moves(str1
, str2
))
sgf_dumptree
= save_sgf_dumptree
;
/* Find the forced moves that prevent a simple depth 5 connection.
* Fills the array moves with the forced moves.
* This is the ip311 game function.
* It finds moves in very important situations such as:
* and enables recursive_disconnect to prove the two black
* strings are connected in these situations.
prevent_simple_connection_three_moves(int *moves
, int str1
, int str2
)
int possible_moves
[MAX_MOVES
];
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
/* turn off the sgf traces
if (simple_connection_three_moves(str1
, str2
)) {
moves_to_prevent_connection_in_three_moves(possible_moves
, str1
, str2
);
order_connection_moves(moves
, str1
, str2
, OTHER_COLOR(board
[str1
]),
"prevent_simple_connection_three_moves");
for (r
= 1; r
< possible_moves
[0] + 1; r
++) {
if (trymove(possible_moves
[r
], OTHER_COLOR(board
[str1
]),
"prevent_simple_connection_three_moves", str1
)) {
if (!connection_one_move(str1
, str2
))
if (!connection_two_moves(str1
, str2
))
if (!simple_connection_three_moves(str1
, str2
))
add_array(moves
, possible_moves
[r
]);
sgf_dumptree
= save_sgf_dumptree
;
/* Find simple connections by looking at common liberties
* or directly capturing a common adjacent string without a snapback
* or looking at a ladder for a common adjacent string.
quiescence_connect(int str1
, int str2
, int *move
)
if (have_common_lib(str1
, str2
, &lib
)) {
/* Common adjacent string in atari, more than one stone, no snapback. */
adj
= chainlinks2(str1
, adjs
, 1);
for (r
= 0; r
< adj
; r
++)
if (adjacent_strings(adjs
[r
], str2
)
findlib(adjs
[r
], 1, move
);
/* Common adjacent string two liberties, read ladder. */
adj
= chainlinks2(str1
, adjs
, 2);
for (r
= 0; r
< adj
; r
++)
if (adjacent_strings(adjs
[r
], str2
))
if (quiescence_capture(adjs
[r
], move
))
/* A persistent connection cache has been implemented, but currently
* (3.3.15) it does not have much impact on performance. Possible
* explanations for this include:
* 1. The active area is too often unnecessarily large.
* 2. Between the persistent caches of tactical reading and owl
* reading, there is not much to gain from also caching the
* 3. There is some bug in the implementation.
* In order to simplify testing of code modifications, the caching
* code has been made conditional. Setting
* USE_PERSISTENT_CONNECTION_CACHE to 0, 1, or 2 has the following
* 0 - Completely turned off.
* 1 - Results are stored in the cache but retrieved results are only
* compared to the non-cached result. Deviations are reported.
#define USE_PERSISTENT_CONNECTION_CACHE 0
/* Externally callable frontend to recursive_connect().
* Returns WIN if str1 and str2 can be connected.
string_connect(int str1
, int str2
, int *move
)
if (alternate_connections
) {
int reading_nodes_when_called
= get_reading_node_counter();
int save_connection_node_limit
= connection_node_limit
;
#if USE_PERSISTENT_CONNECTION_CACHE == 1
if (board
[str1
] == EMPTY
|| board
[str2
] == EMPTY
)
str1
= find_origin(str1
);
str2
= find_origin(str2
);
#if USE_PERSISTENT_CONNECTION_CACHE == 1
if (!search_persistent_connection_cache(CONNECT
, str1
, str2
,
gprintf("Persistent cache found connect %1m %1m: %d %1m\n",
str1
, str2
, result2
, move2
);
#if USE_PERSISTENT_CONNECTION_CACHE == 2
if (search_persistent_connection_cache(CONNECT
, str1
, str2
, &result
, move
))
connection_node_limit
*= pow(1.45, -stackp
+ get_depth_modification());
memset(connection_shadow
, 0, sizeof(connection_shadow
));
result
= recursive_connect2(str1
, str2
, move
, 0);
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
connection_node_limit
= save_connection_node_limit
;
#if USE_PERSISTENT_CONNECTION_CACHE == 1
gprintf("Persistent cache failure connect %1m %1m: %d %1m != %d %1m\n",
str1
, str2
, result
, *move
, result2
, move2
);
gprintf("%oconnect %1M %1M, result %d %1M (%d, %d nodes, %f seconds)\n",
str1
, str2
, result
, *move
,
nodes_connect
, tactical_nodes
, gg_cputime() - start
);
gprintf("%oconnect %1m %1m %d %1m ", str1
, str2
, result
, *move
);
#if USE_PERSISTENT_CONNECTION_CACHE > 0
store_persistent_connection_cache(CONNECT
, str1
, str2
, result
, *move
,
tactical_nodes
, connection_shadow
);
return recursive_connect(str1
, str2
, move
);
/* returns WIN if str1 and str2 can be connected. */
recursive_connect(int str1
, int str2
, int *move
)
int i
, res
= 0, Moves
[MAX_MOVES
], ForcedMoves
[MAX_MOVES
];
SETUP_TRACE_INFO2("recursive_connect", str1
, str2
);
if (board
[str1
] == EMPTY
|| board
[str2
] == EMPTY
) {
SGFTRACE2(PASS_MOVE
, 0, "one string already captured");
if (same_string(str1
, str2
)) {
SGFTRACE2(PASS_MOVE
, WIN
, "already connected");
if (nodes_connect
> connection_node_limit
) {
SGFTRACE2(PASS_MOVE
, 0, "connection node limit reached");
if (stackp
== connect_depth
) {
SGFTRACE2(PASS_MOVE
, 0, "connection depth limit reached");
global_connection_node_counter
++;
if (quiescence_connect (str1
, str2
, move
)) {
SGFTRACE2(*move
, WIN
, "quiescence_connect");
/* if one of the strings to connect can be captured
* and there are forced moves to prevent the capture
* then the only moves to try are the moves that
* defend the string: all the other moves will
* lead to the capture of the string
if (!prevent_capture_one_move(ForcedMoves
, str1
))
prevent_capture_one_move(ForcedMoves
, str2
);
else if (prevent_capture_two_moves(ForcedMoves
, str1
))
else if (prevent_capture_two_moves(ForcedMoves
, str2
))
/* We are at a max node, so any move we can find
* is ok. Try moves that can connect in three moves
* because the function that prevent connection in one
* and two moves are called at AND nodes.
moves_to_connect_in_three_moves(Moves
, str1
, str2
, 1);
/* if there are some forced moves to prevent the capture
* of one of the two strings, then we only look at
* the moves that prevent capture and that might also
if (ForcedMoves
[0] != 0 && Moves
[0] != 0)
intersection_array(Moves
, ForcedMoves
);
order_connection_moves(Moves
, str1
, str2
, board
[str1
],
for (i
= 1; ((i
< Moves
[0] + 1) && (res
== 0)); i
++) {
if (trymove(Moves
[i
], board
[str1
], "recursive_connect", str1
)) {
if (!recursive_disconnect(str1
, str2
, move
)) {
SGFTRACE2(*move
, WIN
, "success");
SGFTRACE2(PASS_MOVE
, 0, "failure");
/* Externally callable frontend to recursive_disconnect().
* Returns WIN if str1 and str2 can be disconnected.
disconnect(int str1
, int str2
, int *move
)
if (alternate_connections
) {
int reading_nodes_when_called
= get_reading_node_counter();
int save_connection_node_limit
= connection_node_limit
;
#if USE_PERSISTENT_CONNECTION_CACHE == 1
if (board
[str1
] == EMPTY
|| board
[str2
] == EMPTY
)
str1
= find_origin(str1
);
str2
= find_origin(str2
);
#if USE_PERSISTENT_CONNECTION_CACHE == 1
if (!search_persistent_connection_cache(DISCONNECT
, str1
, str2
,
gprintf("Persistent cache found disconnect %1m %1m: %d %1m\n",
str1
, str2
, result2
, move2
);
#if USE_PERSISTENT_CONNECTION_CACHE == 2
if (search_persistent_connection_cache(DISCONNECT
, str1
, str2
,
connection_node_limit
*= pow(1.5, -stackp
+ get_depth_modification());
memset(connection_shadow
, 0, sizeof(connection_shadow
));
result
= recursive_disconnect2(str1
, str2
, move
, 0);
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
connection_node_limit
= save_connection_node_limit
;
#if USE_PERSISTENT_CONNECTION_CACHE == 1
gprintf("Persistent cache failure disconnect %1m %1m: %d %1m != %d %1m\n",
str1
, str2
, result
, *move
, result2
, move2
);
gprintf("%odisconnect %1m %1m, result %d %1m (%d, %d nodes, %f seconds)\n",
str1
, str2
, result
, *move
,
nodes_connect
, tactical_nodes
, gg_cputime() - start
);
gprintf("%odisconnect %1m %1m %d %1m ", str1
, str2
, result
, *move
);
#if USE_PERSISTENT_CONNECTION_CACHE > 0
store_persistent_connection_cache(DISCONNECT
, str1
, str2
, result
, *move
,
tactical_nodes
, connection_shadow
);
moves_to_prevent_connection_in_three_moves(Moves
, str1
, str2
);
order_connection_moves(Moves
, str1
, str2
, OTHER_COLOR(board
[str1
]),
for (i
= 1; ((i
< Moves
[0] + 1) && (res
== 0)); i
++)
if (trymove(Moves
[i
], OTHER_COLOR(board
[str1
]),
if (!recursive_connect(str1
, str2
, move
)) {
/* Externally callable frontend to recursive_disconnect().
* Returns WIN if str1 and str2 can be disconnected.
* Uses much lower node and depths limits.
fast_disconnect(int str1
, int str2
, int *move
)
int save_limit
= connection_node_limit
;
int save_verbose
= verbose
;
if (board
[str1
] == EMPTY
|| board
[str2
] == EMPTY
)
str1
= find_origin(str1
);
str2
= find_origin(str2
);
connection_node_limit
/= 4;
result
= recursive_disconnect2(str1
, str2
, move
, 0);
connection_node_limit
= save_limit
;
/* Returns WIN if str1 and str2 can be disconnected. */
recursive_disconnect(int str1
, int str2
, int *move
)
int i
, res
= WIN
, Moves
[MAX_MOVES
];
SETUP_TRACE_INFO2("recursive_disconnect", str1
, str2
);
if (board
[str1
] == EMPTY
|| board
[str2
] == EMPTY
) {
SGFTRACE2(PASS_MOVE
, WIN
, "one string already captured");
if (quiescence_capture(str1
, move
)) {
SGFTRACE2(*move
, WIN
, "first string capturable");
if (quiescence_capture(str2
, move
)) {
SGFTRACE2(*move
, WIN
, "second string capturable");
if (same_string(str1
, str2
)) {
SGFTRACE2(PASS_MOVE
, 0, "already connected");
if (nodes_connect
> connection_node_limit
) {
SGFTRACE2(PASS_MOVE
, WIN
, "connection node limit reached");
if (stackp
== connect_depth
) {
SGFTRACE2(PASS_MOVE
, WIN
, "connection depth limit reached");
global_connection_node_counter
++;
* only look at forced moves here,
* it ensures that the result of recursive_disconnect
* is proved if it returns 0 (that is connections are proved)
if (prevent_connection_one_move(Moves
, str1
, str2
))
else if (prevent_connection_two_moves(Moves
, str1
, str2
))
else if (prevent_simple_connection_three_moves(Moves
, str1
, str2
))
order_connection_moves(Moves
, str1
, str2
, OTHER_COLOR(board
[str1
]),
for (i
= 1; ((i
< Moves
[0] + 1) && (res
== 0)); i
++)
if (trymove(Moves
[i
], OTHER_COLOR(board
[str1
]),
"recursive_disconnect", str1
)) {
if (!recursive_connect(str1
, str2
, move
)) {
SGFTRACE2(*move
, WIN
, "success");
SGFTRACE2(PASS_MOVE
, 0, "failure");
quiescence_capture(int str
, int *move
)
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
/* We turn off the sgf traces here to avoid cluttering them up with
if (countlib(str
) == 1) {
else if (countlib(str
) == 2)
result
= simple_ladder(str
, move
);
/* Turn the sgf traces back on. */
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
capture_one_move(int str
)
/* Find all the possible moves that can prevent the capture
prevent_capture_one_move(int *moves
, int str1
)
int liberties
, libs
[MAXLIBS
];
liberties
= findlib(str1
, MAXLIBS
, libs
);
add_array(moves
, libs
[0]);
adj
= chainlinks2(str1
, adjs
, 1);
for (r
= 0; r
< adj
; r
++) {
findlib(adjs
[r
], 1, libs
);
add_array(moves
, libs
[0]);
/* Returns WIN if str1, str2 and str3 can be connected. */
recursive_transitivity(int str1
, int str2
, int str3
, int *move
)
int i
, res
= 0, Moves
[MAX_MOVES
], ForcedMoves
[MAX_MOVES
];
SETUP_TRACE_INFO2("recursive_transitivity", str1
, str3
);
if (board
[str1
] == EMPTY
|| board
[str2
] == EMPTY
|| board
[str3
] == EMPTY
) {
SGFTRACE2(PASS_MOVE
, 0, "one string already captured");
if (same_string(str1
, str2
) && same_string(str1
, str3
)) {
SGFTRACE2(PASS_MOVE
, WIN
, "already connected");
if (nodes_connect
> connection_node_limit
) {
SGFTRACE2(PASS_MOVE
, 0, "connection node limit reached");
if (stackp
== connect_depth
) {
SGFTRACE2(PASS_MOVE
, 0, "connection depth limit reached");
global_connection_node_counter
++;
if (same_string(str1
, str2
))
if (quiescence_connect (str1
, str3
, move
)) {
SGFTRACE2(*move
, WIN
, "quiescence_connect");
if (same_string(str2
, str3
))
if (quiescence_connect (str1
, str2
, move
)) {
SGFTRACE2(*move
, WIN
, "quiescence_connect");
/* If one of the strings to connect can be captured
* and there are forced moves to prevent the capture
* then the only moves to try are the moves that
* defend the string. All the other moves will
* lead to the capture of the string.
if (!prevent_capture_one_move(ForcedMoves
, str1
))
if (!prevent_capture_one_move(ForcedMoves
, str2
))
prevent_capture_one_move(ForcedMoves
, str3
);
/* We are at a max node, so any move we can find
* is ok. Try moves that can connect in two moves
* because the function that prevents connection in one
* move is called at and nodes.
moves_to_connect_in_two_moves(Moves
, str1
, str2
);
moves_to_connect_in_two_moves(Moves
, str2
, str3
);
/* If there are some forced moves to prevent the capture
* of one of the two strings, then we only look at
* the moves that prevent capture and that might also
if ((ForcedMoves
[0] != 0) && (Moves
[0] != 0))
intersection_array(Moves
, ForcedMoves
);
order_connection_moves(Moves
, str1
, str2
, board
[str1
],
"recursive_transitivity");
for (i
= 1; ((i
< Moves
[0] + 1) && (res
== 0)); i
++) {
if (trymove(Moves
[i
], board
[str1
], "recursive_transitivity", str1
)) {
if (!recursive_non_transitivity(str1
, str2
, str3
, move
)) {
SGFTRACE2(*move
, WIN
, "success");
SGFTRACE2(PASS_MOVE
, 0, "failure");
/* It is often assumed that if str1 connects to str2 and str2
* connects to str3 then str1 connects to str3. This is called
* TRANSITIVITY. However there are exceptions such as this
* Although strings A and B are connected, and strings B and C
* are connected, a move at * disconnects strings A and C.
* This function is a public frontend to recursive_non_transitivity().
* Returns WIN if str1, str2 and str3 can be disconnected.
non_transitivity(int str1
, int str2
, int str3
, int *move
)
int i
, res
= WIN
, Moves
[MAX_MOVES
];
moves_to_prevent_connection_in_three_moves(Moves
, str1
, str3
);
order_connection_moves(Moves
, str1
, str2
, OTHER_COLOR(board
[str1
]),
for (i
= 1; ((i
< Moves
[0] + 1) && (res
== 0)); i
++)
if (trymove(Moves
[i
], OTHER_COLOR(board
[str1
]),
"non_transitivity", str1
)) {
if (!recursive_transitivity(str1
, str2
, str3
, move
)) {
/* Returns WIN if str1, str2 and str3 can be disconnected. */
recursive_non_transitivity(int str1
, int str2
, int str3
, int *move
)
int i
, res
= WIN
, Moves
[MAX_MOVES
];
SETUP_TRACE_INFO2("recursive_non_transitivity", str1
, str3
);
if (board
[str1
] == EMPTY
|| board
[str2
] == EMPTY
|| board
[str3
] == EMPTY
) {
SGFTRACE2(PASS_MOVE
, WIN
, "one string already captured");
if (quiescence_capture(str1
, move
)) {
SGFTRACE2(*move
, WIN
, "first string capturable");
if (quiescence_capture(str2
, move
)) {
SGFTRACE2(*move
, WIN
, "second string capturable");
if (quiescence_capture(str3
, move
)) {
SGFTRACE2(*move
, WIN
, "third string capturable");
if (same_string(str1
, str2
) && same_string(str1
, str3
)) {
SGFTRACE2(PASS_MOVE
, 0, "already connected");
if (nodes_connect
> connection_node_limit
) {
SGFTRACE2(PASS_MOVE
, WIN
, "connection node limit reached");
if (stackp
== connect_depth
) {
SGFTRACE2(PASS_MOVE
, WIN
, "connection depth limit reached");
global_connection_node_counter
++;
/* We are at an and node. Only look at forced moves. */
if (prevent_connection_one_move(Moves
, str1
, str3
))
else if (prevent_connection_two_moves(Moves
, str1
, str3
))
else if (prevent_simple_connection_three_moves(Moves
, str1
, str3
))
order_connection_moves(Moves
, str1
, str2
, OTHER_COLOR(board
[str1
]),
"recursive_non_transitivity");
for (i
= 1; ((i
< Moves
[0] + 1) && (res
== 0)); i
++)
if (trymove(Moves
[i
], OTHER_COLOR(board
[str1
]),
"recursive_non_transitivity", str1
)) {
if (!recursive_transitivity(str1
, str2
, str3
, move
)) {
SGFTRACE2(*move
, WIN
, "success");
SGFTRACE2(PASS_MOVE
, 0, "failure");
/* Order the moves so that we try the ones likely to succeed early. */
order_connection_moves(int *moves
, int str1
, int str2
, int color_to_move
,
for (r
= 1; r
<= moves
[0]; 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.
* We don't use all these values. They are only here so we can
* reuse incremental_order_moves() which was developed for the
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_to_move
, str1
, &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
);
libs
= approxlib(move
, color_to_move
, 10, NULL
);
if (libs
== 1 && captured_stones
== 0)
/* Good to get many liberties. */
/* Very good to capture opponent stones. */
scores
[r
] += 5 + captured_stones
;
/* Good to threaten opponent stones. */
if (threatened_stones
> 0)
/* Extremely good to save own stones. */
scores
[r
] += 10 + saved_stones
;
/* 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
= 1; i
<= moves
[0]; i
++) {
/* Find the move with the biggest score. */
int maxscore
= scores
[i
];
for (j
= i
+1; j
<= moves
[0]; j
++) {
if (scores
[j
] > maxscore
) {
/* Now exchange the move at i with the move at max_at.
* Don't forget to exchange the scores as well.
moves
[i
] = moves
[max_at
];
scores
[i
] = scores
[max_at
];
scores
[max_at
] = tempmax
;
gprintf("%oVariation %d:\n", count_variations
);
for (i
= 1; i
<= moves
[0]; i
++)
gprintf("%o %1M %d\n", moves
[i
], scores
[i
]);
sprintf(buf
, "Move order for %s: %n", funcname
, &chars
);
for (i
= 1; i
<= moves
[0]; i
++) {
sprintf(pos
, "%c%d (%d) %n", J(moves
[i
]) + 'A' + (J(moves
[i
]) >= 8),
board_size
- I(moves
[i
]), scores
[i
], &chars
);
sgftreeAddComment(sgf_dumptree
, buf
);
reset_connection_node_counter()
global_connection_node_counter
= 0;
/* Retrieve statistics. */
get_connection_node_counter()
return global_connection_node_counter
;
/*********************************************************
* Alternate connection reading algorithm.
* This code is enabled with the --enable-alternate-connections
* configure flag at build time or toggled with the
* --alternate-connections option at run time.
*********************************************************/
/* This has been copied from reading.c and modified.
#define ADD_CANDIDATE_MOVE(move, distance, moves, distances, num_moves)\
for (l = 0; l < num_moves; l++)\
if (moves[l] == (move)) {\
if (distances[l] > distance)\
distances[l] = distance;\
if ((l == num_moves) && (num_moves < MAX_MOVES)) {\
moves[num_moves] = move;\
distances[num_moves] = distance;\
static int find_string_connection_moves(int str1
, int str2
, int color_to_move
,
static void clear_connection_data(struct connection_data
*conn
);
static int trivial_connection(int str1
, int str2
, int *move
);
static int does_secure_through_ladder(int color
, int move
, int pos
);
static int ladder_capture(int str
, int *move
);
static int ladder_capturable(int pos
, int color
);
static int no_escape_from_atari(int str
);
static int no_escape_from_ladder(int str
);
static int check_self_atari(int pos
, int color_to_move
);
static int common_vulnerabilities(int a1
, int a2
, int b1
, int b2
, int color
);
static int common_vulnerability(int apos
, int bpos
, int color
);
/* Try to connect two strings. This function is called in a mutual
* recursion with recursive_disconnect2(). Return codes is identical to
* the tactical reading functions. For the has_passed parameter, see the
* documentation of recursive_disconnect2().
* 1. Check if the strings are trivially connected or disconnected or
* the result is already cached.
* 2. Find connection moves.
* 3. Try one move at a time and call recursive_disconnect2() to see
* whether we were successful.
* 4. If no move was found we assume success if the connection
* distance was small and failure otherwise.
recursive_connect2(int str1
, int str2
, int *move
, int has_passed
)
SETUP_TRACE_INFO2("recursive_connect2", str1
, str2
);
global_connection_node_counter
++;
if (board
[str1
] == EMPTY
|| board
[str2
] == EMPTY
) {
SGFTRACE2(PASS_MOVE
, 0, "one string already captured");
if (same_string(str1
, str2
)) {
SGFTRACE2(PASS_MOVE
, WIN
, "already connected");
if (nodes_connect
> connection_node_limit
) {
SGFTRACE2(PASS_MOVE
, 0, "connection node limit reached");
if (stackp
> connect_depth2
) {
SGFTRACE2(PASS_MOVE
, 0, "connection depth limit reached");
str1
= find_origin(str1
);
str2
= find_origin(str2
);
if (stackp
<= depth
&& !has_passed
&& tt_get(&ttable
, CONNECT
, str1
, str2
, depth
- stackp
, NULL
,
&value
, NULL
, &xpos
) == 2) {
TRACE_CACHED_RESULT2(value
, value
, xpos
);
SGFTRACE2(xpos
, value
, "cached");
if (trivial_connection(str1
, str2
, &xpos
) == WIN
) {
SGFTRACE2(xpos
, WIN
, "trivial connection");
READ_RETURN_CONN(CONNECT
, str1
, str2
, depth
- stackp
, move
, xpos
, WIN
);
num_moves
= find_string_connection_moves(str1
, str2
, color
,
for (k
= 0; k
< num_moves
; k
++) {
if (komaster_trymove(xpos
, color
, "recursive_connect2", str1
,
&ko_move
, stackp
<= ko_depth
&& savecode
== 0)) {
int acode
= recursive_disconnect2(str1
, str2
, NULL
,
SGFTRACE2(xpos
, WIN
, "connection effective");
READ_RETURN_CONN(CONNECT
, str1
, str2
, depth
- stackp
,
/* if the move works with ko we save it, then look for something
UPDATE_SAVED_KO_RESULT(savecode
, savemove
, acode
, xpos
);
if (recursive_disconnect2(str1
, str2
, NULL
,
if (tried_moves
== 0 && distance
< FP(1.0)) {
SGFTRACE2(NO_MOVE
, WIN
, "no move, probably connected");
READ_RETURN_CONN(CONNECT
, str1
, str2
, depth
- stackp
, move
, NO_MOVE
, WIN
);
SGFTRACE2(savemove
, savecode
, "saved move");
READ_RETURN_CONN(CONNECT
, str1
, str2
, depth
- stackp
,
move
, savemove
, savecode
);
READ_RETURN_CONN(CONNECT
, str1
, str2
, depth
- stackp
, move
, NO_MOVE
, 0);
/* Try to disconnect two strings. This function is called in a mutual
* recursion with recursive_connect2(). Return codes is identical to
* the tactical reading functions.
* 1. Check if the strings are trivially connected or disconnected or
* the result is already cached.
* 2. Find disconnection moves.
* 3. Try one move at a time and call recursive_connect2() to see
* whether we were successful.
* 4. If no move was found we assume failure if the connection
* distance was small. Otherwise we pass and let
* recursive_connect2() try to connect. However, if we already have
* passed once we just declare success. Whether a pass already has
* been made is indicated by the has_passed parameter.
recursive_disconnect2(int str1
, int str2
, int *move
, int has_passed
)
int other
= OTHER_COLOR(color
);
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
SETUP_TRACE_INFO2("recursive_disconnect2", str1
, str2
);
global_connection_node_counter
++;
if (board
[str1
] == EMPTY
|| board
[str2
] == EMPTY
) {
SGFTRACE2(PASS_MOVE
, WIN
, "one string already captured");
if (same_string(str1
, str2
)) {
SGFTRACE2(PASS_MOVE
, 0, "already connected");
if (nodes_connect
> connection_node_limit
) {
SGFTRACE2(PASS_MOVE
, WIN
, "connection node limit reached");
if (stackp
> connect_depth2
) {
SGFTRACE2(PASS_MOVE
, WIN
, "connection depth limit reached");
str1
= find_origin(str1
);
str2
= find_origin(str2
);
attack_code1
= attack(str1
, &attack_pos1
);
if (attack_code1
== WIN
) {
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
SGFTRACE2(attack_pos1
, WIN
, "one string is capturable");
attack_code2
= attack(str2
, &attack_pos2
);
if (attack_code2
== WIN
) {
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
SGFTRACE2(attack_pos2
, WIN
, "one string is capturable");
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
&& tt_get(&ttable
, DISCONNECT
, str1
, str2
,
&value
, NULL
, &xpos
) == 2) {
TRACE_CACHED_RESULT2(value
, value
, xpos
);
SGFTRACE2(xpos
, value
, "cached");
if (ladder_capture(str1
, &xpos
) == WIN
) {
SGFTRACE2(xpos
, WIN
, "first string capturable");
READ_RETURN_CONN(DISCONNECT
, str1
, str2
, depth
- stackp
, move
, xpos
, WIN
);
if (ladder_capture(str2
, &xpos
) == WIN
) {
SGFTRACE2(xpos
, WIN
, "second string capturable");
READ_RETURN_CONN(DISCONNECT
, str1
, str2
, depth
- stackp
, move
, xpos
, WIN
);
num_moves
= find_string_connection_moves(str1
, str2
, other
,
if (attack_code1
!= 0 && num_moves
< MAX_MOVES
) {
for (k
= 0; k
< num_moves
; k
++) {
if (moves
[k
] == attack_pos1
)
moves
[num_moves
++] = attack_pos1
;
if (attack_code2
!= 0 && num_moves
< MAX_MOVES
) {
for (k
= 0; k
< num_moves
; k
++) {
if (moves
[k
] == attack_pos2
)
moves
[num_moves
++] = attack_pos2
;
for (k
= 0; k
< num_moves
; k
++) {
if (komaster_trymove(xpos
, other
, "recursive_disconnect2", str1
,
&ko_move
, stackp
<= ko_depth
&& savecode
== 0)) {
int dcode
= recursive_connect2(str1
, str2
, NULL
,
SGFTRACE2(xpos
, WIN
, "disconnection effective");
READ_RETURN_CONN(DISCONNECT
, str1
, str2
, depth
- stackp
,
/* if the move works with ko we save it, then look for something
UPDATE_SAVED_KO_RESULT(savecode
, savemove
, dcode
, xpos
);
if (recursive_connect2(str1
, str2
, NULL
,
|| !recursive_connect2(str1
, str2
, NULL
, 1))) {
SGFTRACE2(NO_MOVE
, WIN
, "no move, probably disconnected");
READ_RETURN_CONN(DISCONNECT
, str1
, str2
, depth
- stackp
,
SGFTRACE2(savemove
, savecode
, "saved move");
READ_RETURN_CONN(DISCONNECT
, str1
, str2
, depth
- stackp
,
move
, savemove
, savecode
);
READ_RETURN_CONN(DISCONNECT
, str1
, str2
, depth
- stackp
, move
, NO_MOVE
, 0);
/* Find moves to connect or disconnect the two strings str1 and str2.
* If color_to_move equals the color of the strings we search for
* connecting moves and otherwise disconnecting moves. The moves are
* returned in the moves[] array and the number of moves is the return
* value of the function. The parameter *total_distance is set to the
* approximated connection distance between the two strings. This is
* most useful when no moves are found. If *total_distance is small
* they are probably already effectively connected and if it is huge
* they are probably disconnected.
* The algorithm is to compute connection distances around each string
* and find points where the sum of the distances is small, or more
* exactly where the sum of the distances after the move would be
* small. This can be done with help of delta values returned together
* with distance values from the function
* compute_connection_distances(). This "distance after move" measure
* is modified with various bonuses and then used to order the found
find_connection_moves(int str1
, int str2
, int color_to_move
,
struct connection_data
*conn1
,
struct connection_data
*conn2
,
int max_dist1
, int max_dist2
,
int moves
[MAX_MOVES
], int total_distance
,
int other
= OTHER_COLOR(color
);
int connect_move
= (color_to_move
== color
);
int distances
[MAX_MOVES
];
int attack_move
= NO_MOVE
;
int defense_move
= NO_MOVE
;
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
/* We turn off the sgf traces here to avoid cluttering them up with
* tactical reading moves.
/* Loop through the points with smallish distance from str1 and look
* for ones also having a small distance to str2.
for (r
= 0; r
< conn1
->queue_end
; r
++) {
int pos
= conn1
->queue
[r
];
int dist1
= conn1
->distances
[pos
];
int deltadist1
= conn1
->deltas
[pos
];
int dist2
= conn2
->distances
[pos
];
int deltadist2
= conn2
->deltas
[pos
];
if (dist1
- deltadist1
+ dist2
- deltadist2
> FP(2.5)
|| dist1
> max_dist1
+ FP(0.2)
|| dist2
> max_dist2
+ FP(0.2))
gprintf("%oMove %1m, (%f, %f, %f, %f)\n", pos
,
FIXED_TO_FLOAT(dist1
), FIXED_TO_FLOAT(deltadist1
),
FIXED_TO_FLOAT(dist2
), FIXED_TO_FLOAT(deltadist2
));
/* The basic quality of the move is the sum of the distances to
* each string minus the two delta values. This distance value
* will subsequently be modified to take other factors into
gprintf("%o %f, primary distance\n", FIXED_TO_FLOAT(distance
));
/* Bonus if d1 and d2 are well balanced. */
if ((3 * d1
) / 2 > d2
&& (3 * d2
) / 2 > d1
) {
gprintf("%o -0.1, well balanced\n");
/* Check whether the move is "between" the two strings. */
if (conn1
->coming_from
[pos
] != NO_MOVE
&& conn1
->coming_from
[pos
] == conn2
->coming_from
[pos
]) {
gprintf("%o discarded, not between strings\n");
if (board
[pos
] == EMPTY
) {
if (check_self_atari(pos
, color_to_move
)) {
ADD_CANDIDATE_MOVE(pos
, distance
, moves
, distances
, num_moves
);
gprintf("%o discarded, self atari\n");
else if (board
[pos
] == other
) {
attack_and_defend(pos
, &acode
, &attack_move
, &dcode
, &defense_move
);
gprintf("%o attack with code %d at %1m, defense with code %d at %1m\n",
acode
, attack_move
, dcode
, defense_move
);
if (connect_move
&& acode
!= 0) {
gprintf("%o +0.5, no defense\n");
if (conn1
->distances
[attack_move
]
+ conn2
->distances
[attack_move
] > dist1
+ dist2
) {
gprintf("%o +0.5, attack point not on shortest path\n");
ADD_CANDIDATE_MOVE(attack_move
, distance
- FP(0.15), moves
, distances
,
gprintf("%o -0.15 at %1m, capturing a string\n", attack_move
);
else if (!connect_move
&& acode
!= 0 && dcode
!= 0) {
ADD_CANDIDATE_MOVE(defense_move
, distance
- FP(0.5), moves
, distances
,
gprintf("%o -0.5 at %1m, defending a string\n", defense_move
);
else if (board
[pos
] == color
) {
/* Check whether there are common vulnerable points. */
for (k
= 0; k
< 4; k
++) {
apos
= conn1
->vulnerable1
[pos
];
apos
= conn1
->vulnerable2
[pos
];
bpos
= conn2
->vulnerable1
[pos
];
bpos
= conn2
->vulnerable2
[pos
];
if (common_vulnerability(apos
, bpos
, color
)) {
if (check_self_atari(apos
, color_to_move
)) {
ADD_CANDIDATE_MOVE(apos
, distance
, moves
, distances
, num_moves
);
gprintf("%o +0.0 at %1m, vulnerability\n", apos
);
&& check_self_atari(bpos
, color_to_move
)) {
ADD_CANDIDATE_MOVE(bpos
, distance
, moves
, distances
, num_moves
);
gprintf("%o +0.0 at %1m, vulnerability\n", bpos
);
/* Modify the distance values for the moves with various bonuses. */
for (r
= 0; r
< num_moves
; r
++) {
int adjacent_to_attacker
= 0;
for (k
= 0; k
< 4; k
++) {
int pos
= move
+ delta
[k
];
if (board
[pos
] == other
) {
adjacent_to_attacker
= 1;
distances
[r
] -= FP(0.15);
gprintf("%o%1M -0.15, adjacent to attacker string\n", move
);
if (countlib(pos
) <= 2) {
gprintf("%o%1M -0.2, adjacent to attacker string with at most two liberties\n", move
);
if ((connect_move
|| !bonus_given
)
&& (conn1
->distances
[move
] - conn1
->deltas
[move
] <= FP(0.5)
|| conn1
->distances
[pos
] - conn1
->deltas
[pos
] <= FP(0.5))
&& (conn2
->distances
[move
] - conn2
->deltas
[move
] <= FP(0.5)
|| conn2
->distances
[pos
] - conn2
->deltas
[pos
] <= FP(0.5))
&& conn1
->distances
[pos
] < total_distance
&& conn2
->distances
[pos
] < total_distance
) {
gprintf("%o%1M -0.7, capture or atari of immediately connecting string\n", move
);
else if (board
[pos
] == color
) {
if (countlib(pos
) <= 2) {
gprintf("%o%1M -0.2, adjacent to defender string with at most two liberties\n", move
);
/* The code above (in the 'board[pos] == other' branch) makes
* perfect sense for the defender, but has a tendency to
* overestimate solid connection defenses when the attacker's
* stones happen to be in atari, specially when capturing some
* defender stones instead would help just as well, if not better.
* The following code compensates in such kind of situations.
* See connection:111 and gunnar:53 for example.
if (!connect_move
&& countlib(pos
) == 1
/* let's avoid ko and snapbacks */
&& accuratelib(move
, other
, 2, NULL
) > 1) {
bonus
= FP(0.1) * chainlinks2(pos
, adjs
, 2);
bonus
+= FP(0.5) * chainlinks2(pos
, adjs
, 1);
gprintf("%o%1M -%f, capture of defender string\n",
move
, FIXED_TO_FLOAT(bonus
));
&& is_edge_vertex(move
)) {
gprintf("%o%1M -0.1, disconnect move on edge\n", move
);
if (ladder_capturable(move
, color_to_move
)) {
gprintf("%o%1M +0.3, can be captured in a ladder\n", move
);
/* Bonus for moves adjacent to endpoint strings with 3 liberties.
* Neighbor strings with less than 3 liberties have already
* generated a bonus above.
if ((liberty_of_string(move
, str1
)
|| (ON_BOARD(str2
) && liberty_of_string(move
, str2
)
&& countlib(str2
) == 3)) {
gprintf("%o%1M -0.1, liberty of endpoint string with 3 libs\n", move
);
/* Turn the sgf traces back on. */
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* 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
= 0; i
< num_moves
; i
++) {
/* Find the move with the smallest distance. */
int mindistance
= distances
[i
];
for (j
= i
+ 1; j
< num_moves
; j
++) {
if (distances
[j
] < mindistance
) {
mindistance
= distances
[j
];
/* Now exchange the move at i with the move at min_at.
* Don't forget to exchange the distances as well.
int tempmin
= distances
[i
];
moves
[i
] = moves
[min_at
];
distances
[i
] = distances
[min_at
];
distances
[min_at
] = tempmin
;
gprintf("%oSorted moves:\n");
for (i
= 0; i
< num_moves
; i
++)
gprintf("%o%1M %f\n", moves
[i
], FIXED_TO_FLOAT(distances
[i
]));
sprintf(buf
, "Move order for %sconnect: %n",
connect_move
? "" : "dis", &chars
);
for (i
= 0; i
< num_moves
; i
++) {
sprintf(pos
, "%c%d (%4.2f) %n", J(moves
[i
]) + 'A' + (J(moves
[i
]) >= 8),
board_size
- I(moves
[i
]), FIXED_TO_FLOAT(distances
[i
]),
if (cutoff
< HUGE_CONNECTION_DISTANCE
) {
sprintf(pos
, "(cutoff %f)%n", FIXED_TO_FLOAT(cutoff
), &chars
);
sgftreeAddComment(sgf_dumptree
, buf
);
/* Filter out moves with distance at least 1.5 more than the best
* move, or with distance higher than the cutoff specified.
* In order to further reduce the branching factor, a decreasing
* cutoff is applied between candidates. For instance, in this case
* 1. d 2. d+0.5 3. d+1.0 4. d+1.5
* the 4th candidate will be tested, while in following one
* 1. d 2. d+0.1 3. d+0.2 4. d+1.5
if (num_moves
<= 1 || !is_ko(moves
[0], color_to_move
, NULL
))
distance_limit
= distances
[0] + FP(1.5);
distance_limit
= distances
[1] + FP(1.5);
/* Special case: If the second best move has a distance less than 1,
* include it if even if the best move has a very low distance.
&& distances
[1] < FP(1.0)
&& distances
[1] > distance_limit
)
distance_limit
= distances
[1];
for (r
= 0; r
< num_moves
; r
++) {
&& distances
[r
] > distances
[r
-1]
&& distances
[r
] - distances
[r
-1] > (8 - r
) * FP(0.2))
if (distances
[r
] > distance_limit
|| distances
[r
] > cutoff
)
find_string_connection_moves(int str1
, int str2
, int color_to_move
,
int moves
[MAX_MOVES
], int *total_distance
)
struct connection_data conn1
;
struct connection_data conn2
;
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
/* We turn off the sgf traces here to avoid cluttering them up with
* tactical reading moves.
compute_connection_distances(str1
, str2
, FP(3.051), &conn1
, 1);
compute_connection_distances(str2
, str1
, FP(3.051), &conn2
, 1);
if (findlib(str1
, 1, &lib
) == 1) {
conn1
.distances
[lib
] = 0;
conn1
.coming_from
[lib
] = NO_MOVE
;
conn2
.distances
[lib
] = conn2
.distances
[str1
];
conn2
.coming_from
[lib
] = conn1
.coming_from
[str1
];
if (findlib(str2
, 1, &lib
) == 1) {
conn2
.distances
[lib
] = 0;
conn1
.distances
[lib
] = conn1
.distances
[str2
];
max_dist1
= conn1
.distances
[str2
];
max_dist2
= conn2
.distances
[str1
];
*total_distance
= gg_min(max_dist1
, max_dist2
);
gprintf("%oVariation %d\n", save_count_variations
);
print_connection_distances(&conn1
);
print_connection_distances(&conn2
);
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
num_moves
= find_connection_moves(str1
, str2
, color_to_move
,
&conn1
, &conn2
, max_dist1
, max_dist2
,
HUGE_CONNECTION_DISTANCE
);
add_to_start_queue(int pos
, int dist
, struct connection_data
*conn
)
conn
->queue
[conn
->queue_end
++] = pos
;
conn
->distances
[pos
] = dist
;
conn
->deltas
[pos
] = dist
;
conn
->coming_from
[pos
] = NO_MOVE
;
conn
->vulnerable1
[pos
] = NO_MOVE
;
conn
->vulnerable2
[pos
] = NO_MOVE
;
init_connection_data(int color
, const signed char goal
[BOARDMAX
],
struct connection_data
*conn
, int speculative
)
signed char mark
[BOARDMAX
];
memset(mark
, 0, BOARDMAX
);
VALGRIND_MAKE_WRITABLE(conn
, sizeof(conn
));
clear_connection_data(conn
);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] == color
) {
int origin
= find_origin(pos
);
add_to_start_queue(origin
, FP(0.0), conn
);
else if (board
[pos
] == EMPTY
)
add_to_start_queue(pos
, FP(1.0), conn
);
conn
->cutoff_distance
= cutoff
;
conn
->speculative
= speculative
;
find_break_moves(int str
, const signed char goal
[BOARDMAX
], int color_to_move
,
int moves
[MAX_MOVES
], int *total_distance
)
struct connection_data conn1
;
struct connection_data conn2
;
int max_dist1
= HUGE_CONNECTION_DISTANCE
;
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
/* We turn off the sgf traces here to avoid cluttering them up with
* tactical reading moves.
compute_connection_distances(str
, NO_MOVE
, FP(2.501), &conn1
, 1);
for (k
= 0; k
< conn1
.queue_end
; k
++)
if (board
[conn1
.queue
[k
]] == color
) {
int stones
[MAX_BOARD
* MAX_BOARD
];
int num_stones
= findstones(conn1
.queue
[k
],
MAX_BOARD
* MAX_BOARD
, stones
);
for (i
= 0; i
< num_stones
; i
++) {
str2
= find_origin(stones
[i
]);
TRACE("%oUsing %1m as secondary target.\n", str2
);
mark_string(str2
, breakin_shadow
, 1);
/* Add all stones in the goal to the queue. */
init_connection_data(color
, goal
, str
, FP(2.501), &conn2
, 1);
for (k
= 0; k
< conn2
.queue_end
; k
++) {
if (max_dist1
> conn1
.distances
[conn2
.queue
[k
]])
max_dist1
= conn1
.distances
[conn2
.queue
[k
]];
spread_connection_distances(color
, &conn2
);
if (findlib(str
, 1, &lib
) == 1) {
conn1
.distances
[lib
] = 0;
conn1
.coming_from
[lib
] = NO_MOVE
;
conn2
.distances
[lib
] = conn2
.distances
[str
];
conn2
.coming_from
[lib
] = conn1
.coming_from
[str
];
max_dist2
= conn2
.distances
[str
];
*total_distance
= gg_min(max_dist1
, max_dist2
);
/* Turn the sgf traces back on. */
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
gprintf("%oVariation %d\n", save_count_variations
);
print_connection_distances(&conn1
);
print_connection_distances(&conn2
);
int cutoff
= HUGE_CONNECTION_DISTANCE
;
if (breakin_depth
- stackp
<= 5)
cutoff
= FP(1.101) + (breakin_depth
- stackp
) * FP(0.15);
num_moves
= find_connection_moves(str
, str2
, color_to_move
,
&conn1
, &conn2
, max_dist1
, max_dist2
,
moves
, *total_distance
, cutoff
);
if (color_to_move
!= board
[str
]) {
if (num_moves
< MAX_MOVES
&& ladder_capture(str2
, &move
)) {
moves
[num_moves
++] = move
;
for (k
= 0; k
< num_moves
; k
++)
breakin_shadow
[moves
[k
]] = 1;
/* Can (str) connect to goal[] if the other color moves first? */
recursive_break(int str
, const signed char goal
[BOARDMAX
], int *move
,
SETUP_TRACE_INFO("recursive_break", str
);
global_connection_node_counter
++;
if (board
[str
] == EMPTY
) {
SGFTRACE(PASS_MOVE
, 0, "one string already captured");
if (nodes_connect
> breakin_node_limit
) {
SGFTRACE(PASS_MOVE
, 0, "connection node limit reached");
if (stackp
> breakin_depth
) {
SGFTRACE(PASS_MOVE
, 0, "connection depth limit reached");
if (stackp
<= depth
&& !has_passed
&& tt_get(&ttable
, BREAK_IN
, str
, NO_MOVE
, depth
- stackp
, goal_hash
,
&retval
, NULL
, &xpos
) == 2) {
/* FIXME: Use move for move ordering if tt_get() returned 1 */
TRACE_CACHED_RESULT(retval
, xpos
);
SGFTRACE(xpos
, retval
, "cached");
if (trivial_connection(str1
, str2
, &xpos
) == WIN
) {
SGFTRACE2(xpos
, WIN
, "trivial connection");
READ_RETURN_HASH(BREAK_IN
, str
, depth
- stackp
, goal_hash
,
num_moves
= find_break_moves(str
, goal
, color
, moves
, &distance
);
for (k
= 0; k
< num_moves
; k
++) {
if (komaster_trymove(xpos
, color
, "recursive_break", str
,
&ko_move
, stackp
<= ko_depth
&& savecode
== 0)) {
int acode
= recursive_block(str
, goal
, NULL
, has_passed
, goal_hash
);
SGFTRACE(xpos
, WIN
, "break effective");
READ_RETURN_HASH(BREAK_IN
, str
, depth
- stackp
, goal_hash
,
/* if the move works with ko we save it, then look for something
UPDATE_SAVED_KO_RESULT(savecode
, savemove
, acode
, xpos
);
if (recursive_block(str
, goal
, NULL
, has_passed
, goal_hash
) != WIN
) {
/* Because of a couple differences between the break-in and the
* connection reading code, we can't afford to be as optimistic
* as in recursive_connect2() here. See nando:32
if (tried_moves
== 0 && distance
< FP(0.89)) {
SGFTRACE(NO_MOVE
, WIN
, "no move, probably connected");
READ_RETURN_HASH(BREAK_IN
, str
, depth
- stackp
, goal_hash
,
SGFTRACE(savemove
, savecode
, "saved move");
READ_RETURN_HASH(BREAK_IN
, str
, depth
- stackp
, goal_hash
,
move
, savemove
, savecode
);
READ_RETURN_HASH(BREAK_IN
, str
, depth
- stackp
, goal_hash
, move
, NO_MOVE
, 0);
/* Can (str) connect to goal[] if the other color moves first? */
recursive_block(int str
, const signed char goal
[BOARDMAX
], int *move
,
int has_passed
, Hash_data
*goal_hash
)
int other
= OTHER_COLOR(color
);
SETUP_TRACE_INFO("recursive_block", str
);
global_connection_node_counter
++;
if (board
[str
] == EMPTY
) {
SGFTRACE(PASS_MOVE
, WIN
, "string already captured");
if (same_string(str1
, str2
)) {
SGFTRACE(PASS_MOVE
, 0, "already connected");
if (nodes_connect
> breakin_node_limit
) {
SGFTRACE(PASS_MOVE
, WIN
, "connection node limit reached");
if (stackp
> breakin_depth
) {
SGFTRACE(PASS_MOVE
, WIN
, "connection depth limit reached");
&& tt_get(&ttable
, BLOCK_OFF
, str
, NO_MOVE
,
depth
- stackp
, goal_hash
, &retval
, NULL
, &xpos
) == 2) {
TRACE_CACHED_RESULT(retval
, xpos
);
SGFTRACE(xpos
, retval
, "cached");
if (ladder_capture(str
, &xpos
) == WIN
) {
SGFTRACE(xpos
, WIN
, "string capturable");
READ_RETURN_HASH(BLOCK_OFF
, str
, depth
- stackp
, goal_hash
,
num_moves
= find_break_moves(str
, goal
, other
, moves
, &distance
);
for (k
= 0; k
< num_moves
; k
++) {
if (komaster_trymove(xpos
, other
, "recursive_block", str
,
&ko_move
, stackp
<= ko_depth
&& savecode
== 0)) {
int dcode
= recursive_break(str
, goal
, NULL
, has_passed
, goal_hash
);
SGFTRACE(xpos
, WIN
, "block effective");
READ_RETURN_HASH(BLOCK_OFF
, str
, depth
- stackp
, goal_hash
,
/* if the move works with ko we save it, then look for something
UPDATE_SAVED_KO_RESULT(savecode
, savemove
, dcode
, xpos
);
if (recursive_break(str
, goal
, NULL
,
has_passed
, goal_hash
) != WIN
) {
|| !recursive_break(str
, goal
, NULL
, 1,
SGFTRACE(NO_MOVE
, WIN
, "no move, probably disconnected");
READ_RETURN_HASH(BLOCK_OFF
, str
, depth
- stackp
, goal_hash
,
SGFTRACE(savemove
, savecode
, "saved move");
READ_RETURN_HASH(BLOCK_OFF
, str
, depth
- stackp
, goal_hash
,
move
, savemove
, savecode
);
READ_RETURN_HASH(BLOCK_OFF
, str
, depth
- stackp
, goal_hash
,
/* Externally callable frontend to recursive_break.
* Returns WIN if (str) can connect to the area goal[] (which may or may
* not contain stones), if he gets the first move.
break_in(int str
, const signed char goal
[BOARDMAX
], int *move
)
int reading_nodes_when_called
= get_reading_node_counter();
Hash_data goal_hash
= goal_to_hashvalue(goal
);
if (search_persistent_breakin_cache(BREAK_IN
, str
, &goal_hash
,
breakin_node_limit
, &result
, move
)) {
if (debug
& DEBUG_BREAKIN
) {
gprintf("Break-in from %1m to:\n", str
);
gprintf("Result cached: %s %1m\n", result_to_string(result
), *move
);
memcpy(breakin_shadow
, goal
, sizeof(breakin_shadow
));
result
= recursive_break(str
, goal
, move
, 0, &goal_hash
);
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
if (debug
& DEBUG_BREAKIN
) {
gprintf("%obreak_in %1M, result %s %1M (%d, %d nodes, %f seconds)\n",
str
, result_to_string(result
), *move
,
nodes_connect
, tactical_nodes
, gg_cputime() - start
);
gprintf("%obreak_in %1m %d %1m ", str
, result
, *move
);
store_persistent_breakin_cache(BREAK_IN
, str
, &goal_hash
, result
, *move
,
tactical_nodes
, breakin_node_limit
,
/* Externably callable frontend to recursive_block_off.
* Returns WIN if (str) cannot connect to the area goal[] (which may or may
* not contain stones), if the other color moves first.
block_off(int str
, const signed char goal
[BOARDMAX
], int *move
)
int reading_nodes_when_called
= get_reading_node_counter();
Hash_data goal_hash
= goal_to_hashvalue(goal
);
if (search_persistent_breakin_cache(BLOCK_OFF
, str
, &goal_hash
,
breakin_node_limit
, &result
, move
)) {
if (debug
& DEBUG_BREAKIN
) {
gprintf("Blocking off %1m from:\n", str
);
gprintf("Result cached: %s %1m\n", result_to_string(result
), *move
);
memcpy(breakin_shadow
, goal
, sizeof(breakin_shadow
));
result
= recursive_block(str
, goal
, move
, 0, &goal_hash
);
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
if (debug
& DEBUG_BREAKIN
) {
gprintf("%oblock_off %1m, result %s %1m (%d, %d nodes, %f seconds)\n",
str
, result_to_string(result
), *move
,
nodes_connect
, tactical_nodes
, gg_cputime() - start
);
gprintf("%oblock_off %1m %d %1m ", str
, result
, *move
);
store_persistent_breakin_cache(BLOCK_OFF
, str
, &goal_hash
, result
, *move
,
tactical_nodes
, breakin_node_limit
,
/* Store a possibly expensive decision for later evaluation. The
* data getting stored should be self-explanatory.
* The job of the helper function is to
* - decide whether the spreading step will be allowed (typically
* - add the relevant positions to the connection queue in case the test
* Elements in the heap are kept sorted according to smallest distance.
push_connection_heap_entry(struct connection_data
*conn
, int distance
,
int coming_from
, int target
,
connection_helper_fn_ptr helper
)
struct heap_entry
*new_entry
= &conn
->heap_data
[conn
->heap_data_size
];
gg_assert(conn
->heap_data_size
< 4 * BOARDMAX
);
gg_assert(conn
->heap_size
< BOARDMAX
);
/* Create new heap entry. */
new_entry
->distance
= distance
;
new_entry
->coming_from
= coming_from
;
new_entry
->target
= target
;
new_entry
->helper
= helper
;
/* And insert it into the heap. */
for (k
= conn
->heap_size
++; k
> 0; k
= parent
) {
if (conn
->heap
[parent
]->distance
<= distance
)
conn
->heap
[k
] = conn
->heap
[parent
];
conn
->heap
[k
] = new_entry
;
/* Delete the first entry from the heap. */
pop_connection_heap_entry(struct connection_data
*conn
)
for (k
= 0; 2 * k
+ 1 < conn
->heap_size
; k
= child
) {
if (conn
->heap
[child
]->distance
> conn
->heap
[child
+ 1]->distance
)
if (conn
->heap
[child
]->distance
>= conn
->heap
[conn
->heap_size
]->distance
)
conn
->heap
[k
] = conn
->heap
[child
];
conn
->heap
[k
] = conn
->heap
[conn
->heap_size
];
#define ENQUEUE(conn, from, pos, dist, delta, v1, v2) \
if (dist < conn->distances[pos]) { \
if (conn->distances[pos] == HUGE_CONNECTION_DISTANCE) \
conn->queue[conn->queue_end++] = pos; \
conn->distances[pos] = dist; \
conn->deltas[pos] = delta; \
conn->coming_from[pos] = from; \
conn->vulnerable1[pos] = v1; \
conn->vulnerable2[pos] = v2; \
#define ENQUEUE_STONE(conn, from, pos, dist, delta, v1, v2) \
int origin = find_origin(pos); \
if (dist < conn->distances[origin]) { \
if (conn->distances[origin] == HUGE_CONNECTION_DISTANCE) \
conn->queue[conn->queue_end++] = origin; \
conn->distances[origin] = dist; \
conn->deltas[origin] = delta; \
conn->coming_from[origin] = from; \
conn->vulnerable1[origin] = v1; \
conn->vulnerable2[origin] = v2; \
if (origin == conn->target && dist < conn->cutoff_distance) \
conn->cutoff_distance = dist - FP(0.0001); \
case_6_7_helper(struct connection_data
*conn
, int color
)
struct heap_entry
*data
= conn
->heap
[0];
int pos
= data
->coming_from
;
int other
= OTHER_COLOR(color
);
if (ladder_capturable(apos
, other
))
ENQUEUE(conn
, pos
, apos
, data
->distance
, FP(0.6), apos
, NO_MOVE
);
= FP(0.85) + FP(0.05) * gg_min(approxlib(apos
, other
, 5, NULL
), 5);
ENQUEUE(conn
, pos
, apos
, data
->distance
+ this_delta
- FP(0.6), this_delta
,
case_9_10_helper(struct connection_data
*conn
, int color
)
struct heap_entry
*data
= conn
->heap
[0];
int pos
= data
->coming_from
;
if (no_escape_from_ladder(apos
))
ENQUEUE_STONE(conn
, pos
, apos
, data
->distance
, FP(0.3), NO_MOVE
, NO_MOVE
);
ENQUEUE_STONE(conn
, pos
, apos
, data
->distance
+ FP(0.7), FP(1.0),
ENQUEUE_STONE(conn
, pos
, apos
, data
->distance
+ FP(0.8), FP(1.1),
case_16_17_18_helper(struct connection_data
*conn
, int color
)
struct heap_entry
*data
= conn
->heap
[0];
int pos
= data
->coming_from
;
int apos
= SOUTH(gg_min(pos
, bpos
));
int gpos
= NORTH(gg_max(pos
, bpos
));
int other
= OTHER_COLOR(color
);
&& does_secure_through_ladder(color
, bpos
, apos
))
ENQUEUE(conn
, pos
, bpos
, data
->distance
, FP(1.0), apos
, NO_MOVE
);
else if (board
[gpos
] == EMPTY
&& does_secure_through_ladder(color
, bpos
, gpos
))
ENQUEUE(conn
, pos
, bpos
, data
->distance
, FP(1.0), gpos
, NO_MOVE
);
else if (conn
->distances
[bpos
] > data
->distance
+ FP(0.3)) {
ENQUEUE(conn
, pos
, bpos
, data
->distance
+ FP(0.3), FP(1.0),
else if (board
[gpos
] == EMPTY
ENQUEUE(conn
, pos
, bpos
, data
->distance
+ FP(0.3), FP(1.0),
ENQUEUE(conn
, pos
, bpos
, data
->distance
+ FP(0.6), FP(0.9),
/* Do the real work of computing connection distances.
* This is a rough approximation of the number of moves required to secure
* a connection. We also compute delta values which are intended to tell how
* big difference a particular move locally has on the connection
* distance. However, remember that this is only a heuristic with the
* sole purpose of helping to find relevant moves for connection
* The algorithm is to propagate connection values outwards using a
* breadth-first searching strategy, implemented through an implicitly
* sorted queue. The propagation to new vertices depends on
* geometrical features with significance for connections. E.g. a
* bamboo joint is recognized and the distance added when passing
* through it is small. New points are added to the queue through the
* ENQUEUE macro above. This checks whether the point has already been
* entered on the queue and updates the distance and delta values if
* the previous ones were worse. When a stone is entered, all stones
* of the string are added to the queue simultaneously.
* (target) is the other string when called from find_connection_moves().
* (It can be set to NO_MOVE otherwise.)
* The propagation is inhibited when the distance becomes too large,
* or larger than the shortest path found to the target so far.
* The purpose of the fields called vulnerable is to keep track of
* points where the attacker can threaten an individual
* connection. For example the diagonal formation
* is considered a small distance link but both the empty vertices are
* marked as vulnerable. Thus if we are computing connection distance
* from the lower left O in this diagram,
* the distance to the middle O is small but the second diagonal link
* to the lower right O stone is not given a small distance since a
* had already been marked as vulnerable.
* It should also be pointed out that this reasoning is not relevant
* in this position where X has no cutting potential,
* That is because there is a pattern directly recognizing the safe
* link between the two lower stones, without taking the longer road
* over the two diagonal links.
* (color) is the color for which we are computing connection distances,
* (target) the position we want to reach (can be set to NO_MOVE),
* (*conn) has to have the queue initialized with the positions
* from which we want to know the distances,
* (cutoff_distance) is the highest distance before we give up,
* (speculative) controls some special cases in the propagation rules
* As an optimization, new points are either added directly via the ENQUEUE
* macro if the necessary test is an immediate (usually purely geometric)
* check, or if the decision is more expensive (usually depending on a
* ladder), it gets postponed and stored via push_connection_heap_entry()
spread_connection_distances(int color
, struct connection_data
*conn
)
int other
= OTHER_COLOR(color
);
int stones
[MAX_BOARD
* MAX_BOARD
];
/* Loop until we reach the end of the queue. */
while (conn
->queue_start
< conn
->queue_end
|| conn
->heap_size
> 0) {
/* Delete heap entries for positions that have already been reached
while (conn
->heap_size
> 0
&& conn
->heap
[0]->distance
>= conn
->distances
[conn
->heap
[0]->target
])
pop_connection_heap_entry(conn
);
if (stone
== num_stones
) {
int smallest_dist
= HUGE_CONNECTION_DISTANCE
;
if (conn
->queue_start
== conn
->queue_end
) {
if (conn
->heap_size
> 0) {
conn
->heap
[0]->helper(conn
, color
);
pop_connection_heap_entry(conn
);
gg_assert(conn
->queue_end
<= MAX_BOARD
* MAX_BOARD
);
/* Find the smallest distance among the queued points. */
for (k
= conn
->queue_start
; k
< conn
->queue_end
; k
++) {
if (conn
->distances
[conn
->queue
[k
]] < smallest_dist
) {
smallest_dist
= conn
->distances
[conn
->queue
[k
]];
/* Exchange the best point with the first element in the queue. */
if (best_index
!= conn
->queue_start
) {
int temp
= conn
->queue
[conn
->queue_start
];
conn
->queue
[conn
->queue_start
] = conn
->queue
[best_index
];
conn
->queue
[best_index
] = temp
;
/* If the first element in heap has smaller distance than the
* smallest we have found so far, call the relevant helper function
* now, and delete the heap entry.
if (conn
->heap_size
> 0 && conn
->heap
[0]->distance
< smallest_dist
) {
conn
->heap
[0]->helper(conn
, color
);
pop_connection_heap_entry(conn
);
/* Now we are ready to pick the first element in the queue and
pos
= conn
->queue
[conn
->queue_start
++];
if (board
[pos
] != EMPTY
) {
num_stones
= findstones(pos
, MAX_BOARD
* MAX_BOARD
, stones
);
conn
->distances
[pos
] = conn
->distances
[stones
[0]];
conn
->deltas
[pos
] = conn
->deltas
[stones
[0]];
conn
->coming_from
[pos
] = conn
->coming_from
[stones
[0]];
conn
->vulnerable1
[pos
] = conn
->vulnerable1
[stones
[0]];
conn
->vulnerable2
[pos
] = conn
->vulnerable2
[stones
[0]];
/* No further propagation if the distance is too large. */
distance
= conn
->distances
[pos
];
if (distance
> conn
->cutoff_distance
)
/* Search for new vertices to propagate to. */
if (board
[pos
] == color
) {
for (k
= 0; k
< 4; k
++) {
/* List of relative coordinates. (pos) is marked by *.
/* FIXME: Compactify this list. */
int bpos
= pos
+ right
+ up
;
int cpos
= pos
+ 2 * right
;
int fpos
= pos
+ right
+ 2*up
;
int ipos
= pos
- right
+ up
;
int jpos
= pos
- right
+ 2 * up
;
int kpos
= pos
- 2 * right
;
/* Case 1. "a" is empty and would be suicide for the opponent. */
if (board
[apos
] == EMPTY
&& is_suicide(apos
, other
))
ENQUEUE(conn
, pos
, apos
, distance
, FP(0.0), apos
, NO_MOVE
);
/* Case 2. "a" is empty and would be self atari for the opponent. */
&& conn
->distances
[apos
] > distance
+ FP(0.1)
&& is_self_atari(apos
, other
)) {
int vulnerable1
= NO_MOVE
;
int vulnerable2
= NO_MOVE
;
if (approxlib(apos
, other
, 1, &lib
) >= 1) {
if (approxlib(lib
, other
, 2, NULL
) > 2)
if (countlib(pos
) == 2) {
for (i
= 0; i
< 4; i
++) {
if (board
[lib
+ delta
[i
]] == EMPTY
&& lib
+ delta
[i
] != apos
&& trymove(lib
+ delta
[i
], other
,
"compute_connection_distances", pos
)) {
if (ladder_capture(pos
, NULL
)) {
vulnerable2
= lib
+ delta
[i
];
if (!common_vulnerabilities(conn
->vulnerable1
[pos
],
vulnerable1
, vulnerable2
, color
)) {
ENQUEUE(conn
, pos
, apos
, distance
+ FP(0.1), FP(0.1),
vulnerable1
, vulnerable2
);
/* Case 3. Bamboo joint of "*" + "a" to "e" + "f" through "b" and "g".
* 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
&& board
[gpos
] == EMPTY
) {
ENQUEUE(conn
, pos
, bpos
, distance
+ FP(0.1), FP(0.1),
ENQUEUE(conn
, pos
, gpos
, distance
+ FP(0.1), FP(0.1),
/* Case 4. Diagonal connection to another stone "b" through
* empty vertices "a" and "g".
&& !common_vulnerabilities(conn
->vulnerable1
[pos
],
&& conn
->distances
[bpos
] > distance
+ FP(0.1)) {
ENQUEUE(conn
, pos
, apos
, distance
+ FP(0.2), FP(0.2),
ENQUEUE(conn
, pos
, gpos
, distance
+ FP(0.2), FP(0.2),
ENQUEUE_STONE(conn
, pos
, bpos
, distance
+ FP(0.1), FP(0.1),
/* Case 5. Almost bamboo joint.
&& conn
->distances
[epos
] > distance
+ FP(0.2)
&& approxlib(gpos
, other
, 3, NULL
) <= 2) {
&& approxlib(bpos
, color
, 3, NULL
) >= 3
&& !common_vulnerabilities(conn
->vulnerable1
[pos
],
&& approxlib(apos
, other
, 3, NULL
) <= 2))
&& !common_vulnerabilities(conn
->vulnerable1
[pos
],
&& approxlib(fpos
, other
, 3, NULL
) <= 2))) {
if (board
[apos
] == EMPTY
&& board
[fpos
] == EMPTY
) {
ENQUEUE_STONE(conn
, pos
, epos
, distance
+ FP(0.2), FP(0.2),
else if (board
[apos
] == EMPTY
&& board
[fpos
] != EMPTY
) {
ENQUEUE_STONE(conn
, pos
, epos
, distance
+ FP(0.2), FP(0.2),
else if (board
[apos
] != EMPTY
&& board
[fpos
] == EMPTY
) {
ENQUEUE_STONE(conn
, pos
, epos
, distance
+ FP(0.2), FP(0.2),
else if (board
[apos
] != EMPTY
&& board
[fpos
] != EMPTY
) {
ENQUEUE_STONE(conn
, pos
, epos
, distance
+ FP(0.2), FP(0.2),
&& approxlib(ipos
, color
, 3, NULL
) >= 3
&& !common_vulnerabilities(conn
->vulnerable1
[pos
],
&& approxlib(hpos
, other
, 3, NULL
) <= 2))
&& !common_vulnerabilities(conn
->vulnerable1
[pos
],
&& approxlib(jpos
, other
, 3, NULL
) <= 2))) {
if (board
[hpos
] == EMPTY
&& board
[jpos
] == EMPTY
) {
ENQUEUE_STONE(conn
, pos
, epos
, distance
+ FP(0.2), FP(0.2),
else if (board
[hpos
] == EMPTY
&& board
[jpos
] != EMPTY
) {
ENQUEUE_STONE(conn
, pos
, epos
, distance
+ FP(0.2), FP(0.2),
else if (board
[hpos
] != EMPTY
&& board
[jpos
] == EMPTY
) {
ENQUEUE_STONE(conn
, pos
, epos
, distance
+ FP(0.2), FP(0.2),
else if (board
[hpos
] != EMPTY
&& board
[jpos
] != EMPTY
) {
ENQUEUE_STONE(conn
, pos
, epos
, distance
+ FP(0.2), FP(0.2),
/* Case 6. "a" is empty and an opponent move can be captured
if (board
[apos
] == EMPTY
&& conn
->distances
[apos
] > distance
+ FP(0.6)) {
push_connection_heap_entry(conn
, distance
+ FP(0.6), pos
, apos
,
/* Case 8. Adjacent opponent stone at "a" which can't avoid atari.
&& conn
->distances
[apos
] > distance
+ FP(0.1)
&& no_escape_from_atari(apos
)) {
ENQUEUE_STONE(conn
, pos
, apos
, distance
+ FP(0.1), FP(0.1),
/* Case 9. Adjacent opponent stone at "a" which can't avoid
* Case 10. "a" is occupied by opponent.
if (board
[apos
] == other
&& conn
->distances
[apos
] > distance
+ FP(0.3)) {
push_connection_heap_entry(conn
, distance
+ FP(0.3), pos
, apos
,
/* Case 11. Diagonal connection to empty vertex "b" through
* empty vertex "a" or "g", which makes "a" or "g" self-atari
&& conn
->distances
[bpos
] > distance
+ FP(1.1)
&& does_secure(color
, bpos
, apos
)) {
ENQUEUE(conn
, pos
, bpos
, distance
+ FP(1.1), FP(1.0), apos
, NO_MOVE
);
&& conn
->distances
[bpos
] > distance
+ FP(1.1)
&& does_secure(color
, bpos
, gpos
)) {
ENQUEUE(conn
, pos
, bpos
, distance
+ FP(1.1), FP(1.0), gpos
, NO_MOVE
);
/* Case 12. One-space jump to empty vertex "e" through empty
* vertex "g", which makes "g" self-atari for opponent.
&& conn
->distances
[epos
] > distance
+ FP(1.1)
&& does_secure(color
, epos
, gpos
)) {
ENQUEUE(conn
, pos
, epos
, distance
+ FP(1.1), FP(1.0), gpos
, NO_MOVE
);
/* Case 13. One-space jump to empty vertex "e" through empty
* vertex "g", making a bamboo joint.
&& conn
->distances
[epos
] > distance
+ FP(1.1)
&& ((board
[apos
] == color
&& board
[fpos
] == color
|| (board
[hpos
] == color
&& board
[jpos
] == color
&& board
[ipos
] == EMPTY
))) {
ENQUEUE(conn
, pos
, epos
, distance
+ FP(1.1), FP(1.0), gpos
, NO_MOVE
);
/* Case 14. Diagonal connection to empty vertex "b" through
* empty vertices "a" and "g".
&& board
[apos
] == EMPTY
&& board
[gpos
] == EMPTY
&& conn
->distances
[bpos
] > distance
+ FP(1.3)) {
ENQUEUE(conn
, pos
, bpos
, distance
+ FP(1.3), FP(1.0), apos
, gpos
);
/* Case 15. Keima to "f" or "j" on edge. and one space jump on
&& (conn
->distances
[fpos
] > distance
+ FP(1.3)
|| conn
->distances
[epos
] > distance
+ FP(1.3))
&& (!ON_BOARD(cpos
) || !ON_BOARD(hpos
))) {
ENQUEUE(conn
, pos
, fpos
, distance
+ FP(1.3), FP(1.0),
ENQUEUE(conn
, pos
, epos
, distance
+ FP(1.3), FP(1.0),
&& (conn
->distances
[jpos
] > distance
+ FP(1.3)
|| conn
->distances
[epos
] > distance
+ FP(1.3))
&& (!ON_BOARD(apos
) || !ON_BOARD(kpos
))) {
ENQUEUE(conn
, pos
, jpos
, distance
+ FP(1.3), FP(1.0),
ENQUEUE(conn
, pos
, epos
, distance
+ FP(1.3), FP(1.0),
/* Case 16. Diagonal connection to empty vertex "b" through
* empty vertex "a" or "g", which allows opponent move at "a"
* or "g" to be captured in a ladder.
* Case 17. Diagonal connection to empty vertex "b" through
* one empty and one opponent vertex "a" and "g", where
* the opponent stone is short of liberties.
* Case 18. Diagonal connection to empty vertex "b" through
* empty vertex "a" or "g", with no particular properties.
&& (board
[apos
] == EMPTY
|| board
[gpos
] == EMPTY
)
&& conn
->distances
[bpos
] > distance
+ FP(1.2)) {
push_connection_heap_entry(conn
, distance
+ FP(1.2), pos
, bpos
,
/* Case 19. Clamp at "e" of single stone at "g". */
&& conn
->distances
[epos
] > distance
+ FP(2.0)
&& countstones(gpos
) == 1) {
ENQUEUE(conn
, pos
, epos
, distance
+ FP(2.0), FP(1.0),
/* Case 20. Diagonal connection to empty vertex "b" through
* opponent stones "a" or "g" with few liberties.
&& conn
->distances
[bpos
] > distance
+ FP(2.0)
&& (countlib(apos
) + countlib(gpos
) <= 6)) {
ENQUEUE(conn
, pos
, bpos
, distance
+ FP(2.0), FP(1.0),
/* Case 21. Diagonal connection to own stone "b" through
* opponent stones "a" or "g" with few liberties.
&& conn
->distances
[bpos
] > distance
+ FP(2.0)
&& (countlib(apos
) + countlib(gpos
) <= 5)) {
ENQUEUE_STONE(conn
, pos
, bpos
, distance
+ FP(2.0), FP(1.0),
else if (board
[pos
] == EMPTY
&& no_escape_from_ladder(pos
))) {
for (k
= 0; k
< 4; k
++) {
/* List of relative coordinates. (pos) is marked by *.
/* FIXME: Compactify this list. */
int bpos
= pos
+ right
+ up
;
int cpos
= pos
+ 2 * right
;
int fpos
= pos
+ right
+ 2*up
;
int ipos
= pos
- right
+ up
;
int jpos
= pos
- right
+ 2 * up
;
int kpos
= pos
- 2 * right
;
if (board
[apos
] == color
) {
ENQUEUE_STONE(conn
, pos
, apos
, distance
, FP(0.0),
conn
->vulnerable1
[pos
], conn
->vulnerable2
[pos
]);
else if (board
[apos
] == EMPTY
) {
= FP(0.8) + FP(0.05) * gg_min(approxlib(apos
, other
, 6, NULL
), 6);
ENQUEUE(conn
, pos
, apos
, distance
+ this_delta
, this_delta
,
else if (board
[apos
] == other
) {
ENQUEUE_STONE(conn
, pos
, apos
, distance
+ FP(1.0), FP(1.0),
/* Case 1. Diagonal connection to empty vertex "b" through
* empty vertices "a" and "g".
&& conn
->distances
[bpos
] > distance
+ FP(1.5)) {
ENQUEUE(conn
, pos
, bpos
, distance
+ FP(1.5), FP(1.0),
/* Case 2. Diagonal connection to friendly stone at "b" through
* empty vertices "a" and "g".
&& conn
->distances
[bpos
] > distance
+ FP(1.3)) {
ENQUEUE_STONE(conn
, pos
, bpos
, distance
+ FP(1.3), FP(1.0),
sort_connection_queue_tail(struct connection_data
*conn
)
for (k
= conn
->queue_start
; k
< conn
->queue_end
- 1; k
++) {
int smallest_dist
= conn
->distances
[conn
->queue
[k
]];
for (i
= k
+ 1; i
< conn
->queue_end
; i
++) {
if (conn
->distances
[conn
->queue
[i
]] < smallest_dist
) {
smallest_dist
= conn
->distances
[conn
->queue
[i
]];
int temp
= conn
->queue
[k
];
conn
->queue
[k
] = conn
->queue
[best_index
];
conn
->queue
[best_index
] = temp
;
/* Replace string origins in a connection queue with complete sets of
* corresponding string stones.
expand_connection_queue(struct connection_data
*conn
)
int full_queue
[BOARDMAX
];
int full_queue_position
= 0;
int full_queue_start
= 0;
for (k
= 0; k
< conn
->queue_end
; k
++) {
if (k
== conn
->queue_start
)
full_queue_start
= full_queue_position
;
if (board
[conn
->queue
[k
]] == EMPTY
)
full_queue
[full_queue_position
++] = conn
->queue
[k
];
full_queue_position
+= findstones(conn
->queue
[k
],
full_queue
+ full_queue_position
);
conn
->queue_start
= full_queue_start
;
conn
->queue_end
= full_queue_position
;
memcpy(conn
->queue
, full_queue
, conn
->queue_end
* sizeof(int));
/* Initialize distance and delta values so that the former are
* everywhere huge and the latter everywhere zero.
clear_connection_data(struct connection_data
*conn
)
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
conn
->distances
[pos
] = HUGE_CONNECTION_DISTANCE
;
conn
->deltas
[pos
] = FP(0.0);
conn
->coming_from
[pos
] = NO_MOVE
;
conn
->vulnerable1
[pos
] = NO_MOVE
;
conn
->vulnerable2
[pos
] = NO_MOVE
;
conn
->heap_data_size
= 0;
/* Compute the connection distances from string (str) to nearby
* vertices, until we reach target or the distance gets too high.
compute_connection_distances(int str
, int target
, int cutoff
,
struct connection_data
*conn
,
clear_connection_data(conn
);
/* Add the origin of the initial string to the queue. */
add_to_start_queue(find_origin(str
), FP(0.0), conn
);
conn
->cutoff_distance
= cutoff
;
conn
->speculative
= speculative
;
spread_connection_distances(color
, conn
);
/* Print the connection distances in a struct connection_data. */
print_connection_distances(struct connection_data
*conn
)
for (j
= 0, ch
= 'A'; j
< board_size
; j
++, ch
++) {
fprintf(stderr
, " %c ", ch
);
for (i
= 0; i
< board_size
; i
++) {
fprintf(stderr
, "%2d ", board_size
- i
);
for (j
= 0; j
< board_size
; j
++) {
if (conn
->distances
[pos
] == HUGE_CONNECTION_DISTANCE
) {
fprintf(stderr
, "%3.1f ", FIXED_TO_FLOAT(conn
->distances
[pos
]));
fprintf(stderr
, "Vulnerable:\n");
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (conn
->distances
[pos
] < HUGE_CONNECTION_DISTANCE
&& (conn
->vulnerable1
[pos
] != NO_MOVE
|| conn
->vulnerable2
[pos
] != NO_MOVE
)) {
if (conn
->vulnerable1
[pos
] != NO_MOVE
)
gprintf(" %1m", conn
->vulnerable1
[pos
]);
if (conn
->vulnerable2
[pos
] != NO_MOVE
)
gprintf(" %1m", conn
->vulnerable2
[pos
]);
/* Test whether there is a trivial connection between str1 and str2
* and if so return the connecting move in *move. By trivial
* connection we mean that they either have a common liberty or a
* common neighbor which can be tactically attacked.
trivial_connection(int str1
, int str2
, int *move
)
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
if (have_common_lib(str1
, str2
, move
))
adj
= chainlinks(str1
, adjs
);
/* We turn off the sgf traces here to avoid cluttering them up with
* tactical reading moves.
for (r
= 0; r
< adj
; r
++)
if (adjacent_strings(adjs
[r
], str2
) && attack(adjs
[r
], move
) == WIN
) {
/* Turn the sgf traces back on. */
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* True if a move by color makes an opponent move at pos a self atari
* or possible to capture in a ladder.
does_secure_through_ladder(int color
, int move
, int pos
)
if (trymove(move
, color
, NULL
, NO_MOVE
)) {
if (ladder_capturable(pos
, OTHER_COLOR(color
)))
/* Test whether the string str can be immediately taken off the board
* or captured in a ladder. If so the capturing move is returned in
ladder_capture(int str
, int *move
)
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
int liberties
= countlib(str
);
/* We turn off the sgf traces here to avoid cluttering them up with
* tactical reading moves.
result
= attack(str
, move
);
result
= simple_ladder(str
, move
);
/* Turn the sgf traces back on. */
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* Test whether a move at pos by color can be captured in a ladder. */
ladder_capturable(int pos
, int color
)
if (trymove(pos
, color
, NULL
, NO_MOVE
)) {
int liberties
= countlib(pos
);
if (liberties
== 1 && attack(pos
, NULL
) == WIN
)
else if (liberties
== 2 && simple_ladder(pos
, NULL
) == WIN
)
/* Test whether the string str with one liberty is stuck with at most
* one liberty. This function trivially returns false if the string
* has more than one liberty to start with.
no_escape_from_atari(int str
)
if (findlib(str
, 1, &lib
) > 1)
if (accuratelib(lib
, board
[str
], 2, NULL
) > 1)
/* FIXME: Should exclude snapback. */
if (chainlinks2(str
, adj
, 1) > 0)
/* Test whether the string str with one liberty is captured in a
* ladder. This function trivially returns false if the string has
* more than one liberty to start with, except for one special case.
* FIXME: Needs a simple_ladder_defense().
no_escape_from_ladder(int str
)
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
/* We turn off the sgf traces here to avoid cluttering them up with
* tactical reading moves.
if (countlib(str
) == 1 && find_defense(str
, NULL
) == 0)
&& chainlinks2(str
, adj
, 1) == 0
&& findlib(str
, 2, libs
) == 2
&& approxlib(libs
[0], board
[str
], 2, NULL
) == 1
&& approxlib(libs
[1], board
[str
], 2, NULL
) == 1
&& ladder_capture(str
, NULL
)
&& !find_defense(str
, NULL
))
/* Turn the sgf traces back on. */
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* We usually don't want to spend time with moves which are
* self-atari, unless the stone is involved in a ko.
check_self_atari(int pos
, int color_to_move
)
if (!is_self_atari(pos
, color_to_move
))
if (is_ko(pos
, color_to_move
, NULL
))
/* FIXME: At some time I added this exceptional case but I can no
* longer see how it would be useful. It might still be, however, so
* I leave the code in for a while. /gf
* Code reactivated, see nando:31. /nn
* Added requirement that no additional stones are sacrificed in the
* FIXME: Add a function in board.c to check how big the string
* becomes when playing a move and use for the isolated stone
if (approxlib(pos
, color_to_move
, 1, &lib
) >= 1
&& approxlib(lib
, OTHER_COLOR(color_to_move
), 3, NULL
) <= 2
&& ladder_capturable(lib
, OTHER_COLOR(color_to_move
))) {
for (k
= 0; k
< 4; k
++) {
if (board
[pos
+ delta
[k
]] == color_to_move
)
/* Check for overlap between (a1, a2) and (b1, b2). */
common_vulnerabilities(int a1
, int a2
, int b1
, int b2
, int color
)
return (common_vulnerability(a1
, b1
, color
)
|| common_vulnerability(a1
, b2
, color
)
|| common_vulnerability(a2
, b1
, color
)
|| common_vulnerability(a2
, b2
, color
));
/* Check if apos and bpos are the same or if they are both liberties
* of a string of the given color with at most three liberties.
common_vulnerability(int apos
, int bpos
, int color
)
if (apos
== NO_MOVE
|| bpos
== NO_MOVE
)
if (board
[apos
+ delta
[k
]] == color
&& countlib(apos
+ delta
[k
]) <= 3
&& liberty_of_string(bpos
, apos
+ delta
[k
]))