board_play_in_eye(): Normalize return value
[pachi.git] / board.c
blobbda88f5782ab29a6612468ff5a6907552c860e3b
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, group_t 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 = board_size2(b2) * sizeof(*b2->b);
49 int gsize = board_size2(b2) * sizeof(*b2->g);
50 int fsize = board_size2(b2) * sizeof(*b2->f);
51 int nsize = board_size2(b2) * sizeof(*b2->n);
52 int psize = board_size2(b2) * sizeof(*b2->p);
53 int hsize = board_size2(b2) * 2 * sizeof(*b2->h);
54 int gisize = board_size2(b2) * sizeof(*b2->gi);
55 #ifdef WANT_BOARD_C
56 int csize = board_size2(b2) * 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 #ifdef BOARD_SIZE
93 assert(board_size(board) == size + 2);
94 #else
95 board_size(board) = size + 2 /* S_OFFBOARD margin */;
96 board_size2(board) = board_size(board) * board_size(board);
97 #endif
98 if (board->b)
99 free(board->b);
101 int bsize = board_size2(board) * sizeof(*board->b);
102 int gsize = board_size2(board) * sizeof(*board->g);
103 int fsize = board_size2(board) * sizeof(*board->f);
104 int nsize = board_size2(board) * sizeof(*board->n);
105 int psize = board_size2(board) * sizeof(*board->p);
106 int hsize = board_size2(board) * 2 * sizeof(*board->h);
107 int gisize = board_size2(board) * sizeof(*board->gi);
108 #ifdef WANT_BOARD_C
109 int csize = board_size2(board) * sizeof(*board->c);
110 #else
111 int csize = 0;
112 #endif
113 void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
114 memset(x, 0, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
115 board->b = x; x += bsize;
116 board->g = x; x += gsize;
117 board->f = x; x += fsize;
118 board->p = x; x += psize;
119 board->n = x; x += nsize;
120 board->h = x; x += hsize;
121 board->gi = x; x += gisize;
122 #ifdef WANT_BOARD_C
123 board->c = x; x += csize;
124 #endif
127 void
128 board_clear(struct board *board)
130 int size = board_size(board);
132 board_done_noalloc(board);
133 board_setup(board);
134 board_resize(board, size - 2 /* S_OFFBOARD margin */);
136 /* Draw the offboard margin */
137 int top_row = board_size2(board) - board_size(board);
138 int i;
139 for (i = 0; i < board_size(board); i++)
140 board->b[i] = board->b[top_row + i] = S_OFFBOARD;
141 for (i = 0; i <= top_row; i += board_size(board))
142 board->b[i] = board->b[board_size(board) - 1 + i] = S_OFFBOARD;
144 foreach_point(board) {
145 coord_t coord = c;
146 if (board_at(board, coord) == S_OFFBOARD)
147 continue;
148 foreach_neighbor(board, c, {
149 inc_neighbor_count_at(board, coord, board_at(board, c));
150 } );
151 } foreach_point_end;
153 /* First, pass is always a free position. */
154 board->f[board->flen++] = coord_raw(pass);
155 /* All positions are free! Except the margin. */
156 for (i = board_size(board); i < (board_size(board) - 1) * board_size(board); i++)
157 if (i % board_size(board) != 0 && i % board_size(board) != board_size(board) - 1)
158 board->f[board->flen++] = i;
160 /* Initialize zobrist hashtable. */
161 foreach_point(board) {
162 int max = (sizeof(hash_t) << history_hash_bits);
163 /* fast_random() is 16-bit only */
164 board->h[coord_raw(c) * 2] = ((hash_t) fast_random(max))
165 | ((hash_t) fast_random(max) << 16)
166 | ((hash_t) fast_random(max) << 32)
167 | ((hash_t) fast_random(max) << 48);
168 if (!board->h[coord_raw(c) * 2])
169 /* Would be kinda "oops". */
170 board->h[coord_raw(c) * 2] = 1;
171 /* And once again for white */
172 board->h[coord_raw(c) * 2 + 1] = ((hash_t) fast_random(max))
173 | ((hash_t) fast_random(max) << 16)
174 | ((hash_t) fast_random(max) << 32)
175 | ((hash_t) fast_random(max) << 48);
176 if (!board->h[coord_raw(c) * 2 + 1])
177 board->h[coord_raw(c) * 2 + 1] = 1;
178 } foreach_point_end;
182 void
183 board_print(struct board *board, FILE *f)
185 fprintf(f, "Move: % 3d Komi: %2.1f Captures B: %d W: %d\n ",
186 board->moves, board->komi,
187 board->captures[S_BLACK], board->captures[S_WHITE]);
188 int x, y;
189 char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
190 for (x = 1; x < board_size(board) - 1; x++)
191 fprintf(f, "%c ", asdf[x - 1]);
192 fprintf(f, "\n +-");
193 for (x = 1; x < board_size(board) - 1; x++)
194 fprintf(f, "--");
195 fprintf(f, "+\n");
196 for (y = board_size(board) - 2; y >= 1; y--) {
197 fprintf(f, "%2d | ", y);
198 for (x = 1; x < board_size(board) - 1; x++) {
199 if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
200 fprintf(f, "%c)", stone2char(board_atxy(board, x, y)));
201 else
202 fprintf(f, "%c ", stone2char(board_atxy(board, x, y)));
204 if (DEBUGL(6)) {
205 fprintf(f, "| ");
206 for (x = 1; x < board_size(board) - 1; x++) {
207 fprintf(f, "%d ", group_base(group_atxy(board, x, y)));
210 fprintf(f, "|\n");
212 fprintf(f, " +-");
213 for (x = 1; x < board_size(board) - 1; x++)
214 fprintf(f, "--");
215 fprintf(f, "+\n\n");
219 /* Update board hash with given coordinate. */
220 static void profiling_noinline
221 board_hash_update(struct board *board, coord_t coord, enum stone color)
223 board->hash ^= hash_at(board, coord, color);
224 if (DEBUGL(8))
225 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);
228 /* Commit current board hash to history. */
229 static void profiling_noinline
230 board_hash_commit(struct board *board)
232 if (DEBUGL(8))
233 fprintf(stderr, "board_hash_commit %llx\n", board->hash);
234 if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
235 board->history_hash[board->hash & history_hash_mask] = board->hash;
236 } else {
237 hash_t i = board->hash;
238 while (board->history_hash[i & history_hash_mask]) {
239 if (board->history_hash[i & history_hash_mask] == board->hash) {
240 if (DEBUGL(5))
241 fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
242 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
243 board->superko_violation = true;
244 return;
246 i = history_hash_next(i);
248 board->history_hash[i & history_hash_mask] = board->hash;
253 void
254 board_handicap_stone(struct board *board, int x, int y, FILE *f)
256 struct move m;
257 m.color = S_BLACK;
258 coord_xy(m.coord, x, y, board);
260 board_play(board, &m);
262 char *str = coord2str(m.coord, board);
263 if (DEBUGL(1))
264 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
265 fprintf(f, "%s ", str);
266 free(str);
269 void
270 board_handicap(struct board *board, int stones, FILE *f)
272 int margin = 3 + (board_size(board) >= 13);
273 int min = margin;
274 int mid = board_size(board) / 2;
275 int max = board_size(board) - 1 - margin;
276 const int places[][2] = {
277 { min, min }, { max, max }, { max, min }, { min, max },
278 { min, mid }, { max, mid },
279 { mid, min }, { mid, max },
280 { mid, mid },
283 board->handicap = stones;
285 if (stones == 5 || stones == 7) {
286 board_handicap_stone(board, mid, mid, f);
287 stones--;
290 int i;
291 for (i = 0; i < stones; i++)
292 board_handicap_stone(board, places[i][0], places[i][1], f);
296 static void __attribute__((noinline))
297 check_libs_consistency(struct board *board, group_t g)
299 #ifdef DEBUG
300 if (!g) return;
301 struct group *gi = &board_group_info(board, g);
302 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
303 if (gi->lib[i] && board_at(board, gi->lib[i]) != S_NONE) {
304 fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(group_base(g), board));
305 assert(0);
307 #endif
310 static void
311 board_capturable_add(struct board *board, group_t group)
313 #ifdef WANT_BOARD_C
314 //fprintf(stderr, "add of group %d (%d)\n", group_base(group), board->clen);
315 assert(group);
316 assert(board->clen < board_size2(board));
317 board->c[board->clen++] = group;
318 #endif
320 static void
321 board_capturable_rm(struct board *board, group_t group)
323 #ifdef WANT_BOARD_C
324 //fprintf(stderr, "rm of group %d\n", group_base(group));
325 for (int i = 0; i < board->clen; i++) {
326 if (unlikely(board->c[i] == group)) {
327 board->c[i] = board->c[--board->clen];
328 return;
331 fprintf(stderr, "rm of bad group %d\n", group_base(group));
332 assert(0);
333 #endif
336 static void
337 board_group_addlib(struct board *board, group_t group, coord_t coord, bool fresh)
339 if (DEBUGL(7)) {
340 fprintf(stderr, "Group %d[%s]: Adding liberty %s\n",
341 group_base(group), coord2sstr(group_base(group), board), coord2sstr(coord, board));
344 check_libs_consistency(board, group);
346 struct group *gi = &board_group_info(board, group);
347 if (gi->libs < GROUP_KEEP_LIBS) {
348 if (!fresh)
349 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
350 #if 0
351 /* Seems extra branch just slows it down */
352 if (!gi->lib[i])
353 break;
354 #endif
355 if (unlikely(gi->lib[i] == coord))
356 return;
358 if (gi->libs == 0)
359 board_capturable_add(board, group);
360 else if (gi->libs == 1)
361 board_capturable_rm(board, group);
362 gi->lib[gi->libs++] = coord;
365 check_libs_consistency(board, group);
368 static void
369 board_group_rmlib(struct board *board, group_t group, coord_t coord)
371 if (DEBUGL(7)) {
372 fprintf(stderr, "Group %d[%s]: Removing liberty %s\n",
373 group_base(group), coord2sstr(group_base(group), board), coord2sstr(coord, board));
376 struct group *gi = &board_group_info(board, group);
377 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
378 #if 0
379 /* Seems extra branch just slows it down */
380 if (!gi->lib[i])
381 break;
382 #endif
383 if (likely(gi->lib[i] != coord))
384 continue;
386 int j = i;
387 for (i++; i < GROUP_KEEP_LIBS; i++)
388 if (!gi->lib[i])
389 break; /* Unfilled liberties. */
390 gi->lib[j] = gi->lib[i - 1];
391 gi->lib[--gi->libs] = 0;
393 check_libs_consistency(board, group);
394 if (gi->libs < GROUP_KEEP_LIBS - 1) {
395 if (gi->libs == 1)
396 board_capturable_add(board, group);
397 else if (gi->libs == 0)
398 board_capturable_rm(board, group);
399 return;
401 /* Postpone refilling lib[] until we need to. */
402 if (i > GROUP_REFILL_LIBS)
403 return;
404 goto find_extra_lib;
407 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
408 * can call this multiple times per coord. */
409 check_libs_consistency(board, group);
410 return;
412 /* Add extra liberty from the board to our liberty list. */
413 find_extra_lib:;
414 bool watermark[board_size2(board)];
415 memset(watermark, 0, sizeof(watermark));
417 foreach_in_group(board, group) {
418 coord_t coord2 = c;
419 foreach_neighbor(board, coord2, {
420 if (likely(watermark[coord_raw(c)]))
421 continue;
422 watermark[coord_raw(c)] = true;
423 if (c != coord && board_at(board, c) == S_NONE) {
424 bool next = false;
425 for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++) {
426 if (gi->lib[i] == c) {
427 next = true;
428 break;
431 if (!next) {
432 gi->lib[gi->libs++] = c;
433 if (gi->libs >= GROUP_KEEP_LIBS)
434 return;
437 } );
438 } foreach_in_group_end;
442 /* This is a low-level routine that doesn't maintain consistency
443 * of all the board data structures. Use board_group_capture() from
444 * your code. */
445 static void
446 board_remove_stone(struct board *board, coord_t c)
448 enum stone color = board_at(board, c);
449 board_at(board, c) = S_NONE;
450 group_at(board, c) = 0;
451 board_hash_update(board, c, color);
453 /* Increase liberties of surrounding groups */
454 coord_t coord = c;
455 foreach_neighbor(board, coord, {
456 dec_neighbor_count_at(board, c, color);
457 group_t g = group_at(board, c);
458 if (g)
459 board_group_addlib(board, g, coord, true);
462 if (DEBUGL(6))
463 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
464 board->f[board->flen++] = coord_raw(c);
468 static void profiling_noinline
469 add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord)
471 foreach_neighbor(board, coord, {
472 if (board_at(board, c) == S_NONE)
473 board_group_addlib(board, group, c, false);
476 group_at(board, coord) = group;
477 groupnext_at(board, coord) = groupnext_at(board, prevstone);
478 groupnext_at(board, prevstone) = coord_raw(coord);
480 if (DEBUGL(8))
481 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
482 coord_x(prevstone, board), coord_y(prevstone, board),
483 coord_x(coord, board), coord_y(coord, board),
484 groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
485 group_base(group));
488 static void profiling_noinline
489 merge_groups(struct board *board, group_t group_to, group_t group_from)
491 if (DEBUGL(7))
492 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
493 group_base(group_from), group_base(group_to));
495 coord_t last_in_group;
496 foreach_in_group(board, group_from) {
497 last_in_group = c;
498 group_at(board, c) = group_to;
499 } foreach_in_group_end;
500 groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to));
501 groupnext_at(board, group_base(group_to)) = group_base(group_from);
503 struct group *gi_from = &board_group_info(board, group_from);
504 struct group *gi_to = &board_group_info(board, group_to);
505 if (gi_to->libs < GROUP_KEEP_LIBS) {
506 for (int i = 0; i < gi_from->libs; i++) {
507 for (int j = 0; j < gi_to->libs; j++)
508 if (gi_to->lib[j] == gi_from->lib[i])
509 goto next_from_lib;
510 if (gi_to->libs == 0)
511 board_capturable_add(board, group_to);
512 else if (gi_to->libs == 1)
513 board_capturable_rm(board, group_to);
514 gi_to->lib[gi_to->libs++] = gi_from->lib[i];
515 if (gi_to->libs >= GROUP_KEEP_LIBS)
516 break;
517 next_from_lib:;
521 if (gi_from->libs == 1)
522 board_capturable_rm(board, group_from);
523 memset(gi_from, 0, sizeof(struct group));
525 if (DEBUGL(7))
526 fprintf(stderr, "board_play_raw: merged group: %d\n",
527 group_base(group_to));
530 static group_t profiling_noinline
531 new_group(struct board *board, coord_t coord)
533 group_t group = coord_raw(coord);
534 struct group *gi = &board_group_info(board, group);
535 foreach_neighbor(board, coord, {
536 if (board_at(board, c) == S_NONE)
537 /* board_group_addlib is ridiculously expensive for us */
538 #if GROUP_KEEP_LIBS < 4
539 if (gi->libs < GROUP_KEEP_LIBS)
540 #endif
541 gi->lib[gi->libs++] = c;
543 if (gi->libs == 1)
544 board_capturable_add(board, group);
545 check_libs_consistency(board, group);
547 group_at(board, coord) = group;
548 groupnext_at(board, coord) = 0;
550 if (DEBUGL(8))
551 fprintf(stderr, "new_group: added %d,%d to group %d\n",
552 coord_x(coord, board), coord_y(coord, board),
553 group_base(group));
555 return group;
558 static inline group_t
559 play_one_neighbor(struct board *board,
560 coord_t coord, enum stone color, enum stone other_color,
561 coord_t c, group_t group)
563 enum stone ncolor = board_at(board, c);
564 group_t ngroup = group_at(board, c);
566 inc_neighbor_count_at(board, c, color);
568 if (!ngroup)
569 return group;
571 board_group_rmlib(board, ngroup, coord);
572 if (DEBUGL(7))
573 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
574 group_base(ngroup), ncolor, color, other_color);
576 if (ncolor == color && ngroup != group) {
577 if (!group) {
578 group = ngroup;
579 add_to_group(board, group, c, coord);
580 } else {
581 merge_groups(board, group, ngroup);
583 } else if (ncolor == other_color) {
584 if (DEBUGL(8)) {
585 struct group *gi = &board_group_info(board, ngroup);
586 fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board));
587 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
588 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
589 fprintf(stderr, "\n");
591 if (unlikely(board_group_captured(board, ngroup)))
592 board_group_capture(board, ngroup);
594 return group;
597 /* We played on a place with at least one liberty. We will become a member of
598 * some group for sure. */
599 static group_t profiling_noinline
600 board_play_outside(struct board *board, struct move *m, int f)
602 coord_t coord = m->coord;
603 enum stone color = m->color;
604 enum stone other_color = stone_other(color);
605 group_t group = 0;
607 board->f[f] = board->f[--board->flen];
608 if (DEBUGL(6))
609 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
611 foreach_neighbor(board, coord, {
612 group = play_one_neighbor(board, coord, color, other_color, c, group);
615 if (unlikely(!group))
616 group = new_group(board, coord);
618 board_at(board, coord) = color;
619 board->last_move = *m;
620 board->moves++;
621 board_hash_update(board, coord, color);
622 struct move ko = { pass, S_NONE };
623 board->ko = ko;
625 return group;
628 /* We played in an eye-like shape. Either we capture at least one of the eye
629 * sides in the process of playing, or return -1. */
630 static int profiling_noinline
631 board_play_in_eye(struct board *board, struct move *m, int f)
633 coord_t coord = m->coord;
634 enum stone color = m->color;
635 /* Check ko: Capture at a position of ko capture one move ago */
636 if (unlikely(color == board->ko.color && coord_eq(coord, board->ko.coord))) {
637 if (DEBUGL(5))
638 fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
639 return -1;
640 } else if (DEBUGL(6)) {
641 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
642 color, coord_x(coord, board), coord_y(coord, board),
643 board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
646 struct move ko = { pass, S_NONE };
648 int captured_groups = 0;
650 foreach_neighbor(board, coord, {
651 captured_groups += (board_group_info(board, group_at(board, c)).libs == 1);
654 if (likely(captured_groups == 0)) {
655 if (DEBUGL(5)) {
656 if (DEBUGL(6))
657 board_print(board, stderr);
658 fprintf(stderr, "board_check: one-stone suicide\n");
661 return -1;
664 board->f[f] = board->f[--board->flen];
665 if (DEBUGL(6))
666 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
668 foreach_neighbor(board, coord, {
669 inc_neighbor_count_at(board, c, color);
671 group_t group = group_at(board, c);
672 if (!group)
673 continue;
675 board_group_rmlib(board, group, coord);
676 if (DEBUGL(7))
677 fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
678 group_base(group));
680 if (board_group_captured(board, group)) {
681 if (board_group_capture(board, group) == 1) {
682 /* If we captured multiple groups at once,
683 * we can't be fighting ko so we don't need
684 * to check for that. */
685 ko.color = stone_other(color);
686 ko.coord = c;
687 if (DEBUGL(5))
688 fprintf(stderr, "guarding ko at %d,%d,%d\n", ko.color, coord_x(ko.coord, board), coord_y(ko.coord, board));
693 board_at(board, coord) = color;
695 board->last_move = *m;
696 board->moves++;
697 board_hash_update(board, coord, color);
698 board_hash_commit(board);
699 board->ko = ko;
701 return !!new_group(board, coord);
704 static int __attribute__((flatten))
705 board_play_f(struct board *board, struct move *m, int f)
707 if (DEBUGL(7)) {
708 fprintf(stderr, "board_play(): ---- Playing %d,%d\n", coord_x(m->coord, board), coord_y(m->coord, board));
710 if (likely(!board_is_eyelike(board, &m->coord, stone_other(m->color)))) {
711 /* NOT playing in an eye. Thus this move has to succeed. (This
712 * is thanks to New Zealand rules. Otherwise, multi-stone
713 * suicide might fail.) */
714 group_t group = board_play_outside(board, m, f);
715 if (unlikely(board_group_captured(board, group))) {
716 board_group_capture(board, group);
718 board_hash_commit(board);
719 return 0;
720 } else {
721 return board_play_in_eye(board, m, f);
726 board_play(struct board *board, struct move *m)
728 if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
729 board->last_move = *m;
730 return 0;
733 int f;
734 for (f = 0; f < board->flen; f++)
735 if (board->f[f] == coord_raw(m->coord))
736 return board_play_f(board, m, f);
738 if (DEBUGL(7))
739 fprintf(stderr, "board_check: stone exists\n");
740 return -1;
744 static inline bool
745 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f)
747 coord_raw(*coord) = b->f[f];
748 if (unlikely(is_pass(*coord)))
749 return random_pass;
750 struct move m = { *coord, color };
751 if (DEBUGL(6))
752 fprintf(stderr, "trying random move %d: %d,%d\n", f, coord_x(*coord, b), coord_y(*coord, b));
753 return (likely(!board_is_one_point_eye(b, coord, color)) /* bad idea to play into one, usually */
754 && likely(board_play_f(b, &m, f) >= 0));
757 void
758 board_play_random(struct board *b, enum stone color, coord_t *coord)
760 int base = fast_random(b->flen);
761 coord_pos(*coord, base, b);
762 if (likely(board_try_random_move(b, color, coord, base)))
763 return;
765 int f;
766 for (f = base + 1; f < b->flen; f++)
767 if (board_try_random_move(b, color, coord, f))
768 return;
769 for (f = 0; f < base; f++)
770 if (board_try_random_move(b, color, coord, f))
771 return;
773 *coord = pass;
777 bool
778 board_is_eyelike(struct board *board, coord_t *coord, enum stone eye_color)
780 return (neighbor_count_at(board, *coord, eye_color) + neighbor_count_at(board, *coord, S_OFFBOARD)) == 4;
783 bool
784 board_is_one_point_eye(struct board *board, coord_t *coord, enum stone eye_color)
786 enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
788 if (likely(neighbor_count_at(board, *coord, eye_color) + neighbor_count_at(board, *coord, S_OFFBOARD) < 4)) {
789 return false;
792 /* XXX: We attempt false eye detection but we will yield false
793 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
795 foreach_diag_neighbor(board, *coord) {
796 color_diag_libs[(enum stone) board_at(board, c)]++;
797 } foreach_diag_neighbor_end;
798 color_diag_libs[stone_other(eye_color)] += !!color_diag_libs[S_OFFBOARD];
799 return likely(color_diag_libs[stone_other(eye_color)] < 2);
802 enum stone
803 board_get_one_point_eye(struct board *board, coord_t *coord)
805 if (board_is_one_point_eye(board, coord, S_WHITE))
806 return S_WHITE;
807 else if (board_is_one_point_eye(board, coord, S_BLACK))
808 return S_BLACK;
809 else
810 return S_NONE;
814 int profiling_noinline
815 board_group_capture(struct board *board, group_t group)
817 int stones = 0;
819 foreach_in_group(board, group) {
820 board->captures[stone_other(board_at(board, c))]++;
821 board_remove_stone(board, c);
822 stones++;
823 } foreach_in_group_end;
825 if (board_group_info(board, group).libs == 1)
826 board_capturable_rm(board, group);
827 memset(&board_group_info(board, group), 0, sizeof(struct group));
829 return stones;
832 bool
833 board_group_in_atari(struct board *board, group_t group, coord_t *lastlib)
835 if (board_group_info(board, group).libs != 1)
836 return false;
837 *lastlib = board_group_info(board, group).lib[0];
838 return true;
841 bool
842 board_group_can_atari(struct board *board, group_t group, coord_t lastlib[2])
844 if (board_group_info(board, group).libs != 2)
845 return false;
846 lastlib[0] = board_group_info(board, group).lib[0];
847 lastlib[1] = board_group_info(board, group).lib[1];
848 return true;
852 static enum stone
853 board_tromp_taylor_owner(struct board *board, coord_t c)
855 int x = coord_x(c, board), y = coord_y(c, board);
856 enum stone color = S_NONE;
857 #define TEST_REACH(xx, yy) \
859 enum stone c2 = board_atxy(board, xx, yy); \
860 if (c2 != S_NONE) { \
861 if (color != S_NONE && color != c2) \
862 return S_NONE; \
863 color = c2; \
864 break; \
867 for (int i = x; i > 0; i--)
868 TEST_REACH(i, y);
869 for (int i = x; i < board_size(board) - 1; i++)
870 TEST_REACH(i, y);
871 for (int i = y; i > 0; i--)
872 TEST_REACH(x, i);
873 for (int i = y; i < board_size(board) - 1; i++)
874 TEST_REACH(x, i);
875 return color;
878 /* Tromp-Taylor Counting */
879 float
880 board_official_score(struct board *board)
883 /* A point P, not colored C, is said to reach C, if there is a path of
884 * (vertically or horizontally) adjacent points of P's color from P to
885 * a point of color C.
887 * A player's score is the number of points of her color, plus the
888 * number of empty points that reach only her color. */
890 int scores[S_MAX];
891 memset(scores, 0, sizeof(scores));
893 foreach_point(board) {
894 enum stone color = board_at(board, c);
895 if (color == S_NONE)
896 color = board_tromp_taylor_owner(board, c);
897 scores[color]++;
898 } foreach_point_end;
900 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
903 float
904 board_fast_score(struct board *board)
906 int scores[S_MAX];
907 memset(scores, 0, sizeof(scores));
909 foreach_point(board) {
910 enum stone color = board_at(board, c);
911 if (color == S_NONE)
912 color = board_get_one_point_eye(board, &c);
913 scores[color]++;
914 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
915 } foreach_point_end;
917 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
921 bool
922 valid_escape_route(struct board *b, enum stone color, coord_t to)
924 /* Assess if we actually gain any liberties by this escape route.
925 * Note that this is not 100% as we cannot check whether we are
926 * connecting out or just to ourselves. */
927 /* Also, we prohibit 1-1 here:
928 * X X X X |
929 * O X O O |
930 * O O X O |
931 * .(O)X . |
932 * --------+
934 int friends = neighbor_count_at(b, to, color);
935 int borders = neighbor_count_at(b, to, S_OFFBOARD);
936 int libs = immediate_liberty_count(b, to);
937 return (friends > 1 && friends + borders < 4) || (libs > 1);
941 bool
942 board_stone_radar(struct board *b, coord_t coord, int distance)
944 int bounds[4] = {
945 coord_x(coord, b) - distance,
946 coord_y(coord, b) - distance,
947 coord_x(coord, b) + distance,
948 coord_y(coord, b) + distance
950 for (int i = 0; i < 4; i++)
951 if (bounds[i] < 1)
952 bounds[i] = 1;
953 else if (bounds[i] > board_size(b) - 2)
954 bounds[i] = board_size(b) - 2;
955 for (int x = bounds[0]; x <= bounds[2]; x++)
956 for (int y = bounds[1]; y <= bounds[3]; y++)
957 if (board_atxy(b, x, y) != S_NONE) {
958 //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));
959 return true;
961 return false;