| 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 "gg_utils.h" |
| 32 | #include "patterns.h" |
| 33 | #include "dfa.h" |
| 34 | |
| 35 | |
| 36 | /**************************************************************************/ |
| 37 | /* Pattern profiling functions: */ |
| 38 | /**************************************************************************/ |
| 39 | |
| 40 | |
| 41 | #if PROFILE_PATTERNS |
| 42 | /* Initialize pattern profiling fields in one pattern struct array. */ |
| 43 | static void |
| 44 | clear_profile(struct pattern *pattern) |
| 45 | { |
| 46 | for (; pattern->patn; ++pattern) { |
| 47 | pattern->hits = 0; |
| 48 | pattern->reading_nodes = 0; |
| 49 | pattern->dfa_hits = 0; |
| 50 | } |
| 51 | } |
| 52 | #endif |
| 53 | |
| 54 | #if PROFILE_PATTERNS |
| 55 | /* Print profiling information for one pattern struct array. */ |
| 56 | static void |
| 57 | print_profile(struct pattern *pattern, int *total_hits, |
| 58 | int *total_nodes, int *total_dfa_hits) |
| 59 | { |
| 60 | for (; pattern->patn; ++pattern) |
| 61 | if (pattern->hits > 0) { |
| 62 | *total_hits += pattern->hits; |
| 63 | *total_nodes += pattern->reading_nodes; |
| 64 | *total_dfa_hits += pattern->dfa_hits; |
| 65 | fprintf(stderr, "%6d %6d %9d %8.1f %s\n", |
| 66 | pattern->dfa_hits, |
| 67 | pattern->hits, |
| 68 | pattern->reading_nodes, |
| 69 | pattern->reading_nodes / (float) pattern->hits, |
| 70 | pattern->name); |
| 71 | } |
| 72 | } |
| 73 | #endif /* PROFILE_PATTERNS */ |
| 74 | |
| 75 | |
| 76 | /* Initialize pattern profiling fields in pattern struct arrays. */ |
| 77 | void |
| 78 | prepare_pattern_profiling() |
| 79 | { |
| 80 | #if PROFILE_PATTERNS |
| 81 | clear_profile(pat_db.patterns); |
| 82 | clear_profile(attpat_db.patterns); |
| 83 | clear_profile(defpat_db.patterns); |
| 84 | clear_profile(endpat_db.patterns); |
| 85 | clear_profile(conn_db.patterns); |
| 86 | clear_profile(influencepat_db.patterns); |
| 87 | clear_profile(barrierspat_db.patterns); |
| 88 | clear_profile(aa_attackpat_db.patterns); |
| 89 | clear_profile(owl_attackpat_db.patterns); |
| 90 | clear_profile(owl_vital_apat_db.patterns); |
| 91 | clear_profile(owl_defendpat_db.patterns); |
| 92 | clear_profile(fusekipat_db.patterns); |
| 93 | clear_profile(oracle_db.patterns); |
| 94 | #else |
| 95 | fprintf(stderr, |
| 96 | "Warning, no support for pattern profiling in this binary.\n"); |
| 97 | #endif |
| 98 | } |
| 99 | |
| 100 | |
| 101 | /* Report result of pattern profiling. Only patterns with at least one |
| 102 | * match are listed. |
| 103 | */ |
| 104 | void |
| 105 | report_pattern_profiling() |
| 106 | { |
| 107 | #if PROFILE_PATTERNS |
| 108 | int hits = 0; |
| 109 | int dfa_hits = 0; |
| 110 | int nodes = 0; |
| 111 | |
| 112 | print_profile(pat_db.patterns, &hits, &nodes, &dfa_hits); |
| 113 | print_profile(attpat_db.patterns, &hits, &nodes, &dfa_hits); |
| 114 | print_profile(defpat_db.patterns, &hits, &nodes, &dfa_hits); |
| 115 | print_profile(endpat_db.patterns, &hits, &nodes, &dfa_hits); |
| 116 | print_profile(conn_db.patterns, &hits, &nodes, &dfa_hits); |
| 117 | print_profile(influencepat_db.patterns, &hits, &nodes, &dfa_hits); |
| 118 | print_profile(barrierspat_db.patterns, &hits, &nodes, &dfa_hits); |
| 119 | print_profile(aa_attackpat_db.patterns, &hits, &nodes, &dfa_hits); |
| 120 | print_profile(owl_attackpat_db.patterns, &hits, &nodes, &dfa_hits); |
| 121 | print_profile(owl_vital_apat_db.patterns, &hits, &nodes, &dfa_hits); |
| 122 | print_profile(owl_defendpat_db.patterns, &hits, &nodes, &dfa_hits); |
| 123 | print_profile(fusekipat_db.patterns, &hits, &nodes, &dfa_hits); |
| 124 | print_profile(oracle_db.patterns, &hits, &nodes, &dfa_hits); |
| 125 | fprintf(stderr, "------ ---------\n"); |
| 126 | fprintf(stderr, "%6d, %6d %9d\n", dfa_hits, hits, nodes); |
| 127 | #endif |
| 128 | } |
| 129 | |
| 130 | |
| 131 | |
| 132 | /**************************************************************************/ |
| 133 | /* Standard matcher: */ |
| 134 | /**************************************************************************/ |
| 135 | |
| 136 | |
| 137 | /* Forward declarations. */ |
| 138 | |
| 139 | static void fixup_patterns_for_board_size(struct pattern *pattern); |
| 140 | static void prepare_for_match(int color); |
| 141 | static void do_matchpat(int anchor, matchpat_callback_fn_ptr callback, |
| 142 | int color, struct pattern *database, |
| 143 | void *callback_data, signed char goal[BOARDMAX]); |
| 144 | static void matchpat_loop(matchpat_callback_fn_ptr callback, |
| 145 | int color, int anchor, |
| 146 | struct pattern_db *pdb, void *callback_data, |
| 147 | signed char goal[BOARDMAX], int anchor_in_goal); |
| 148 | |
| 149 | /* Precomputed tables to allow rapid checks on the piece at |
| 150 | * the board. This table relies on the fact that color is |
| 151 | * 1 or 2. |
| 152 | * |
| 153 | * For pattern element i, require (board[pos] & andmask[i]) == valmask[i] |
| 154 | * |
| 155 | * .XO) For i=0,1,2, board[pos] & 3 is a no-op, so we check board[pos] |
| 156 | * == valmask |
| 157 | * x) For i=3, we are checking that board[pos] is not color, so AND |
| 158 | * color and we get 0 for either empty or OTHER_COLOR, but color |
| 159 | * if it contains color |
| 160 | * o) Works the other way round for checking it is not X. |
| 161 | * |
| 162 | * |
| 163 | * gcc allows the entries to be computed at run-time, but that is not ANSI. |
| 164 | */ |
| 165 | |
| 166 | static const int and_mask[2][8] = { |
| 167 | /* . X O x o , a ! color */ |
| 168 | { 3, 3, 3, WHITE, BLACK, 3, 3, 3 }, /* BLACK */ |
| 169 | { 3, 3, 3, BLACK, WHITE, 3, 3, 3 } /* WHITE */ |
| 170 | }; |
| 171 | |
| 172 | static const int val_mask[2][8] = { |
| 173 | { EMPTY, BLACK, WHITE, 0, 0, EMPTY, EMPTY, EMPTY}, /* BLACK */ |
| 174 | { EMPTY, WHITE, BLACK, 0, 0, EMPTY, EMPTY, EMPTY} /* WHITE */ |
| 175 | }; |
| 176 | |
| 177 | |
| 178 | /* and a table for checking classes quickly |
| 179 | * class_mask[status][color] contains the mask to look for in class. |
| 180 | * ie. if pat[r].class & class_mask[dragon[pos].status][board[pos]] |
| 181 | * is not zero then we reject it |
| 182 | * Most elements if class_mask[] are zero - it is a sparse |
| 183 | * matrix containing |
| 184 | * CLASS_O in [DEAD][color] |
| 185 | * CLASS_O in [CRITICAL][color] |
| 186 | * CLASS_o in [ALIVE][color] |
| 187 | * CLASS_X in [DEAD][other] |
| 188 | * CLASS_x in [ALIVE][other] |
| 189 | * |
| 190 | * so eg. if we have a dead white dragon, and we |
| 191 | * are checking a pattern for black, then |
| 192 | * class_mask[DEAD][other] will contain CLASS_X |
| 193 | * Then we reject any patterns which have CLASS_X |
| 194 | * set in the class bits. |
| 195 | * |
| 196 | * Making it static guarantees that all fields are |
| 197 | * initially set to 0, and we overwrite the ones |
| 198 | * we care about each time. |
| 199 | */ |
| 200 | |
| 201 | static unsigned int class_mask[NUM_DRAGON_STATUS][3]; |
| 202 | |
| 203 | |
| 204 | /* In the current implementation, the edge constraints depend on |
| 205 | * the board size, because we pad width or height out to the |
| 206 | * board size. (This is because it is easy to find the corners |
| 207 | * of the rotated pattern, but it is harder to transform the |
| 208 | * bitmask of edge constraints.) |
| 209 | * |
| 210 | * But since version 1.103, board size is variable. Thus we |
| 211 | * make a first pass through the table once we know the board |
| 212 | * size. |
| 213 | * |
| 214 | * This should be called once for each pattern database. |
| 215 | */ |
| 216 | |
| 217 | static void |
| 218 | fixup_patterns_for_board_size(struct pattern *pattern) |
| 219 | { |
| 220 | for (; pattern->patn; ++pattern) |
| 221 | if (pattern->edge_constraints != 0) { |
| 222 | |
| 223 | /* If the patterns have been fixed up for a different board size |
| 224 | * earlier, we need to undo the modifications that were done |
| 225 | * below before we do them anew. The first time this function is |
| 226 | * called, this step is effectively a no-op. |
| 227 | */ |
| 228 | |
| 229 | if (pattern->edge_constraints & NORTH_EDGE) |
| 230 | pattern->maxi = pattern->mini + pattern->height; |
| 231 | |
| 232 | if (pattern->edge_constraints & SOUTH_EDGE) |
| 233 | pattern->mini = pattern->maxi - pattern->height; |
| 234 | |
| 235 | if (pattern->edge_constraints & WEST_EDGE) |
| 236 | pattern->maxj = pattern->minj + pattern->width; |
| 237 | |
| 238 | if (pattern->edge_constraints & EAST_EDGE) |
| 239 | pattern->minj = pattern->maxj - pattern->width; |
| 240 | |
| 241 | /* we extend the pattern in the direction opposite the constraint, |
| 242 | * such that maxi (+ve) - mini (-ve) = board_size-1 |
| 243 | * Note : the pattern may be wider than the board, so |
| 244 | * we need to be a bit careful ! |
| 245 | */ |
| 246 | |
| 247 | if (pattern->edge_constraints & NORTH_EDGE) |
| 248 | if (pattern->maxi < (board_size-1) + pattern->mini) |
| 249 | pattern->maxi = (board_size-1) + pattern->mini; |
| 250 | |
| 251 | if (pattern->edge_constraints & SOUTH_EDGE) |
| 252 | if (pattern->mini > pattern->maxi - (board_size-1)) |
| 253 | pattern->mini = pattern->maxi - (board_size-1); |
| 254 | |
| 255 | if (pattern->edge_constraints & WEST_EDGE) |
| 256 | if (pattern->maxj < (board_size-1) + pattern->minj) |
| 257 | pattern->maxj = (board_size-1) + pattern->minj; |
| 258 | |
| 259 | if (pattern->edge_constraints & EAST_EDGE) |
| 260 | if (pattern->minj > pattern->maxj - (board_size-1)) |
| 261 | pattern->minj = pattern->maxj - (board_size-1); |
| 262 | } |
| 263 | } |
| 264 | |
| 265 | |
| 266 | /* |
| 267 | * prepare a pattern matching for color point of view |
| 268 | */ |
| 269 | static void |
| 270 | prepare_for_match(int color) |
| 271 | { |
| 272 | int other = OTHER_COLOR(color); |
| 273 | |
| 274 | /* Basic sanity checks. */ |
| 275 | gg_assert(color != EMPTY); |
| 276 | |
| 277 | /* If we set one of class_mask[XXX][color] and |
| 278 | * class_mask[XXX][other], we have to explicitly set or reset the |
| 279 | * other as well, since 'color' may change between calls. |
| 280 | */ |
| 281 | class_mask[DEAD][color] = CLASS_O; |
| 282 | class_mask[DEAD][other] = CLASS_X; |
| 283 | class_mask[CRITICAL][color] = CLASS_O; |
| 284 | class_mask[CRITICAL][other] = 0; /* Need to reset this. */ |
| 285 | class_mask[ALIVE][color] = CLASS_o; |
| 286 | class_mask[ALIVE][other] = CLASS_x; |
| 287 | } |
| 288 | |
| 289 | |
| 290 | /* |
| 291 | * Try all the patterns in the given array at (anchor). Invoke the |
| 292 | * callback for any that matches. Classes X,O,x,o are checked here. It |
| 293 | * is up to the callback to process the other classes, and any helper |
| 294 | * or autohelper functions. |
| 295 | * |
| 296 | * If the support of goal[BOARDMAX] is a subset of the board, patterns |
| 297 | * are rejected which do not involve this dragon. If goal is a null |
| 298 | * pointer, this parameter is ignored. |
| 299 | */ |
| 300 | |
| 301 | static void |
| 302 | do_matchpat(int anchor, matchpat_callback_fn_ptr callback, int color, |
| 303 | struct pattern *pattern, void *callback_data, |
| 304 | signed char goal[BOARDMAX]) |
| 305 | { |
| 306 | const int anchor_test = board[anchor] ^ color; /* see below */ |
| 307 | int m = I(anchor); |
| 308 | int n = J(anchor); |
| 309 | int merged_val; |
| 310 | |
| 311 | /* Basic sanity checks. */ |
| 312 | ASSERT_ON_BOARD1(anchor); |
| 313 | |
| 314 | /* calculate the merged value around [m][n] for the grid opt */ |
| 315 | { |
| 316 | /* FIXME: Convert this to 2D (using delta[]) but be aware that you'll |
| 317 | * also need to make corresponding changes in mkpat.c! |
| 318 | */ |
| 319 | int i, j; |
| 320 | int shift = 30; |
| 321 | |
| 322 | merged_val = 0; |
| 323 | for (i = m-1; i <= m+2; ++i) |
| 324 | for (j = n-1; j <= n+2; shift -= 2, ++j) { |
| 325 | unsigned int this; |
| 326 | if (!ON_BOARD2(i, j)) |
| 327 | this = 3; |
| 328 | else if ((this = BOARD(i, j)) == 0) |
| 329 | continue; |
| 330 | else if (color == 2) |
| 331 | this = OTHER_COLOR(this); |
| 332 | merged_val |= (this << shift); |
| 333 | } |
| 334 | } |
| 335 | |
| 336 | /* Try each pattern - NULL pattern marks end of list. Assume at least 1 */ |
| 337 | gg_assert(pattern->patn); |
| 338 | |
| 339 | do { |
| 340 | /* |
| 341 | * These days we always match all patterns. |
| 342 | */ |
| 343 | { |
| 344 | int end_transformation; |
| 345 | int ll; /* Iterate over transformations (rotations or reflections) */ |
| 346 | int k; /* Iterate over elements of pattern */ |
| 347 | int found_goal; |
| 348 | |
| 349 | /* We can check the color of the anchor stone now. |
| 350 | * Roughly half the patterns are anchored at each |
| 351 | * color, and since the anchor stone is invariant under |
| 352 | * rotation, we can reject all rotations of a wrongly-anchored |
| 353 | * pattern in one go. |
| 354 | * |
| 355 | * Patterns are always drawn from O perspective in .db, |
| 356 | * so board[pos] is 'color' if the pattern is anchored |
| 357 | * at O, or 'other' for X. |
| 358 | * Since we require that this flag contains 3 for |
| 359 | * anchored_at_X, we can check that |
| 360 | * board[pos] == (color ^ anchored_at_X) |
| 361 | * which is equivalent to |
| 362 | * (board[pos] ^ color) == anchored_at_X) |
| 363 | * and the LHS is something we precomputed. |
| 364 | */ |
| 365 | |
| 366 | if (anchor_test != pattern->anchored_at_X) |
| 367 | continue; /* does not match the anchor */ |
| 368 | |
| 369 | ll = 0; /* first transformation number */ |
| 370 | end_transformation = pattern->trfno; |
| 371 | |
| 372 | /* Ugly trick for dealing with 'O' symmetry. */ |
| 373 | if (pattern->trfno == 5) { |
| 374 | ll = 2; |
| 375 | end_transformation = 6; |
| 376 | } |
| 377 | |
| 378 | /* try each orientation transformation. Assume at least 1 */ |
| 379 | |
| 380 | do { |
| 381 | |
| 382 | #if PROFILE_PATTERNS |
| 383 | int nodes_before; |
| 384 | #endif |
| 385 | |
| 386 | #if GRID_OPT == 1 |
| 387 | |
| 388 | /* We first perform the grid check : this checks up to 16 |
| 389 | * elements in one go, and allows us to rapidly reject |
| 390 | * patterns which do not match. While this check invokes a |
| 391 | * necessary condition, it is not a sufficient test, so more |
| 392 | * careful checks are still required, but this allows rapid |
| 393 | * rejection. merged_val should contain a combination of |
| 394 | * 16 board positions around m, n. The colours have been fixed |
| 395 | * up so that stones which are 'O' in the pattern are |
| 396 | * bit-pattern %01. |
| 397 | */ |
| 398 | if ((merged_val & pattern->and_mask[ll]) != pattern->val_mask[ll]) |
| 399 | continue; /* large-scale match failed */ |
| 400 | |
| 401 | #endif /* GRID_OPT == 1 */ |
| 402 | |
| 403 | /* Next, we do the range check. This applies the edge |
| 404 | * constraints implicitly. |
| 405 | */ |
| 406 | { |
| 407 | int mi, mj, xi, xj; |
| 408 | |
| 409 | TRANSFORM2(pattern->mini, pattern->minj, &mi, &mj, ll); |
| 410 | TRANSFORM2(pattern->maxi, pattern->maxj, &xi, &xj, ll); |
| 411 | |
| 412 | /* {min,max}{i,j} are the appropriate corners of the original |
| 413 | * pattern, Once we transform, {m,x}{i,j} are still corners, |
| 414 | * but we don't know *which* corners. |
| 415 | * We could sort them, but it turns out to be cheaper |
| 416 | * to just test enough cases to be safe. |
| 417 | */ |
| 418 | |
| 419 | DEBUG(DEBUG_MATCHER, |
| 420 | "---\nconsidering pattern '%s', rotation %d at %1m. Range %d,%d -> %d,%d\n", |
| 421 | pattern->name, ll, anchor, mi, mj, xi, xj); |
| 422 | |
| 423 | /* now do the range-check */ |
| 424 | if (!ON_BOARD2(m + mi, n + mj) || !ON_BOARD2(m + xi, n + xj)) |
| 425 | continue; /* out of range */ |
| 426 | } |
| 427 | |
| 428 | /* Now iterate over the elements of the pattern. */ |
| 429 | found_goal = 0; |
| 430 | for (k = 0; k < pattern->patlen; ++k) { /* match each point */ |
| 431 | int pos; /* absolute coords of (transformed) pattern element */ |
| 432 | int att = pattern->patn[k].att; /* what we are looking for */ |
| 433 | |
| 434 | /* Work out the position on the board of this pattern element. */ |
| 435 | |
| 436 | /* transform pattern real coordinate... */ |
| 437 | pos = AFFINE_TRANSFORM(pattern->patn[k].offset, ll, anchor); |
| 438 | |
| 439 | ASSERT_ON_BOARD1(pos); |
| 440 | |
| 441 | /* ...and check that board[pos] matches (see above). */ |
| 442 | if ((board[pos] & and_mask[color-1][att]) != val_mask[color-1][att]) |
| 443 | goto match_failed; |
| 444 | |
| 445 | if (goal != NULL && board[pos] != EMPTY && goal[pos]) |
| 446 | found_goal = 1; |
| 447 | |
| 448 | /* Check out the class_X, class_O, class_x, class_o |
| 449 | * attributes - see patterns.db and above. |
| 450 | */ |
| 451 | if ((pattern->class |
| 452 | & class_mask[dragon[pos].status][board[pos]]) != 0) |
| 453 | goto match_failed; |
| 454 | |
| 455 | } /* loop over elements */ |
| 456 | |
| 457 | |
| 458 | #if GRID_OPT == 2 |
| 459 | /* Make sure the grid optimisation wouldn't have |
| 460 | rejected this pattern */ |
| 461 | ASSERT2((merged_val & pattern->and_mask[ll]) |
| 462 | == pattern->val_mask[ll], m, n); |
| 463 | #endif /* we don't trust the grid optimisation */ |
| 464 | |
| 465 | |
| 466 | /* Make it here ==> We have matched all the elements to the board. */ |
| 467 | if ((goal != NULL) && !found_goal) |
| 468 | goto match_failed; |
| 469 | |
| 470 | #if PROFILE_PATTERNS |
| 471 | pattern->hits++; |
| 472 | nodes_before = stats.nodes; |
| 473 | #endif |
| 474 | |
| 475 | /* A match! - Call back to the invoker to let it know. */ |
| 476 | callback(anchor, color, pattern, ll, callback_data); |
| 477 | |
| 478 | #if PROFILE_PATTERNS |
| 479 | pattern->reading_nodes += stats.nodes - nodes_before; |
| 480 | #endif |
| 481 | |
| 482 | /* We jump to here as soon as we discover a pattern has failed. */ |
| 483 | match_failed: |
| 484 | DEBUG(DEBUG_MATCHER, |
| 485 | "end of pattern '%s', rotation %d at %1m\n---\n", |
| 486 | pattern->name, ll, anchor); |
| 487 | |
| 488 | } while (++ll < end_transformation); /* ll loop over symmetries */ |
| 489 | } /* if not rejected by maxwt */ |
| 490 | } while ((++pattern)->patn); /* loop over patterns */ |
| 491 | } |
| 492 | |
| 493 | |
| 494 | /* |
| 495 | * Scan the board to get patterns anchored by anchor from color |
| 496 | * point of view. |
| 497 | * the board must be prepared by dfa_prepare_for_match(color) ! |
| 498 | */ |
| 499 | static void |
| 500 | matchpat_loop(matchpat_callback_fn_ptr callback, int color, int anchor, |
| 501 | struct pattern_db *pdb, void *callback_data, |
| 502 | signed char goal[BOARDMAX], int anchor_in_goal) |
| 503 | { |
| 504 | int pos; |
| 505 | |
| 506 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 507 | if (board[pos] == anchor && (!anchor_in_goal || goal[pos] != 0)) |
| 508 | do_matchpat(pos, callback, color, pdb->patterns, |
| 509 | callback_data, goal); |
| 510 | } |
| 511 | } |
| 512 | |
| 513 | |
| 514 | /**************************************************************************/ |
| 515 | /* DFA matcher: */ |
| 516 | /**************************************************************************/ |
| 517 | |
| 518 | /* Set this to show the dfa board in action */ |
| 519 | /* #define DFA_TRACE 1 */ |
| 520 | |
| 521 | /* Data. */ |
| 522 | static int dfa_board_size = -1; |
| 523 | static int dfa_p[DFA_BASE * DFA_BASE]; |
| 524 | |
| 525 | /* This is used by the EXPECTED_COLOR macro. */ |
| 526 | static const int convert[3][4] = { |
| 527 | {-1, -1, -1, -1}, /* not used */ |
| 528 | {EMPTY, WHITE, BLACK, OUT_BOARD}, /* WHITE */ |
| 529 | {EMPTY, BLACK, WHITE, OUT_BOARD} /* BLACK */ |
| 530 | }; |
| 531 | #define EXPECTED_COLOR(player_c, position_c) \ |
| 532 | (convert[player_c][position_c]) |
| 533 | |
| 534 | /* Forward declarations. */ |
| 535 | static void dfa_prepare_for_match(int color); |
| 536 | static int scan_for_patterns(dfa_rt_t *pdfa, int l, int *dfa_pos, |
| 537 | int *pat_list); |
| 538 | static void do_dfa_matchpat(dfa_rt_t *pdfa, |
| 539 | int anchor, matchpat_callback_fn_ptr callback, |
| 540 | int color, struct pattern *database, |
| 541 | void *callback_data, signed char goal[BOARDMAX], |
| 542 | int anchor_in_goal); |
| 543 | static void check_pattern_light(int anchor, |
| 544 | matchpat_callback_fn_ptr callback, |
| 545 | int color, struct pattern *pattern, int ll, |
| 546 | void *callback_data, |
| 547 | signed char goal[BOARDMAX], |
| 548 | int anchor_in_goal); |
| 549 | static void dfa_matchpat_loop(matchpat_callback_fn_ptr callback, |
| 550 | int color, int anchor, |
| 551 | struct pattern_db *pdb, void *callback_data, |
| 552 | signed char goal[BOARDMAX], int anchor_in_goal); |
| 553 | |
| 554 | |
| 555 | /***********************************************************************/ |
| 556 | |
| 557 | |
| 558 | |
| 559 | /* prepare the dfa board (gnugo initialization) */ |
| 560 | void |
| 561 | dfa_match_init(void) |
| 562 | { |
| 563 | build_spiral_order(); |
| 564 | |
| 565 | if (owl_vital_apat_db.pdfa != NULL) |
| 566 | DEBUG(DEBUG_MATCHER, "owl_vital_apat --> using dfa\n"); |
| 567 | if (owl_attackpat_db.pdfa != NULL) |
| 568 | DEBUG(DEBUG_MATCHER, "owl_attackpat --> using dfa\n"); |
| 569 | if (owl_defendpat_db.pdfa != NULL) |
| 570 | DEBUG(DEBUG_MATCHER, "owl_defendpat --> using dfa\n"); |
| 571 | if (pat_db.pdfa != NULL) |
| 572 | DEBUG(DEBUG_MATCHER, "pat --> using dfa\n"); |
| 573 | if (attpat_db.pdfa != NULL) |
| 574 | DEBUG(DEBUG_MATCHER, "attpat --> using dfa\n"); |
| 575 | if (defpat_db.pdfa != NULL) |
| 576 | DEBUG(DEBUG_MATCHER, "defpat --> using dfa\n"); |
| 577 | if (endpat_db.pdfa != NULL) |
| 578 | DEBUG(DEBUG_MATCHER, "endpat --> using dfa\n"); |
| 579 | if (conn_db.pdfa != NULL) |
| 580 | DEBUG(DEBUG_MATCHER, "conn --> using dfa\n"); |
| 581 | if (influencepat_db.pdfa != NULL) |
| 582 | DEBUG(DEBUG_MATCHER, "influencepat --> using dfa\n"); |
| 583 | if (barrierspat_db.pdfa != NULL) |
| 584 | DEBUG(DEBUG_MATCHER, "barrierspat --> using dfa\n"); |
| 585 | if (fusekipat_db.pdfa != NULL) |
| 586 | DEBUG(DEBUG_MATCHER, "barrierspat --> using dfa\n"); |
| 587 | |
| 588 | /* force out_board initialization */ |
| 589 | dfa_board_size = -1; |
| 590 | } |
| 591 | |
| 592 | /* |
| 593 | * copy the board on a private board with adapted colors |
| 594 | * and adapted size |
| 595 | */ |
| 596 | static void |
| 597 | dfa_prepare_for_match(int color) |
| 598 | { |
| 599 | int i, j; |
| 600 | int pos; |
| 601 | |
| 602 | if (dfa_board_size != board_size) { |
| 603 | dfa_board_size = board_size; |
| 604 | /* clean up the board */ |
| 605 | for (pos = 0; pos < DFA_BASE * DFA_BASE; pos++) |
| 606 | dfa_p[pos] = OUT_BOARD; |
| 607 | } |
| 608 | |
| 609 | /* copy the board */ |
| 610 | for (i = 0; i < dfa_board_size; i++) |
| 611 | for (j = 0; j < dfa_board_size; j++) |
| 612 | dfa_p[DFA_POS(i, j)] = EXPECTED_COLOR(color, BOARD(i, j)); |
| 613 | |
| 614 | prepare_for_match(color); |
| 615 | } |
| 616 | |
| 617 | #if 0 |
| 618 | /* Debug function. */ |
| 619 | static void |
| 620 | dump_dfa_board(int m, int n) |
| 621 | { |
| 622 | int i, j; |
| 623 | |
| 624 | for (i = 0; i < dfa_board_size; i++) { |
| 625 | for (j = 0; j < dfa_board_size; j++) { |
| 626 | if (i != m || j != n) |
| 627 | fprintf(stderr, "%1d", dfa_p[DFA_POS(i, j)]); |
| 628 | else |
| 629 | fprintf(stderr, "*"); |
| 630 | } |
| 631 | |
| 632 | fprintf(stderr, "\n"); |
| 633 | } |
| 634 | } |
| 635 | #endif |
| 636 | |
| 637 | |
| 638 | /* |
| 639 | * Scan the board with a DFA to get all patterns matching at |
| 640 | * `dfa_pos' with transformation l. Store patterns indexes |
| 641 | * `pat_list'. Return the number of patterns found. |
| 642 | */ |
| 643 | static int |
| 644 | scan_for_patterns(dfa_rt_t *pdfa, int l, int *dfa_pos, int *pat_list) |
| 645 | { |
| 646 | int delta; |
| 647 | int state = 1; /* initial state */ |
| 648 | int row = 0; /* initial row */ |
| 649 | int id = 0; /* position in id_list */ |
| 650 | |
| 651 | do { |
| 652 | /* collect patterns indexes */ |
| 653 | int att = pdfa->states[state].att; |
| 654 | while (att != 0) { |
| 655 | pat_list[id] = pdfa->indexes[att].val; |
| 656 | id++; |
| 657 | att = pdfa->indexes[att].next; |
| 658 | } |
| 659 | |
| 660 | /* go to next state */ |
| 661 | delta = pdfa->states[state].next[dfa_pos[spiral[row][l]]]; |
| 662 | state += delta; |
| 663 | row++; |
| 664 | } while (delta != 0); /* while not on error state */ |
| 665 | |
| 666 | return id; |
| 667 | } |
| 668 | |
| 669 | |
| 670 | /* Perform pattern matching with DFA filtering. */ |
| 671 | static void |
| 672 | do_dfa_matchpat(dfa_rt_t *pdfa, |
| 673 | int anchor, matchpat_callback_fn_ptr callback, |
| 674 | int color, struct pattern *database, |
| 675 | void *callback_data, signed char goal[BOARDMAX], |
| 676 | int anchor_in_goal) |
| 677 | { |
| 678 | int k; |
| 679 | int ll; /* Iterate over transformations (rotations or reflections) */ |
| 680 | int patterns[DFA_MAX_MATCHED + 8]; |
| 681 | int num_matched = 0; |
| 682 | int *dfa_pos = dfa_p + DFA_POS(I(anchor), J(anchor)); |
| 683 | |
| 684 | /* Basic sanity checks. */ |
| 685 | ASSERT_ON_BOARD1(anchor); |
| 686 | |
| 687 | /* One scan by transformation */ |
| 688 | for (ll = 0; ll < 8; ll++) { |
| 689 | num_matched += scan_for_patterns(pdfa, ll, dfa_pos, |
| 690 | patterns + num_matched); |
| 691 | patterns[num_matched++] = -1; |
| 692 | } |
| 693 | |
| 694 | ASSERT1(num_matched <= DFA_MAX_MATCHED + 8, anchor); |
| 695 | |
| 696 | /* Constraints and other tests. */ |
| 697 | for (ll = 0, k = 0; ll < 8; k++) { |
| 698 | int matched; |
| 699 | |
| 700 | if (patterns[k] == -1) { |
| 701 | ll++; |
| 702 | continue; |
| 703 | } |
| 704 | |
| 705 | matched = patterns[k]; |
| 706 | |
| 707 | #if PROFILE_PATTERNS |
| 708 | database[matched].dfa_hits++; |
| 709 | #endif |
| 710 | |
| 711 | check_pattern_light(anchor, callback, color, database + matched, |
| 712 | ll, callback_data, goal, anchor_in_goal); |
| 713 | } |
| 714 | } |
| 715 | |
| 716 | |
| 717 | /* |
| 718 | * Do the pattern matching for a given pattern and a given |
| 719 | * transformation ll. |
| 720 | * (does not recompute what dfa filtering has already done) |
| 721 | */ |
| 722 | |
| 723 | static void |
| 724 | check_pattern_light(int anchor, matchpat_callback_fn_ptr callback, int color, |
| 725 | struct pattern *pattern, int ll, void *callback_data, |
| 726 | signed char goal[BOARDMAX], int anchor_in_goal) |
| 727 | { |
| 728 | int k; /* Iterate over elements of pattern */ |
| 729 | int found_goal = 0; |
| 730 | |
| 731 | #if PROFILE_PATTERNS |
| 732 | int nodes_before; |
| 733 | #endif |
| 734 | |
| 735 | if (0) |
| 736 | gprintf("check_pattern_light @ %1m rot:%d pattern: %s\n", |
| 737 | anchor, ll, pattern->name); |
| 738 | |
| 739 | /* Throw out duplicating orientations of symmetric patterns. */ |
| 740 | if (pattern->trfno == 5) { |
| 741 | if (ll < 2 || ll >= 6) |
| 742 | return; |
| 743 | } |
| 744 | else { |
| 745 | if (ll >= pattern->trfno) |
| 746 | return; |
| 747 | } |
| 748 | |
| 749 | |
| 750 | /* Now iterate over the elements of the pattern. */ |
| 751 | for (k = 0; k < pattern->patlen; k++) { |
| 752 | /* match each point */ |
| 753 | int pos; /* absolute (board) co-ords of |
| 754 | (transformed) pattern element */ |
| 755 | |
| 756 | /* transform pattern real coordinate... */ |
| 757 | pos = AFFINE_TRANSFORM(pattern->patn[k].offset, ll, anchor); |
| 758 | ASSERT_ON_BOARD1(pos); |
| 759 | |
| 760 | if (!anchor_in_goal) { |
| 761 | /* goal check */ |
| 762 | if (goal != NULL && board[pos] != EMPTY && goal[pos]) |
| 763 | found_goal = 1; |
| 764 | } |
| 765 | |
| 766 | /* class check */ |
| 767 | ASSERT1(dragon[pos].status < 4, anchor); |
| 768 | if ((pattern->class & class_mask[dragon[pos].status][board[pos]]) != 0) |
| 769 | goto match_failed; |
| 770 | |
| 771 | } /* loop over elements */ |
| 772 | |
| 773 | /* Make it here ==> We have matched all the elements to the board. */ |
| 774 | if (!anchor_in_goal) { |
| 775 | if (goal != NULL && !found_goal) |
| 776 | goto match_failed; |
| 777 | } |
| 778 | |
| 779 | #if PROFILE_PATTERNS |
| 780 | pattern->hits++; |
| 781 | nodes_before = stats.nodes; |
| 782 | #endif |
| 783 | |
| 784 | /* A match! - Call back to the invoker to let it know. */ |
| 785 | callback(anchor, color, pattern, ll, callback_data); |
| 786 | |
| 787 | #if PROFILE_PATTERNS |
| 788 | pattern->reading_nodes += stats.nodes - nodes_before; |
| 789 | #endif |
| 790 | |
| 791 | /* We jump to here as soon as we discover a pattern has failed. */ |
| 792 | match_failed: |
| 793 | DEBUG(DEBUG_MATCHER, "end of pattern '%s', rotation %d at %1m\n---\n", |
| 794 | pattern->name, ll, anchor); |
| 795 | |
| 796 | } /* check_pattern_light */ |
| 797 | |
| 798 | |
| 799 | /* |
| 800 | * Scan the board to get patterns anchored by anchor from color |
| 801 | * point of view. |
| 802 | * the board must be prepared by dfa_prepare_for_match(color) ! |
| 803 | */ |
| 804 | static void |
| 805 | dfa_matchpat_loop(matchpat_callback_fn_ptr callback, int color, int anchor, |
| 806 | struct pattern_db *pdb, void *callback_data, |
| 807 | signed char goal[BOARDMAX], int anchor_in_goal) |
| 808 | { |
| 809 | int pos; |
| 810 | |
| 811 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { |
| 812 | if (board[pos] == anchor && (!anchor_in_goal || goal[pos] != 0)) |
| 813 | do_dfa_matchpat(pdb->pdfa, pos, callback, color, pdb->patterns, |
| 814 | callback_data, goal, anchor_in_goal); |
| 815 | } |
| 816 | } |
| 817 | |
| 818 | |
| 819 | |
| 820 | /**************************************************************************/ |
| 821 | /* Main functions: */ |
| 822 | /**************************************************************************/ |
| 823 | |
| 824 | |
| 825 | typedef void (*loop_fn_ptr_t)(matchpat_callback_fn_ptr callback, |
| 826 | int color, int anchor, |
| 827 | struct pattern_db *pdb, void *callback_data, |
| 828 | signed char goal[BOARDMAX], int anchor_in_goal); |
| 829 | |
| 830 | typedef void (*prepare_fn_ptr_t)(int color); |
| 831 | |
| 832 | /* same as the old matchpat but for all the board with |
| 833 | * preparation. |
| 834 | * |
| 835 | * 4 possible values for color argument: |
| 836 | * WHITE or BLACK: matchpat is called from this color point of view. |
| 837 | * ANCHOR_COLOR : matchpat is called from the anchor's point of view. |
| 838 | * ANCHOR_OTHER : matchpat is called from the opposite color of the |
| 839 | * anchor's point of view. |
| 840 | */ |
| 841 | |
| 842 | void |
| 843 | matchpat(matchpat_callback_fn_ptr callback, int color, |
| 844 | struct pattern_db *pdb, void *callback_data, |
| 845 | signed char goal[BOARDMAX]) |
| 846 | { |
| 847 | matchpat_goal_anchor(callback, color, pdb, callback_data, goal, |
| 848 | pdb->fixed_anchor); |
| 849 | } |
| 850 | |
| 851 | void |
| 852 | matchpat_goal_anchor(matchpat_callback_fn_ptr callback, int color, |
| 853 | struct pattern_db *pdb, void *callback_data, |
| 854 | signed char goal[BOARDMAX], int anchor_in_goal) |
| 855 | { |
| 856 | loop_fn_ptr_t loop = matchpat_loop; |
| 857 | prepare_fn_ptr_t prepare = prepare_for_match; |
| 858 | |
| 859 | /* check board size */ |
| 860 | if (pdb->fixed_for_size != board_size) { |
| 861 | fixup_patterns_for_board_size(pdb->patterns); |
| 862 | pdb->fixed_for_size = board_size; |
| 863 | } |
| 864 | |
| 865 | /* select pattern matching strategy */ |
| 866 | if (pdb->pdfa != NULL) { |
| 867 | loop = dfa_matchpat_loop; |
| 868 | prepare = dfa_prepare_for_match; |
| 869 | } |
| 870 | |
| 871 | /* select strategy */ |
| 872 | switch (color) { |
| 873 | case ANCHOR_COLOR: |
| 874 | { /* match pattern for the color of their anchor */ |
| 875 | prepare(WHITE); |
| 876 | loop(callback, WHITE, WHITE, pdb, callback_data, goal, anchor_in_goal); |
| 877 | prepare(BLACK); |
| 878 | loop(callback, BLACK, BLACK, pdb, callback_data, goal, anchor_in_goal); |
| 879 | } |
| 880 | break; |
| 881 | case ANCHOR_OTHER: |
| 882 | { /* match pattern for the opposite color of their anchor */ |
| 883 | prepare(WHITE); |
| 884 | loop(callback, WHITE, BLACK, pdb, callback_data, goal, anchor_in_goal); |
| 885 | prepare(BLACK); |
| 886 | loop(callback, BLACK, WHITE, pdb, callback_data, goal, anchor_in_goal); |
| 887 | } |
| 888 | break; |
| 889 | default: |
| 890 | { /* match all patterns for color */ |
| 891 | prepare(color); |
| 892 | loop(callback, color, WHITE, pdb, callback_data, goal, anchor_in_goal); |
| 893 | loop(callback, color, BLACK, pdb, callback_data, goal, anchor_in_goal); |
| 894 | } |
| 895 | } |
| 896 | } |
| 897 | |
| 898 | |
| 899 | static int |
| 900 | fullboard_transform(int pos, int trans) |
| 901 | { |
| 902 | int dx = I(pos) - (board_size-1)/2; |
| 903 | int dy = J(pos) - (board_size-1)/2; |
| 904 | int x, y; |
| 905 | gg_assert(POS((board_size-1)/2, (board_size-1)/2) + DELTA(dx, dy) == pos); |
| 906 | TRANSFORM2(dx, dy, &x, &y, trans); |
| 907 | return POS(x + (board_size-1)/2, y + (board_size-1)/2); |
| 908 | } |
| 909 | |
| 910 | /* A dedicated matcher which can only do fullboard matching on |
| 911 | * odd-sized boards, optimized for fuseki patterns. |
| 912 | */ |
| 913 | void |
| 914 | fullboard_matchpat(fullboard_matchpat_callback_fn_ptr callback, int color, |
| 915 | struct fullboard_pattern *pattern) |
| 916 | { |
| 917 | int ll; /* Iterate over transformations (rotations or reflections) */ |
| 918 | /* We transform around the center point. */ |
| 919 | int number_of_stones_on_board = stones_on_board(BLACK | WHITE); |
| 920 | static int color_map[gg_max(WHITE, BLACK) + 1]; |
| 921 | /* One hash value for each rotation/reflection: */ |
| 922 | Hash_data current_board_hash[8]; |
| 923 | |
| 924 | /* Basic sanity check. */ |
| 925 | gg_assert(color != EMPTY); |
| 926 | gg_assert(board_size % 2 == 1); |
| 927 | |
| 928 | color_map[EMPTY] = EMPTY; |
| 929 | if (color == WHITE) { |
| 930 | color_map[WHITE] = WHITE; |
| 931 | color_map[BLACK] = BLACK; |
| 932 | } |
| 933 | else { |
| 934 | color_map[WHITE] = BLACK; |
| 935 | color_map[BLACK] = WHITE; |
| 936 | } |
| 937 | |
| 938 | /* Get hash data of all rotations/reflections of current board position. */ |
| 939 | for (ll = 0; ll < 8; ll++) { |
| 940 | Intersection p[BOARDSIZE]; |
| 941 | int pos; |
| 942 | for (pos = 0; pos < BOARDSIZE; pos++) |
| 943 | if (ON_BOARD(pos)) |
| 944 | p[pos] = color_map[board[fullboard_transform(pos, ll)]]; |
| 945 | else |
| 946 | p[pos] = GRAY; |
| 947 | |
| 948 | if (ON_BOARD(board_ko_pos)) |
| 949 | hashdata_recalc(¤t_board_hash[ll], p, |
| 950 | fullboard_transform(board_ko_pos, ll)); |
| 951 | else |
| 952 | hashdata_recalc(¤t_board_hash[ll], p, NO_MOVE); |
| 953 | } |
| 954 | |
| 955 | /* Try each pattern - NULL pattern name marks end of list. */ |
| 956 | for (; pattern->name; pattern++) { |
| 957 | if (pattern->number_of_stones != number_of_stones_on_board) |
| 958 | continue; |
| 959 | /* Try each orientation transformation. */ |
| 960 | for (ll = 0; ll < 8; ll++) |
| 961 | if (hashdata_is_equal(current_board_hash[ll], pattern->fullboard_hash)) { |
| 962 | /* A match! - Call back to the invoker to let it know. */ |
| 963 | int pos = AFFINE_TRANSFORM(pattern->move_offset, ll, |
| 964 | POS((board_size-1)/2, (board_size-1)/2)); |
| 965 | callback(pos, pattern, ll); |
| 966 | } |
| 967 | } |
| 968 | } |
| 969 | |
| 970 | |
| 971 | /**************************************************************************/ |
| 972 | /* Corner matcher */ |
| 973 | /**************************************************************************/ |
| 974 | |
| 975 | /* These arrays specify anchor corner for each transformation. They _must_ |
| 976 | * be in line with transformation2[][] array in patterns/transform.c. |
| 977 | */ |
| 978 | static const int corner_x[8] = {0, 0, 1, 1, 1, 1, 0, 0}; |
| 979 | static const int corner_y[8] = {0, 1, 1, 0, 1, 0, 0, 1}; |
| 980 | |
| 981 | /* The number of stones in "corner area" for each board position. For example, |
| 982 | * corner area for position E3 when anchoring at A1 corner, looks like this: |
| 983 | * |
| 984 | * |........ In general, NUM_STONES(pos) is the number of stones |
| 985 | * |........ which are closer to the corner (stone at pos, if any, |
| 986 | * 3 |#####... counts too) than pos. Note, that say G2 is not closer |
| 987 | * |#####... to the corner than E3, the reverse isn't true either. |
| 988 | * 1 |#####... Their distances are "incomparable" since E < G but |
| 989 | * +-------- 3 > 2. |
| 990 | * A E |
| 991 | * |
| 992 | * Note that we need these values in at most MAX_BOARD x MAX_BOARD array. |
| 993 | * However, it may be anchored at any corner of the board, so if the board is |
| 994 | * small, we may calculate NUM_STONES() at negative coordinates. |
| 995 | */ |
| 996 | static int num_stones[2*BOARDMAX]; |
| 997 | #define NUM_STONES(pos) num_stones[(pos) + BOARDMAX] |
| 998 | |
| 999 | /* Stone locations are stored in this array. They might be needed by callback |
| 1000 | * function. |
| 1001 | */ |
| 1002 | static int pattern_stones[BOARDMAX]; |
| 1003 | |
| 1004 | |
| 1005 | /* Recursively performs corner matching. This function checks whether |
| 1006 | * `num_variation' variations pointed by `variation' parameter match. |
| 1007 | * If any of them does, the function calls itself recursively. If any |
| 1008 | * pattern corresponding to those variations matches, it notifies |
| 1009 | * callback function. |
| 1010 | */ |
| 1011 | static void |
| 1012 | do_corner_matchpat(int num_variations, struct corner_variation *variation, |
| 1013 | int match_color, corner_matchpat_callback_fn_ptr callback, |
| 1014 | int callback_color, int trans, int anchor, int stones) |
| 1015 | { |
| 1016 | for (; --num_variations >= 0; variation++) { |
| 1017 | int move = AFFINE_TRANSFORM(variation->move_offset, trans, anchor); |
| 1018 | int color_check = match_color ^ variation->xor_att; |
| 1019 | struct corner_pattern *pattern = variation->pattern; |
| 1020 | |
| 1021 | if (pattern && color_check == callback_color) { |
| 1022 | int second_corner |
| 1023 | = AFFINE_TRANSFORM(pattern->second_corner_offset, trans, anchor); |
| 1024 | |
| 1025 | if (NUM_STONES(second_corner) == stones |
| 1026 | && (!pattern->symmetric || trans < 4)) { |
| 1027 | /* We have found a matching pattern. */ |
| 1028 | ASSERT1(board[move] == EMPTY, move); |
| 1029 | |
| 1030 | callback(move, callback_color, pattern, trans, pattern_stones, stones); |
| 1031 | continue; |
| 1032 | } |
| 1033 | } |
| 1034 | |
| 1035 | if (variation->num_variations |
| 1036 | && NUM_STONES(move) == variation->num_stones |
| 1037 | && board[move] == color_check) { |
| 1038 | /* A matching variation. */ |
| 1039 | pattern_stones[stones] = move; |
| 1040 | do_corner_matchpat(variation->num_variations, variation->variations, |
| 1041 | match_color, callback, callback_color, |
| 1042 | trans, anchor, stones + 1); |
| 1043 | } |
| 1044 | } |
| 1045 | } |
| 1046 | |
| 1047 | |
| 1048 | /* Perform corner matching at all four corners and both possible |
| 1049 | * transformations at each corner. `callback' is notified if any |
| 1050 | * matching pattern is found. |
| 1051 | */ |
| 1052 | void |
| 1053 | corner_matchpat(corner_matchpat_callback_fn_ptr callback, int color, |
| 1054 | struct corner_db *database) |
| 1055 | { |
| 1056 | int k; |
| 1057 | |
| 1058 | for (k = 0; k < 8; k++) { |
| 1059 | int anchor = POS(corner_x[k] * (board_size - 1), |
| 1060 | corner_y[k] * (board_size - 1)); |
| 1061 | int i; |
| 1062 | int j; |
| 1063 | int dx = TRANSFORM(OFFSET(1, 0), k); |
| 1064 | int dy = TRANSFORM(OFFSET(0, 1), k); |
| 1065 | int pos; |
| 1066 | struct corner_variation *variation = database->top_variations; |
| 1067 | |
| 1068 | /* Fill in the NUM_STONES() array. We use `max_width' and `max_height' |
| 1069 | * fields of database structure to stop working as early as possible. |
| 1070 | */ |
| 1071 | NUM_STONES(anchor) = IS_STONE(board[anchor]); |
| 1072 | |
| 1073 | pos = anchor; |
| 1074 | for (i = 1; i < database->max_height; i++) { |
| 1075 | pos += dx; |
| 1076 | if (!ON_BOARD(pos)) { |
| 1077 | do { |
| 1078 | NUM_STONES(pos) = BOARDMAX; |
| 1079 | pos += dx; |
| 1080 | } while (++i < database->max_height); |
| 1081 | |
| 1082 | break; |
| 1083 | } |
| 1084 | |
| 1085 | NUM_STONES(pos) = NUM_STONES(pos - dx) + IS_STONE(board[pos]); |
| 1086 | } |
| 1087 | |
| 1088 | pos = anchor; |
| 1089 | for (j = 1; j < database->max_width; j++) { |
| 1090 | pos += dy; |
| 1091 | if (!ON_BOARD(pos)) { |
| 1092 | do { |
| 1093 | NUM_STONES(pos) = BOARDMAX; |
| 1094 | pos += dy; |
| 1095 | } while (++j < database->max_width); |
| 1096 | |
| 1097 | break; |
| 1098 | } |
| 1099 | |
| 1100 | NUM_STONES(pos) = NUM_STONES(pos - dy) + IS_STONE(board[pos]); |
| 1101 | } |
| 1102 | |
| 1103 | for (i = 1; i < database->max_height; i++) { |
| 1104 | pos = anchor + i * dy; |
| 1105 | for (j = 1; j < database->max_width; j++) { |
| 1106 | pos += dx; |
| 1107 | NUM_STONES(pos) = NUM_STONES(pos - dx) + NUM_STONES(pos - dy) |
| 1108 | - NUM_STONES(pos - dx - dy); |
| 1109 | if (ON_BOARD1(pos) && IS_STONE(board[pos])) |
| 1110 | NUM_STONES(pos)++; |
| 1111 | } |
| 1112 | } |
| 1113 | |
| 1114 | /* Try to match top variations. If any of them matches, we call |
| 1115 | * do_corner_matchpat() to recurse that variation's tree. |
| 1116 | */ |
| 1117 | for (i = 0; i < database->num_top_variations; i++) { |
| 1118 | int move = AFFINE_TRANSFORM(variation->move_offset, k, anchor); |
| 1119 | |
| 1120 | if (NUM_STONES(move) == 1 && IS_STONE(board[move])) { |
| 1121 | pattern_stones[0] = move; |
| 1122 | do_corner_matchpat(variation->num_variations, variation->variations, |
| 1123 | board[move], callback, color, k, anchor, 1); |
| 1124 | } |
| 1125 | |
| 1126 | variation++; |
| 1127 | } |
| 1128 | } |
| 1129 | } |
| 1130 | |
| 1131 | |
| 1132 | /* |
| 1133 | * Local Variables: |
| 1134 | * tab-width: 8 |
| 1135 | * c-basic-offset: 2 |
| 1136 | * End: |
| 1137 | */ |