UCB: Account for prior values properly when descending early
[pachi.git] / board.c
blob8c12b13bab0999acd342d10e71b9727d2f4b7a47
1 #include <alloca.h>
2 #include <assert.h>
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <string.h>
7 #include "board.h"
8 #include "debug.h"
9 #include "random.h"
11 int board_group_capture(struct board *board, int group);
13 bool random_pass = false;
16 #if 0
17 #define profiling_noinline __attribute__((noinline))
18 #else
19 #define profiling_noinline
20 #endif
22 #define gi_granularity 4
23 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
26 static void
27 board_setup(struct board *b)
29 memset(b, 0, sizeof(*b));
31 struct move m = { pass, S_NONE };
32 b->last_move = b->ko = m;
35 struct board *
36 board_init(void)
38 struct board *b = malloc(sizeof(struct board));
39 board_setup(b);
40 return b;
43 struct board *
44 board_copy(struct board *b2, struct board *b1)
46 memcpy(b2, b1, sizeof(struct board));
48 int bsize = b2->size2 * sizeof(*b2->b);
49 int gsize = b2->size2 * sizeof(*b2->g);
50 int fsize = b2->size2 * sizeof(*b2->f);
51 int nsize = b2->size2 * sizeof(*b2->n);
52 int psize = b2->size2 * sizeof(*b2->p);
53 int hsize = b2->size2 * 2 * sizeof(*b2->h);
54 int gisize = b2->size2 * sizeof(*b2->gi);
55 #ifdef WANT_BOARD_C
56 int csize = b2->size2 * sizeof(*b2->c);
57 #else
58 int csize = 0;
59 #endif
60 void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
61 memcpy(x, b1->b, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
62 b2->b = x; x += bsize;
63 b2->g = x; x += gsize;
64 b2->f = x; x += fsize;
65 b2->p = x; x += psize;
66 b2->n = x; x += nsize;
67 b2->h = x; x += hsize;
68 b2->gi = x; x += gisize;
69 #ifdef WANT_BOARD_C
70 b2->c = x; x += csize;
71 #endif
73 return b2;
76 void
77 board_done_noalloc(struct board *board)
79 if (board->b) free(board->b);
82 void
83 board_done(struct board *board)
85 board_done_noalloc(board);
86 free(board);
89 void
90 board_resize(struct board *board, int size)
92 board->size = size + 2 /* S_OFFBOARD margin */;
93 board->size2 = board->size * board->size;
94 if (board->b)
95 free(board->b);
97 int bsize = board->size2 * sizeof(*board->b);
98 int gsize = board->size2 * sizeof(*board->g);
99 int fsize = board->size2 * sizeof(*board->f);
100 int nsize = board->size2 * sizeof(*board->n);
101 int psize = board->size2 * sizeof(*board->p);
102 int hsize = board->size2 * 2 * sizeof(*board->h);
103 int gisize = board->size2 * sizeof(*board->gi);
104 #ifdef WANT_BOARD_C
105 int csize = board->size2 * sizeof(*board->c);
106 #else
107 int csize = 0;
108 #endif
109 void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
110 memset(x, 0, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
111 board->b = x; x += bsize;
112 board->g = x; x += gsize;
113 board->f = x; x += fsize;
114 board->p = x; x += psize;
115 board->n = x; x += nsize;
116 board->h = x; x += hsize;
117 board->gi = x; x += gisize;
118 #ifdef WANT_BOARD_C
119 board->c = x; x += csize;
120 #endif
123 void
124 board_clear(struct board *board)
126 int size = board->size;
128 board_done_noalloc(board);
129 board_setup(board);
130 board_resize(board, size - 2 /* S_OFFBOARD margin */);
132 /* Draw the offboard margin */
133 int top_row = board->size2 - board->size;
134 int i;
135 for (i = 0; i < board->size; i++)
136 board->b[i] = board->b[top_row + i] = S_OFFBOARD;
137 for (i = 0; i <= top_row; i += board->size)
138 board->b[i] = board->b[board->size - 1 + i] = S_OFFBOARD;
140 foreach_point(board) {
141 coord_t coord = c;
142 if (board_at(board, coord) == S_OFFBOARD)
143 continue;
144 foreach_neighbor(board, c, {
145 inc_neighbor_count_at(board, coord, board_at(board, c));
146 } );
147 } foreach_point_end;
149 /* First, pass is always a free position. */
150 board->f[board->flen++] = coord_raw(pass);
151 /* All positions are free! Except the margin. */
152 for (i = board->size; i < (board->size - 1) * board->size; i++)
153 if (i % board->size != 0 && i % board->size != board->size - 1)
154 board->f[board->flen++] = i;
156 /* Initialize zobrist hashtable. */
157 foreach_point(board) {
158 int max = (sizeof(hash_t) << history_hash_bits);
159 /* fast_random() is 16-bit only */
160 board->h[coord_raw(c) * 2] = ((hash_t) fast_random(max))
161 | ((hash_t) fast_random(max) << 16)
162 | ((hash_t) fast_random(max) << 32)
163 | ((hash_t) fast_random(max) << 48);
164 if (!board->h[coord_raw(c) * 2])
165 /* Would be kinda "oops". */
166 board->h[coord_raw(c) * 2] = 1;
167 /* And once again for white */
168 board->h[coord_raw(c) * 2 + 1] = ((hash_t) fast_random(max))
169 | ((hash_t) fast_random(max) << 16)
170 | ((hash_t) fast_random(max) << 32)
171 | ((hash_t) fast_random(max) << 48);
172 if (!board->h[coord_raw(c) * 2 + 1])
173 board->h[coord_raw(c) * 2 + 1] = 1;
174 } foreach_point_end;
178 void
179 board_print(struct board *board, FILE *f)
181 fprintf(f, "Move: % 3d Komi: %2.1f Captures B: %d W: %d\n ",
182 board->moves, board->komi,
183 board->captures[S_BLACK], board->captures[S_WHITE]);
184 int x, y;
185 char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
186 for (x = 1; x < board->size - 1; x++)
187 fprintf(f, "%c ", asdf[x - 1]);
188 fprintf(f, "\n +-");
189 for (x = 1; x < board->size - 1; x++)
190 fprintf(f, "--");
191 fprintf(f, "+\n");
192 for (y = board->size - 2; y >= 1; y--) {
193 fprintf(f, "%2d | ", y);
194 for (x = 1; x < board->size - 1; x++) {
195 if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
196 fprintf(f, "%c)", stone2char(board_atxy(board, x, y)));
197 else
198 fprintf(f, "%c ", stone2char(board_atxy(board, x, y)));
200 if (DEBUGL(6)) {
201 fprintf(f, "| ");
202 for (x = 1; x < board->size - 1; x++) {
203 fprintf(f, "%d ", group_atxy(board, x, y));
206 fprintf(f, "|\n");
208 fprintf(f, " +-");
209 for (x = 1; x < board->size - 1; x++)
210 fprintf(f, "--");
211 fprintf(f, "+\n\n");
215 /* Update board hash with given coordinate. */
216 static void profiling_noinline
217 board_hash_update(struct board *board, coord_t coord, enum stone color)
219 board->hash ^= hash_at(board, coord, color);
220 if (DEBUGL(8))
221 fprintf(stderr, "board_hash_update(%d,%d,%d) ^ %llx -> %llx\n", color, coord_x(coord, board), coord_y(coord, board), hash_at(board, coord, color), board->hash);
224 /* Commit current board hash to history. */
225 static void profiling_noinline
226 board_hash_commit(struct board *board)
228 if (DEBUGL(8))
229 fprintf(stderr, "board_hash_commit %llx\n", board->hash);
230 if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
231 board->history_hash[board->hash & history_hash_mask] = board->hash;
232 } else {
233 hash_t i = board->hash;
234 while (board->history_hash[i & history_hash_mask]) {
235 if (board->history_hash[i & history_hash_mask] == board->hash) {
236 if (DEBUGL(5))
237 fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
238 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
239 board->superko_violation = true;
240 return;
242 i = history_hash_next(i);
244 board->history_hash[i & history_hash_mask] = board->hash;
249 void
250 board_handicap_stone(struct board *board, int x, int y, FILE *f)
252 struct move m;
253 m.color = S_BLACK;
254 coord_xy(m.coord, x, y, board);
256 board_play(board, &m);
258 char *str = coord2str(m.coord, board);
259 if (DEBUGL(1))
260 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
261 fprintf(f, "%s ", str);
262 free(str);
265 void
266 board_handicap(struct board *board, int stones, FILE *f)
268 int margin = 3 + (board->size >= 13);
269 int min = margin;
270 int mid = board->size / 2;
271 int max = board->size - 1 - margin;
272 const int places[][2] = {
273 { min, min }, { max, max }, { max, min }, { min, max },
274 { min, mid }, { max, mid },
275 { mid, min }, { mid, max },
276 { mid, mid },
279 board->handicap = stones;
281 if (stones == 5 || stones == 7) {
282 board_handicap_stone(board, mid, mid, f);
283 stones--;
286 int i;
287 for (i = 0; i < stones; i++)
288 board_handicap_stone(board, places[i][0], places[i][1], f);
292 static void __attribute__((noinline))
293 check_libs_consistency(struct board *board, group_t g)
295 #ifdef DEBUG
296 if (!g) return;
297 struct group *gi = &board_group_info(board, g);
298 for (int i = 0; i < gi->libs; i++)
299 if (board_at(board, gi->lib[i]) != S_NONE) {
300 fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(g, board));
301 assert(0);
303 #endif
306 static void
307 board_capturable_add(struct board *board, group_t group)
309 #ifdef WANT_BOARD_C
310 //fprintf(stderr, "add of group %d (%d)\n", group, board->clen);
311 assert(board->clen < board->size2);
312 board->c[board->clen++] = group;
313 #endif
315 static void
316 board_capturable_rm(struct board *board, group_t group)
318 #ifdef WANT_BOARD_C
319 //fprintf(stderr, "rm of group %d\n", group);
320 for (int i = 0; i < board->clen; i++) {
321 if (unlikely(board->c[i] == group)) {
322 board->c[i] = board->c[--board->clen];
323 return;
326 fprintf(stderr, "rm of bad group %d\n", group);
327 assert(0);
328 #endif
331 static void
332 board_group_addlib(struct board *board, group_t group, coord_t coord)
334 if (DEBUGL(7)) {
335 fprintf(stderr, "Group %d[%s]: Adding liberty %s\n",
336 group, coord2sstr(group, board), coord2sstr(coord, board));
339 check_libs_consistency(board, group);
341 struct group *gi = &board_group_info(board, group);
342 if (gi->libs < GROUP_KEEP_LIBS) {
343 for (int i = 0; i < gi->libs; i++)
344 if (gi->lib[i] == coord)
345 return;
346 if (gi->libs == 0)
347 board_capturable_add(board, group);
348 else if (gi->libs == 1)
349 board_capturable_rm(board, group);
350 gi->lib[gi->libs++] = coord;
354 static void
355 board_group_rmlib(struct board *board, group_t group, coord_t coord)
357 if (DEBUGL(7)) {
358 fprintf(stderr, "Group %d[%s]: Removing liberty %s\n",
359 group, coord2sstr(group, board), coord2sstr(coord, board));
362 struct group *gi = &board_group_info(board, group);
363 for (int i = 0; i < gi->libs; i++) {
364 if (gi->lib[i] == coord) {
365 for (i++; i < gi->libs; i++)
366 gi->lib[i - 1] = gi->lib[i];
367 gi->libs--;
369 check_libs_consistency(board, group);
370 if (gi->libs < GROUP_KEEP_LIBS - 1) {
371 if (gi->libs == 1)
372 board_capturable_add(board, group);
373 else if (gi->libs == 0)
374 board_capturable_rm(board, group);
375 return;
377 goto find_extra_lib;
381 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
382 * can call this multiple times per coord. */
383 check_libs_consistency(board, group);
384 return;
386 /* Add extra liberty from the board to our liberty list. */
387 find_extra_lib:;
388 bool watermark[board->size2];
389 memset(watermark, 0, sizeof(watermark));
391 foreach_in_group(board, group) {
392 coord_t coord2 = c;
393 foreach_neighbor(board, coord2, {
394 if (likely(watermark[coord_raw(c)]))
395 continue;
396 watermark[coord_raw(c)] = true;
397 if (c != coord && board_at(board, c) == S_NONE) {
398 bool next = false;
399 for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++) {
400 if (gi->lib[i] == c) {
401 next = true;
402 break;
405 if (!next) {
406 gi->lib[gi->libs++] = c;
407 return;
410 } );
411 } foreach_in_group_end;
415 /* This is a low-level routine that doesn't maintain consistency
416 * of all the board data structures. Use board_group_capture() from
417 * your code. */
418 static void
419 board_remove_stone(struct board *board, coord_t c)
421 enum stone color = board_at(board, c);
422 board_at(board, c) = S_NONE;
423 group_at(board, c) = 0;
424 board_hash_update(board, c, color);
426 /* Increase liberties of surrounding groups */
427 coord_t coord = c;
428 foreach_neighbor(board, coord, {
429 dec_neighbor_count_at(board, c, color);
430 board_group_addlib(board, group_at(board, c), coord);
433 if (DEBUGL(6))
434 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
435 board->f[board->flen++] = coord_raw(c);
439 static void profiling_noinline
440 add_to_group(struct board *board, int gid, coord_t prevstone, coord_t coord)
442 foreach_neighbor(board, coord, {
443 if (board_at(board, c) == S_NONE)
444 board_group_addlib(board, gid, c);
447 group_at(board, coord) = gid;
448 groupnext_at(board, coord) = groupnext_at(board, prevstone);
449 groupnext_at(board, prevstone) = coord_raw(coord);
451 if (DEBUGL(8))
452 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
453 coord_x(prevstone, board), coord_y(prevstone, board),
454 coord_x(coord, board), coord_y(coord, board),
455 groupnext_at(board, coord) % board->size, groupnext_at(board, coord) / board->size,
456 gid);
459 static void profiling_noinline
460 merge_groups(struct board *board, group_t group_to, group_t group_from)
462 if (DEBUGL(7))
463 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
464 group_from, group_to);
466 coord_t last_in_group;
467 foreach_in_group(board, group_from) {
468 last_in_group = c;
469 group_at(board, c) = group_to;
470 } foreach_in_group_end;
471 groupnext_at(board, last_in_group) = groupnext_at(board, group_to);
472 groupnext_at(board, group_to) = group_from;
474 struct group *gi_from = &board_group_info(board, group_from);
475 struct group *gi_to = &board_group_info(board, group_to);
476 if (gi_to->libs < GROUP_KEEP_LIBS) {
477 for (int i = 0; i < gi_from->libs; i++) {
478 for (int j = 0; j < gi_to->libs; j++)
479 if (gi_to->lib[j] == gi_from->lib[i])
480 goto next_from_lib;
481 if (gi_to->libs == 0)
482 board_capturable_add(board, group_to);
483 else if (gi_to->libs == 1)
484 board_capturable_rm(board, group_to);
485 gi_to->lib[gi_to->libs++] = gi_from->lib[i];
486 if (gi_to->libs >= GROUP_KEEP_LIBS)
487 break;
488 next_from_lib:;
492 if (gi_from->libs == 1)
493 board_capturable_rm(board, group_from);
494 memset(gi_from, 0, sizeof(struct group));
496 if (DEBUGL(7))
497 fprintf(stderr, "board_play_raw: merged group: %d\n",
498 group_to);
501 static group_t profiling_noinline
502 new_group(struct board *board, coord_t coord)
504 group_t gid = coord_raw(coord);
505 foreach_neighbor(board, coord, {
506 if (board_at(board, c) == S_NONE)
507 board_group_addlib(board, gid, c);
510 group_at(board, coord) = gid;
511 groupnext_at(board, coord) = 0;
513 if (DEBUGL(8))
514 fprintf(stderr, "new_group: added %d,%d to group %d\n",
515 coord_x(coord, board), coord_y(coord, board),
516 gid);
518 return gid;
521 /* We played on a place with at least one liberty. We will become a member of
522 * some group for sure. */
523 static int profiling_noinline
524 board_play_outside(struct board *board, struct move *m, int f)
526 coord_t coord = m->coord;
527 enum stone color = m->color;
528 enum stone other_color = stone_other(color);
529 int gid = 0;
531 board->f[f] = board->f[--board->flen];
532 if (DEBUGL(6))
533 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
535 foreach_neighbor(board, coord, {
536 enum stone ncolor = board_at(board, c);
537 group_t ngroup = group_at(board, c);
539 inc_neighbor_count_at(board, c, color);
541 if (!ngroup)
542 continue;
544 board_group_rmlib(board, ngroup, coord);
545 if (DEBUGL(7))
546 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
547 ngroup, ncolor, color, other_color);
549 if (ncolor == color && ngroup != gid) {
550 if (gid <= 0) {
551 gid = ngroup;
552 add_to_group(board, gid, c, coord);
553 } else {
554 merge_groups(board, gid, ngroup);
556 } else if (ncolor == other_color) {
557 if (DEBUGL(8)) {
558 struct group *gi = &board_group_info(board, ngroup);
559 fprintf(stderr, "testing captured group %d[%s]: ", ngroup, coord2sstr(ngroup, board));
560 for (int i = 0; i < gi->libs; i++)
561 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
562 fprintf(stderr, "\n");
564 if (unlikely(board_group_captured(board, ngroup)))
565 board_group_capture(board, ngroup);
569 if (unlikely(gid <= 0))
570 gid = new_group(board, coord);
572 board_at(board, coord) = color;
573 board->last_move = *m;
574 board->moves++;
575 board_hash_update(board, coord, color);
576 struct move ko = { pass, S_NONE };
577 board->ko = ko;
579 return gid;
582 /* We played in an eye-like shape. Either we capture at least one of the eye
583 * sides in the process of playing, or return -1. */
584 static int profiling_noinline
585 board_play_in_eye(struct board *board, struct move *m, int f)
587 coord_t coord = m->coord;
588 enum stone color = m->color;
589 /* Check ko: Capture at a position of ko capture one move ago */
590 if (unlikely(color == board->ko.color && coord_eq(coord, board->ko.coord))) {
591 if (DEBUGL(5))
592 fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
593 return -1;
594 } else if (DEBUGL(6)) {
595 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
596 color, coord_x(coord, board), coord_y(coord, board),
597 board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
600 struct move ko = { pass, S_NONE };
602 board->f[f] = board->f[--board->flen];
603 if (DEBUGL(6))
604 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
606 int captured_groups = 0;
608 foreach_neighbor(board, coord, {
609 group_t group = group_at(board, c);
610 if (!group)
611 continue;
613 board_group_rmlib(board, group, coord);
614 if (DEBUGL(7))
615 fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
616 group);
618 if (unlikely(board_group_captured(board, group))) {
619 captured_groups++;
620 if (board_group_capture(board, group) == 1) {
621 /* If we captured multiple groups at once,
622 * we can't be fighting ko so we don't need
623 * to check for that. */
624 ko.color = stone_other(color);
625 ko.coord = c;
626 if (DEBUGL(5))
627 fprintf(stderr, "guarding ko at %d,%d,%d\n", ko.color, coord_x(ko.coord, board), coord_y(ko.coord, board));
632 if (likely(captured_groups == 0)) {
633 if (DEBUGL(5)) {
634 if (DEBUGL(6))
635 board_print(board, stderr);
636 fprintf(stderr, "board_check: one-stone suicide\n");
639 foreach_neighbor(board, coord, {
640 board_group_addlib(board, group_at(board, c), coord);
641 if (DEBUGL(7))
642 fprintf(stderr, "board_play_raw: restoring libs for group %d\n",
643 group_at(board, c));
646 coord_t c = coord;
647 if (DEBUGL(6))
648 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
649 board->f[board->flen++] = coord_raw(c);
650 return -1;
653 foreach_neighbor(board, coord, {
654 inc_neighbor_count_at(board, c, color);
657 board_at(board, coord) = color;
659 board->last_move = *m;
660 board->moves++;
661 board_hash_update(board, coord, color);
662 board_hash_commit(board);
663 board->ko = ko;
665 return new_group(board, coord);
668 static int __attribute__((flatten))
669 board_play_f(struct board *board, struct move *m, int f)
671 if (DEBUGL(7)) {
672 fprintf(stderr, "board_play(): ---- Playing %d,%d\n", coord_x(m->coord, board), coord_y(m->coord, board));
674 if (likely(!board_is_eyelike(board, &m->coord, stone_other(m->color)))) {
675 /* NOT playing in an eye. Thus this move has to succeed. (This
676 * is thanks to New Zealand rules. Otherwise, multi-stone
677 * suicide might fail.) */
678 int gid = board_play_outside(board, m, f);
679 if (unlikely(board_group_captured(board, gid))) {
680 board_group_capture(board, gid);
682 board_hash_commit(board);
683 return 0;
684 } else {
685 return board_play_in_eye(board, m, f);
690 board_play(struct board *board, struct move *m)
692 if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
693 board->last_move = *m;
694 return 0;
697 int f;
698 for (f = 0; f < board->flen; f++)
699 if (board->f[f] == coord_raw(m->coord))
700 return board_play_f(board, m, f);
702 if (DEBUGL(7))
703 fprintf(stderr, "board_check: stone exists\n");
704 return -1;
708 static inline bool
709 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f)
711 coord_raw(*coord) = b->f[f];
712 if (is_pass(*coord))
713 return random_pass;
714 struct move m = { *coord, color };
715 if (DEBUGL(6))
716 fprintf(stderr, "trying random move %d: %d,%d\n", f, coord_x(*coord, b), coord_y(*coord, b));
717 return (!board_is_one_point_eye(b, coord, color) /* bad idea to play into one, usually */
718 && board_play_f(b, &m, f) >= 0);
721 void
722 board_play_random(struct board *b, enum stone color, coord_t *coord)
724 int base = fast_random(b->flen);
725 coord_pos(*coord, base, b);
726 if (likely(board_try_random_move(b, color, coord, base)))
727 return;
729 int f;
730 for (f = base + 1; f < b->flen; f++)
731 if (board_try_random_move(b, color, coord, f))
732 return;
733 for (f = 0; f < base; f++)
734 if (board_try_random_move(b, color, coord, f))
735 return;
737 *coord = pass;
741 bool
742 board_is_eyelike(struct board *board, coord_t *coord, enum stone eye_color)
744 return (neighbor_count_at(board, *coord, eye_color) + neighbor_count_at(board, *coord, S_OFFBOARD)) == 4;
747 bool
748 board_is_one_point_eye(struct board *board, coord_t *coord, enum stone eye_color)
750 enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
752 if (likely(neighbor_count_at(board, *coord, eye_color) + neighbor_count_at(board, *coord, S_OFFBOARD) < 4)) {
753 return false;
756 /* XXX: We attempt false eye detection but we will yield false
757 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
759 foreach_diag_neighbor(board, *coord) {
760 color_diag_libs[(enum stone) board_at(board, c)]++;
761 } foreach_diag_neighbor_end;
762 color_diag_libs[stone_other(eye_color)] += !!color_diag_libs[S_OFFBOARD];
763 return likely(color_diag_libs[stone_other(eye_color)] < 2);
766 enum stone
767 board_get_one_point_eye(struct board *board, coord_t *coord)
769 if (board_is_one_point_eye(board, coord, S_WHITE))
770 return S_WHITE;
771 else if (board_is_one_point_eye(board, coord, S_BLACK))
772 return S_BLACK;
773 else
774 return S_NONE;
778 int profiling_noinline
779 board_group_capture(struct board *board, int group)
781 int stones = 0;
783 foreach_in_group(board, group) {
784 board->captures[stone_other(board_at(board, c))]++;
785 board_remove_stone(board, c);
786 stones++;
787 } foreach_in_group_end;
789 if (board_group_info(board, group).libs == 1)
790 board_capturable_rm(board, group);
791 memset(&board_group_info(board, group), 0, sizeof(struct group));
793 return stones;
796 bool
797 board_group_in_atari(struct board *board, group_t group, coord_t *lastlib)
799 if (board_group_info(board, group).libs != 1)
800 return false;
801 *lastlib = board_group_info(board, group).lib[0];
802 return true;
805 bool
806 board_group_can_atari(struct board *board, group_t group, coord_t lastlib[2])
808 if (board_group_info(board, group).libs != 2)
809 return false;
810 lastlib[0] = board_group_info(board, group).lib[0];
811 lastlib[1] = board_group_info(board, group).lib[1];
812 return true;
816 static enum stone
817 board_tromp_taylor_owner(struct board *board, coord_t c)
819 int x = coord_x(c, board), y = coord_y(c, board);
820 enum stone color = S_NONE;
821 #define TEST_REACH(xx, yy) \
823 enum stone c2 = board_atxy(board, xx, yy); \
824 if (c2 != S_NONE) { \
825 if (color != S_NONE && color != c2) \
826 return S_NONE; \
827 color = c2; \
828 break; \
831 for (int i = x; i > 0; i--)
832 TEST_REACH(i, y);
833 for (int i = x; i < board->size - 1; i++)
834 TEST_REACH(i, y);
835 for (int i = y; i > 0; i--)
836 TEST_REACH(x, i);
837 for (int i = y; i < board->size - 1; i++)
838 TEST_REACH(x, i);
839 return color;
842 /* Tromp-Taylor Counting */
843 float
844 board_official_score(struct board *board)
847 /* A point P, not colored C, is said to reach C, if there is a path of
848 * (vertically or horizontally) adjacent points of P's color from P to
849 * a point of color C.
851 * A player's score is the number of points of her color, plus the
852 * number of empty points that reach only her color. */
854 int scores[S_MAX];
855 memset(scores, 0, sizeof(scores));
857 foreach_point(board) {
858 enum stone color = board_at(board, c);
859 if (color == S_NONE)
860 color = board_tromp_taylor_owner(board, c);
861 scores[color]++;
862 } foreach_point_end;
864 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
867 float
868 board_fast_score(struct board *board)
870 int scores[S_MAX];
871 memset(scores, 0, sizeof(scores));
873 foreach_point(board) {
874 enum stone color = board_at(board, c);
875 if (color == S_NONE)
876 color = board_get_one_point_eye(board, &c);
877 scores[color]++;
878 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
879 } foreach_point_end;
881 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
885 bool
886 valid_escape_route(struct board *b, enum stone color, coord_t to)
888 /* Assess if we actually gain any liberties by this escape route.
889 * Note that this is not 100% as we cannot check whether we are
890 * connecting out or just to ourselves. */
891 /* Also, we prohibit 1-1 here:
892 * X X X X |
893 * O X O O |
894 * O O X O |
895 * .(O)X . |
896 * --------+
898 int friends = neighbor_count_at(b, to, color);
899 int borders = neighbor_count_at(b, to, S_OFFBOARD);
900 int libs = immediate_liberty_count(b, to);
901 return (friends > 1 && friends + borders < 4) || (libs > 1);
905 bool
906 board_stone_radar(struct board *b, coord_t coord, int distance)
908 int bounds[4] = {
909 coord_x(coord, b) - distance,
910 coord_y(coord, b) - distance,
911 coord_x(coord, b) + distance,
912 coord_y(coord, b) + distance
914 for (int i = 0; i < 4; i++)
915 if (bounds[i] < 1)
916 bounds[i] = 1;
917 else if (bounds[i] > b->size - 2)
918 bounds[i] = b->size - 2;
919 for (int x = bounds[0]; x <= bounds[2]; x++)
920 for (int y = bounds[1]; y <= bounds[3]; y++)
921 if (board_atxy(b, x, y) != S_NONE) {
922 //fprintf(stderr, "radar %d,%d,%d: %d,%d (%d)\n", coord_x(coord, b), coord_y(coord, b), distance, x, y, board_atxy(b, x, y));
923 return true;
925 return false;