Index: engine/cache.h =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/cache.h,v retrieving revision 1.8 diff -u -r1.8 cache.h --- engine/cache.h 29 Jan 2002 18:20:00 -0000 1.8 +++ engine/cache.h 31 Jan 2002 21:39:42 -0000 @@ -245,10 +245,8 @@ int get_read_result(int routine, int komaster, int kom_pos, int *str, Read_result **read_result); -int -get_read_result2(int routine, int komaster, int kom_pos, int *str1, int *str2, - Read_result **read_result); - +int get_read_result2(int routine, int komaster, int kom_pos, + int *str1, int *str2, Read_result **read_result); /* ================================================================ */ @@ -340,8 +338,11 @@ #define OWL_DEFEND 9 #define SEMEAI 10 -#define MAX_ROUTINE SEMEAI -#define NUM_ROUTINES (MAX_ROUTINE+1) +#define CONNECT 11 +#define DISCONNECT 12 + +#define MAX_ROUTINE DISCONNECT +#define NUM_ROUTINES (MAX_ROUTINE + 1) #endif Index: engine/globals.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/globals.c,v retrieving revision 1.16 diff -u -r1.16 globals.c --- engine/globals.c 19 Jan 2002 16:11:16 -0000 1.16 +++ engine/globals.c 31 Jan 2002 21:39:42 -0000 @@ -119,6 +119,8 @@ int semeai_variations = DEFAULT_SEMEAI_VARIATIONS; /* use experimental connection module */ int experimental_connections = EXPERIMENTAL_CONNECTIONS; +/* use alternate connection reading algorithm */ +int alternate_connections = ALTERNATE_CONNECTIONS; int owl_threats = OWL_THREATS; /* compute owl threats */ /* use experimental influence module */ Index: engine/gnugo.h =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/gnugo.h,v retrieving revision 1.36 diff -u -r1.36 gnugo.h --- engine/gnugo.h 31 Jan 2002 16:19:36 -0000 1.36 +++ engine/gnugo.h 31 Jan 2002 21:39:43 -0000 @@ -251,10 +251,13 @@ #define HASH_OWL_ATTACK 0x0100 #define HASH_OWL_DEFEND 0x0200 #define HASH_SEMEAI 0x0400 +#define HASH_CONNECT 0x0800 +#define HASH_DISCONNECT 0x1000 #define HASH_NOTHING 0 #define HASH_ALL 0xffff #define HASH_DEFAULT (HASH_ATTACK | HASH_FIND_DEFENSE\ - | HASH_OWL_ATTACK | HASH_OWL_DEFEND | HASH_SEMEAI) + | HASH_OWL_ATTACK | HASH_OWL_DEFEND | HASH_SEMEAI\ + | HASH_CONNECT | HASH_DISCONNECT) extern int debug; /* debug flags */ extern int hashflags; /* hash flags */ Index: engine/readconnect.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/readconnect.c,v retrieving revision 1.20 diff -u -r1.20 readconnect.c --- engine/readconnect.c 24 Jan 2002 22:32:54 -0000 1.20 +++ engine/readconnect.c 31 Jan 2002 21:39:44 -0000 @@ -40,6 +40,11 @@ int i; } zone; +static int recursive_connect2(int str1, int str2, int *move, + int komaster, int kom_pos, int has_passed); +static int recursive_disconnect2(int str1, int str2, int *move, + int komaster, int kom_pos, int has_passed); + static int add_array(int *array, int elt); static int element_array (int *array,int elt); static void intersection_array(int *array1, int *array2); @@ -76,6 +81,7 @@ int nodes_connect = 0; int max_nodes_connect = 2000; int max_connect_depth = 64; +int max_connect_depth2 = 20; /* Used by the alternate algorithm. */ /* Statistics. */ static int global_connection_node_counter = 0; @@ -88,13 +94,13 @@ /* send back 1 if the intersection is in the zone */ -/* +#if 0 static int elt_zone (zone *zn, int elt) { if ((zn->bits[elt >> 5] >> (elt & 31)) & 1) return 1; return 0; } -*/ +#endif /* Adds an intersection to a zone */ @@ -110,30 +116,30 @@ /* start to loop over a zone */ -/* +#if 0 static int start_zone (zone *zn) { if (zn->array[0] < 1) return -1; zn->i = 1; return zn->array[1]; } -*/ +#endif /* continue to loop over a zone */ -/* +#if 0 static int next_zone (zone *zn) { zn->i++; if (zn->i > zn->array[0]) return -1; return zn->array[zn->i]; } -*/ +#endif /* only keep the elements of zn1 which are also in zn2 */ -/* +#if 0 static void intersection_zone(zone *zn1, zone *zn2) { int r, s; @@ -146,7 +152,7 @@ zn1->i--; } } -*/ +#endif /* 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]. @@ -997,8 +1003,17 @@ int string_connect(int str1, int str2, int *move) { + int dummy_move; + + if (move == NULL) + move = &dummy_move; + nodes_connect = 0; *move = PASS_MOVE; + + if (alternate_connections) + return recursive_connect2(str1, str2, move, EMPTY, NO_MOVE, 0); + return recursive_connect(str1, str2, move); } @@ -1095,10 +1110,20 @@ /* Externally callable frontend to recursive_disconnect(). */ int disconnect(int str1, int str2, int *move) { - int i, res = WIN, Moves[MAX_MOVES]; + int i; + int res = WIN; + int Moves[MAX_MOVES]; + int dummy_move; + + if (move == NULL) + move = &dummy_move; nodes_connect = 0; *move = PASS_MOVE; + + if (alternate_connections) + return recursive_disconnect2(str1, str2, move, EMPTY, NO_MOVE, 0); + Moves[0]=0; moves_to_prevent_connection_in_three_moves (Moves, str1, str2); if (Moves[0] > 0) @@ -1587,6 +1612,1255 @@ { 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)\ + do {\ + int l;\ + for (l = 0; l < num_moves; l++)\ + if (moves[l] == (move)) {\ + if (distances[l] > distance)\ + distances[l] = distance;\ + break;\ + }\ + if ((l == num_moves) && (num_moves < MAX_MOVES)) {\ + moves[num_moves] = move;\ + distances[num_moves] = distance;\ + (num_moves)++;\ + }\ + } while (0) + + +struct connection_data { + float distances[BOARDMAX]; + float deltas[BOARDMAX]; + int queue[BOARDMAX]; + int queue_start; + int queue_end; +}; + +#define HUGE_CONNECTION_DISTANCE 100.0 + +static int find_connection_moves(int str1, int str2, int color_to_move, + int moves[MAX_MOVES], float *total_distance); +static void compute_connection_distances(int str, + struct connection_data *conn); +static void print_connection_distances(struct connection_data *conn); +static int trivial_connection(int str1, int str2, int *move); +static int does_secure(int color, int move, int pos); +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); + + +/* Try to connect two strings. This function is called in a mutual + * recursion with recursive_disconnect2(). Return codes and the + * meaning of komaster and kom_pos is identical to the tactical + * reading functions. For the has_passed parameter, see the + * documentation of recursive_disconnect2(). + * + * The algorithm is + * 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. + */ +static int +recursive_connect2(int str1, int str2, int *move, int komaster, int kom_pos, + int has_passed) +{ + int color = board[str1]; + int moves[MAX_MOVES]; + int num_moves; + float distance = 0.0; + int k; + int xpos; + int savemove = NO_MOVE; + int savecode = 0; + int found_read_result; + Read_result *read_result = NULL; + + SETUP_TRACE_INFO2("recursive_connect2", str1, str2); + + if (move) + *move = NO_MOVE; + + nodes_connect++; + global_connection_node_counter++; + + if (board[str1] == EMPTY || board[str2] == EMPTY) { + SGFTRACE2(PASS_MOVE, 0, "one string already captured"); + return 0; + } + + if (same_string(str1, str2)) { + SGFTRACE2(PASS_MOVE, WIN, "already connected"); + return WIN; + } + + if (nodes_connect > max_nodes_connect) { + SGFTRACE2(PASS_MOVE, 0, "connection node limit reached"); + return 0; + } + + if (stackp > max_connect_depth2) { + SGFTRACE2(PASS_MOVE, 0, "connection depth limit reached"); + return 0; + } + + if (stackp <= depth + && (hashflags & HASH_CONNECT) + && !has_passed) { + found_read_result = get_read_result2(CONNECT, komaster, kom_pos, + &str1, &str2, &read_result); + if (found_read_result) { + TRACE_CACHED_RESULT(*read_result); + if (rr_get_result(*read_result) != 0) + if (move) + *move = rr_get_move(*read_result); + + SGFTRACE2(rr_get_move(*read_result), + rr_get_result(*read_result), "cached"); + return rr_get_result(*read_result); + } + } + + if (trivial_connection(str1, str2, &xpos) == WIN) { + SGFTRACE2(xpos, WIN, "trivial connection"); + READ_RETURN(read_result, move, xpos, WIN); + } + + num_moves = find_connection_moves(str1, str2, color, moves, &distance); + + for (k = 0; k < num_moves; k++) { + int new_komaster; + int new_kom_pos; + int ko_move; + + xpos = moves[k]; + + if (komaster_trymove(xpos, color, "recursive_connect2", str1, + komaster, kom_pos, &new_komaster, &new_kom_pos, + &ko_move, stackp <= ko_depth && savecode == 0)) { + if (!ko_move) { + int acode = recursive_disconnect2(str1, str2, NULL, + new_komaster, new_kom_pos, + has_passed); + popgo(); + if (acode == 0) { + SGFTRACE2(xpos, WIN, "connection effective"); + READ_RETURN(read_result, move, xpos, WIN); + } + /* if the move works with ko we save it, then look for something + * better. + */ + UPDATE_SAVED_KO_RESULT(savecode, savemove, acode, xpos); + } + else { + if (recursive_disconnect2(str1, str2, NULL, + new_komaster, new_kom_pos, + has_passed) != WIN) { + savemove = xpos; + savecode = KO_B; + } + popgo(); + } + } + } + + if (num_moves == 0 && distance < 1.0) { + SGFTRACE2(NO_MOVE, WIN, "no move, probably connected"); + READ_RETURN(read_result, move, NO_MOVE, WIN); + } + + if (savecode != 0) { + SGFTRACE2(savemove, savecode, "saved move"); + READ_RETURN(read_result, move, savemove, savecode); + } + + SGFTRACE2(0, 0, NULL); + READ_RETURN0(read_result); +} + + +/* Try to disconnect two strings. This function is called in a mutual + * recursion with recursive_connect2(). Return codes and the meaning + * of komaster and kom_pos is identical to the tactical reading + * functions. + * + * The algorithm is + * 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. + */ +static int +recursive_disconnect2(int str1, int str2, int *move, int komaster, int kom_pos, + int has_passed) +{ + int color = board[str1]; + int other = OTHER_COLOR(color); + int moves[MAX_MOVES]; + int num_moves; + float distance = 0.0; + int k; + int xpos; + int savemove = NO_MOVE; + int savecode = 0; + int found_read_result; + Read_result *read_result = NULL; + + SETUP_TRACE_INFO2("recursive_disconnect2", str1, str2); + + nodes_connect++; + global_connection_node_counter++; + + if (move) + *move = NO_MOVE; + + if (board[str1] == EMPTY || board[str2] == EMPTY) { + SGFTRACE2(PASS_MOVE, WIN, "one string already captured"); + return WIN; + } + + if (same_string(str1, str2)) { + SGFTRACE2(PASS_MOVE, 0, "already connected"); + return 0; + } + + if (nodes_connect > max_nodes_connect) { + SGFTRACE2(PASS_MOVE, WIN, "connection node limit reached"); + return WIN; + } + + if (stackp > max_connect_depth2) { + SGFTRACE2(PASS_MOVE, WIN, "connection depth limit reached"); + return WIN; + } + + if ((stackp <= depth) && (hashflags & HASH_DISCONNECT)) { + found_read_result = get_read_result2(DISCONNECT, komaster, kom_pos, + &str1, &str2, &read_result); + if (found_read_result) { + TRACE_CACHED_RESULT(*read_result); + if (rr_get_result(*read_result) != 0) + if (move) + *move = rr_get_move(*read_result); + + SGFTRACE2(rr_get_move(*read_result), + rr_get_result(*read_result), "cached"); + return rr_get_result(*read_result); + } + } + + if (ladder_capture(str1, &xpos) == WIN) { + SGFTRACE2(xpos, WIN, "first string capturable"); + READ_RETURN(read_result, move, xpos, WIN); + } + if (ladder_capture(str2, &xpos) == WIN) { + SGFTRACE2(xpos, WIN, "second string capturable"); + READ_RETURN(read_result, move, xpos, WIN); + } + + num_moves = find_connection_moves(str1, str2, other, moves, &distance); + + for (k = 0; k < num_moves; k++) { + int new_komaster; + int new_kom_pos; + int ko_move; + + xpos = moves[k]; + + if (komaster_trymove(xpos, other, "recursive_disconnect2", str1, + komaster, kom_pos, &new_komaster, &new_kom_pos, + &ko_move, stackp <= ko_depth && savecode == 0)) { + if (!ko_move) { + int dcode = recursive_connect2(str1, str2, NULL, + new_komaster, new_kom_pos, has_passed); + popgo(); + if (dcode == 0) { + SGFTRACE2(xpos, WIN, "disconnection effective"); + READ_RETURN(read_result, move, xpos, WIN); + } + /* if the move works with ko we save it, then look for something + * better. + */ + UPDATE_SAVED_KO_RESULT(savecode, savemove, dcode, xpos); + } + else { + if (recursive_connect2(str1, str2, NULL, + new_komaster, new_kom_pos, + has_passed) != WIN) { + savemove = xpos; + savecode = KO_B; + } + popgo(); + } + } + } + + if (num_moves == 0 + && distance >= 1.0 + && (has_passed + || !recursive_connect2(str1, str2, NULL, komaster, kom_pos, 1))) { + SGFTRACE2(NO_MOVE, WIN, "no move, probably disconnected"); + READ_RETURN(read_result, move, NO_MOVE, WIN); + } + + if (savecode != 0) { + SGFTRACE2(savemove, savecode, "saved move"); + READ_RETURN(read_result, move, savemove, savecode); + } + + SGFTRACE2(0, 0, NULL); + READ_RETURN0(read_result); +} + + +/* 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 + * moves. + */ +static int +find_connection_moves(int str1, int str2, int color_to_move, + int moves[MAX_MOVES], float *total_distance) +{ + int color = board[str1]; + int other = OTHER_COLOR(color); + int connect_move = (color_to_move == color); + int r; + struct connection_data conn1; + struct connection_data conn2; + float distances[MAX_MOVES]; + int num_moves = 0; + SGFTree *save_sgf_dumptree = sgf_dumptree; + int save_count_variations = count_variations; + int acode = 0; + int attack_move = NO_MOVE; + int dcode = 0; + int defense_move = NO_MOVE; + float max_dist1; + float max_dist2; + int lib; + int k; + int i, j; + + /* We turn off the sgf traces here to avoid cluttering them up with + * tactical reading moves. + */ + sgf_dumptree = NULL; + count_variations = 0; + + compute_connection_distances(str1, &conn1); + compute_connection_distances(str2, &conn2); + + if (findlib(str1, 1, &lib) == 1) { + conn1.distances[lib] = 0; + conn2.distances[lib] = conn2.distances[str1]; + } + + if (findlib(str2, 1, &lib) == 1) { + conn1.distances[lib] = 0; + conn2.distances[lib] = conn2.distances[str2]; + } + + + max_dist1 = conn1.distances[str2]; + max_dist2 = conn2.distances[str1]; + + *total_distance = gg_min(max_dist1, max_dist2); + + if (verbose > 0) { + gprintf("%oVariation %d\n", save_count_variations); + dump_stack(); + showboard(0); + print_connection_distances(&conn1); + print_connection_distances(&conn2); + } + + /* Loop through the points with smallish distance from str1 an look + * for ones also having a small distane to str2. + */ + for (r = 0; r < conn1.queue_end; r++) { + int pos = conn1.queue[r]; + float dist1 = conn1.distances[pos]; + float deltadist1 = conn1.deltas[pos]; + float dist2 = conn2.distances[pos]; + float deltadist2 = conn2.deltas[pos]; + float d1; + float d2; + float distance; + + if (dist1 - deltadist1 + dist2 - deltadist2 > 2.5 + || dist1 > max_dist1 + || dist2 > max_dist2) + continue; + + if (board[pos] == other && find_origin(pos) != pos) + continue; + + if (board[pos] == color) + continue; + + if (verbose > 0) + gprintf("%oMove %1m, (%f, %f, %f, %f)\n", + pos, dist1, deltadist1, dist2, 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 + * account. + */ + d1 = dist1 - deltadist1; + d2 = dist2 - deltadist2; + distance = d1 + d2; + if (verbose > 0) + gprintf("%o %f, primary distance\n", distance); + + /* Bonus if d1 and d2 are well balanced. */ + if (1.5 * d1 > d2 && 1.5 * d2 > d1) { + distance -= 0.1; + if (verbose > 0) + gprintf("%o -0.1, well balanced\n"); + } + + /* Check the surrounding eight vertices to see whether this move + * is "between" the two strings. + */ + for (k = 0; k < 8; k++) { + if (ON_BOARD(pos + delta[k]) && board[pos + delta[k]] != other) { + d1 = dist1 - conn1.distances[pos + delta[k]]; + d2 = dist2 - conn2.distances[pos + delta[k]]; + if (d1 * d2 <= 0.0 && (d1 != 0.0 || d2 != 0.0)) + break; + } + } + if (k == 8 && board[pos] == EMPTY + && (!((liberty_of_string(pos, str1) && countlib(str1) < 3) + || (liberty_of_string(pos, str2) && countlib(str2) < 3)))) { + if (verbose > 0) + gprintf("%o discarded, not on the shortest path\n"); + continue; + } + + if (board[pos] == EMPTY) { + if (!is_self_atari(pos, color_to_move)) { + ADD_CANDIDATE_MOVE(pos, distance, moves, distances, num_moves); + } + else { + if (verbose > 0) + gprintf("%o discarded, self atari\n"); + } + } + else if (board[pos] == other) { + attack_and_defend(pos, &acode, &attack_move, &dcode, &defense_move); + if (verbose > 0) + 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) { + if (dcode == 0) { + distance += 0.5; + if (verbose > 0) + gprintf("%o +0.5, no defense\n"); + } + else { + if (conn1.distances[attack_move] + + conn2.distances[attack_move] > dist1 + dist2) { + distance += 0.5; + if (verbose > 0) + gprintf("%o +0.5, attack point not on shortest path\n"); + } + } + ADD_CANDIDATE_MOVE(attack_move, distance - 0.15, moves, distances, + num_moves); + if (verbose > 0) + gprintf("%o -0.15, capturing a string\n"); + } + else if (!connect_move && acode != 0 && dcode != 0) { + ADD_CANDIDATE_MOVE(defense_move, distance - 0.5, moves, distances, + num_moves); + if (verbose > 0) + gprintf("%o -0.5, defending a string\n"); + } + } + } + + /* Turn the sgf traces back on. */ + sgf_dumptree = save_sgf_dumptree; + count_variations = save_count_variations; + + /* Modify the distance values for the moves with various bonuses. */ + for (r = 0; r < num_moves; r++) { + int move = 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] -= 0.15; + if (verbose > 0) + gprintf("%o%1M -0.15, adjacent to attacker string\n", move); + if (countlib(pos) <= 2) { + distances[r] -= 0.2; + if (verbose > 0) + gprintf("%o%1M -0.2, adjacent to attacker string with at most two liberties\n", move); + if ((conn1.distances[move] - conn1.deltas[move] <= 0.5 + || conn1.distances[pos] - conn1.deltas[pos] <= 0.5) + && (conn2.distances[move] - conn2.deltas[move] <= 0.5 + || conn2.distances[pos] - conn2.deltas[pos] <= 0.5) + && conn1.distances[pos] < *total_distance + && conn2.distances[pos] < *total_distance) { + distances[r] -= 0.7; + if (verbose > 0) + gprintf("%o%1M -0.7, capture or atari of immediately connecting string\n", move); + } + } + } + else if (board[pos] == color) { + if (countlib(pos) <= 2) { + if (verbose > 0) + gprintf("%o%1M -0.2, adjacent to defender string with at most two liberties\n", move); + } + } + } + if (adjacent_to_attacker + && color != color_to_move + && is_edge_vertex(move)) { + distances[r] -= 0.1; + if (verbose > 0) + gprintf("%o%1M -0.1, disconnect move on edge\n", move); + } + + } + + /* 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 + * selection sort. + */ + for (i = 0; i < num_moves; i++) { + /* Find the move with the smallest distance. */ + float mindistance = distances[i]; + int min_at = i; + for (j = i + 1; j < num_moves; j++) { + if (distances[j] < mindistance) { + mindistance = distances[j]; + min_at = j; + } + } + + /* Now exchange the move at i with the move at min_at. + * Don't forget to exchange the distances as well. + */ + if (min_at != i) { + int temp = moves[i]; + float tempmin = distances[i]; + + moves[i] = moves[min_at]; + distances[i] = distances[min_at]; + + moves[min_at] = temp; + distances[min_at] = tempmin; + } + } + + if (verbose > 0) { + gprintf("%oSorted moves:\n"); + for (i = 0; i < num_moves; i++) + gprintf("%o%1M %f\n", moves[i], distances[i]); + } + + if (sgf_dumptree) { + char buf[500]; + char *pos; + int chars; + sprintf(buf, "Move order for %sconnect: %n", + color_to_move == color ? "" : "dis", &chars); + pos = buf + 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]), distances[i], &chars); + pos += chars; + } + sgftreeAddComment(sgf_dumptree, NULL, buf); + } + + + /* Filter out moves with distance at least 1.5 more than the best + * move. + */ + for (r = 0; r < num_moves; r++) + if (distances[r] > distances[0] + 1.5) + break; + num_moves = r; + + return num_moves; +} + + +/* Helper macro for the function below. */ +#define ENQUEUE(conn, pos, dist, delta) \ + do { \ + if (dist < conn->distances[pos]) { \ + if (board[pos] == EMPTY) { \ + if (conn->distances[pos] == HUGE_CONNECTION_DISTANCE) \ + conn->queue[conn->queue_end++] = pos; \ + conn->distances[pos] = dist; \ + conn->deltas[pos] = delta; \ + } \ + else { \ + int r; \ + num_stones = findstones(pos, MAX_BOARD * MAX_BOARD, stones); \ + for (r = 0; r < num_stones; r++) { \ + if (conn->distances[stones[r]] == HUGE_CONNECTION_DISTANCE) \ + conn->queue[conn->queue_end++] = stones[r]; \ + conn->distances[stones[r]] = dist; \ + conn->deltas[stones[r]] = delta; \ + } \ + } \ + } \ + } while (0); + +/* Compute connection distances from the string str to nearby + * vertices. This is a rough approximation of the number of moves + * required to secure a connection from str to another vertex of the + * board. 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 + * problems. + * + * 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. + * + * The propagation is inhibited when the distance becomes too large. + */ +static void +compute_connection_distances(int str, struct connection_data *conn) +{ + int color = board[str]; + int other = OTHER_COLOR(color); + int pos; + int k; + float distance; + int stones[MAX_BOARD * MAX_BOARD]; + int num_stones = findstones(str, MAX_BOARD * MAX_BOARD, stones); + + conn->queue_start = 0; + conn->queue_end = 0; + + /* Initialize distance and delta values so that the former are + * everywhere huge and the latter everywhere zero. + */ + for (pos = BOARDMIN; pos < BOARDMAX; pos++) { + conn->distances[pos] = HUGE_CONNECTION_DISTANCE; + conn->deltas[pos] = 0.0; + } + + /* Add all stones in the initial string to the queue. */ + for (k = 0; k < num_stones; k++) { + ENQUEUE(conn, stones[k], 0.0, 0.0); + } + + /* Loop until we reach the end of the queue. */ + for (; conn->queue_start < conn->queue_end; conn->queue_start++) { + float smallest_dist = HUGE_CONNECTION_DISTANCE; + int best_index = -1; + + 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]]; + best_index = k; + } + } + + /* Exchange the best point with the first element in the queue. */ + if (best_index != conn->queue_start) { + int tmp = conn->queue[conn->queue_start]; + conn->queue[conn->queue_start] = conn->queue[best_index]; + conn->queue[best_index] = tmp; + } + + /* Now we are ready to pick the first element in the queue and + * process it. + */ + pos = conn->queue[conn->queue_start]; + distance = conn->distances[pos]; + + /* No further propagation if the distance is too large. */ + if (distance > 3.0) + break; + + /* 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 *. + * + * jef. + * igb. + * kh*ac + * .d. + * + */ + int right = delta[k]; + int up = delta[(k+1)%4]; + + /* FIXME: Compactify this list. */ + int apos = pos + right; + int bpos = pos + right + up; + int cpos = pos + 2 * right; + int epos = pos + 2*up; + int fpos = pos + right + 2*up; + int gpos = pos + up; + int hpos = pos - right; + 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, apos, distance, 0.0); + } + + /* Case 2. "a" is empty and would be self atari for the opponent. */ + if (conn->distances[apos] > distance + 0.1 + && board[apos] == EMPTY + && is_self_atari(apos, other)) { + ENQUEUE(conn, apos, distance + 0.1, 0.1); + } + + /* 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, bpos, distance + 0.1, 0.1); + ENQUEUE(conn, gpos, distance + 0.1, 0.1); + } + + /* Case 4. Diagonal connection to another stone "b" through + * empty vertices "a" and "g". + */ + if (conn->distances[bpos] > distance + 0.2 + && board[bpos] == color + && board[apos] == EMPTY && board[gpos] == EMPTY) { + ENQUEUE(conn, apos, distance + 0.2, 0.2); + ENQUEUE(conn, gpos, distance + 0.2, 0.2); + } + + /* Case 5. Almost bamboo joint. + * + */ + if (conn->distances[gpos] > distance + 0.2 + && board[gpos] == EMPTY + && board[epos] == color + && approxlib(gpos, other, 3, NULL) <= 2 + && ((board[bpos] == EMPTY + && approxlib(bpos, color, 3, NULL) >= 3 + && (board[apos] == color + || (board[apos] == EMPTY + && approxlib(apos, other, 3, NULL) <= 2)) + && (board[fpos] == color + || (board[fpos] == EMPTY + && approxlib(fpos, other, 3, NULL) <= 2))) + || (board[ipos] == EMPTY + && approxlib(ipos, color, 3, NULL) >= 3 + && (board[hpos] == color + || (board[hpos] == EMPTY + && approxlib(hpos, other, 3, NULL) <= 2)) + && (board[jpos] == color + || (board[jpos] == EMPTY + && approxlib(jpos, other, 3, NULL) <= 2))))) { + ENQUEUE(conn, gpos, distance + 0.2, 0.2); + } + + /* Case 6. "a" is empty and an opponent move can be captured in + * a ladder. + */ + if (conn->distances[apos] > distance + 0.7 + && board[apos] == EMPTY + && ladder_capturable(apos, other)) { + ENQUEUE(conn, apos, distance + 0.7, 0.7); + } + + /* Case 7. "a" is empty or occupied by opponent. + */ + if (conn->distances[apos] > distance + 1.0 + && (board[apos] == EMPTY + || board[apos] == other)) { + ENQUEUE(conn, apos, distance + 1.0, 1.0); + } + + /* Case 8. Diagonal connection to empty vertex "b" through + * empty vertex "a" or "g", which makes "a" or "g" self_atari + * for opponent. + */ + if (conn->distances[bpos] > distance + 1.1 + && board[bpos] == EMPTY + && board[apos] == EMPTY && does_secure(color, bpos, apos)) { + ENQUEUE(conn, bpos, distance + 1.1, 1.0); + } + + if (conn->distances[bpos] > distance + 1.1 + && board[bpos] == EMPTY + && board[gpos] == EMPTY && does_secure(color, bpos, gpos)) { + ENQUEUE(conn, bpos, distance + 1.1, 1.0); + } + + /* Case 9. One-space jump to empty vertex "e" through empty + * vertex "g", which makes "g" self_atari for opponent. + */ + if (conn->distances[epos] > distance + 1.1 + && board[gpos] == EMPTY + && board[epos] == EMPTY && does_secure(color, epos, gpos)) { + ENQUEUE(conn, epos, distance + 1.1, 1.0); + } + + /* Case 10. Diagonal connection to empty vertex "b" through + * empty vertices "a" and "g". + */ + if (conn->distances[bpos] > distance + 1.3 + && board[bpos] == EMPTY + && board[apos] == EMPTY && board[gpos] == EMPTY) { + ENQUEUE(conn, bpos, distance + 1.3, 1.0); + } + + /* Case 11. Keima to f or j on edge and one space jump on + * first or second line. + */ + if ((conn->distances[fpos] > distance + 1.3 + || conn->distances[epos] > distance + 1.5) + && countlib(pos) >= 3 + && board[apos] == EMPTY + && board[bpos] == EMPTY + && board[gpos] == EMPTY + && board[epos] == EMPTY + && board[fpos] == EMPTY + && (!ON_BOARD(cpos) || !ON_BOARD(hpos))) { + ENQUEUE(conn, fpos, distance + 1.3, 1.0); + ENQUEUE(conn, epos, distance + 1.3, 1.0); + } + + if ((conn->distances[jpos] > distance + 1.3 + || conn->distances[epos] > distance + 1.5) + && countlib(pos) >= 3 + && board[hpos] == EMPTY + && board[ipos] == EMPTY + && board[gpos] == EMPTY + && board[epos] == EMPTY + && board[jpos] == EMPTY + && (!ON_BOARD(apos) || !ON_BOARD(kpos))) { + ENQUEUE(conn, jpos, distance + 1.3, 1.0); + ENQUEUE(conn, epos, distance + 1.3, 1.0); + } + + /* Case 12. 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. + */ + if (conn->distances[bpos] > distance + 1.2 + && board[bpos] == EMPTY + && board[apos] == EMPTY + && does_secure_through_ladder(color, bpos, apos)) { + ENQUEUE(conn, bpos, distance + 1.2, 1.0); + } + + if (conn->distances[bpos] > distance + 1.2 + && board[bpos] == EMPTY + && board[gpos] == EMPTY + && does_secure_through_ladder(color, bpos, gpos)) { + ENQUEUE(conn, bpos, distance + 1.2, 1.0); + } + + /* Case 13. Diagonal connection to empty vertex "b" through + * empty vertex "a" or "g", with no particular properties. + */ + if (conn->distances[bpos] > distance + 1.8 + && board[bpos] == EMPTY + && board[apos] == EMPTY) { + ENQUEUE(conn, bpos, distance + 1.8, 0.9); + } + + if (conn->distances[bpos] > distance + 1.8 + && board[bpos] == EMPTY + && board[gpos] == EMPTY + && does_secure_through_ladder(color, bpos, gpos)) { + ENQUEUE(conn, bpos, distance + 1.8, 0.9); + } + + /* Case 14. Diagonal connection to empty vertex "b" through + * opponent stones "a" or "g" with few liberties. + */ + if (conn->distances[bpos] > distance + 2.0 + && board[bpos] == EMPTY + && board[apos] == other + && board[gpos] == other + && (countlib(apos) + countlib(gpos) <= 6)) { + ENQUEUE(conn, bpos, distance + 2.0, 1.0); + } + + /* Case 15. Diagonal connection to own stone "b" through + * opponent stones "a" or "g" with few liberties. + */ + if (conn->distances[bpos] > distance + 2.0 + && board[bpos] == color + && board[apos] == other + && board[gpos] == other + && (countlib(apos) + countlib(gpos) <= 5)) { + ENQUEUE(conn, bpos, distance + 2.0, 1.0); + } + + /* Case 16. Adjacent opponent stone at "a" which can't avoid atari. + */ + if (conn->distances[apos] > distance + 0.1 + && board[apos] == other + && no_escape_from_atari(apos)) { + ENQUEUE(conn, apos, distance + 0.1, 0.1); + } + + /* Case 17. Adjacent opponent stone at "a" which can't avoid + * ladder capture. + */ + if (conn->distances[apos] > distance + 0.3 + && board[apos] == other + && no_escape_from_ladder(apos)) { + ENQUEUE(conn, apos, distance + 0.3, 0.3); + } + } + } + else if (board[pos] == EMPTY + || (board[pos] == other + && (no_escape_from_ladder(pos)) + && countlib(pos) <= 2)) { + for (k = 0; k < 4; k++) { + /* List of relative coordinates. (pos) is marked by *. + * + * jef. + * igb. + * kh*ac + * .d. + * + */ + int right = delta[k]; + int up = delta[(k+1)%4]; + + /* FIXME: Compactify this list. */ + int apos = pos + right; + int bpos = pos + right + up; +#if 0 + int cpos = pos + 2 * right; + int epos = pos + 2*up; + int fpos = pos + right + 2*up; +#endif + int gpos = pos + up; +#if 0 + int hpos = pos - right; + int ipos = pos - right + up; + int jpos = pos - right + 2 * up; + int kpos = pos - 2 * right; +#endif + + if (board[apos] == color) { + ENQUEUE(conn, apos, distance, 0.0); + } + else if (ON_BOARD(apos)) { + ENQUEUE(conn, apos, distance + 1.0, 1.0); + } + + /* Case 1. Diagonal connection to empty vertex "b" through + * empty vertices "a" and "g". + */ + if (conn->distances[bpos] > distance + 1.5 + && board[bpos] == EMPTY + && board[apos] == EMPTY && board[gpos] == EMPTY) { + ENQUEUE(conn, bpos, distance + 1.5, 1.0); + } + + /* Case 2. Diagonal connection to friendly stone at "b" through + * empty vertices "a" and "g". + */ + if (conn->distances[bpos] > distance + 1.3 + && board[bpos] == color + && board[apos] == EMPTY && board[gpos] == EMPTY) { + ENQUEUE(conn, bpos, distance + 1.3, 1.0); + } + } + } + } +} + + +/* Print the connection distances in a struct connection_data. */ +static void +print_connection_distances(struct connection_data *conn) +{ + int i, j; + int ch; + + fprintf(stderr, " "); + for (j = 0, ch = 'A'; j < board_size; j++, ch++) { + if (ch == 'I') + ch++; + fprintf(stderr, " %c ", ch); + } + fprintf(stderr, "\n"); + + for (i = 0; i < board_size; i++) { + fprintf(stderr, "%2d ", board_size - i); + for (j = 0; j < board_size; j++) { + int pos = POS(i, j); + if (conn->distances[pos] == HUGE_CONNECTION_DISTANCE) { + if (board[pos] == WHITE) + fprintf(stderr, " O "); + if (board[pos] == BLACK) + fprintf(stderr, " X "); + if (board[pos] == EMPTY) + fprintf(stderr, " . "); + } + else { + fprintf(stderr, "%3.1f ", conn->distances[pos]); + } + } + fprintf(stderr, "\n"); + } + fprintf(stderr, "\n"); +} + + +/* 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. + */ +static int +trivial_connection(int str1, int str2, int *move) +{ + SGFTree *save_sgf_dumptree = sgf_dumptree; + int save_count_variations = count_variations; + int adj, adjs[MAXCHAIN]; + int r; + int result = 0; + + if (have_common_lib(str1, str2, move)) + return WIN; + + adj = chainlinks(str1, adjs); + + /* We turn off the sgf traces here to avoid cluttering them up with + * tactical reading moves. + */ + sgf_dumptree = NULL; + count_variations = 0; + + for (r = 0; r < adj; r++) + if (adjacent_strings(adjs[r], str2) && attack(adjs[r], move) == WIN) { + result = WIN; + break; + } + + /* Turn the sgf traces back on. */ + sgf_dumptree = save_sgf_dumptree; + count_variations = save_count_variations; + + return result; +} + + +/* True if a move by color makes an opponent move at pos a self atari. + */ +static int +does_secure(int color, int move, int pos) +{ + int result = 0; + if (trymove(move, color, NULL, NO_MOVE, EMPTY, NO_MOVE)) { + if (is_self_atari(pos, OTHER_COLOR(color))) + result = 1; + popgo(); + } + + return result; +} + + +/* True if a move by color makes an opponent move at pos a self atari + * or possible to capture in a ladder. + */ +static int +does_secure_through_ladder(int color, int move, int pos) +{ + int result = 0; + + if (trymove(move, color, NULL, NO_MOVE, EMPTY, NO_MOVE)) { + if (ladder_capturable(pos, OTHER_COLOR(color))) + result = 1; + popgo(); + } + + return result; +} + +/* 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 + * *move. + */ +static int +ladder_capture(int str, int *move) +{ + int result; + 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. + */ + sgf_dumptree = NULL; + count_variations = 0; + + if (liberties == 1) + result = attack(str, move); + else if (liberties == 2) + result = simple_ladder(str, move); + else + result = 0; + + /* Turn the sgf traces back on. */ + sgf_dumptree = save_sgf_dumptree; + count_variations = save_count_variations; + + return result; +} + +/* Test whether a move at pos by color can be captured in a ladder. */ +static int +ladder_capturable(int pos, int color) +{ + int result = 0; + + if (trymove(pos, color, NULL, NO_MOVE, EMPTY, NO_MOVE)) { + int liberties = countlib(pos); + if (liberties == 1 && attack(pos, NULL) == WIN) + result = 1; + else if (liberties == 2 && simple_ladder(pos, NULL) == WIN) + result = 1; + popgo(); + } + else + result = 1; + + return result; +} + + +/* 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. + */ +static int +no_escape_from_atari(int str) +{ + int lib; + int adj[MAXCHAIN]; + + if (findlib(str, 1, &lib) > 1) + return 0; + + if (accurate_approxlib(lib, board[str], 2, NULL) > 1) + return 0; + + /* FIXME: Should exclude snapback. */ + if (chainlinks2(str, adj, 1) > 0) + return 0; + + return 1; +} + + +/* 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. + * FIXME: Needs a simple_ladder_defense(). + */ +static int +no_escape_from_ladder(int str) +{ + int result = 0; + 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. + */ + sgf_dumptree = NULL; + count_variations = 0; + + if (countlib(str) == 1 && find_defense(str, NULL) == 0) + result = 1; + + /* Turn the sgf traces back on. */ + sgf_dumptree = save_sgf_dumptree; + count_variations = save_count_variations; + + return result; +} + /* * Local Variables: Index: interface/main.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/interface/main.c,v retrieving revision 1.24 diff -u -r1.24 main.c --- interface/main.c 19 Jan 2002 16:11:16 -0000 1.24 +++ interface/main.c 31 Jan 2002 21:39:46 -0000 @@ -90,6 +90,7 @@ OPT_SEMEAI_VARIATIONS, OPT_EXPERIMENTAL_CONNECTIONS, OPT_EXPERIMENTAL_INFLUENCE, + OPT_ALTERNATE_CONNECTIONS, OPT_STANDARD_SEMEAI, OPT_STANDARD_CONNECTIONS, OPT_STANDARD_INFLUENCE, @@ -206,7 +207,9 @@ {"no-owl-threats", no_argument, 0, OPT_NO_OWL_THREATS}, {"experimental-influence", no_argument, 0, OPT_EXPERIMENTAL_INFLUENCE}, {"standard-influence", no_argument, 0, OPT_STANDARD_INFLUENCE}, + {"standard-connections", no_argument, 0, OPT_STANDARD_CONNECTIONS}, {"standard_semeai", no_argument, 0, OPT_STANDARD_SEMEAI}, + {"alternate-connections", no_argument, 0, OPT_ALTERNATE_CONNECTIONS}, {"allow-suicide", no_argument, 0, OPT_ALLOW_SUICIDE}, {"capture-all-dead", no_argument, 0, OPT_CAPTURE_ALL_DEAD}, {"play-out-aftermath", no_argument, 0, OPT_PLAY_OUT_AFTERMATH}, @@ -466,6 +469,10 @@ case OPT_STANDARD_CONNECTIONS: experimental_connections = 0; + break; + + case OPT_ALTERNATE_CONNECTIONS: + alternate_connections = !alternate_connections; break; case OPT_EXPERIMENTAL_INFLUENCE: