Change default time settings from -t =80000 to -t 15
[pachi/nmclean.git] / board.c
blob96a00eb8d1260ba1820bd9f65f503933cc63ac55
1 #include <assert.h>
2 #include <math.h>
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <string.h>
7 //#define DEBUG
8 #include "board.h"
9 #include "debug.h"
10 #include "fbook.h"
11 #include "mq.h"
12 #include "random.h"
14 #ifdef BOARD_SPATHASH
15 #include "patternsp.h"
16 #endif
17 #ifdef BOARD_PAT3
18 #include "pattern3.h"
19 #endif
20 #ifdef BOARD_TRAITS
21 static void board_trait_recompute(struct board *board, coord_t coord);
22 #include "tactics/selfatari.h"
23 #endif
26 #if 0
27 #define profiling_noinline __attribute__((noinline))
28 #else
29 #define profiling_noinline
30 #endif
32 #define gi_granularity 4
33 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
36 static void
37 board_setup(struct board *b)
39 memset(b, 0, sizeof(*b));
41 struct move m = { pass, S_NONE };
42 b->last_move = b->last_move2 = b->last_move3 = b->last_move4 = b->last_ko = b->ko = m;
45 struct board *
46 board_init(char *fbookfile)
48 struct board *b = malloc2(sizeof(struct board));
49 board_setup(b);
51 b->fbookfile = fbookfile;
53 // Default setup
54 b->size = 9 + 2;
55 board_clear(b);
57 return b;
60 static size_t
61 board_alloc(struct board *board)
63 /* We do not allocate the board structure itself but we allocate
64 * all the arrays with board contents. */
66 int bsize = board_size2(board) * sizeof(*board->b);
67 int gsize = board_size2(board) * sizeof(*board->g);
68 int fsize = board_size2(board) * sizeof(*board->f);
69 int nsize = board_size2(board) * sizeof(*board->n);
70 int psize = board_size2(board) * sizeof(*board->p);
71 int hsize = board_size2(board) * 2 * sizeof(*board->h);
72 int gisize = board_size2(board) * sizeof(*board->gi);
73 #ifdef WANT_BOARD_C
74 int csize = board_size2(board) * sizeof(*board->c);
75 #else
76 int csize = 0;
77 #endif
78 #ifdef BOARD_SPATHASH
79 int ssize = board_size2(board) * sizeof(*board->spathash);
80 #else
81 int ssize = 0;
82 #endif
83 #ifdef BOARD_PAT3
84 int p3size = board_size2(board) * sizeof(*board->pat3);
85 #else
86 int p3size = 0;
87 #endif
88 #ifdef BOARD_TRAITS
89 int tsize = board_size2(board) * sizeof(*board->t);
90 int tqsize = board_size2(board) * sizeof(*board->t);
91 #else
92 int tsize = 0;
93 int tqsize = 0;
94 #endif
95 int cdsize = board_size2(board) * sizeof(*board->coord);
97 size_t size = bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize + tqsize + cdsize;
98 void *x = malloc2(size);
100 /* board->b must come first */
101 board->b = x; x += bsize;
102 board->g = x; x += gsize;
103 board->f = x; x += fsize;
104 board->p = x; x += psize;
105 board->n = x; x += nsize;
106 board->h = x; x += hsize;
107 board->gi = x; x += gisize;
108 #ifdef WANT_BOARD_C
109 board->c = x; x += csize;
110 #endif
111 #ifdef BOARD_SPATHASH
112 board->spathash = x; x += ssize;
113 #endif
114 #ifdef BOARD_PAT3
115 board->pat3 = x; x += p3size;
116 #endif
117 #ifdef BOARD_TRAITS
118 board->t = x; x += tsize;
119 board->tq = x; x += tqsize;
120 #endif
121 board->coord = x; x += cdsize;
123 return size;
126 struct board *
127 board_copy(struct board *b2, struct board *b1)
129 memcpy(b2, b1, sizeof(struct board));
131 size_t size = board_alloc(b2);
132 memcpy(b2->b, b1->b, size);
134 // XXX: Special semantics.
135 b2->fbook = NULL;
137 return b2;
140 void
141 board_done_noalloc(struct board *board)
143 if (board->b) free(board->b);
144 if (board->fbook) fbook_done(board->fbook);
147 void
148 board_done(struct board *board)
150 board_done_noalloc(board);
151 free(board);
154 void
155 board_resize(struct board *board, int size)
157 #ifdef BOARD_SIZE
158 assert(board_size(board) == size + 2);
159 #endif
160 assert(size <= BOARD_MAX_SIZE);
161 board->size = size + 2 /* S_OFFBOARD margin */;
162 board->size2 = board_size(board) * board_size(board);
164 board->bits2 = 1;
165 while ((1 << board->bits2) < board->size2) board->bits2++;
167 if (board->b)
168 free(board->b);
170 size_t asize = board_alloc(board);
171 memset(board->b, 0, asize);
174 static void
175 board_init_data(struct board *board)
177 int size = board_size(board);
179 board_setup(board);
180 board_resize(board, size - 2 /* S_OFFBOARD margin */);
182 /* Setup neighborhood iterators */
183 board->nei8[0] = -size - 1; // (-1,-1)
184 board->nei8[1] = 1;
185 board->nei8[2] = 1;
186 board->nei8[3] = size - 2; // (-1,0)
187 board->nei8[4] = 2;
188 board->nei8[5] = size - 2; // (-1,1)
189 board->nei8[6] = 1;
190 board->nei8[7] = 1;
191 board->dnei[0] = -size - 1;
192 board->dnei[1] = 2;
193 board->dnei[2] = size*2 - 2;
194 board->dnei[3] = 2;
196 /* Setup initial symmetry */
197 if (size % 2) {
198 board->symmetry.d = 1;
199 board->symmetry.x1 = board->symmetry.y1 = board_size(board) / 2;
200 board->symmetry.x2 = board->symmetry.y2 = board_size(board) - 1;
201 board->symmetry.type = SYM_FULL;
202 } else {
203 /* TODO: We do not handle board symmetry on boards
204 * with no tengen yet. */
205 board->symmetry.d = 0;
206 board->symmetry.x1 = board->symmetry.y1 = 1;
207 board->symmetry.x2 = board->symmetry.y2 = board_size(board) - 1;
208 board->symmetry.type = SYM_NONE;
211 /* Set up coordinate cache */
212 foreach_point(board) {
213 board->coord[c][0] = c % board_size(board);
214 board->coord[c][1] = c / board_size(board);
215 } foreach_point_end;
217 /* Draw the offboard margin */
218 int top_row = board_size2(board) - board_size(board);
219 int i;
220 for (i = 0; i < board_size(board); i++)
221 board->b[i] = board->b[top_row + i] = S_OFFBOARD;
222 for (i = 0; i <= top_row; i += board_size(board))
223 board->b[i] = board->b[board_size(board) - 1 + i] = S_OFFBOARD;
225 foreach_point(board) {
226 coord_t coord = c;
227 if (board_at(board, coord) == S_OFFBOARD)
228 continue;
229 foreach_neighbor(board, c, {
230 inc_neighbor_count_at(board, coord, board_at(board, c));
231 } );
232 } foreach_point_end;
234 /* All positions are free! Except the margin. */
235 for (i = board_size(board); i < (board_size(board) - 1) * board_size(board); i++)
236 if (i % board_size(board) != 0 && i % board_size(board) != board_size(board) - 1)
237 board->f[board->flen++] = i;
239 /* Initialize zobrist hashtable. */
240 /* We will need these to be stable across Pachi runs for
241 * certain kinds of pattern matching, thus we do not use
242 * fast_random() for this. */
243 hash_t hseed = 0x3121110101112131;
244 foreach_point(board) {
245 board->h[c * 2] = (hseed *= 16807);
246 if (!board->h[c * 2])
247 board->h[c * 2] = 1;
248 /* And once again for white */
249 board->h[c * 2 + 1] = (hseed *= 16807);
250 if (!board->h[c * 2 + 1])
251 board->h[c * 2 + 1] = 1;
252 } foreach_point_end;
254 #ifdef BOARD_SPATHASH
255 /* Initialize spatial hashes. */
256 foreach_point(board) {
257 for (int d = 1; d <= BOARD_SPATHASH_MAXD; d++) {
258 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
259 ptcoords_at(x, y, c, board, j);
260 board->spathash[coord_xy(board, x, y)][d - 1][0] ^=
261 pthashes[0][j][board_at(board, c)];
262 board->spathash[coord_xy(board, x, y)][d - 1][1] ^=
263 pthashes[0][j][stone_other(board_at(board, c))];
266 } foreach_point_end;
267 #endif
268 #ifdef BOARD_PAT3
269 /* Initialize 3x3 pattern codes. */
270 foreach_point(board) {
271 if (board_at(board, c) == S_NONE)
272 board->pat3[c] = pattern3_hash(board, c);
273 } foreach_point_end;
274 #endif
275 #ifdef BOARD_TRAITS
276 /* Initialize traits. */
277 foreach_point(board) {
278 trait_at(board, c, S_BLACK).cap = 0;
279 trait_at(board, c, S_WHITE).cap = 0;
280 trait_at(board, c, S_BLACK).cap1 = 0;
281 trait_at(board, c, S_WHITE).cap1 = 0;
282 #ifdef BOARD_TRAIT_SAFE
283 trait_at(board, c, S_BLACK).safe = true;
284 trait_at(board, c, S_WHITE).safe = true;
285 #endif
286 } foreach_point_end;
287 #endif
290 void
291 board_clear(struct board *board)
293 int size = board_size(board);
294 floating_t komi = board->komi;
295 char *fbookfile = board->fbookfile;
296 enum go_ruleset rules = board->rules;
298 board_done_noalloc(board);
300 static struct board bcache[BOARD_MAX_SIZE + 2];
301 assert(size > 0 && size <= BOARD_MAX_SIZE + 2);
302 if (bcache[size - 1].size == size) {
303 board_copy(board, &bcache[size - 1]);
304 } else {
305 board_init_data(board);
306 board_copy(&bcache[size - 1], board);
309 board->komi = komi;
310 board->fbookfile = fbookfile;
311 board->rules = rules;
313 if (board->fbookfile) {
314 board->fbook = fbook_init(board->fbookfile, board);
318 static char *
319 board_print_top(struct board *board, char *s, char *end, int c)
321 for (int i = 0; i < c; i++) {
322 char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
323 s += snprintf(s, end - s, " ");
324 for (int x = 1; x < board_size(board) - 1; x++)
325 s += snprintf(s, end - s, "%c ", asdf[x - 1]);
326 s += snprintf(s, end -s, " ");
328 s += snprintf(s, end - s, "\n");
329 for (int i = 0; i < c; i++) {
330 s += snprintf(s, end - s, " +-");
331 for (int x = 1; x < board_size(board) - 1; x++)
332 s += snprintf(s, end - s, "--");
333 s += snprintf(s, end - s, "+");
335 s += snprintf(s, end - s, "\n");
336 return s;
339 static char *
340 board_print_bottom(struct board *board, char *s, char *end, int c)
342 for (int i = 0; i < c; i++) {
343 s += snprintf(s, end - s, " +-");
344 for (int x = 1; x < board_size(board) - 1; x++)
345 s += snprintf(s, end - s, "--");
346 s += snprintf(s, end - s, "+");
348 s += snprintf(s, end - s, "\n");
349 return s;
352 static char *
353 board_print_row(struct board *board, int y, char *s, char *end, board_cprint cprint)
355 s += snprintf(s, end - s, " %2d | ", y);
356 for (int x = 1; x < board_size(board) - 1; x++) {
357 if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
358 s += snprintf(s, end - s, "%c)", stone2char(board_atxy(board, x, y)));
359 else
360 s += snprintf(s, end - s, "%c ", stone2char(board_atxy(board, x, y)));
362 s += snprintf(s, end - s, "|");
363 if (cprint) {
364 s += snprintf(s, end - s, " %2d | ", y);
365 for (int x = 1; x < board_size(board) - 1; x++) {
366 s = cprint(board, coord_xy(board, x, y), s, end);
368 s += snprintf(s, end - s, "|");
370 s += snprintf(s, end - s, "\n");
371 return s;
374 void
375 board_print_custom(struct board *board, FILE *f, board_cprint cprint)
377 char buf[10240];
378 char *s = buf;
379 char *end = buf + sizeof(buf);
380 s += snprintf(s, end - s, "Move: % 3d Komi: %2.1f Handicap: %d Captures B: %d W: %d\n",
381 board->moves, board->komi, board->handicap,
382 board->captures[S_BLACK], board->captures[S_WHITE]);
383 s = board_print_top(board, s, end, 1 + !!cprint);
384 for (int y = board_size(board) - 2; y >= 1; y--)
385 s = board_print_row(board, y, s, end, cprint);
386 board_print_bottom(board, s, end, 1 + !!cprint);
387 fprintf(f, "%s\n", buf);
390 static char *
391 cprint_group(struct board *board, coord_t c, char *s, char *end)
393 s += snprintf(s, end - s, "%d ", group_base(group_at(board, c)));
394 return s;
397 void
398 board_print(struct board *board, FILE *f)
400 board_print_custom(board, f, DEBUGL(6) ? cprint_group : NULL);
404 #ifdef BOARD_TRAITS
406 #if BOARD_TRAIT_SAFE == 1
407 static bool
408 board_trait_safe(struct board *board, coord_t coord, enum stone color)
410 return board_safe_to_play(board, coord, color);
412 #elif BOARD_TRAIT_SAFE == 2
413 static bool
414 board_trait_safe(struct board *board, coord_t coord, enum stone color)
416 return !is_bad_selfatari(board, color, coord);
418 #endif
420 static void
421 board_trait_recompute(struct board *board, coord_t coord)
423 int sfb = -1, sfw = -1;
424 #ifdef BOARD_TRAIT_SAFE
425 sfb = trait_at(board, coord, S_BLACK).safe = board_trait_safe(board, coord, S_BLACK);
426 sfw = trait_at(board, coord, S_WHITE).safe = board_trait_safe(board, coord, S_WHITE);
427 #endif
428 if (DEBUGL(8)) {
429 fprintf(stderr, "traits[%s:%s lib=%d] (black cap=%d cap1=%d safe=%d) (white cap=%d cap1=%d safe=%d)\n",
430 coord2sstr(coord, board), stone2str(board_at(board, coord)), immediate_liberty_count(board, coord),
431 trait_at(board, coord, S_BLACK).cap, trait_at(board, coord, S_BLACK).cap1, sfb,
432 trait_at(board, coord, S_WHITE).cap, trait_at(board, coord, S_WHITE).cap1, sfw);
435 #endif
437 /* Recompute traits for dirty points that we have previously touched
438 * somehow (libs of their neighbors changed or so). */
439 static void
440 board_traits_recompute(struct board *board)
442 #ifdef BOARD_TRAITS
443 for (int i = 0; i < board->tqlen; i++) {
444 coord_t coord = board->tq[i];
445 trait_at(board, coord, S_BLACK).dirty = false;
446 if (board_at(board, coord) != S_NONE)
447 continue;
448 board_trait_recompute(board, coord);
450 board->tqlen = 0;
451 #endif
454 /* Queue traits of given point for recomputing. */
455 static void
456 board_trait_queue(struct board *board, coord_t coord)
458 #ifdef BOARD_TRAITS
459 if (trait_at(board, coord, S_BLACK).dirty)
460 return;
461 board->tq[board->tqlen++] = coord;
462 trait_at(board, coord, S_BLACK).dirty = true;
463 #endif
467 /* Update board hash with given coordinate. */
468 static void profiling_noinline
469 board_hash_update(struct board *board, coord_t coord, enum stone color)
471 board->hash ^= hash_at(board, coord, color);
472 board->qhash[coord_quadrant(coord, board)] ^= hash_at(board, coord, color);
473 if (DEBUGL(8))
474 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);
476 #ifdef BOARD_SPATHASH
477 /* Gridcular metric is reflective, so we update all hashes
478 * of appropriate ditance in OUR circle. */
479 for (int d = 1; d <= BOARD_SPATHASH_MAXD; d++) {
480 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
481 ptcoords_at(x, y, coord, board, j);
482 /* We either changed from S_NONE to color
483 * or vice versa; doesn't matter. */
484 board->spathash[coord_xy(board, x, y)][d - 1][0] ^=
485 pthashes[0][j][color] ^ pthashes[0][j][S_NONE];
486 board->spathash[coord_xy(board, x, y)][d - 1][1] ^=
487 pthashes[0][j][stone_other(color)] ^ pthashes[0][j][S_NONE];
490 #endif
492 #if defined(BOARD_PAT3)
493 /* @color is not what we need in case of capture. */
494 static const int ataribits[8] = { -1, 0, -1, 1, 2, -1, 3, -1 };
495 enum stone new_color = board_at(board, coord);
496 bool in_atari = false;
497 if (new_color == S_NONE) {
498 board->pat3[coord] = pattern3_hash(board, coord);
499 } else {
500 in_atari = (board_group_info(board, group_at(board, coord)).libs == 1);
502 foreach_8neighbor(board, coord) {
503 /* Internally, the loop uses fn__i=[0..7]. We can use
504 * it directly to address bits within the bitmap of the
505 * neighbors since the bitmap order is reverse to the
506 * loop order. */
507 if (board_at(board, c) != S_NONE)
508 continue;
509 board->pat3[c] &= ~(3 << (fn__i*2));
510 board->pat3[c] |= new_color << (fn__i*2);
511 if (ataribits[fn__i] >= 0) {
512 board->pat3[c] &= ~(1 << (16 + ataribits[fn__i]));
513 board->pat3[c] |= in_atari << (16 + ataribits[fn__i]);
515 #if defined(BOARD_TRAITS)
516 board_trait_queue(board, c);
517 #endif
518 } foreach_8neighbor_end;
519 #endif
522 /* Commit current board hash to history. */
523 static void profiling_noinline
524 board_hash_commit(struct board *board)
526 if (DEBUGL(8))
527 fprintf(stderr, "board_hash_commit %"PRIhash"\n", board->hash);
528 if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
529 board->history_hash[board->hash & history_hash_mask] = board->hash;
530 } else {
531 hash_t i = board->hash;
532 while (board->history_hash[i & history_hash_mask]) {
533 if (board->history_hash[i & history_hash_mask] == board->hash) {
534 if (DEBUGL(5))
535 fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
536 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
537 board->superko_violation = true;
538 return;
540 i = history_hash_next(i);
542 board->history_hash[i & history_hash_mask] = board->hash;
547 void
548 board_symmetry_update(struct board *b, struct board_symmetry *symmetry, coord_t c)
550 if (likely(symmetry->type == SYM_NONE)) {
551 /* Fully degenerated already. We do not support detection
552 * of restoring of symmetry, assuming that this is too rare
553 * a case to handle. */
554 return;
557 int x = coord_x(c, b), y = coord_y(c, b), t = board_size(b) / 2;
558 int dx = board_size(b) - 1 - x; /* for SYM_DOWN */
559 if (DEBUGL(6)) {
560 fprintf(stderr, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
561 symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
562 symmetry->d, symmetry->type, x, y);
565 switch (symmetry->type) {
566 case SYM_FULL:
567 if (x == t && y == t) {
568 /* Tengen keeps full symmetry. */
569 return;
571 /* New symmetry now? */
572 if (x == y) {
573 symmetry->type = SYM_DIAG_UP;
574 symmetry->x1 = symmetry->y1 = 1;
575 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
576 symmetry->d = 1;
577 } else if (dx == y) {
578 symmetry->type = SYM_DIAG_DOWN;
579 symmetry->x1 = symmetry->y1 = 1;
580 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
581 symmetry->d = 1;
582 } else if (x == t) {
583 symmetry->type = SYM_HORIZ;
584 symmetry->y1 = 1;
585 symmetry->y2 = board_size(b) - 1;
586 symmetry->d = 0;
587 } else if (y == t) {
588 symmetry->type = SYM_VERT;
589 symmetry->x1 = 1;
590 symmetry->x2 = board_size(b) - 1;
591 symmetry->d = 0;
592 } else {
593 break_symmetry:
594 symmetry->type = SYM_NONE;
595 symmetry->x1 = symmetry->y1 = 1;
596 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
597 symmetry->d = 0;
599 break;
600 case SYM_DIAG_UP:
601 if (x == y)
602 return;
603 goto break_symmetry;
604 case SYM_DIAG_DOWN:
605 if (dx == y)
606 return;
607 goto break_symmetry;
608 case SYM_HORIZ:
609 if (x == t)
610 return;
611 goto break_symmetry;
612 case SYM_VERT:
613 if (y == t)
614 return;
615 goto break_symmetry;
616 case SYM_NONE:
617 assert(0);
618 break;
621 if (DEBUGL(6)) {
622 fprintf(stderr, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
623 symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
624 symmetry->d, symmetry->type);
626 /* Whew. */
630 void
631 board_handicap_stone(struct board *board, int x, int y, FILE *f)
633 struct move m;
634 m.color = S_BLACK; m.coord = coord_xy(board, x, y);
636 board_play(board, &m);
637 /* Simulate white passing; otherwise, UCT search can get confused since
638 * tree depth parity won't match the color to move. */
639 board->moves++;
641 char *str = coord2str(m.coord, board);
642 if (DEBUGL(1))
643 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
644 if (f) fprintf(f, "%s ", str);
645 free(str);
648 void
649 board_handicap(struct board *board, int stones, FILE *f)
651 int margin = 3 + (board_size(board) >= 13);
652 int min = margin;
653 int mid = board_size(board) / 2;
654 int max = board_size(board) - 1 - margin;
655 const int places[][2] = {
656 { min, min }, { max, max }, { min, max }, { max, min },
657 { min, mid }, { max, mid },
658 { mid, min }, { mid, max },
659 { mid, mid },
662 board->handicap = stones;
664 if (stones == 5 || stones == 7) {
665 board_handicap_stone(board, mid, mid, f);
666 stones--;
669 int i;
670 for (i = 0; i < stones; i++)
671 board_handicap_stone(board, places[i][0], places[i][1], f);
675 static void __attribute__((noinline))
676 check_libs_consistency(struct board *board, group_t g)
678 #ifdef DEBUG
679 if (!g) return;
680 struct group *gi = &board_group_info(board, g);
681 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
682 if (gi->lib[i] && board_at(board, gi->lib[i]) != S_NONE) {
683 fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(group_base(g), board));
684 assert(0);
686 #endif
689 static void
690 check_pat3_consistency(struct board *board, coord_t coord)
692 #ifdef DEBUG
693 foreach_8neighbor(board, coord) {
694 if (board_at(board, c) == S_NONE && pattern3_hash(board, c) != board->pat3[c]) {
695 board_print(board, stderr);
696 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);
697 assert(0);
699 } foreach_8neighbor_end;
700 #endif
703 static void
704 board_capturable_add(struct board *board, group_t group, coord_t lib, bool onestone)
706 //fprintf(stderr, "group %s cap %s\n", coord2sstr(group, board), coord2sstr(lib, boarD));
707 #ifdef BOARD_TRAITS
708 /* Increase capturable count trait of my last lib. */
709 enum stone capturing_color = stone_other(board_at(board, group));
710 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
711 foreach_neighbor(board, lib, {
712 if (DEBUGL(8) && group_at(board, c) == group)
713 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);
714 trait_at(board, lib, capturing_color).cap += (group_at(board, c) == group);
715 trait_at(board, lib, capturing_color).cap1 += (group_at(board, c) == group && onestone);
717 board_trait_queue(board, lib);
718 #endif
720 #ifdef BOARD_PAT3
721 int fn__i = 0;
722 foreach_neighbor(board, lib, {
723 board->pat3[lib] |= (group_at(board, c) == group) << (16 + 3 - fn__i);
724 fn__i++;
726 #endif
728 #ifdef WANT_BOARD_C
729 /* Update the list of capturable groups. */
730 assert(group);
731 assert(board->clen < board_size2(board));
732 board->c[board->clen++] = group;
733 #endif
735 static void
736 board_capturable_rm(struct board *board, group_t group, coord_t lib, bool onestone)
738 //fprintf(stderr, "group %s nocap %s\n", coord2sstr(group, board), coord2sstr(lib, board));
739 #ifdef BOARD_TRAITS
740 /* Decrease capturable count trait of my previously-last lib. */
741 enum stone capturing_color = stone_other(board_at(board, group));
742 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
743 foreach_neighbor(board, lib, {
744 if (DEBUGL(8) && group_at(board, c) == group)
745 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);
746 trait_at(board, lib, capturing_color).cap -= (group_at(board, c) == group);
747 trait_at(board, lib, capturing_color).cap1 -= (group_at(board, c) == group && onestone);
749 board_trait_queue(board, lib);
750 #endif
752 #ifdef BOARD_PAT3
753 int fn__i = 0;
754 foreach_neighbor(board, lib, {
755 board->pat3[lib] &= ~((group_at(board, c) == group) << (16 + 3 - fn__i));
756 fn__i++;
758 #endif
760 #ifdef WANT_BOARD_C
761 /* Update the list of capturable groups. */
762 for (int i = 0; i < board->clen; i++) {
763 if (unlikely(board->c[i] == group)) {
764 board->c[i] = board->c[--board->clen];
765 return;
768 fprintf(stderr, "rm of bad group %d\n", group_base(group));
769 assert(0);
770 #endif
773 static void
774 board_atariable_add(struct board *board, group_t group, coord_t lib1, coord_t lib2)
776 #ifdef BOARD_TRAITS
777 board_trait_queue(board, lib1);
778 board_trait_queue(board, lib2);
779 #endif
781 static void
782 board_atariable_rm(struct board *board, group_t group, coord_t lib1, coord_t lib2)
784 #ifdef BOARD_TRAITS
785 board_trait_queue(board, lib1);
786 board_trait_queue(board, lib2);
787 #endif
790 static void
791 board_group_addlib(struct board *board, group_t group, coord_t coord)
793 if (DEBUGL(7)) {
794 fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n",
795 group_base(group), coord2sstr(group_base(group), board),
796 board_group_info(board, group).libs, coord2sstr(coord, board));
799 check_libs_consistency(board, group);
801 struct group *gi = &board_group_info(board, group);
802 bool onestone = group_is_onestone(board, group);
803 if (gi->libs < GROUP_KEEP_LIBS) {
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 (unlikely(gi->lib[i] == coord))
811 return;
813 if (gi->libs == 0) {
814 board_capturable_add(board, group, coord, onestone);
815 } else if (gi->libs == 1) {
816 board_capturable_rm(board, group, gi->lib[0], onestone);
817 board_atariable_add(board, group, gi->lib[0], coord);
818 } else if (gi->libs == 2) {
819 board_atariable_rm(board, group, gi->lib[0], gi->lib[1]);
821 gi->lib[gi->libs++] = coord;
824 check_libs_consistency(board, group);
827 static void
828 board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid)
830 /* Add extra liberty from the board to our liberty list. */
831 unsigned char watermark[board_size2(board) / 8];
832 memset(watermark, 0, sizeof(watermark));
833 #define watermark_get(c) (watermark[c >> 3] & (1 << (c & 7)))
834 #define watermark_set(c) watermark[c >> 3] |= (1 << (c & 7))
836 for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++)
837 watermark_set(gi->lib[i]);
838 watermark_set(avoid);
840 foreach_in_group(board, group) {
841 coord_t coord2 = c;
842 foreach_neighbor(board, coord2, {
843 if (board_at(board, c) + watermark_get(c) != S_NONE)
844 continue;
845 watermark_set(c);
846 gi->lib[gi->libs++] = c;
847 if (unlikely(gi->libs >= GROUP_KEEP_LIBS))
848 return;
849 } );
850 } foreach_in_group_end;
851 #undef watermark_get
852 #undef watermark_set
855 static void
856 board_group_rmlib(struct board *board, group_t group, coord_t coord)
858 if (DEBUGL(7)) {
859 fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n",
860 group_base(group), coord2sstr(group_base(group), board),
861 board_group_info(board, group).libs, coord2sstr(coord, board));
864 struct group *gi = &board_group_info(board, group);
865 bool onestone = group_is_onestone(board, group);
866 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
867 #if 0
868 /* Seems extra branch just slows it down */
869 if (!gi->lib[i])
870 break;
871 #endif
872 if (likely(gi->lib[i] != coord))
873 continue;
875 coord_t lib = gi->lib[i] = gi->lib[--gi->libs];
876 gi->lib[gi->libs] = 0;
878 check_libs_consistency(board, group);
880 /* Postpone refilling lib[] until we need to. */
881 assert(GROUP_REFILL_LIBS > 1);
882 if (gi->libs > GROUP_REFILL_LIBS)
883 return;
884 if (gi->libs == GROUP_REFILL_LIBS)
885 board_group_find_extra_libs(board, group, gi, coord);
887 if (gi->libs == 2) {
888 board_atariable_add(board, group, gi->lib[0], gi->lib[1]);
889 } else if (gi->libs == 1) {
890 board_capturable_add(board, group, gi->lib[0], onestone);
891 board_atariable_rm(board, group, gi->lib[0], lib);
892 } else if (gi->libs == 0)
893 board_capturable_rm(board, group, lib, onestone);
894 return;
897 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
898 * can call this multiple times per coord. */
899 check_libs_consistency(board, group);
900 return;
904 /* This is a low-level routine that doesn't maintain consistency
905 * of all the board data structures. */
906 static void
907 board_remove_stone(struct board *board, group_t group, coord_t c)
909 enum stone color = board_at(board, c);
910 board_at(board, c) = S_NONE;
911 group_at(board, c) = 0;
912 board_hash_update(board, c, color);
913 #ifdef BOARD_TRAITS
914 /* We mark as cannot-capture now. If this is a ko/snapback,
915 * we will get incremented later in board_group_addlib(). */
916 trait_at(board, c, S_BLACK).cap = trait_at(board, c, S_BLACK).cap1 = 0;
917 trait_at(board, c, S_WHITE).cap = trait_at(board, c, S_WHITE).cap1 = 0;
918 board_trait_queue(board, c);
919 #endif
921 /* Increase liberties of surrounding groups */
922 coord_t coord = c;
923 foreach_neighbor(board, coord, {
924 dec_neighbor_count_at(board, c, color);
925 board_trait_queue(board, c);
926 group_t g = group_at(board, c);
927 if (g && g != group)
928 board_group_addlib(board, g, coord);
931 #ifdef BOARD_PAT3
932 /* board_hash_update() might have seen the freed up point as able
933 * to capture another group in atari that only after the loop
934 * above gained enough liberties. Reset pat3 again. */
935 board->pat3[c] = pattern3_hash(board, c);
936 #endif
938 if (DEBUGL(6))
939 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
940 board->f[board->flen++] = c;
943 static int profiling_noinline
944 board_group_capture(struct board *board, group_t group)
946 int stones = 0;
948 foreach_in_group(board, group) {
949 board->captures[stone_other(board_at(board, c))]++;
950 board_remove_stone(board, group, c);
951 stones++;
952 } foreach_in_group_end;
954 struct group *gi = &board_group_info(board, group);
955 assert(gi->libs == 0);
956 memset(gi, 0, sizeof(*gi));
958 return stones;
962 static void profiling_noinline
963 add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord)
965 #ifdef BOARD_TRAITS
966 struct group *gi = &board_group_info(board, group);
967 bool onestone = group_is_onestone(board, group);
969 if (gi->libs == 1) {
970 /* Our group is temporarily in atari; make sure the capturable
971 * counts also correspond to the newly added stone before we
972 * start adding liberties again so bump-dump ops match. */
973 enum stone capturing_color = stone_other(board_at(board, group));
974 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
976 coord_t lib = board_group_info(board, group).lib[0];
977 if (coord_is_adjecent(lib, coord, board)) {
978 if (DEBUGL(8))
979 fprintf(stderr, "add_to_group %s: %s[%d] bump\n", coord2sstr(group, board), coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap);
980 trait_at(board, lib, capturing_color).cap++;
981 /* This is never a 1-stone group, obviously. */
982 board_trait_queue(board, lib);
985 if (onestone) {
986 /* We are not 1-stone group anymore, update the cap1
987 * counter specifically. */
988 foreach_neighbor(board, group, {
989 if (board_at(board, c) != S_NONE) continue;
990 trait_at(board, c, capturing_color).cap1--;
991 board_trait_queue(board, c);
995 #endif
997 group_at(board, coord) = group;
998 groupnext_at(board, coord) = groupnext_at(board, prevstone);
999 groupnext_at(board, prevstone) = coord;
1001 foreach_neighbor(board, coord, {
1002 if (board_at(board, c) == S_NONE)
1003 board_group_addlib(board, group, c);
1006 if (DEBUGL(8))
1007 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
1008 coord_x(prevstone, board), coord_y(prevstone, board),
1009 coord_x(coord, board), coord_y(coord, board),
1010 groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
1011 group_base(group));
1014 static void profiling_noinline
1015 merge_groups(struct board *board, group_t group_to, group_t group_from)
1017 if (DEBUGL(7))
1018 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
1019 group_base(group_from), group_base(group_to));
1020 struct group *gi_from = &board_group_info(board, group_from);
1021 struct group *gi_to = &board_group_info(board, group_to);
1022 bool onestone_from = group_is_onestone(board, group_from);
1023 bool onestone_to = group_is_onestone(board, group_to);
1025 /* We do this early before the group info is rewritten. */
1026 if (gi_from->libs == 2)
1027 board_atariable_rm(board, group_from, gi_from->lib[0], gi_from->lib[1]);
1028 else if (gi_from->libs == 1)
1029 board_capturable_rm(board, group_from, gi_from->lib[0], onestone_from);
1031 if (DEBUGL(7))
1032 fprintf(stderr,"---- (froml %d, tol %d)\n", gi_from->libs, gi_to->libs);
1034 if (gi_to->libs < GROUP_KEEP_LIBS) {
1035 for (int i = 0; i < gi_from->libs; i++) {
1036 for (int j = 0; j < gi_to->libs; j++)
1037 if (gi_to->lib[j] == gi_from->lib[i])
1038 goto next_from_lib;
1039 if (gi_to->libs == 0) {
1040 board_capturable_add(board, group_to, gi_from->lib[i], onestone_to);
1041 } else if (gi_to->libs == 1) {
1042 board_capturable_rm(board, group_to, gi_to->lib[0], onestone_to);
1043 board_atariable_add(board, group_to, gi_to->lib[0], gi_from->lib[i]);
1044 } else if (gi_to->libs == 2) {
1045 board_atariable_rm(board, group_to, gi_to->lib[0], gi_to->lib[1]);
1047 gi_to->lib[gi_to->libs++] = gi_from->lib[i];
1048 if (gi_to->libs >= GROUP_KEEP_LIBS)
1049 break;
1050 next_from_lib:;
1054 if (gi_to->libs == 1) {
1055 coord_t lib = board_group_info(board, group_to).lib[0];
1056 #ifdef BOARD_TRAITS
1057 enum stone capturing_color = stone_other(board_at(board, group_to));
1058 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
1060 /* Our group is currently in atari; make sure we properly
1061 * count in even the neighbors from the other group in the
1062 * capturable counter. */
1063 foreach_neighbor(board, lib, {
1064 if (DEBUGL(8) && group_at(board, c) == group_from)
1065 fprintf(stderr, "%s[%d] cap bump\n", coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap);
1066 trait_at(board, lib, capturing_color).cap += (group_at(board, c) == group_from);
1067 /* This is never a 1-stone group, obviously. */
1069 board_trait_queue(board, lib);
1071 if (onestone_to) {
1072 /* We are not 1-stone group anymore, update the cap1
1073 * counter specifically. */
1074 foreach_neighbor(board, group_to, {
1075 if (board_at(board, c) != S_NONE) continue;
1076 trait_at(board, c, capturing_color).cap1--;
1077 board_trait_queue(board, c);
1080 #endif
1081 #ifdef BOARD_PAT3
1082 if (gi_from->libs == 1) {
1083 /* We removed group_from from capturable groups,
1084 * therefore switching the atari flag off.
1085 * We need to set it again since group_to is also
1086 * capturable. */
1087 int fn__i = 0;
1088 foreach_neighbor(board, lib, {
1089 board->pat3[lib] |= (group_at(board, c) == group_from) << (16 + 3 - fn__i);
1090 fn__i++;
1093 #endif
1096 coord_t last_in_group;
1097 foreach_in_group(board, group_from) {
1098 last_in_group = c;
1099 group_at(board, c) = group_to;
1100 } foreach_in_group_end;
1101 groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to));
1102 groupnext_at(board, group_base(group_to)) = group_base(group_from);
1103 memset(gi_from, 0, sizeof(struct group));
1105 if (DEBUGL(7))
1106 fprintf(stderr, "board_play_raw: merged group: %d\n",
1107 group_base(group_to));
1110 static group_t profiling_noinline
1111 new_group(struct board *board, coord_t coord)
1113 group_t group = coord;
1114 struct group *gi = &board_group_info(board, group);
1115 foreach_neighbor(board, coord, {
1116 if (board_at(board, c) == S_NONE)
1117 /* board_group_addlib is ridiculously expensive for us */
1118 #if GROUP_KEEP_LIBS < 4
1119 if (gi->libs < GROUP_KEEP_LIBS)
1120 #endif
1121 gi->lib[gi->libs++] = c;
1124 group_at(board, coord) = group;
1125 groupnext_at(board, coord) = 0;
1127 if (gi->libs == 2)
1128 board_atariable_add(board, group, gi->lib[0], gi->lib[1]);
1129 else if (gi->libs == 1)
1130 board_capturable_add(board, group, gi->lib[0], true);
1131 check_libs_consistency(board, group);
1133 if (DEBUGL(8))
1134 fprintf(stderr, "new_group: added %d,%d to group %d\n",
1135 coord_x(coord, board), coord_y(coord, board),
1136 group_base(group));
1138 return group;
1141 static inline group_t
1142 play_one_neighbor(struct board *board,
1143 coord_t coord, enum stone color, enum stone other_color,
1144 coord_t c, group_t group)
1146 enum stone ncolor = board_at(board, c);
1147 group_t ngroup = group_at(board, c);
1149 inc_neighbor_count_at(board, c, color);
1150 /* We can be S_NONE, in that case we need to update the safety
1151 * trait since we might be left with only one liberty. */
1152 board_trait_queue(board, c);
1154 if (!ngroup)
1155 return group;
1157 board_group_rmlib(board, ngroup, coord);
1158 if (DEBUGL(7))
1159 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
1160 group_base(ngroup), ncolor, color, other_color);
1162 if (ncolor == color && ngroup != group) {
1163 if (!group) {
1164 group = ngroup;
1165 add_to_group(board, group, c, coord);
1166 } else {
1167 merge_groups(board, group, ngroup);
1169 } else if (ncolor == other_color) {
1170 if (DEBUGL(8)) {
1171 struct group *gi = &board_group_info(board, ngroup);
1172 fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board));
1173 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
1174 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
1175 fprintf(stderr, "\n");
1177 if (unlikely(board_group_captured(board, ngroup)))
1178 board_group_capture(board, ngroup);
1180 return group;
1183 /* We played on a place with at least one liberty. We will become a member of
1184 * some group for sure. */
1185 static group_t profiling_noinline
1186 board_play_outside(struct board *board, struct move *m, int f)
1188 coord_t coord = m->coord;
1189 enum stone color = m->color;
1190 enum stone other_color = stone_other(color);
1191 group_t group = 0;
1193 board->f[f] = board->f[--board->flen];
1194 if (DEBUGL(6))
1195 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
1197 #if defined(BOARD_TRAITS) && defined(DEBUG)
1198 /* Sanity check that cap matches reality. */
1200 int a = 0, b = 0;
1201 foreach_neighbor(board, coord, {
1202 group_t g = group_at(board, c);
1203 a += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1);
1204 b += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1) && group_is_onestone(board, g);
1206 assert(a == trait_at(board, coord, color).cap);
1207 assert(b == trait_at(board, coord, color).cap1);
1208 #ifdef BOARD_TRAIT_SAFE
1209 assert(board_trait_safe(board, coord, color) == trait_at(board, coord, color).safe);
1210 #endif
1212 #endif
1213 foreach_neighbor(board, coord, {
1214 group = play_one_neighbor(board, coord, color, other_color, c, group);
1217 board_at(board, coord) = color;
1218 if (unlikely(!group))
1219 group = new_group(board, coord);
1221 board->last_move2 = board->last_move;
1222 board->last_move = *m;
1223 board->moves++;
1224 board_hash_update(board, coord, color);
1225 board_symmetry_update(board, &board->symmetry, coord);
1226 struct move ko = { pass, S_NONE };
1227 board->ko = ko;
1229 check_pat3_consistency(board, coord);
1231 return group;
1234 /* We played in an eye-like shape. Either we capture at least one of the eye
1235 * sides in the process of playing, or return -1. */
1236 static int profiling_noinline
1237 board_play_in_eye(struct board *board, struct move *m, int f)
1239 coord_t coord = m->coord;
1240 enum stone color = m->color;
1241 /* Check ko: Capture at a position of ko capture one move ago */
1242 if (unlikely(color == board->ko.color && coord == board->ko.coord)) {
1243 if (DEBUGL(5))
1244 fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
1245 return -1;
1246 } else if (DEBUGL(6)) {
1247 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
1248 color, coord_x(coord, board), coord_y(coord, board),
1249 board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
1252 struct move ko = { pass, S_NONE };
1254 int captured_groups = 0;
1256 foreach_neighbor(board, coord, {
1257 group_t g = group_at(board, c);
1258 if (DEBUGL(7))
1259 fprintf(stderr, "board_check: group %d has %d libs\n",
1260 g, board_group_info(board, g).libs);
1261 captured_groups += (board_group_info(board, g).libs == 1);
1264 if (likely(captured_groups == 0)) {
1265 if (DEBUGL(5)) {
1266 if (DEBUGL(6))
1267 board_print(board, stderr);
1268 fprintf(stderr, "board_check: one-stone suicide\n");
1271 return -1;
1273 #ifdef BOARD_TRAITS
1274 /* We _will_ for sure capture something. */
1275 assert(trait_at(board, coord, color).cap > 0);
1276 #ifdef BOARD_TRAIT_SAFE
1277 assert(trait_at(board, coord, color).safe == board_trait_safe(board, coord, color));
1278 #endif
1279 #endif
1281 board->f[f] = board->f[--board->flen];
1282 if (DEBUGL(6))
1283 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
1285 int ko_caps = 0;
1286 coord_t cap_at = pass;
1287 foreach_neighbor(board, coord, {
1288 inc_neighbor_count_at(board, c, color);
1289 /* Originally, this could not have changed any trait
1290 * since no neighbors were S_NONE, however by now some
1291 * of them might be removed from the board. */
1292 board_trait_queue(board, c);
1294 group_t group = group_at(board, c);
1295 if (!group)
1296 continue;
1298 board_group_rmlib(board, group, coord);
1299 if (DEBUGL(7))
1300 fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
1301 group_base(group));
1303 if (board_group_captured(board, group)) {
1304 ko_caps += board_group_capture(board, group);
1305 cap_at = c;
1308 if (ko_caps == 1) {
1309 ko.color = stone_other(color);
1310 ko.coord = cap_at; // unique
1311 board->last_ko = ko;
1312 board->last_ko_age = board->moves;
1313 if (DEBUGL(5))
1314 fprintf(stderr, "guarding ko at %d,%s\n", ko.color, coord2sstr(ko.coord, board));
1317 board_at(board, coord) = color;
1318 group_t group = new_group(board, coord);
1320 board->last_move2 = board->last_move;
1321 board->last_move = *m;
1322 board->moves++;
1323 board_hash_update(board, coord, color);
1324 board_hash_commit(board);
1325 board_traits_recompute(board);
1326 board_symmetry_update(board, &board->symmetry, coord);
1327 board->ko = ko;
1329 check_pat3_consistency(board, coord);
1331 return !!group;
1334 static int __attribute__((flatten))
1335 board_play_f(struct board *board, struct move *m, int f)
1337 if (DEBUGL(7)) {
1338 fprintf(stderr, "board_play(%s): ---- Playing %d,%d\n", coord2sstr(m->coord, board), coord_x(m->coord, board), coord_y(m->coord, board));
1340 if (likely(!board_is_eyelike(board, m->coord, stone_other(m->color)))) {
1341 /* NOT playing in an eye. Thus this move has to succeed. (This
1342 * is thanks to New Zealand rules. Otherwise, multi-stone
1343 * suicide might fail.) */
1344 group_t group = board_play_outside(board, m, f);
1345 if (unlikely(board_group_captured(board, group))) {
1346 board_group_capture(board, group);
1348 board_hash_commit(board);
1349 board_traits_recompute(board);
1350 return 0;
1351 } else {
1352 return board_play_in_eye(board, m, f);
1357 board_play(struct board *board, struct move *m)
1359 if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
1360 if (is_pass(m->coord) && board->rules == RULES_SIMING) {
1361 /* On pass, the player gives a pass stone
1362 * to the opponent. */
1363 board->captures[stone_other(m->color)]++;
1365 struct move nomove = { pass, S_NONE };
1366 board->ko = nomove;
1367 board->last_move4 = board->last_move3;
1368 board->last_move3 = board->last_move2;
1369 board->last_move2 = board->last_move;
1370 board->last_move = *m;
1371 return 0;
1374 int f;
1375 for (f = 0; f < board->flen; f++)
1376 if (board->f[f] == m->coord)
1377 return board_play_f(board, m, f);
1379 if (DEBUGL(7))
1380 fprintf(stderr, "board_check: stone exists\n");
1381 return -1;
1384 /* Undo, supported only for pass moves. This form of undo is required by KGS
1385 * to settle disputes on dead groups. (Undo of real moves would be more complex
1386 * particularly for capturing moves.) */
1387 int board_undo(struct board *board)
1389 if (!is_pass(board->last_move.coord))
1390 return -1;
1391 if (board->rules == RULES_SIMING) {
1392 /* Return pass stone to the passing player. */
1393 board->captures[stone_other(board->last_move.color)]--;
1395 board->last_move = board->last_move2;
1396 board->last_move2 = board->last_move3;
1397 board->last_move3 = board->last_move4;
1398 if (board->last_ko_age == board->moves)
1399 board->ko = board->last_ko;
1400 return 0;
1403 static inline bool
1404 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f, ppr_permit permit, void *permit_data)
1406 *coord = b->f[f];
1407 struct move m = { *coord, color };
1408 if (DEBUGL(6))
1409 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));
1410 if (unlikely(board_is_one_point_eye(b, *coord, color)) /* bad idea to play into one, usually */
1411 || !board_is_valid_move(b, &m)
1412 || (permit && !permit(permit_data, b, &m)))
1413 return false;
1414 if (m.coord == *coord) {
1415 return likely(board_play_f(b, &m, f) >= 0);
1416 } else {
1417 *coord = m.coord; // permit modified the coordinate
1418 return likely(board_play(b, &m) >= 0);
1422 void
1423 board_play_random(struct board *b, enum stone color, coord_t *coord, ppr_permit permit, void *permit_data)
1425 if (unlikely(b->flen == 0))
1426 goto pass;
1428 int base = fast_random(b->flen), f;
1429 for (f = base; f < b->flen; f++)
1430 if (board_try_random_move(b, color, coord, f, permit, permit_data))
1431 return;
1432 for (f = 0; f < base; f++)
1433 if (board_try_random_move(b, color, coord, f, permit, permit_data))
1434 return;
1436 pass:
1437 *coord = pass;
1438 struct move m = { pass, color };
1439 board_play(b, &m);
1443 bool
1444 board_is_false_eyelike(struct board *board, coord_t coord, enum stone eye_color)
1446 enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
1448 /* XXX: We attempt false eye detection but we will yield false
1449 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
1451 foreach_diag_neighbor(board, coord) {
1452 color_diag_libs[(enum stone) board_at(board, c)]++;
1453 } foreach_diag_neighbor_end;
1454 /* For false eye, we need two enemy stones diagonally in the
1455 * middle of the board, or just one enemy stone at the edge
1456 * or in the corner. */
1457 color_diag_libs[stone_other(eye_color)] += !!color_diag_libs[S_OFFBOARD];
1458 return color_diag_libs[stone_other(eye_color)] >= 2;
1461 bool
1462 board_is_one_point_eye(struct board *board, coord_t coord, enum stone eye_color)
1464 return board_is_eyelike(board, coord, eye_color)
1465 && !board_is_false_eyelike(board, coord, eye_color);
1468 enum stone
1469 board_get_one_point_eye(struct board *board, coord_t coord)
1471 if (board_is_one_point_eye(board, coord, S_WHITE))
1472 return S_WHITE;
1473 else if (board_is_one_point_eye(board, coord, S_BLACK))
1474 return S_BLACK;
1475 else
1476 return S_NONE;
1480 floating_t
1481 board_fast_score(struct board *board)
1483 int scores[S_MAX];
1484 memset(scores, 0, sizeof(scores));
1486 foreach_point(board) {
1487 enum stone color = board_at(board, c);
1488 if (color == S_NONE && board->rules != RULES_STONES_ONLY)
1489 color = board_get_one_point_eye(board, c);
1490 scores[color]++;
1491 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1492 } foreach_point_end;
1494 return board->komi + (board->rules != RULES_SIMING ? board->handicap : 0) + scores[S_WHITE] - scores[S_BLACK];
1497 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1499 /* One flood-fill iteration; returns true if next iteration
1500 * is required. */
1501 static bool
1502 board_tromp_taylor_iter(struct board *board, int *ownermap)
1504 bool needs_update = false;
1505 foreach_free_point(board) {
1506 /* Ignore occupied and already-dame positions. */
1507 assert(board_at(board, c) == S_NONE);
1508 if (board->rules == RULES_STONES_ONLY)
1509 ownermap[c] = 3;
1510 if (ownermap[c] == 3)
1511 continue;
1512 /* Count neighbors. */
1513 int nei[4] = {0};
1514 foreach_neighbor(board, c, {
1515 nei[ownermap[c]]++;
1517 /* If we have neighbors of both colors, or dame,
1518 * we are dame too. */
1519 if ((nei[1] && nei[2]) || nei[3]) {
1520 ownermap[c] = 3;
1521 /* Speed up the propagation. */
1522 foreach_neighbor(board, c, {
1523 if (board_at(board, c) == S_NONE)
1524 ownermap[c] = 3;
1526 needs_update = true;
1527 continue;
1529 /* If we have neighbors of one color, we are owned
1530 * by that color, too. */
1531 if (!ownermap[c] && (nei[1] || nei[2])) {
1532 int newowner = nei[1] ? 1 : 2;
1533 ownermap[c] = newowner;
1534 /* Speed up the propagation. */
1535 foreach_neighbor(board, c, {
1536 if (board_at(board, c) == S_NONE && !ownermap[c])
1537 ownermap[c] = newowner;
1539 needs_update = true;
1540 continue;
1542 } foreach_free_point_end;
1543 return needs_update;
1546 /* Tromp-Taylor Counting */
1547 floating_t
1548 board_official_score(struct board *board, struct move_queue *q)
1551 /* A point P, not colored C, is said to reach C, if there is a path of
1552 * (vertically or horizontally) adjacent points of P's color from P to
1553 * a point of color C.
1555 * A player's score is the number of points of her color, plus the
1556 * number of empty points that reach only her color. */
1558 int ownermap[board_size2(board)];
1559 int s[4] = {0};
1560 const int o[4] = {0, 1, 2, 0};
1561 foreach_point(board) {
1562 ownermap[c] = o[board_at(board, c)];
1563 s[board_at(board, c)]++;
1564 } foreach_point_end;
1566 if (q) {
1567 /* Process dead groups. */
1568 for (unsigned int i = 0; i < q->moves; i++) {
1569 foreach_in_group(board, q->move[i]) {
1570 enum stone color = board_at(board, c);
1571 ownermap[c] = o[stone_other(color)];
1572 s[color]--; s[stone_other(color)]++;
1573 } foreach_in_group_end;
1577 /* We need to special-case empty board. */
1578 if (!s[S_BLACK] && !s[S_WHITE])
1579 return board->komi;
1581 while (board_tromp_taylor_iter(board, ownermap))
1582 /* Flood-fill... */;
1584 int scores[S_MAX];
1585 memset(scores, 0, sizeof(scores));
1587 foreach_point(board) {
1588 assert(board_at(board, c) == S_OFFBOARD || ownermap[c] != 0);
1589 if (ownermap[c] == 3)
1590 continue;
1591 scores[ownermap[c]]++;
1592 } foreach_point_end;
1594 return board->komi + (board->rules != RULES_SIMING ? board->handicap : 0) + scores[S_WHITE] - scores[S_BLACK];
1597 bool
1598 board_set_rules(struct board *board, char *name)
1600 if (!strcasecmp(name, "japanese")) {
1601 board->rules = RULES_JAPANESE;
1602 } else if (!strcasecmp(name, "chinese")) {
1603 board->rules = RULES_CHINESE;
1604 } else if (!strcasecmp(name, "aga")) {
1605 board->rules = RULES_AGA;
1606 } else if (!strcasecmp(name, "new_zealand")) {
1607 board->rules = RULES_NEW_ZEALAND;
1608 } else if (!strcasecmp(name, "siming") || !strcasecmp(name, "simplified_ing")) {
1609 board->rules = RULES_SIMING;
1610 } else {
1611 return false;
1613 return true;