| 1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ |
| 2 | * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * |
| 3 | * http://www.gnu.org/software/gnugo/ for more information. * |
| 4 | * * |
| 5 | * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * |
| 6 | * 2008 and 2009 by the Free Software Foundation. * |
| 7 | * * |
| 8 | * This program is free software; you can redistribute it and/or * |
| 9 | * modify it under the terms of the GNU General Public License as * |
| 10 | * published by the Free Software Foundation - version 3 or * |
| 11 | * (at your option) any later version. * |
| 12 | * * |
| 13 | * This program is distributed in the hope that it will be useful, * |
| 14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * |
| 15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * |
| 16 | * GNU General Public License in file COPYING for more details. * |
| 17 | * * |
| 18 | * You should have received a copy of the GNU General Public * |
| 19 | * License along with this program; if not, write to the Free * |
| 20 | * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * |
| 21 | * Boston, MA 02111, USA. * |
| 22 | \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ |
| 23 | |
| 24 | #include "gnugo.h" |
| 25 | #include "liberty.h" |
| 26 | #include "readconnect.h" |
| 27 | |
| 28 | #include <stdio.h> |
| 29 | #include <stdlib.h> |
| 30 | #include <string.h> |
| 31 | |
| 32 | |
| 33 | /* This module looks for break-ins into territories that require |
| 34 | * deeper tactical reading and are thus impossible to detect for the |
| 35 | * influence module. It gets run after the influence module and revises |
| 36 | * its territory valuations. |
| 37 | * |
| 38 | * The procedure is as follows: We look at all big (>= 10) territory regions |
| 39 | * as detected by the influence code. Using the computation of |
| 40 | * connection distances from readconnect.c, we compute all nearby vertices |
| 41 | * of this territory. We look for the closest safe stones belonging to |
| 42 | * the opponent. |
| 43 | * For each such string (str) we call |
| 44 | * - break_in(str, territory) if the opponent is assumed to be next to move, |
| 45 | * or |
| 46 | * - block_off(str, territory) if the territory owner is next. |
| 47 | * If the break in is successful resp. the blocking unsuccessful, we |
| 48 | * shrink the territory, and see whether the opponent can still break in. |
| 49 | * We repeat this until the territory is shrunk so much that the opponent |
| 50 | * can no longer reach it. |
| 51 | */ |
| 52 | |
| 53 | |
| 54 | /* Store possible break-ins in initial position to generate move reasons |
| 55 | * later. |
| 56 | */ |
| 57 | struct break_in_data { |
| 58 | int str; |
| 59 | int move; |
| 60 | }; |
| 61 | |
| 62 | #define MAX_BREAK_INS 50 |
| 63 | static struct break_in_data break_in_list[MAX_BREAK_INS]; |
| 64 | static int num_break_ins; |
| 65 | |
| 66 | |
| 67 | /* Adds all empty intersections that have two goal neighbors to the goal. */ |
| 68 | static void |
| 69 | enlarge_goal(signed char goal[BOARDMAX]) |
| 70 | { |
| 71 | int pos; |
| 72 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 73 | if (board[pos] == EMPTY && !goal[pos]) { |
| 74 | int k; |
| 75 | int goal_neighbors = 0; |
| 76 | for (k = 0; k < 4; k++) |
| 77 | if (board[pos + delta[k]] == EMPTY && goal[pos + delta[k]] == 1) |
| 78 | goal_neighbors++; |
| 79 | if (goal_neighbors >= 2) |
| 80 | goal[pos] = 2; |
| 81 | } |
| 82 | } |
| 83 | } |
| 84 | |
| 85 | |
| 86 | /* The "smaller goal" is the intersection of the goal with what is |
| 87 | * stored in the queue of the connection_data conn. |
| 88 | * Plus we need a couple of extra careful modifications in the case |
| 89 | * of "blocking off", i.e. when color_to_move == owner. |
| 90 | */ |
| 91 | static void |
| 92 | compute_smaller_goal(int owner, int color_to_move, |
| 93 | const struct connection_data *conn, |
| 94 | const signed char goal[BOARDMAX], |
| 95 | signed char smaller_goal[BOARDMAX]) |
| 96 | { |
| 97 | int k, j; |
| 98 | int own_stones_visited[BOARDMAX]; |
| 99 | memset(smaller_goal, 0, BOARDMAX); |
| 100 | for (k = 0; k < conn->queue_end; k++) { |
| 101 | int pos = conn->queue[k]; |
| 102 | int goal_neighbors = 0; |
| 103 | /* If we are trying to block-off, we need to be extra careful: We only |
| 104 | * can block intrusions coming directly from the string in question. |
| 105 | * Therefore, we discard the area if we have traversed more than two |
| 106 | * stones of the color breaking in on the way to the goal. |
| 107 | */ |
| 108 | if (owner == color_to_move) { |
| 109 | int coming_from = conn->coming_from[pos]; |
| 110 | if (coming_from == NO_MOVE) |
| 111 | own_stones_visited[pos] = 0; |
| 112 | else { |
| 113 | own_stones_visited[pos] = own_stones_visited[coming_from]; |
| 114 | /* How many stones have we used to jump from coming_from to pos? |
| 115 | * Use Manhattan metric as a guess. |
| 116 | */ |
| 117 | if (!goal[pos] && board[pos] == OTHER_COLOR(owner)) { |
| 118 | int i; |
| 119 | int stones[MAX_BOARD * MAX_BOARD]; |
| 120 | int num_stones = findstones(pos, MAX_BOARD * MAX_BOARD, stones); |
| 121 | int smallest_distance = 3; |
| 122 | |
| 123 | for (i = 0; i < num_stones; i++) { |
| 124 | int distance = (gg_abs(I(stones[i]) - I(coming_from)) |
| 125 | + gg_abs(J(stones[i]) - J(coming_from))); |
| 126 | |
| 127 | if (distance < smallest_distance) |
| 128 | smallest_distance = distance; |
| 129 | } |
| 130 | |
| 131 | own_stones_visited[pos] += smallest_distance; |
| 132 | } |
| 133 | |
| 134 | if (own_stones_visited[pos] > 2) |
| 135 | continue; |
| 136 | } |
| 137 | } |
| 138 | |
| 139 | if (!goal[pos]) |
| 140 | continue; |
| 141 | |
| 142 | /* We don't want vertices that are at the border of the territory, and |
| 143 | * from which a break-in is unlikely; these often lead to false |
| 144 | * positives. |
| 145 | * So we throw out every vertex that has only one neighbor in the goal, |
| 146 | * or that is on an edge and has only two goal neighbors. |
| 147 | */ |
| 148 | for (j = 0; j < 4; j++) |
| 149 | if (ON_BOARD(pos + delta[j]) |
| 150 | && goal[pos + delta[j]] |
| 151 | && (board[pos] == EMPTY || goal[pos] == OTHER_COLOR(owner))) |
| 152 | goal_neighbors++; |
| 153 | #if 0 |
| 154 | if (goal_neighbors > 2 |
| 155 | || goal_neighbors == 2 && !is_edge_vertex(pos)) |
| 156 | #else |
| 157 | if (goal_neighbors >= 2) |
| 158 | smaller_goal[pos] = 1; |
| 159 | #endif |
| 160 | } |
| 161 | |
| 162 | /* Finally, in the case of blocking off, we only want one connected |
| 163 | * component. |
| 164 | */ |
| 165 | if (owner == color_to_move) { |
| 166 | signed char marked[BOARDMAX]; |
| 167 | int sizes[BOARDMAX / 2]; |
| 168 | signed char mark = 0; |
| 169 | int biggest_region = 1; |
| 170 | memset(marked, 0, BOARDMAX); |
| 171 | for (k = 0; k < conn->queue_end; k++) { |
| 172 | int pos = conn->queue[k]; |
| 173 | if (ON_BOARD(pos) && smaller_goal[pos] && !marked[pos]) { |
| 174 | /* Floodfill the connected component of (pos) in the goal. */ |
| 175 | int queue_start = 0; |
| 176 | int queue_end = 1; |
| 177 | int queue[BOARDMAX]; |
| 178 | mark++; |
| 179 | sizes[(int) mark] = 1; |
| 180 | marked[pos] = mark; |
| 181 | queue[0] = pos; |
| 182 | while (queue_start < queue_end) { |
| 183 | test_gray_border(); |
| 184 | for (j = 0; j < 4; j++) { |
| 185 | int pos2 = queue[queue_start] + delta[j]; |
| 186 | if (!ON_BOARD(pos2)) |
| 187 | continue; |
| 188 | ASSERT1(marked[pos2] == 0 || marked[pos2] == mark, pos2); |
| 189 | if (smaller_goal[pos2] |
| 190 | && !marked[pos2]) { |
| 191 | sizes[(int) mark]++; |
| 192 | marked[pos2] = mark; |
| 193 | queue[queue_end++] = pos2; |
| 194 | } |
| 195 | } |
| 196 | queue_start++; |
| 197 | } |
| 198 | } |
| 199 | } |
| 200 | /* Now selected the biggest connected component. (In case of |
| 201 | * equality, take the first one. |
| 202 | */ |
| 203 | for (k = 1; k <= mark; k++) { |
| 204 | if (sizes[k] > sizes[biggest_region]) |
| 205 | biggest_region = k; |
| 206 | } |
| 207 | memset(smaller_goal, 0, BOARDMAX); |
| 208 | for (k = 0; k < conn->queue_end; k++) { |
| 209 | int pos = conn->queue[k]; |
| 210 | if (marked[pos] == biggest_region) |
| 211 | smaller_goal[pos] = 1; |
| 212 | } |
| 213 | } |
| 214 | } |
| 215 | |
| 216 | |
| 217 | /* Try to intrude from str into goal. If successful, we shrink the goal, |
| 218 | * store the non-territory fields in the non_territory array, and |
| 219 | * try again. |
| 220 | */ |
| 221 | static int |
| 222 | break_in_goal_from_str(int str, signed char goal[BOARDMAX], |
| 223 | int *num_non_territory, int non_territory[BOARDMAX], |
| 224 | int color_to_move, int info_pos) |
| 225 | { |
| 226 | int move = NO_MOVE; |
| 227 | int saved_move = NO_MOVE; |
| 228 | signed char smaller_goal[BOARDMAX]; |
| 229 | struct connection_data conn; |
| 230 | |
| 231 | /* When blocking off, we use a somewhat smaller goal area. */ |
| 232 | if (color_to_move == board[str]) |
| 233 | compute_connection_distances(str, NO_MOVE, FP(3.01), &conn, 1); |
| 234 | else |
| 235 | compute_connection_distances(str, NO_MOVE, FP(2.81), &conn, 1); |
| 236 | |
| 237 | sort_connection_queue_tail(&conn); |
| 238 | expand_connection_queue(&conn); |
| 239 | compute_smaller_goal(OTHER_COLOR(board[str]), color_to_move, |
| 240 | &conn, goal, smaller_goal); |
| 241 | if (0 && (debug & DEBUG_BREAKIN)) |
| 242 | print_connection_distances(&conn); |
| 243 | DEBUG(DEBUG_BREAKIN, "Trying to break in from %1m to:\n", str); |
| 244 | if (debug & DEBUG_BREAKIN) |
| 245 | goaldump(smaller_goal); |
| 246 | while ((color_to_move == board[str] |
| 247 | && break_in(str, smaller_goal, &move)) |
| 248 | || (color_to_move == OTHER_COLOR(board[str]) |
| 249 | && !block_off(str, smaller_goal, NULL))) { |
| 250 | /* Successful break-in/unsuccessful block. Now where exactly can we |
| 251 | * erase territory? This is difficult, and the method here is very |
| 252 | * crude: Wherever we enter the territory when computing the closest |
| 253 | * neighbors of (str). Plus at the location of the break-in move. |
| 254 | * FIXME: This needs improvement. |
| 255 | */ |
| 256 | int k; |
| 257 | int save_num = *num_non_territory; |
| 258 | int affected_size = 0; |
| 259 | int cut_off_distance = FP(3.5); |
| 260 | if (ON_BOARD(move) && goal[move]) { |
| 261 | non_territory[(*num_non_territory)++] = move; |
| 262 | if (info_pos) |
| 263 | DEBUG(DEBUG_TERRITORY | DEBUG_BREAKIN, |
| 264 | "%1m: Erasing territory at %1m -a.\n", info_pos, move); |
| 265 | else |
| 266 | DEBUG(DEBUG_TERRITORY | DEBUG_BREAKIN, |
| 267 | "Erasing territory at %1m -a.\n", move); |
| 268 | } |
| 269 | |
| 270 | for (k = 0; k < conn.queue_end; k++) { |
| 271 | int pos = conn.queue[k]; |
| 272 | if (conn.distances[pos] > cut_off_distance + FP(0.31)) |
| 273 | break; |
| 274 | if (goal[pos] |
| 275 | && (!ON_BOARD(conn.coming_from[pos]) |
| 276 | || !goal[conn.coming_from[pos]])) { |
| 277 | non_territory[(*num_non_territory)++] = pos; |
| 278 | if (info_pos) |
| 279 | DEBUG(DEBUG_TERRITORY | DEBUG_BREAKIN, |
| 280 | "%1m: Erasing territory at %1m -b.\n", info_pos, pos); |
| 281 | else |
| 282 | DEBUG(DEBUG_TERRITORY | DEBUG_BREAKIN, |
| 283 | "Erasing territory at %1m -b.\n", pos); |
| 284 | if (conn.distances[pos] < cut_off_distance) |
| 285 | cut_off_distance = conn.distances[pos]; |
| 286 | } |
| 287 | if (*num_non_territory >= save_num + 4) |
| 288 | break; |
| 289 | } |
| 290 | |
| 291 | /* Shouldn't happen, but it does. */ |
| 292 | if (*num_non_territory == save_num) |
| 293 | break; |
| 294 | |
| 295 | for (k = save_num; k < *num_non_territory; k++) { |
| 296 | int j; |
| 297 | int pos = non_territory[k]; |
| 298 | if (goal[pos]) { |
| 299 | affected_size++; |
| 300 | goal[pos] = 0; |
| 301 | } |
| 302 | for (j = 0; j < 4; j++) |
| 303 | if (ON_BOARD(pos + delta[j]) && goal[pos + delta[j]]) |
| 304 | affected_size++; |
| 305 | /* Don't kill too much territory at a time. */ |
| 306 | if (affected_size >= 5) { |
| 307 | *num_non_territory = k; |
| 308 | break; |
| 309 | } |
| 310 | } |
| 311 | |
| 312 | compute_smaller_goal(OTHER_COLOR(board[str]), color_to_move, |
| 313 | &conn, goal, smaller_goal); |
| 314 | DEBUG(DEBUG_BREAKIN, "Now trying to break to smaller goal:\n", str); |
| 315 | if (debug & DEBUG_BREAKIN) |
| 316 | goaldump(smaller_goal); |
| 317 | |
| 318 | if (saved_move == NO_MOVE) |
| 319 | saved_move = move; |
| 320 | } |
| 321 | return saved_move; |
| 322 | } |
| 323 | |
| 324 | #define MAX_TRIES 10 |
| 325 | |
| 326 | static void |
| 327 | break_in_goal(int color_to_move, int owner, signed char goal[BOARDMAX], |
| 328 | struct influence_data *q, int store, int info_pos) |
| 329 | { |
| 330 | struct connection_data conn; |
| 331 | int k; |
| 332 | int intruder = OTHER_COLOR(owner); |
| 333 | signed char used[BOARDMAX]; |
| 334 | int non_territory[BOARDMAX]; |
| 335 | int num_non_territory = 0; |
| 336 | int candidate_strings[MAX_TRIES]; |
| 337 | int candidates = 0; |
| 338 | int min_distance = FP(5.0); |
| 339 | |
| 340 | DEBUG(DEBUG_BREAKIN, |
| 341 | "Trying to break (%C to move) %C's territory ", color_to_move, owner); |
| 342 | if (debug & DEBUG_BREAKIN) |
| 343 | goaldump(goal); |
| 344 | /* Compute nearby fields of goal. */ |
| 345 | init_connection_data(intruder, goal, NO_MOVE, FP(3.01), &conn, 1); |
| 346 | k = conn.queue_end; |
| 347 | spread_connection_distances(intruder, &conn); |
| 348 | sort_connection_queue_tail(&conn); |
| 349 | if (0 && (debug & DEBUG_BREAKIN)) |
| 350 | print_connection_distances(&conn); |
| 351 | |
| 352 | /* Look for nearby stones. */ |
| 353 | memset(used, 0, BOARDMAX); |
| 354 | for (; k < conn.queue_end; k++) { |
| 355 | int pos = conn.queue[k]; |
| 356 | if (conn.distances[pos] > min_distance + FP(1.001)) |
| 357 | break; |
| 358 | if (board[pos] == intruder |
| 359 | && influence_considered_lively(q, pos)) { |
| 360 | /* Discard this string in case the shortest path goes via a string |
| 361 | * that we have in the candidate list already. |
| 362 | */ |
| 363 | int pos2 = pos; |
| 364 | while (ON_BOARD(pos2)) { |
| 365 | pos2 = conn.coming_from[pos2]; |
| 366 | if (IS_STONE(board[pos2])) |
| 367 | pos2 = find_origin(pos2); |
| 368 | |
| 369 | if (used[pos2]) |
| 370 | break; |
| 371 | } |
| 372 | |
| 373 | used[pos] = 1; |
| 374 | if (ON_BOARD(pos2)) |
| 375 | continue; |
| 376 | if (candidates == 0) |
| 377 | min_distance = conn.distances[pos]; |
| 378 | candidate_strings[candidates++] = pos; |
| 379 | if (candidates == MAX_TRIES) |
| 380 | break; |
| 381 | } |
| 382 | } |
| 383 | |
| 384 | /* Finally, try the break-ins. */ |
| 385 | memset(non_territory, 0, BOARDMAX); |
| 386 | for (k = 0; k < candidates; k++) { |
| 387 | int move = break_in_goal_from_str(candidate_strings[k], goal, |
| 388 | &num_non_territory, non_territory, |
| 389 | color_to_move, info_pos); |
| 390 | if (store && ON_BOARD(move) && num_break_ins < MAX_BREAK_INS) { |
| 391 | /* Remember the move as a possible move candidate for later. */ |
| 392 | break_in_list[num_break_ins].str = candidate_strings[k]; |
| 393 | break_in_list[num_break_ins].move = move; |
| 394 | num_break_ins++; |
| 395 | } |
| 396 | } |
| 397 | |
| 398 | for (k = 0; k < num_non_territory; k++) |
| 399 | influence_erase_territory(q, non_territory[k], owner); |
| 400 | if (0 && num_non_territory > 0 && (debug & DEBUG_BREAKIN)) |
| 401 | showboard(0); |
| 402 | } |
| 403 | |
| 404 | |
| 405 | /* The main function of this module. color_to_move is self-explanatory, |
| 406 | * and the influence_data refers to the influence territory evaluation that |
| 407 | * we are analyzing (and will be correcting). store indicates whether |
| 408 | * the successful break-ins should be stored in the break_in_list[] (which |
| 409 | * later gets used to generate move reasons). |
| 410 | */ |
| 411 | void |
| 412 | break_territories(int color_to_move, struct influence_data *q, int store, |
| 413 | int info_pos) |
| 414 | { |
| 415 | struct moyo_data territories; |
| 416 | int k; |
| 417 | |
| 418 | if (!experimental_break_in || get_level() < 10) |
| 419 | return; |
| 420 | |
| 421 | influence_get_territory_segmentation(q, &territories); |
| 422 | for (k = 1; k <= territories.number; k++) { |
| 423 | signed char goal[BOARDMAX]; |
| 424 | int pos; |
| 425 | int size = 0; |
| 426 | |
| 427 | memset(goal, 0, BOARDMAX); |
| 428 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) |
| 429 | if (ON_BOARD(pos) && territories.segmentation[pos] == k) { |
| 430 | goal[pos] = 1; |
| 431 | if (board[pos] != territories.owner[k]) |
| 432 | size++; |
| 433 | } |
| 434 | if (size < 10) |
| 435 | continue; |
| 436 | |
| 437 | if (color_to_move == OTHER_COLOR(territories.owner[k])) |
| 438 | enlarge_goal(goal); |
| 439 | break_in_goal(color_to_move, territories.owner[k], goal, q, store, |
| 440 | info_pos); |
| 441 | } |
| 442 | } |
| 443 | |
| 444 | void |
| 445 | clear_break_in_list() |
| 446 | { |
| 447 | num_break_ins = 0; |
| 448 | } |
| 449 | |
| 450 | /* The blocking moves should usually already have a move reason. |
| 451 | * |
| 452 | * The EXPAND_TERRITORY move reason ensures a territory evaluation of |
| 453 | * this move, without setting the move.safety field. (I.e. the move will |
| 454 | * be treated as a sacrifice move unless another move reasons tells us |
| 455 | * otherwise.) |
| 456 | */ |
| 457 | void |
| 458 | break_in_move_reasons(int color) |
| 459 | { |
| 460 | int k; |
| 461 | for (k = 0; k < num_break_ins; k++) |
| 462 | if (board[break_in_list[k].str] == color) |
| 463 | add_expand_territory_move(break_in_list[k].move); |
| 464 | } |