Set board->size even if BOARD_SIZE is defined, for consistency
[pachi/derm.git] / board.c
blobddd6bc7f4e4b5687034211b2147a9988c2fd1218
1 #include <alloca.h>
2 #include <assert.h>
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <string.h>
7 #include "board.h"
8 #include "debug.h"
9 #include "mq.h"
10 #include "random.h"
12 #ifdef BOARD_SPATHASH
13 #include "patternsp.h"
14 #endif
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.h"
21 #endif
22 #ifdef BOARD_GAMMA
23 #include "pattern.h"
24 #endif
26 bool random_pass = false;
29 #if 0
30 #define profiling_noinline __attribute__((noinline))
31 #else
32 #define profiling_noinline
33 #endif
35 #define gi_granularity 4
36 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
39 static void
40 board_setup(struct board *b)
42 memset(b, 0, sizeof(*b));
44 struct move m = { pass, S_NONE };
45 b->last_move = b->last_move2 = b->last_ko = b->ko = m;
48 struct board *
49 board_init(void)
51 struct board *b = malloc(sizeof(struct board));
52 board_setup(b);
54 // Default setup
55 b->size = 9 + 2;
56 board_clear(b);
58 return b;
61 struct board *
62 board_copy(struct board *b2, struct board *b1)
64 memcpy(b2, b1, sizeof(struct board));
66 int bsize = board_size2(b2) * sizeof(*b2->b);
67 int gsize = board_size2(b2) * sizeof(*b2->g);
68 int fsize = board_size2(b2) * sizeof(*b2->f);
69 int nsize = board_size2(b2) * sizeof(*b2->n);
70 int psize = board_size2(b2) * sizeof(*b2->p);
71 int hsize = board_size2(b2) * 2 * sizeof(*b2->h);
72 int gisize = board_size2(b2) * sizeof(*b2->gi);
73 #ifdef WANT_BOARD_C
74 int csize = board_size2(b2) * sizeof(*b2->c);
75 #else
76 int csize = 0;
77 #endif
78 #ifdef BOARD_SPATHASH
79 int ssize = board_size2(b2) * sizeof(*b2->spathash);
80 #else
81 int ssize = 0;
82 #endif
83 #ifdef BOARD_PAT3
84 int p3size = board_size2(b2) * sizeof(*b2->pat3);
85 #else
86 int p3size = 0;
87 #endif
88 #ifdef BOARD_TRAITS
89 int tsize = board_size2(b2) * sizeof(*b2->t);
90 int tqsize = board_size2(b2) * sizeof(*b2->t);
91 #else
92 int tsize = 0;
93 int tqsize = 0;
94 #endif
95 #ifdef BOARD_GAMMA
96 int pbsize = board_size2(b2) * sizeof(*b2->prob[0].items);
97 #else
98 int pbsize = 0;
99 #endif
100 void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize + tqsize + pbsize * 2);
101 memcpy(x, b1->b, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize + tqsize + pbsize * 2);
102 b2->b = x; x += bsize;
103 b2->g = x; x += gsize;
104 b2->f = x; x += fsize;
105 b2->p = x; x += psize;
106 b2->n = x; x += nsize;
107 b2->h = x; x += hsize;
108 b2->gi = x; x += gisize;
109 #ifdef WANT_BOARD_C
110 b2->c = x; x += csize;
111 #endif
112 #ifdef BOARD_SPATHASH
113 b2->spathash = x; x += ssize;
114 #endif
115 #ifdef BOARD_PAT3
116 b2->pat3 = x; x += p3size;
117 #endif
118 #ifdef BOARD_TRAITS
119 b2->t = x; x += tsize;
120 b2->tq = x; x += tqsize;
121 #endif
122 #ifdef BOARD_GAMMA
123 b2->prob[0].items = x; x += pbsize;
124 b2->prob[1].items = x; x += pbsize;
125 #endif
127 return b2;
130 void
131 board_done_noalloc(struct board *board)
133 if (board->b) free(board->b);
136 void
137 board_done(struct board *board)
139 board_done_noalloc(board);
140 free(board);
143 void
144 board_resize(struct board *board, int size)
146 #ifdef BOARD_SIZE
147 assert(board_size(board) == size + 2);
148 #endif
149 board->size = size + 2 /* S_OFFBOARD margin */;
150 board->size2 = board_size(board) * board_size(board);
151 if (board->b)
152 free(board->b);
154 int bsize = board_size2(board) * sizeof(*board->b);
155 int gsize = board_size2(board) * sizeof(*board->g);
156 int fsize = board_size2(board) * sizeof(*board->f);
157 int nsize = board_size2(board) * sizeof(*board->n);
158 int psize = board_size2(board) * sizeof(*board->p);
159 int hsize = board_size2(board) * 2 * sizeof(*board->h);
160 int gisize = board_size2(board) * sizeof(*board->gi);
161 #ifdef WANT_BOARD_C
162 int csize = board_size2(board) * sizeof(*board->c);
163 #else
164 int csize = 0;
165 #endif
166 #ifdef BOARD_SPATHASH
167 int ssize = board_size2(board) * sizeof(*board->spathash);
168 #else
169 int ssize = 0;
170 #endif
171 #ifdef BOARD_PAT3
172 int p3size = board_size2(board) * sizeof(*board->pat3);
173 #else
174 int p3size = 0;
175 #endif
176 #ifdef BOARD_TRAITS
177 int tsize = board_size2(board) * sizeof(*board->t);
178 int tqsize = board_size2(board) * sizeof(*board->t);
179 #else
180 int tsize = 0;
181 int tqsize = 0;
182 #endif
183 #ifdef BOARD_GAMMA
184 int pbsize = board_size2(board) * sizeof(*board->prob[0].items);
185 #else
186 int pbsize = 0;
187 #endif
188 void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize + tqsize + pbsize * 2);
189 memset(x, 0, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize + tqsize + pbsize * 2);
190 board->b = x; x += bsize;
191 board->g = x; x += gsize;
192 board->f = x; x += fsize;
193 board->p = x; x += psize;
194 board->n = x; x += nsize;
195 board->h = x; x += hsize;
196 board->gi = x; x += gisize;
197 #ifdef WANT_BOARD_C
198 board->c = x; x += csize;
199 #endif
200 #ifdef BOARD_SPATHASH
201 board->spathash = x; x += ssize;
202 #endif
203 #ifdef BOARD_PAT3
204 board->pat3 = x; x += p3size;
205 #endif
206 #ifdef BOARD_TRAITS
207 board->t = x; x += tsize;
208 board->tq = x; x += tqsize;
209 #endif
210 #ifdef BOARD_GAMMA
211 board->prob[0].items = x; x += pbsize;
212 board->prob[1].items = x; x += pbsize;
213 #endif
216 void
217 board_clear(struct board *board)
219 int size = board_size(board);
220 float komi = board->komi;
222 board_done_noalloc(board);
223 board_setup(board);
224 board_resize(board, size - 2 /* S_OFFBOARD margin */);
226 board->komi = komi;
228 /* Setup neighborhood iterators */
229 board->nei8[0] = -size - 1; // (-1,-1)
230 board->nei8[1] = 1;
231 board->nei8[2] = 1;
232 board->nei8[3] = size - 2; // (-1,0)
233 board->nei8[4] = 2;
234 board->nei8[5] = size - 2; // (-1,1)
235 board->nei8[6] = 1;
236 board->nei8[7] = 1;
237 board->dnei[0] = -size - 1;
238 board->dnei[1] = 2;
239 board->dnei[2] = size*2 - 2;
240 board->dnei[3] = 2;
242 /* Setup initial symmetry */
243 board->symmetry.d = 1;
244 board->symmetry.x1 = board->symmetry.y1 = board_size(board) / 2;
245 board->symmetry.x2 = board->symmetry.y2 = board_size(board) - 1;
246 board->symmetry.type = SYM_FULL;
248 /* Draw the offboard margin */
249 int top_row = board_size2(board) - board_size(board);
250 int i;
251 for (i = 0; i < board_size(board); i++)
252 board->b[i] = board->b[top_row + i] = S_OFFBOARD;
253 for (i = 0; i <= top_row; i += board_size(board))
254 board->b[i] = board->b[board_size(board) - 1 + i] = S_OFFBOARD;
256 foreach_point(board) {
257 coord_t coord = c;
258 if (board_at(board, coord) == S_OFFBOARD)
259 continue;
260 foreach_neighbor(board, c, {
261 inc_neighbor_count_at(board, coord, board_at(board, c));
262 } );
263 } foreach_point_end;
265 /* First, pass is always a free position. */
266 board->f[board->flen++] = coord_raw(pass);
267 /* All positions are free! Except the margin. */
268 for (i = board_size(board); i < (board_size(board) - 1) * board_size(board); i++)
269 if (i % board_size(board) != 0 && i % board_size(board) != board_size(board) - 1)
270 board->f[board->flen++] = i;
272 /* Initialize zobrist hashtable. */
273 foreach_point(board) {
274 int max = (sizeof(hash_t) << history_hash_bits);
275 /* fast_random() is 16-bit only */
276 board->h[coord_raw(c) * 2] = ((hash_t) fast_random(max))
277 | ((hash_t) fast_random(max) << 16)
278 | ((hash_t) fast_random(max) << 32)
279 | ((hash_t) fast_random(max) << 48);
280 if (!board->h[coord_raw(c) * 2])
281 /* Would be kinda "oops". */
282 board->h[coord_raw(c) * 2] = 1;
283 /* And once again for white */
284 board->h[coord_raw(c) * 2 + 1] = ((hash_t) fast_random(max))
285 | ((hash_t) fast_random(max) << 16)
286 | ((hash_t) fast_random(max) << 32)
287 | ((hash_t) fast_random(max) << 48);
288 if (!board->h[coord_raw(c) * 2 + 1])
289 board->h[coord_raw(c) * 2 + 1] = 1;
290 } foreach_point_end;
292 #ifdef BOARD_SPATHASH
293 /* Initialize spatial hashes. */
294 foreach_point(board) {
295 for (int d = 1; d <= BOARD_SPATHASH_MAXD; d++) {
296 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
297 ptcoords_at(x, y, c, board, j);
298 board->spathash[coord_xy(board, x, y)][d - 1][0] ^=
299 pthashes[0][j][board_at(board, c)];
300 board->spathash[coord_xy(board, x, y)][d - 1][1] ^=
301 pthashes[0][j][stone_other(board_at(board, c))];
304 } foreach_point_end;
305 #endif
306 #ifdef BOARD_PAT3
307 /* Initialize 3x3 pattern codes. */
308 foreach_point(board) {
309 if (board_at(board, c) == S_NONE)
310 board->pat3[c] = pattern3_hash(board, c);
311 } foreach_point_end;
312 #endif
313 #ifdef BOARD_TRAITS
314 /* Initialize traits. */
315 foreach_point(board) {
316 trait_at(board, c, S_BLACK).cap = 0;
317 trait_at(board, c, S_BLACK).safe = true;
318 trait_at(board, c, S_WHITE).cap = 0;
319 trait_at(board, c, S_WHITE).safe = true;
320 } foreach_point_end;
321 #endif
322 #ifdef BOARD_GAMMA
323 board->prob[0].n = board->prob[1].n = board_size2(board);
324 foreach_point(board) {
325 probdist_set(&board->prob[0], c, (board_at(board, c) == S_NONE) * 1.0f);
326 probdist_set(&board->prob[1], c, (board_at(board, c) == S_NONE) * 1.0f);
327 } foreach_point_end;
328 #endif
332 static void
333 board_print_top(struct board *board, FILE *f, int c)
335 for (int i = 0; i < c; i++) {
336 char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
337 fprintf(f, " ");
338 for (int x = 1; x < board_size(board) - 1; x++)
339 fprintf(f, "%c ", asdf[x - 1]);
340 fprintf(f, " ");
342 fprintf(f, "\n");
343 for (int i = 0; i < c; i++) {
344 fprintf(f, " +-");
345 for (int x = 1; x < board_size(board) - 1; x++)
346 fprintf(f, "--");
347 fprintf(f, "+");
349 fprintf(f, "\n");
352 static void
353 board_print_bottom(struct board *board, FILE *f, int c)
355 for (int i = 0; i < c; i++) {
356 fprintf(f, " +-");
357 for (int x = 1; x < board_size(board) - 1; x++)
358 fprintf(f, "--");
359 fprintf(f, "+");
361 fprintf(f, "\n");
364 static void
365 board_print_row(struct board *board, int y, FILE *f, board_cprint cprint)
367 fprintf(f, " %2d | ", y);
368 for (int x = 1; x < board_size(board) - 1; x++) {
369 if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
370 fprintf(f, "%c)", stone2char(board_atxy(board, x, y)));
371 else
372 fprintf(f, "%c ", stone2char(board_atxy(board, x, y)));
374 fprintf(f, "|");
375 if (cprint) {
376 fprintf(f, " %2d | ", y);
377 for (int x = 1; x < board_size(board) - 1; x++) {
378 cprint(board, coord_xy(board, x, y), f);
380 fprintf(f, "|");
382 fprintf(f, "\n");
385 void
386 board_print_custom(struct board *board, FILE *f, board_cprint cprint)
388 fprintf(f, "Move: % 3d Komi: %2.1f Handicap: %d Captures B: %d W: %d\n",
389 board->moves, board->komi, board->handicap,
390 board->captures[S_BLACK], board->captures[S_WHITE]);
391 board_print_top(board, f, 1 + !!cprint);
392 for (int y = board_size(board) - 2; y >= 1; y--)
393 board_print_row(board, y, f, cprint);
394 board_print_bottom(board, f, 1 + !!cprint);
395 fprintf(f, "\n");
398 static void
399 cprint_group(struct board *board, coord_t c, FILE *f)
401 fprintf(f, "%d ", group_base(group_at(board, c)));
404 void
405 board_print(struct board *board, FILE *f)
407 board_print_custom(board, f, DEBUGL(6) ? cprint_group : NULL);
410 void
411 board_gamma_set(struct board *b, struct features_gamma *gamma, bool precise_selfatari)
413 #ifdef BOARD_GAMMA
414 b->gamma = gamma;
415 b->precise_selfatari = precise_selfatari;
416 for (int i = 0; i < b->flen; i++) {
417 if (is_pass(b->f[i])) continue;
418 board_trait_recompute(b, b->f[i]);
420 #endif
424 /* Update the probability distribution we maintain incrementally. */
425 void
426 board_gamma_update(struct board *board, coord_t coord, enum stone color)
428 #ifdef BOARD_GAMMA
429 if (!board->gamma)
430 return;
432 /* Punch out invalid moves and moves filling our own eyes. */
433 if (board_at(board, coord) != S_NONE
434 || (board_is_eyelike(board, coord, stone_other(color))
435 && !trait_at(board, coord, color).cap)
436 || (board_is_one_point_eye(board, coord, color))) {
437 probdist_set(&board->prob[color - 1], coord, 0);
438 return;
441 int pat = board->pat3[coord];
442 if (color == S_WHITE) {
443 /* We work with the pattern3s as black-to-play. */
444 pat = pattern3_reverse(pat);
447 /* We just quickly replicate the general pattern matcher stuff
448 * here in the most bare-bone way. */
449 double value = board->gamma->gamma[FEAT_PATTERN3][pat];
450 if (trait_at(board, coord, color).cap)
451 value *= board->gamma->gamma[FEAT_CAPTURE][0];
452 if (trait_at(board, coord, stone_other(color)).cap
453 && trait_at(board, coord, color).safe)
454 value *= board->gamma->gamma[FEAT_AESCAPE][0];
455 if (!trait_at(board, coord, color).safe)
456 value *= board->gamma->gamma[FEAT_SELFATARI][1 + board->precise_selfatari];
457 probdist_set(&board->prob[color - 1], coord, value);
458 #endif
461 #ifdef BOARD_TRAITS
462 static bool
463 board_trait_safe(struct board *board, coord_t coord, enum stone color)
465 /* sic! */
466 if (board->precise_selfatari)
467 return is_bad_selfatari(board, color, coord);
468 else
469 return board_safe_to_play(board, coord, color);
472 static void
473 board_trait_recompute(struct board *board, coord_t coord)
475 trait_at(board, coord, S_BLACK).safe = board_trait_safe(board, coord, S_BLACK);;
476 trait_at(board, coord, S_WHITE).safe = board_trait_safe(board, coord, S_WHITE);
477 if (DEBUGL(8)) {
478 fprintf(stderr, "traits[%s:%s lib=%d] (black cap=%d safe=%d) (white cap=%d safe=%d)\n",
479 coord2sstr(coord, board), stone2str(board_at(board, coord)), immediate_liberty_count(board, coord),
480 trait_at(board, coord, S_BLACK).cap, trait_at(board, coord, S_BLACK).safe,
481 trait_at(board, coord, S_WHITE).cap, trait_at(board, coord, S_WHITE).safe);
483 board_gamma_update(board, coord, S_BLACK);
484 board_gamma_update(board, coord, S_WHITE);
486 #endif
488 /* Recompute traits for dirty points that we have previously touched
489 * somehow (libs of their neighbors changed or so). */
490 static void
491 board_traits_recompute(struct board *board)
493 #ifdef BOARD_TRAITS
494 for (int i = 0; i < board->tqlen; i++) {
495 coord_t coord = board->tq[i];
496 if (!trait_at(board, coord, S_BLACK).dirty) continue;
497 if (board_at(board, coord) != S_NONE) continue;
498 board_trait_recompute(board, coord);
499 trait_at(board, coord, S_BLACK).dirty = false;
501 board->tqlen = 0;
502 #endif
505 /* Queue traits of given point for recomputing. */
506 static void
507 board_trait_queue(struct board *board, coord_t coord)
509 #ifdef BOARD_TRAITS
510 board->tq[board->tqlen++] = coord;
511 trait_at(board, coord, S_BLACK).dirty = true;
512 #endif
516 /* Update board hash with given coordinate. */
517 static void profiling_noinline
518 board_hash_update(struct board *board, coord_t coord, enum stone color)
520 board->hash ^= hash_at(board, coord, color);
521 if (DEBUGL(8))
522 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);
524 #ifdef BOARD_SPATHASH
525 /* Gridcular metric is reflective, so we update all hashes
526 * of appropriate ditance in OUR circle. */
527 for (int d = 1; d <= BOARD_SPATHASH_MAXD; d++) {
528 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
529 ptcoords_at(x, y, coord, board, j);
530 /* We either changed from S_NONE to color
531 * or vice versa; doesn't matter. */
532 board->spathash[coord_xy(board, x, y)][d - 1][0] ^=
533 pthashes[0][j][color] ^ pthashes[0][j][S_NONE];
534 board->spathash[coord_xy(board, x, y)][d - 1][1] ^=
535 pthashes[0][j][stone_other(color)] ^ pthashes[0][j][S_NONE];
538 #endif
540 #if defined(BOARD_PAT3)
541 /* @color is not what we need in case of capture. */
542 enum stone new_color = board_at(board, coord);
543 if (new_color == S_NONE)
544 board->pat3[coord] = pattern3_hash(board, coord);
545 foreach_8neighbor(board, coord) { // internally, the loop uses fn__i=[0..7]
546 if (board_at(board, c) != S_NONE)
547 continue;
548 board->pat3[c] &= ~(3 << (fn__i*2));
549 board->pat3[c] |= new_color << (fn__i*2);
550 #if 0
551 if (board_at(board, c) != S_OFFBOARD && pattern3_hash(board, c) != board->pat3[c]) {
552 board_print(board, stderr);
553 fprintf(stderr, "%s->%s %x != %x (%d-%d:%d)\n", coord2sstr(coord, board), coord2sstr(c, board), pattern3_hash(board, c), board->pat3[c], coord, c, fn__i);
554 assert(0);
556 #endif
557 board_gamma_update(board, c, S_BLACK);
558 board_gamma_update(board, c, S_WHITE);
559 } foreach_8neighbor_end;
560 #endif
563 /* Commit current board hash to history. */
564 static void profiling_noinline
565 board_hash_commit(struct board *board)
567 if (DEBUGL(8))
568 fprintf(stderr, "board_hash_commit %"PRIhash"\n", board->hash);
569 if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
570 board->history_hash[board->hash & history_hash_mask] = board->hash;
571 } else {
572 hash_t i = board->hash;
573 while (board->history_hash[i & history_hash_mask]) {
574 if (board->history_hash[i & history_hash_mask] == board->hash) {
575 if (DEBUGL(5))
576 fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
577 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
578 board->superko_violation = true;
579 return;
581 i = history_hash_next(i);
583 board->history_hash[i & history_hash_mask] = board->hash;
588 void
589 board_symmetry_update(struct board *b, struct board_symmetry *symmetry, coord_t c)
591 if (likely(symmetry->type == SYM_NONE)) {
592 /* Fully degenerated already. We do not support detection
593 * of restoring of symmetry, assuming that this is too rare
594 * a case to handle. */
595 return;
598 int x = coord_x(c, b), y = coord_y(c, b), t = board_size(b) / 2;
599 int dx = board_size(b) - 1 - x; /* for SYM_DOWN */
600 if (DEBUGL(6)) {
601 fprintf(stderr, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
602 symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
603 symmetry->d, symmetry->type, x, y);
606 switch (symmetry->type) {
607 case SYM_FULL:
608 if (x == t && y == t) {
609 /* Tengen keeps full symmetry. */
610 return;
612 /* New symmetry now? */
613 if (x == y) {
614 symmetry->type = SYM_DIAG_UP;
615 symmetry->x1 = symmetry->y1 = 1;
616 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
617 symmetry->d = 1;
618 } else if (dx == y) {
619 symmetry->type = SYM_DIAG_DOWN;
620 symmetry->x1 = symmetry->y1 = 1;
621 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
622 symmetry->d = 1;
623 } else if (x == t) {
624 symmetry->type = SYM_HORIZ;
625 symmetry->y1 = 1;
626 symmetry->y2 = board_size(b) - 1;
627 symmetry->d = 0;
628 } else if (y == t) {
629 symmetry->type = SYM_VERT;
630 symmetry->x1 = 1;
631 symmetry->x2 = board_size(b) - 1;
632 symmetry->d = 0;
633 } else {
634 break_symmetry:
635 symmetry->type = SYM_NONE;
636 symmetry->x1 = symmetry->y1 = 1;
637 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
638 symmetry->d = 0;
640 break;
641 case SYM_DIAG_UP:
642 if (x == y)
643 return;
644 goto break_symmetry;
645 case SYM_DIAG_DOWN:
646 if (dx == y)
647 return;
648 goto break_symmetry;
649 case SYM_HORIZ:
650 if (x == t)
651 return;
652 goto break_symmetry;
653 case SYM_VERT:
654 if (y == t)
655 return;
656 goto break_symmetry;
657 case SYM_NONE:
658 assert(0);
659 break;
662 if (DEBUGL(6)) {
663 fprintf(stderr, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
664 symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
665 symmetry->d, symmetry->type);
667 /* Whew. */
671 void
672 board_handicap_stone(struct board *board, int x, int y, FILE *f)
674 struct move m;
675 m.color = S_BLACK; m.coord = coord_xy(board, x, y);
677 board_play(board, &m);
678 /* Simulate white passing; otherwise, UCT search can get confused since
679 * tree depth parity won't match the color to move. */
680 board->moves++;
682 char *str = coord2str(m.coord, board);
683 if (DEBUGL(1))
684 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
685 fprintf(f, "%s ", str);
686 free(str);
689 void
690 board_handicap(struct board *board, int stones, FILE *f)
692 int margin = 3 + (board_size(board) >= 13);
693 int min = margin;
694 int mid = board_size(board) / 2;
695 int max = board_size(board) - 1 - margin;
696 const int places[][2] = {
697 { min, min }, { max, max }, { max, min }, { min, max },
698 { min, mid }, { max, mid },
699 { mid, min }, { mid, max },
700 { mid, mid },
703 board->handicap = stones;
705 if (stones == 5 || stones == 7) {
706 board_handicap_stone(board, mid, mid, f);
707 stones--;
710 int i;
711 for (i = 0; i < stones; i++)
712 board_handicap_stone(board, places[i][0], places[i][1], f);
716 static void __attribute__((noinline))
717 check_libs_consistency(struct board *board, group_t g)
719 #ifdef DEBUG
720 if (!g) return;
721 struct group *gi = &board_group_info(board, g);
722 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
723 if (gi->lib[i] && board_at(board, gi->lib[i]) != S_NONE) {
724 fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(group_base(g), board));
725 assert(0);
727 #endif
730 static void
731 board_capturable_add(struct board *board, group_t group, coord_t lib)
733 //fprintf(stderr, "group %s cap %s\n", coord2sstr(group, board), coord2sstr(lib, boarD));
734 #ifdef BOARD_TRAITS
735 /* Increase capturable count trait of my last lib. */
736 enum stone capturing_color = stone_other(board_at(board, group));
737 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
738 foreach_neighbor(board, lib, {
739 if (DEBUGL(8) && group_at(board, c) == group)
740 fprintf(stderr, "%s[%d] %s cap bump bc of %s(%d) member %s\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));
741 trait_at(board, lib, capturing_color).cap += (group_at(board, c) == group);
743 board_trait_queue(board, lib);
744 #endif
746 #ifdef WANT_BOARD_C
747 /* Update the list of capturable groups. */
748 assert(group);
749 assert(board->clen < board_size2(board));
750 board->c[board->clen++] = group;
751 #endif
753 static void
754 board_capturable_rm(struct board *board, group_t group, coord_t lib)
756 //fprintf(stderr, "group %s nocap %s\n", coord2sstr(group, board), coord2sstr(lib, board));
757 #ifdef BOARD_TRAITS
758 /* Decrease capturable count trait of my previously-last lib. */
759 enum stone capturing_color = stone_other(board_at(board, group));
760 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
761 foreach_neighbor(board, lib, {
762 if (DEBUGL(8) && group_at(board, c) == group)
763 fprintf(stderr, "%s[%d] cap dump bc of %s(%d) member %s\n", coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap, coord2sstr(group, board), board_group_info(board, group).libs, coord2sstr(c, board));
764 trait_at(board, lib, capturing_color).cap -= (group_at(board, c) == group);
766 board_trait_queue(board, lib);
767 #endif
769 #ifdef WANT_BOARD_C
770 /* Update the list of capturable groups. */
771 for (int i = 0; i < board->clen; i++) {
772 if (unlikely(board->c[i] == group)) {
773 board->c[i] = board->c[--board->clen];
774 return;
777 fprintf(stderr, "rm of bad group %d\n", group_base(group));
778 assert(0);
779 #endif
782 static void
783 board_atariable_add(struct board *board, group_t group, coord_t lib1, coord_t lib2)
785 #ifdef BOARD_TRAITS
786 board_trait_queue(board, lib1);
787 board_trait_queue(board, lib2);
788 #endif
790 static void
791 board_atariable_rm(struct board *board, group_t group, coord_t lib1, coord_t lib2)
793 #ifdef BOARD_TRAITS
794 board_trait_queue(board, lib1);
795 board_trait_queue(board, lib2);
796 #endif
799 static void
800 board_group_addlib(struct board *board, group_t group, coord_t coord)
802 if (DEBUGL(7)) {
803 fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n",
804 group_base(group), coord2sstr(group_base(group), board),
805 board_group_info(board, group).libs, coord2sstr(coord, board));
808 check_libs_consistency(board, group);
810 struct group *gi = &board_group_info(board, group);
811 if (gi->libs < GROUP_KEEP_LIBS) {
812 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
813 #if 0
814 /* Seems extra branch just slows it down */
815 if (!gi->lib[i])
816 break;
817 #endif
818 if (unlikely(gi->lib[i] == coord))
819 return;
821 if (gi->libs == 0) {
822 board_capturable_add(board, group, coord);
823 } else if (gi->libs == 1) {
824 board_capturable_rm(board, group, gi->lib[0]);
825 board_atariable_add(board, group, gi->lib[0], coord);
826 } else if (gi->libs == 2) {
827 board_atariable_rm(board, group, gi->lib[0], gi->lib[1]);
829 gi->lib[gi->libs++] = coord;
832 check_libs_consistency(board, group);
835 static void
836 board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid)
838 /* Add extra liberty from the board to our liberty list. */
839 unsigned char watermark[board_size2(board) / 8];
840 memset(watermark, 0, sizeof(watermark));
841 #define watermark_get(c) (watermark[coord_raw(c) >> 3] & (1 << (coord_raw(c) & 7)))
842 #define watermark_set(c) watermark[coord_raw(c) >> 3] |= (1 << (coord_raw(c) & 7))
844 for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++)
845 watermark_set(gi->lib[i]);
846 watermark_set(avoid);
848 foreach_in_group(board, group) {
849 coord_t coord2 = c;
850 foreach_neighbor(board, coord2, {
851 if (board_at(board, c) + watermark_get(c) != S_NONE)
852 continue;
853 watermark_set(c);
854 gi->lib[gi->libs++] = c;
855 if (unlikely(gi->libs >= GROUP_KEEP_LIBS))
856 return;
857 } );
858 } foreach_in_group_end;
859 #undef watermark_get
860 #undef watermark_set
863 static void
864 board_group_rmlib(struct board *board, group_t group, coord_t coord)
866 if (DEBUGL(7)) {
867 fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n",
868 group_base(group), coord2sstr(group_base(group), board),
869 board_group_info(board, group).libs, coord2sstr(coord, board));
872 struct group *gi = &board_group_info(board, group);
873 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
874 #if 0
875 /* Seems extra branch just slows it down */
876 if (!gi->lib[i])
877 break;
878 #endif
879 if (likely(gi->lib[i] != coord))
880 continue;
882 coord_t lib = gi->lib[i] = gi->lib[--gi->libs];
883 gi->lib[gi->libs] = 0;
885 check_libs_consistency(board, group);
887 /* Postpone refilling lib[] until we need to. */
888 assert(GROUP_REFILL_LIBS > 1);
889 if (gi->libs > GROUP_REFILL_LIBS)
890 return;
891 if (gi->libs == GROUP_REFILL_LIBS)
892 board_group_find_extra_libs(board, group, gi, coord);
894 if (gi->libs == 2) {
895 board_atariable_add(board, group, gi->lib[0], gi->lib[1]);
896 } else if (gi->libs == 1) {
897 board_capturable_add(board, group, gi->lib[0]);
898 board_atariable_rm(board, group, gi->lib[0], lib);
899 } else if (gi->libs == 0)
900 board_capturable_rm(board, group, lib);
901 return;
904 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
905 * can call this multiple times per coord. */
906 check_libs_consistency(board, group);
907 return;
911 /* This is a low-level routine that doesn't maintain consistency
912 * of all the board data structures. */
913 static void
914 board_remove_stone(struct board *board, group_t group, coord_t c)
916 enum stone color = board_at(board, c);
917 board_at(board, c) = S_NONE;
918 group_at(board, c) = 0;
919 board_hash_update(board, c, color);
920 #ifdef BOARD_TRAITS
921 /* We mark as cannot-capture now. If this is a ko/snapback,
922 * we will get incremented later in board_group_addlib(). */
923 trait_at(board, c, S_BLACK).cap = 0;
924 trait_at(board, c, S_WHITE).cap = 0;
925 board_trait_queue(board, c);
926 #endif
928 /* Increase liberties of surrounding groups */
929 coord_t coord = c;
930 foreach_neighbor(board, coord, {
931 dec_neighbor_count_at(board, c, color);
932 board_trait_queue(board, c);
933 group_t g = group_at(board, c);
934 if (g && g != group)
935 board_group_addlib(board, g, coord);
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++] = coord_raw(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 if (gi->libs == 2)
956 board_atariable_rm(board, group, gi->lib[0], gi->lib[1]);
957 else if (gi->libs == 1)
958 board_capturable_rm(board, group, gi->lib[0]);
959 memset(gi, 0, sizeof(*gi));
961 return stones;
965 static void profiling_noinline
966 add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord)
968 group_at(board, coord) = group;
969 groupnext_at(board, coord) = groupnext_at(board, prevstone);
970 groupnext_at(board, prevstone) = coord_raw(coord);
972 #ifdef BOARD_TRAITS
973 if (board_group_info(board, group).libs == 1) {
974 /* Our group is temporarily in atari; make sure the capturable
975 * counts also correspond to the newly added stone before we
976 * start adding liberties again so bump-dump ops match. */
977 enum stone capturing_color = stone_other(board_at(board, group));
978 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
979 coord_t lib = board_group_info(board, group).lib[0];
980 if (coord_is_adjecent(lib, coord, board)) {
981 if (DEBUGL(8)) fprintf(stderr, "add_to_group %s: %s[%d] bump\n", coord2sstr(group, board), coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap);
982 trait_at(board, lib, capturing_color).cap++;
983 board_trait_queue(board, lib);
986 #endif
988 foreach_neighbor(board, coord, {
989 if (board_at(board, c) == S_NONE)
990 board_group_addlib(board, group, c);
993 if (DEBUGL(8))
994 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
995 coord_x(prevstone, board), coord_y(prevstone, board),
996 coord_x(coord, board), coord_y(coord, board),
997 groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
998 group_base(group));
1001 static void profiling_noinline
1002 merge_groups(struct board *board, group_t group_to, group_t group_from)
1004 if (DEBUGL(7))
1005 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
1006 group_base(group_from), group_base(group_to));
1007 struct group *gi_from = &board_group_info(board, group_from);
1008 struct group *gi_to = &board_group_info(board, group_to);
1010 /* We do this early before the group info is rewritten. */
1011 if (gi_from->libs == 2)
1012 board_atariable_rm(board, group_from, gi_from->lib[0], gi_from->lib[1]);
1013 else if (gi_from->libs == 1)
1014 board_capturable_rm(board, group_from, gi_from->lib[0]);
1016 if (DEBUGL(7))
1017 fprintf(stderr,"---- (froml %d, tol %d)\n", gi_from->libs, gi_to->libs);
1019 if (gi_to->libs < GROUP_KEEP_LIBS) {
1020 for (int i = 0; i < gi_from->libs; i++) {
1021 for (int j = 0; j < gi_to->libs; j++)
1022 if (gi_to->lib[j] == gi_from->lib[i])
1023 goto next_from_lib;
1024 if (gi_to->libs == 0) {
1025 board_capturable_add(board, group_to, gi_from->lib[i]);
1026 } else if (gi_to->libs == 1) {
1027 board_capturable_rm(board, group_to, gi_to->lib[0]);
1028 board_atariable_add(board, group_to, gi_to->lib[0], gi_from->lib[i]);
1029 } else if (gi_to->libs == 2) {
1030 board_atariable_rm(board, group_to, gi_to->lib[0], gi_to->lib[1]);
1032 gi_to->lib[gi_to->libs++] = gi_from->lib[i];
1033 if (gi_to->libs >= GROUP_KEEP_LIBS)
1034 break;
1035 next_from_lib:;
1039 #ifdef BOARD_TRAITS
1040 if (board_group_info(board, group_to).libs == 1) {
1041 /* Our group is currently in atari; make sure we properly
1042 * count in even the neighbors from the other group in the
1043 * capturable counter. */
1044 enum stone capturing_color = stone_other(board_at(board, group_to));
1045 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
1046 coord_t lib = board_group_info(board, group_to).lib[0];
1047 foreach_neighbor(board, lib, {
1048 if (DEBUGL(8) && group_at(board, c) == group_from) fprintf(stderr, "%s[%d] cap bump\n", coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap);
1049 trait_at(board, lib, capturing_color).cap += (group_at(board, c) == group_from);
1051 board_trait_queue(board, lib);
1053 #endif
1055 coord_t last_in_group;
1056 foreach_in_group(board, group_from) {
1057 last_in_group = c;
1058 group_at(board, c) = group_to;
1059 } foreach_in_group_end;
1060 groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to));
1061 groupnext_at(board, group_base(group_to)) = group_base(group_from);
1062 memset(gi_from, 0, sizeof(struct group));
1064 if (DEBUGL(7))
1065 fprintf(stderr, "board_play_raw: merged group: %d\n",
1066 group_base(group_to));
1069 static group_t profiling_noinline
1070 new_group(struct board *board, coord_t coord)
1072 group_t group = coord_raw(coord);
1073 struct group *gi = &board_group_info(board, group);
1074 foreach_neighbor(board, coord, {
1075 if (board_at(board, c) == S_NONE)
1076 /* board_group_addlib is ridiculously expensive for us */
1077 #if GROUP_KEEP_LIBS < 4
1078 if (gi->libs < GROUP_KEEP_LIBS)
1079 #endif
1080 gi->lib[gi->libs++] = c;
1083 group_at(board, coord) = group;
1084 groupnext_at(board, coord) = 0;
1086 if (gi->libs == 2)
1087 board_atariable_add(board, group, gi->lib[0], gi->lib[1]);
1088 else if (gi->libs == 1)
1089 board_capturable_add(board, group, gi->lib[0]);
1090 check_libs_consistency(board, group);
1092 if (DEBUGL(8))
1093 fprintf(stderr, "new_group: added %d,%d to group %d\n",
1094 coord_x(coord, board), coord_y(coord, board),
1095 group_base(group));
1097 return group;
1100 static inline group_t
1101 play_one_neighbor(struct board *board,
1102 coord_t coord, enum stone color, enum stone other_color,
1103 coord_t c, group_t group)
1105 enum stone ncolor = board_at(board, c);
1106 group_t ngroup = group_at(board, c);
1108 inc_neighbor_count_at(board, c, color);
1109 /* We can be S_NONE, in that case we need to update the safety
1110 * trait since we might be left with only one liberty. */
1111 board_trait_queue(board, c);
1113 if (!ngroup)
1114 return group;
1116 board_group_rmlib(board, ngroup, coord);
1117 if (DEBUGL(7))
1118 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
1119 group_base(ngroup), ncolor, color, other_color);
1121 if (ncolor == color && ngroup != group) {
1122 if (!group) {
1123 group = ngroup;
1124 add_to_group(board, group, c, coord);
1125 } else {
1126 merge_groups(board, group, ngroup);
1128 } else if (ncolor == other_color) {
1129 if (DEBUGL(8)) {
1130 struct group *gi = &board_group_info(board, ngroup);
1131 fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board));
1132 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
1133 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
1134 fprintf(stderr, "\n");
1136 if (unlikely(board_group_captured(board, ngroup)))
1137 board_group_capture(board, ngroup);
1139 return group;
1142 /* We played on a place with at least one liberty. We will become a member of
1143 * some group for sure. */
1144 static group_t profiling_noinline
1145 board_play_outside(struct board *board, struct move *m, int f)
1147 coord_t coord = m->coord;
1148 enum stone color = m->color;
1149 enum stone other_color = stone_other(color);
1150 group_t group = 0;
1152 board->f[f] = board->f[--board->flen];
1153 if (DEBUGL(6))
1154 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
1156 #if defined(BOARD_TRAITS) && defined(DEBUG)
1157 /* Sanity check that cap matches reality. */
1159 int a = 0;
1160 foreach_neighbor(board, coord, {
1161 group_t g = group_at(board, c);
1162 a += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1);
1164 assert(a == trait_at(board, coord, color).cap);
1165 assert(board_trait_safe(board, coord, color) == trait_at(board, coord, color).safe);
1167 #endif
1168 foreach_neighbor(board, coord, {
1169 group = play_one_neighbor(board, coord, color, other_color, c, group);
1172 board_at(board, coord) = color;
1173 if (unlikely(!group))
1174 group = new_group(board, coord);
1175 board_gamma_update(board, coord, S_BLACK);
1176 board_gamma_update(board, coord, S_WHITE);
1178 board->last_move2 = board->last_move;
1179 board->last_move = *m;
1180 board->moves++;
1181 board_hash_update(board, coord, color);
1182 board_symmetry_update(board, &board->symmetry, coord);
1183 struct move ko = { pass, S_NONE };
1184 board->ko = ko;
1186 return group;
1189 /* We played in an eye-like shape. Either we capture at least one of the eye
1190 * sides in the process of playing, or return -1. */
1191 static int profiling_noinline
1192 board_play_in_eye(struct board *board, struct move *m, int f)
1194 coord_t coord = m->coord;
1195 enum stone color = m->color;
1196 /* Check ko: Capture at a position of ko capture one move ago */
1197 if (unlikely(color == board->ko.color && coord_eq(coord, board->ko.coord))) {
1198 if (DEBUGL(5))
1199 fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
1200 return -1;
1201 } else if (DEBUGL(6)) {
1202 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
1203 color, coord_x(coord, board), coord_y(coord, board),
1204 board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
1207 struct move ko = { pass, S_NONE };
1209 int captured_groups = 0;
1211 foreach_neighbor(board, coord, {
1212 group_t g = group_at(board, c);
1213 if (DEBUGL(7))
1214 fprintf(stderr, "board_check: group %d has %d libs\n",
1215 g, board_group_info(board, g).libs);
1216 captured_groups += (board_group_info(board, g).libs == 1);
1219 if (likely(captured_groups == 0)) {
1220 if (DEBUGL(5)) {
1221 if (DEBUGL(6))
1222 board_print(board, stderr);
1223 fprintf(stderr, "board_check: one-stone suicide\n");
1226 return -1;
1228 #ifdef BOARD_TRAITS
1229 /* We _will_ for sure capture something. */
1230 assert(trait_at(board, coord, color).cap > 0);
1231 assert(trait_at(board, coord, color).safe == board_trait_safe(board, coord, color));
1232 #endif
1234 board->f[f] = board->f[--board->flen];
1235 if (DEBUGL(6))
1236 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
1238 foreach_neighbor(board, coord, {
1239 inc_neighbor_count_at(board, c, color);
1240 /* Originally, this could not have changed any trait
1241 * since no neighbors were S_NONE, however by now some
1242 * of them might be removed from the board. */
1243 board_trait_queue(board, c);
1245 group_t group = group_at(board, c);
1246 if (!group)
1247 continue;
1249 board_group_rmlib(board, group, coord);
1250 if (DEBUGL(7))
1251 fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
1252 group_base(group));
1254 if (board_group_captured(board, group)) {
1255 if (board_group_capture(board, group) == 1) {
1256 /* If we captured multiple groups at once,
1257 * we can't be fighting ko so we don't need
1258 * to check for that. */
1259 ko.color = stone_other(color);
1260 ko.coord = c;
1261 board->last_ko = ko;
1262 board->last_ko_age = board->moves;
1263 if (DEBUGL(5))
1264 fprintf(stderr, "guarding ko at %d,%s\n", ko.color, coord2sstr(ko.coord, board));
1269 board_at(board, coord) = color;
1270 group_t group = new_group(board, coord);
1271 board_gamma_update(board, coord, S_BLACK);
1272 board_gamma_update(board, coord, S_WHITE);
1274 board->last_move2 = board->last_move;
1275 board->last_move = *m;
1276 board->moves++;
1277 board_hash_update(board, coord, color);
1278 board_hash_commit(board);
1279 board_traits_recompute(board);
1280 board_symmetry_update(board, &board->symmetry, coord);
1281 board->ko = ko;
1283 return !!group;
1286 static int __attribute__((flatten))
1287 board_play_f(struct board *board, struct move *m, int f)
1289 if (DEBUGL(7)) {
1290 fprintf(stderr, "board_play(): ---- Playing %d,%d\n", coord_x(m->coord, board), coord_y(m->coord, board));
1292 if (likely(!board_is_eyelike(board, m->coord, stone_other(m->color)))) {
1293 /* NOT playing in an eye. Thus this move has to succeed. (This
1294 * is thanks to New Zealand rules. Otherwise, multi-stone
1295 * suicide might fail.) */
1296 group_t group = board_play_outside(board, m, f);
1297 if (unlikely(board_group_captured(board, group))) {
1298 board_group_capture(board, group);
1300 board_hash_commit(board);
1301 board_traits_recompute(board);
1302 return 0;
1303 } else {
1304 return board_play_in_eye(board, m, f);
1309 board_play(struct board *board, struct move *m)
1311 if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
1312 struct move nomove = { pass, S_NONE };
1313 board->ko = nomove;
1314 board->last_move2 = board->last_move;
1315 board->last_move = *m;
1316 return 0;
1319 int f;
1320 for (f = 0; f < board->flen; f++)
1321 if (board->f[f] == coord_raw(m->coord))
1322 return board_play_f(board, m, f);
1324 if (DEBUGL(7))
1325 fprintf(stderr, "board_check: stone exists\n");
1326 return -1;
1330 static inline bool
1331 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f, ppr_permit permit, void *permit_data)
1333 coord_raw(*coord) = b->f[f];
1334 if (unlikely(is_pass(*coord)))
1335 return random_pass;
1336 struct move m = { *coord, color };
1337 if (DEBUGL(6))
1338 fprintf(stderr, "trying random move %d: %d,%d\n", f, coord_x(*coord, b), coord_y(*coord, b));
1339 return (likely(!board_is_one_point_eye(b, *coord, color)) /* bad idea to play into one, usually */
1340 && board_is_valid_move(b, &m)
1341 && (!permit || permit(permit_data, b, &m))
1342 && likely(board_play_f(b, &m, f) >= 0));
1345 void
1346 board_play_random(struct board *b, enum stone color, coord_t *coord, ppr_permit permit, void *permit_data)
1348 int base = fast_random(b->flen);
1349 coord_pos(*coord, base, b);
1350 if (likely(board_try_random_move(b, color, coord, base, permit, permit_data)))
1351 return;
1353 int f;
1354 for (f = base + 1; f < b->flen; f++)
1355 if (board_try_random_move(b, color, coord, f, permit, permit_data))
1356 return;
1357 for (f = 0; f < base; f++)
1358 if (board_try_random_move(b, color, coord, f, permit, permit_data))
1359 return;
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 float
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_point(board) {
1430 /* Ignore occupied and already-dame positions. */
1431 if (board_at(board, c) != S_NONE || ownermap[c] == 3)
1432 continue;
1433 /* Count neighbors. */
1434 int nei[4] = {0};
1435 foreach_neighbor(board, c, {
1436 nei[ownermap[c]]++;
1438 /* If we have neighbors of both colors, or dame,
1439 * we are dame too. */
1440 if ((nei[1] && nei[2]) || nei[3]) {
1441 ownermap[c] = 3;
1442 /* Speed up the propagation. */
1443 foreach_neighbor(board, c, {
1444 if (board_at(board, c) == S_NONE)
1445 ownermap[c] = 3;
1447 needs_update = true;
1448 continue;
1450 /* If we have neighbors of one color, we are owned
1451 * by that color, too. */
1452 if (!ownermap[c] && (nei[1] || nei[2])) {
1453 int newowner = nei[1] ? 1 : 2;
1454 ownermap[c] = newowner;
1455 /* Speed up the propagation. */
1456 foreach_neighbor(board, c, {
1457 if (board_at(board, c) == S_NONE && !ownermap[c])
1458 ownermap[c] = newowner;
1460 needs_update = true;
1461 continue;
1463 } foreach_point_end;
1464 return needs_update;
1467 /* Tromp-Taylor Counting */
1468 float
1469 board_official_score(struct board *board, struct move_queue *q)
1472 /* A point P, not colored C, is said to reach C, if there is a path of
1473 * (vertically or horizontally) adjacent points of P's color from P to
1474 * a point of color C.
1476 * A player's score is the number of points of her color, plus the
1477 * number of empty points that reach only her color. */
1479 int ownermap[board_size2(board)];
1480 int s[4] = {0};
1481 const int o[4] = {0, 1, 2, 0};
1482 foreach_point(board) {
1483 ownermap[c] = o[board_at(board, c)];
1484 s[board_at(board, c)]++;
1485 } foreach_point_end;
1487 if (q) {
1488 /* Process dead groups. */
1489 for (int i = 0; i < q->moves; i++) {
1490 foreach_in_group(board, q->move[i]) {
1491 enum stone color = board_at(board, c);
1492 ownermap[c] = o[stone_other(color)];
1493 s[color]--; s[stone_other(color)]++;
1494 } foreach_in_group_end;
1498 /* We need to special-case empty board. */
1499 if (!s[S_BLACK] && !s[S_WHITE])
1500 return board->komi + board->handicap;
1502 while (board_tromp_taylor_iter(board, ownermap))
1503 /* Flood-fill... */;
1505 int scores[S_MAX];
1506 memset(scores, 0, sizeof(scores));
1508 foreach_point(board) {
1509 assert(board_at(board, c) == S_OFFBOARD || ownermap[c] != 0);
1510 if (ownermap[c] == 3)
1511 continue;
1512 scores[ownermap[c]]++;
1513 } foreach_point_end;
1515 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];