Commit | Line | Data |
---|---|---|
7eeb782e AT |
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 | */ |