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 | #include "gnugo.h" | |
26 | ||
27 | #include <stdio.h> | |
28 | #include <stdlib.h> | |
29 | #include <string.h> | |
30 | #include "liberty.h" | |
31 | ||
32 | static int do_aftermath_genmove(int color, | |
33 | int under_control[BOARDMAX], | |
34 | int do_capture_dead_stones); | |
35 | ||
36 | ||
37 | static int | |
38 | all_own_neighbors_inessential(int pos, int color) | |
39 | { | |
40 | int k; | |
41 | for (k = 0; k < 4; k++) | |
42 | if (board[pos + delta[k]] == color | |
43 | && DRAGON2(pos + delta[k]).safety != INESSENTIAL | |
44 | && (DRAGON2(pos + delta[k]).safety != ALIVE | |
45 | || DRAGON2(pos + delta[k]).owl_status != DEAD)) | |
46 | return 0; | |
47 | ||
48 | return 1; | |
49 | } | |
50 | ||
51 | /* Does a move by color at pos make one of the neighboring points into | |
52 | * a solid one-point eye? | |
53 | */ | |
54 | static int make_solid_eye(int pos, int color) | |
55 | { | |
56 | int k; | |
57 | int r; | |
58 | for (k = 0; k < 4; k++) { | |
59 | int eyepos = pos + delta[k]; | |
60 | if (board[eyepos] == EMPTY | |
61 | || (board[eyepos] == OTHER_COLOR(color) | |
62 | && countlib(eyepos) == 1)) { | |
63 | /* For a solid one-point eye all four neighbors must be own | |
64 | * stones. But one is about to be played so we need three in the | |
65 | * center, two on the edge and one in the corner. | |
66 | * | |
67 | * We also need a sufficient number of own diagonals; three in | |
68 | * the center, two on the edge, and one in the corner. | |
69 | * | |
70 | * Notice that the same numbers are needed for both neighbors | |
71 | * and diagonals and if we start counting at 2 in the corner and | |
72 | * at 1 on the edge, we need to reach 3 everywhere on the board. | |
73 | */ | |
74 | int own_neighbors = is_edge_vertex(pos) + is_corner_vertex(pos); | |
75 | int own_diagonals = own_neighbors; | |
76 | for (r = 0; r < 8; r++) { | |
77 | if (board[eyepos + delta[r]] == color) { | |
78 | if (r < 4) | |
79 | own_neighbors++; | |
80 | else | |
81 | own_diagonals++; | |
82 | } | |
83 | } | |
84 | if (own_neighbors == 3 && own_diagonals >= 3) | |
85 | return 1; | |
86 | } | |
87 | } | |
88 | ||
89 | return 0; | |
90 | } | |
91 | ||
92 | /* External interface to do_aftermath_genmove(). | |
93 | * | |
94 | * If the suggested move turns out not to be allowed we just return | |
95 | * pass. This is not ideal but also not a big deal. If | |
96 | * do_aftermath_genmove() is ever redesigned that would be a good time | |
97 | * to integrate allowed_moves. | |
98 | */ | |
99 | ||
100 | int | |
101 | aftermath_genmove(int color, int do_capture_dead_stones, | |
102 | int allowed_moves[BOARDMAX]) | |
103 | { | |
104 | int move = do_aftermath_genmove(color, NULL, do_capture_dead_stones); | |
105 | if (move != PASS_MOVE && allowed_moves && !allowed_moves[move]) | |
106 | move = PASS_MOVE; | |
107 | ||
108 | return move; | |
109 | } | |
110 | ||
111 | ||
112 | /* Generate a move to definitely settle the position after the game | |
113 | * has been finished. The purpose of this is to robustly determine | |
114 | * life and death status and to distinguish between life in seki and | |
115 | * life with territory. | |
116 | * | |
117 | * The strategy is basically to turn all own living stones into | |
118 | * invincible ones and remove from the board all dead opponent stones. | |
119 | * Stones which cannot be removed, nor turned invincible, are alive in | |
120 | * seki. | |
121 | * | |
122 | * If do_capture_dead_stones is 0, opponent stones are not necessarily | |
123 | * removed from the board. This happens if they become unconditionally | |
124 | * dead anyway. | |
125 | * | |
126 | * Moves are generated in the following order of priority: | |
127 | * -1. Play a move which is listed as a replacement for an | |
128 | * unconditionally meaningless move. This is guaranteed to extend | |
129 | * the unconditionally settled part of the board. Only do this if | |
130 | * the meaningless move is not connected through open space to an | |
131 | * invincible string. | |
132 | * 0. Play edge liberties in certain positions. This is not really | |
133 | * necessary, but often it can simplify the tactical and strategical | |
134 | * reading substantially, making subsequent moves faster to generate. | |
135 | * 1a. Capture an opponent string in atari and adjacent to own invincible | |
136 | * string. Moves leading to ko or snapback are excluded. | |
137 | * 1b. If do_capture_dead_stones, play a non-self-atari move adjacent | |
138 | * to an unconditionally dead opponent string. | |
139 | * 1c. If do_capture_dead_stones, play a liberty of an opponent string | |
140 | * where the liberty is adjacent to own invincible string. | |
141 | * 2. Extend an invincible string to a liberty of an opponent string. | |
142 | * 3. Connect a non-invincible string to an invincible string. | |
143 | * 4. Extend an invincible string towards an opponent string or an own | |
144 | * non-invincible string. | |
145 | * 5. Split a big eyespace of an alive own dragon without invincible | |
146 | * strings into smaller pieces. Do not play self-atari here. | |
147 | * 6. Play a liberty of a dead opponent dragon. | |
148 | * | |
149 | * Steps 2--4 are interleaved to try to optimize the efficiency of the | |
150 | * moves. In step 5 too, efforts are made to play efficient moves. By | |
151 | * efficient we here mean moves which are effectively settling the | |
152 | * position and simplify the tactical and strategical reading for | |
153 | * subsequent moves. | |
154 | * | |
155 | * Steps 1--4 are guaranteed to be completely safe. Step 0 and 5 | |
156 | * should also be risk-free. Step 6 on the other hand definitely | |
157 | * isn't. Consider for example this position: | |
158 | * | |
159 | * .XXXXX. | |
160 | * XXOOOXX | |
161 | * XOO.OOX | |
162 | * XOXXXOX | |
163 | * XO.XXOX | |
164 | * ------- | |
165 | * | |
166 | * In order to remove the O stones, it is necessary to play on one of | |
167 | * the inner liberties, but one of them lets O live. Thus we have to | |
168 | * check carefully for blunders at this step. | |
169 | * | |
170 | * Update: Step 0 is only safe against blunders if care is taken not | |
171 | * to get into a shortage of liberties. | |
172 | * Step 5 also has some risks. Consider this position: | |
173 | * | |
174 | * |XXXXX. | |
175 | * |OOOOXX | |
176 | * |..O.OX | |
177 | * |OX*OOX | |
178 | * +------ | |
179 | * | |
180 | * Playing at * allows X to make seki. | |
181 | * | |
182 | * IMPORTANT RESTRICTION: | |
183 | * Before calling this function it is mandatory to call genmove() or | |
184 | * genmove_conservative(). For this function to be meaningful, the | |
185 | * genmove() call should return pass. | |
186 | */ | |
187 | static int | |
188 | do_aftermath_genmove(int color, | |
189 | int under_control[BOARDMAX], | |
190 | int do_capture_dead_stones) | |
191 | { | |
192 | int k; | |
193 | int other = OTHER_COLOR(color); | |
194 | int distance[BOARDMAX]; | |
195 | int score[BOARDMAX]; | |
196 | float owl_hotspot[BOARDMAX]; | |
197 | float reading_hotspot[BOARDMAX]; | |
198 | int dragons[BOARDMAX]; | |
199 | int something_found; | |
200 | int closest_opponent = NO_MOVE; | |
201 | int closest_own = NO_MOVE; | |
202 | int d; | |
203 | int move = NO_MOVE; | |
204 | int pos = NO_MOVE; | |
205 | int best_score; | |
206 | int best_scoring_move; | |
207 | ||
208 | owl_hotspots(owl_hotspot); | |
209 | reading_hotspots(reading_hotspot); | |
210 | ||
211 | /* As a preparation we compute a distance map to the invincible strings. */ | |
212 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
213 | if (!ON_BOARD(pos)) | |
214 | continue; | |
215 | else if (board[pos] == color && worm[pos].invincible) | |
216 | distance[pos] = 0; | |
217 | else if (!do_capture_dead_stones | |
218 | && ((board[pos] == other | |
219 | && worm[pos].unconditional_status == DEAD) | |
220 | || (board[pos] == color | |
221 | && worm[pos].unconditional_status == ALIVE))) | |
222 | distance[pos] = 0; | |
223 | else | |
224 | distance[pos] = -1; | |
225 | } | |
226 | ||
227 | d = 0; | |
228 | do { | |
229 | something_found = 0; | |
230 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
231 | if (ON_BOARD(pos) && distance[pos] == -1) { | |
232 | for (k = 0; k < 4; k++) { | |
233 | int pos2 = pos + delta[k]; | |
234 | if (!ON_BOARD(pos2)) | |
235 | continue; | |
236 | if ((d == 0 || board[pos2] == EMPTY) | |
237 | && distance[pos2] == d) { | |
238 | if (d > 0 && board[pos] == other) { | |
239 | distance[pos] = d + 1; | |
240 | if (closest_opponent == NO_MOVE) | |
241 | closest_opponent = pos; | |
242 | } | |
243 | else if (d > 0 && board[pos] == color) { | |
244 | distance[pos] = d + 1; | |
245 | if (closest_own == NO_MOVE) | |
246 | closest_own = pos; | |
247 | } | |
248 | else if (board[pos] == EMPTY) { | |
249 | distance[pos] = d + 1; | |
250 | something_found = 1; | |
251 | } | |
252 | break; | |
253 | } | |
254 | } | |
255 | } | |
256 | } | |
257 | d++; | |
258 | } while (something_found); | |
259 | ||
260 | if (under_control) { | |
261 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
262 | if (!ON_BOARD(pos)) | |
263 | continue; | |
264 | else if (distance[pos] == -1) | |
265 | under_control[pos] = 0; | |
266 | else | |
267 | under_control[pos] = 1; | |
268 | } | |
269 | } | |
270 | ||
271 | if (debug & DEBUG_AFTERMATH) { | |
272 | int m, n; | |
273 | for (m = 0; m < board_size; m++) { | |
274 | for (n = 0; n < board_size; n++) { | |
275 | pos = POS(m, n); | |
276 | if (distance[pos] > 0) | |
277 | fprintf(stderr, "%2d", distance[pos]); | |
278 | else if (distance[pos] == 0) { | |
279 | if (board[pos] == WHITE) | |
280 | gprintf(" o"); | |
281 | else if (board[pos] == BLACK) | |
282 | gprintf(" x"); | |
283 | else | |
284 | gprintf(" ?"); | |
285 | } | |
286 | else { | |
287 | if (board[pos] == WHITE) | |
288 | gprintf(" O"); | |
289 | else if (board[pos] == BLACK) | |
290 | gprintf(" X"); | |
291 | else | |
292 | gprintf(" ."); | |
293 | } | |
294 | } | |
295 | gprintf("\n"); | |
296 | } | |
297 | ||
298 | gprintf("Closest opponent %1m", closest_opponent); | |
299 | if (closest_opponent != NO_MOVE) | |
300 | gprintf(", distance %d\n", distance[closest_opponent]); | |
301 | else | |
302 | gprintf("\n"); | |
303 | ||
304 | gprintf("Closest own %1m", closest_own); | |
305 | if (closest_own != NO_MOVE) | |
306 | gprintf(", distance %d\n", distance[closest_own]); | |
307 | else | |
308 | gprintf("\n"); | |
309 | } | |
310 | ||
311 | /* Case -1. */ | |
312 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
313 | int replacement_move; | |
314 | if (board[pos] == EMPTY | |
315 | && distance[pos] == -1 | |
316 | && unconditionally_meaningless_move(pos, color, &replacement_move) | |
317 | && replacement_move != NO_MOVE) { | |
318 | DEBUG(DEBUG_AFTERMATH, "Replacement move for %1m at %1m\n", pos, | |
319 | replacement_move); | |
320 | return replacement_move; | |
321 | } | |
322 | } | |
323 | ||
324 | /* Case 0. This is a special measure to avoid a certain kind of | |
325 | * tactical reading inefficiency. | |
326 | * | |
327 | * Here we play on edge liberties in the configuration | |
328 | * | |
329 | * XO. | |
330 | * .*. | |
331 | * --- | |
332 | * | |
333 | * to stop X from "leaking" out along the edge. Sometimes this can | |
334 | * save huge amounts of tactical reading for later moves. | |
335 | */ | |
336 | best_scoring_move = NO_MOVE; | |
337 | best_score = 5; | |
338 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
339 | int libs; | |
340 | if (board[pos] != EMPTY | |
341 | || distance[pos] == 0) | |
342 | continue; | |
343 | ||
344 | libs = approxlib(pos, color, 3, NULL); | |
345 | if (libs < 3) | |
346 | continue; | |
347 | ||
348 | if (is_self_atari(pos, other)) | |
349 | continue; | |
350 | ||
351 | for (k = 0; k < 4; k++) { | |
352 | int dir = delta[k]; | |
353 | int right = delta[(k+1)%4]; | |
354 | if (!ON_BOARD(pos - dir) | |
355 | && board[pos + dir] == color | |
356 | && board[pos + dir + right] == other | |
357 | && board[pos + dir - right] == other | |
358 | && (libs > countlib(pos + dir) | |
359 | || (libs > 4 | |
360 | && libs == countlib(pos + dir))) | |
361 | && (DRAGON2(pos + dir).safety == INVINCIBLE | |
362 | || DRAGON2(pos + dir).safety == STRONGLY_ALIVE)) { | |
363 | int this_score = 20 * (owl_hotspot[pos] + reading_hotspot[pos]); | |
364 | if (this_score > best_score) { | |
365 | best_score = this_score; | |
366 | best_scoring_move = pos; | |
367 | } | |
368 | } | |
369 | } | |
370 | } | |
371 | ||
372 | if (best_scoring_move != NO_MOVE | |
373 | && safe_move(best_scoring_move, color) == WIN) { | |
374 | DEBUG(DEBUG_AFTERMATH, "Closing edge at %1m\n", best_scoring_move); | |
375 | return best_scoring_move; | |
376 | } | |
377 | ||
378 | /* Case 1a. */ | |
379 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
380 | int lib; | |
381 | if (board[pos] == other | |
382 | && worm[pos].unconditional_status != DEAD | |
383 | && countlib(pos) == 1 | |
384 | && ((ON_BOARD(SOUTH(pos)) && distance[SOUTH(pos)] == 0) | |
385 | || (ON_BOARD(WEST(pos)) && distance[WEST(pos)] == 0) | |
386 | || (ON_BOARD(NORTH(pos)) && distance[NORTH(pos)] == 0) | |
387 | || (ON_BOARD(EAST(pos)) && distance[EAST(pos)] == 0))) { | |
388 | findlib(pos, 1, &lib); | |
389 | /* Make sure we don't play into a ko or a (proper) snapback. */ | |
390 | if (countstones(pos) > 1 || !is_self_atari(lib, color)) { | |
391 | return lib; | |
392 | } | |
393 | } | |
394 | } | |
395 | ||
396 | /* Case 1b. Play liberties of unconditionally dead stones, but never | |
397 | * self-atari. For efficiency against stubborn opponents, we want to | |
398 | * split up the empty space as much as possible. Therefore we look | |
399 | * among this class of moves for one with a maximum number of | |
400 | * adjacent empty spaces and opponent stones. | |
401 | */ | |
402 | if (do_capture_dead_stones) { | |
403 | best_score = 0; | |
404 | best_scoring_move = NO_MOVE; | |
405 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
406 | /* Look at empty points which are connectable to some invincible | |
407 | * string through empty space. | |
408 | */ | |
409 | if (board[pos] == EMPTY | |
410 | && distance[pos] >= 0) { | |
411 | int valid_move = 0; | |
412 | int this_score = 0; | |
413 | for (k = 0; k < 4; k++) { | |
414 | int pos2 = pos + delta[k]; | |
415 | if (board[pos2] == EMPTY) | |
416 | this_score += 2; | |
417 | else if (board[pos2] == other | |
418 | && worm[pos2].unconditional_status == DEAD) { | |
419 | this_score++; | |
420 | valid_move = 1; | |
421 | } | |
422 | } | |
423 | if (valid_move | |
424 | && this_score > best_score | |
425 | && !is_self_atari(pos, color)) { | |
426 | best_score = this_score; | |
427 | best_scoring_move = pos; | |
428 | } | |
429 | } | |
430 | } | |
431 | if (best_score > 0) | |
432 | return best_scoring_move; | |
433 | } | |
434 | ||
435 | /* Case 1c. */ | |
436 | if (do_capture_dead_stones) { | |
437 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
438 | if (board[pos] == EMPTY | |
439 | && distance[pos] == 1 | |
440 | && has_neighbor(pos, other)) { | |
441 | return pos; | |
442 | } | |
443 | } | |
444 | } | |
445 | ||
446 | /* Cases 2--4. */ | |
447 | if (closest_opponent != NO_MOVE || closest_own != NO_MOVE) { | |
448 | if (closest_own == NO_MOVE | |
449 | || (capture_all_dead | |
450 | && closest_opponent != NO_MOVE | |
451 | && distance[closest_opponent] < distance[closest_own])) | |
452 | move = closest_opponent; | |
453 | else | |
454 | move = closest_own; | |
455 | ||
456 | /* if we're about to play at distance 1, try to optimize the move. */ | |
457 | if (distance[move] == 2) { | |
458 | signed char mx[BOARDMAX]; | |
459 | signed char mark = 0; | |
460 | memset(mx, 0, sizeof(mx)); | |
461 | best_score = 0; | |
462 | best_scoring_move = move; | |
463 | ||
464 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
465 | int score = 0; | |
466 | int move_ok = 0; | |
467 | if (!ON_BOARD(pos) || distance[pos] != 1) | |
468 | continue; | |
469 | mark++; | |
470 | for (k = 0; k < 4; k++) { | |
471 | int pos2 = pos + delta[k]; | |
472 | if (!ON_BOARD(pos2)) | |
473 | continue; | |
474 | if (distance[pos2] < 1) | |
475 | score--; | |
476 | else if (board[pos2] == EMPTY) | |
477 | score++; | |
478 | else if (mx[pos2] == mark) | |
479 | score--; | |
480 | else { | |
481 | if (board[pos2] == color) { | |
482 | move_ok = 1; | |
483 | score += 7; | |
484 | if (countstones(pos2) > 2) | |
485 | score++; | |
486 | if (countstones(pos2) > 4) | |
487 | score++; | |
488 | if (countlib(pos2) < 4) | |
489 | score++; | |
490 | if (countlib(pos2) < 3) | |
491 | score++; | |
492 | } | |
493 | else { | |
494 | int deltalib = (approxlib(pos, other, MAXLIBS, NULL) | |
495 | - countlib(pos2)); | |
496 | move_ok = 1; | |
497 | score++; | |
498 | if (deltalib >= 0) | |
499 | score++; | |
500 | if (deltalib > 0) | |
501 | score++; | |
502 | } | |
503 | mark_string(pos2, mx, mark); | |
504 | } | |
505 | } | |
506 | if (is_suicide(pos, other)) | |
507 | score -= 3; | |
508 | ||
509 | if (0) | |
510 | gprintf("Score %1m = %d\n", pos, score); | |
511 | ||
512 | if (move_ok && score > best_score) { | |
513 | best_score = score; | |
514 | best_scoring_move = pos; | |
515 | } | |
516 | } | |
517 | move = best_scoring_move; | |
518 | } | |
519 | ||
520 | while (distance[move] > 1) { | |
521 | for (k = 0; k < 4; k++) { | |
522 | int pos2 = move + delta[k]; | |
523 | if (ON_BOARD(pos2) | |
524 | && board[pos2] == EMPTY | |
525 | && distance[pos2] == distance[move] - 1) { | |
526 | move = pos2; | |
527 | break; | |
528 | } | |
529 | } | |
530 | } | |
531 | return move; | |
532 | } | |
533 | ||
534 | /* Case 5. | |
535 | * If we reach here, either all strings of a dragon are invincible | |
536 | * or no string is. Next we try to make alive dragons invincible by | |
537 | * splitting big eyes into smaller ones. Our strategy is to search | |
538 | * for an empty vertex with as many eye points as possible adjacent | |
539 | * and with at least one alive but not invincible stone adjacent or | |
540 | * diagonal. | |
541 | */ | |
542 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
543 | int eyespace_neighbors = 0; | |
544 | int own_neighbors = 0; | |
545 | int own_diagonals = 0; | |
546 | int opponent_dragons = 0; | |
547 | int own_worms = 0; | |
548 | int safety = UNKNOWN; | |
549 | int bonus = 0; | |
550 | int mx[BOARDMAX]; | |
551 | score[pos] = 0; | |
552 | ||
553 | if (board[pos] != EMPTY || distance[pos] != -1) | |
554 | continue; | |
555 | ||
556 | /* Do not play self-atari here. */ | |
557 | if (is_self_atari(pos, color)) | |
558 | continue; | |
559 | ||
560 | memset(mx, 0, sizeof(mx)); | |
561 | ||
562 | for (k = 0; k < 8; k++) { | |
563 | int pos2 = pos + delta[k]; | |
564 | if (!ON_BOARD(pos2)) | |
565 | continue; | |
566 | ||
567 | if (board[pos2] == EMPTY) { | |
568 | if (k < 4) | |
569 | eyespace_neighbors++; | |
570 | continue; | |
571 | } | |
572 | ||
573 | if (board[pos2] == other) { | |
574 | int origin = dragon[pos2].origin; | |
575 | ||
576 | if (k < 4) { | |
577 | if (dragon[pos2].status == ALIVE) { | |
578 | safety = DEAD; | |
579 | break; | |
580 | } | |
581 | else if (!mx[origin]) { | |
582 | eyespace_neighbors++; | |
583 | opponent_dragons++; | |
584 | } | |
585 | } | |
586 | ||
587 | if (!mx[origin] && dragon[pos2].status == DEAD) { | |
588 | bonus++; | |
589 | if (k < 4 | |
590 | && countlib(pos2) <= 2 | |
591 | && countstones(pos2) >= 3) | |
592 | bonus++; | |
593 | ||
594 | if (k < 4 && countlib(pos2) == 1) | |
595 | bonus += 3; | |
596 | } | |
597 | mx[origin] = 1; | |
598 | } | |
599 | else if (board[pos2] == color) { | |
600 | dragons[pos] = pos2; | |
601 | ||
602 | if (safety == UNKNOWN && dragon[pos2].status == ALIVE) | |
603 | safety = ALIVE; | |
604 | ||
605 | if (DRAGON2(pos2).safety == INVINCIBLE) | |
606 | safety = INVINCIBLE; | |
607 | ||
608 | if (k < 4) { | |
609 | int apos = worm[pos2].origin; | |
610 | ||
611 | if (!mx[apos]) { | |
612 | own_worms++; | |
613 | if (countstones(apos) == 1) | |
614 | bonus += 2; | |
615 | if (countlib(apos) < 6 | |
616 | && approxlib(pos, color, 5, NULL) < countlib(apos)) | |
617 | bonus -= 5; | |
618 | mx[apos] = 1; | |
619 | } | |
620 | ||
621 | if (countlib(apos) <= 2) { | |
622 | int r; | |
623 | int important = 0; | |
624 | int safe_atari = 0; | |
625 | for (r = 0; r < 4; r++) { | |
626 | d = delta[r]; | |
627 | if (!ON_BOARD(apos+d)) | |
628 | continue; | |
629 | if (board[apos+d] == other | |
630 | && dragon[apos+d].status == DEAD) | |
631 | important = 1; | |
632 | else if (board[apos+d] == EMPTY | |
633 | && !is_self_atari(apos+d, other)) | |
634 | safe_atari = 1; | |
635 | } | |
636 | if (approxlib(pos, color, 3, NULL) > 2) { | |
637 | bonus++; | |
638 | if (important) { | |
639 | bonus += 2; | |
640 | if (safe_atari) | |
641 | bonus += 2; | |
642 | } | |
643 | } | |
644 | } | |
645 | ||
646 | own_neighbors++; | |
647 | } | |
648 | else | |
649 | own_diagonals++; | |
650 | } | |
651 | } | |
652 | if (safety == DEAD || safety == UNKNOWN | |
653 | || eyespace_neighbors == 0 | |
654 | || (own_neighbors + own_diagonals) == 0) | |
655 | continue; | |
656 | ||
657 | if (bonus < 0) | |
658 | bonus = 0; | |
659 | ||
660 | /* Big bonus for making a small solid eye while splitting the | |
661 | * eyespace. Don't bother optimizing for making two solid eyes, | |
662 | * unconditional replacement moves (case -1) will take care of | |
663 | * that. | |
664 | * | |
665 | * Additional bonus if adjacent to an opponent dragon and we are | |
666 | * asked to remove all dead opponent stones. | |
667 | */ | |
668 | if (eyespace_neighbors >= 2) | |
669 | if (make_solid_eye(pos, color)) { | |
670 | bonus += 20; | |
671 | if (do_capture_dead_stones && opponent_dragons > 0) | |
672 | bonus += 10; | |
673 | } | |
674 | ||
675 | score[pos] = 4 * eyespace_neighbors + bonus; | |
676 | if (safety == INVINCIBLE) { | |
677 | score[pos] += own_neighbors; | |
678 | if (own_neighbors < 2) | |
679 | score[pos] += own_diagonals; | |
680 | if (own_worms > 1 && eyespace_neighbors >= 1) | |
681 | score[pos] += 10 + 5 * (own_worms - 2); | |
682 | } | |
683 | else if (eyespace_neighbors > 2) | |
684 | score[pos] += own_diagonals; | |
685 | ||
686 | /* Splitting bonus. */ | |
687 | if (opponent_dragons > 1) | |
688 | score[pos] += 10 * (opponent_dragons - 1); | |
689 | ||
690 | /* Hotspot bonus. */ | |
691 | { | |
692 | int owl_hotspot_bonus = (int) (20.0 * owl_hotspot[pos]); | |
693 | int reading_hotspot_bonus = (int) (20.0 * reading_hotspot[pos]); | |
694 | int hotspot_bonus = owl_hotspot_bonus + reading_hotspot_bonus; | |
695 | ||
696 | /* Don't allow the hotspot bonus to turn a positive score into | |
697 | * a non-positive one. | |
698 | */ | |
699 | if (score[pos] > 0 && score[pos] + hotspot_bonus <= 0) | |
700 | hotspot_bonus = 1 - score[pos]; | |
701 | ||
702 | score[pos] += hotspot_bonus; | |
703 | ||
704 | if (1 && (debug & DEBUG_AFTERMATH)) | |
705 | gprintf("Score %1M = %d (hotspot bonus %d + %d)\n", pos, score[pos], | |
706 | owl_hotspot_bonus, reading_hotspot_bonus); | |
707 | } | |
708 | ||
709 | /* Avoid taking ko. */ | |
710 | if (is_ko(pos, color, NULL)) | |
711 | score[pos] = (score[pos] + 1) / 2; | |
712 | } | |
713 | ||
714 | while (1) { | |
715 | int bb; | |
716 | best_score = 0; | |
717 | move = NO_MOVE; | |
718 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
719 | if (ON_BOARD(pos) && score[pos] > best_score) { | |
720 | best_score = score[pos]; | |
721 | move = pos; | |
722 | } | |
723 | } | |
724 | ||
725 | if (move == NO_MOVE) | |
726 | break; | |
727 | ||
728 | bb = dragons[move]; | |
729 | if (is_illegal_ko_capture(move, color) | |
730 | || !safe_move(move, color) | |
731 | || (DRAGON2(bb).safety != INVINCIBLE | |
732 | && DRAGON2(bb).safety != STRONGLY_ALIVE | |
733 | && owl_does_defend(move, bb, NULL) != WIN) | |
734 | || (!confirm_safety(move, color, NULL, NULL))) { | |
735 | score[move] = 0; | |
736 | } | |
737 | else { | |
738 | /* If we're getting short of liberties, we must be more careful. | |
739 | * Check that no adjacent string or dragon gets more alive by | |
740 | * the move. | |
741 | */ | |
742 | int libs = approxlib(move, color, 5, NULL); | |
743 | int move_ok = 1; | |
744 | if (libs < 5) { | |
745 | for (k = 0; k < 4; k++) { | |
746 | if (board[move + delta[k]] == color | |
747 | && countlib(move + delta[k]) > libs) | |
748 | break; | |
749 | } | |
750 | if (k < 4) { | |
751 | if (trymove(move, color, "aftermath-B", move + delta[k])) { | |
752 | int adjs[MAXCHAIN]; | |
753 | int neighbors; | |
754 | int r; | |
755 | neighbors = chainlinks(move, adjs); | |
756 | for (r = 0; r < neighbors; r++) { | |
757 | if (worm[adjs[r]].attack_codes[0] != 0 | |
758 | && (find_defense(adjs[r], NULL) | |
759 | > worm[adjs[r]].defense_codes[0])) { | |
760 | DEBUG(DEBUG_AFTERMATH, | |
761 | "Blunder: %1m becomes tactically safer after %1m\n", | |
762 | adjs[r], move); | |
763 | move_ok = 0; | |
764 | } | |
765 | } | |
766 | popgo(); | |
767 | for (r = 0; r < neighbors && move_ok; r++) { | |
768 | if (dragon[adjs[r]].status == DEAD | |
769 | && !owl_does_attack(move, adjs[r], NULL)) { | |
770 | DEBUG(DEBUG_AFTERMATH, | |
771 | "Blunder: %1m becomes more alive after %1m\n", | |
772 | adjs[r], move); | |
773 | move_ok = 0; | |
774 | } | |
775 | } | |
776 | } | |
777 | } | |
778 | } | |
779 | ||
780 | if (!move_ok) | |
781 | score[move] = 0; | |
782 | else { | |
783 | DEBUG(DEBUG_AFTERMATH, "Splitting eyespace at %1m\n", move); | |
784 | return move; | |
785 | } | |
786 | } | |
787 | } | |
788 | ||
789 | /* Case 6. | |
790 | * Finally we try to play on liberties of remaining DEAD opponent | |
791 | * dragons, carefully checking against mistakes. | |
792 | */ | |
793 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
794 | int target; | |
795 | int cc = NO_MOVE; | |
796 | int self_atari_ok = 0; | |
797 | if (board[pos] != EMPTY || distance[pos] != -1) | |
798 | continue; | |
799 | target = NO_MOVE; | |
800 | for (k = 0; k < 8; k++) { | |
801 | int pos2 = pos + delta[k]; | |
802 | if (!ON_BOARD(pos2)) | |
803 | continue; | |
804 | if (board[pos2] == other | |
805 | && dragon[pos2].status != ALIVE | |
806 | && dragon[pos2].status != UNKNOWN | |
807 | && (do_capture_dead_stones | |
808 | || worm[pos2].unconditional_status != DEAD) | |
809 | && DRAGON2(pos2).safety != INESSENTIAL) { | |
810 | if (k < 4 || all_own_neighbors_inessential(pos, color)) { | |
811 | target = pos2; | |
812 | break; | |
813 | } | |
814 | } | |
815 | } | |
816 | if (target == NO_MOVE) | |
817 | continue; | |
818 | ||
819 | /* At this point, (pos) is a move that potentially may capture | |
820 | * a dead opponent string at (target). | |
821 | */ | |
822 | ||
823 | if (!trymove(pos, color, "aftermath-A", target)) | |
824 | continue; | |
825 | ||
826 | /* It is frequently necessary to sacrifice own stones in order | |
827 | * to force the opponent's stones to be removed from the board, | |
828 | * e.g. by adding stones to fill up a nakade shape. However, we | |
829 | * should only play into a self atari if the sacrificed stones | |
830 | * are classified as INESSENTIAL. Thus it would be ok for O to | |
831 | * try a self atari in this position: | |
832 | * | |
833 | * |OOOO | |
834 | * |XXXO | |
835 | * |..XO | |
836 | * |OOXO | |
837 | * +---- | |
838 | * | |
839 | * but not in this one: | |
840 | * | |
841 | * |XXX.. | |
842 | * |OOXX. | |
843 | * |.OOXX | |
844 | * |XXOOX | |
845 | * |.O.OX | |
846 | * +----- | |
847 | */ | |
848 | ||
849 | self_atari_ok = 1; | |
850 | for (k = 0; k < 4; k++) { | |
851 | if (board[pos + delta[k]] == color | |
852 | && DRAGON2(pos + delta[k]).safety != INESSENTIAL) { | |
853 | self_atari_ok = 0; | |
854 | cc = pos + delta[k]; | |
855 | break; | |
856 | } | |
857 | } | |
858 | ||
859 | /* Copy the potential move to (move). */ | |
860 | move = pos; | |
861 | ||
862 | /* If the move is a self atari, but that isn't okay, try to | |
863 | * recursively find a backfilling move which later makes the | |
864 | * potential move possible. | |
865 | */ | |
866 | if (!self_atari_ok) { | |
867 | while (countlib(pos) == 1) { | |
868 | int lib; | |
869 | findlib(pos, 1, &lib); | |
870 | move = lib; | |
871 | if (!trymove(move, color, "aftermath-B", target)) | |
872 | break; | |
873 | } | |
874 | ||
875 | if (countlib(pos) == 1) | |
876 | move = NO_MOVE; | |
877 | } | |
878 | ||
879 | while (stackp > 0) | |
880 | popgo(); | |
881 | ||
882 | if (move == NO_MOVE) | |
883 | continue; | |
884 | ||
885 | /* Make sure that the potential move really isn't a self | |
886 | * atari. In the case of a move found after backfilling this | |
887 | * could happen (because the backfilling moves happened to | |
888 | * capture some stones). The position of the move may even be | |
889 | * occupied. | |
890 | */ | |
891 | if (!self_atari_ok && (board[move] != EMPTY || is_self_atari(move, color))) | |
892 | continue; | |
893 | ||
894 | /* Consult the owl code to determine whether the considered move | |
895 | * really is effective. Blunders should be detected here. | |
896 | */ | |
897 | if (owl_does_attack(move, target, NULL) == WIN) { | |
898 | /* If we have an adjacent own dragon, which is not inessential, | |
899 | * verify that it remains safe. | |
900 | */ | |
901 | if (cc != NO_MOVE && !owl_does_defend(move, cc, NULL)) { | |
902 | int resulta, resultb; | |
903 | owl_analyze_semeai_after_move(move, color, target, cc, | |
904 | &resulta, &resultb, NULL, 1, NULL, 1); | |
905 | if (resulta != 0) | |
906 | continue; | |
907 | } | |
908 | ||
909 | /* If we don't allow self atari, also call confirm safety to | |
910 | * avoid setting up combination attacks. | |
911 | */ | |
912 | if (!self_atari_ok && !confirm_safety(move, color, NULL, NULL)) | |
913 | continue; | |
914 | ||
915 | DEBUG(DEBUG_AFTERMATH, "Filling opponent liberty at %1m\n", move); | |
916 | return move; | |
917 | } | |
918 | } | |
919 | ||
920 | /* Case 7. | |
921 | * In very rare cases it turns out we need yet another pass. An | |
922 | * example is this position: | |
923 | * | |
924 | * |..... | |
925 | * |OOOO. | |
926 | * |XXXO. | |
927 | * |.OXO. | |
928 | * |O.XO. | |
929 | * +----- | |
930 | * | |
931 | * Here the X stones are found tactically dead and therefore the | |
932 | * corner O stones have been amalgamated with the surrounding | |
933 | * stones. Since the previous case only allows sacrificing | |
934 | * INESSENTIAL stones, it fails to take X off the board. | |
935 | * | |
936 | * The solution is to look for tactically attackable opponent stones | |
937 | * that still remain on the board but should be removed. | |
938 | */ | |
939 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
940 | if (board[pos] == other | |
941 | && (worm[pos].unconditional_status == UNKNOWN | |
942 | || do_capture_dead_stones) | |
943 | && (DRAGON2(pos).safety == DEAD | |
944 | || DRAGON2(pos).safety == TACTICALLY_DEAD) | |
945 | && worm[pos].attack_codes[0] != 0 | |
946 | && !is_illegal_ko_capture(worm[pos].attack_points[0], color)) { | |
947 | DEBUG(DEBUG_AFTERMATH, "Tactically attack %1m at %1m\n", | |
948 | pos, worm[pos].attack_points[0]); | |
949 | return worm[pos].attack_points[0]; | |
950 | } | |
951 | } | |
952 | ||
953 | /* No move found. */ | |
954 | return PASS_MOVE; | |
955 | } | |
956 | ||
957 | /* This is a substitute for genmove_conservative() which only does | |
958 | * what is required when doing the aftermath. Notice though that this | |
959 | * generates an "ordinary" move, in contrast to aftermath_genmove(). | |
960 | * Usually this should turn up a pass, but when it doesn't it's | |
961 | * important not to miss the move. | |
962 | */ | |
963 | static int | |
964 | reduced_genmove(int color) | |
965 | { | |
966 | float value; | |
967 | int save_verbose; | |
968 | float our_score; | |
969 | int move; | |
970 | ||
971 | /* no move is found yet. */ | |
972 | move = PASS_MOVE; | |
973 | value = 0.0; | |
974 | ||
975 | /* Prepare pattern matcher and reading code. */ | |
976 | reset_engine(); | |
977 | ||
978 | /* Find out information about the worms and dragons. */ | |
979 | examine_position(EXAMINE_ALL, 1); | |
980 | ||
981 | /* The score will be used to determine when we are safely | |
982 | * ahead. So we want the most conservative score. | |
983 | */ | |
984 | if (color == WHITE) | |
985 | our_score = black_score; | |
986 | else | |
987 | our_score = -white_score; | |
988 | ||
989 | gg_assert(stackp == 0); | |
990 | ||
991 | /* | |
992 | * Ok, information gathering is complete. Now start to find some moves! | |
993 | */ | |
994 | ||
995 | /* Pick up moves that we know of already. */ | |
996 | save_verbose = verbose; | |
997 | if (verbose > 0) | |
998 | verbose--; | |
999 | collect_move_reasons(color); | |
1000 | verbose = save_verbose; | |
1001 | ||
1002 | /* Look for combination attacks and defenses against them. */ | |
1003 | combinations(color); | |
1004 | gg_assert(stackp == 0); | |
1005 | ||
1006 | /* Review the move reasons and estimate move values. */ | |
1007 | if (review_move_reasons(&move, &value, color, 0.0, our_score, NULL, 0)) | |
1008 | TRACE("Move generation likes %1m with value %f\n", move, value); | |
1009 | gg_assert(stackp == 0); | |
1010 | ||
1011 | /* If no move is found then pass. */ | |
1012 | if (move == PASS_MOVE) | |
1013 | TRACE("I pass.\n"); | |
1014 | else | |
1015 | TRACE("reduced_genmove() recommends %1m with value %f\n", move, value); | |
1016 | ||
1017 | return move; | |
1018 | } | |
1019 | ||
1020 | /* Preliminary function for playing through the aftermath. */ | |
1021 | static void | |
1022 | do_play_aftermath(int color, struct aftermath_data *a, | |
1023 | SGFTree *aftermath_sgftree) | |
1024 | { | |
1025 | int move; | |
1026 | int pass = 0; | |
1027 | int moves = 0; | |
1028 | int color_to_play = color; | |
1029 | DEBUG(DEBUG_AFTERMATH, "The aftermath starts.\n"); | |
1030 | ||
1031 | /* Disable computing worm and owl threats. */ | |
1032 | disable_threat_computation = 1; | |
1033 | /* Disable matching of endgame patterns. */ | |
1034 | disable_endgame_patterns = 1; | |
1035 | ||
1036 | while (pass < 2 && moves < board_size * board_size) { | |
1037 | int reading_nodes = get_reading_node_counter(); | |
1038 | int owl_nodes = get_owl_node_counter(); | |
1039 | move = reduced_genmove(color_to_play); | |
1040 | if (move == PASS_MOVE) { | |
1041 | int save_verbose = verbose; | |
1042 | if (verbose > 0) | |
1043 | verbose--; | |
1044 | move = do_aftermath_genmove(color_to_play, | |
1045 | (color_to_play == WHITE ? | |
1046 | a->white_control : a->black_control), | |
1047 | 0); | |
1048 | verbose = save_verbose; | |
1049 | } | |
1050 | play_move(move, color_to_play); | |
1051 | if (aftermath_sgftree) | |
1052 | sgftreeAddPlay(aftermath_sgftree, color_to_play, I(move), J(move)); | |
1053 | moves++; | |
1054 | DEBUG(DEBUG_AFTERMATH, "%d %C move %1m (nodes %d, %d total %d, %d)\n", | |
1055 | movenum, color_to_play, move, get_owl_node_counter() - owl_nodes, | |
1056 | get_reading_node_counter() - reading_nodes, | |
1057 | get_owl_node_counter(), get_reading_node_counter()); | |
1058 | if (move != PASS_MOVE) | |
1059 | pass = 0; | |
1060 | else | |
1061 | pass++; | |
1062 | color_to_play = OTHER_COLOR(color_to_play); | |
1063 | } | |
1064 | ||
1065 | /* Reenable worm and dragon threats and endgame patterns. */ | |
1066 | disable_threat_computation = 0; | |
1067 | disable_endgame_patterns = 0; | |
1068 | } | |
1069 | ||
1070 | static struct aftermath_data aftermath; | |
1071 | ||
1072 | static void | |
1073 | play_aftermath(int color, SGFTree *aftermath_sgftree) | |
1074 | { | |
1075 | int pos; | |
1076 | struct board_state saved_board; | |
1077 | struct aftermath_data *a = &aftermath; | |
1078 | static int current_board[BOARDMAX]; | |
1079 | static int current_color = EMPTY; | |
1080 | int cached_board = 1; | |
1081 | gg_assert(color == BLACK || color == WHITE); | |
1082 | ||
1083 | if (current_color != color) { | |
1084 | current_color = color; | |
1085 | cached_board = 0; | |
1086 | } | |
1087 | ||
1088 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1089 | if (ON_BOARD(pos) && board[pos] != current_board[pos]) { | |
1090 | current_board[pos] = board[pos]; | |
1091 | cached_board = 0; | |
1092 | } | |
1093 | } | |
1094 | ||
1095 | /* If this is exactly the same position as the one we analyzed the | |
1096 | * last time, the content of the aftermath struct is up to date. | |
1097 | */ | |
1098 | if (cached_board) | |
1099 | return; | |
1100 | ||
1101 | a->white_captured = white_captured; | |
1102 | a->black_captured = black_captured; | |
1103 | a->white_prisoners = 0; | |
1104 | a->black_prisoners = 0; | |
1105 | a->white_territory = 0; | |
1106 | a->black_territory = 0; | |
1107 | a->white_area = 0; | |
1108 | a->black_area = 0; | |
1109 | ||
1110 | store_board(&saved_board); | |
1111 | do_play_aftermath(color, a, aftermath_sgftree); | |
1112 | restore_board(&saved_board); | |
1113 | ||
1114 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1115 | if (!ON_BOARD(pos)) | |
1116 | continue; | |
1117 | if (a->black_control[pos]) { | |
1118 | a->black_area++; | |
1119 | if (board[pos] == WHITE) { | |
1120 | a->black_territory++; | |
1121 | a->white_prisoners++; | |
1122 | a->final_status[pos] = DEAD; | |
1123 | } | |
1124 | else if (board[pos] == EMPTY) { | |
1125 | a->black_territory++; | |
1126 | a->final_status[pos] = BLACK_TERRITORY; | |
1127 | } | |
1128 | else | |
1129 | a->final_status[pos] = ALIVE; | |
1130 | } | |
1131 | else if (a->white_control[pos]) { | |
1132 | a->white_area++; | |
1133 | if (board[pos] == BLACK) { | |
1134 | a->white_territory++; | |
1135 | a->black_prisoners++; | |
1136 | a->final_status[pos] = DEAD; | |
1137 | } | |
1138 | else if (board[pos] == EMPTY) { | |
1139 | a->white_territory++; | |
1140 | a->final_status[pos] = WHITE_TERRITORY; | |
1141 | } | |
1142 | else | |
1143 | a->final_status[pos] = ALIVE; | |
1144 | } | |
1145 | else { | |
1146 | if (board[pos] == EMPTY) | |
1147 | a->final_status[pos] = DAME; | |
1148 | else { | |
1149 | a->final_status[pos] = ALIVE_IN_SEKI; | |
1150 | if (board[pos] == WHITE) | |
1151 | a->white_area++; | |
1152 | else | |
1153 | a->black_area++; | |
1154 | } | |
1155 | } | |
1156 | } | |
1157 | ||
1158 | if (debug & DEBUG_AFTERMATH) { | |
1159 | gprintf("White captured: %d\n", a->white_captured); | |
1160 | gprintf("Black captured: %d\n", a->black_captured); | |
1161 | gprintf("White prisoners: %d\n", a->white_prisoners); | |
1162 | gprintf("Black prisoners: %d\n", a->black_prisoners); | |
1163 | gprintf("White territory: %d\n", a->white_territory); | |
1164 | gprintf("Black territory: %d\n", a->black_territory); | |
1165 | gprintf("White area: %d\n", a->white_area); | |
1166 | gprintf("Black area: %d\n", a->black_area); | |
1167 | } | |
1168 | } | |
1169 | ||
1170 | float | |
1171 | aftermath_compute_score(int color, SGFTree *tree) | |
1172 | { | |
1173 | struct aftermath_data *a = &aftermath; | |
1174 | play_aftermath(color, tree); | |
1175 | if (chinese_rules) | |
1176 | return (a->white_area | |
1177 | - a->black_area | |
1178 | + komi | |
1179 | + handicap); | |
1180 | else | |
1181 | return (a->white_territory | |
1182 | + a->black_captured | |
1183 | + a->black_prisoners | |
1184 | - (a->black_territory | |
1185 | + a->white_captured | |
1186 | + a->white_prisoners) | |
1187 | + komi); | |
1188 | } | |
1189 | ||
1190 | /* Report the final status of a vertex on the board. | |
1191 | * Possible results are ALIVE, DEAD, ALIVE_IN_SEKI, WHITE_TERRITORY, | |
1192 | * BLACK_TERRITORY, and DAME. | |
1193 | */ | |
1194 | enum dragon_status | |
1195 | aftermath_final_status(int color, int pos) | |
1196 | { | |
1197 | ASSERT_ON_BOARD1(pos); | |
1198 | play_aftermath(color, NULL); | |
1199 | return aftermath.final_status[pos]; | |
1200 | } | |
1201 | ||
1202 | /* | |
1203 | * Local Variables: | |
1204 | * tab-width: 8 | |
1205 | * c-basic-offset: 2 | |
1206 | * End: | |
1207 | */ |