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 | ||
25 | /* This file contains functions that deals with threats and, | |
26 | * especially, combinations of threats. | |
27 | */ | |
28 | ||
29 | #include "gnugo.h" | |
30 | ||
31 | #include <string.h> | |
32 | ||
33 | #include "liberty.h" | |
34 | #include "gg_utils.h" | |
35 | #include "patterns.h" | |
36 | ||
37 | ||
38 | static void find_double_threats(int color); | |
39 | ||
40 | /* Generate move reasons for combination attacks and defenses against | |
41 | * them. | |
42 | * | |
43 | * This is one of the move generators called from genmove(). | |
44 | */ | |
45 | ||
46 | void | |
47 | combinations(int color) | |
48 | { | |
49 | int save_verbose; | |
50 | int attack_point; | |
51 | signed char defense_points[BOARDMAX]; | |
52 | int other = OTHER_COLOR(color); | |
53 | int aa_val; | |
54 | ||
55 | /* Find intersections with multiple threats. */ | |
56 | find_double_threats(color); | |
57 | ||
58 | save_verbose = verbose; | |
59 | if (verbose > 0) | |
60 | verbose--; | |
61 | ||
62 | if (save_verbose) | |
63 | gprintf("\nlooking for combination attacks ...\n"); | |
64 | ||
65 | aa_val = atari_atari(color, &attack_point, NULL, save_verbose); | |
66 | if (aa_val > 0) { | |
67 | if (save_verbose) | |
68 | gprintf("Combination attack for %C with size %d found at %1m\n", | |
69 | color, aa_val, attack_point); | |
70 | add_my_atari_atari_move(attack_point, aa_val); | |
71 | } | |
72 | ||
73 | aa_val = atari_atari(other, &attack_point, defense_points, save_verbose); | |
74 | if (aa_val > 0) { | |
75 | int pos; | |
76 | if (save_verbose) | |
77 | gprintf("Combination attack for %C with size %d found at %1m\n", | |
78 | other, aa_val, attack_point); | |
79 | ||
80 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
81 | if (ON_BOARD(pos) && defense_points[pos]) { | |
82 | add_your_atari_atari_move(pos, aa_val); | |
83 | if (save_verbose) | |
84 | gprintf("- defense at %1m\n", pos); | |
85 | } | |
86 | } | |
87 | } | |
88 | verbose = save_verbose; | |
89 | } | |
90 | ||
91 | ||
92 | #define MAX_THREATENED_STRINGS 10 /* Should be enough for one intersection */ | |
93 | ||
94 | static void | |
95 | find_double_threats(int color) | |
96 | { | |
97 | int ii; | |
98 | int k; | |
99 | int l; | |
100 | ||
101 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) { | |
102 | int num_a_threatened_groups; | |
103 | int a_threatened_groups[MAX_THREATENED_STRINGS]; | |
104 | #if 0 | |
105 | int num_d_threatened_groups; | |
106 | int d_threatened_groups[MAX_THREATENED_STRINGS]; | |
107 | #endif | |
108 | ||
109 | if (!ON_BOARD(ii)) | |
110 | continue; | |
111 | ||
112 | /* Generate an EITHER_MOVE move reasons for each pair of the | |
113 | * threatened strings. We must also remove the threats, because | |
114 | * otherwise we would get followup points for them as well. | |
115 | * | |
116 | * FIXME: | |
117 | * - This is perhaps not the best way to do it, but realistically | |
118 | * it will be seldom that more than two strings are threatened | |
119 | * at the same point. Still, we should find a better way. | |
120 | * - EITHER_MOVE should be generalized to more than two strings. | |
121 | */ | |
122 | num_a_threatened_groups = get_attack_threats(ii, MAX_THREATENED_STRINGS, | |
123 | a_threatened_groups); | |
124 | if (num_a_threatened_groups > 1) { | |
125 | if (trymove(ii, color, "find_double_threats-A", ii)) { | |
126 | for (k = 0; k < num_a_threatened_groups - 1; ++k) | |
127 | for (l = k + 1; l < num_a_threatened_groups; ++l) { | |
128 | /* Note: If we used attack_either() here instead of trymove() | |
129 | * and !defend_both(), we would not make use of the fact | |
130 | * that we already know of a common threat point for | |
131 | * the two strings. | |
132 | * Besides, attack_either is currently (3.1.11) not very good. | |
133 | * | |
134 | * The call to attack() is intended to detect the case | |
135 | * where the move at ii is a snapback capture. | |
136 | */ | |
137 | if (board[a_threatened_groups[k]] == EMPTY | |
138 | || board[a_threatened_groups[l]] == EMPTY) { | |
139 | if (!attack(ii, NULL)) { | |
140 | TRACE("Double threat at %1m, either %1m or %1m attacked.\n", | |
141 | ii, a_threatened_groups[k], a_threatened_groups[l]); | |
142 | add_either_move(ii, ATTACK_STRING, a_threatened_groups[k], | |
143 | ATTACK_STRING, a_threatened_groups[l]); | |
144 | remove_attack_threat_move(ii, a_threatened_groups[k]); | |
145 | remove_attack_threat_move(ii, a_threatened_groups[l]); | |
146 | } | |
147 | } | |
148 | else if (!defend_both(a_threatened_groups[k], | |
149 | a_threatened_groups[l])) { | |
150 | TRACE("Double threat at %1m, either %1m or %1m attacked.\n", | |
151 | ii, a_threatened_groups[k], a_threatened_groups[l]); | |
152 | add_either_move(ii, ATTACK_STRING, a_threatened_groups[k], | |
153 | ATTACK_STRING, a_threatened_groups[l]); | |
154 | remove_attack_threat_move(ii, a_threatened_groups[k]); | |
155 | remove_attack_threat_move(ii, a_threatened_groups[l]); | |
156 | } | |
157 | } | |
158 | popgo(); | |
159 | } | |
160 | } | |
161 | } | |
162 | ||
163 | ||
164 | /* FIXME: | |
165 | * TODO: | |
166 | * - defense threats | |
167 | * - combinations of owl threats and other threats | |
168 | * - combinations of threats to cut and connect | |
169 | * - combinations of breakins into enemy territory | |
170 | */ | |
171 | } | |
172 | ||
173 | ||
174 | /* ================================================================ */ | |
175 | /* Combination attacks */ | |
176 | /* ================================================================ */ | |
177 | ||
178 | ||
179 | /* atari_atari(color, *move) looks for a series of ataris on | |
180 | * strings of the other color culminating in the capture of | |
181 | * a string which is thought to be invulnerable by the reading | |
182 | * code. Such a move can be missed since it may be that each | |
183 | * string involved individually can be rescued, but nevertheless | |
184 | * one of them can be caught. The simplest example is a double | |
185 | * atari. The return value is the size of the smallest opponent | |
186 | * worm. | |
187 | * | |
188 | * One danger with this scheme is that the first atari | |
189 | * tried might be irrelevant to the actual combination. | |
190 | * To detect this possibility, once we've found a combination, | |
191 | * we mark that first move as forbidden, then try again. If | |
192 | * no combination of the same size or larger turns up, then | |
193 | * the first move was indeed essential. | |
194 | * | |
195 | * For the purpose of the move generation, returns the | |
196 | * size of the smallest of the worms under attack. | |
197 | */ | |
198 | ||
199 | /* Local struct to keep track of atari_atari attack moves and what | |
200 | * they threat. | |
201 | */ | |
202 | #define AA_MAX_TARGETS_PER_MOVE 4 | |
203 | ||
204 | #define MAX_AA_DIST 5 | |
205 | ||
206 | struct aa_move { | |
207 | int move; | |
208 | int target[AA_MAX_TARGETS_PER_MOVE]; | |
209 | }; | |
210 | ||
211 | #define AA_MAX_MOVES MAX_BOARD * MAX_BOARD | |
212 | static int aa_status[BOARDMAX]; /* ALIVE, DEAD or CRITICAL */ | |
213 | static int forbidden[BOARDMAX]; | |
214 | static int aa_values[BOARDMAX]; | |
215 | static void compute_aa_status(int color, | |
216 | const signed char safe_stones[BOARDMAX]); | |
217 | static void compute_aa_values(int color); | |
218 | static int get_aa_status(int pos); | |
219 | static int do_atari_atari(int color, int *attack_point, int *defense_point, | |
220 | signed char all_potential_defenses[BOARDMAX], | |
221 | int last_friendly, int save_verbose, int minsize, | |
222 | signed char goal[BOARDMAX]); | |
223 | static int atari_atari_succeeded(int color, int *attack_point, | |
224 | int *defense_point, int last_friendly, | |
225 | int save_verbose, int minsize); | |
226 | static void atari_atari_find_attack_moves(int color, int minsize, | |
227 | struct aa_move attacks[AA_MAX_MOVES], | |
228 | signed char goal[BOARDMAX]); | |
229 | static void atari_atari_attack_patterns(int color, int minsize, | |
230 | struct aa_move attacks[AA_MAX_MOVES], | |
231 | signed char goal[BOARDMAX]); | |
232 | static void atari_atari_attack_callback(int anchor, int color, | |
233 | struct pattern *pattern, | |
234 | int ll, void *data); | |
235 | static int atari_atari_find_defense_moves(int targets[AA_MAX_TARGETS_PER_MOVE], | |
236 | int moves[AA_MAX_MOVES]); | |
237 | static int get_aa_value(int str); | |
238 | static int update_aa_goal(signed char goal[BOARDMAX], | |
239 | signed char new_goal[BOARDMAX], | |
240 | int apos, int color); | |
241 | static void aa_init_moves(struct aa_move attacks[AA_MAX_MOVES]); | |
242 | static void aa_add_move(struct aa_move attacks[AA_MAX_MOVES], | |
243 | int move, int target); | |
244 | static int aa_move_known(struct aa_move attacks[AA_MAX_MOVES], | |
245 | int move, int target); | |
246 | static void aa_sort_moves(struct aa_move attacks[AA_MAX_MOVES]); | |
247 | ||
248 | /* Set to 1 if you want verbose traces from this function. */ | |
249 | ||
250 | int | |
251 | atari_atari(int color, int *attack_move, signed char defense_moves[BOARDMAX], | |
252 | int save_verbose) | |
253 | { | |
254 | int other = OTHER_COLOR(color); | |
255 | int apos; | |
256 | int dpos; | |
257 | int aa_val; | |
258 | signed char saved_defense_moves[BOARDMAX]; | |
259 | ||
260 | /* Collect worm statuses of opponent's worms. We need to | |
261 | * know this because we only want to report unexpected | |
262 | * results. For example, we do not want to report success | |
263 | * if we find we can kill a worm which is already dead. | |
264 | * The worm status of empty points is set to UNKNOWN to signal | |
265 | * that stones added along the way need special attention. | |
266 | */ | |
267 | if (aa_depth < 2) | |
268 | return 0; | |
269 | memset(forbidden, 0, sizeof(forbidden)); | |
270 | ||
271 | compute_aa_status(color, NULL); | |
272 | compute_aa_values(color); | |
273 | ||
274 | if (defense_moves) | |
275 | memset(defense_moves, 0, BOARDMAX); | |
276 | aa_val = do_atari_atari(color, &apos, &dpos, defense_moves, NO_MOVE, | |
277 | save_verbose, 0, NULL); | |
278 | ||
279 | if (aa_val == 0) | |
280 | return 0; | |
281 | ||
282 | /* We try excluding the first atari found and see if the | |
283 | * combination still works. Repeat until failure. | |
284 | */ | |
285 | while (1) { | |
286 | int new_aa_val; | |
287 | ||
288 | if (attack_move) | |
289 | *attack_move = apos; | |
290 | ||
291 | forbidden[apos] = 1; | |
292 | if (defense_moves) { | |
293 | memcpy(saved_defense_moves, defense_moves, BOARDMAX); | |
294 | memset(defense_moves, 0, BOARDMAX); | |
295 | } | |
296 | new_aa_val = do_atari_atari(color, &apos, &dpos, defense_moves, NO_MOVE, | |
297 | save_verbose, aa_val, NULL); | |
298 | ||
299 | /* The last do_atari_atari call fails. When do_atari_atari fails, | |
300 | * it does not change the value of (apos), so these correspond | |
301 | * to a move that works and is necessary. | |
302 | */ | |
303 | if (new_aa_val == 0) | |
304 | break; | |
305 | else | |
306 | aa_val = new_aa_val; | |
307 | } | |
308 | ||
309 | if (defense_moves) { | |
310 | int pos; | |
311 | memcpy(defense_moves, saved_defense_moves, BOARDMAX); | |
312 | /* defense_moves[] contains potential defense moves. Now we | |
313 | * examine which of them really work. | |
314 | */ | |
315 | forbidden[apos] = 0; | |
316 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
317 | if (!ON_BOARD(pos) || !defense_moves[pos]) | |
318 | continue; | |
319 | ||
320 | if (!trymove(pos, other, "atari_atari", NO_MOVE)) { | |
321 | defense_moves[pos] = 0; | |
322 | if (save_verbose) | |
323 | gprintf("%1m deleted defense point, illegal\n", pos); | |
324 | continue; | |
325 | } | |
326 | ||
327 | if (attack(pos, NULL)) { | |
328 | defense_moves[pos] = 0; | |
329 | popgo(); | |
330 | if (save_verbose) | |
331 | gprintf("%1m deleted defense point, unsafe\n", pos); | |
332 | continue; | |
333 | } | |
334 | ||
335 | if (do_atari_atari(color, &apos, &dpos, NULL, NO_MOVE, | |
336 | save_verbose, aa_val, NULL) > 0) { | |
337 | if (save_verbose) | |
338 | gprintf("%1m deleted defense point, didn't work\n", pos); | |
339 | defense_moves[pos] = 0; | |
340 | } | |
341 | ||
342 | popgo(); | |
343 | } | |
344 | } | |
345 | return aa_val; | |
346 | } | |
347 | ||
348 | ||
349 | /* Wrapper around atari_atari_blunder_size. Check whether a | |
350 | * combination attack of size at least minsize appears after move | |
351 | * at (move) has been made. | |
352 | * The arrays saved_dragons[] and saved_worms[] should be one for | |
353 | * stones belonging to dragons or worms respectively, which are | |
354 | * supposedly saved by (move). | |
355 | * | |
356 | * FIXME: We probably want to change the calling convention of this | |
357 | * function to return all defense moves. | |
358 | */ | |
359 | int | |
360 | atari_atari_confirm_safety(int color, int move, int *defense, int minsize, | |
361 | const signed char saved_dragons[BOARDMAX], | |
362 | const signed char saved_worms[BOARDMAX]) | |
363 | { | |
364 | signed char safe_stones[BOARDMAX]; | |
365 | signed char defense_moves[BOARDMAX]; | |
366 | int pos; | |
367 | int blunder_size; | |
368 | ||
369 | mark_safe_stones(color, move, saved_dragons, saved_worms, safe_stones); | |
370 | blunder_size = atari_atari_blunder_size(color, move, defense_moves, | |
371 | safe_stones); | |
372 | ||
373 | if (defense) { | |
374 | /* Return one arbitrary defense move. */ | |
375 | *defense = NO_MOVE; | |
376 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
377 | if (ON_BOARD(pos) && defense_moves[pos]) { | |
378 | *defense = pos; | |
379 | break; | |
380 | } | |
381 | } | |
382 | ||
383 | return blunder_size >= minsize; | |
384 | } | |
385 | ||
386 | ||
387 | /* This function checks whether any new combination attack appears after | |
388 | * move at (move) has been made, and returns its size (in points). | |
389 | * safe_stones marks which of our stones are supposedly safe after this move. | |
390 | */ | |
391 | int | |
392 | atari_atari_blunder_size(int color, int move, | |
393 | signed char defense_moves[BOARDMAX], | |
394 | const signed char safe_stones[BOARDMAX]) | |
395 | { | |
396 | int apos; | |
397 | int defense_point = NO_MOVE; | |
398 | int aa_val, after_aa_val; | |
399 | int other = OTHER_COLOR(color); | |
400 | signed char defense_points[BOARDMAX]; | |
401 | int last_forbidden = NO_MOVE; | |
402 | ||
403 | /* If aa_depth is too small, we can't see any combination attacks, | |
404 | * so in this respect the move is safe enough. | |
405 | */ | |
406 | if (aa_depth < 2) | |
407 | return 0; | |
408 | ||
409 | memset(forbidden, 0, sizeof(forbidden)); | |
410 | memset(defense_points, 0, sizeof(defense_points)); | |
411 | ||
412 | compute_aa_status(other, safe_stones); | |
413 | compute_aa_values(other); | |
414 | ||
415 | /* Accept illegal ko capture here. */ | |
416 | if (!tryko(move, color, NULL)) | |
417 | /* Really shouldn't happen. */ | |
418 | abortgo(__FILE__, __LINE__, "trymove", move); | |
419 | ||
420 | increase_depth_values(); | |
421 | ||
422 | aa_val = do_atari_atari(other, &apos, &defense_point, defense_points, | |
423 | NO_MOVE, 0, 0, NULL); | |
424 | after_aa_val = aa_val; | |
425 | ||
426 | if (aa_val == 0 || defense_point == NO_MOVE) { | |
427 | ||
428 | /* No sufficiently large combination attack, so the move is safe from | |
429 | * this danger. | |
430 | * | |
431 | * On rare occasions do_atari_atari might find a combination | |
432 | * but no defense. In this case we assume that the combination | |
433 | * is illusory. | |
434 | */ | |
435 | ||
436 | popgo(); | |
437 | decrease_depth_values(); | |
438 | return 0; | |
439 | } | |
440 | ||
441 | while (aa_val >= after_aa_val && defense_point != NO_MOVE) { | |
442 | /* Try dropping moves from the combination and see if it still | |
443 | * works. What we really want is to get the proper defense move | |
444 | * into (*defense). | |
445 | */ | |
446 | forbidden[apos] = 1; | |
447 | last_forbidden = apos; | |
448 | aa_val = do_atari_atari(other, &apos, &defense_point, NULL, | |
449 | NO_MOVE, 0, aa_val, NULL); | |
450 | } | |
451 | ||
452 | popgo(); | |
453 | decrease_depth_values(); | |
454 | /* We know that a combination exists, but we don't know if | |
455 | * the original move at (aa) was really relevant. So we | |
456 | * try omitting it and see if a combination is still found. | |
457 | */ | |
458 | compute_aa_status(other, NULL); | |
459 | compute_aa_values(other); | |
460 | forbidden[last_forbidden] = 0; | |
461 | aa_val = do_atari_atari(other, NULL, NULL, NULL, NO_MOVE, 0, 0, NULL); | |
462 | if (aa_val >= after_aa_val) | |
463 | return 0; | |
464 | ||
465 | /* Try the potential defense moves to see which are effective. */ | |
466 | if (defense_moves) { | |
467 | int pos; | |
468 | /* defense_points[] contains potential defense moves. Now we | |
469 | * examine which of them really work. | |
470 | */ | |
471 | ||
472 | /* FIXME: Maybe these should be moved after the tryko() below? */ | |
473 | compute_aa_status(other, safe_stones); | |
474 | compute_aa_values(other); | |
475 | ||
476 | memcpy(defense_moves, defense_points, sizeof(defense_points)); | |
477 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
478 | if (!ON_BOARD(pos) || !defense_moves[pos] || pos == move) | |
479 | continue; | |
480 | ||
481 | if (!trymove(pos, color, "atari_atari", NO_MOVE)) { | |
482 | defense_moves[pos] = 0; | |
483 | continue; | |
484 | } | |
485 | increase_depth_values(); | |
486 | ||
487 | if (attack(pos, NULL)) { | |
488 | defense_moves[pos] = 0; | |
489 | decrease_depth_values(); | |
490 | popgo(); | |
491 | continue; | |
492 | } | |
493 | ||
494 | /* Accept illegal ko capture here. */ | |
495 | if (!tryko(move, color, NULL)) | |
496 | /* Really shouldn't happen. */ | |
497 | abortgo(__FILE__, __LINE__, "trymove", move); | |
498 | increase_depth_values(); | |
499 | ||
500 | if (do_atari_atari(other, &apos, &defense_point, NULL, NO_MOVE, | |
501 | 0, after_aa_val, NULL) >= after_aa_val) | |
502 | defense_moves[pos] = 0; | |
503 | ||
504 | decrease_depth_values(); | |
505 | popgo(); | |
506 | decrease_depth_values(); | |
507 | popgo(); | |
508 | } | |
509 | } | |
510 | ||
511 | return after_aa_val - aa_val; | |
512 | } | |
513 | ||
514 | ||
515 | /* ---------------------------------------------------------------- */ | |
516 | /* Helper functions for atari_atari. */ | |
517 | /* ---------------------------------------------------------------- */ | |
518 | ||
519 | ||
520 | /* Helper function for computing the aa_status for all opponent's strings. | |
521 | * If safe_stones is given, we just copy the information from there. | |
522 | * If called at stackp > 0, safe_stones must be provided since the | |
523 | * dragon_data is not valid then. | |
524 | */ | |
525 | ||
526 | static void | |
527 | compute_aa_status(int color, const signed char safe_stones[BOARDMAX]) | |
528 | { | |
529 | int other = OTHER_COLOR(color); | |
530 | int pos; | |
531 | SGFTree *save_sgf_dumptree = sgf_dumptree; | |
532 | int save_count_variations = count_variations; | |
533 | int save_verbose = verbose; | |
534 | ||
535 | gg_assert(safe_stones || stackp == 0); | |
536 | ||
537 | sgf_dumptree = NULL; | |
538 | count_variations = 0; | |
539 | if (verbose) | |
540 | verbose--; | |
541 | ||
542 | /* Collect worm statuses of opponent's worms. We need to | |
543 | * know this because we only want to report unexpected | |
544 | * results. For example, we do not want to report success | |
545 | * if we find we can kill a worm which is already dead. | |
546 | * The worm status of empty points is set to UNKNOWN to signal | |
547 | * that stones added along the way need special attention. | |
548 | */ | |
549 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
550 | if (board[pos] == other) { | |
551 | if (safe_stones) { | |
552 | if (safe_stones[pos]) | |
553 | aa_status[pos] = ALIVE; | |
554 | else | |
555 | aa_status[pos] = DEAD; | |
556 | } | |
557 | else { | |
558 | if (dragon[pos].status == DEAD) | |
559 | aa_status[pos] = DEAD; | |
560 | else if (dragon[pos].status == CRITICAL) | |
561 | aa_status[pos] = CRITICAL; | |
562 | else if (worm[pos].attack_codes[0] != 0) { | |
563 | if (worm[pos].defense_codes[0] != 0) | |
564 | aa_status[pos] = CRITICAL; | |
565 | else | |
566 | aa_status[pos] = DEAD; | |
567 | } | |
568 | else | |
569 | aa_status[pos] = ALIVE; | |
570 | } | |
571 | } | |
572 | else if (ON_BOARD(pos)) | |
573 | aa_status[pos] = UNKNOWN; | |
574 | } | |
575 | ||
576 | /* reclassify a worm with 2 liberties as INSUBSTANTIAL if capturing | |
577 | * it does not result in a live group. | |
578 | */ | |
579 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
580 | if (board[pos] == other | |
581 | && find_origin(pos) == pos | |
582 | && countlib(pos) == 2 | |
583 | && aa_status[pos] == ALIVE) { | |
584 | int libs[2]; | |
585 | findlib(pos, 2, libs); | |
586 | /* Don't waste time running owl_substantial() if we can't safely | |
587 | * atari anyway. | |
588 | */ | |
589 | if (is_self_atari(libs[0], color) | |
590 | && is_self_atari(libs[1], color)) | |
591 | continue; | |
592 | ||
593 | if (!owl_substantial(pos)) { | |
594 | int pos2; | |
595 | for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) | |
596 | if (board[pos2] == other && find_origin(pos2) == pos) | |
597 | aa_status[pos2] = INSUBSTANTIAL; | |
598 | } | |
599 | } | |
600 | } | |
601 | ||
602 | if (debug & DEBUG_ATARI_ATARI) { | |
603 | gprintf("compute_aa_status() for %C\n", color); | |
604 | gprintf("aa_status: (ALIVE worms not listed)\n"); | |
605 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
606 | if (board[pos] == other && is_worm_origin(pos, pos)) { | |
607 | const char *status = "UNKNOWN (shouldn't happen)"; | |
608 | if (aa_status[pos] == DEAD) | |
609 | status = "DEAD"; | |
610 | else if (aa_status[pos] == CRITICAL) | |
611 | status = "CRITICAL"; | |
612 | else if (aa_status[pos] == INSUBSTANTIAL) | |
613 | status = "INSUBSTANTIAL"; | |
614 | ||
615 | if (aa_status[pos] != ALIVE) | |
616 | gprintf("%1M: %s\n", pos, status); | |
617 | } | |
618 | } | |
619 | } | |
620 | ||
621 | sgf_dumptree = save_sgf_dumptree; | |
622 | count_variations = save_count_variations; | |
623 | verbose = save_verbose; | |
624 | } | |
625 | ||
626 | ||
627 | /* Helper function for retrieving the aa_status for a string. We can't | |
628 | * reliably do this simply by looking up aa_status[pos] since this is | |
629 | * only valid at vertices which were non-empty at the start of the | |
630 | * reading. For later added stones, we need to find their aa_status by | |
631 | * locating a part of the string which was a worm at the beginning of | |
632 | * the reading. | |
633 | */ | |
634 | ||
635 | static int | |
636 | get_aa_status(int pos) | |
637 | { | |
638 | int stones[MAX_BOARD * MAX_BOARD]; | |
639 | int num_stones; | |
640 | int k; | |
641 | ||
642 | if (aa_status[pos] != UNKNOWN) | |
643 | return aa_status[pos]; | |
644 | ||
645 | num_stones = findstones(pos, MAX_BOARD * MAX_BOARD, stones); | |
646 | for (k = 0; k < num_stones; k++) | |
647 | if (aa_status[stones[k]] != UNKNOWN) | |
648 | return aa_status[stones[k]]; | |
649 | ||
650 | return UNKNOWN; | |
651 | } | |
652 | ||
653 | ||
654 | ||
655 | /* Helper function for atari_atari. Here worms is the number of | |
656 | * opponent worms involved in the combination, and (last_friendly) is | |
657 | * the location of the last friendly move played. Moves marked | |
658 | * with the forbidden array are not tried. If no move is found, | |
659 | * the values of *attack_point and *defense_point are not changed. | |
660 | * | |
661 | * If not NULL, *attack_point is left pointing to the location of the | |
662 | * attacking move, and *defense_point points to a move defending the | |
663 | * combination. In rare cases a defensive move might not be found. If | |
664 | * a non-static function calling do_atari_atari gets a return value of | |
665 | * 1 but NO_MOVE as the defense point, this should be treated as | |
666 | * equivalent to a return value of 0. | |
667 | * | |
668 | * The goal array limits where we are allowed to consider threats. | |
669 | * Only strings for which goal is set to 1 may be threatened. If goal | |
670 | * is NULL, anything may be attacked. Thus goal is typically NULL when | |
671 | * do_atari_atari() is called from an external function. After the | |
672 | * first threat has been made, the goal array is set to one in a | |
673 | * neighborhood of the move and after subsequent threats it is | |
674 | * expanded with neighborhoods of those moves. The details of this can | |
675 | * be found in the function update_aa_goal(). | |
676 | */ | |
677 | ||
678 | static int | |
679 | do_atari_atari(int color, int *attack_point, int *defense_point, | |
680 | signed char all_potential_defenses[BOARDMAX], int last_friendly, | |
681 | int save_verbose, int minsize, signed char goal[BOARDMAX]) | |
682 | { | |
683 | int other = OTHER_COLOR(color); | |
684 | int k; | |
685 | struct aa_move attacks[AA_MAX_MOVES]; | |
686 | int num_defense_moves; | |
687 | int defense_moves[AA_MAX_MOVES]; | |
688 | int pos; | |
689 | SGFTree *save_sgf_dumptree; | |
690 | int save_count_variations; | |
691 | ||
692 | if (debug & DEBUG_ATARI_ATARI) { | |
693 | gprintf("%odo_atari_atari: "); | |
694 | dump_stack(); | |
695 | gprintf("%oforbidden moves: "); | |
696 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
697 | if (ON_BOARD(pos) && forbidden[pos]) | |
698 | gprintf("%o%1m ", pos); | |
699 | gprintf("\n"); | |
700 | gprintf("%ogoal: "); | |
701 | if (!goal) | |
702 | gprintf("none"); | |
703 | else { | |
704 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
705 | if (ON_BOARD(pos) && goal[pos]) | |
706 | gprintf("%o%1m ", pos); | |
707 | } | |
708 | gprintf("\n"); | |
709 | } | |
710 | ||
711 | /* First look for strings adjacent to the last friendly move played | |
712 | * (or to another stone in the same string) which can be | |
713 | * unexpectedly attacked. If so, the combination attack | |
714 | * has succeeded. | |
715 | */ | |
716 | if (last_friendly != NO_MOVE) { | |
717 | int retval; | |
718 | save_sgf_dumptree = sgf_dumptree; | |
719 | save_count_variations = count_variations; | |
720 | sgf_dumptree = NULL; | |
721 | count_variations = 0; | |
722 | retval = atari_atari_succeeded(color, attack_point, defense_point, | |
723 | last_friendly, save_verbose, minsize); | |
724 | sgf_dumptree = save_sgf_dumptree; | |
725 | count_variations = save_count_variations; | |
726 | if (retval != 0) { | |
727 | if (sgf_dumptree) | |
728 | /* FIXME: Better message. */ | |
729 | sgftreeAddComment(sgf_dumptree, "attack found"); | |
730 | return retval; | |
731 | } | |
732 | } | |
733 | ||
734 | if (stackp > aa_depth) | |
735 | return 0; | |
736 | ||
737 | /* Find attack moves. These are typically ataris but may also be | |
738 | * more general. | |
739 | */ | |
740 | save_sgf_dumptree = sgf_dumptree; | |
741 | save_count_variations = count_variations; | |
742 | sgf_dumptree = NULL; | |
743 | count_variations = 0; | |
744 | atari_atari_find_attack_moves(color, minsize, attacks, goal); | |
745 | sgf_dumptree = save_sgf_dumptree; | |
746 | count_variations = save_count_variations; | |
747 | ||
748 | /* Try the attacking moves and let the opponent defend. Then call | |
749 | * ourselves recursively. | |
750 | */ | |
751 | for (k = 0; attacks[k].move != NO_MOVE; k++) { | |
752 | int aa_val; | |
753 | int str = attacks[k].target[0]; | |
754 | int apos = attacks[k].move; | |
755 | int bpos; | |
756 | int r; | |
757 | ||
758 | if (!trymove(apos, color, "do_atari_atari-A", str)) | |
759 | continue; | |
760 | ||
761 | if (all_potential_defenses) { | |
762 | all_potential_defenses[apos] = 1; | |
763 | if (countlib(apos) <= 2) { | |
764 | int libs[2]; | |
765 | int num_libs = findlib(apos, 2, libs); | |
766 | all_potential_defenses[libs[0]] = 1; | |
767 | if (num_libs == 2) | |
768 | all_potential_defenses[libs[1]] = 1; | |
769 | } | |
770 | } | |
771 | ||
772 | if (!IS_STONE(board[str])) { | |
773 | /* Error situation. This could be caused by a wrong matcher status. */ | |
774 | if (save_verbose || (debug & DEBUG_ATARI_ATARI)) | |
775 | gprintf("%oError condition found by atari_atari\n"); | |
776 | popgo(); | |
777 | return 0; | |
778 | } | |
779 | ||
780 | /* Try to defend the stone (str) which is threatened. */ | |
781 | aa_val = get_aa_value(str); | |
782 | ||
783 | /* Pick up defense moves. */ | |
784 | save_sgf_dumptree = sgf_dumptree; | |
785 | save_count_variations = count_variations; | |
786 | sgf_dumptree = NULL; | |
787 | count_variations = 0; | |
788 | num_defense_moves = atari_atari_find_defense_moves(attacks[k].target, | |
789 | defense_moves); | |
790 | sgf_dumptree = save_sgf_dumptree; | |
791 | count_variations = save_count_variations; | |
792 | ||
793 | for (r = 0; r < num_defense_moves; r++) { | |
794 | bpos = defense_moves[r]; | |
795 | ||
796 | if (all_potential_defenses) | |
797 | all_potential_defenses[bpos] = 1; | |
798 | ||
799 | if (trymove(bpos, other, "do_atari_atari-B", str)) { | |
800 | int new_aa_val; | |
801 | signed char new_goal[BOARDMAX]; | |
802 | /* These moves may have been irrelevant for later | |
803 | * reading, so in order to avoid horizon problems, we | |
804 | * need to temporarily increase the depth values. | |
805 | */ | |
806 | modify_depth_values(2); | |
807 | update_aa_goal(goal, new_goal, apos, color); | |
808 | new_aa_val = do_atari_atari(color, NULL, defense_point, | |
809 | all_potential_defenses, | |
810 | apos, save_verbose, minsize, new_goal); | |
811 | modify_depth_values(-2); | |
812 | if (new_aa_val < aa_val) | |
813 | aa_val = new_aa_val; | |
814 | popgo(); | |
815 | } | |
816 | ||
817 | /* Defense successful, no need to try any further. */ | |
818 | if (aa_val == 0) | |
819 | break; | |
820 | } | |
821 | ||
822 | /* Undo the attacking move. */ | |
823 | popgo(); | |
824 | ||
825 | if (aa_val == 0) | |
826 | continue; | |
827 | ||
828 | /* atari_atari successful */ | |
829 | if (num_defense_moves == 0) { | |
830 | if (save_verbose || (debug & DEBUG_ATARI_ATARI)) { | |
831 | gprintf("%oThe worm %1m can be attacked at %1m after ", str, apos); | |
832 | dump_stack(); | |
833 | } | |
834 | if (sgf_dumptree) | |
835 | /* FIXME: Better message. */ | |
836 | sgftreeAddComment(sgf_dumptree, "attack found"); | |
837 | } | |
838 | ||
839 | if (attack_point) | |
840 | *attack_point = apos; | |
841 | ||
842 | if (defense_point) { | |
843 | save_sgf_dumptree = sgf_dumptree; | |
844 | save_count_variations = count_variations; | |
845 | sgf_dumptree = NULL; | |
846 | count_variations = 0; | |
847 | ||
848 | if (!find_defense(str, defense_point)) | |
849 | *defense_point = NO_MOVE; | |
850 | ||
851 | /* If no defense point is known and (apos) is a safe | |
852 | * move for other, it probably defends the combination. | |
853 | */ | |
854 | if ((*defense_point == NO_MOVE || !safe_move(*defense_point, other)) | |
855 | && safe_move(apos, other)) | |
856 | *defense_point = apos; | |
857 | ||
858 | sgf_dumptree = save_sgf_dumptree; | |
859 | count_variations = save_count_variations; | |
860 | } | |
861 | ||
862 | DEBUG(DEBUG_ATARI_ATARI, "%oreturn value:%d (%1m)\n", aa_val, str); | |
863 | return aa_val; | |
864 | } | |
865 | ||
866 | /* No atari_atari attack. */ | |
867 | return 0; | |
868 | } | |
869 | ||
870 | ||
871 | static int | |
872 | atari_atari_succeeded(int color, int *attack_point, int *defense_point, | |
873 | int last_friendly, int save_verbose, int minsize) | |
874 | { | |
875 | int pos; | |
876 | int apos; | |
877 | int other = OTHER_COLOR(color); | |
878 | ||
879 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
880 | if (board[pos] != other) | |
881 | continue; | |
882 | ||
883 | if (pos != find_origin(pos)) | |
884 | continue; | |
885 | ||
886 | if (minsize > 0 | |
887 | && get_aa_value(pos) < minsize) | |
888 | continue; | |
889 | ||
890 | if (get_aa_status(pos) != ALIVE) | |
891 | continue; | |
892 | ||
893 | if (board[last_friendly] != EMPTY | |
894 | && !adjacent_strings(last_friendly, pos)) | |
895 | continue; | |
896 | ||
897 | if (board[last_friendly] == EMPTY | |
898 | && !liberty_of_string(last_friendly, pos)) | |
899 | continue; | |
900 | ||
901 | if (debug & DEBUG_ATARI_ATARI) | |
902 | gprintf("Considering attack of %1m. depth = %d.\n", pos, depth); | |
903 | ||
904 | if (attack(pos, &apos) && !forbidden[apos]) { | |
905 | if (save_verbose || (debug & DEBUG_ATARI_ATARI)) { | |
906 | gprintf("%oThe worm %1m can be attacked at %1m after ", pos, apos); | |
907 | dump_stack(); | |
908 | } | |
909 | if (attack_point) | |
910 | *attack_point = apos; | |
911 | ||
912 | /* We look for a move defending the combination. | |
913 | * Normally this is found by find_defense but failing | |
914 | * that, if the attacking move is a safe move for color, | |
915 | * it probably defends. | |
916 | */ | |
917 | if (defense_point) { | |
918 | if (!find_defense(pos, defense_point)) { | |
919 | if (safe_move(apos, other)) | |
920 | *defense_point = apos; | |
921 | else | |
922 | *defense_point = NO_MOVE; | |
923 | } | |
924 | } | |
925 | ||
926 | DEBUG(DEBUG_ATARI_ATARI, "%oreturn value:%d (%1m)\n", | |
927 | get_aa_value(pos), pos); | |
928 | return get_aa_value(pos); | |
929 | } | |
930 | } | |
931 | ||
932 | return 0; | |
933 | } | |
934 | ||
935 | #define MAX_THREAT_MOVES MAX_TACTICAL_POINTS | |
936 | ||
937 | static void | |
938 | atari_atari_find_attack_moves(int color, int minsize, | |
939 | struct aa_move attacks[AA_MAX_MOVES], | |
940 | signed char goal[BOARDMAX]) | |
941 | { | |
942 | int k; | |
943 | int r; | |
944 | ||
945 | aa_init_moves(attacks); | |
946 | ||
947 | atari_atari_attack_patterns(color, minsize, attacks, goal); | |
948 | ||
949 | /* Sort the attack moves. */ | |
950 | aa_sort_moves(attacks); | |
951 | ||
952 | if (debug & DEBUG_ATARI_ATARI) { | |
953 | gprintf("Attack moves:"); | |
954 | for (k = 0; k < AA_MAX_MOVES && attacks[k].move != NO_MOVE; k++) { | |
955 | gprintf("%o %1m(", attacks[k].move); | |
956 | for (r = 0; r < AA_MAX_TARGETS_PER_MOVE; r++) { | |
957 | if (attacks[k].target[r] == NO_MOVE) | |
958 | break; | |
959 | gprintf("%o%s%1m", r == 0 ? "" : ",", attacks[k].target[r]); | |
960 | } | |
961 | gprintf("%o)"); | |
962 | } | |
963 | gprintf("%o\n"); | |
964 | } | |
965 | } | |
966 | ||
967 | /* FIXME: Move these to a struct and pass to callback through the | |
968 | * *data parameter. | |
969 | */ | |
970 | static int current_minsize; | |
971 | static struct aa_move *current_attacks; | |
972 | static int conditional_attack_point[BOARDMAX]; | |
973 | ||
974 | static void | |
975 | atari_atari_attack_patterns(int color, int minsize, | |
976 | struct aa_move attacks[AA_MAX_MOVES], | |
977 | signed char goal[BOARDMAX]) | |
978 | { | |
979 | signed char revised_goal[BOARDMAX]; | |
980 | current_minsize = minsize; | |
981 | current_attacks = attacks; | |
982 | memset(conditional_attack_point, 0, sizeof(conditional_attack_point)); | |
983 | ||
984 | /* If goal is NULL and there are forbidden moves we need to compute | |
985 | * a new goal around the forbidden moves. | |
986 | */ | |
987 | if (goal == NULL && update_aa_goal(goal, revised_goal, NO_MOVE, color)) | |
988 | goal = revised_goal; | |
989 | ||
990 | #if 0 | |
991 | if (goal != NULL) { | |
992 | int pos; | |
993 | gprintf("goal:"); | |
994 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
995 | if (ON_BOARD(pos) && goal[pos]) | |
996 | gprintf("%o %1m", pos); | |
997 | gprintf("%o\n"); | |
998 | } | |
999 | #endif | |
1000 | ||
1001 | matchpat(atari_atari_attack_callback, color, &aa_attackpat_db, NULL, goal); | |
1002 | } | |
1003 | ||
1004 | /* Try to attack every X string in the pattern, whether there is an attack | |
1005 | * before or not. Only exclude already known attacking moves. | |
1006 | */ | |
1007 | static void | |
1008 | atari_atari_attack_callback(int anchor, int color, | |
1009 | struct pattern *pattern, int ll, void *data) | |
1010 | { | |
1011 | int move; | |
1012 | int k; | |
1013 | UNUSED(data); | |
1014 | ||
1015 | move = AFFINE_TRANSFORM(pattern->move_offset, ll, anchor); | |
1016 | ||
1017 | if (forbidden[move]) | |
1018 | return; | |
1019 | ||
1020 | /* If the pattern has a constraint, call the autohelper to see | |
1021 | * if the pattern must be rejected. | |
1022 | */ | |
1023 | if (pattern->autohelper_flag & HAVE_CONSTRAINT) | |
1024 | if (!pattern->autohelper(ll, move, color, 0)) | |
1025 | return; | |
1026 | ||
1027 | /* If the pattern has a helper, call it to see if the pattern must | |
1028 | * be rejected. | |
1029 | */ | |
1030 | if (pattern->helper) | |
1031 | if (!pattern->helper(pattern, ll, move, color)) | |
1032 | return; | |
1033 | ||
1034 | /* Loop through pattern elements in search of X strings to | |
1035 | * threaten to attack. | |
1036 | */ | |
1037 | for (k = 0; k < pattern->patlen; ++k) { /* match each point */ | |
1038 | if (pattern->patn[k].att == ATT_X) { | |
1039 | /* transform pattern real coordinate */ | |
1040 | int str = find_origin(AFFINE_TRANSFORM(pattern->patn[k].offset, | |
1041 | ll, anchor)); | |
1042 | ||
1043 | if (current_minsize > 0 | |
1044 | && get_aa_value(str) < current_minsize) | |
1045 | continue; | |
1046 | ||
1047 | if (aa_move_known(current_attacks, move, str)) | |
1048 | continue; | |
1049 | ||
1050 | if (get_aa_status(str) != ALIVE) | |
1051 | continue; | |
1052 | ||
1053 | /* Usually we don't want to play self atari. However, if we | |
1054 | * capture in snapback it's okay. For s class patterns we don't | |
1055 | * have this requirement. | |
1056 | */ | |
1057 | if (!(pattern->class & CLASS_s) && is_self_atari(move, color)) { | |
1058 | if (countlib(str) > 2) | |
1059 | continue; | |
1060 | ||
1061 | if (!safe_move(move, color)) | |
1062 | continue; | |
1063 | } | |
1064 | ||
1065 | /* | |
1066 | * Play (move) and see if there is an attack. | |
1067 | */ | |
1068 | if (trymove(move, color, "attack_callback", str)) { | |
1069 | int acode; | |
1070 | int attack_point = NO_MOVE; | |
1071 | ||
1072 | if (!board[str]) | |
1073 | acode = WIN; | |
1074 | else | |
1075 | acode = attack(str, &attack_point); | |
1076 | ||
1077 | popgo(); | |
1078 | ||
1079 | if (acode != 0) { | |
1080 | if ((pattern->class & CLASS_c) | |
1081 | && !aa_move_known(current_attacks, move, NO_MOVE)) { | |
1082 | /* Conditional pattern. */ | |
1083 | DEBUG(DEBUG_ATARI_ATARI, | |
1084 | "aa_attack pattern %s+%d (conditional) found threat on %1m at %1m with code %d\n", | |
1085 | pattern->name, ll, str, move, acode); | |
1086 | if (conditional_attack_point[move] == NO_MOVE) | |
1087 | conditional_attack_point[move] = str; | |
1088 | else if (conditional_attack_point[move] != str) { | |
1089 | aa_add_move(current_attacks, move, | |
1090 | conditional_attack_point[move]); | |
1091 | aa_add_move(current_attacks, move, str); | |
1092 | } | |
1093 | } | |
1094 | else { | |
1095 | aa_add_move(current_attacks, move, str); | |
1096 | DEBUG(DEBUG_ATARI_ATARI, | |
1097 | "aa_attack pattern %s+%d found threat on %1m at %1m with code %d\n", | |
1098 | pattern->name, ll, str, move, acode); | |
1099 | } | |
1100 | } | |
1101 | } | |
1102 | } | |
1103 | } | |
1104 | } | |
1105 | ||
1106 | ||
1107 | static int | |
1108 | atari_atari_find_defense_moves(int targets[AA_MAX_TARGETS_PER_MOVE], | |
1109 | int moves[AA_MAX_MOVES]) | |
1110 | { | |
1111 | int num_moves = 0; | |
1112 | int move; | |
1113 | int k; | |
1114 | int liberties; | |
1115 | int libs[4]; | |
1116 | int neighbors; | |
1117 | int adjs[MAXCHAIN]; | |
1118 | int mx[BOARDMAX]; | |
1119 | int r, s; | |
1120 | ||
1121 | memset(mx, 0, sizeof(mx)); | |
1122 | ||
1123 | for (r = 0; r < AA_MAX_TARGETS_PER_MOVE && targets[r] != NO_MOVE; r++) { | |
1124 | int str = targets[r]; | |
1125 | ||
1126 | /* If the attack move happened to remove (str), there's no defense. */ | |
1127 | if (board[str] == EMPTY) | |
1128 | continue; | |
1129 | ||
1130 | /* Because we know (str) is threatened there is an | |
1131 | * attack and we can be sure find_defense() will give a | |
1132 | * useful defense point if it returns non-zero. Usually we | |
1133 | * would need to call attack_and_defend() to be certain of | |
1134 | * this. | |
1135 | */ | |
1136 | if (!find_defense(str, &move)) | |
1137 | continue; | |
1138 | moves[num_moves++] = move; | |
1139 | if (num_moves == AA_MAX_MOVES) | |
1140 | return num_moves; | |
1141 | mx[move] = 1; | |
1142 | ||
1143 | /* Consider all moves to attack a neighbor or to play on a liberty. */ | |
1144 | liberties = findlib(str, 4, libs); | |
1145 | for (k = 0; k < liberties; k++) { | |
1146 | if (!mx[libs[k]] | |
1147 | && trymove(libs[k], board[str], "aa_defend-A", str)) { | |
1148 | if (attack(str, NULL) == 0) { | |
1149 | moves[num_moves++] = libs[k]; | |
1150 | mx[libs[k]] = 1; | |
1151 | } | |
1152 | popgo(); | |
1153 | if (num_moves == AA_MAX_MOVES) | |
1154 | return num_moves; | |
1155 | } | |
1156 | } | |
1157 | ||
1158 | neighbors = chainlinks(str, adjs); | |
1159 | for (k = 0; k < neighbors; k++) { | |
1160 | int attack_point; | |
1161 | if (attack(adjs[k], &attack_point) == WIN | |
1162 | && !mx[attack_point]) { | |
1163 | moves[num_moves++] = attack_point; | |
1164 | if (num_moves == AA_MAX_MOVES) | |
1165 | return num_moves; | |
1166 | mx[attack_point] = 1; | |
1167 | } | |
1168 | ||
1169 | /* If the neighbor has at most three liberties, try all of them | |
1170 | * for defense, except self-ataris. | |
1171 | */ | |
1172 | liberties = findlib(adjs[k], 3, libs); | |
1173 | if (liberties <= 3) { | |
1174 | for (s = 0; s < liberties; s++) { | |
1175 | if (!mx[libs[s]] | |
1176 | && !is_self_atari(libs[s], board[str]) | |
1177 | && trymove(libs[s], board[str], "aa_defend-B", str)) { | |
1178 | if (attack(str, NULL) == 0) { | |
1179 | moves[num_moves++] = libs[s]; | |
1180 | mx[libs[s]] = 1; | |
1181 | } | |
1182 | popgo(); | |
1183 | if (num_moves == AA_MAX_MOVES) | |
1184 | return num_moves; | |
1185 | } | |
1186 | } | |
1187 | } | |
1188 | } | |
1189 | ||
1190 | if (debug & DEBUG_ATARI_ATARI) { | |
1191 | gprintf("Defense moves for %1m:", str); | |
1192 | for (k = 0; k < num_moves; k++) | |
1193 | gprintf("%o %1m", moves[k]); | |
1194 | gprintf("%o\n"); | |
1195 | } | |
1196 | } | |
1197 | ||
1198 | return num_moves; | |
1199 | } | |
1200 | ||
1201 | ||
1202 | /* Try to guess the value of the strings. We do this by adding twice | |
1203 | * the number of stones to the number of liberties and second order | |
1204 | * liberties within the moyo around the string. This is of course | |
1205 | * quite crude since it doesn't take into account any strategic | |
1206 | * effects, e.g. a string being cutting stones. | |
1207 | */ | |
1208 | static void | |
1209 | compute_aa_values(int color) | |
1210 | { | |
1211 | int other = OTHER_COLOR(color); | |
1212 | int pos; | |
1213 | int value; | |
1214 | int liberties; | |
1215 | int libs[MAXLIBS]; | |
1216 | int mx[BOARDMAX]; | |
1217 | int r, k; | |
1218 | ||
1219 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1220 | if (board[pos] != other | |
1221 | || pos != find_origin(pos) | |
1222 | || aa_status[pos] != ALIVE) { | |
1223 | aa_values[pos] = 0; | |
1224 | continue; | |
1225 | } | |
1226 | ||
1227 | memset(mx, 0, sizeof(mx)); | |
1228 | liberties = findlib(pos, MAXLIBS, libs); | |
1229 | value = 2 * countstones(pos); | |
1230 | ||
1231 | for (r = 0; r < liberties; r++) { | |
1232 | if (!mx[libs[r]] | |
1233 | && (whose_moyo(&initial_black_influence, libs[r]) == other | |
1234 | || whose_moyo(&initial_white_influence, libs[r]) == other)) { | |
1235 | mx[libs[r]] = 1; | |
1236 | value++; | |
1237 | } | |
1238 | for (k = 0; k < 4; k++) { | |
1239 | int librd = libs[r] + delta[k]; | |
1240 | if (!ON_BOARD1(librd) || mx[librd]) | |
1241 | continue; | |
1242 | mx[librd] = 1; | |
1243 | if (board[librd] == EMPTY | |
1244 | && (whose_moyo(&initial_black_influence, librd) == other | |
1245 | || (whose_moyo(&initial_white_influence, librd) == other))) | |
1246 | value++; | |
1247 | } | |
1248 | } | |
1249 | ||
1250 | aa_values[pos] = value; | |
1251 | if (1) | |
1252 | DEBUG(DEBUG_ATARI_ATARI, "aa_value for %1m = %d\n", pos, value); | |
1253 | } | |
1254 | } | |
1255 | ||
1256 | /* The aa_value for a string is the sum of the aa_values for all | |
1257 | * included strings in the original position. This will systematically | |
1258 | * overvalue strings which consist of multiple original strings, but | |
1259 | * this is okay since the defender very rarely should defend a string | |
1260 | * first and then sacrifice it later. | |
1261 | */ | |
1262 | static int | |
1263 | get_aa_value(int str) | |
1264 | { | |
1265 | int stones[MAX_BOARD * MAX_BOARD]; | |
1266 | int k; | |
1267 | int num_stones = findstones(str, MAX_BOARD * MAX_BOARD, stones); | |
1268 | int value = 0; | |
1269 | ||
1270 | for (k = 0; k < num_stones; k++) | |
1271 | value += aa_values[stones[k]]; | |
1272 | ||
1273 | return value; | |
1274 | } | |
1275 | ||
1276 | ||
1277 | /* update_aa_goal(goal, new_goal, apos, color) extends the goal array | |
1278 | * with vertices in a neighborhood of apos. The algorithm is that | |
1279 | * starting at apos, a distance measure is computed to nearby | |
1280 | * vertices. The distance increases with one for each step through | |
1281 | * empty vertices and by a liberty depending number when passing | |
1282 | * through strings of the attacked color. Strings with 3 or fewer | |
1283 | * liberties are free to pass through while strings with more | |
1284 | * liberties cost (libs - 3) to pass through. Stones with a distance | |
1285 | * of 5 or less are included in the goal. | |
1286 | * | |
1287 | * Additionally neighborhoods of the moves in the forbidden array are | |
1288 | * included in the goal, to make it possible to limit the goal to a | |
1289 | * specific area from the beginning. This is needed when trying to | |
1290 | * decide which moves are relevant to the combination. | |
1291 | */ | |
1292 | ||
1293 | #define ENQUEUE(pos, dist) \ | |
1294 | do { \ | |
1295 | if ((dist) <= MAX_AA_DIST) { \ | |
1296 | if (dists[pos] == 0) { \ | |
1297 | queue[queue_end++] = (pos); \ | |
1298 | dists[pos] = (dist); \ | |
1299 | } \ | |
1300 | else if (dists[pos] < (dist)) \ | |
1301 | dists[pos] = (dist); \ | |
1302 | } \ | |
1303 | } while (0); | |
1304 | ||
1305 | static int | |
1306 | update_aa_goal(signed char goal[BOARDMAX], signed char new_goal[BOARDMAX], | |
1307 | int apos, int color) | |
1308 | { | |
1309 | int other = OTHER_COLOR(color); | |
1310 | int dists[BOARDMAX]; | |
1311 | int queue[MAX_BOARD * MAX_BOARD]; | |
1312 | int queue_end = 0; | |
1313 | int k, r, s; | |
1314 | int pos; | |
1315 | ||
1316 | if (goal == NULL) | |
1317 | memset(new_goal, 0, BOARDMAX); | |
1318 | else | |
1319 | memcpy(new_goal, goal, BOARDMAX); | |
1320 | ||
1321 | memset(dists, 0, sizeof(dists)); | |
1322 | ||
1323 | if (apos != NO_MOVE) { | |
1324 | dists[apos] = 1; | |
1325 | queue[queue_end++] = apos; | |
1326 | } | |
1327 | ||
1328 | #if 0 | |
1329 | /* Disabled for now, since it does nothing but break atari_atari:16 | |
1330 | * and trevorc:1540. It could be reactivated when the rest of the | |
1331 | * function would be modified in order to garanty that a forbidden | |
1332 | * move is strictly equivalent to a played move in terms of goal | |
1333 | * mapping. I doubt it would be anything worth though... | |
1334 | */ | |
1335 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1336 | if (ON_BOARD(pos) && forbidden[pos]) { | |
1337 | dists[pos] = 1; | |
1338 | queue[queue_end++] = pos; | |
1339 | } | |
1340 | } | |
1341 | #endif | |
1342 | ||
1343 | if (queue_end == 0) | |
1344 | return 0; | |
1345 | ||
1346 | for (r = 0; r < queue_end; r++) { | |
1347 | int smallest_dist = MAX_BOARD * MAX_BOARD; | |
1348 | int best_index = -1; | |
1349 | ||
1350 | gg_assert(queue_end < MAX_BOARD * MAX_BOARD); | |
1351 | ||
1352 | for (k = r; k < queue_end; k++) { | |
1353 | if (dists[queue[k]] < smallest_dist) { | |
1354 | smallest_dist = dists[queue[k]]; | |
1355 | best_index = k; | |
1356 | } | |
1357 | } | |
1358 | ||
1359 | if (best_index != r) { | |
1360 | int tmp = queue[r]; | |
1361 | queue[r] = queue[best_index]; | |
1362 | queue[best_index] = tmp; | |
1363 | } | |
1364 | ||
1365 | pos = queue[r]; | |
1366 | if (board[pos] == other) | |
1367 | new_goal[pos] = 1; | |
1368 | ||
1369 | /* FIXME: We shouldn't let dead opponent stones stop the | |
1370 | * propagation of distance. | |
1371 | * | |
1372 | * As a partial fix we include pos == apos in a test below. | |
1373 | */ | |
1374 | for (k = 0; k < 4; k++) { | |
1375 | int pos2 = pos + delta[k]; | |
1376 | if (!ON_BOARD(pos2)) | |
1377 | continue; | |
1378 | if ((board[pos] != color || pos == apos) && board[pos2] == EMPTY) { | |
1379 | ENQUEUE(pos2, dists[pos] + 1); | |
1380 | } | |
1381 | else if (board[pos] != other && board[pos2] == other) { | |
1382 | int stones[MAX_BOARD * MAX_BOARD]; | |
1383 | int size = findstones(pos2, MAX_BOARD * MAX_BOARD, stones); | |
1384 | int libs = countlib(pos2); | |
1385 | int deltadist = libs - 3; | |
1386 | if (deltadist < 0) | |
1387 | deltadist = 0; | |
1388 | for (s = 0; s < size; s++) | |
1389 | ENQUEUE(stones[s], dists[pos] + deltadist); | |
1390 | } | |
1391 | } | |
1392 | } | |
1393 | return 1; | |
1394 | } | |
1395 | ||
1396 | /* Initialize an array with atari_atari attacks. The convention is that | |
1397 | * the array ends when a NO_MOVE is encountered in the move field. | |
1398 | */ | |
1399 | static void | |
1400 | aa_init_moves(struct aa_move attacks[AA_MAX_MOVES]) | |
1401 | { | |
1402 | attacks[0].move = NO_MOVE; | |
1403 | } | |
1404 | ||
1405 | ||
1406 | /* Add an atari_atari attack move to a struct aa_move array. If the | |
1407 | * move already is included in the array, we check whether the target | |
1408 | * also is known for that move and add it if not. | |
1409 | */ | |
1410 | static void | |
1411 | aa_add_move(struct aa_move attacks[AA_MAX_MOVES], int move, int target) | |
1412 | { | |
1413 | int k; | |
1414 | int r; | |
1415 | ||
1416 | for (k = 0; k < AA_MAX_MOVES; k++) | |
1417 | if (attacks[k].move == move || attacks[k].move == NO_MOVE) | |
1418 | break; | |
1419 | ||
1420 | /* If the array is full, give up. */ | |
1421 | if (k == AA_MAX_MOVES) | |
1422 | return; | |
1423 | ||
1424 | target = find_origin(target); | |
1425 | ||
1426 | /* New move. */ | |
1427 | if (attacks[k].move == NO_MOVE) { | |
1428 | attacks[k].move = move; | |
1429 | attacks[k].target[0] = target; | |
1430 | if (AA_MAX_TARGETS_PER_MOVE > 0) | |
1431 | attacks[k].target[1] = NO_MOVE; | |
1432 | ||
1433 | if (k < AA_MAX_MOVES - 1) | |
1434 | attacks[k+1].move = NO_MOVE; | |
1435 | ||
1436 | return; | |
1437 | } | |
1438 | ||
1439 | /* Known move, maybe new target. */ | |
1440 | for (r = 0; r < AA_MAX_TARGETS_PER_MOVE; r++) | |
1441 | if (attacks[k].target[r] == target || attacks[k].target[r] == NO_MOVE) | |
1442 | break; | |
1443 | ||
1444 | /* No place for more targets. */ | |
1445 | if (r == AA_MAX_TARGETS_PER_MOVE) | |
1446 | return; | |
1447 | ||
1448 | /* Target known. */ | |
1449 | if (attacks[k].target[r] == target) | |
1450 | return; | |
1451 | ||
1452 | /* Add target. */ | |
1453 | attacks[k].target[r] = target; | |
1454 | if (r < AA_MAX_TARGETS_PER_MOVE - 1) | |
1455 | attacks[k].target[r + 1] = NO_MOVE; | |
1456 | } | |
1457 | ||
1458 | /* Check whether an atari_atari attack move is included in an struct | |
1459 | * aa_move array. If target is not NO_MOVE, we also require that the | |
1460 | * target is known for the move. | |
1461 | */ | |
1462 | static int | |
1463 | aa_move_known(struct aa_move attacks[AA_MAX_MOVES], int move, int target) | |
1464 | { | |
1465 | int k; | |
1466 | int r; | |
1467 | ||
1468 | for (k = 0; k < AA_MAX_MOVES; k++) | |
1469 | if (attacks[k].move == move || attacks[k].move == NO_MOVE) | |
1470 | break; | |
1471 | ||
1472 | /* If the array is full, give up and claim the move to be known. */ | |
1473 | if (k == AA_MAX_MOVES) | |
1474 | return 1; | |
1475 | ||
1476 | /* Unknown move. */ | |
1477 | if (attacks[k].move == NO_MOVE) | |
1478 | return 0; | |
1479 | ||
1480 | /* Move known, but how about the target? | |
1481 | * If no target specified, just return 1. | |
1482 | */ | |
1483 | if (target == NO_MOVE) | |
1484 | return 1; | |
1485 | ||
1486 | target = find_origin(target); | |
1487 | for (r = 0; r < AA_MAX_TARGETS_PER_MOVE; r++) | |
1488 | if (attacks[k].target[r] == target || attacks[k].target[r] == NO_MOVE) | |
1489 | break; | |
1490 | ||
1491 | /* No place for more targets. Give up and claim the target to be known. */ | |
1492 | if (r == AA_MAX_TARGETS_PER_MOVE) | |
1493 | return 1; | |
1494 | ||
1495 | /* Target known. */ | |
1496 | if (attacks[k].target[r] == target) | |
1497 | return 1; | |
1498 | ||
1499 | /* Unknown target. */ | |
1500 | return 0; | |
1501 | } | |
1502 | ||
1503 | ||
1504 | /* Auxiliary function for aa_sort_moves(). */ | |
1505 | static int | |
1506 | target_comp_func(const void *a, const void *b) | |
1507 | { | |
1508 | int asize = get_aa_value(*((const int *) a)); | |
1509 | int bsize = get_aa_value(*((const int *) b)); | |
1510 | return asize - bsize; | |
1511 | } | |
1512 | ||
1513 | ||
1514 | /* Auxiliary function for aa_sort_moves(). */ | |
1515 | static int | |
1516 | move_comp_func(const void *a, const void *b) | |
1517 | { | |
1518 | const struct aa_move *aa = a; | |
1519 | const struct aa_move *bb = b; | |
1520 | int asize = get_aa_value(aa->target[0]); | |
1521 | int bsize = get_aa_value(bb->target[0]); | |
1522 | return asize - bsize; | |
1523 | } | |
1524 | ||
1525 | /* Sort the attack moves. For each move the targets are sorted in | |
1526 | * decreasing size. Then the moves are sorted with increasing size | |
1527 | * of their first target. | |
1528 | */ | |
1529 | static void | |
1530 | aa_sort_moves(struct aa_move attacks[AA_MAX_MOVES]) | |
1531 | { | |
1532 | int k; | |
1533 | int r; | |
1534 | int number_of_attacks; | |
1535 | int number_of_targets; | |
1536 | ||
1537 | for (k = 0; k < AA_MAX_MOVES && attacks[k].move != NO_MOVE; k++) { | |
1538 | for (r = 0; r < AA_MAX_TARGETS_PER_MOVE; r++) | |
1539 | if (attacks[k].target[r] == NO_MOVE) | |
1540 | break; | |
1541 | number_of_targets = r; | |
1542 | gg_sort(attacks[k].target, number_of_targets, | |
1543 | sizeof(attacks[k].target[0]), target_comp_func); | |
1544 | } | |
1545 | number_of_attacks = k; | |
1546 | gg_sort(attacks, number_of_attacks, sizeof(attacks[0]), move_comp_func); | |
1547 | } | |
1548 | ||
1549 | ||
1550 | #if 0 | |
1551 | ||
1552 | /* Returns true if a move by (color) at (pos) is atari on something. | |
1553 | * Currently unused. | |
1554 | */ | |
1555 | ||
1556 | static int | |
1557 | is_atari(int pos, int color) | |
1558 | { | |
1559 | int other = OTHER_COLOR(color); | |
1560 | ||
1561 | if (!is_legal(pos, color)) | |
1562 | return 0; | |
1563 | ||
1564 | if (board[SOUTH(pos)] == other | |
1565 | && countlib(SOUTH(pos)) == 2) | |
1566 | return 1; | |
1567 | ||
1568 | if (board[WEST(pos)] == other | |
1569 | && countlib(WEST(pos)) == 2) | |
1570 | return 1; | |
1571 | ||
1572 | if (board[NORTH(pos)] == other | |
1573 | && countlib(NORTH(pos)) == 2) | |
1574 | return 1; | |
1575 | ||
1576 | if (board[EAST(pos)] == other | |
1577 | && countlib(EAST(pos)) == 2) | |
1578 | return 1; | |
1579 | ||
1580 | return 0; | |
1581 | } | |
1582 | ||
1583 | #endif | |
1584 | ||
1585 | ||
1586 | /* | |
1587 | * Local Variables: | |
1588 | * tab-width: 8 | |
1589 | * c-basic-offset: 2 | |
1590 | * End: | |
1591 | */ |