More notes on the possible min/max method.
[pachi/pachi-r6144.git] / board.c
blob6d7e048a4f6e46446f3b418fe8b3a52d619fe492
1 #include <alloca.h>
2 #include <assert.h>
3 #include <math.h>
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <string.h>
8 //#define DEBUG
9 #include "board.h"
10 #include "debug.h"
11 #include "fbook.h"
12 #include "mq.h"
13 #include "random.h"
15 #ifdef BOARD_PAT3
16 #include "pattern3.h"
17 #endif
18 #ifdef BOARD_TRAITS
19 static void board_trait_recompute(struct board *board, coord_t coord);
20 #include "tactics/selfatari.h"
21 #endif
24 #if 0
25 #define profiling_noinline __attribute__((noinline))
26 #else
27 #define profiling_noinline
28 #endif
30 #define gi_granularity 4
31 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
34 static void
35 board_setup(struct board *b)
37 memset(b, 0, sizeof(*b));
39 struct move m = { pass, S_NONE };
40 b->last_move = b->last_move2 = b->last_move3 = b->last_move4 = b->last_ko = b->ko = m;
43 struct board *
44 board_init(char *fbookfile)
46 struct board *b = malloc2(sizeof(struct board));
47 board_setup(b);
49 b->fbookfile = fbookfile;
51 // Default setup
52 b->size = 9 + 2;
53 board_clear(b);
55 return b;
58 static size_t
59 board_alloc(struct board *board)
61 /* We do not allocate the board structure itself but we allocate
62 * all the arrays with board contents. */
64 int bsize = board_size2(board) * sizeof(*board->b);
65 int gsize = board_size2(board) * sizeof(*board->g);
66 int fsize = board_size2(board) * sizeof(*board->f);
67 int nsize = board_size2(board) * sizeof(*board->n);
68 int psize = board_size2(board) * sizeof(*board->p);
69 int hsize = board_size2(board) * 2 * sizeof(*board->h);
70 int gisize = board_size2(board) * sizeof(*board->gi);
71 #ifdef WANT_BOARD_C
72 int csize = board_size2(board) * sizeof(*board->c);
73 #else
74 int csize = 0;
75 #endif
76 #ifdef BOARD_PAT3
77 int p3size = board_size2(board) * sizeof(*board->pat3);
78 #else
79 int p3size = 0;
80 #endif
81 #ifdef BOARD_TRAITS
82 int tsize = board_size2(board) * sizeof(*board->t);
83 int tqsize = board_size2(board) * sizeof(*board->t);
84 #else
85 int tsize = 0;
86 int tqsize = 0;
87 #endif
88 int cdsize = board_size2(board) * sizeof(*board->coord);
90 size_t size = bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + p3size + tsize + tqsize + cdsize;
91 void *x = malloc2(size);
93 /* board->b must come first */
94 board->b = x; x += bsize;
95 board->g = x; x += gsize;
96 board->f = x; x += fsize;
97 board->p = x; x += psize;
98 board->n = x; x += nsize;
99 board->h = x; x += hsize;
100 board->gi = x; x += gisize;
101 #ifdef WANT_BOARD_C
102 board->c = x; x += csize;
103 #endif
104 #ifdef BOARD_PAT3
105 board->pat3 = x; x += p3size;
106 #endif
107 #ifdef BOARD_TRAITS
108 board->t = x; x += tsize;
109 board->tq = x; x += tqsize;
110 #endif
111 board->coord = x; x += cdsize;
113 return size;
116 struct board *
117 board_copy(struct board *b2, struct board *b1)
119 memcpy(b2, b1, sizeof(struct board));
121 size_t size = board_alloc(b2);
122 memcpy(b2->b, b1->b, size);
124 // XXX: Special semantics.
125 b2->fbook = NULL;
127 return b2;
130 void
131 board_done_noalloc(struct board *board)
133 if (board->b) free(board->b);
134 if (board->fbook) fbook_done(board->fbook);
137 void
138 board_done(struct board *board)
140 board_done_noalloc(board);
141 free(board);
144 void
145 board_resize(struct board *board, int size)
147 #ifdef BOARD_SIZE
148 assert(board_size(board) == size + 2);
149 #endif
150 assert(size <= BOARD_MAX_SIZE);
151 board->size = size + 2 /* S_OFFBOARD margin */;
152 board->size2 = board_size(board) * board_size(board);
154 board->bits2 = 1;
155 while ((1 << board->bits2) < board->size2) board->bits2++;
157 if (board->b)
158 free(board->b);
160 size_t asize = board_alloc(board);
161 memset(board->b, 0, asize);
164 static void
165 board_init_data(struct board *board)
167 int size = board_size(board);
169 board_setup(board);
170 board_resize(board, size - 2 /* S_OFFBOARD margin */);
172 /* Setup neighborhood iterators */
173 board->nei8[0] = -size - 1; // (-1,-1)
174 board->nei8[1] = 1;
175 board->nei8[2] = 1;
176 board->nei8[3] = size - 2; // (-1,0)
177 board->nei8[4] = 2;
178 board->nei8[5] = size - 2; // (-1,1)
179 board->nei8[6] = 1;
180 board->nei8[7] = 1;
181 board->dnei[0] = -size - 1;
182 board->dnei[1] = 2;
183 board->dnei[2] = size*2 - 2;
184 board->dnei[3] = 2;
186 /* Setup initial symmetry */
187 board->symmetry.d = 1;
188 board->symmetry.x1 = board->symmetry.y1 = board_size(board) / 2;
189 board->symmetry.x2 = board->symmetry.y2 = board_size(board) - 1;
190 board->symmetry.type = SYM_FULL;
192 /* Set up coordinate cache */
193 foreach_point(board) {
194 board->coord[c][0] = c % board_size(board);
195 board->coord[c][1] = c / board_size(board);
196 } foreach_point_end;
198 /* Draw the offboard margin */
199 int top_row = board_size2(board) - board_size(board);
200 int i;
201 for (i = 0; i < board_size(board); i++)
202 board->b[i] = board->b[top_row + i] = S_OFFBOARD;
203 for (i = 0; i <= top_row; i += board_size(board))
204 board->b[i] = board->b[board_size(board) - 1 + i] = S_OFFBOARD;
206 foreach_point(board) {
207 coord_t coord = c;
208 if (board_at(board, coord) == S_OFFBOARD)
209 continue;
210 foreach_neighbor(board, c, {
211 inc_neighbor_count_at(board, coord, board_at(board, c));
212 } );
213 } foreach_point_end;
215 /* All positions are free! Except the margin. */
216 for (i = board_size(board); i < (board_size(board) - 1) * board_size(board); i++)
217 if (i % board_size(board) != 0 && i % board_size(board) != board_size(board) - 1)
218 board->f[board->flen++] = i;
220 /* Initialize zobrist hashtable. */
221 /* We will need these to be stable across Pachi runs for
222 * certain kinds of pattern matching, thus we do not use
223 * fast_random() for this. */
224 hash_t hseed = 0x3121110101112131;
225 foreach_point(board) {
226 board->h[c * 2] = (hseed *= 16807);
227 if (!board->h[c * 2])
228 board->h[c * 2] = 1;
229 /* And once again for white */
230 board->h[c * 2 + 1] = (hseed *= 16807);
231 if (!board->h[c * 2 + 1])
232 board->h[c * 2 + 1] = 1;
233 } foreach_point_end;
235 #ifdef BOARD_PAT3
236 /* Initialize 3x3 pattern codes. */
237 foreach_point(board) {
238 if (board_at(board, c) == S_NONE)
239 board->pat3[c] = pattern3_hash(board, c);
240 } foreach_point_end;
241 #endif
242 #ifdef BOARD_TRAITS
243 /* Initialize traits. */
244 foreach_point(board) {
245 trait_at(board, c, S_BLACK).cap = 0;
246 trait_at(board, c, S_BLACK).cap1 = 0;
247 trait_at(board, c, S_BLACK).safe = true;
248 trait_at(board, c, S_WHITE).cap = 0;
249 trait_at(board, c, S_WHITE).cap1 = 0;
250 trait_at(board, c, S_WHITE).safe = true;
251 } foreach_point_end;
252 #endif
255 void
256 board_clear(struct board *board)
258 int size = board_size(board);
259 floating_t komi = board->komi;
260 char *fbookfile = board->fbookfile;
262 board_done_noalloc(board);
264 static struct board bcache[BOARD_MAX_SIZE + 2];
265 assert(size > 0 && size <= BOARD_MAX_SIZE + 2);
266 if (bcache[size - 1].size == size) {
267 board_copy(board, &bcache[size - 1]);
268 } else {
269 board_init_data(board);
270 board_copy(&bcache[size - 1], board);
273 board->komi = komi;
274 board->fbookfile = fbookfile;
276 if (board->fbookfile) {
277 board->fbook = fbook_init(board->fbookfile, board);
281 static char *
282 board_print_top(struct board *board, char *s, char *end, int c)
284 for (int i = 0; i < c; i++) {
285 char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
286 s += snprintf(s, end - s, " ");
287 for (int x = 1; x < board_size(board) - 1; x++)
288 s += snprintf(s, end - s, "%c ", asdf[x - 1]);
289 s += snprintf(s, end -s, " ");
291 s += snprintf(s, end - s, "\n");
292 for (int i = 0; i < c; i++) {
293 s += snprintf(s, end - s, " +-");
294 for (int x = 1; x < board_size(board) - 1; x++)
295 s += snprintf(s, end - s, "--");
296 s += snprintf(s, end - s, "+");
298 s += snprintf(s, end - s, "\n");
299 return s;
302 static char *
303 board_print_bottom(struct board *board, char *s, char *end, int c)
305 for (int i = 0; i < c; i++) {
306 s += snprintf(s, end - s, " +-");
307 for (int x = 1; x < board_size(board) - 1; x++)
308 s += snprintf(s, end - s, "--");
309 s += snprintf(s, end - s, "+");
311 s += snprintf(s, end - s, "\n");
312 return s;
315 static char *
316 board_print_row(struct board *board, int y, char *s, char *end, board_cprint cprint)
318 s += snprintf(s, end - s, " %2d | ", y);
319 for (int x = 1; x < board_size(board) - 1; x++) {
320 if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
321 s += snprintf(s, end - s, "%c)", stone2char(board_atxy(board, x, y)));
322 else
323 s += snprintf(s, end - s, "%c ", stone2char(board_atxy(board, x, y)));
325 s += snprintf(s, end - s, "|");
326 if (cprint) {
327 s += snprintf(s, end - s, " %2d | ", y);
328 for (int x = 1; x < board_size(board) - 1; x++) {
329 s = cprint(board, coord_xy(board, x, y), s, end);
331 s += snprintf(s, end - s, "|");
333 s += snprintf(s, end - s, "\n");
334 return s;
337 void
338 board_print_custom(struct board *board, FILE *f, board_cprint cprint)
340 char buf[10240];
341 char *s = buf;
342 char *end = buf + sizeof(buf);
343 s += snprintf(s, end - s, "Move: % 3d Komi: %2.1f Handicap: %d Captures B: %d W: %d\n",
344 board->moves, board->komi, board->handicap,
345 board->captures[S_BLACK], board->captures[S_WHITE]);
346 s = board_print_top(board, s, end, 1 + !!cprint);
347 for (int y = board_size(board) - 2; y >= 1; y--)
348 s = board_print_row(board, y, s, end, cprint);
349 board_print_bottom(board, s, end, 1 + !!cprint);
350 fprintf(f, "%s\n", buf);
353 static char *
354 cprint_group(struct board *board, coord_t c, char *s, char *end)
356 s += snprintf(s, end - s, "%d ", group_base(group_at(board, c)));
357 return s;
360 void
361 board_print(struct board *board, FILE *f)
363 board_print_custom(board, f, DEBUGL(6) ? cprint_group : NULL);
367 #ifdef BOARD_TRAITS
368 static bool
369 board_trait_safe(struct board *board, coord_t coord, enum stone color)
371 if (board->precise_selfatari)
372 return !is_bad_selfatari(board, color, coord);
373 else
374 return board_safe_to_play(board, coord, color);
377 static void
378 board_trait_recompute(struct board *board, coord_t coord)
380 trait_at(board, coord, S_BLACK).safe = board_trait_safe(board, coord, S_BLACK);;
381 trait_at(board, coord, S_WHITE).safe = board_trait_safe(board, coord, S_WHITE);
382 if (DEBUGL(8)) {
383 fprintf(stderr, "traits[%s:%s lib=%d] (black cap=%d cap1=%d safe=%d) (white cap=%d cap1=%d safe=%d)\n",
384 coord2sstr(coord, board), stone2str(board_at(board, coord)), immediate_liberty_count(board, coord),
385 trait_at(board, coord, S_BLACK).cap, trait_at(board, coord, S_BLACK).cap1, trait_at(board, coord, S_BLACK).safe,
386 trait_at(board, coord, S_WHITE).cap, trait_at(board, coord, S_WHITE).cap1, trait_at(board, coord, S_WHITE).safe);
389 #endif
391 /* Recompute traits for dirty points that we have previously touched
392 * somehow (libs of their neighbors changed or so). */
393 static void
394 board_traits_recompute(struct board *board)
396 #ifdef BOARD_TRAITS
397 for (int i = 0; i < board->tqlen; i++) {
398 coord_t coord = board->tq[i];
399 trait_at(board, coord, S_BLACK).dirty = false;
400 if (board_at(board, coord) != S_NONE)
401 continue;
402 board_trait_recompute(board, coord);
404 board->tqlen = 0;
405 #endif
408 /* Queue traits of given point for recomputing. */
409 static void
410 board_trait_queue(struct board *board, coord_t coord)
412 #ifdef BOARD_TRAITS
413 if (trait_at(board, coord, S_BLACK).dirty)
414 return;
415 board->tq[board->tqlen++] = coord;
416 trait_at(board, coord, S_BLACK).dirty = true;
417 #endif
421 /* Update board hash with given coordinate. */
422 static void profiling_noinline
423 board_hash_update(struct board *board, coord_t coord, enum stone color)
425 board->hash ^= hash_at(board, coord, color);
426 board->qhash[coord_quadrant(coord, board)] ^= hash_at(board, coord, color);
427 if (DEBUGL(8))
428 fprintf(stderr, "board_hash_update(%d,%d,%d) ^ %"PRIhash" -> %"PRIhash"\n", color, coord_x(coord, board), coord_y(coord, board), hash_at(board, coord, color), board->hash);
430 #if defined(BOARD_PAT3)
431 /* @color is not what we need in case of capture. */
432 static const int ataribits[8] = { -1, 0, -1, 1, 2, -1, 3, -1 };
433 enum stone new_color = board_at(board, coord);
434 bool in_atari = false;
435 if (new_color == S_NONE) {
436 board->pat3[coord] = pattern3_hash(board, coord);
437 } else {
438 in_atari = (board_group_info(board, group_at(board, coord)).libs == 1);
440 foreach_8neighbor(board, coord) {
441 /* Internally, the loop uses fn__i=[0..7]. We can use
442 * it directly to address bits within the bitmap of the
443 * neighbors since the bitmap order is reverse to the
444 * loop order. */
445 if (board_at(board, c) != S_NONE)
446 continue;
447 board->pat3[c] &= ~(3 << (fn__i*2));
448 board->pat3[c] |= new_color << (fn__i*2);
449 if (ataribits[fn__i] >= 0) {
450 board->pat3[c] &= ~(1 << (16 + ataribits[fn__i]));
451 board->pat3[c] |= in_atari << (16 + ataribits[fn__i]);
453 #if defined(BOARD_TRAITS)
454 board_trait_queue(board, c);
455 #endif
456 } foreach_8neighbor_end;
457 #endif
460 /* Commit current board hash to history. */
461 static void profiling_noinline
462 board_hash_commit(struct board *board)
464 if (DEBUGL(8))
465 fprintf(stderr, "board_hash_commit %"PRIhash"\n", board->hash);
466 if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
467 board->history_hash[board->hash & history_hash_mask] = board->hash;
468 } else {
469 hash_t i = board->hash;
470 while (board->history_hash[i & history_hash_mask]) {
471 if (board->history_hash[i & history_hash_mask] == board->hash) {
472 if (DEBUGL(5))
473 fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
474 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
475 board->superko_violation = true;
476 return;
478 i = history_hash_next(i);
480 board->history_hash[i & history_hash_mask] = board->hash;
485 void
486 board_symmetry_update(struct board *b, struct board_symmetry *symmetry, coord_t c)
488 if (likely(symmetry->type == SYM_NONE)) {
489 /* Fully degenerated already. We do not support detection
490 * of restoring of symmetry, assuming that this is too rare
491 * a case to handle. */
492 return;
495 int x = coord_x(c, b), y = coord_y(c, b), t = board_size(b) / 2;
496 int dx = board_size(b) - 1 - x; /* for SYM_DOWN */
497 if (DEBUGL(6)) {
498 fprintf(stderr, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
499 symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
500 symmetry->d, symmetry->type, x, y);
503 switch (symmetry->type) {
504 case SYM_FULL:
505 if (x == t && y == t) {
506 /* Tengen keeps full symmetry. */
507 return;
509 /* New symmetry now? */
510 if (x == y) {
511 symmetry->type = SYM_DIAG_UP;
512 symmetry->x1 = symmetry->y1 = 1;
513 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
514 symmetry->d = 1;
515 } else if (dx == y) {
516 symmetry->type = SYM_DIAG_DOWN;
517 symmetry->x1 = symmetry->y1 = 1;
518 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
519 symmetry->d = 1;
520 } else if (x == t) {
521 symmetry->type = SYM_HORIZ;
522 symmetry->y1 = 1;
523 symmetry->y2 = board_size(b) - 1;
524 symmetry->d = 0;
525 } else if (y == t) {
526 symmetry->type = SYM_VERT;
527 symmetry->x1 = 1;
528 symmetry->x2 = board_size(b) - 1;
529 symmetry->d = 0;
530 } else {
531 break_symmetry:
532 symmetry->type = SYM_NONE;
533 symmetry->x1 = symmetry->y1 = 1;
534 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
535 symmetry->d = 0;
537 break;
538 case SYM_DIAG_UP:
539 if (x == y)
540 return;
541 goto break_symmetry;
542 case SYM_DIAG_DOWN:
543 if (dx == y)
544 return;
545 goto break_symmetry;
546 case SYM_HORIZ:
547 if (x == t)
548 return;
549 goto break_symmetry;
550 case SYM_VERT:
551 if (y == t)
552 return;
553 goto break_symmetry;
554 case SYM_NONE:
555 assert(0);
556 break;
559 if (DEBUGL(6)) {
560 fprintf(stderr, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
561 symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
562 symmetry->d, symmetry->type);
564 /* Whew. */
568 void
569 board_handicap_stone(struct board *board, int x, int y, FILE *f)
571 struct move m;
572 m.color = S_BLACK; m.coord = coord_xy(board, x, y);
574 board_play(board, &m);
575 /* Simulate white passing; otherwise, UCT search can get confused since
576 * tree depth parity won't match the color to move. */
577 board->moves++;
579 char *str = coord2str(m.coord, board);
580 if (DEBUGL(1))
581 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
582 if (f) fprintf(f, "%s ", str);
583 free(str);
586 void
587 board_handicap(struct board *board, int stones, FILE *f)
589 int margin = 3 + (board_size(board) >= 13);
590 int min = margin;
591 int mid = board_size(board) / 2;
592 int max = board_size(board) - 1 - margin;
593 const int places[][2] = {
594 { min, min }, { max, max }, { min, max }, { max, min },
595 { min, mid }, { max, mid },
596 { mid, min }, { mid, max },
597 { mid, mid },
600 board->handicap = stones;
602 if (stones == 5 || stones == 7) {
603 board_handicap_stone(board, mid, mid, f);
604 stones--;
607 int i;
608 for (i = 0; i < stones; i++)
609 board_handicap_stone(board, places[i][0], places[i][1], f);
613 static void __attribute__((noinline))
614 check_libs_consistency(struct board *board, group_t g)
616 #ifdef DEBUG
617 if (!g) return;
618 struct group *gi = &board_group_info(board, g);
619 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
620 if (gi->lib[i] && board_at(board, gi->lib[i]) != S_NONE) {
621 fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(group_base(g), board));
622 assert(0);
624 #endif
627 static void
628 check_pat3_consistency(struct board *board, coord_t coord)
630 #ifdef DEBUG
631 foreach_8neighbor(board, coord) {
632 if (board_at(board, c) == S_NONE && pattern3_hash(board, c) != board->pat3[c]) {
633 board_print(board, stderr);
634 fprintf(stderr, "%s(%d)->%s(%d) computed %x != stored %x (%d)\n", coord2sstr(coord, board), coord, coord2sstr(c, board), c, pattern3_hash(board, c), board->pat3[c], fn__i);
635 assert(0);
637 } foreach_8neighbor_end;
638 #endif
641 static void
642 board_capturable_add(struct board *board, group_t group, coord_t lib, bool onestone)
644 //fprintf(stderr, "group %s cap %s\n", coord2sstr(group, board), coord2sstr(lib, boarD));
645 #ifdef BOARD_TRAITS
646 /* Increase capturable count trait of my last lib. */
647 enum stone capturing_color = stone_other(board_at(board, group));
648 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
649 foreach_neighbor(board, lib, {
650 if (DEBUGL(8) && group_at(board, c) == group)
651 fprintf(stderr, "%s[%d] %s cap bump bc of %s(%d) member %s onestone %d\n", coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap, stone2str(capturing_color), coord2sstr(group, board), board_group_info(board, group).libs, coord2sstr(c, board), onestone);
652 trait_at(board, lib, capturing_color).cap += (group_at(board, c) == group);
653 trait_at(board, lib, capturing_color).cap1 += (group_at(board, c) == group && onestone);
655 board_trait_queue(board, lib);
656 #endif
658 #ifdef BOARD_PAT3
659 int fn__i = 0;
660 foreach_neighbor(board, lib, {
661 board->pat3[lib] |= (group_at(board, c) == group) << (16 + 3 - fn__i);
662 fn__i++;
664 #endif
666 #ifdef WANT_BOARD_C
667 /* Update the list of capturable groups. */
668 assert(group);
669 assert(board->clen < board_size2(board));
670 board->c[board->clen++] = group;
671 #endif
673 static void
674 board_capturable_rm(struct board *board, group_t group, coord_t lib, bool onestone)
676 //fprintf(stderr, "group %s nocap %s\n", coord2sstr(group, board), coord2sstr(lib, board));
677 #ifdef BOARD_TRAITS
678 /* Decrease capturable count trait of my previously-last lib. */
679 enum stone capturing_color = stone_other(board_at(board, group));
680 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
681 foreach_neighbor(board, lib, {
682 if (DEBUGL(8) && group_at(board, c) == group)
683 fprintf(stderr, "%s[%d] cap dump bc of %s(%d) member %s onestone %d\n", coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap, coord2sstr(group, board), board_group_info(board, group).libs, coord2sstr(c, board), onestone);
684 trait_at(board, lib, capturing_color).cap -= (group_at(board, c) == group);
685 trait_at(board, lib, capturing_color).cap1 -= (group_at(board, c) == group && onestone);
687 board_trait_queue(board, lib);
688 #endif
690 #ifdef BOARD_PAT3
691 int fn__i = 0;
692 foreach_neighbor(board, lib, {
693 board->pat3[lib] &= ~((group_at(board, c) == group) << (16 + 3 - fn__i));
694 fn__i++;
696 #endif
698 #ifdef WANT_BOARD_C
699 /* Update the list of capturable groups. */
700 for (int i = 0; i < board->clen; i++) {
701 if (unlikely(board->c[i] == group)) {
702 board->c[i] = board->c[--board->clen];
703 return;
706 fprintf(stderr, "rm of bad group %d\n", group_base(group));
707 assert(0);
708 #endif
711 static void
712 board_atariable_add(struct board *board, group_t group, coord_t lib1, coord_t lib2)
714 #ifdef BOARD_TRAITS
715 board_trait_queue(board, lib1);
716 board_trait_queue(board, lib2);
717 #endif
719 static void
720 board_atariable_rm(struct board *board, group_t group, coord_t lib1, coord_t lib2)
722 #ifdef BOARD_TRAITS
723 board_trait_queue(board, lib1);
724 board_trait_queue(board, lib2);
725 #endif
728 static void
729 board_group_addlib(struct board *board, group_t group, coord_t coord)
731 if (DEBUGL(7)) {
732 fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n",
733 group_base(group), coord2sstr(group_base(group), board),
734 board_group_info(board, group).libs, coord2sstr(coord, board));
737 check_libs_consistency(board, group);
739 struct group *gi = &board_group_info(board, group);
740 bool onestone = group_is_onestone(board, group);
741 if (gi->libs < GROUP_KEEP_LIBS) {
742 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
743 #if 0
744 /* Seems extra branch just slows it down */
745 if (!gi->lib[i])
746 break;
747 #endif
748 if (unlikely(gi->lib[i] == coord))
749 return;
751 if (gi->libs == 0) {
752 board_capturable_add(board, group, coord, onestone);
753 } else if (gi->libs == 1) {
754 board_capturable_rm(board, group, gi->lib[0], onestone);
755 board_atariable_add(board, group, gi->lib[0], coord);
756 } else if (gi->libs == 2) {
757 board_atariable_rm(board, group, gi->lib[0], gi->lib[1]);
759 gi->lib[gi->libs++] = coord;
762 check_libs_consistency(board, group);
765 static void
766 board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid)
768 /* Add extra liberty from the board to our liberty list. */
769 unsigned char watermark[board_size2(board) / 8];
770 memset(watermark, 0, sizeof(watermark));
771 #define watermark_get(c) (watermark[c >> 3] & (1 << (c & 7)))
772 #define watermark_set(c) watermark[c >> 3] |= (1 << (c & 7))
774 for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++)
775 watermark_set(gi->lib[i]);
776 watermark_set(avoid);
778 foreach_in_group(board, group) {
779 coord_t coord2 = c;
780 foreach_neighbor(board, coord2, {
781 if (board_at(board, c) + watermark_get(c) != S_NONE)
782 continue;
783 watermark_set(c);
784 gi->lib[gi->libs++] = c;
785 if (unlikely(gi->libs >= GROUP_KEEP_LIBS))
786 return;
787 } );
788 } foreach_in_group_end;
789 #undef watermark_get
790 #undef watermark_set
793 static void
794 board_group_rmlib(struct board *board, group_t group, coord_t coord)
796 if (DEBUGL(7)) {
797 fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n",
798 group_base(group), coord2sstr(group_base(group), board),
799 board_group_info(board, group).libs, coord2sstr(coord, board));
802 struct group *gi = &board_group_info(board, group);
803 bool onestone = group_is_onestone(board, group);
804 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
805 #if 0
806 /* Seems extra branch just slows it down */
807 if (!gi->lib[i])
808 break;
809 #endif
810 if (likely(gi->lib[i] != coord))
811 continue;
813 coord_t lib = gi->lib[i] = gi->lib[--gi->libs];
814 gi->lib[gi->libs] = 0;
816 check_libs_consistency(board, group);
818 /* Postpone refilling lib[] until we need to. */
819 assert(GROUP_REFILL_LIBS > 1);
820 if (gi->libs > GROUP_REFILL_LIBS)
821 return;
822 if (gi->libs == GROUP_REFILL_LIBS)
823 board_group_find_extra_libs(board, group, gi, coord);
825 if (gi->libs == 2) {
826 board_atariable_add(board, group, gi->lib[0], gi->lib[1]);
827 } else if (gi->libs == 1) {
828 board_capturable_add(board, group, gi->lib[0], onestone);
829 board_atariable_rm(board, group, gi->lib[0], lib);
830 } else if (gi->libs == 0)
831 board_capturable_rm(board, group, lib, onestone);
832 return;
835 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
836 * can call this multiple times per coord. */
837 check_libs_consistency(board, group);
838 return;
842 /* This is a low-level routine that doesn't maintain consistency
843 * of all the board data structures. */
844 static void
845 board_remove_stone(struct board *board, group_t group, coord_t c)
847 enum stone color = board_at(board, c);
848 board_at(board, c) = S_NONE;
849 group_at(board, c) = 0;
850 board_hash_update(board, c, color);
851 #ifdef BOARD_TRAITS
852 /* We mark as cannot-capture now. If this is a ko/snapback,
853 * we will get incremented later in board_group_addlib(). */
854 trait_at(board, c, S_BLACK).cap = trait_at(board, c, S_BLACK).cap1 = 0;
855 trait_at(board, c, S_WHITE).cap = trait_at(board, c, S_WHITE).cap1 = 0;
856 board_trait_queue(board, c);
857 #endif
859 /* Increase liberties of surrounding groups */
860 coord_t coord = c;
861 foreach_neighbor(board, coord, {
862 dec_neighbor_count_at(board, c, color);
863 board_trait_queue(board, c);
864 group_t g = group_at(board, c);
865 if (g && g != group)
866 board_group_addlib(board, g, coord);
869 #ifdef BOARD_PAT3
870 /* board_hash_update() might have seen the freed up point as able
871 * to capture another group in atari that only after the loop
872 * above gained enough liberties. Reset pat3 again. */
873 board->pat3[c] = pattern3_hash(board, c);
874 #endif
876 if (DEBUGL(6))
877 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
878 board->f[board->flen++] = c;
881 static int profiling_noinline
882 board_group_capture(struct board *board, group_t group)
884 int stones = 0;
886 foreach_in_group(board, group) {
887 board->captures[stone_other(board_at(board, c))]++;
888 board_remove_stone(board, group, c);
889 stones++;
890 } foreach_in_group_end;
892 struct group *gi = &board_group_info(board, group);
893 assert(gi->libs == 0);
894 memset(gi, 0, sizeof(*gi));
896 return stones;
900 static void profiling_noinline
901 add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord)
903 #ifdef BOARD_TRAITS
904 struct group *gi = &board_group_info(board, group);
905 bool onestone = group_is_onestone(board, group);
907 if (gi->libs == 1) {
908 /* Our group is temporarily in atari; make sure the capturable
909 * counts also correspond to the newly added stone before we
910 * start adding liberties again so bump-dump ops match. */
911 enum stone capturing_color = stone_other(board_at(board, group));
912 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
914 coord_t lib = board_group_info(board, group).lib[0];
915 if (coord_is_adjecent(lib, coord, board)) {
916 if (DEBUGL(8))
917 fprintf(stderr, "add_to_group %s: %s[%d] bump\n", coord2sstr(group, board), coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap);
918 trait_at(board, lib, capturing_color).cap++;
919 /* This is never a 1-stone group, obviously. */
920 board_trait_queue(board, lib);
923 if (onestone) {
924 /* We are not 1-stone group anymore, update the cap1
925 * counter specifically. */
926 foreach_neighbor(board, group, {
927 if (board_at(board, c) != S_NONE) continue;
928 trait_at(board, c, capturing_color).cap1--;
929 board_trait_queue(board, c);
933 #endif
935 group_at(board, coord) = group;
936 groupnext_at(board, coord) = groupnext_at(board, prevstone);
937 groupnext_at(board, prevstone) = coord;
939 foreach_neighbor(board, coord, {
940 if (board_at(board, c) == S_NONE)
941 board_group_addlib(board, group, c);
944 if (DEBUGL(8))
945 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
946 coord_x(prevstone, board), coord_y(prevstone, board),
947 coord_x(coord, board), coord_y(coord, board),
948 groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
949 group_base(group));
952 static void profiling_noinline
953 merge_groups(struct board *board, group_t group_to, group_t group_from)
955 if (DEBUGL(7))
956 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
957 group_base(group_from), group_base(group_to));
958 struct group *gi_from = &board_group_info(board, group_from);
959 struct group *gi_to = &board_group_info(board, group_to);
960 bool onestone_from = group_is_onestone(board, group_from);
961 bool onestone_to = group_is_onestone(board, group_to);
963 /* We do this early before the group info is rewritten. */
964 if (gi_from->libs == 2)
965 board_atariable_rm(board, group_from, gi_from->lib[0], gi_from->lib[1]);
966 else if (gi_from->libs == 1)
967 board_capturable_rm(board, group_from, gi_from->lib[0], onestone_from);
969 if (DEBUGL(7))
970 fprintf(stderr,"---- (froml %d, tol %d)\n", gi_from->libs, gi_to->libs);
972 if (gi_to->libs < GROUP_KEEP_LIBS) {
973 for (int i = 0; i < gi_from->libs; i++) {
974 for (int j = 0; j < gi_to->libs; j++)
975 if (gi_to->lib[j] == gi_from->lib[i])
976 goto next_from_lib;
977 if (gi_to->libs == 0) {
978 board_capturable_add(board, group_to, gi_from->lib[i], onestone_to);
979 } else if (gi_to->libs == 1) {
980 board_capturable_rm(board, group_to, gi_to->lib[0], onestone_to);
981 board_atariable_add(board, group_to, gi_to->lib[0], gi_from->lib[i]);
982 } else if (gi_to->libs == 2) {
983 board_atariable_rm(board, group_to, gi_to->lib[0], gi_to->lib[1]);
985 gi_to->lib[gi_to->libs++] = gi_from->lib[i];
986 if (gi_to->libs >= GROUP_KEEP_LIBS)
987 break;
988 next_from_lib:;
992 if (gi_to->libs == 1) {
993 coord_t lib = board_group_info(board, group_to).lib[0];
994 #ifdef BOARD_TRAITS
995 enum stone capturing_color = stone_other(board_at(board, group_to));
996 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
998 /* Our group is currently in atari; make sure we properly
999 * count in even the neighbors from the other group in the
1000 * capturable counter. */
1001 foreach_neighbor(board, lib, {
1002 if (DEBUGL(8) && group_at(board, c) == group_from)
1003 fprintf(stderr, "%s[%d] cap bump\n", coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap);
1004 trait_at(board, lib, capturing_color).cap += (group_at(board, c) == group_from);
1005 /* This is never a 1-stone group, obviously. */
1007 board_trait_queue(board, lib);
1009 if (onestone_to) {
1010 /* We are not 1-stone group anymore, update the cap1
1011 * counter specifically. */
1012 foreach_neighbor(board, group_to, {
1013 if (board_at(board, c) != S_NONE) continue;
1014 trait_at(board, c, capturing_color).cap1--;
1015 board_trait_queue(board, c);
1018 #endif
1019 #ifdef BOARD_PAT3
1020 if (gi_from->libs == 1) {
1021 /* We removed group_from from capturable groups,
1022 * therefore switching the atari flag off.
1023 * We need to set it again since group_to is also
1024 * capturable. */
1025 int fn__i = 0;
1026 foreach_neighbor(board, lib, {
1027 board->pat3[lib] |= (group_at(board, c) == group_from) << (16 + 3 - fn__i);
1028 fn__i++;
1031 #endif
1034 coord_t last_in_group;
1035 foreach_in_group(board, group_from) {
1036 last_in_group = c;
1037 group_at(board, c) = group_to;
1038 } foreach_in_group_end;
1039 groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to));
1040 groupnext_at(board, group_base(group_to)) = group_base(group_from);
1041 memset(gi_from, 0, sizeof(struct group));
1043 if (DEBUGL(7))
1044 fprintf(stderr, "board_play_raw: merged group: %d\n",
1045 group_base(group_to));
1048 static group_t profiling_noinline
1049 new_group(struct board *board, coord_t coord)
1051 group_t group = coord;
1052 struct group *gi = &board_group_info(board, group);
1053 foreach_neighbor(board, coord, {
1054 if (board_at(board, c) == S_NONE)
1055 /* board_group_addlib is ridiculously expensive for us */
1056 #if GROUP_KEEP_LIBS < 4
1057 if (gi->libs < GROUP_KEEP_LIBS)
1058 #endif
1059 gi->lib[gi->libs++] = c;
1062 group_at(board, coord) = group;
1063 groupnext_at(board, coord) = 0;
1065 if (gi->libs == 2)
1066 board_atariable_add(board, group, gi->lib[0], gi->lib[1]);
1067 else if (gi->libs == 1)
1068 board_capturable_add(board, group, gi->lib[0], true);
1069 check_libs_consistency(board, group);
1071 if (DEBUGL(8))
1072 fprintf(stderr, "new_group: added %d,%d to group %d\n",
1073 coord_x(coord, board), coord_y(coord, board),
1074 group_base(group));
1076 return group;
1079 static inline group_t
1080 play_one_neighbor(struct board *board,
1081 coord_t coord, enum stone color, enum stone other_color,
1082 coord_t c, group_t group)
1084 enum stone ncolor = board_at(board, c);
1085 group_t ngroup = group_at(board, c);
1087 inc_neighbor_count_at(board, c, color);
1088 /* We can be S_NONE, in that case we need to update the safety
1089 * trait since we might be left with only one liberty. */
1090 board_trait_queue(board, c);
1092 if (!ngroup)
1093 return group;
1095 board_group_rmlib(board, ngroup, coord);
1096 if (DEBUGL(7))
1097 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
1098 group_base(ngroup), ncolor, color, other_color);
1100 if (ncolor == color && ngroup != group) {
1101 if (!group) {
1102 group = ngroup;
1103 add_to_group(board, group, c, coord);
1104 } else {
1105 merge_groups(board, group, ngroup);
1107 } else if (ncolor == other_color) {
1108 if (DEBUGL(8)) {
1109 struct group *gi = &board_group_info(board, ngroup);
1110 fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board));
1111 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
1112 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
1113 fprintf(stderr, "\n");
1115 if (unlikely(board_group_captured(board, ngroup)))
1116 board_group_capture(board, ngroup);
1118 return group;
1121 /* We played on a place with at least one liberty. We will become a member of
1122 * some group for sure. */
1123 static group_t profiling_noinline
1124 board_play_outside(struct board *board, struct move *m, int f)
1126 coord_t coord = m->coord;
1127 enum stone color = m->color;
1128 enum stone other_color = stone_other(color);
1129 group_t group = 0;
1131 board->f[f] = board->f[--board->flen];
1132 if (DEBUGL(6))
1133 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
1135 #if defined(BOARD_TRAITS) && defined(DEBUG)
1136 /* Sanity check that cap matches reality. */
1138 int a = 0, b = 0;
1139 foreach_neighbor(board, coord, {
1140 group_t g = group_at(board, c);
1141 a += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1);
1142 b += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1) && group_is_onestone(board, g);
1144 assert(a == trait_at(board, coord, color).cap);
1145 assert(b == trait_at(board, coord, color).cap1);
1146 assert(board_trait_safe(board, coord, color) == trait_at(board, coord, color).safe);
1148 #endif
1149 foreach_neighbor(board, coord, {
1150 group = play_one_neighbor(board, coord, color, other_color, c, group);
1153 board_at(board, coord) = color;
1154 if (unlikely(!group))
1155 group = new_group(board, coord);
1157 board->last_move2 = board->last_move;
1158 board->last_move = *m;
1159 board->moves++;
1160 board_hash_update(board, coord, color);
1161 board_symmetry_update(board, &board->symmetry, coord);
1162 struct move ko = { pass, S_NONE };
1163 board->ko = ko;
1165 check_pat3_consistency(board, coord);
1167 return group;
1170 /* We played in an eye-like shape. Either we capture at least one of the eye
1171 * sides in the process of playing, or return -1. */
1172 static int profiling_noinline
1173 board_play_in_eye(struct board *board, struct move *m, int f)
1175 coord_t coord = m->coord;
1176 enum stone color = m->color;
1177 /* Check ko: Capture at a position of ko capture one move ago */
1178 if (unlikely(color == board->ko.color && coord == board->ko.coord)) {
1179 if (DEBUGL(5))
1180 fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
1181 return -1;
1182 } else if (DEBUGL(6)) {
1183 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
1184 color, coord_x(coord, board), coord_y(coord, board),
1185 board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
1188 struct move ko = { pass, S_NONE };
1190 int captured_groups = 0;
1192 foreach_neighbor(board, coord, {
1193 group_t g = group_at(board, c);
1194 if (DEBUGL(7))
1195 fprintf(stderr, "board_check: group %d has %d libs\n",
1196 g, board_group_info(board, g).libs);
1197 captured_groups += (board_group_info(board, g).libs == 1);
1200 if (likely(captured_groups == 0)) {
1201 if (DEBUGL(5)) {
1202 if (DEBUGL(6))
1203 board_print(board, stderr);
1204 fprintf(stderr, "board_check: one-stone suicide\n");
1207 return -1;
1209 #ifdef BOARD_TRAITS
1210 /* We _will_ for sure capture something. */
1211 assert(trait_at(board, coord, color).cap > 0);
1212 assert(trait_at(board, coord, color).safe == board_trait_safe(board, coord, color));
1213 #endif
1215 board->f[f] = board->f[--board->flen];
1216 if (DEBUGL(6))
1217 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
1219 foreach_neighbor(board, coord, {
1220 inc_neighbor_count_at(board, c, color);
1221 /* Originally, this could not have changed any trait
1222 * since no neighbors were S_NONE, however by now some
1223 * of them might be removed from the board. */
1224 board_trait_queue(board, c);
1226 group_t group = group_at(board, c);
1227 if (!group)
1228 continue;
1230 board_group_rmlib(board, group, coord);
1231 if (DEBUGL(7))
1232 fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
1233 group_base(group));
1235 if (board_group_captured(board, group)) {
1236 if (board_group_capture(board, group) == 1) {
1237 /* If we captured multiple groups at once,
1238 * we can't be fighting ko so we don't need
1239 * to check for that. */
1240 ko.color = stone_other(color);
1241 ko.coord = c;
1242 board->last_ko = ko;
1243 board->last_ko_age = board->moves;
1244 if (DEBUGL(5))
1245 fprintf(stderr, "guarding ko at %d,%s\n", ko.color, coord2sstr(ko.coord, board));
1250 board_at(board, coord) = color;
1251 group_t group = new_group(board, coord);
1253 board->last_move2 = board->last_move;
1254 board->last_move = *m;
1255 board->moves++;
1256 board_hash_update(board, coord, color);
1257 board_hash_commit(board);
1258 board_traits_recompute(board);
1259 board_symmetry_update(board, &board->symmetry, coord);
1260 board->ko = ko;
1262 check_pat3_consistency(board, coord);
1264 return !!group;
1267 static int __attribute__((flatten))
1268 board_play_f(struct board *board, struct move *m, int f)
1270 if (DEBUGL(7)) {
1271 fprintf(stderr, "board_play(%s): ---- Playing %d,%d\n", coord2sstr(m->coord, board), coord_x(m->coord, board), coord_y(m->coord, board));
1273 if (likely(!board_is_eyelike(board, m->coord, stone_other(m->color)))) {
1274 /* NOT playing in an eye. Thus this move has to succeed. (This
1275 * is thanks to New Zealand rules. Otherwise, multi-stone
1276 * suicide might fail.) */
1277 group_t group = board_play_outside(board, m, f);
1278 if (unlikely(board_group_captured(board, group))) {
1279 board_group_capture(board, group);
1281 board_hash_commit(board);
1282 board_traits_recompute(board);
1283 return 0;
1284 } else {
1285 return board_play_in_eye(board, m, f);
1290 board_play(struct board *board, struct move *m)
1292 if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
1293 struct move nomove = { pass, S_NONE };
1294 board->ko = nomove;
1295 board->last_move4 = board->last_move3;
1296 board->last_move3 = board->last_move2;
1297 board->last_move2 = board->last_move;
1298 board->last_move = *m;
1299 return 0;
1302 int f;
1303 for (f = 0; f < board->flen; f++)
1304 if (board->f[f] == m->coord)
1305 return board_play_f(board, m, f);
1307 if (DEBUGL(7))
1308 fprintf(stderr, "board_check: stone exists\n");
1309 return -1;
1312 /* Undo, supported only for pass moves. This form of undo is required by KGS
1313 * to settle disputes on dead groups. (Undo of real moves would be more complex
1314 * particularly for capturing moves.) */
1315 int board_undo(struct board *board)
1317 if (!is_pass(board->last_move.coord))
1318 return -1;
1319 board->last_move = board->last_move2;
1320 board->last_move2 = board->last_move3;
1321 board->last_move3 = board->last_move4;
1322 if (board->last_ko_age == board->moves)
1323 board->ko = board->last_ko;
1324 return 0;
1327 static inline bool
1328 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f, ppr_permit permit, void *permit_data)
1330 *coord = b->f[f];
1331 struct move m = { *coord, color };
1332 if (DEBUGL(6))
1333 fprintf(stderr, "trying random move %d: %d,%d %s %d\n", f, coord_x(*coord, b), coord_y(*coord, b), coord2sstr(*coord, b), board_is_valid_move(b, &m));
1334 if (unlikely(board_is_one_point_eye(b, *coord, color)) /* bad idea to play into one, usually */
1335 || !board_is_valid_move(b, &m)
1336 || (permit && !permit(permit_data, b, &m)))
1337 return false;
1338 if (m.coord == *coord) {
1339 return likely(board_play_f(b, &m, f) >= 0);
1340 } else {
1341 *coord = m.coord; // permit modified the coordinate
1342 return likely(board_play(b, &m) >= 0);
1346 void
1347 board_play_random(struct board *b, enum stone color, coord_t *coord, ppr_permit permit, void *permit_data)
1349 if (unlikely(b->flen == 0))
1350 goto pass;
1352 int base = fast_random(b->flen), f;
1353 for (f = base; f < b->flen; f++)
1354 if (board_try_random_move(b, color, coord, f, permit, permit_data))
1355 return;
1356 for (f = 0; f < base; f++)
1357 if (board_try_random_move(b, color, coord, f, permit, permit_data))
1358 return;
1360 pass:
1361 *coord = pass;
1362 struct move m = { pass, color };
1363 board_play(b, &m);
1367 bool
1368 board_is_false_eyelike(struct board *board, coord_t coord, enum stone eye_color)
1370 enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
1372 /* XXX: We attempt false eye detection but we will yield false
1373 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
1375 foreach_diag_neighbor(board, coord) {
1376 color_diag_libs[(enum stone) board_at(board, c)]++;
1377 } foreach_diag_neighbor_end;
1378 /* For false eye, we need two enemy stones diagonally in the
1379 * middle of the board, or just one enemy stone at the edge
1380 * or in the corner. */
1381 color_diag_libs[stone_other(eye_color)] += !!color_diag_libs[S_OFFBOARD];
1382 return color_diag_libs[stone_other(eye_color)] >= 2;
1385 bool
1386 board_is_one_point_eye(struct board *board, coord_t coord, enum stone eye_color)
1388 return board_is_eyelike(board, coord, eye_color)
1389 && !board_is_false_eyelike(board, coord, eye_color);
1392 enum stone
1393 board_get_one_point_eye(struct board *board, coord_t coord)
1395 if (board_is_one_point_eye(board, coord, S_WHITE))
1396 return S_WHITE;
1397 else if (board_is_one_point_eye(board, coord, S_BLACK))
1398 return S_BLACK;
1399 else
1400 return S_NONE;
1404 floating_t
1405 board_fast_score(struct board *board)
1407 int scores[S_MAX];
1408 memset(scores, 0, sizeof(scores));
1410 foreach_point(board) {
1411 enum stone color = board_at(board, c);
1412 if (color == S_NONE)
1413 color = board_get_one_point_eye(board, c);
1414 scores[color]++;
1415 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1416 } foreach_point_end;
1418 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
1421 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1423 /* One flood-fill iteration; returns true if next iteration
1424 * is required. */
1425 static bool
1426 board_tromp_taylor_iter(struct board *board, int *ownermap)
1428 bool needs_update = false;
1429 foreach_free_point(board) {
1430 /* Ignore occupied and already-dame positions. */
1431 assert(board_at(board, c) == S_NONE);
1432 if (ownermap[c] == 3)
1433 continue;
1434 /* Count neighbors. */
1435 int nei[4] = {0};
1436 foreach_neighbor(board, c, {
1437 nei[ownermap[c]]++;
1439 /* If we have neighbors of both colors, or dame,
1440 * we are dame too. */
1441 if ((nei[1] && nei[2]) || nei[3]) {
1442 ownermap[c] = 3;
1443 /* Speed up the propagation. */
1444 foreach_neighbor(board, c, {
1445 if (board_at(board, c) == S_NONE)
1446 ownermap[c] = 3;
1448 needs_update = true;
1449 continue;
1451 /* If we have neighbors of one color, we are owned
1452 * by that color, too. */
1453 if (!ownermap[c] && (nei[1] || nei[2])) {
1454 int newowner = nei[1] ? 1 : 2;
1455 ownermap[c] = newowner;
1456 /* Speed up the propagation. */
1457 foreach_neighbor(board, c, {
1458 if (board_at(board, c) == S_NONE && !ownermap[c])
1459 ownermap[c] = newowner;
1461 needs_update = true;
1462 continue;
1464 } foreach_free_point_end;
1465 return needs_update;
1468 /* Tromp-Taylor Counting */
1469 floating_t
1470 board_official_score(struct board *board, struct move_queue *q)
1473 /* A point P, not colored C, is said to reach C, if there is a path of
1474 * (vertically or horizontally) adjacent points of P's color from P to
1475 * a point of color C.
1477 * A player's score is the number of points of her color, plus the
1478 * number of empty points that reach only her color. */
1480 int ownermap[board_size2(board)];
1481 int s[4] = {0};
1482 const int o[4] = {0, 1, 2, 0};
1483 foreach_point(board) {
1484 ownermap[c] = o[board_at(board, c)];
1485 s[board_at(board, c)]++;
1486 } foreach_point_end;
1488 if (q) {
1489 /* Process dead groups. */
1490 for (unsigned int i = 0; i < q->moves; i++) {
1491 foreach_in_group(board, q->move[i]) {
1492 enum stone color = board_at(board, c);
1493 ownermap[c] = o[stone_other(color)];
1494 s[color]--; s[stone_other(color)]++;
1495 } foreach_in_group_end;
1499 /* We need to special-case empty board. */
1500 if (!s[S_BLACK] && !s[S_WHITE])
1501 return board->komi + board->handicap;
1503 while (board_tromp_taylor_iter(board, ownermap))
1504 /* Flood-fill... */;
1506 int scores[S_MAX];
1507 memset(scores, 0, sizeof(scores));
1509 foreach_point(board) {
1510 assert(board_at(board, c) == S_OFFBOARD || ownermap[c] != 0);
1511 if (ownermap[c] == 3)
1512 continue;
1513 scores[ownermap[c]]++;
1514 } foreach_point_end;
1516 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];