| 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 | |
| 26 | #include <stdio.h> |
| 27 | #include <stdlib.h> |
| 28 | #include <string.h> |
| 29 | |
| 30 | #include "liberty.h" |
| 31 | #include "patterns.h" |
| 32 | |
| 33 | static void compute_effective_worm_sizes(void); |
| 34 | static void do_compute_effective_worm_sizes(int color, |
| 35 | int (*cw)[MAX_CLOSE_WORMS], |
| 36 | int *ncw, int max_distance); |
| 37 | static void compute_unconditional_status(void); |
| 38 | static void find_worm_attacks_and_defenses(void); |
| 39 | static void find_worm_threats(void); |
| 40 | static int find_lunch(int str, int *lunch); |
| 41 | static void change_tactical_point(int str, int move, int code, |
| 42 | int points[MAX_TACTICAL_POINTS], |
| 43 | int codes[MAX_TACTICAL_POINTS]); |
| 44 | static void propagate_worm2(int str); |
| 45 | static int genus(int str); |
| 46 | static void markcomponent(int str, int pos, int mg[BOARDMAX]); |
| 47 | static int examine_cavity(int pos, int *edge); |
| 48 | static void cavity_recurse(int pos, int mx[BOARDMAX], |
| 49 | int *border_color, int *edge, int str); |
| 50 | static void ping_cave(int str, int *result1, int *result2, |
| 51 | int *result3, int *result4); |
| 52 | static void ping_recurse(int pos, int *counter, |
| 53 | int mx[BOARDMAX], |
| 54 | int mr[BOARDMAX], int color); |
| 55 | static int touching(int pos, int color); |
| 56 | static void find_attack_patterns(void); |
| 57 | static void attack_callback(int anchor, int color, |
| 58 | struct pattern *pattern, int ll, void *data); |
| 59 | static void find_defense_patterns(void); |
| 60 | static void defense_callback(int anchor, int color, |
| 61 | struct pattern *pattern, int ll, void *data); |
| 62 | static void build_worms(void); |
| 63 | static void report_worm(int pos); |
| 64 | |
| 65 | /* A worm or string is a maximal connected set of stones of the same color, |
| 66 | * black or white. |
| 67 | * |
| 68 | * Cavities are sets of connected empty vertices. |
| 69 | */ |
| 70 | |
| 71 | |
| 72 | /* make_worms() finds all worms and assembles some data about them. |
| 73 | * |
| 74 | * Each worm is marked with an origin. This is an arbitrarily chosen |
| 75 | * element of the worm, in practice the algorithm puts the origin at |
| 76 | * the first element when they are given the lexicographical order, |
| 77 | * though its location is irrelevant for applications. To see if two |
| 78 | * stones lie in the same worm, compare their origins. |
| 79 | * |
| 80 | * We will use the field dragon[ii].genus to keep track of |
| 81 | * black- or white-bordered cavities (essentially eyes) which are found. |
| 82 | * so this field must be zero'd now. |
| 83 | */ |
| 84 | |
| 85 | void |
| 86 | make_worms(void) |
| 87 | { |
| 88 | int pos; |
| 89 | |
| 90 | /* Build the basic worm data: color, origin, size, liberties. */ |
| 91 | build_worms(); |
| 92 | |
| 93 | /* No point continuing if the board is completely empty. */ |
| 94 | if (stones_on_board(BLACK | WHITE) == 0) |
| 95 | return; |
| 96 | |
| 97 | /* Compute effective sizes of all worms. */ |
| 98 | compute_effective_worm_sizes(); |
| 99 | |
| 100 | /* Look for unconditionally alive and dead worms, and unconditional |
| 101 | * territory. |
| 102 | */ |
| 103 | compute_unconditional_status(); |
| 104 | |
| 105 | find_worm_attacks_and_defenses(); |
| 106 | |
| 107 | gg_assert(stackp == 0); |
| 108 | |
| 109 | /* Count liberties of different orders and initialize cutstone fields. */ |
| 110 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 111 | if (IS_STONE(board[pos]) && is_worm_origin(pos, pos)) { |
| 112 | int lib1, lib2, lib3, lib4; |
| 113 | |
| 114 | ping_cave(pos, &lib1, &lib2, &lib3, &lib4); |
| 115 | ASSERT1(worm[pos].liberties == lib1, pos); |
| 116 | worm[pos].liberties2 = lib2; |
| 117 | worm[pos].liberties3 = lib3; |
| 118 | worm[pos].liberties4 = lib4; |
| 119 | worm[pos].cutstone = 0; |
| 120 | worm[pos].cutstone2 = 0; |
| 121 | propagate_worm(pos); |
| 122 | } |
| 123 | } |
| 124 | |
| 125 | gg_assert(stackp == 0); |
| 126 | |
| 127 | /* |
| 128 | * There are two concepts of cutting stones in the worm array. |
| 129 | * |
| 130 | * worm.cutstone: |
| 131 | * |
| 132 | * A CUTTING STONE is one adjacent to two enemy strings, |
| 133 | * which do not have a liberty in common. The most common |
| 134 | * type of cutting string is in this situation. |
| 135 | * |
| 136 | * XO |
| 137 | * OX |
| 138 | * |
| 139 | * A POTENTIAL CUTTING STONE is adjacent to two enemy |
| 140 | * strings which do share a liberty. For example, X in: |
| 141 | * |
| 142 | * XO |
| 143 | * O. |
| 144 | * |
| 145 | * For cutting strings we set worm[m][n].cutstone=2. For potential |
| 146 | * cutting strings we set worm[m][n].cutstone=1. For other strings, |
| 147 | * worm[m][n].cutstone=0. |
| 148 | * |
| 149 | * worm.cutstone2: |
| 150 | * |
| 151 | * Cutting points are identified by the patterns in the |
| 152 | * connections database. Proper cuts are handled by the fact |
| 153 | * that attacking and defending moves also count as moves |
| 154 | * cutting or connecting the surrounding dragons. |
| 155 | * |
| 156 | * The cutstone field will now be set. The cutstone2 field is set |
| 157 | * later, during find_cuts(), called from make_dragons(). |
| 158 | * |
| 159 | * We maintain both fields because the historically older cutstone |
| 160 | * field is needed to deal with the fact that e.g. in the position |
| 161 | * |
| 162 | * |
| 163 | * OXX.O |
| 164 | * .OOXO |
| 165 | * OXX.O |
| 166 | * |
| 167 | * the X stones are amalgamated into one dragon because neither cut |
| 168 | * works as long as the two O stones are in atari. Therefore we add |
| 169 | * one to the cutstone field for each potential cutting point, |
| 170 | * indicating that these O stones are indeed worth rescuing. |
| 171 | * |
| 172 | * For the time being we use both concepts in parallel. It's |
| 173 | * possible we also need the old concept for correct handling of lunches. |
| 174 | */ |
| 175 | |
| 176 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 177 | int w1 = NO_MOVE; |
| 178 | int w2 = NO_MOVE; |
| 179 | int k; |
| 180 | int pos2; |
| 181 | |
| 182 | /* Only work on each worm once. This is easiest done if we only |
| 183 | * work with the origin of each worm. |
| 184 | */ |
| 185 | if (!IS_STONE(board[pos]) || !is_worm_origin(pos, pos)) |
| 186 | continue; |
| 187 | |
| 188 | /* Try to find two adjacent worms (w1) and (w2) |
| 189 | * of opposite colour from (pos). |
| 190 | */ |
| 191 | for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) { |
| 192 | /* Work only with the opposite color from (pos). */ |
| 193 | if (board[pos2] != OTHER_COLOR(board[pos])) |
| 194 | continue; |
| 195 | |
| 196 | for (k = 0; k < 4; k++) { |
| 197 | if (!ON_BOARD(pos2 + delta[k]) |
| 198 | || worm[pos2 + delta[k]].origin != pos) |
| 199 | continue; |
| 200 | |
| 201 | ASSERT1(board[pos2 + delta[k]] == board[pos], pos); |
| 202 | |
| 203 | /* If we have not already found a worm which meets the criteria, |
| 204 | * store it into (w1), otherwise store it into (w2). |
| 205 | */ |
| 206 | if (w1 == NO_MOVE) |
| 207 | w1 = worm[pos2].origin; |
| 208 | else if (!is_same_worm(pos2, w1)) |
| 209 | w2 = worm[pos2].origin; |
| 210 | } |
| 211 | } |
| 212 | |
| 213 | /* |
| 214 | * We now verify the definition of cutting stones. We have |
| 215 | * verified that the string at (pos) is adjacent to two enemy |
| 216 | * strings at (w1) and (w2). We need to know if these |
| 217 | * strings share a liberty. |
| 218 | */ |
| 219 | |
| 220 | /* Only do this if we really found something. */ |
| 221 | if (w2 != NO_MOVE) { |
| 222 | worm[pos].cutstone = 2; |
| 223 | if (count_common_libs(w1, w2) > 0) |
| 224 | worm[pos].cutstone = 1; |
| 225 | |
| 226 | DEBUG(DEBUG_WORMS, "Worm at %1m has w1 %1m and w2 %1m, cutstone %d\n", |
| 227 | pos, w1, w2, worm[pos].cutstone); |
| 228 | } |
| 229 | } |
| 230 | |
| 231 | gg_assert(stackp == 0); |
| 232 | |
| 233 | /* Set the genus of all worms. */ |
| 234 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 235 | if (IS_STONE(board[pos]) && is_worm_origin(pos, pos)) { |
| 236 | worm[pos].genus = genus(pos); |
| 237 | propagate_worm(pos); |
| 238 | } |
| 239 | } |
| 240 | gg_assert(stackp == 0); |
| 241 | |
| 242 | /* Now we try to improve the values of worm.attack and worm.defend. |
| 243 | * If we find that capturing the string at str also defends the |
| 244 | * string at str2, or attacks it, then we add points of attack and |
| 245 | * defense. We don't add attacking point for strings that can't be |
| 246 | * defended. |
| 247 | */ |
| 248 | { |
| 249 | int color; |
| 250 | int str; |
| 251 | int moves_to_try[BOARDMAX]; |
| 252 | memset(moves_to_try, 0, sizeof(moves_to_try)); |
| 253 | |
| 254 | /* Find which colors to try at what points. */ |
| 255 | for (str = BOARDMIN; str < BOARDMAX; str++) { |
| 256 | if (IS_STONE(board[str]) && is_worm_origin(str, str)) { |
| 257 | color = board[str]; |
| 258 | moves_to_try[worm[str].defense_points[0]] |= color; |
| 259 | moves_to_try[worm[str].attack_points[0]] |= OTHER_COLOR(color); |
| 260 | } |
| 261 | } |
| 262 | |
| 263 | /* Loop over the board and over the colors and try the moves found |
| 264 | * in the previous loop. |
| 265 | */ |
| 266 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 267 | if (!ON_BOARD(pos)) |
| 268 | continue; |
| 269 | |
| 270 | for (color = WHITE; color <= BLACK; color++) { |
| 271 | if (!(moves_to_try[pos] & color)) |
| 272 | continue; |
| 273 | |
| 274 | /* Try to play color at pos and see what it leads to. */ |
| 275 | if (!trymove(pos, color, "make_worms", NO_MOVE)) |
| 276 | continue; |
| 277 | |
| 278 | /* We must read to the same depth that was used in the |
| 279 | * initial determination of worm.attack and worm.defend |
| 280 | * to avoid horizon effects. Since stackp has been |
| 281 | * incremented we must also increment depth values. |
| 282 | */ |
| 283 | |
| 284 | DEBUG(DEBUG_WORMS, "trying %1m\n", pos); |
| 285 | increase_depth_values(); |
| 286 | |
| 287 | /* Now we try to find a group which is saved or attacked as well |
| 288 | * by this move. |
| 289 | */ |
| 290 | for (str = BOARDMIN; str < BOARDMAX; str++) { |
| 291 | if (!IS_STONE(board[str]) |
| 292 | || !is_worm_origin(str, str)) |
| 293 | continue; |
| 294 | |
| 295 | /* If the worm is of the opposite color to the move, |
| 296 | * then we try to defend it. If there was a previous |
| 297 | * attack and defense of it, and there is no defense |
| 298 | * for the attack now... |
| 299 | */ |
| 300 | if (worm[str].color == OTHER_COLOR(color) |
| 301 | && worm[str].attack_codes[0] != 0 |
| 302 | && worm[str].defense_codes[0] != 0) { |
| 303 | int dcode = find_defense(str, NULL); |
| 304 | if (dcode < worm[str].defense_codes[0]) { |
| 305 | int attack_works = 1; |
| 306 | |
| 307 | /* Sometimes find_defense() fails to find a |
| 308 | * defense which has been found by other means. |
| 309 | * Try if the old defense move still works. |
| 310 | * |
| 311 | * However, we first check if the _attack_ still exists, |
| 312 | * because we could, for instance, drive the worm into |
| 313 | * seki with our move. |
| 314 | */ |
| 315 | if (attack(str, NULL) >= worm[str].attack_codes[0]) { |
| 316 | if (worm[str].defense_codes[0] != 0 |
| 317 | && trymove(worm[str].defense_points[0], |
| 318 | OTHER_COLOR(color), "make_worms", 0)) { |
| 319 | int this_dcode = REVERSE_RESULT(attack(str, NULL)); |
| 320 | if (this_dcode > dcode) { |
| 321 | dcode = this_dcode; |
| 322 | if (dcode >= worm[str].defense_codes[0]) |
| 323 | attack_works = 0; |
| 324 | } |
| 325 | popgo(); |
| 326 | } |
| 327 | } |
| 328 | else |
| 329 | attack_works = 0; |
| 330 | |
| 331 | /* ...then add an attack point of that worm at pos. */ |
| 332 | if (attack_works) { |
| 333 | DEBUG(DEBUG_WORMS, |
| 334 | "adding point of attack of %1m at %1m with code %d\n", |
| 335 | str, pos, REVERSE_RESULT(dcode)); |
| 336 | change_attack(str, pos, REVERSE_RESULT(dcode)); |
| 337 | } |
| 338 | } |
| 339 | } |
| 340 | |
| 341 | /* If the worm is of the same color as the move we try to |
| 342 | * attack it. If there previously was an attack on it, but |
| 343 | * there is none now, then add a defense point of str at |
| 344 | * pos. |
| 345 | */ |
| 346 | else if (worm[str].color == color |
| 347 | && worm[str].attack_codes[0] != 0) { |
| 348 | int acode = attack(str, NULL); |
| 349 | if (acode < worm[str].attack_codes[0]) { |
| 350 | int defense_works = 1; |
| 351 | /* Sometimes attack() fails to find an |
| 352 | * attack which has been found by other means. |
| 353 | * Try if the old attack move still works. |
| 354 | */ |
| 355 | if (worm[str].attack_codes[0] != 0 |
| 356 | && trymove(worm[str].attack_points[0], |
| 357 | OTHER_COLOR(color), "make_worms", 0)) { |
| 358 | int this_acode; |
| 359 | if (board[str] == EMPTY) |
| 360 | this_acode = WIN; |
| 361 | else |
| 362 | this_acode = REVERSE_RESULT(find_defense(str, NULL)); |
| 363 | if (this_acode > acode) { |
| 364 | acode = this_acode; |
| 365 | if (acode >= worm[str].attack_codes[0]) |
| 366 | defense_works = 0; |
| 367 | } |
| 368 | popgo(); |
| 369 | } |
| 370 | |
| 371 | /* ...then add an attack point of that worm at pos. */ |
| 372 | if (defense_works) { |
| 373 | DEBUG(DEBUG_WORMS, |
| 374 | "adding point of defense of %1m at %1m with code %d\n", |
| 375 | str, pos, REVERSE_RESULT(acode)); |
| 376 | change_defense(str, pos, REVERSE_RESULT(acode)); |
| 377 | } |
| 378 | } |
| 379 | } |
| 380 | } |
| 381 | decrease_depth_values(); |
| 382 | popgo(); |
| 383 | } |
| 384 | } |
| 385 | } |
| 386 | |
| 387 | gg_assert(stackp == 0); |
| 388 | |
| 389 | /* Sometimes it happens that the tactical reading finds adjacent |
| 390 | * strings which both can be attacked but not defended. (The reason |
| 391 | * seems to be that the attacker tries harder to attack a string, |
| 392 | * than the defender tries to capture it's neighbors.) When this |
| 393 | * happens, the eyes code produces overlapping eye spaces and, still |
| 394 | * worse, all the nondefendable stones actually get amalgamated with |
| 395 | * their allies on the outside. |
| 396 | * |
| 397 | * To solve this we scan through the strings which can't be defended |
| 398 | * and check whether they have a neighbor that can be attacked. In |
| 399 | * this case we set the defense point of the former string to the |
| 400 | * attacking point of the latter. |
| 401 | * |
| 402 | * Please notice that find_defense() will still read this out |
| 403 | * incorrectly, which may lead to some confusion later. |
| 404 | */ |
| 405 | |
| 406 | /* First look for vertical neighbors. */ |
| 407 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 408 | if (IS_STONE(board[pos]) |
| 409 | && IS_STONE(board[SOUTH(pos)]) |
| 410 | && !is_same_worm(pos, SOUTH(pos))) { |
| 411 | if (worm[pos].attack_codes[0] != 0 |
| 412 | && worm[SOUTH(pos)].attack_codes[0] != 0) { |
| 413 | if (worm[pos].defense_codes[0] == 0 |
| 414 | && does_defend(worm[SOUTH(pos)].attack_points[0], pos)) { |
| 415 | /* FIXME: need to check ko relationship here */ |
| 416 | change_defense(pos, worm[SOUTH(pos)].attack_points[0], WIN); |
| 417 | } |
| 418 | if (worm[SOUTH(pos)].defense_codes[0] == 0 |
| 419 | && does_defend(worm[pos].attack_points[0], SOUTH(pos))) { |
| 420 | /* FIXME: need to check ko relationship here */ |
| 421 | change_defense(SOUTH(pos), worm[pos].attack_points[0], WIN); |
| 422 | } |
| 423 | } |
| 424 | } |
| 425 | } |
| 426 | |
| 427 | /* Then look for horizontal neighbors. */ |
| 428 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 429 | if (IS_STONE(board[pos]) |
| 430 | && IS_STONE(board[EAST(pos)]) |
| 431 | && !is_same_worm(pos, EAST(pos))) { |
| 432 | if (worm[pos].attack_codes[0] != 0 |
| 433 | && worm[EAST(pos)].attack_codes[0] != 0) { |
| 434 | if (worm[pos].defense_codes[0] == 0 |
| 435 | && does_defend(worm[EAST(pos)].attack_points[0], pos)) { |
| 436 | /* FIXME: need to check ko relationship here */ |
| 437 | change_defense(pos, worm[EAST(pos)].attack_points[0], WIN); |
| 438 | } |
| 439 | if (worm[EAST(pos)].defense_codes[0] == 0 |
| 440 | && does_defend(worm[pos].attack_points[0], EAST(pos))) { |
| 441 | /* FIXME: need to check ko relationship here */ |
| 442 | change_defense(EAST(pos), worm[pos].attack_points[0], WIN); |
| 443 | } |
| 444 | } |
| 445 | } |
| 446 | } |
| 447 | |
| 448 | gg_assert(stackp == 0); |
| 449 | |
| 450 | /* Find adjacent worms that can be easily captured, aka lunches. */ |
| 451 | |
| 452 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 453 | int lunch; |
| 454 | |
| 455 | if (!IS_STONE(board[pos]) || !is_worm_origin(pos, pos)) |
| 456 | continue; |
| 457 | |
| 458 | if (find_lunch(pos, &lunch) |
| 459 | && (worm[lunch].attack_codes[0] == WIN |
| 460 | || worm[lunch].attack_codes[0] == KO_A)) { |
| 461 | DEBUG(DEBUG_WORMS, "lunch found for %1m at %1m\n", pos, lunch); |
| 462 | worm[pos].lunch = lunch; |
| 463 | } |
| 464 | else |
| 465 | worm[pos].lunch = NO_MOVE; |
| 466 | |
| 467 | propagate_worm(pos); |
| 468 | } |
| 469 | |
| 470 | if (!disable_threat_computation) |
| 471 | find_worm_threats(); |
| 472 | |
| 473 | /* Identify INESSENTIAL strings. |
| 474 | * |
| 475 | * These are defined as surrounded strings which have no life |
| 476 | * potential unless part of their surrounding chain can be captured. |
| 477 | * We give a conservative definition of inessential: |
| 478 | * - the genus must be zero |
| 479 | * - there can no second order liberties |
| 480 | * - there can be no more than two edge liberties |
| 481 | * - if it is removed from the board, the remaining cavity has |
| 482 | * border color the opposite color of the string |
| 483 | * - it contains at most two edge vertices. |
| 484 | * |
| 485 | * If we get serious about identifying seki, we might want to add: |
| 486 | * |
| 487 | * - if it has fewer than 4 liberties it is tactically dead. |
| 488 | * |
| 489 | * The last condition is helpful in excluding strings which are |
| 490 | * alive in seki. |
| 491 | * |
| 492 | * An inessential string can be thought of as residing inside the |
| 493 | * opponent's eye space. |
| 494 | */ |
| 495 | |
| 496 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 497 | if (IS_STONE(board[pos]) |
| 498 | && worm[pos].origin == pos |
| 499 | && worm[pos].genus == 0 |
| 500 | && worm[pos].liberties2 == 0 |
| 501 | && !worm[pos].cutstone |
| 502 | && worm[pos].lunch == NO_MOVE) { |
| 503 | int edge; |
| 504 | int border_color = examine_cavity(pos, &edge); |
| 505 | if (border_color != GRAY && edge < 3) { |
| 506 | DEBUG(DEBUG_WORMS, "Worm %1m identified as inessential.\n", pos); |
| 507 | worm[pos].inessential = 1; |
| 508 | propagate_worm(pos); |
| 509 | } |
| 510 | } |
| 511 | } |
| 512 | } |
| 513 | |
| 514 | |
| 515 | /* |
| 516 | * Clear all worms and initialize the basic data fields: |
| 517 | * color, origin, size, liberties |
| 518 | * This is a substep of make_worms(). |
| 519 | */ |
| 520 | |
| 521 | static void |
| 522 | build_worms() |
| 523 | { |
| 524 | int pos; |
| 525 | |
| 526 | /* Set all worm data fields to 0. */ |
| 527 | memset(worm, 0 , sizeof(worm)); |
| 528 | |
| 529 | /* Initialize the worm data for each worm. */ |
| 530 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) |
| 531 | if (ON_BOARD(pos)) |
| 532 | worm[pos].origin = NO_MOVE; |
| 533 | |
| 534 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 535 | if (!ON_BOARD(pos) || worm[pos].origin != NO_MOVE) |
| 536 | continue; |
| 537 | worm[pos].color = board[pos]; |
| 538 | worm[pos].origin = pos; |
| 539 | worm[pos].inessential = 0; |
| 540 | worm[pos].invincible = 0; |
| 541 | worm[pos].unconditional_status = UNKNOWN; |
| 542 | worm[pos].effective_size = 0.0; |
| 543 | if (IS_STONE(board[pos])) { |
| 544 | worm[pos].liberties = countlib(pos); |
| 545 | worm[pos].size = countstones(pos); |
| 546 | propagate_worm(pos); |
| 547 | } |
| 548 | } |
| 549 | } |
| 550 | |
| 551 | |
| 552 | /* Compute effective size of each worm. |
| 553 | * |
| 554 | * Effective size is the number of stones in a worm plus half the |
| 555 | * number of empty intersections that are at least as close to this |
| 556 | * worm as to any other worm. This is used to estimate the direct |
| 557 | * territorial value of capturing a worm. Intersections that are |
| 558 | * shared are counted with equal fractional values for each worm. |
| 559 | * |
| 560 | * We never count intersections further away than distance 3. |
| 561 | * |
| 562 | * This function is also used to compute arrays with information about |
| 563 | * the distances to worms of both or either color. In the latter case |
| 564 | * we count intersections up to a distance of 5. |
| 565 | */ |
| 566 | |
| 567 | static void |
| 568 | compute_effective_worm_sizes() |
| 569 | { |
| 570 | do_compute_effective_worm_sizes(BLACK | WHITE, close_worms, |
| 571 | number_close_worms, 3); |
| 572 | do_compute_effective_worm_sizes(BLACK, close_black_worms, |
| 573 | number_close_black_worms, 5); |
| 574 | do_compute_effective_worm_sizes(WHITE, close_white_worms, |
| 575 | number_close_white_worms, 5); |
| 576 | } |
| 577 | |
| 578 | static void |
| 579 | do_compute_effective_worm_sizes(int color, int (*cw)[MAX_CLOSE_WORMS], |
| 580 | int *ncw, int max_distance) |
| 581 | { |
| 582 | int pos; |
| 583 | |
| 584 | /* Distance to closest worm, -1 means unassigned, 0 that there is |
| 585 | * a stone at the location, 1 a liberty of a stone, and so on. |
| 586 | */ |
| 587 | int distance[BOARDMAX]; |
| 588 | /* Pointer to the origin of the closest worms. A very large number of |
| 589 | * worms may potentially be equally close, but no more than |
| 590 | * 2*(board_size-1). |
| 591 | */ |
| 592 | static int worms[BOARDMAX][2*(MAX_BOARD-1)]; |
| 593 | int nworms[BOARDMAX]; /* number of equally close worms */ |
| 594 | int found_one; |
| 595 | int dist; /* current distance */ |
| 596 | int k, l; |
| 597 | int r; |
| 598 | |
| 599 | /* Initialize arrays. */ |
| 600 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 601 | if (!ON_BOARD(pos)) |
| 602 | continue; |
| 603 | |
| 604 | for (k = 0; k < 2*(board_size-1); k++) |
| 605 | worms[pos][k] = NO_MOVE; |
| 606 | |
| 607 | nworms[pos] = 0; |
| 608 | |
| 609 | if (board[pos] & color) { |
| 610 | distance[pos] = 0; |
| 611 | worms[pos][0] = worm[pos].origin; |
| 612 | nworms[pos]++; |
| 613 | } |
| 614 | else |
| 615 | distance[pos] = -1; |
| 616 | } |
| 617 | |
| 618 | dist = 0; |
| 619 | found_one = 1; |
| 620 | while (found_one && dist <= max_distance) { |
| 621 | found_one = 0; |
| 622 | dist++; |
| 623 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 624 | if (!ON_BOARD(pos) || distance[pos] != -1) |
| 625 | continue; /* already claimed */ |
| 626 | |
| 627 | for (r = 0; r < 4; r++) { |
| 628 | int pos2 = pos + delta[r]; |
| 629 | |
| 630 | if (ON_BOARD(pos2) && distance[pos2] == dist - 1) { |
| 631 | found_one = 1; |
| 632 | distance[pos] = dist; |
| 633 | for (k = 0; k < nworms[pos2]; k++) { |
| 634 | int already_counted = 0; |
| 635 | for (l = 0; l < nworms[pos]; l++) |
| 636 | if (worms[pos][l] == worms[pos2][k]) { |
| 637 | already_counted = 1; |
| 638 | break; |
| 639 | } |
| 640 | if (!already_counted) { |
| 641 | ASSERT1(nworms[pos] < 2*(board_size-1), pos); |
| 642 | worms[pos][nworms[pos]] = worms[pos2][k]; |
| 643 | nworms[pos]++; |
| 644 | } |
| 645 | } |
| 646 | } |
| 647 | } |
| 648 | } |
| 649 | } |
| 650 | |
| 651 | /* Compute the effective sizes but only when all worms are considered. */ |
| 652 | if (color == (BLACK | WHITE)) { |
| 653 | /* Distribute (fractional) contributions to the worms. */ |
| 654 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 655 | if (!ON_BOARD(pos)) |
| 656 | continue; |
| 657 | |
| 658 | for (k = 0; k < nworms[pos]; k++) { |
| 659 | int w = worms[pos][k]; |
| 660 | if (board[pos] == EMPTY) |
| 661 | worm[w].effective_size += 0.5/nworms[pos]; |
| 662 | else |
| 663 | worm[w].effective_size += 1.0; |
| 664 | } |
| 665 | } |
| 666 | |
| 667 | /* Propagate the effective size values all over the worms. */ |
| 668 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) |
| 669 | if (IS_STONE(board[pos]) && is_worm_origin(pos, pos)) |
| 670 | propagate_worm(pos); |
| 671 | } |
| 672 | |
| 673 | /* Fill in the appropriate close_*_worms (cw) and |
| 674 | * number_close_*_worms (ncw) arrays. |
| 675 | */ |
| 676 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 677 | if (!ON_BOARD(pos)) |
| 678 | continue; |
| 679 | |
| 680 | if (nworms[pos] > MAX_CLOSE_WORMS) |
| 681 | ncw[pos] = 0; |
| 682 | else |
| 683 | ncw[pos] = nworms[pos]; |
| 684 | |
| 685 | for (k = 0; k < ncw[pos]; k++) |
| 686 | cw[pos][k] = worms[pos][k]; |
| 687 | } |
| 688 | } |
| 689 | |
| 690 | /* Identify worms which are unconditionally uncapturable in the |
| 691 | * strongest sense, i.e. even if the opponent is allowed an arbitrary |
| 692 | * number of consecutive moves. Also identify worms which are |
| 693 | * similarly unconditionally dead and empty points which are |
| 694 | * unconditional territory for either player. |
| 695 | */ |
| 696 | static void |
| 697 | compute_unconditional_status() |
| 698 | { |
| 699 | int unconditional_territory[BOARDMAX]; |
| 700 | int pos; |
| 701 | int color; |
| 702 | |
| 703 | for (color = WHITE; color <= BLACK; color++) { |
| 704 | unconditional_life(unconditional_territory, color); |
| 705 | if (get_level() >= 10) |
| 706 | find_unconditionally_meaningless_moves(unconditional_territory, color); |
| 707 | |
| 708 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 709 | if (!ON_BOARD(pos) || !unconditional_territory[pos]) |
| 710 | continue; |
| 711 | |
| 712 | if (board[pos] == color) { |
| 713 | worm[pos].unconditional_status = ALIVE; |
| 714 | if (unconditional_territory[pos] == 1) |
| 715 | worm[pos].invincible = 1; |
| 716 | } |
| 717 | else if (board[pos] == EMPTY) { |
| 718 | if (color == WHITE) |
| 719 | worm[pos].unconditional_status = WHITE_TERRITORY; |
| 720 | else |
| 721 | worm[pos].unconditional_status = BLACK_TERRITORY; |
| 722 | } |
| 723 | else |
| 724 | worm[pos].unconditional_status = DEAD; |
| 725 | } |
| 726 | } |
| 727 | gg_assert(stackp == 0); |
| 728 | } |
| 729 | |
| 730 | /* |
| 731 | * Analyze tactical safety of each worm. |
| 732 | */ |
| 733 | |
| 734 | static void |
| 735 | find_worm_attacks_and_defenses() |
| 736 | { |
| 737 | int str; |
| 738 | int k; |
| 739 | int acode, dcode; |
| 740 | int attack_point; |
| 741 | int defense_point; |
| 742 | static int libs[MAXLIBS]; |
| 743 | int liberties; |
| 744 | int color; |
| 745 | int other; |
| 746 | |
| 747 | /* 1. Start with finding attack points. */ |
| 748 | for (str = BOARDMIN; str < BOARDMAX; str++) { |
| 749 | if (!IS_STONE(board[str]) || !is_worm_origin(str, str)) |
| 750 | continue; |
| 751 | |
| 752 | TRACE("considering attack of %1m\n", str); |
| 753 | /* Initialize all relevant fields at once. */ |
| 754 | for (k = 0; k < MAX_TACTICAL_POINTS; k++) { |
| 755 | worm[str].attack_codes[k] = 0; |
| 756 | worm[str].attack_points[k] = 0; |
| 757 | worm[str].defense_codes[k] = 0; |
| 758 | worm[str].defense_points[k] = 0; |
| 759 | } |
| 760 | propagate_worm(str); |
| 761 | |
| 762 | acode = attack(str, &attack_point); |
| 763 | if (acode != 0) { |
| 764 | DEBUG(DEBUG_WORMS, "worm at %1m can be attacked at %1m\n", |
| 765 | str, attack_point); |
| 766 | change_attack(str, attack_point, acode); |
| 767 | } |
| 768 | } |
| 769 | gg_assert(stackp == 0); |
| 770 | |
| 771 | /* 2. Use pattern matching to find a few more attacks. */ |
| 772 | find_attack_patterns(); |
| 773 | gg_assert(stackp == 0); |
| 774 | |
| 775 | /* 3. Now find defense moves. */ |
| 776 | for (str = BOARDMIN; str < BOARDMAX; str++) { |
| 777 | if (!IS_STONE(board[str]) || !is_worm_origin(str, str)) |
| 778 | continue; |
| 779 | |
| 780 | if (worm[str].attack_codes[0] != 0) { |
| 781 | |
| 782 | TRACE("considering defense of %1m\n", str); |
| 783 | dcode = find_defense(str, &defense_point); |
| 784 | if (dcode != 0) { |
| 785 | TRACE("worm at %1m can be defended at %1m\n", str, defense_point); |
| 786 | if (defense_point != NO_MOVE) |
| 787 | change_defense(str, defense_point, dcode); |
| 788 | } |
| 789 | else { |
| 790 | /* If the point of attack is not adjacent to the worm, |
| 791 | * it is possible that this is an overlooked point of |
| 792 | * defense, so we try and see if it defends. |
| 793 | */ |
| 794 | attack_point = worm[str].attack_points[0]; |
| 795 | if (!liberty_of_string(attack_point, str)) |
| 796 | if (trymove(attack_point, worm[str].color, "make_worms", NO_MOVE)) { |
| 797 | int acode = attack(str, NULL); |
| 798 | if (acode != WIN) { |
| 799 | change_defense(str, attack_point, REVERSE_RESULT(acode)); |
| 800 | TRACE("worm at %1m can be defended at %1m with code %d\n", |
| 801 | str, attack_point, REVERSE_RESULT(acode)); |
| 802 | } |
| 803 | popgo(); |
| 804 | } |
| 805 | } |
| 806 | } |
| 807 | } |
| 808 | gg_assert(stackp == 0); |
| 809 | |
| 810 | /* 4. Use pattern matching to find a few more defense moves. */ |
| 811 | find_defense_patterns(); |
| 812 | gg_assert(stackp == 0); |
| 813 | |
| 814 | /* |
| 815 | * 5. Find additional attacks and defenses by testing all immediate |
| 816 | * liberties. Further attacks and defenses are found by pattern |
| 817 | * matching and by trying whether each attack or defense point |
| 818 | * attacks or defends other strings. |
| 819 | */ |
| 820 | for (str = BOARDMIN; str < BOARDMAX; str++) { |
| 821 | color = board[str]; |
| 822 | if (!IS_STONE(color) || !is_worm_origin(str, str)) |
| 823 | continue; |
| 824 | |
| 825 | other = OTHER_COLOR(color); |
| 826 | |
| 827 | if (worm[str].attack_codes[0] == 0) |
| 828 | continue; |
| 829 | |
| 830 | /* There is at least one attack on this group. Try the |
| 831 | * liberties. |
| 832 | */ |
| 833 | liberties = findlib(str, MAXLIBS, libs); |
| 834 | |
| 835 | for (k = 0; k < liberties; k++) { |
| 836 | int pos = libs[k]; |
| 837 | if (!attack_move_known(pos, str)) { |
| 838 | /* Try to attack on the liberty. Don't consider |
| 839 | * send-two-return-one moves. |
| 840 | */ |
| 841 | if (!send_two_return_one(pos, other) |
| 842 | && trymove(pos, other, "make_worms", str)) { |
| 843 | if (board[str] == EMPTY || attack(str, NULL)) { |
| 844 | if (board[str] == EMPTY) |
| 845 | dcode = 0; |
| 846 | else |
| 847 | dcode = find_defense(str, NULL); |
| 848 | |
| 849 | if (dcode != WIN) |
| 850 | change_attack(str, pos, REVERSE_RESULT(dcode)); |
| 851 | } |
| 852 | popgo(); |
| 853 | } |
| 854 | } |
| 855 | /* Try to defend at the liberty. */ |
| 856 | if (!defense_move_known(pos, str)) { |
| 857 | if (worm[str].defense_codes[0] != 0) |
| 858 | if (trymove(pos, color, "make_worms", NO_MOVE)) { |
| 859 | acode = attack(str, NULL); |
| 860 | if (acode != WIN) |
| 861 | change_defense(str, pos, REVERSE_RESULT(acode)); |
| 862 | popgo(); |
| 863 | } |
| 864 | } |
| 865 | } |
| 866 | } |
| 867 | gg_assert(stackp == 0); |
| 868 | } |
| 869 | |
| 870 | |
| 871 | /* |
| 872 | * Find moves threatening to attack or save all worms. |
| 873 | */ |
| 874 | |
| 875 | static void |
| 876 | find_worm_threats() |
| 877 | { |
| 878 | int str; |
| 879 | static int libs[MAXLIBS]; |
| 880 | int liberties; |
| 881 | |
| 882 | int k; |
| 883 | int l; |
| 884 | int color; |
| 885 | |
| 886 | for (str = BOARDMIN; str < BOARDMAX; str++) { |
| 887 | color = board[str]; |
| 888 | if (!IS_STONE(color) || !is_worm_origin(str, str)) |
| 889 | continue; |
| 890 | |
| 891 | /* 1. Start with finding attack threats. */ |
| 892 | /* Only try those worms that have no attack. */ |
| 893 | if (worm[str].attack_codes[0] == 0) { |
| 894 | attack_threats(str, MAX_TACTICAL_POINTS, |
| 895 | worm[str].attack_threat_points, |
| 896 | worm[str].attack_threat_codes); |
| 897 | #if 0 |
| 898 | /* Threaten to attack by saving weak neighbors. */ |
| 899 | num_adj = chainlinks(str, adjs); |
| 900 | for (k = 0; k < num_adj; k++) { |
| 901 | if (worm[adjs[k]].attack_codes[0] != 0 |
| 902 | && worm[adjs[k]].defense_codes[0] != 0) |
| 903 | for (r = 0; r < MAX_TACTICAL_POINTS; r++) { |
| 904 | int bb; |
| 905 | |
| 906 | if (worm[adjs[k]].defense_codes[r] == 0) |
| 907 | break; |
| 908 | bb = worm[adjs[k]].defense_points[r]; |
| 909 | if (trymove(bb, other, "threaten attack", str, |
| 910 | EMPTY, NO_MOVE)) { |
| 911 | int acode; |
| 912 | if (board[str] == EMPTY) |
| 913 | acode = WIN; |
| 914 | else |
| 915 | acode = attack(str, NULL); |
| 916 | if (acode != 0) |
| 917 | change_attack_threat(str, bb, acode); |
| 918 | popgo(); |
| 919 | } |
| 920 | } |
| 921 | } |
| 922 | #endif |
| 923 | /* FIXME: Try other moves also (patterns?). */ |
| 924 | } |
| 925 | |
| 926 | /* 2. Continue with finding defense threats. */ |
| 927 | /* Only try those worms that have an attack. */ |
| 928 | if (worm[str].attack_codes[0] != 0 |
| 929 | && worm[str].defense_codes[0] == 0) { |
| 930 | |
| 931 | liberties = findlib(str, MAXLIBS, libs); |
| 932 | |
| 933 | for (k = 0; k < liberties; k++) { |
| 934 | int aa = libs[k]; |
| 935 | |
| 936 | /* Try to threaten on the liberty. */ |
| 937 | if (trymove(aa, color, "threaten defense", NO_MOVE)) { |
| 938 | if (attack(str, NULL) == WIN) { |
| 939 | int dcode = find_defense(str, NULL); |
| 940 | if (dcode != 0) |
| 941 | change_defense_threat(str, aa, dcode); |
| 942 | } |
| 943 | popgo(); |
| 944 | } |
| 945 | |
| 946 | /* Try to threaten on second order liberties. */ |
| 947 | for (l = 0; l < 4; l++) { |
| 948 | int bb = libs[k] + delta[l]; |
| 949 | |
| 950 | if (!ON_BOARD(bb) |
| 951 | || IS_STONE(board[bb]) |
| 952 | || liberty_of_string(bb, str)) |
| 953 | continue; |
| 954 | |
| 955 | if (trymove(bb, color, "threaten defense", str)) { |
| 956 | if (attack(str, NULL) == WIN) { |
| 957 | int dcode = find_defense(str, NULL); |
| 958 | if (dcode != 0) |
| 959 | change_defense_threat(str, bb, dcode); |
| 960 | } |
| 961 | popgo(); |
| 962 | } |
| 963 | } |
| 964 | } |
| 965 | |
| 966 | /* It might be interesting to look for defense threats by |
| 967 | * attacking weak neighbors, similar to threatening attack by |
| 968 | * defending a weak neighbor. However, in this case it seems |
| 969 | * probable that if there is such an attack, it's a real |
| 970 | * defense, not only a threat. |
| 971 | */ |
| 972 | |
| 973 | /* FIXME: Try other moves also (patterns?). */ |
| 974 | } |
| 975 | } |
| 976 | } |
| 977 | |
| 978 | |
| 979 | /* find_lunch(str, &worm) looks for a worm adjoining the |
| 980 | * string at (str) which can be easily captured. Whether or not it can |
| 981 | * be defended doesn't matter. |
| 982 | * |
| 983 | * Returns the location of the string in (*lunch). |
| 984 | */ |
| 985 | |
| 986 | static int |
| 987 | find_lunch(int str, int *lunch) |
| 988 | { |
| 989 | int pos; |
| 990 | int k; |
| 991 | |
| 992 | ASSERT1(IS_STONE(board[str]), str); |
| 993 | ASSERT1(stackp == 0, str); |
| 994 | |
| 995 | *lunch = NO_MOVE; |
| 996 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 997 | if (board[pos] != OTHER_COLOR(board[str])) |
| 998 | continue; |
| 999 | for (k = 0; k < 8; k++) { |
| 1000 | int apos = pos + delta[k]; |
| 1001 | if (ON_BOARD(apos) && is_same_worm(apos, str)) { |
| 1002 | if (worm[pos].attack_codes[0] != 0 && !is_ko_point(pos)) { |
| 1003 | /* |
| 1004 | * If several adjacent lunches are found, we pick the |
| 1005 | * juiciest. First maximize cutstone, then minimize liberties. |
| 1006 | * We can only do this if the worm data is available, |
| 1007 | * i.e. if stackp==0. |
| 1008 | */ |
| 1009 | if (*lunch == NO_MOVE |
| 1010 | || worm[pos].cutstone > worm[*lunch].cutstone |
| 1011 | || (worm[pos].cutstone == worm[*lunch].cutstone |
| 1012 | && worm[pos].liberties < worm[*lunch].liberties)) { |
| 1013 | *lunch = worm[pos].origin; |
| 1014 | } |
| 1015 | } |
| 1016 | break; |
| 1017 | } |
| 1018 | } |
| 1019 | } |
| 1020 | |
| 1021 | if (*lunch != NO_MOVE) |
| 1022 | return 1; |
| 1023 | |
| 1024 | return 0; |
| 1025 | } |
| 1026 | |
| 1027 | |
| 1028 | /* |
| 1029 | * Test whether two worms are the same. Used by autohelpers. |
| 1030 | * Before this function can be called, build_worms must have been run. |
| 1031 | */ |
| 1032 | |
| 1033 | int |
| 1034 | is_same_worm(int w1, int w2) |
| 1035 | { |
| 1036 | return worm[w1].origin == worm[w2].origin; |
| 1037 | } |
| 1038 | |
| 1039 | |
| 1040 | /* |
| 1041 | * Test whether the origin of the worm at (w) is (pos). |
| 1042 | */ |
| 1043 | |
| 1044 | int |
| 1045 | is_worm_origin(int w, int pos) |
| 1046 | { |
| 1047 | return worm[w].origin == pos; |
| 1048 | } |
| 1049 | |
| 1050 | |
| 1051 | /* |
| 1052 | * change_defense(str, move, dcode) is used to add and remove defense |
| 1053 | * points. It can also be used to change the defense code. The meaning |
| 1054 | * of the call is that the string (str) can be defended by (move) with |
| 1055 | * defense code (dcode). If (dcode) is zero, the move is removed from |
| 1056 | * the list of defense moves if it was previously listed. |
| 1057 | */ |
| 1058 | |
| 1059 | void |
| 1060 | change_defense(int str, int move, int dcode) |
| 1061 | { |
| 1062 | str = worm[str].origin; |
| 1063 | change_tactical_point(str, move, dcode, |
| 1064 | worm[str].defense_points, worm[str].defense_codes); |
| 1065 | } |
| 1066 | |
| 1067 | |
| 1068 | /* |
| 1069 | * change_attack(str, move, acode) is used to add and remove attack |
| 1070 | * points. It can also be used to change the attack code. The meaning |
| 1071 | * of the call is that the string (str) can be attacked by (move) with |
| 1072 | * attack code (acode). If (acode) is zero, the move is removed from |
| 1073 | * the list of attack moves if it was previously listed. |
| 1074 | */ |
| 1075 | |
| 1076 | void |
| 1077 | change_attack(int str, int move, int acode) |
| 1078 | { |
| 1079 | str = worm[str].origin; |
| 1080 | DEBUG(DEBUG_WORMS, "change_attack: %1m %1m %d\n", str, move, acode); |
| 1081 | change_tactical_point(str, move, acode, |
| 1082 | worm[str].attack_points, worm[str].attack_codes); |
| 1083 | } |
| 1084 | |
| 1085 | |
| 1086 | /* |
| 1087 | * change_defense_threat(str, move, dcode) is used to add and remove |
| 1088 | * defense threat points. It can also be used to change the defense |
| 1089 | * threat code. The meaning of the call is that the string (str) can |
| 1090 | * threaten to be defended by (move) with defense threat code (dcode). |
| 1091 | * If (dcode) is zero, the move is removed from the list of defense |
| 1092 | * threat moves if it was previously listed. |
| 1093 | */ |
| 1094 | |
| 1095 | void |
| 1096 | change_defense_threat(int str, int move, int dcode) |
| 1097 | { |
| 1098 | str = worm[str].origin; |
| 1099 | change_tactical_point(str, move, dcode, |
| 1100 | worm[str].defense_threat_points, |
| 1101 | worm[str].defense_threat_codes); |
| 1102 | } |
| 1103 | |
| 1104 | |
| 1105 | /* |
| 1106 | * change_attack_threat(str, move, acode) is used to add and remove |
| 1107 | * attack threat points. It can also be used to change the attack |
| 1108 | * threat code. The meaning of the call is that the string (str) can |
| 1109 | * threaten to be attacked by (move) with attack threat code (acode). |
| 1110 | * If (acode) is zero, the move is removed from the list of attack |
| 1111 | * threat moves if it was previously listed. |
| 1112 | */ |
| 1113 | |
| 1114 | void |
| 1115 | change_attack_threat(int str, int move, int acode) |
| 1116 | { |
| 1117 | str = worm[str].origin; |
| 1118 | change_tactical_point(str, move, acode, |
| 1119 | worm[str].attack_threat_points, |
| 1120 | worm[str].attack_threat_codes); |
| 1121 | } |
| 1122 | |
| 1123 | |
| 1124 | /* Check whether (move) is listed as an attack point for (str) and |
| 1125 | * return the attack code. If (move) is not listed, return 0. |
| 1126 | */ |
| 1127 | int |
| 1128 | attack_move_known(int move, int str) |
| 1129 | { |
| 1130 | return movelist_move_known(move, MAX_TACTICAL_POINTS, |
| 1131 | worm[str].attack_points, |
| 1132 | worm[str].attack_codes); |
| 1133 | } |
| 1134 | |
| 1135 | /* Check whether (move) is listed as a defense point for (str) and |
| 1136 | * return the defense code. If (move) is not listed, return 0. |
| 1137 | */ |
| 1138 | int |
| 1139 | defense_move_known(int move, int str) |
| 1140 | { |
| 1141 | return movelist_move_known(move, MAX_TACTICAL_POINTS, |
| 1142 | worm[str].defense_points, |
| 1143 | worm[str].defense_codes); |
| 1144 | } |
| 1145 | |
| 1146 | /* Check whether (move) is listed as an attack threat point for (str) |
| 1147 | * and return the attack threat code. If (move) is not listed, return |
| 1148 | * 0. |
| 1149 | */ |
| 1150 | int |
| 1151 | attack_threat_move_known(int move, int str) |
| 1152 | { |
| 1153 | return movelist_move_known(move, MAX_TACTICAL_POINTS, |
| 1154 | worm[str].attack_threat_points, |
| 1155 | worm[str].attack_threat_codes); |
| 1156 | } |
| 1157 | |
| 1158 | /* Check whether (move) is listed as a defense threat point for (str) |
| 1159 | * and return the defense threat code. If (move) is not listed, return |
| 1160 | * 0. |
| 1161 | */ |
| 1162 | int |
| 1163 | defense_threat_move_known(int move, int str) |
| 1164 | { |
| 1165 | return movelist_move_known(move, MAX_TACTICAL_POINTS, |
| 1166 | worm[str].defense_threat_points, |
| 1167 | worm[str].defense_threat_codes); |
| 1168 | } |
| 1169 | |
| 1170 | |
| 1171 | /* |
| 1172 | * This function does the real work for change_attack(), |
| 1173 | * change_defense(), change_attack_threat(), and |
| 1174 | * change_defense_threat(). |
| 1175 | */ |
| 1176 | |
| 1177 | static void |
| 1178 | change_tactical_point(int str, int move, int code, |
| 1179 | int points[MAX_TACTICAL_POINTS], |
| 1180 | int codes[MAX_TACTICAL_POINTS]) |
| 1181 | { |
| 1182 | ASSERT_ON_BOARD1(str); |
| 1183 | ASSERT1(str == worm[str].origin, str); |
| 1184 | |
| 1185 | movelist_change_point(move, code, MAX_TACTICAL_POINTS, points, codes); |
| 1186 | propagate_worm2(str); |
| 1187 | } |
| 1188 | |
| 1189 | |
| 1190 | /* |
| 1191 | * propagate_worm() takes the worm data at one stone and copies it to |
| 1192 | * the remaining members of the worm. |
| 1193 | * |
| 1194 | * Even though we don't need to copy all the fields, it's probably |
| 1195 | * better to do a structure copy which should compile to a block copy. |
| 1196 | */ |
| 1197 | |
| 1198 | void |
| 1199 | propagate_worm(int pos) |
| 1200 | { |
| 1201 | int k; |
| 1202 | int num_stones; |
| 1203 | int stones[MAX_BOARD * MAX_BOARD]; |
| 1204 | gg_assert(stackp == 0); |
| 1205 | ASSERT1(IS_STONE(board[pos]), pos); |
| 1206 | |
| 1207 | num_stones = findstones(pos, MAX_BOARD * MAX_BOARD, stones); |
| 1208 | for (k = 0; k < num_stones; k++) |
| 1209 | if (stones[k] != pos) |
| 1210 | worm[stones[k]] = worm[pos]; |
| 1211 | } |
| 1212 | |
| 1213 | |
| 1214 | /* |
| 1215 | * propagate_worm2() is a relative to propagate_worm() which can be |
| 1216 | * used when stackp>0 but not for the initial construction of the |
| 1217 | * worms. |
| 1218 | */ |
| 1219 | |
| 1220 | static void |
| 1221 | propagate_worm2(int str) |
| 1222 | { |
| 1223 | int pos; |
| 1224 | ASSERT_ON_BOARD1(str); |
| 1225 | ASSERT1(IS_STONE(worm[str].color), str); |
| 1226 | |
| 1227 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) |
| 1228 | if (board[pos] == board[str] && is_same_worm(pos, str) |
| 1229 | && pos != str) |
| 1230 | worm[pos] = worm[str]; |
| 1231 | } |
| 1232 | |
| 1233 | |
| 1234 | /* Report all known attack, defense, attack threat, and defense threat |
| 1235 | * moves. But limit this to the moves which can be made by (color). |
| 1236 | */ |
| 1237 | void |
| 1238 | worm_reasons(int color) |
| 1239 | { |
| 1240 | int pos; |
| 1241 | int k; |
| 1242 | |
| 1243 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 1244 | if (!ON_BOARD(pos) || board[pos] == EMPTY) |
| 1245 | continue; |
| 1246 | |
| 1247 | if (!is_worm_origin(pos, pos)) |
| 1248 | continue; |
| 1249 | |
| 1250 | if (board[pos] == OTHER_COLOR(color)) { |
| 1251 | for (k = 0; k < MAX_TACTICAL_POINTS; k++) { |
| 1252 | if (worm[pos].attack_codes[k] != 0) |
| 1253 | add_attack_move(worm[pos].attack_points[k], pos, |
| 1254 | worm[pos].attack_codes[k]); |
| 1255 | if (worm[pos].attack_threat_codes[k] != 0) |
| 1256 | add_attack_threat_move(worm[pos].attack_threat_points[k], pos, |
| 1257 | worm[pos].attack_threat_codes[k]); |
| 1258 | } |
| 1259 | } |
| 1260 | |
| 1261 | if (board[pos] == color) { |
| 1262 | for (k = 0; k < MAX_TACTICAL_POINTS; k++) { |
| 1263 | if (worm[pos].defense_codes[k] != 0) |
| 1264 | add_defense_move(worm[pos].defense_points[k], pos, |
| 1265 | worm[pos].defense_codes[k]); |
| 1266 | |
| 1267 | if (worm[pos].defense_threat_codes[k] != 0) |
| 1268 | add_defense_threat_move(worm[pos].defense_threat_points[k], pos, |
| 1269 | worm[pos].defense_threat_codes[k]); |
| 1270 | } |
| 1271 | } |
| 1272 | } |
| 1273 | } |
| 1274 | |
| 1275 | |
| 1276 | /* ping_cave(str, *lib1, ...) is applied when (str) points to a string. |
| 1277 | * It computes the vector (*lib1, *lib2, *lib3, *lib4), |
| 1278 | * where *lib1 is the number of liberties of the string, |
| 1279 | * *lib2 is the number of second order liberties (empty vertices |
| 1280 | * at distance two) and so forth. |
| 1281 | * |
| 1282 | * The definition of liberties of order >1 is adapted to the problem |
| 1283 | * of detecting the shape of the surrounding cavity. In particular |
| 1284 | * we want to be able to see if a group is loosely surrounded. |
| 1285 | * |
| 1286 | * A liberty of order n is an empty space which may be connected |
| 1287 | * to the string by placing n stones of the same color on the board, |
| 1288 | * but no fewer. The path of connection may pass through an intervening group |
| 1289 | * of the same color. The stones placed at distance >1 may not touch a |
| 1290 | * group of the opposite color. At the edge, also diagonal neighbors |
| 1291 | * count as touching. The path may also not pass through a liberty at distance |
| 1292 | * 1 if that liberty is flanked by two stones of the opposing color. This |
| 1293 | * reflects the fact that the O stone is blocked from expansion to the |
| 1294 | * left by the two X stones in the following situation: |
| 1295 | * |
| 1296 | * X. |
| 1297 | * .O |
| 1298 | * X. |
| 1299 | * |
| 1300 | * On the edge, one stone is sufficient to block expansion: |
| 1301 | * |
| 1302 | * X. |
| 1303 | * .O |
| 1304 | * -- |
| 1305 | */ |
| 1306 | |
| 1307 | static void |
| 1308 | ping_cave(int str, int *lib1, int *lib2, int *lib3, int *lib4) |
| 1309 | { |
| 1310 | int pos; |
| 1311 | int k; |
| 1312 | int libs[MAXLIBS]; |
| 1313 | int mrc[BOARDMAX]; |
| 1314 | int mse[BOARDMAX]; |
| 1315 | int color = board[str]; |
| 1316 | int other = OTHER_COLOR(color); |
| 1317 | |
| 1318 | memset(mse, 0, sizeof(mse)); |
| 1319 | |
| 1320 | /* Find and mark the first order liberties. */ |
| 1321 | *lib1 = findlib(str, MAXLIBS, libs); |
| 1322 | for (k = 0; k < *lib1; k++) |
| 1323 | mse[libs[k]] = 1; |
| 1324 | |
| 1325 | /* Reset mse at liberties which are flanked by two stones of the |
| 1326 | * opposite color, or one stone and the edge. |
| 1327 | */ |
| 1328 | |
| 1329 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) |
| 1330 | if (ON_BOARD(pos) |
| 1331 | && mse[pos] |
| 1332 | && ((( !ON_BOARD(SOUTH(pos)) || board[SOUTH(pos)] == other) |
| 1333 | && ( !ON_BOARD(NORTH(pos)) || board[NORTH(pos)] == other)) |
| 1334 | || (( !ON_BOARD(WEST(pos)) || board[WEST(pos)] == other) |
| 1335 | && (!ON_BOARD(EAST(pos)) || board[EAST(pos)] == other)))) |
| 1336 | mse[pos] = 0; |
| 1337 | |
| 1338 | *lib2 = 0; |
| 1339 | memset(mrc, 0, sizeof(mrc)); |
| 1340 | ping_recurse(str, lib2, mse, mrc, color); |
| 1341 | |
| 1342 | *lib3 = 0; |
| 1343 | memset(mrc, 0, sizeof(mrc)); |
| 1344 | ping_recurse(str, lib3, mse, mrc, color); |
| 1345 | |
| 1346 | *lib4 = 0; |
| 1347 | memset(mrc, 0, sizeof(mrc)); |
| 1348 | ping_recurse(str, lib4, mse, mrc, color); |
| 1349 | } |
| 1350 | |
| 1351 | |
| 1352 | /* recursive function called by ping_cave */ |
| 1353 | |
| 1354 | static void |
| 1355 | ping_recurse(int pos, int *counter, |
| 1356 | int mx[BOARDMAX], int mr[BOARDMAX], |
| 1357 | int color) |
| 1358 | { |
| 1359 | int k; |
| 1360 | mr[pos] = 1; |
| 1361 | |
| 1362 | for (k = 0; k < 4; k++) { |
| 1363 | int apos = pos + delta[k]; |
| 1364 | if (board[apos] == EMPTY |
| 1365 | && mx[apos] == 0 |
| 1366 | && mr[apos] == 0 |
| 1367 | && !touching(apos, OTHER_COLOR(color))) { |
| 1368 | (*counter)++; |
| 1369 | mr[apos] = 1; |
| 1370 | mx[apos] = 1; |
| 1371 | } |
| 1372 | } |
| 1373 | |
| 1374 | if (!is_ko_point(pos)) { |
| 1375 | for (k = 0; k < 4; k++) { |
| 1376 | int apos = pos + delta[k]; |
| 1377 | if (ON_BOARD(apos) |
| 1378 | && mr[apos] == 0 |
| 1379 | && (mx[apos] == 1 |
| 1380 | || board[apos] == color)) |
| 1381 | ping_recurse(apos, counter, mx, mr, color); |
| 1382 | } |
| 1383 | } |
| 1384 | } |
| 1385 | |
| 1386 | |
| 1387 | /* touching(pos, color) returns true if the vertex at (pos) is |
| 1388 | * touching any stone of (color). |
| 1389 | */ |
| 1390 | |
| 1391 | static int |
| 1392 | touching(int pos, int color) |
| 1393 | { |
| 1394 | return (board[SOUTH(pos)] == color |
| 1395 | || board[WEST(pos)] == color |
| 1396 | || board[NORTH(pos)] == color |
| 1397 | || board[EAST(pos)] == color); |
| 1398 | } |
| 1399 | |
| 1400 | |
| 1401 | /* The GENUS of a string is the number of connected components of |
| 1402 | * its complement, minus one. It is an approximation to the number of |
| 1403 | * eyes of the string. |
| 1404 | */ |
| 1405 | |
| 1406 | static int |
| 1407 | genus(int str) |
| 1408 | { |
| 1409 | int pos; |
| 1410 | int mg[BOARDMAX]; |
| 1411 | int gen = -1; |
| 1412 | |
| 1413 | memset(mg, 0, sizeof(mg)); |
| 1414 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 1415 | if (ON_BOARD(pos) |
| 1416 | && !mg[pos] |
| 1417 | && (board[pos] == EMPTY || !is_same_worm(pos, str))) { |
| 1418 | markcomponent(str, pos, mg); |
| 1419 | gen++; |
| 1420 | } |
| 1421 | } |
| 1422 | |
| 1423 | return gen; |
| 1424 | } |
| 1425 | |
| 1426 | |
| 1427 | /* This recursive function marks the component at (pos) of |
| 1428 | * the complement of the string with origin (str) |
| 1429 | */ |
| 1430 | |
| 1431 | static void |
| 1432 | markcomponent(int str, int pos, int mg[BOARDMAX]) |
| 1433 | { |
| 1434 | int k; |
| 1435 | mg[pos] = 1; |
| 1436 | for (k = 0; k < 4; k++) { |
| 1437 | int apos = pos + delta[k]; |
| 1438 | if (ON_BOARD(apos) |
| 1439 | && mg[apos] == 0 |
| 1440 | && (board[apos] == EMPTY || !is_same_worm(apos, str))) |
| 1441 | markcomponent(str, apos, mg); |
| 1442 | } |
| 1443 | } |
| 1444 | |
| 1445 | |
| 1446 | /* examine_cavity(pos, *edge), if (pos) is EMPTY, examines the |
| 1447 | * cavity at (m, n) and returns its bordercolor, |
| 1448 | * which can be BLACK, WHITE or GRAY. The edge parameter is set to the |
| 1449 | * number of edge vertices in the cavity. |
| 1450 | * |
| 1451 | * If (pos) is nonempty, it returns the same result, imagining |
| 1452 | * that the string at (pos) is removed. The edge parameter is |
| 1453 | * set to the number of vertices where the cavity meets the |
| 1454 | * edge in a point outside the removed string. |
| 1455 | */ |
| 1456 | |
| 1457 | static int |
| 1458 | examine_cavity(int pos, int *edge) |
| 1459 | { |
| 1460 | int border_color = EMPTY; |
| 1461 | int ml[BOARDMAX]; |
| 1462 | int origin = NO_MOVE; |
| 1463 | |
| 1464 | ASSERT_ON_BOARD1(pos); |
| 1465 | gg_assert(edge != NULL); |
| 1466 | |
| 1467 | memset(ml, 0, sizeof(ml)); |
| 1468 | |
| 1469 | *edge = 0; |
| 1470 | |
| 1471 | if (IS_STONE(board[pos])) |
| 1472 | origin = find_origin(pos); |
| 1473 | |
| 1474 | cavity_recurse(pos, ml, &border_color, edge, origin); |
| 1475 | |
| 1476 | if (border_color != EMPTY) |
| 1477 | return border_color; |
| 1478 | |
| 1479 | /* We should have returned now, unless the board is completely empty. |
| 1480 | * Verify that this is the case and then return GRAY. |
| 1481 | * |
| 1482 | * Notice that the board appears completely empty if there's only a |
| 1483 | * single string and pos points to it. |
| 1484 | */ |
| 1485 | gg_assert(border_color == EMPTY |
| 1486 | && ((pos == NO_MOVE |
| 1487 | && stones_on_board(BLACK | WHITE) == 0) |
| 1488 | || (pos != NO_MOVE |
| 1489 | && stones_on_board(BLACK | WHITE) == countstones(pos)))); |
| 1490 | |
| 1491 | return GRAY; |
| 1492 | } |
| 1493 | |
| 1494 | |
| 1495 | /* helper function for examine_cavity. |
| 1496 | * border_color contains information so far : transitions allowed are |
| 1497 | * EMPTY -> BLACK/WHITE |
| 1498 | * BLACK/WHITE -> BLACK | WHITE |
| 1499 | * |
| 1500 | * mx[pos] is 1 if (pos) has already been visited. |
| 1501 | * |
| 1502 | * if (str) points to the origin of a string, it will be ignored. |
| 1503 | * |
| 1504 | * On (fully-unwound) exit |
| 1505 | * *border_color should be BLACK, WHITE or BLACK | WHITE |
| 1506 | * *edge is the count of edge pieces |
| 1507 | * |
| 1508 | * *border_color should be EMPTY if and only if the board |
| 1509 | * is completely empty or only contains the ignored string. |
| 1510 | */ |
| 1511 | |
| 1512 | static void |
| 1513 | cavity_recurse(int pos, int mx[BOARDMAX], |
| 1514 | int *border_color, int *edge, int str) |
| 1515 | { |
| 1516 | int k; |
| 1517 | ASSERT1(mx[pos] == 0, pos); |
| 1518 | |
| 1519 | mx[pos] = 1; |
| 1520 | |
| 1521 | if (is_edge_vertex(pos) && board[pos] == EMPTY) |
| 1522 | (*edge)++; |
| 1523 | |
| 1524 | /* Loop over the four neighbors. */ |
| 1525 | for (k = 0; k < 4; k++) { |
| 1526 | int apos = pos + delta[k]; |
| 1527 | if (ON_BOARD(apos) && !mx[apos]) { |
| 1528 | int neighbor_empty = 0; |
| 1529 | |
| 1530 | if (board[apos] == EMPTY) |
| 1531 | neighbor_empty = 1; |
| 1532 | else { |
| 1533 | /* Count the neighbor as empty if it is part of the (ai, aj) string. */ |
| 1534 | if (str == find_origin(apos)) |
| 1535 | neighbor_empty = 1; |
| 1536 | else |
| 1537 | neighbor_empty = 0; |
| 1538 | } |
| 1539 | |
| 1540 | if (!neighbor_empty) |
| 1541 | *border_color |= board[apos]; |
| 1542 | else |
| 1543 | cavity_recurse(apos, mx, border_color, edge, str); |
| 1544 | } |
| 1545 | } |
| 1546 | } |
| 1547 | |
| 1548 | |
| 1549 | /* Find attacking moves by pattern matching, for both colors. */ |
| 1550 | static void |
| 1551 | find_attack_patterns(void) |
| 1552 | { |
| 1553 | matchpat(attack_callback, ANCHOR_OTHER, &attpat_db, NULL, NULL); |
| 1554 | } |
| 1555 | |
| 1556 | /* Try to attack every X string in the pattern, whether there is an attack |
| 1557 | * before or not. Only exclude already known attacking moves. |
| 1558 | */ |
| 1559 | static void |
| 1560 | attack_callback(int anchor, int color, struct pattern *pattern, int ll, |
| 1561 | void *data) |
| 1562 | { |
| 1563 | int move; |
| 1564 | int k; |
| 1565 | UNUSED(data); |
| 1566 | |
| 1567 | move = AFFINE_TRANSFORM(pattern->move_offset, ll, anchor); |
| 1568 | |
| 1569 | /* If the pattern has a constraint, call the autohelper to see |
| 1570 | * if the pattern must be rejected. |
| 1571 | */ |
| 1572 | if (pattern->autohelper_flag & HAVE_CONSTRAINT) { |
| 1573 | if (!pattern->autohelper(ll, move, color, 0)) |
| 1574 | return; |
| 1575 | } |
| 1576 | |
| 1577 | /* If the pattern has a helper, call it to see if the pattern must |
| 1578 | * be rejected. |
| 1579 | */ |
| 1580 | if (pattern->helper) { |
| 1581 | if (!pattern->helper(pattern, ll, move, color)) { |
| 1582 | DEBUG(DEBUG_WORMS, |
| 1583 | "Attack pattern %s+%d rejected by helper at %1m\n", |
| 1584 | pattern->name, ll, move); |
| 1585 | return; |
| 1586 | } |
| 1587 | } |
| 1588 | |
| 1589 | /* Loop through pattern elements in search of X strings to attack. */ |
| 1590 | for (k = 0; k < pattern->patlen; ++k) { /* match each point */ |
| 1591 | if (pattern->patn[k].att == ATT_X) { |
| 1592 | /* transform pattern real coordinate */ |
| 1593 | int pos = AFFINE_TRANSFORM(pattern->patn[k].offset, ll, anchor); |
| 1594 | |
| 1595 | int str = worm[pos].origin; |
| 1596 | |
| 1597 | /* A string with 5 liberties or more is considered tactically alive. */ |
| 1598 | if (countlib(str) > 4) |
| 1599 | continue; |
| 1600 | |
| 1601 | if (attack_move_known(move, str)) |
| 1602 | continue; |
| 1603 | |
| 1604 | /* No defenses are known at this time, so defend_code is always 0. */ |
| 1605 | #if 0 |
| 1606 | /* If the string can be attacked but not defended, ignore it. */ |
| 1607 | if (worm[str].attack_codes[0] == WIN && worm[str].defense_codes[0] == 0) |
| 1608 | continue; |
| 1609 | #endif |
| 1610 | |
| 1611 | /* FIXME: Don't attack the same string more than once. |
| 1612 | * Play (move) and see if there is a defense. |
| 1613 | */ |
| 1614 | if (trymove(move, color, "attack_callback", str)) { |
| 1615 | int dcode; |
| 1616 | if (!board[str]) |
| 1617 | dcode = 0; |
| 1618 | else if (!attack(str, NULL)) |
| 1619 | dcode = WIN; |
| 1620 | else |
| 1621 | dcode = find_defense(str, NULL); |
| 1622 | |
| 1623 | popgo(); |
| 1624 | |
| 1625 | /* Do not pick up suboptimal attacks at this time. Since we |
| 1626 | * don't know whether the string can be defended it's quite |
| 1627 | * possible that it only has a ko defense and then we would |
| 1628 | * risk to find an irrelevant move to attack with ko. |
| 1629 | */ |
| 1630 | if (dcode != WIN && REVERSE_RESULT(dcode) >= worm[str].attack_codes[0]) { |
| 1631 | change_attack(str, move, REVERSE_RESULT(dcode)); |
| 1632 | DEBUG(DEBUG_WORMS, |
| 1633 | "Attack pattern %s+%d found attack on %1m at %1m with code %d\n", |
| 1634 | pattern->name, ll, str, move, REVERSE_RESULT(dcode)); |
| 1635 | } |
| 1636 | } |
| 1637 | } |
| 1638 | } |
| 1639 | } |
| 1640 | |
| 1641 | static void |
| 1642 | find_defense_patterns(void) |
| 1643 | { |
| 1644 | matchpat(defense_callback, ANCHOR_COLOR, &defpat_db, NULL, NULL); |
| 1645 | } |
| 1646 | |
| 1647 | static void |
| 1648 | defense_callback(int anchor, int color, struct pattern *pattern, int ll, |
| 1649 | void *data) |
| 1650 | { |
| 1651 | int move; |
| 1652 | int k; |
| 1653 | UNUSED(data); |
| 1654 | |
| 1655 | move = AFFINE_TRANSFORM(pattern->move_offset, ll, anchor); |
| 1656 | |
| 1657 | /* If the pattern has a constraint, call the autohelper to see |
| 1658 | * if the pattern must be rejected. |
| 1659 | */ |
| 1660 | if (pattern->autohelper_flag & HAVE_CONSTRAINT) { |
| 1661 | if (!pattern->autohelper(ll, move, color, 0)) |
| 1662 | return; |
| 1663 | } |
| 1664 | |
| 1665 | /* If the pattern has a helper, call it to see if the pattern must |
| 1666 | * be rejected. |
| 1667 | */ |
| 1668 | if (pattern->helper) { |
| 1669 | if (!pattern->helper(pattern, ll, move, color)) { |
| 1670 | DEBUG(DEBUG_WORMS, |
| 1671 | "Defense pattern %s+%d rejected by helper at %1m\n", |
| 1672 | pattern->name, ll, move); |
| 1673 | return; |
| 1674 | } |
| 1675 | } |
| 1676 | |
| 1677 | /* Loop through pattern elements in search for O strings to defend. */ |
| 1678 | for (k = 0; k < pattern->patlen; ++k) { /* match each point */ |
| 1679 | if (pattern->patn[k].att == ATT_O) { |
| 1680 | /* transform pattern real coordinate */ |
| 1681 | int pos = AFFINE_TRANSFORM(pattern->patn[k].offset, ll, anchor); |
| 1682 | int str = worm[pos].origin; |
| 1683 | |
| 1684 | if (worm[str].attack_codes[0] == 0 |
| 1685 | || defense_move_known(move, str)) |
| 1686 | continue; |
| 1687 | |
| 1688 | /* FIXME: Don't try to defend the same string more than once. |
| 1689 | * FIXME: For all attacks on this string, we should test whether |
| 1690 | * the proposed move happens to refute the attack. |
| 1691 | * Play (move) and see if there is an attack. |
| 1692 | */ |
| 1693 | if (trymove(move, color, "defense_callback", str)) { |
| 1694 | int acode = attack(str, NULL); |
| 1695 | |
| 1696 | popgo(); |
| 1697 | |
| 1698 | if (acode < worm[str].attack_codes[0]) { |
| 1699 | change_defense(str, move, REVERSE_RESULT(acode)); |
| 1700 | DEBUG(DEBUG_WORMS, |
| 1701 | "Defense pattern %s+%d found defense of %1m at %1m with code %d\n", |
| 1702 | pattern->name, ll, str, move, REVERSE_RESULT(acode)); |
| 1703 | } |
| 1704 | } |
| 1705 | } |
| 1706 | } |
| 1707 | } |
| 1708 | |
| 1709 | |
| 1710 | void |
| 1711 | get_lively_stones(int color, signed char safe_stones[BOARDMAX]) |
| 1712 | { |
| 1713 | int pos; |
| 1714 | memset(safe_stones, 0, BOARDMAX * sizeof(*safe_stones)); |
| 1715 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) |
| 1716 | if (IS_STONE(board[pos]) && find_origin(pos) == pos) { |
| 1717 | if ((stackp == 0 && worm[pos].attack_codes[0] == 0) || !attack(pos, NULL) |
| 1718 | || (board[pos] == color |
| 1719 | && ((stackp == 0 && worm[pos].defense_codes[0] != 0) |
| 1720 | || find_defense(pos, NULL)))) |
| 1721 | mark_string(pos, safe_stones, 1); |
| 1722 | } |
| 1723 | } |
| 1724 | |
| 1725 | |
| 1726 | void |
| 1727 | compute_worm_influence() |
| 1728 | { |
| 1729 | signed char safe_stones[BOARDMAX]; |
| 1730 | |
| 1731 | get_lively_stones(BLACK, safe_stones); |
| 1732 | compute_influence(BLACK, safe_stones, NULL, &initial_black_influence, |
| 1733 | NO_MOVE, "initial black influence"); |
| 1734 | get_lively_stones(WHITE, safe_stones); |
| 1735 | compute_influence(WHITE, safe_stones, NULL, &initial_white_influence, |
| 1736 | NO_MOVE, "initial white influence"); |
| 1737 | } |
| 1738 | |
| 1739 | /* ================================================================ */ |
| 1740 | /* Debugger functions */ |
| 1741 | /* ================================================================ */ |
| 1742 | |
| 1743 | /* For use in gdb, print details of the worm at (m, n). |
| 1744 | * Add this to your .gdbinit file: |
| 1745 | * |
| 1746 | * define worm |
| 1747 | * set ascii_report_worm("$arg0") |
| 1748 | * end |
| 1749 | * |
| 1750 | * Now 'worm S8' will report the details of the S8 worm. |
| 1751 | * |
| 1752 | */ |
| 1753 | |
| 1754 | void |
| 1755 | ascii_report_worm(char *string) |
| 1756 | { |
| 1757 | int pos = string_to_location(board_size, string); |
| 1758 | report_worm(pos); |
| 1759 | } |
| 1760 | |
| 1761 | |
| 1762 | static void |
| 1763 | report_worm(int pos) |
| 1764 | { |
| 1765 | int i; |
| 1766 | |
| 1767 | if (board[pos] == EMPTY) { |
| 1768 | gprintf("There is no worm at %1m\n", pos); |
| 1769 | return; |
| 1770 | } |
| 1771 | |
| 1772 | gprintf("*** worm at %1m:\n", pos); |
| 1773 | gprintf("color: %s; origin: %1m; size: %d; effective size: %f\n", |
| 1774 | (worm[pos].color == WHITE) ? "White" : "Black", |
| 1775 | worm[pos].origin, worm[pos].size, worm[pos].effective_size); |
| 1776 | |
| 1777 | gprintf("liberties: %d order 2 liberties:%d order 3:%d order 4:%d\n", |
| 1778 | worm[pos].liberties, |
| 1779 | worm[pos].liberties2, |
| 1780 | worm[pos].liberties3, |
| 1781 | worm[pos].liberties4); |
| 1782 | |
| 1783 | /* List all attack points. */ |
| 1784 | if (worm[pos].attack_points[0] == NO_MOVE) |
| 1785 | gprintf("no attack point, "); |
| 1786 | else { |
| 1787 | gprintf("attack point(s):"); |
| 1788 | i = 0; |
| 1789 | while (worm[pos].attack_points[i] != NO_MOVE) { |
| 1790 | if (i > 0) |
| 1791 | gprintf(","); |
| 1792 | gprintf(" %1m: %s", worm[pos].attack_points[i], |
| 1793 | result_to_string(worm[pos].attack_codes[i])); |
| 1794 | i++; |
| 1795 | } |
| 1796 | gprintf("\n;"); |
| 1797 | } |
| 1798 | |
| 1799 | /* List all defense points. */ |
| 1800 | if (worm[pos].defense_points[0] == NO_MOVE) |
| 1801 | gprintf("no defense point, "); |
| 1802 | else { |
| 1803 | gprintf("defense point(s):"); |
| 1804 | i = 0; |
| 1805 | while (worm[pos].defense_points[i] != NO_MOVE) { |
| 1806 | if (i > 0) |
| 1807 | gprintf(","); |
| 1808 | gprintf(" %1m: %s", worm[pos].defense_points[i], |
| 1809 | result_to_string(worm[pos].defense_codes[i])); |
| 1810 | i++; |
| 1811 | } |
| 1812 | gprintf("\n;"); |
| 1813 | } |
| 1814 | |
| 1815 | /* List all attack threat points. */ |
| 1816 | if (worm[pos].attack_threat_points[0] == NO_MOVE) |
| 1817 | gprintf("no attack threat point, "); |
| 1818 | else { |
| 1819 | gprintf("attack threat point(s):"); |
| 1820 | i = 0; |
| 1821 | while (worm[pos].attack_threat_points[i] != NO_MOVE) { |
| 1822 | if (i > 0) |
| 1823 | gprintf(","); |
| 1824 | gprintf(" %1m: %s", worm[pos].attack_threat_points[i], |
| 1825 | result_to_string(worm[pos].attack_threat_codes[i])); |
| 1826 | i++; |
| 1827 | } |
| 1828 | gprintf("\n;"); |
| 1829 | } |
| 1830 | |
| 1831 | /* List all defense threat points. */ |
| 1832 | if (worm[pos].defense_threat_points[0] == NO_MOVE) |
| 1833 | gprintf("no defense threat point, "); |
| 1834 | else { |
| 1835 | gprintf("defense threat point(s):"); |
| 1836 | i = 0; |
| 1837 | while (worm[pos].defense_threat_points[i] != NO_MOVE) { |
| 1838 | if (i > 0) |
| 1839 | gprintf(","); |
| 1840 | gprintf(" %1m: %s", worm[pos].defense_threat_points[i], |
| 1841 | result_to_string(worm[pos].defense_threat_codes[i])); |
| 1842 | i++; |
| 1843 | } |
| 1844 | gprintf("\n;"); |
| 1845 | } |
| 1846 | |
| 1847 | /* Report lunch if any. */ |
| 1848 | if (worm[pos].lunch != NO_MOVE) |
| 1849 | gprintf("lunch at %1m\n", worm[pos].lunch); |
| 1850 | |
| 1851 | gprintf("cutstone: %d, cutstone2: %d\n", |
| 1852 | worm[pos].cutstone, worm[pos].cutstone2); |
| 1853 | |
| 1854 | gprintf("genus: %d, ", worm[pos].genus); |
| 1855 | |
| 1856 | if (worm[pos].inessential) |
| 1857 | gprintf("inessential: YES, "); |
| 1858 | else |
| 1859 | gprintf("inessential: NO, "); |
| 1860 | |
| 1861 | if (worm[pos].invincible) |
| 1862 | gprintf("invincible: YES, \n"); |
| 1863 | else |
| 1864 | gprintf("invincible: NO, \n"); |
| 1865 | |
| 1866 | gprintf("unconditional status %s\n", |
| 1867 | status_to_string(worm[pos].unconditional_status)); |
| 1868 | } |
| 1869 | |
| 1870 | |
| 1871 | /* |
| 1872 | * Local Variables: |
| 1873 | * tab-width: 8 |
| 1874 | * c-basic-offset: 2 |
| 1875 | * End: |
| 1876 | */ |