[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] breakin tesujis
|
From: |
Arend Bayer |
|
Subject: |
[gnugo-devel] breakin tesujis |
|
Date: |
Mon, 26 May 2003 00:21:58 +0200 (CEST) |
I wrote:
> Paul wrote:
> > while looking through Trevor's test suites today i discovered trevora:610
> > problem. a wonderful tesuji! it would be very nice if gnu go knew it.
>
> Wouldn't "How to teach gnugo wonderful tesujis?" be a more motivating
> subject line? ;)
>
> > A B C D E F G H J
> > 9 . . . . . . . . . 9
> > 8 . . . . . . O O O 8
> > 7 O O O O . . O X X 7
> > 6 X O X X O O X . X 6
> > 5 X X . X + . X X . 5
> > 4 . . X O O O O X . 4
> > 3 . . X . . . X . . 3
> > 2 . . . . X . . . . 2 WHITE (O) has captured 0 stones
> > 1 . . . . . . . . . 1 BLACK (X) has captured 1 stones
> > A B C D E F G H J
> >
> > white D2 or F2 invades. this position must be rather common in games.
>
> I just recently chatted with Gunnar about similar situations. Take e.g.:
> A B C D E F G H J
> 9 . . . . . . . . . 9
> 8 . . . . . . . . . 8
> 7 . . + O X X + . . 7
> 6 . . . O O O X . . 6
> 5 . . . . + . . . . 5
> 4 . . . . . . X . . 4
> 3 . . + . . . + . . 3
> 2 . . . . . . . . . 2 WHITE (O) has captured 0 stones
> 1 . . . . . . . . . 1 BLACK (X) has captured 0 stones
> A B C D E F G H J
>
> O can gain a lot here by playing G7 or G5. And I think GG could improve
> a lot by finding such moves (moves breaking into opponents purposed
> territory/moyo).
>
> Possible ways to try to find these:
(...)
> 3. I have the crude idea that one could misuse the connection code
> as follows:
>
> A B C D E F G H J
> 9 . . . . . a a a a 9
> 8 . . . . . a a a a 8
> 7 . . + B X X a a a 7
> 6 . . . B B B X a a 6
> 5 . . . . + . . a a 5
> 4 . . . . . . X . . 4
> 3 . . + . . . + . . 3
> 2 . . . . . . . . . 2 WHITE (O) has captured 0 stones
> 1 . . . . . . . . . 1 BLACK (X) has captured 0 stones
> A B C D E F G H J
>
> connect(a, B) is deemed successful if white can get any stone on a
> connected to B.
The patch below does just that.
It still has some problems, most notably performance, so it's put under
an --experimental command line switch. It does seem to generally work
for the situations it was intended for, and in particularly solves both
the above cases.
It adds:
- A new recursive function pair recursive_break(str, goal, ...) and
recursive_block(str, goal) that do the reading for what I called
connect(B,a) above. The nice thing is that I really could reuse big
parts of Gunnar's code after a small reorganization.
- Frontends break_in(str, goal, *move) and block_off(str, goal, *move)
to these function (with GTP commands)
- A new file breakin.c that does a systematic analysis of all big
territories whether there are break-in possibilities. That file should
have sufficiently many comments that I don't need to explain much of
the details here.
It again reuses compute_connection_distances() to identify opposite
stones from which a break-in could be launched. As I didn't want to make
those (and the struct connection_data) globally accessible, I added a new
file readconnect.h to export them.
Oh, and I followed one of my convictions that we should analyze
positons, not moves. So while that module does generate move reasons
for break-in moves (EXPAND_TERRITORY), it doesn't explicitly assign them
values. Instead, it does get called automatically for every move, and
will then notice that there is an unstoppable intrusion.
This does explain part of the slowness, of course, but that should be
solvable by a persistent cache (I haven't implemented any caching yet).
If anyone wants to experiment with it, that would be welcome. I won't be
able to touch it for the next week.
Arend
trevora:150 PASS F6 [F6]
trevora:510 PASS F4 [F4]
nngs1:26 FAIL Q3 [P3]
nngs1:33 FAIL S9 [!S9]
lazarus:6 PASS H3 [H3]
trevorb:290 PASS H8 [!E13]
trevorb:360 FAIL H7 [K3]
trevorb:680 FAIL G5 [M5]
trevor:1100 PASS D15 [D15]
trevorc:630 FAIL C8 [G2|H2]
trevorc:1000 PASS M11 [N9|M11]
strategy3:120 FAIL B7 [C7]
trevord:160 PASS N7 [N7]
trevord:330 FAIL K19 [D16]
trevord:680 FAIL R15 [S16]
trevord:1090 FAIL G5 [L7]
nngs3:420 FAIL O15 [R14|R15]
nngs3:700 FAIL C2 [Q2]
nngs3:710 FAIL C2 [Q2]
gunnar:10 PASS R12 [R12|R14]
Index: engine/Makefile.am
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/Makefile.am,v
retrieving revision 1.19
diff -u -p -r1.19 Makefile.am
--- engine/Makefile.am 22 Feb 2003 10:54:23 -0000 1.19
+++ engine/Makefile.am 25 May 2003 22:22:22 -0000
@@ -9,7 +9,7 @@ INCLUDES = \
-I$(top_srcdir)/sgf \
-I$(top_srcdir)/utils
-noinst_HEADERS = cache.h gnugo.h hash.h clock.h \
+noinst_HEADERS = cache.h gnugo.h hash.h clock.h readconnect.h \
influence.h liberty.h move_reasons.h
# preconfigured settings for various configurations
@@ -18,6 +18,7 @@ noinst_LIBRARIES = libengine.a libboard.
libengine_a_SOURCES = \
aftermath.c \
board.c \
+ breakin.c \
cache.c \
clock.c \
combination.c \
Index: engine/dragon.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v
retrieving revision 1.111
diff -u -p -r1.111 dragon.c
--- engine/dragon.c 11 May 2003 06:41:38 -0000 1.111
+++ engine/dragon.c 25 May 2003 22:22:25 -0000
@@ -1228,10 +1228,12 @@ compute_dragon_influence()
set_strength_data(BLACK, safe_stones, strength);
compute_influence(BLACK, safe_stones, strength, &initial_black_influence,
NO_MOVE, "initial black influence, dragons known");
+ break_territories(BLACK, &initial_black_influence, 1);
set_strength_data(WHITE, safe_stones, strength);
compute_influence(WHITE, safe_stones, strength, &initial_white_influence,
NO_MOVE, "initial white influence, dragons known");
+ break_territories(WHITE, &initial_white_influence, 1);
}
Index: engine/genmove.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/genmove.c,v
retrieving revision 1.73
diff -u -p -r1.73 genmove.c
--- engine/genmove.c 10 May 2003 19:28:20 -0000 1.73
+++ engine/genmove.c 25 May 2003 22:22:26 -0000
@@ -88,6 +88,7 @@ reset_engine()
/* Prepare our table of move reasons. */
clear_move_reasons();
+ clear_break_in_list();
/* Set up depth values (see comments there for details). */
set_depth_values(level);
@@ -291,6 +292,7 @@ collect_move_reasons(int color)
worm_reasons(color);
owl_reasons(color);
semeai_move_reasons(color);
+ break_in_move_reasons(color);
}
/*
Index: engine/globals.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/globals.c,v
retrieving revision 1.46
diff -u -p -r1.46 globals.c
--- engine/globals.c 1 May 2003 20:55:26 -0000 1.46
+++ engine/globals.c 25 May 2003 22:22:27 -0000
@@ -141,6 +141,8 @@ int alternate_connections = ALTERNATE_CO
int owl_threats = OWL_THREATS; /* compute owl threats */
/* use experimental owl extension (GAIN/LOSS) */
int experimental_owl_ext = EXPERIMENTAL_OWL_EXT;
+/* use experimental territory break-in module */
+int experimental_break_in = 0;
int allow_suicide = 0; /* allow opponent to make suicide moves */
int capture_all_dead = 0; /* capture all dead opponent stones */
Index: engine/gnugo.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/gnugo.h,v
retrieving revision 1.94
diff -u -p -r1.94 gnugo.h
--- engine/gnugo.h 1 May 2003 20:55:26 -0000 1.94
+++ engine/gnugo.h 25 May 2003 22:22:27 -0000
@@ -279,7 +279,6 @@ extern int experimental_semeai; /*
extern int experimental_connections; /* use experimental connection module */
extern int alternate_connections; /* use alternate connection module */
extern int owl_threats; /* compute owl threats */
-extern int experimental_influence; /* use experimental influence module */
extern int allow_suicide; /* allow opponent to make suicide moves */
extern int capture_all_dead; /* capture all dead opponent stones */
extern int play_out_aftermath; /* make everything unconditionally settled */
Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.79
diff -u -p -r1.79 influence.c
--- engine/influence.c 6 May 2003 11:46:12 -0000 1.79
+++ engine/influence.c 25 May 2003 22:22:34 -0000
@@ -892,6 +892,27 @@ influence_mark_non_territory(int pos, in
current_influence->non_territory[pos] |= color;
}
+/* Erases all territory for color at (pos), and all directly neighboring
+ * fields.
+ */
+void
+influence_erase_territory(struct influence_data *q, int pos, int color)
+{
+ int k;
+ float factor;
+ ASSERT1((color == WHITE && q->territory_value[pos] >= 0.0)
+ || (color == BLACK && q->territory_value[pos] <= 0.0), pos);
+
+ current_influence = q;
+
+ q->territory_value[pos] = 0.0;
+ influence_mark_non_territory(pos, color);
+ for (k = 0; k < 4; k++) {
+ q->territory_value[pos + delta[k]] = 0.0;
+ influence_mark_non_territory(pos + delta[k], color);
+ }
+}
+
/* Match the patterns in influence.db and barriers.db in order to add:
* - influence barriers,
* - extra influence sources at possible invasion and intrusion points, and
@@ -1411,6 +1432,53 @@ influence_get_moyo_segmentation(const st
}
}
+
+/* Export the territory segmentation. */
+void
+influence_get_territory_segmentation(const struct influence_data *q,
+ struct moyo_data *moyos)
+{
+ int ii;
+ int min_moyo_id;
+ int max_moyo_id;
+ int i;
+
+ min_moyo_id = MAX_REGIONS;
+ max_moyo_id = 0;
+
+ /* Find out range of region ids used by moyos. */
+ for (ii = BOARDMIN; ii < BOARDMAX; ii++)
+ if (ON_BOARD(ii)) {
+ if (q->territory_segmentation[ii] != 0) {
+ min_moyo_id = gg_min(min_moyo_id, q->territory_segmentation[ii]);
+ max_moyo_id = gg_max(max_moyo_id, q->territory_segmentation[ii]);
+ }
+ }
+ moyos->number = max_moyo_id - min_moyo_id + 1;
+
+ /* Export segmentation. */
+ for (ii = BOARDMIN; ii < BOARDMAX; ii++)
+ if (ON_BOARD(ii)) {
+ if (q->territory_segmentation[ii] != 0) {
+ moyos->segmentation[ii]
+ = q->territory_segmentation[ii] - min_moyo_id + 1;
+ }
+ else
+ moyos->segmentation[ii] = 0;
+ }
+
+ /* Export size and owner info. */
+ for (i = min_moyo_id; i <= max_moyo_id; i++) {
+ moyos->size[i - min_moyo_id + 1] = q->region_size[i];
+ moyos->territorial_value[i - min_moyo_id + 1]
+ = q->region_territorial_value[i];
+ if (q->region_type[i] & BLACK_REGION)
+ moyos->owner[i - min_moyo_id + 1] = BLACK;
+ else
+ moyos->owner[i - min_moyo_id + 1] = WHITE;
+ }
+}
+
/* Another function to export a certain amount of moyo data. */
void
influence_get_moyo_data(const struct influence_data *q,
@@ -1436,6 +1504,12 @@ influence_territory(const struct influen
return q->territory_value[pos];
else
return -q->territory_value[pos];
+}
+
+int
+influence_considered_safe(const struct influence_data *q, int pos)
+{
+ return q->safe[pos];
}
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.172
diff -u -p -r1.172 liberty.h
--- engine/liberty.h 19 May 2003 16:11:16 -0000 1.172
+++ engine/liberty.h 25 May 2003 22:22:34 -0000
@@ -356,6 +356,9 @@ int string_connect(int str1, int str2, i
int disconnect(int str1, int str2, int *move);
int non_transitivity(int str1, int str2, int str3, int *move);
+int break_in(int str, char goal[BOARDMAX], int *move);
+int block_off(int str1, char goal[BOARDMAX], int *move);
+
/* board.c */
int liberty_of_string(int pos, int str);
int second_order_liberty_of_string(int pos, int str);
@@ -698,6 +701,8 @@ int whose_area(const struct influence_da
float influence_territory(const struct influence_data *q, int pos, int color);
void influence_get_moyo_segmentation(const struct influence_data *q,
struct moyo_data *moyo);
+void influence_get_territory_segmentation(const struct influence_data *q,
+ struct moyo_data *moyo);
void influence_get_moyo_data(const struct influence_data *q,
int moyo_color[BOARDMAX],
float territory_value[BOARDMAX]);
@@ -709,6 +714,13 @@ float influence_score(const struct influ
float game_status(int color);
void resegment_initial_influence(void);
void influence_mark_non_territory(int pos, int color);
+int influence_considered_safe(const struct influence_data *q, int pos);
+void influence_erase_territory(struct influence_data *q, int pos, int color);
+
+void break_territories(int color_to_move, struct influence_data *q,
+ int store);
+void clear_break_in_list(void);
+void break_in_move_reasons(int color);
float estimate_score(float *upper, float *lower);
@@ -796,7 +808,7 @@ extern int experimental_semeai; /*
extern int experimental_connections; /* use experimental connection module */
extern int alternate_connections; /* use alternate connection module */
extern int owl_threats; /* compute owl threats */
-extern int experimental_influence; /* use experimental influence module */
+extern int experimental_break_in; /* use experimental module breakin.c */
extern int thrashing_dragon; /* Dead opponent's dragon trying to live */
extern char thrashing_stone[BOARDMAX]; /* All thrashing stones. */
Index: engine/readconnect.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/readconnect.c,v
retrieving revision 1.47
diff -u -p -r1.47 readconnect.c
--- engine/readconnect.c 22 May 2003 22:50:06 -0000 1.47
+++ engine/readconnect.c 25 May 2003 22:22:37 -0000
@@ -30,6 +30,7 @@
#include "liberty.h"
#include "cache.h"
#include "gg_utils.h"
+#include "readconnect.h"
/* Size of array where candidate moves are stored. */
#define MAX_MOVES 362
@@ -46,6 +47,10 @@ static int recursive_connect2(int str1,
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 recursive_break(int str, char goal[BOARDMAX], int *move,
+ int komaster, int kom_pos, int has_passed);
+static int recursive_block(int str, char goal[BOARDMAX], 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);
@@ -1869,24 +1874,12 @@ get_connection_node_counter()
} while (0)
-struct connection_data {
- float distances[BOARDMAX];
- float deltas[BOARDMAX];
- int coming_from[BOARDMAX];
- int vulnerable1[BOARDMAX];
- int vulnerable2[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, int target,
- struct connection_data *conn);
-static void print_connection_distances(struct connection_data *conn);
+static int find_string_connection_moves(int str1, int str2, int color_to_move,
+ int moves[MAX_MOVES],
+ float *total_distance);
+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);
@@ -1977,7 +1970,8 @@ recursive_connect2(int str1, int str2, i
READ_RETURN_CONN(read_result, move, xpos, WIN);
}
- num_moves = find_connection_moves(str1, str2, color, moves, &distance);
+ num_moves = find_string_connection_moves(str1, str2, color,
+ moves, &distance);
for (k = 0; k < num_moves; k++) {
int new_komaster;
@@ -2116,7 +2110,8 @@ recursive_disconnect2(int str1, int str2
READ_RETURN_CONN(read_result, move, xpos, WIN);
}
- num_moves = find_connection_moves(str1, str2, other, moves, &distance);
+ num_moves = find_string_connection_moves(str1, str2, other,
+ moves, &distance);
for (k = 0; k < num_moves; k++) {
int new_komaster;
@@ -2192,27 +2187,25 @@ recursive_disconnect2(int str1, int str2
*/
static int
find_connection_moves(int str1, int str2, int color_to_move,
- int moves[MAX_MOVES], float *total_distance)
+ struct connection_data *conn1,
+ struct connection_data *conn2,
+ float max_dist1, float max_dist2,
+ 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;
+ 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.
@@ -2220,44 +2213,15 @@ find_connection_moves(int str1, int str2
sgf_dumptree = NULL;
count_variations = 0;
- compute_connection_distances(str1, str2, &conn1);
- compute_connection_distances(str2, str1, &conn2);
-
- 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);
-
- 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 and look
* for ones also having a small distance 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];
+ 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;
@@ -2293,8 +2257,8 @@ find_connection_moves(int str1, int str2
}
/* Check whether the move is "between" the two strings. */
- if (conn1.coming_from[pos] != NO_MOVE
- && conn1.coming_from[pos] == conn2.coming_from[pos]) {
+ if (conn1->coming_from[pos] != NO_MOVE
+ && conn1->coming_from[pos] == conn2->coming_from[pos]) {
if (verbose > 0)
gprintf("%o discarded, not between strings\n");
continue;
@@ -2322,8 +2286,8 @@ find_connection_moves(int str1, int str2
gprintf("%o +0.5, no defense\n");
}
else {
- if (conn1.distances[attack_move]
- + conn2.distances[attack_move] > dist1 + dist2) {
+ 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");
@@ -2346,14 +2310,14 @@ find_connection_moves(int str1, int str2
for (k = 0; k < 4; k++) {
int apos, bpos;
if (k & 1)
- apos = conn1.vulnerable1[pos];
+ apos = conn1->vulnerable1[pos];
else
- apos = conn1.vulnerable2[pos];
+ apos = conn1->vulnerable2[pos];
if (k & 2)
- bpos = conn2.vulnerable1[pos];
+ bpos = conn2->vulnerable1[pos];
else
- bpos = conn2.vulnerable2[pos];
+ bpos = conn2->vulnerable2[pos];
if (common_vulnerability(apos, bpos, color)) {
if (check_self_atari(apos, color_to_move)) {
@@ -2373,10 +2337,6 @@ find_connection_moves(int str1, int str2
}
}
- /* 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];
@@ -2393,12 +2353,12 @@ find_connection_moves(int str1, int str2
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) {
+ 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);
@@ -2427,7 +2387,7 @@ find_connection_moves(int str1, int str2
*/
if ((liberty_of_string(move, str1)
&& countlib(str1) == 3)
- || (liberty_of_string(move, str2)
+ || (ON_BOARD(str2) && liberty_of_string(move, str2)
&& countlib(str2) == 3)) {
distances[r] -= 0.1;
if (verbose > 0)
@@ -2435,6 +2395,10 @@ find_connection_moves(int str1, int str2
}
}
+ /* Turn the sgf traces back on. */
+ sgf_dumptree = save_sgf_dumptree;
+ count_variations = save_count_variations;
+
/* Normalize distance values. See comment to gg_normalize_float() in
* utils/gg_utils.c for an explanation of this operation. It is
* assumed that all distance values are integral multiples of 0.001.
@@ -2485,7 +2449,7 @@ find_connection_moves(int str1, int str2
char *pos;
int chars;
sprintf(buf, "Move order for %sconnect: %n",
- color_to_move == color ? "" : "dis", &chars);
+ connect_move ? "" : "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),
@@ -2507,6 +2471,499 @@ find_connection_moves(int str1, int str2
return num_moves;
}
+static int
+find_string_connection_moves(int str1, int str2, int color_to_move,
+ int moves[MAX_MOVES], float *total_distance)
+{
+ struct connection_data conn1;
+ struct connection_data conn2;
+ float max_dist1;
+ float max_dist2;
+ int num_moves;
+ int lib;
+ 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;
+
+ compute_connection_distances(str1, str2, 3.051, &conn1);
+ compute_connection_distances(str2, str1, 3.051, &conn2);
+
+ 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);
+
+ if (verbose > 0) {
+ gprintf("%oVariation %d\n", save_count_variations);
+ dump_stack();
+ showboard(0);
+ 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,
+ moves, *total_distance);
+ return num_moves;
+}
+
+void
+init_connection_data(int color, const char goal[BOARDMAX],
+ struct connection_data *conn)
+{
+ int pos;
+ clear_connection_data(conn);
+ for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+ if ((board[pos] == EMPTY || board[pos] == color)
+ && goal[pos]) {
+ conn->queue[conn->queue_end++] = pos;
+ if (board[pos] == color) {
+ conn->distances[pos] = 0.0;
+ conn->deltas[pos] = 0.0;
+ }
+ else {
+ conn->distances[pos] = 1.0;
+ conn->deltas[pos] = 1.0;
+ }
+ conn->coming_from[pos] = NO_MOVE;
+ conn->vulnerable1[pos] = NO_MOVE;
+ conn->vulnerable2[pos] = NO_MOVE;
+ }
+}
+
+static int
+find_break_moves(int str, char goal[BOARDMAX], int color_to_move,
+ int moves[MAX_MOVES], float *total_distance)
+{
+ struct connection_data conn1;
+ struct connection_data conn2;
+ float max_dist1 = HUGE_CONNECTION_DISTANCE;
+ float max_dist2;
+ int num_moves;
+ int str2 = NO_MOVE;
+ int color = board[str];
+ int lib;
+ int k;
+ 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;
+
+ compute_connection_distances(str, NO_MOVE, 2.501, &conn1);
+ for (k = 0; k < conn1.queue_end; k++)
+ if (goal[conn1.queue[k]]
+ && board[conn1.queue[k]] == color) {
+ str2 = conn1.queue[k];
+ TRACE("%oUsing %1m as secondary target.\n", str2);
+ break;
+ }
+
+ /* Add all stones in the goal to the queue. */
+ init_connection_data(color, goal, &conn2);
+ 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, str, &conn2, 2.501, 1);
+
+ 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);
+
+ if (verbose > 0) {
+ gprintf("%oVariation %d\n", save_count_variations);
+ dump_stack();
+ showboard(0);
+ print_connection_distances(&conn1);
+ print_connection_distances(&conn2);
+ }
+
+ /* Turn the sgf traces back on. */
+ sgf_dumptree = save_sgf_dumptree;
+ count_variations = save_count_variations;
+
+ num_moves = find_connection_moves(str, str2, color_to_move,
+ &conn1, &conn2, max_dist1, max_dist2,
+ moves, *total_distance);
+
+ {
+ int move;
+ if (num_moves < MAX_MOVES
+ && ON_BOARD(str2)
+ && ladder_capture(str2, &move)) {
+ moves[num_moves++] = move;
+ }
+ }
+
+ return num_moves;
+}
+
+
+int break_in_node_limit;
+int break_in_depth;
+
+static int
+recursive_break(int str, char goal[BOARDMAX], int *move,
+ int komaster, int kom_pos, int has_passed)
+{
+ int color = board[str];
+ int moves[MAX_MOVES];
+ int num_moves;
+ float distance = 0.0;
+ int k;
+ int xpos;
+ int savemove = NO_MOVE;
+ int savecode = 0;
+#if 0
+ int found_read_result;
+#endif
+ Read_result *read_result = NULL;
+
+ SETUP_TRACE_INFO("recursive_break", str);
+
+ if (move)
+ *move = NO_MOVE;
+
+ nodes_connect++;
+ global_connection_node_counter++;
+
+ if (board[str] == EMPTY) {
+ SGFTRACE(PASS_MOVE, 0, "one string already captured");
+ return 0;
+ }
+
+ if (nodes_connect > break_in_node_limit) {
+ SGFTRACE(PASS_MOVE, 0, "connection node limit reached");
+ return 0;
+ }
+
+ if (stackp > break_in_depth) {
+ SGFTRACE(PASS_MOVE, 0, "connection depth limit reached");
+ return 0;
+ }
+
+#if 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_RESULT2(*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);
+ }
+ }
+#endif
+
+#if 0
+ if (trivial_connection(str1, str2, &xpos) == WIN) {
+ SGFTRACE2(xpos, WIN, "trivial connection");
+ READ_RETURN_CONN(read_result, move, xpos, WIN);
+ }
+#endif
+
+ num_moves = find_break_moves(str, goal, 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_break", str,
+ komaster, kom_pos, &new_komaster, &new_kom_pos,
+ &ko_move, stackp <= ko_depth && savecode == 0)) {
+ if (!ko_move) {
+ int acode = recursive_block(str, goal, NULL,
+ new_komaster, new_kom_pos,
+ has_passed);
+ popgo();
+ if (acode == 0) {
+ SGFTRACE(xpos, WIN, "break 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_block(str, goal, NULL, new_komaster, new_kom_pos,
+ has_passed) != WIN) {
+ savemove = xpos;
+ savecode = KO_B;
+ }
+ popgo();
+ }
+ }
+ }
+
+ if (num_moves == 0 && distance < 1.0) {
+ SGFTRACE(NO_MOVE, WIN, "no move, probably connected");
+ READ_RETURN(read_result, move, NO_MOVE, WIN);
+ }
+
+ if (savecode != 0) {
+ SGFTRACE(savemove, savecode, "saved move");
+ READ_RETURN(read_result, move, savemove, savecode);
+ }
+
+ SGFTRACE(0, 0, NULL);
+ READ_RETURN(read_result, move, NO_MOVE, 0);
+}
+
+
+static int
+recursive_block(int str, char goal[BOARDMAX], int *move,
+ int komaster, int kom_pos, int has_passed)
+{
+ int color = board[str];
+ 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;
+#if 0
+ int found_read_result;
+#endif
+ Read_result *read_result = NULL;
+ SETUP_TRACE_INFO("recursive_block", str);
+
+ nodes_connect++;
+ global_connection_node_counter++;
+
+ if (move)
+ *move = NO_MOVE;
+
+ if (board[str] == EMPTY) {
+ SGFTRACE(PASS_MOVE, WIN, "string already captured");
+ return WIN;
+ }
+
+#if 0
+ if (same_string(str1, str2)) {
+ SGFTRACE(PASS_MOVE, 0, "already connected");
+ return 0;
+ }
+#endif
+
+ if (nodes_connect > break_in_node_limit) {
+ SGFTRACE(PASS_MOVE, WIN, "connection node limit reached");
+ return WIN;
+ }
+
+ if (stackp > break_in_depth) {
+ SGFTRACE(PASS_MOVE, WIN, "connection depth limit reached");
+ return WIN;
+ }
+
+#if 0
+ 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_RESULT2(*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);
+ }
+ }
+#endif
+
+ if (ladder_capture(str, &xpos) == WIN) {
+ SGFTRACE(xpos, WIN, "string capturable");
+ READ_RETURN(read_result, move, xpos, WIN);
+ }
+
+ num_moves = find_break_moves(str, goal, 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_block", str,
+ komaster, kom_pos, &new_komaster, &new_kom_pos,
+ &ko_move, stackp <= ko_depth && savecode == 0)) {
+ if (!ko_move) {
+ int dcode = recursive_break(str, goal, NULL,
+ new_komaster, new_kom_pos, has_passed);
+ popgo();
+ if (dcode == 0) {
+ SGFTRACE(xpos, WIN, "block 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_break(str, goal, 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_break(str, goal, NULL, komaster, kom_pos, 1))) {
+ SGFTRACE(NO_MOVE, WIN, "no move, probably disconnected");
+ READ_RETURN(read_result, move, NO_MOVE, WIN);
+ }
+
+ if (savecode != 0) {
+ SGFTRACE(savemove, savecode, "saved move");
+ READ_RETURN(read_result, move, savemove, savecode);
+ }
+
+ SGFTRACE(0, 0, NULL);
+ READ_RETURN(read_result, move, NO_MOVE, 0);
+}
+
+
+int
+break_in(int str, char goal [BOARDMAX], int *move)
+{
+ int dummy_move;
+ int save_verbose;
+ int result;
+ int reading_nodes_when_called = get_reading_node_counter();
+ double start = 0;
+ int tactical_nodes;
+
+ break_in_node_limit = connection_node_limit / 5;
+ break_in_depth = connect_depth2 - 5;
+
+ if (move == NULL)
+ move = &dummy_move;
+
+ nodes_connect = 0;
+ *move = PASS_MOVE;
+
+ if (board[str] == EMPTY)
+ return 0;
+ str = find_origin(str);
+
+ save_verbose = verbose;
+ if (verbose > 0)
+ verbose--;
+ start = gg_cputime();
+ memset(connection_shadow, 0, sizeof(connection_shadow));
+ result = recursive_break(str, goal, move, EMPTY, NO_MOVE, 0);
+ verbose = save_verbose;
+ tactical_nodes = get_reading_node_counter() - reading_nodes_when_called;
+ if (0) {
+ gprintf("%obreak_in %1M, result %d %1M (%d, %d nodes, %f seconds)\n",
+ str, result, *move,
+ nodes_connect, tactical_nodes, gg_cputime() - start);
+ dump_stack();
+ }
+ if (0) {
+ gprintf("%obreak_in %1m %d %1m ", str, result, *move);
+ dump_stack();
+ goaldump(goal);
+ }
+
+ return result;
+}
+
+
+int
+block_off(int str, char goal[BOARDMAX], int *move)
+{
+ int dummy_move;
+ int result;
+ int save_verbose;
+ int reading_nodes_when_called = get_reading_node_counter();
+ double start = 0;
+ int tactical_nodes;
+
+ if (move == NULL)
+ move = &dummy_move;
+
+ nodes_connect = 0;
+ *move = PASS_MOVE;
+
+ str = find_origin(str);
+
+ save_verbose = verbose;
+ if (verbose > 0)
+ verbose--;
+ start = gg_cputime();
+ memset(connection_shadow, 0, sizeof(connection_shadow));
+ result = recursive_block(str, goal, move, EMPTY, NO_MOVE, 0);
+ verbose = save_verbose;
+ tactical_nodes = get_reading_node_counter() - reading_nodes_when_called;
+
+#if 0
+ if (0) {
+ gprintf("%odisconnect %1m %1m, result %d %1m (%d, %d nodes, %f seconds)\n",
+ str1, str2, result, *move,
+ nodes_connect, tactical_nodes, gg_cputime() - start);
+ dump_stack();
+ }
+ if (0) {
+ gprintf("%odisconnect %1m %1m %d %1m ", str1, str2, result, *move);
+ dump_stack();
+ }
+#endif
+
+ return result;
+}
+
+
/* Helper macro for the function below. */
#define ENQUEUE(conn, from, pos, dist, delta, v1, v2) \
@@ -2607,7 +3064,7 @@ find_connection_moves(int str1, int str2
* below.
*/
-static void
+void
spread_connection_distances(int color, int target,
struct connection_data *conn,
float cutoff_distance, int speculative)
@@ -3118,8 +3575,9 @@ clear_connection_data(struct connection_
/* Compute the connection distances from string (str) to nearby
* vertices, until we reach target or the distance gets too high.
*/
-static void
-compute_connection_distances(int str, int target, struct connection_data *conn)
+void
+compute_connection_distances(int str, int target, float cutoff,
+ struct connection_data *conn)
{
int color = board[str];
@@ -3139,8 +3597,9 @@ compute_connection_distances(int str, in
conn->vulnerable2[stones[k]] = NO_MOVE;
}
}
- spread_connection_distances(color, target, conn, 3.0501, 1);
+ spread_connection_distances(color, target, conn, cutoff, 1);
}
+
/* Print the connection distances in a struct connection_data. */
Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.93
diff -u -p -r1.93 value_moves.c
--- engine/value_moves.c 19 May 2003 16:11:16 -0000 1.93
+++ engine/value_moves.c 25 May 2003 22:22:37 -0000
@@ -1940,17 +1940,21 @@ estimate_territorial_value(int pos, int
}
/* tm added move_safety check (3.1.22) (see trevorc:880) */
- if (does_block && move[pos].move_safety
+ if (does_block
+#if 0
+ && move[pos].move_safety
+#endif
&& tryko(pos, color, "estimate_territorial_value", EMPTY, NO_MOVE)) {
if (!retrieve_delta_territory_cache(pos, color, &this_value,
&move[pos].influence_followup_value,
OPPOSITE_INFLUENCE(color))) {
compute_influence(OTHER_COLOR(color), safe_stones, strength,
&move_influence, pos, "after move");
- compute_followup_influence(&move_influence, &followup_influence,
- pos, "followup");
+ break_territories(OTHER_COLOR(color), &move_influence, 0);
this_value = influence_delta_territory(OPPOSITE_INFLUENCE(color),
&move_influence, color, pos);
+ compute_followup_influence(&move_influence, &followup_influence,
+ pos, "followup");
if (this_value != 0.0)
TRACE("%1m: %f - change in territory\n", pos, this_value);
else
Index: interface/main.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/main.c,v
retrieving revision 1.70
diff -u -p -r1.70 main.c
--- interface/main.c 1 May 2003 20:55:26 -0000 1.70
+++ interface/main.c 25 May 2003 22:22:38 -0000
@@ -92,6 +92,7 @@ enum {OPT_BOARDSIZE=127,
OPT_EXPERIMENTAL_CONNECTIONS,
OPT_EXPERIMENTAL_INFLUENCE,
OPT_ALTERNATE_CONNECTIONS,
+ OPT_EXPERIMENTAL_BREAK_IN,
OPT_OPTIONS,
OPT_STANDARD_SEMEAI,
OPT_STANDARD_CONNECTIONS,
@@ -226,6 +227,7 @@ static struct gg_option const long_optio
{"standard-connections", no_argument, 0, OPT_STANDARD_CONNECTIONS},
{"standard-semeai", no_argument, 0, OPT_STANDARD_SEMEAI},
{"alternate-connections", no_argument, 0, OPT_ALTERNATE_CONNECTIONS},
+ {"experimental-break-in", no_argument, 0, OPT_EXPERIMENTAL_BREAK_IN},
{"options", no_argument, 0, OPT_OPTIONS},
{"allow-suicide", no_argument, 0, OPT_ALLOW_SUICIDE},
{"capture-all-dead", no_argument, 0, OPT_CAPTURE_ALL_DEAD},
@@ -546,6 +548,10 @@ main(int argc, char *argv[])
case OPT_ALTERNATE_CONNECTIONS:
alternate_connections = !alternate_connections;
+ break;
+
+ case OPT_EXPERIMENTAL_BREAK_IN:
+ experimental_break_in = 1;
break;
case OPT_ALLOW_SUICIDE:
Index: interface/play_gtp.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_gtp.c,v
retrieving revision 1.117
diff -u -p -r1.117 play_gtp.c
--- interface/play_gtp.c 4 May 2003 11:20:00 -0000 1.117
+++ interface/play_gtp.c 25 May 2003 22:22:41 -0000
@@ -57,6 +57,8 @@ DECLARE(gtp_all_legal);
DECLARE(gtp_analyze_eyegraph);
DECLARE(gtp_attack);
DECLARE(gtp_attack_either);
+DECLARE(gtp_block_off);
+DECLARE(gtp_break_in);
DECLARE(gtp_clear_board);
DECLARE(gtp_clear_cache);
DECLARE(gtp_combination_attack);
@@ -175,6 +177,8 @@ static struct gtp_command commands[] = {
{"attack", gtp_attack},
{"attack_either", gtp_attack_either},
{"black", gtp_playblack},
+ {"block_off", gtp_block_off},
+ {"break_in", gtp_break_in},
{"boardsize", gtp_set_boardsize},
{"captures", gtp_captures},
{"clear_board", gtp_clear_board},
@@ -1807,6 +1811,102 @@ gtp_disconnect(char *s)
return gtp_finish_response();
}
+
+
+/* Function: Try to break from string into area.
+ * Arguments: vertex, vertices
+ * Fails: invalid vertex, empty vertex.
+ * Returns: result followed by break in point if successful.
+ */
+static int
+gtp_break_in(char *s)
+{
+ int ai, aj;
+ int i, j;
+ char goal[BOARDMAX];
+ int break_move = PASS_MOVE;
+ int result;
+ int n;
+ int k;
+
+ n = gtp_decode_coord(s, &ai, &aj);
+ if (n == 0)
+ return gtp_failure("invalid coordinate");
+
+ memset(goal, 0, BOARDMAX);
+ s += n;
+
+ for (k = 0; k < MAX_BOARD * MAX_BOARD; k++) {
+ n = gtp_decode_coord(s, &i, &j);
+ if (n > 0) {
+ goal[POS(i, j)] = 1;
+ s += n;
+ }
+ else if (sscanf(s, "%*s") != EOF)
+ return gtp_failure("invalid coordinate");
+ else
+ break;
+ }
+
+ if (BOARD(ai, aj) == EMPTY)
+ return gtp_failure("vertex must not be empty");
+
+ result = break_in(POS(ai, aj), goal, &break_move);
+ gtp_start_response(GTP_SUCCESS);
+ gtp_print_code(result);
+ if (result != 0)
+ gtp_mprintf(" %m", I(break_move), J(break_move));
+
+ return gtp_finish_response();
+}
+
+/* Function: Try to block string from area.
+ * Arguments: vertex, vertices
+ * Fails: invalid vertex, empty vertex.
+ * Returns: result followed by block point if successful.
+ */
+static int
+gtp_block_off(char *s)
+{
+ int ai, aj;
+ int i, j;
+ char goal[BOARDMAX];
+ int block_move = PASS_MOVE;
+ int result;
+ int n;
+ int k;
+
+ n = gtp_decode_coord(s, &ai, &aj);
+ if (n == 0)
+ return gtp_failure("invalid coordinate");
+
+ memset(goal, 0, BOARDMAX);
+ s += n;
+
+ for (k = 0; k < MAX_BOARD * MAX_BOARD; k++) {
+ n = gtp_decode_coord(s, &i, &j);
+ if (n > 0) {
+ goal[POS(i, j)] = 1;
+ s += n;
+ }
+ else if (sscanf(s, "%*s") != EOF)
+ return gtp_failure("invalid coordinate");
+ else
+ break;
+ }
+
+ if (BOARD(ai, aj) == EMPTY)
+ return gtp_failure("vertex must not be empty");
+
+ result = block_off(POS(ai, aj), goal, &block_move);
+ gtp_start_response(GTP_SUCCESS);
+ gtp_print_code(result);
+ if (result != 0)
+ gtp_mprintf(" %m", I(block_move), J(block_move));
+
+ return gtp_finish_response();
+}
+
/********