1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
2 * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see *
3 * http://www.gnu.org/software/gnugo/ for more information. *
4 * *
5 * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, *
6 * 2008 and 2009 by the Free Software Foundation. *
7 * *
8 * This program is free software; you can redistribute it and/or *
9 * modify it under the terms of the GNU General Public License as *
10 * published by the Free Software Foundation - version 3 or *
11 * (at your option) any later version. *
12 * *
13 * This program is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
16 * GNU General Public License in file COPYING for more details. *
17 * *
18 * You should have received a copy of the GNU General Public *
19 * License along with this program; if not, write to the Free *
20 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, *
21 * Boston, MA 02111, USA. *
22 \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
23
24 #include "gnugo.h"
25
26 #include <stdio.h>
27 #include <string.h>
28 #include <math.h>
29
30 #include "liberty.h"
31 #include "gg_utils.h"
32
33 /* Forward declarations */
34 static int goal_dist(int pos, signed char goal[BOARDMAX]);
35 static int compare_angles(const void *a, const void *b);
36 static void show_surround_map(signed char mf[BOARDMAX],
37 signed char mn[BOARDMAX]);
38
39 /* Globals */
40 static int gg; /* stores the gravity center of the goal */
41
42
43 /* Returns true if a dragon is enclosed within the convex hull of
44 * its hostile neighbor dragons. This is an indication that the dragon is
45 * in danger. Stones on the second and first lines are not tested.
46 *
47 * Normally NULL will be passed to the parameter apos. It can be
48 * an empty board location. If apos is non NULL it is marked and
49 * added to the the hull. Thus we can ask if adding a single stone
50 * to the board surrounds the dragon.
51 *
52 * A CORNER is a vertex of the polygon which comprises this convex
53 * hull. The algorithm proceeds by first finding the sequence of
54 * corners on the left side of the polyhedron, then the sequence
55 * of corners on the right side.
56 *
57 * The hull is marked in the array mn with the number 1. A slight
58 * expansion is marked with the number 2. Return code is SURROUNDED if
59 * the friendly dragon lies within the area marked 1,
60 * WEAKLY_SURROUNDED if it lies in the slightly larger area marked 1
61 * and 2, and 0 otherwise.
62 *
63 * The notion of weak surroundedness seems to be much less indicative
64 * of a dragon's immanent danger than surroundedness.
65 *
66 * An exception: if the larger area contains any stone of a different
67 * friendly dragon (which is not DEAD) the return code is 0, unless
68 * that allied dragon is ENTIRELY contained within the hull.
69 *
70 * Another exception: an ikken tobi (one space jump) is generally not
71 * a connection but in practice may be almost as good. If there is an
72 * ikken tobi out of the hull, then the dragon is not surrounded.
73 *
74 * If the parameter showboard is 1, the figure is drawn. If showboard
75 * is 2, the figure is only drawn if the region is surrounded.
76 *
77 * If (apos) is NULL, the result is saved in the surround_data cache.
78 * The assumption is that the function will only be called once
79 * with (apos) null, during make_dragons; thereafter the surroundedness
80 * will be accessed using the function is_surrounded().
81 *
82 * If *surround_size is not a NULL pointer, then surround_size
83 * returns the size of the surroundings.
84 */
85
86 int
compute_surroundings(int pos,int apos,int showboard,int * surround_size)87 compute_surroundings(int pos, int apos, int showboard, int *surround_size)
88 {
89 int i, j;
90 int m, n;
91 int k;
92 int dpos;
93 int surrounded;
94
95 int left_corner[MAX_BOARD];
96 int right_corner[MAX_BOARD];
97 int corner[BOARDMAX];
98 int left_corners = 0, right_corners = 0;
99 int corners = 0;
100 int top_row, bottom_row;
101 int color = board[pos];
102 int other = OTHER_COLOR(color);
103 int gi = 0;
104 int gj = 0;
105 int stones = 0;
106 int found_some;
107
108 signed char mf[BOARDMAX]; /* friendly dragon */
109 signed char mn[BOARDMAX]; /* neighbor dragons */
110 int sd[BOARDMAX]; /* distances to the goal */
111
112 if (DRAGON2(pos).hostile_neighbors == 0)
113 return(0);
114
115 memset(mf, 0, sizeof(mf));
116 memset(mn, 0, sizeof(mn));
117 memset(sd, 0, sizeof(sd));
118
119 mark_dragon(pos, mf, 1);
120
121 /* mark hostile neighbors */
122
123 for (k = 0; k < DRAGON2(pos).neighbors; k++) {
124 int nd = DRAGON(DRAGON2(pos).adjacent[k]).origin;
125
126 if (board[nd] != color) {
127 if (0)
128 gprintf("neighbor: %1m\n", nd);
129 mark_dragon(nd, mn, 1);
130 }
131 }
132
133 /* descend markings from stones lying on the 2nd and third lines */
134
135 for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++)
136 if (ON_BOARD(dpos) && mn[dpos]) {
137 for (k = 0; k < 4; k++) {
138 int d = delta[k];
139 if (!ON_BOARD(dpos + d))
140 continue;
141 if (!ON_BOARD(dpos + 2*d)) {
142 if (board[dpos + d] == EMPTY)
143 mn[dpos + d] = 1;
144 }
145 else if (!ON_BOARD(dpos + 3*d)) {
146 if (board[dpos + d] == EMPTY
147 && board[dpos + 2*d] == EMPTY)
148 mn[dpos + 2*d] = 1;
149 }
150 }
151 }
152
153 /* compute minimum distances to the goal */
154
155 for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++)
156 if (ON_BOARD(dpos) && mn[dpos])
157 sd[dpos] = goal_dist(dpos, mf);
158
159 /* revise markings */
160
161 do {
162 found_some = 0;
163 for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++)
164 if (ON_BOARD(dpos) && mn[dpos] && sd[dpos] > 8) {
165 /* discard markings if we can find 2 stones
166 * that verify :
167 * - it is closer to the goal than we are
168 * - it is closer to us than the goal is
169 * - they are closer to each other than we are to the goal
170 */
171 for (i = BOARDMIN; i < BOARDMAX; i++)
172 if (ON_BOARD(i) && mn[i] && i != dpos
173 && sd[i] < sd[dpos]
174 && square_dist(i, dpos) < sd[dpos]) {
175 for (j = i + 1; j < BOARDMAX; j++)
176 if (ON_BOARD(j) && mn[j] && j != dpos
177 && sd[j] < sd[dpos]
178 && square_dist(j, dpos) < sd[dpos]
179 && square_dist(i, j) < sd[dpos]) {
180 mn[dpos] = 0;
181 found_some = 1;
182 break;
183 }
184 if (mn[dpos] == 0)
185 break;
186 }
187 }
188 } while (found_some);
189
190 /* prepare corner array */
191
192 for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++)
193 if (ON_BOARD(dpos) && mn[dpos])
194 corner[corners++] = dpos;
195
196 /* compute gravity center of the goal */
197
198 for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++)
199 if (ON_BOARD(dpos) && mf[dpos]) {
200 gi += I(dpos);
201 gj += J(dpos);
202 stones++;
203 }
204 gi /= stones;
205 gj /= stones;
206 gg = POS(gi, gj);
207
208 /* sort the corner array */
209
210 gg_sort(corner, corners, sizeof(int), compare_angles);
211
212 /* if apos is not NO_MOVE, mark it. */
213
214 if (apos != NO_MOVE) {
215 ASSERT_ON_BOARD1(apos);
216 mn[apos] = 1;
217 }
218
219 if (showboard == 1) {
220 show_surround_map(mf, mn);
221 }
222
223 /* find top row of surrounding polyhedron */
224
225 top_row = -1;
226 for (m = 0; m < board_size; m++) {
227 if (top_row != -1)
228 break;
229 for (n = 0; n < board_size; n++)
230 if (mn[POS(m, n)]) {
231 left_corner[0] = POS(m, n);
232 top_row = m;
233 break;
234 }
235 }
236
237 /* find bottom row */
238
239 bottom_row = -1;
240 for (m = board_size - 1; m >= 0; m--) {
241 if (bottom_row != -1)
242 break;
243 for (n = 0; n < board_size; n++)
244 if (mn[POS(m, n)]) {
245 bottom_row = m;
246 break;
247 }
248 }
249
250 /* find the corners on the left side */
251
252 for (left_corners = 1; I(left_corner[left_corners-1]) < bottom_row;
253 left_corners++) {
254 int best_found = 0;
255 float best_slope = 0.;
256 int m = I(left_corner[left_corners-1]);
257 int n = J(left_corner[left_corners-1]);
258
259 for (i = m + 1; i <= bottom_row; i++)
260 for (j = 0; j < board_size; j++)
261 if (mn[POS(i, j)]) {
262 float slope = ((float) (j - n))/((float) (i - m));
263 if (0)
264 gprintf("(left) at %m, last %m, slope=%f\n", i, j, m, n, slope);
265
266 if (!best_found || slope < best_slope) {
267 best_found = POS(i, j);
268 best_slope = slope;
269 }
270 }
271 ASSERT_ON_BOARD1(best_found);
272 left_corner[left_corners] = best_found;
273 }
274
275 for (n = board_size-1; n >= 0; n--)
276 if (mn[POS(top_row, n)]) {
277 right_corner[0] = POS(top_row, n);
278 break;
279 }
280
281 /* find the corners on the right side */
282
283 for (right_corners = 1; I(right_corner[right_corners-1]) < bottom_row;
284 right_corners++) {
285 int best_found = 0;
286 float best_slope = 0.;
287 int m = I(right_corner[right_corners-1]);
288 int n = J(right_corner[right_corners-1]);
289
290 for (i = m + 1; i <= bottom_row; i++) {
291 for (j = board_size - 1; j >= 0; j--) {
292 if (mn[POS(i, j)]) {
293 float slope = ((float) (j - n))/((float) (i - m));
294 if (0)
295 gprintf("(right) at %m, last %m, slope=%f\n", i, j, m, n, slope);
296 if (!best_found || slope > best_slope) {
297 best_found = POS(i, j);
298 best_slope = slope;
299 }
300 }
301 }
302 }
303 ASSERT_ON_BOARD1(best_found);
304 right_corner[right_corners] = best_found;
305 }
306
307 if (0) {
308 for (k = 0; k < left_corners; k++)
309 gprintf("left corner %d: %1m\n", k, left_corner[k]);
310
311 for (k = 0; k < right_corners; k++)
312 gprintf("right corner %d: %1m\n", k, right_corner[k]);
313 }
314
315 /* Now mark the interior of the convex hull */
316
317 for (n = J(left_corner[0]); n <= J(right_corner[0]); n++)
318 mn[POS(top_row, n)] = 1;
319
320 for (n = J(left_corner[left_corners-1]);
321 n <= J(right_corner[right_corners-1]); n++)
322 mn[POS(bottom_row, n)] = 1;
323
324 for (m = top_row+1; m < bottom_row; m++) {
325 int left_boundary = -1, right_boundary = -1;
326 for (k = 1; k < left_corners; k++) {
327 if (I(left_corner[k]) > m) {
328 float ti = I(left_corner[k-1]);
329 float tj = J(left_corner[k-1]);
330 float bi = I(left_corner[k]);
331 float bj = J(left_corner[k]);
332
333 if (0)
334 gprintf("(left) %d: %1m %1m\n",
335 m, left_corner[k-1], left_corner[k]);
336 /* left edge in this row is on segment (ti,tj) -> (bi, bj) */
337
338 /* FIXME: Rewrite this to avoid floating point arithmetic */
339 left_boundary = ceil(tj + (m - ti) * (bj - tj) / (bi - ti));
340 break;
341 }
342 }
343
344 for (k = 1; k < right_corners; k++) {
345 if (I(right_corner[k]) > m) {
346 float ti = I(right_corner[k-1]);
347 float tj = J(right_corner[k-1]);
348 float bi = I(right_corner[k]);
349 float bj = J(right_corner[k]);
350
351 if (0)
352 gprintf("(right) %d: %1m %1m\n",
353 m, right_corner[k-1], right_corner[k]);
354
355 /* FIXME: Rewrite this to avoid floating point arithmetic */
356 right_boundary = floor(tj + (m - ti) * (bj - tj) / (bi - ti));
357 break;
358 }
359 }
360
361 for (n = left_boundary; n <= right_boundary; n++)
362 mn[POS(m, n)] = 1;
363 }
364
365 /* mark the expanded region */
366
367 for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++)
368 if (ON_BOARD(dpos) && mn[dpos] == 1)
369 for (k = 0; k < 4; k++)
370 if (ON_BOARD(dpos + delta[k]) && !mn[dpos + delta[k]])
371 mn[dpos + delta[k]] = 2;
372
373 /* Mark allied dragons that intersect the (unexpanded) hull.
374 * These must all lie entirely within the hull for the
375 * dragon to be considered surrounded.
376 *
377 * Only neighbor dragons are considered since dragons that
378 * are not neighbors are less likely to be helpful.
379 */
380
381 for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++) {
382 int mpos;
383 if (ON_BOARD(dpos)
384 && mn[dpos] == 1
385 && board[dpos] == color
386 && are_neighbor_dragons(pos, dpos)
387 && !mf[dpos]) {
388
389 for (mpos = BOARDMIN; mpos < BOARDMAX; mpos++)
390 if (ON_BOARD(mpos) && is_same_dragon(mpos, dpos))
391 mf[mpos] = 2;
392 }
393 /* A special case
394 *
395 * . X X .
396 * X O . X
397 * X . O O
398 * . O . .
399 *
400 * The O stone hasn't been amalgamated and the surround computations
401 * might think this single stone dragon is surrounded, which in turn
402 * can generate overvaluation of moves around this stone.
403 * Consequently, we allow inclusion of the stones at kosumi distance
404 * in the mf (friendly) array.
405 */
406 if (ON_BOARD(dpos)
407 && mn[dpos] == 2
408 && board[dpos] == color
409 && are_neighbor_dragons(pos, dpos)
410 && !mf[dpos]) {
411 for (k = 4; k < 8; k++)
412 if (ON_BOARD(dpos + delta[k]) && board[dpos + delta[k]] == color
413 && mn[dpos + delta[k]] == 1
414 && board[dpos + delta[k-4]] == EMPTY
415 && board[dpos + delta[(k-3)%4]] == EMPTY) {
416 for (mpos = BOARDMIN; mpos < BOARDMAX; mpos++)
417 if (ON_BOARD(mpos) && is_same_dragon(mpos, dpos))
418 mf[mpos] = 2;
419 }
420 }
421 }
422
423 /* determine the surround status of the dragon */
424
425 surrounded = SURROUNDED;
426
427 /* Compute the maximum surround status awarded
428 * If distances between enclosing stones are large, reduce to
429 * WEAKLY_SURROUNDED. If (really) too large, then reduce to 0
430 * FIXME: constants chosen completely ad hoc. Possibly better tunings
431 * can be found.
432 */
433
434 for (k = 0; k < corners - 1; k++) {
435 if (is_edge_vertex(corner[k])
436 && is_edge_vertex(corner[k+1]))
437 continue;
438 if (square_dist(corner[k], corner[k+1]) > 60) {
439 surrounded = 0;
440 break;
441 }
442 else if (square_dist(corner[k], corner[k+1]) > 27)
443 surrounded = WEAKLY_SURROUNDED;
444 }
445 if (surrounded
446 && (!is_edge_vertex(corner[0])
447 || !is_edge_vertex(corner[corners-1]))) {
448 if (square_dist(corner[0], corner[corners-1]) > 60)
449 surrounded = 0;
450 else if (square_dist(corner[0], corner[corners-1]) > 27)
451 surrounded = WEAKLY_SURROUNDED;
452 }
453
454 if (surrounded)
455 for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++)
456 if (mf[dpos]) {
457 if (mn[dpos] == 0) {
458 surrounded = 0;
459 break;
460 }
461 else if (mn[dpos] == 2)
462 surrounded = WEAKLY_SURROUNDED;
463 }
464
465 /* revise the status for single stone dragons. */
466
467 if (stones == 1
468 && surrounded == WEAKLY_SURROUNDED
469 && mn[pos] == 2)
470 surrounded = 0;
471
472 /* revise the status if an ikken tobi jumps out. */
473
474 if (surrounded) {
475 for (dpos = BOARDMIN; dpos < BOARDMAX && surrounded; dpos++) {
476 if (!ON_BOARD(dpos) || !mf[dpos])
477 continue;
478
479 for (k = 0; k < 4; k++) {
480 int up = delta[k];
481 int right = delta[(k + 1) % 4];
482 if (board[dpos + up] == EMPTY
483 && board[dpos + 2*up] == color
484 && mn[dpos + 2*up] != 1
485 && ON_BOARD(dpos + up + right)
486 && board[dpos + up + right] != other
487 && ON_BOARD(dpos + up - right)
488 && board[dpos + up - right] != other) {
489 surrounded = 0;
490 break;
491 }
492 }
493 }
494 }
495
496 if (showboard == 1 || (showboard == 2 && surrounded)) {
497 show_surround_map(mf, mn);
498 }
499
500 if (!apos && surrounded && surround_pointer < MAX_SURROUND) {
501 memcpy(surroundings[surround_pointer].surround_map, mn, sizeof(mn));
502 surroundings[surround_pointer].dragon_number = dragon[pos].id;
503 surround_pointer++;
504 }
505
506 if (surround_size) {
507 int pos;
508
509 *surround_size = 0;
510 for (pos = BOARDMIN; pos < BOARDMAX; pos++)
511 if (ON_BOARD(pos) && mn[pos] == 1)
512 (*surround_size)++;
513 }
514
515 return surrounded;
516 }
517
518
519 /* Computes the minimum distance to the goal
520 */
521
522 static int
goal_dist(int pos,signed char goal[BOARDMAX])523 goal_dist(int pos, signed char goal[BOARDMAX])
524 {
525 int dist = 10000;
526 int ii;
527
528 for (ii = BOARDMIN; ii < BOARDMAX; ii++)
529 if (ON_BOARD(ii) && goal[ii])
530 dist = gg_min(dist, square_dist(ii, pos));
531
532 return dist;
533 }
534
535 /* Compares angles. Chosen convention:
536 * - SOUTH is "lowest"
537 * - ascending order is done clock-wise (WEST, NORTH, EAST)
538 */
539 static int
compare_angles(const void * a,const void * b)540 compare_angles(const void *a, const void *b)
541 {
542 int aa = *((const int *)a);
543 int bb = *((const int *)b);
544
545 int di_a = I(aa) - I(gg);
546 int dj_a = J(aa) - J(gg);
547 int di_b = I(bb) - I(gg);
548 int dj_b = J(bb) - J(gg);
549
550 float sin_a, sin_b;
551
552 if (aa == gg)
553 return 1;
554 if (bb == gg)
555 return -1;
556
557 if (dj_a == 0) {
558 if (di_a > 0) {
559 if (dj_b != 0 || di_b <= 0)
560 return -1;
561 return 0;
562 }
563 else {
564 if (dj_b > 0)
565 return -1;
566 else if (dj_b < 0 || di_b > 0)
567 return 1;
568 else
569 return 0;
570 }
571 }
572
573 sin_a = (float)di_a / sqrt(di_a*di_a + dj_a*dj_a);
574 sin_b = (float)di_b / sqrt(di_b*di_b + dj_b*dj_b);
575
576 if (dj_a > 0) {
577 if (dj_b <= 0)
578 return 1;
579 if (sin_a > sin_b)
580 return 1;
581 else if (sin_a < sin_b)
582 return -1;
583 else
584 return 0;
585 }
586 else { /* if (dj_a < 0) */
587 if (dj_b > 0)
588 return -1;
589 if (sin_a < sin_b)
590 return 1;
591 else if (sin_a > sin_b)
592 return -1;
593 else
594 return 0;
595 }
596 }
597
598
599 static void
show_surround_map(signed char mf[BOARDMAX],signed char mn[BOARDMAX])600 show_surround_map(signed char mf[BOARDMAX], signed char mn[BOARDMAX])
601 {
602 int m, n;
603
604 start_draw_board();
605 for (m = 0; m < board_size; m++)
606 for (n = 0; n < board_size; n++) {
607 int col, c;
608
609 if (mf[POS(m, n)]) {
610 if (mn[POS(m, n)] == 1)
611 col = GG_COLOR_RED;
612 else if (mn[POS(m, n)] == 2)
613 col = GG_COLOR_YELLOW;
614 else
615 col = GG_COLOR_GREEN;
616 }
617 else if (mn[POS(m, n)] == 1)
618 col = GG_COLOR_BLUE;
619 else if (mn[POS(m, n)] == 2)
620 col = GG_COLOR_CYAN;
621 else
622 col = GG_COLOR_BLACK;
623 if (board[POS(m, n)] == BLACK)
624 c = 'X';
625 else if (board[POS(m, n)] == WHITE)
626 c = 'O';
627 else if (mn[POS(m, n)])
628 c = '*';
629 else
630 c = '.';
631 draw_color_char(m, n, c, col);
632 }
633 end_draw_board();
634 }
635
636
637
638 int
is_surrounded(int dr)639 is_surrounded(int dr)
640 {
641 return(DRAGON2(dr).surround_status);
642 }
643
644 /* Returns true if (dragon) is not surrounded, but (move) surrounds it.
645 */
646
647 int
does_surround(int move,int dr)648 does_surround(int move, int dr)
649 {
650 if (DRAGON2(dr).surround_status)
651 return 0;
652 return compute_surroundings(dr, move, 0, NULL);
653 }
654
655
656 /* Should be run once per genmove, before make_dragons. */
657
658 void
reset_surround_data(void)659 reset_surround_data(void)
660 {
661 surround_pointer = 0;
662 }
663
664
665 /* Returns 1 (respectively 2) if pos is in the convex hull
666 * (respectively expanded hull boundary) of the surrounding
667 * dragons. Returns -1 if the dragon is not found.
668 */
669 int
surround_map(int dr,int pos)670 surround_map(int dr, int pos)
671 {
672 int k;
673
674 for (k = 0; k < surround_pointer; k++)
675 if (surroundings[k].dragon_number == dragon[dr].id)
676 return surroundings[k].surround_map[pos];
677 return -1;
678 }
679
680
681
682
683
684 /*
685 * Local Variables:
686 * tab-width: 8
687 * c-basic-offset: 2
688 * End:
689 */
690