Merge pull request #50 from lemonsqueeze/can_countercap
[pachi.git] / tactics / dragon.c
blob8921fe14b9d0c20535267a8fb8a5acb8c4e0bed8
1 #include <assert.h>
2 #include <stdio.h>
3 #include <stdlib.h>
5 #define QUICK_BOARD_CODE
7 #define DEBUG
8 #include "board.h"
9 #include "debug.h"
10 #include "tactics/dragon.h"
12 static char*
13 print_handler(struct board *board, coord_t c, void *data)
15 static char buf[64];
16 group_t dragon = *(group_t*)data;
17 char *before = "", *after = "";
18 if (dragon_at(board, c) == dragon) {
19 before = "\x1b[40;33;1m";
20 after = "\x1b[0m";
22 sprintf(buf, "%s%c%s", before, stone2char(board_at(board, c)), after);
23 return buf;
26 void
27 dragon_print(struct board *board, FILE *f, group_t dragon)
29 board_hprint(board, f, print_handler, &dragon);
32 static char *bold_colors[] = {
33 "\x1b[40;33;1m", // gold
34 "\x1b[40;32;1m", // green
35 "\x1b[40;31;1m", // red
36 "\x1b[40;34;1m", // blue
37 "\x1b[40;35;1m", // purple
38 "\x1b[40;36;1m", // lblue
39 "\x1b[40;37;1m", // white
42 static char *normal_colors[] = {
43 "\x1b[40;33m", // gold
44 "\x1b[40;32m", // green
45 "\x1b[40;31m", // red
46 "\x1b[40;34m", // blue
47 "\x1b[40;35m", // purple
48 "\x1b[40;36m", // lblue
49 "\x1b[40;37m", // white, must be last
52 static char *ansi_color_end = "\x1b[0m";
54 char *
55 pick_dragon_color(int i, bool bold, bool white_ok)
57 int ncolors = sizeof(normal_colors) / sizeof(char *);
58 if (!white_ok)
59 ncolors--;
60 if (bold)
61 return bold_colors[i % ncolors];
62 return normal_colors[i % ncolors];
65 static char*
66 print_dragons(struct board *board, coord_t c, void *data)
68 static char buf[64];
69 group_t *dragons = data;
70 group_t d = dragon_at(board, c);
71 char *before = "", *after = "";
73 if (d) {
74 int i; // Dragon index
75 for (i = 0; dragons[i] && dragons[i] != d; i++)
77 if (!dragons[i]) { dragons[i] = d; } /* Add new */
79 before = pick_dragon_color(i, (c == d), true); // Dragon base: bold
80 after = ansi_color_end;
83 sprintf(buf, "%s%c%s", before, stone2char(board_at(board, c)), after);
84 return buf;
87 void
88 board_print_dragons(struct board *board, FILE *f)
90 group_t dragons[BOARD_MAX_GROUPS] = { 0, };
91 board_hprint(board, f, print_dragons, dragons);
94 #define no_stone_at(c) (board_at(b, (c)) == S_NONE)
95 #define own_stone_at(c) (board_at(b, (c)) == color)
96 #define enemy_stone_at(c) (board_at(b, (c)) == stone_other(color))
97 #define no_stone_atxy(x, y) (board_atxy(b, (x), (y)) == S_NONE)
98 #define own_stone_atxy(x, y) (board_atxy(b, (x), (y)) == color)
99 #define enemy_stone_atxy(x, y) (board_atxy(b, (x), (y)) == stone_other(color))
101 static bool
102 is_controlled_eye_point(struct board *b, coord_t to, enum stone color);
104 /* Check if g and g2 are virtually connected through lib.
105 * c2 is a stone of g2 next to lib */
106 static bool
107 virtual_connection_at(struct board *b, enum stone color, coord_t lib, coord_t c2, group_t g1, group_t g2)
109 assert(board_at(b, lib) == S_NONE);
110 assert(board_at(b, c2) == color);
111 assert(group_at(b, c2) == g2);
113 /* Eye / Hanging connection ? */
114 if (is_controlled_eye_point(b, lib, color))
115 return true;
117 /* Diagonal connection ? */
118 int x2 = coord_x(c2, b), y2 = coord_y(c2, b);
119 foreach_diag_neighbor(b, c2) {
120 if (board_at(b, c) != color || group_at(b, c) != g1)
121 continue;
122 int x = coord_x(c, b); coord_t d1 = coord_xy(b, x, y2);
123 int y = coord_y(c, b); coord_t d2 = coord_xy(b, x2, y);
124 if (no_stone_at(d1) && no_stone_at(d2))
125 return true;
126 } foreach_diag_neighbor_end;
128 int x = coord_x(lib, b); int dx = coord_dx(lib, c2, b);
129 int y = coord_y(lib, b); int dy = coord_dy(lib, c2, b);
130 int x1 = x + dx;
131 int y1 = y + dy;
132 coord_t c1 = coord_xy(b, x1, y1); // other side of lib wrt c2
134 /* Bamboo joint or stronger ? */
135 if ( own_stone_at(c1) && group_at(b, c1) == g1 &&
136 ( (!dx && own_stone_atxy(x1-1, y1) && own_stone_atxy(x2-1, y2) && !enemy_stone_atxy(x-1, y)) ||
137 (!dx && own_stone_atxy(x1+1, y1) && own_stone_atxy(x2+1, y2) && !enemy_stone_atxy(x+1, y)) ||
138 (!dy && own_stone_atxy(x1, y1-1) && own_stone_atxy(x2, y2-1) && !enemy_stone_atxy(x, y-1)) ||
139 (!dy && own_stone_atxy(x1, y1+1) && own_stone_atxy(x2, y2+1) && !enemy_stone_atxy(x, y+1)) ))
140 return true;
142 /* TODO more fancy stuff ... */
144 return false;
149 /* Handler should return -1 to stop iterating */
150 typedef int (*foreach_in_connected_groups_t)(struct board *b, enum stone color, coord_t c, void *data);
152 static int
153 foreach_in_connected_groups_(struct board *b, enum stone color, group_t g,
154 foreach_in_connected_groups_t f, void *data, int *visited)
156 if (visited[group_base(g)])
157 return 0;
158 visited[group_base(g)] = 1;
160 foreach_in_group(b, g) {
161 if (f(b, color, c, data) == -1)
162 return -1;
163 } foreach_in_group_end;
165 // Look for virtually connected groups
166 for (int i = 0; i < board_group_info(b, g).libs; i++) {
167 coord_t lib = board_group_info(b, g).lib[i];
168 // TODO could mark liberties visited, more efficient ?
169 foreach_neighbor(b, lib, {
170 if (board_at(b, c) != color)
171 continue;
172 group_t g2 = group_at(b, c);
173 if (visited[g2] || !virtual_connection_at(b, color, lib, c, g, g2))
174 continue;
175 if (foreach_in_connected_groups_(b, color, g2, f, data, visited) == -1)
176 return -1;
179 return 0;
182 /* Call f() for each stone in dragon at @to. */
183 static void
184 foreach_in_connected_groups(struct board *b, enum stone color, coord_t to,
185 foreach_in_connected_groups_t f, void *data)
187 int visited[BOARD_MAX_COORDS] = {0, };
188 assert(board_at(b, to) == color);
189 group_t g = group_at(b, to);
190 foreach_in_connected_groups_(b, color, g, f, data, visited);
194 /* Handler should return -1 to stop iterating. */
195 typedef int (*foreach_connected_group_t)(struct board *b, enum stone color, group_t g, void *data);
197 static int
198 foreach_connected_group_(struct board *b, enum stone color, group_t g,
199 foreach_connected_group_t f, void *data, int *visited)
201 if (visited[group_base(g)])
202 return 0;
204 visited[group_base(g)] = 1;
205 if (f(b, color, g, data) == -1)
206 return -1;
208 // Look for virtually connected groups
209 for (int i = 0; i < board_group_info(b, g).libs; i++) {
210 coord_t lib = board_group_info(b, g).lib[i];
211 // TODO could mark liberties visited, more efficient ?
212 foreach_neighbor(b, lib, {
213 if (board_at(b, c) != color)
214 continue;
215 group_t g2 = group_at(b, c);
216 if (visited[g2] || !virtual_connection_at(b, color, lib, c, g, g2))
217 continue;
218 if (foreach_connected_group_(b, color, g2, f, data, visited) == -1)
219 return -1;
222 return 0;
225 /* Call f() for each group in dragon at @to. */
226 static void
227 foreach_connected_group(struct board *b, enum stone color, coord_t to,
228 foreach_connected_group_t f, void *data)
230 int visited[BOARD_MAX_COORDS] = {0, };
231 assert(board_at(b, to) == color);
232 group_t g = group_at(b, to);
233 foreach_connected_group_(b, color, g, f, data, visited);
236 struct foreach_lib_data {
237 int *visited;
238 foreach_in_connected_groups_t f;
239 void *data;
242 static int
243 foreach_lib_handler(struct board *b, enum stone color, group_t g, void *data)
245 struct foreach_lib_data *d = data;
246 for (int i = 0; i < board_group_info(b, g).libs; i++) {
247 coord_t lib = board_group_info(b, g).lib[i];
248 if (d->visited[lib])
249 continue;
250 d->visited[lib] = 1;
251 if (d->f(b, color, lib, d->data) == -1)
252 return -1;
254 return 0;
257 /* Call f() for each liberty of dragon at @to. */
258 static void
259 foreach_lib_in_connected_groups(struct board *b, enum stone color, coord_t to,
260 foreach_in_connected_groups_t f, void *data)
262 int visited[BOARD_MAX_COORDS] = {0, };
263 struct foreach_lib_data d = { .visited = visited, .f = f, .data = data };
264 foreach_connected_group(b, color, to, foreach_lib_handler, &d);
268 static int
269 stones_all_connected_handler(struct board *b, enum stone color, coord_t c, void *data)
271 int *connected = data;
272 connected[c] = 1; return 0;
275 static bool
276 stones_all_connected(struct board *b, enum stone color, coord_t *stones, int n)
278 // TODO optimize: check if all same group first ...
279 int connected[BOARD_MAX_COORDS] = {0, };
281 foreach_in_connected_groups(b, color, stones[0], stones_all_connected_handler, connected);
283 for (int i = 0; i < n; i++)
284 if (!connected[stones[i]])
285 return false;
286 return true;
289 /* Try to detect big eye area, ie:
290 * - completely enclosed area, not too big,
291 * - surrounding stones all connected to each other
292 * - size >= 2 (so no false eye issues)
293 * Returns size of the area, or 0 if doesn't match. */
295 big_eye_area(struct board *b, enum stone color, coord_t around, int *visited)
297 int NAKADE_MAX = 8; // min area size for living group (corner)
298 // could increase to 10 (side) and 12 (middle)
299 // and/or check prisoners
300 coord_t area[NAKADE_MAX];
301 int area_n = 0;
302 int STONES_MAX = 50;
303 int stones[STONES_MAX];
304 int stones_n = 0;
305 area[area_n++] = around;
307 assert(!visited[around]);
308 for (int i = 0; i < area_n; i++) {
309 foreach_neighbor(b, area[i], {
310 if (board_at(b, c) == S_OFFBOARD)
311 continue;
313 if (board_at(b, c) == color) { // Found border, save it and continue
314 bool dup = false;
315 for (int j = 0; j < stones_n; j++)
316 if (c == stones[j]) {
317 dup = true;
318 break;
320 if (dup) continue;
322 assert(stones_n < STONES_MAX);
323 stones[stones_n++] = c;
324 continue;
327 // Empty spot or prisoner, add it to area
328 bool dup = false;
329 for (int j = 0; j < area_n; j++)
330 if (c == area[j]) {
331 dup = true;
332 break;
334 if (dup) continue;
336 if (area_n >= NAKADE_MAX)
337 return 0;
339 area[area_n++] = c;
343 if (area_n < 3 || !stones_all_connected(b, color, stones, stones_n))
344 return 0;
346 // Ok good, mark area visited
347 // TODO if (area_n < 7) ...
348 for (int i = 0; i < area_n; i++)
349 visited[area[i]] = 1;
351 return area_n;
355 /* Point we control:
356 * Opponent can't play there or we can capture if he does.
357 * TODO - could make tiger mouth check smarter (check selfatari)
358 * - handle more exotic cases (ladders ?) */
359 static bool
360 is_controlled_eye_point(struct board *b, coord_t to, enum stone color)
362 assert(no_stone_at(to));
364 /* Eye-like ? */
365 if (!board_is_valid_play_no_suicide(b, stone_other(color), to))
366 return true;
368 /* Tiger mouth ?
369 * Check no opponent stone nearby and we can't be captured.
370 * also works for side connection */
371 if (immediate_liberty_count(b, to) == 1) {
372 int good = 0;
373 foreach_neighbor(b, to, {
374 if (enemy_stone_at(c))
375 return false;
376 if ((own_stone_at(c) && board_group_info(b, group_at(b, c)).libs > 1) ||
377 board_at(b, c) == S_OFFBOARD)
378 good++;
380 return (good == 3);
383 return false;
387 static bool
388 real_eye_endpoint(struct board *board, coord_t to, enum stone color)
390 enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
392 foreach_diag_neighbor(board, to) {
393 color_diag_libs[(enum stone) board_at(board, c)]++;
394 } foreach_diag_neighbor_end;
395 /* We need to control 3 corners of the eye in the middle of the board,
396 * 2 on the side, and 1 in the corner. */
397 if (color_diag_libs[S_OFFBOARD]) {
398 color_diag_libs[color] += color_diag_libs[S_OFFBOARD] - 1;
399 color_diag_libs[stone_other(color)]++;
402 /* Corners could be eye-like too ... */
403 foreach_diag_neighbor(board, to) {
404 if (color_diag_libs[color] >= 3) return true;
405 if (color_diag_libs[stone_other(color)] >= 2) return false;
407 if (board_at(board, c) != S_NONE)
408 continue;
409 if (is_controlled_eye_point(board, c, color)) /* No need to recurse, thank goodness */
410 color_diag_libs[color]++;
411 else
412 color_diag_libs[stone_other(color)]++;
413 } foreach_diag_neighbor_end;
415 return (color_diag_libs[color] >= 3);
418 /* Point is finished one point eye.
419 * (board_is_one_point_eye() ones can become false later ...) */
420 static bool
421 is_real_one_point_eye(struct board *b, coord_t to, enum stone color)
423 return (board_is_eyelike(b, to, color) &&
424 real_eye_endpoint(b, to, color));
427 static bool
428 is_real_two_point_eye(struct board *b, coord_t to, enum stone color, coord_t *pother)
430 if ((neighbor_count_at(b, to, color) +
431 neighbor_count_at(b, to, S_OFFBOARD)) != 3)
432 return false;
433 coord_t other = pass;
434 foreach_neighbor(b, to, { /* Find the other point ... */
435 if ((board_at(b, c) == S_NONE ||
436 board_at(b, c) == stone_other(color)) &&
437 (neighbor_count_at(b, c, color) +
438 neighbor_count_at(b, c, S_OFFBOARD)) == 3) {
439 other = c;
440 break;
443 *pother = other;
445 return (!is_pass(other) &&
446 real_eye_endpoint(b, to, color) &&
447 real_eye_endpoint(b, other, color));
450 struct safe_data {
451 int *visited;
452 int *eyes;
455 static int
456 count_eyes(struct board *b, enum stone color, coord_t lib, void *data)
458 struct safe_data *d = data;
459 if (d->visited[lib]) /* Don't visit big eyes multiple times */
460 return 0;
462 if (is_real_one_point_eye(b, lib, color)) {
463 // fprintf(stderr, "real eye: %s\n", coord2sstr(lib, b));
464 if (++(*d->eyes) >= 2)
465 return -1;
466 return 0;
469 coord_t other = pass;
470 if (is_real_two_point_eye(b, lib, color, &other)) {
471 // fprintf(stderr, "two-point eye: %s\n", coord2sstr(lib, b));
472 d->visited[other] = 1;
473 if (++(*d->eyes) >= 2)
474 return -1;
475 return 0;
478 /* TODO check shape ... */
479 int area_size = big_eye_area(b, color, lib, d->visited);
480 if (area_size) {
481 *d->eyes += (area_size > 7 ? 2 : 1);
482 if (*d->eyes >= 2)
483 return -1;
484 return 0;
487 return 0;
490 bool
491 dragon_is_safe_full(struct board *b, group_t g, enum stone color, int *visited, int *eyes)
493 struct safe_data d = { .visited = visited, .eyes = eyes };
494 foreach_lib_in_connected_groups(b, color, g, count_eyes, &d);
495 return (*eyes >= 2);
498 bool
499 dragon_is_safe(struct board *b, group_t g, enum stone color)
501 int visited[BOARD_MAX_COORDS] = {0, };
502 int eyes = 0;
503 return dragon_is_safe_full(b, g, color, visited, &eyes);
506 static int
507 count_libs(struct board *b, enum stone color, coord_t c, void *data)
509 int *libs = data;
510 (*libs)++; return 0;
514 dragon_liberties(struct board *b, enum stone color, coord_t to)
516 int libs = 0;
517 foreach_lib_in_connected_groups(b, color, to, count_libs, &libs);
518 return libs;
522 static int
523 dragon_at_handler(struct board *b, enum stone color, group_t g, void *data)
525 group_t *d = data;
526 *d = (*d > g ? *d : g); return 0;
529 group_t
530 dragon_at(struct board *b, coord_t to)
532 group_t g = group_at(b, to);
533 group_t d = 0;
534 enum stone color = board_at(b, to);
535 if (!g)
536 return 0;
538 foreach_connected_group(b, color, to, dragon_at_handler, &d);
539 return d;
543 #define GAP_LENGTH 4
545 /* Vertical gap ? */
546 static inline bool
547 is_vert_gap(struct board *b, enum stone color, int *connected, int lx, int ly, int x, int dy)
549 assert(dy);
550 for (int i = 0; i < GAP_LENGTH; i++) {
551 int y = ly + dy * i;
552 coord_t d = coord_xy(b, x, y);
553 if (board_at(b, d) == S_NONE)
554 continue;
555 if (board_at(b, d) == color && !connected[d])
556 return false; // reach other group, could still be cut though ...
557 if (board_at(b, d) == color && connected[d])
558 return false; // wrong direction
559 return false;
561 //fprintf(stderr, "vert gap %s %s\n", (dy > 0 ? "above" : "below"), coord2sstr(coord_xy(b, x, ly), b));
562 return true;
565 /* Horizontal gap ? */
566 static inline bool
567 is_horiz_gap(struct board *b, enum stone color, int *connected, int lx, int ly, int y, int dx)
569 assert(dx);
570 for (int i = 0; i < GAP_LENGTH; i++) {
571 int x = lx + dx * i;
572 coord_t d = coord_xy(b, x, y);
573 if (board_at(b, d) == S_NONE)
574 continue;
575 if (board_at(b, d) == color && !connected[d])
576 return false; // reach other group, could still be cut though ...
577 if (board_at(b, d) == color && connected[d])
578 return false; // wrong direction
579 return false;
581 return true;
584 #define vert_gap(x, dy) is_vert_gap(b, color, connected, lx, ly, x, dy)
585 #define horiz_gap(y, dx) is_horiz_gap(b, color, connected, lx, ly, y, dx)
587 /* Looking for 2-stones horizontal/vertical gap of length GAP_LENGTH extending
588 * outwards from lib. For example, something like this:
590 * . X X . . . X X X X X . . .
591 * . O . X . . X O O O * * * *
592 * . O * * * * X O . O * * * *
593 * . O * * * * X . O . . . . .
594 * . O . X . .
596 static bool
597 two_stones_gap(struct board *b, enum stone color, coord_t lib, int *connected)
599 int lx = coord_x(lib, b);
600 int ly = coord_y(lib, b);
602 for (int dx = -1; dx <= 1; dx++)
603 for (int dy = -1; dy <= 1; dy++) {
604 if (dy && !dx)
605 if ( vert_gap(lx, dy) && // center gap + 1 on either side
606 (vert_gap(lx - 1, dy) || vert_gap(lx + 1, dy)) )
607 return true;
608 if (dx && !dy)
609 if ( horiz_gap(ly, dx) && // center gap + 1 on either side
610 (horiz_gap(ly - 1, dx) || horiz_gap(ly + 1, dx)) )
611 return true;
613 return false;
616 static int
617 mark_connected(struct board *b, enum stone color, coord_t c, void *data)
619 int *connected = data;
620 connected[c] = 1; return 0;
623 struct surrounded_data {
624 int *connected;
625 bool surrounded;
628 static int
629 surrounded_check(struct board *b, enum stone color, coord_t lib, void *data)
631 struct surrounded_data *d = data;
632 if (two_stones_gap(b, color, lib, d->connected)) {
633 d->surrounded = 0; return -1;
635 /* Other group we could connect to ? */
636 foreach_neighbor(b, lib, {
637 if (board_at(b, c) == color && !d->connected[c]) {
638 with_move(b, lib, color, {
639 if (!group_at(b, lib))
640 break;
641 d->surrounded = dragon_is_surrounded(b, lib);
642 with_move_return(-1);
646 return 0;
649 bool
650 dragon_is_surrounded(struct board *b, coord_t to)
652 enum stone color = board_at(b, to);
653 assert(color == S_BLACK || color == S_WHITE);
654 int connected[BOARD_MAX_COORDS] = {0, };
656 /* Mark connected stones */
657 foreach_in_connected_groups(b, color, to, mark_connected, connected);
659 struct surrounded_data d = { .connected = connected, .surrounded = 1 };
660 foreach_lib_in_connected_groups(b, color, to, surrounded_check, &d);
661 return d.surrounded;