Merge branch 'master' of ssh://repo.or.cz/srv/git/pachi
[pachi/json.git] / board.c
blob9c005a849f8d833a74dedcf973b77b51676153e6
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 = malloc2(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 = malloc2(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 = malloc2(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
331 static char *
332 board_print_top(struct board *board, char *s, char *end, int c)
334 for (int i = 0; i < c; i++) {
335 char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
336 s += snprintf(s, end - s, " ");
337 for (int x = 1; x < board_size(board) - 1; x++)
338 s += snprintf(s, end - s, "%c ", asdf[x - 1]);
339 s += snprintf(s, end -s, " ");
341 s += snprintf(s, end - s, "\n");
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_bottom(struct board *board, char *s, char *end, int c)
355 for (int i = 0; i < c; i++) {
356 s += snprintf(s, end - s, " +-");
357 for (int x = 1; x < board_size(board) - 1; x++)
358 s += snprintf(s, end - s, "--");
359 s += snprintf(s, end - s, "+");
361 s += snprintf(s, end - s, "\n");
362 return s;
365 static char *
366 board_print_row(struct board *board, int y, char *s, char *end, board_cprint cprint)
368 s += snprintf(s, end - s, " %2d | ", y);
369 for (int x = 1; x < board_size(board) - 1; x++) {
370 if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
371 s += snprintf(s, end - s, "%c)", stone2char(board_atxy(board, x, y)));
372 else
373 s += snprintf(s, end - s, "%c ", stone2char(board_atxy(board, x, y)));
375 s += snprintf(s, end - s, "|");
376 if (cprint) {
377 s += snprintf(s, end - s, " %2d | ", y);
378 for (int x = 1; x < board_size(board) - 1; x++) {
379 s = cprint(board, coord_xy(board, x, y), s, end);
381 s += snprintf(s, end - s, "|");
383 s += snprintf(s, end - s, "\n");
384 return s;
387 void
388 board_print_custom(struct board *board, FILE *f, board_cprint cprint)
390 char buf[10240];
391 char *s = buf;
392 char *end = buf + sizeof(buf);
393 s += snprintf(s, end - s, "Move: % 3d Komi: %2.1f Handicap: %d Captures B: %d W: %d\n",
394 board->moves, board->komi, board->handicap,
395 board->captures[S_BLACK], board->captures[S_WHITE]);
396 s = board_print_top(board, s, end, 1 + !!cprint);
397 for (int y = board_size(board) - 2; y >= 1; y--)
398 s = board_print_row(board, y, s, end, cprint);
399 board_print_bottom(board, s, end, 1 + !!cprint);
400 fprintf(f, "%s\n", buf);
403 static char *
404 cprint_group(struct board *board, coord_t c, char *s, char *end)
406 s += snprintf(s, end - s, "%d ", group_base(group_at(board, c)));
407 return s;
410 void
411 board_print(struct board *board, FILE *f)
413 board_print_custom(board, f, DEBUGL(6) ? cprint_group : NULL);
416 void
417 board_gamma_set(struct board *b, struct features_gamma *gamma, bool precise_selfatari)
419 #ifdef BOARD_GAMMA
420 b->gamma = gamma;
421 b->precise_selfatari = precise_selfatari;
422 for (int i = 0; i < b->flen; i++) {
423 if (is_pass(b->f[i])) continue;
424 board_trait_recompute(b, b->f[i]);
426 #endif
430 /* Update the probability distribution we maintain incrementally. */
431 void
432 board_gamma_update(struct board *board, coord_t coord, enum stone color)
434 #ifdef BOARD_GAMMA
435 if (!board->gamma)
436 return;
438 /* Punch out invalid moves and moves filling our own eyes. */
439 if (board_at(board, coord) != S_NONE
440 || (board_is_eyelike(board, coord, stone_other(color))
441 && !trait_at(board, coord, color).cap)
442 || (board_is_one_point_eye(board, coord, color))) {
443 probdist_set(&board->prob[color - 1], coord, 0);
444 return;
447 int pat = board->pat3[coord];
448 if (color == S_WHITE) {
449 /* We work with the pattern3s as black-to-play. */
450 pat = pattern3_reverse(pat);
453 /* We just quickly replicate the general pattern matcher stuff
454 * here in the most bare-bone way. */
455 double value = board->gamma->gamma[FEAT_PATTERN3][pat];
456 if (trait_at(board, coord, color).cap)
457 value *= board->gamma->gamma[FEAT_CAPTURE][0];
458 if (trait_at(board, coord, stone_other(color)).cap
459 && trait_at(board, coord, color).safe)
460 value *= board->gamma->gamma[FEAT_AESCAPE][0];
461 if (!trait_at(board, coord, color).safe)
462 value *= board->gamma->gamma[FEAT_SELFATARI][1 + board->precise_selfatari];
463 probdist_set(&board->prob[color - 1], coord, value);
464 #endif
467 #ifdef BOARD_TRAITS
468 static bool
469 board_trait_safe(struct board *board, coord_t coord, enum stone color)
471 /* sic! */
472 if (board->precise_selfatari)
473 return is_bad_selfatari(board, color, coord);
474 else
475 return board_safe_to_play(board, coord, color);
478 static void
479 board_trait_recompute(struct board *board, coord_t coord)
481 trait_at(board, coord, S_BLACK).safe = board_trait_safe(board, coord, S_BLACK);;
482 trait_at(board, coord, S_WHITE).safe = board_trait_safe(board, coord, S_WHITE);
483 if (DEBUGL(8)) {
484 fprintf(stderr, "traits[%s:%s lib=%d] (black cap=%d safe=%d) (white cap=%d safe=%d)\n",
485 coord2sstr(coord, board), stone2str(board_at(board, coord)), immediate_liberty_count(board, coord),
486 trait_at(board, coord, S_BLACK).cap, trait_at(board, coord, S_BLACK).safe,
487 trait_at(board, coord, S_WHITE).cap, trait_at(board, coord, S_WHITE).safe);
489 board_gamma_update(board, coord, S_BLACK);
490 board_gamma_update(board, coord, S_WHITE);
492 #endif
494 /* Recompute traits for dirty points that we have previously touched
495 * somehow (libs of their neighbors changed or so). */
496 static void
497 board_traits_recompute(struct board *board)
499 #ifdef BOARD_TRAITS
500 for (int i = 0; i < board->tqlen; i++) {
501 coord_t coord = board->tq[i];
502 if (!trait_at(board, coord, S_BLACK).dirty) continue;
503 if (board_at(board, coord) != S_NONE) continue;
504 board_trait_recompute(board, coord);
505 trait_at(board, coord, S_BLACK).dirty = false;
507 board->tqlen = 0;
508 #endif
511 /* Queue traits of given point for recomputing. */
512 static void
513 board_trait_queue(struct board *board, coord_t coord)
515 #ifdef BOARD_TRAITS
516 board->tq[board->tqlen++] = coord;
517 trait_at(board, coord, S_BLACK).dirty = true;
518 #endif
522 /* Update board hash with given coordinate. */
523 static void profiling_noinline
524 board_hash_update(struct board *board, coord_t coord, enum stone color)
526 board->hash ^= hash_at(board, coord, color);
527 if (DEBUGL(8))
528 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);
530 #ifdef BOARD_SPATHASH
531 /* Gridcular metric is reflective, so we update all hashes
532 * of appropriate ditance in OUR circle. */
533 for (int d = 1; d <= BOARD_SPATHASH_MAXD; d++) {
534 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
535 ptcoords_at(x, y, coord, board, j);
536 /* We either changed from S_NONE to color
537 * or vice versa; doesn't matter. */
538 board->spathash[coord_xy(board, x, y)][d - 1][0] ^=
539 pthashes[0][j][color] ^ pthashes[0][j][S_NONE];
540 board->spathash[coord_xy(board, x, y)][d - 1][1] ^=
541 pthashes[0][j][stone_other(color)] ^ pthashes[0][j][S_NONE];
544 #endif
546 #if defined(BOARD_PAT3)
547 /* @color is not what we need in case of capture. */
548 enum stone new_color = board_at(board, coord);
549 if (new_color == S_NONE)
550 board->pat3[coord] = pattern3_hash(board, coord);
551 foreach_8neighbor(board, coord) { // internally, the loop uses fn__i=[0..7]
552 if (board_at(board, c) != S_NONE)
553 continue;
554 board->pat3[c] &= ~(3 << (fn__i*2));
555 board->pat3[c] |= new_color << (fn__i*2);
556 #if 0
557 if (board_at(board, c) != S_OFFBOARD && pattern3_hash(board, c) != board->pat3[c]) {
558 board_print(board, stderr);
559 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);
560 assert(0);
562 #endif
563 board_gamma_update(board, c, S_BLACK);
564 board_gamma_update(board, c, S_WHITE);
565 } foreach_8neighbor_end;
566 #endif
569 /* Commit current board hash to history. */
570 static void profiling_noinline
571 board_hash_commit(struct board *board)
573 if (DEBUGL(8))
574 fprintf(stderr, "board_hash_commit %"PRIhash"\n", board->hash);
575 if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
576 board->history_hash[board->hash & history_hash_mask] = board->hash;
577 } else {
578 hash_t i = board->hash;
579 while (board->history_hash[i & history_hash_mask]) {
580 if (board->history_hash[i & history_hash_mask] == board->hash) {
581 if (DEBUGL(5))
582 fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
583 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
584 board->superko_violation = true;
585 return;
587 i = history_hash_next(i);
589 board->history_hash[i & history_hash_mask] = board->hash;
594 void
595 board_symmetry_update(struct board *b, struct board_symmetry *symmetry, coord_t c)
597 if (likely(symmetry->type == SYM_NONE)) {
598 /* Fully degenerated already. We do not support detection
599 * of restoring of symmetry, assuming that this is too rare
600 * a case to handle. */
601 return;
604 int x = coord_x(c, b), y = coord_y(c, b), t = board_size(b) / 2;
605 int dx = board_size(b) - 1 - x; /* for SYM_DOWN */
606 if (DEBUGL(6)) {
607 fprintf(stderr, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
608 symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
609 symmetry->d, symmetry->type, x, y);
612 switch (symmetry->type) {
613 case SYM_FULL:
614 if (x == t && y == t) {
615 /* Tengen keeps full symmetry. */
616 return;
618 /* New symmetry now? */
619 if (x == y) {
620 symmetry->type = SYM_DIAG_UP;
621 symmetry->x1 = symmetry->y1 = 1;
622 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
623 symmetry->d = 1;
624 } else if (dx == y) {
625 symmetry->type = SYM_DIAG_DOWN;
626 symmetry->x1 = symmetry->y1 = 1;
627 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
628 symmetry->d = 1;
629 } else if (x == t) {
630 symmetry->type = SYM_HORIZ;
631 symmetry->y1 = 1;
632 symmetry->y2 = board_size(b) - 1;
633 symmetry->d = 0;
634 } else if (y == t) {
635 symmetry->type = SYM_VERT;
636 symmetry->x1 = 1;
637 symmetry->x2 = board_size(b) - 1;
638 symmetry->d = 0;
639 } else {
640 break_symmetry:
641 symmetry->type = SYM_NONE;
642 symmetry->x1 = symmetry->y1 = 1;
643 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
644 symmetry->d = 0;
646 break;
647 case SYM_DIAG_UP:
648 if (x == y)
649 return;
650 goto break_symmetry;
651 case SYM_DIAG_DOWN:
652 if (dx == y)
653 return;
654 goto break_symmetry;
655 case SYM_HORIZ:
656 if (x == t)
657 return;
658 goto break_symmetry;
659 case SYM_VERT:
660 if (y == t)
661 return;
662 goto break_symmetry;
663 case SYM_NONE:
664 assert(0);
665 break;
668 if (DEBUGL(6)) {
669 fprintf(stderr, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
670 symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
671 symmetry->d, symmetry->type);
673 /* Whew. */
677 void
678 board_handicap_stone(struct board *board, int x, int y, FILE *f)
680 struct move m;
681 m.color = S_BLACK; m.coord = coord_xy(board, x, y);
683 board_play(board, &m);
684 /* Simulate white passing; otherwise, UCT search can get confused since
685 * tree depth parity won't match the color to move. */
686 board->moves++;
688 char *str = coord2str(m.coord, board);
689 if (DEBUGL(1))
690 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
691 if (f) fprintf(f, "%s ", str);
692 free(str);
695 void
696 board_handicap(struct board *board, int stones, FILE *f)
698 int margin = 3 + (board_size(board) >= 13);
699 int min = margin;
700 int mid = board_size(board) / 2;
701 int max = board_size(board) - 1 - margin;
702 const int places[][2] = {
703 { min, min }, { max, max }, { max, min }, { min, max },
704 { min, mid }, { max, mid },
705 { mid, min }, { mid, max },
706 { mid, mid },
709 board->handicap = stones;
711 if (stones == 5 || stones == 7) {
712 board_handicap_stone(board, mid, mid, f);
713 stones--;
716 int i;
717 for (i = 0; i < stones; i++)
718 board_handicap_stone(board, places[i][0], places[i][1], f);
722 static void __attribute__((noinline))
723 check_libs_consistency(struct board *board, group_t g)
725 #ifdef DEBUG
726 if (!g) return;
727 struct group *gi = &board_group_info(board, g);
728 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
729 if (gi->lib[i] && board_at(board, gi->lib[i]) != S_NONE) {
730 fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(group_base(g), board));
731 assert(0);
733 #endif
736 static void
737 board_capturable_add(struct board *board, group_t group, coord_t lib)
739 //fprintf(stderr, "group %s cap %s\n", coord2sstr(group, board), coord2sstr(lib, boarD));
740 #ifdef BOARD_TRAITS
741 /* Increase capturable count trait of my last lib. */
742 enum stone capturing_color = stone_other(board_at(board, group));
743 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
744 foreach_neighbor(board, lib, {
745 if (DEBUGL(8) && group_at(board, c) == group)
746 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));
747 trait_at(board, lib, capturing_color).cap += (group_at(board, c) == group);
749 board_trait_queue(board, lib);
750 #endif
752 #ifdef WANT_BOARD_C
753 /* Update the list of capturable groups. */
754 assert(group);
755 assert(board->clen < board_size2(board));
756 board->c[board->clen++] = group;
757 #endif
759 static void
760 board_capturable_rm(struct board *board, group_t group, coord_t lib)
762 //fprintf(stderr, "group %s nocap %s\n", coord2sstr(group, board), coord2sstr(lib, board));
763 #ifdef BOARD_TRAITS
764 /* Decrease capturable count trait of my previously-last lib. */
765 enum stone capturing_color = stone_other(board_at(board, group));
766 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
767 foreach_neighbor(board, lib, {
768 if (DEBUGL(8) && group_at(board, c) == group)
769 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));
770 trait_at(board, lib, capturing_color).cap -= (group_at(board, c) == group);
772 board_trait_queue(board, lib);
773 #endif
775 #ifdef WANT_BOARD_C
776 /* Update the list of capturable groups. */
777 for (int i = 0; i < board->clen; i++) {
778 if (unlikely(board->c[i] == group)) {
779 board->c[i] = board->c[--board->clen];
780 return;
783 fprintf(stderr, "rm of bad group %d\n", group_base(group));
784 assert(0);
785 #endif
788 static void
789 board_atariable_add(struct board *board, group_t group, coord_t lib1, coord_t lib2)
791 #ifdef BOARD_TRAITS
792 board_trait_queue(board, lib1);
793 board_trait_queue(board, lib2);
794 #endif
796 static void
797 board_atariable_rm(struct board *board, group_t group, coord_t lib1, coord_t lib2)
799 #ifdef BOARD_TRAITS
800 board_trait_queue(board, lib1);
801 board_trait_queue(board, lib2);
802 #endif
805 static void
806 board_group_addlib(struct board *board, group_t group, coord_t coord)
808 if (DEBUGL(7)) {
809 fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n",
810 group_base(group), coord2sstr(group_base(group), board),
811 board_group_info(board, group).libs, coord2sstr(coord, board));
814 check_libs_consistency(board, group);
816 struct group *gi = &board_group_info(board, group);
817 if (gi->libs < GROUP_KEEP_LIBS) {
818 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
819 #if 0
820 /* Seems extra branch just slows it down */
821 if (!gi->lib[i])
822 break;
823 #endif
824 if (unlikely(gi->lib[i] == coord))
825 return;
827 if (gi->libs == 0) {
828 board_capturable_add(board, group, coord);
829 } else if (gi->libs == 1) {
830 board_capturable_rm(board, group, gi->lib[0]);
831 board_atariable_add(board, group, gi->lib[0], coord);
832 } else if (gi->libs == 2) {
833 board_atariable_rm(board, group, gi->lib[0], gi->lib[1]);
835 gi->lib[gi->libs++] = coord;
838 check_libs_consistency(board, group);
841 static void
842 board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid)
844 /* Add extra liberty from the board to our liberty list. */
845 unsigned char watermark[board_size2(board) / 8];
846 memset(watermark, 0, sizeof(watermark));
847 #define watermark_get(c) (watermark[coord_raw(c) >> 3] & (1 << (coord_raw(c) & 7)))
848 #define watermark_set(c) watermark[coord_raw(c) >> 3] |= (1 << (coord_raw(c) & 7))
850 for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++)
851 watermark_set(gi->lib[i]);
852 watermark_set(avoid);
854 foreach_in_group(board, group) {
855 coord_t coord2 = c;
856 foreach_neighbor(board, coord2, {
857 if (board_at(board, c) + watermark_get(c) != S_NONE)
858 continue;
859 watermark_set(c);
860 gi->lib[gi->libs++] = c;
861 if (unlikely(gi->libs >= GROUP_KEEP_LIBS))
862 return;
863 } );
864 } foreach_in_group_end;
865 #undef watermark_get
866 #undef watermark_set
869 static void
870 board_group_rmlib(struct board *board, group_t group, coord_t coord)
872 if (DEBUGL(7)) {
873 fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n",
874 group_base(group), coord2sstr(group_base(group), board),
875 board_group_info(board, group).libs, coord2sstr(coord, board));
878 struct group *gi = &board_group_info(board, group);
879 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
880 #if 0
881 /* Seems extra branch just slows it down */
882 if (!gi->lib[i])
883 break;
884 #endif
885 if (likely(gi->lib[i] != coord))
886 continue;
888 coord_t lib = gi->lib[i] = gi->lib[--gi->libs];
889 gi->lib[gi->libs] = 0;
891 check_libs_consistency(board, group);
893 /* Postpone refilling lib[] until we need to. */
894 assert(GROUP_REFILL_LIBS > 1);
895 if (gi->libs > GROUP_REFILL_LIBS)
896 return;
897 if (gi->libs == GROUP_REFILL_LIBS)
898 board_group_find_extra_libs(board, group, gi, coord);
900 if (gi->libs == 2) {
901 board_atariable_add(board, group, gi->lib[0], gi->lib[1]);
902 } else if (gi->libs == 1) {
903 board_capturable_add(board, group, gi->lib[0]);
904 board_atariable_rm(board, group, gi->lib[0], lib);
905 } else if (gi->libs == 0)
906 board_capturable_rm(board, group, lib);
907 return;
910 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
911 * can call this multiple times per coord. */
912 check_libs_consistency(board, group);
913 return;
917 /* This is a low-level routine that doesn't maintain consistency
918 * of all the board data structures. */
919 static void
920 board_remove_stone(struct board *board, group_t group, coord_t c)
922 enum stone color = board_at(board, c);
923 board_at(board, c) = S_NONE;
924 group_at(board, c) = 0;
925 board_hash_update(board, c, color);
926 #ifdef BOARD_TRAITS
927 /* We mark as cannot-capture now. If this is a ko/snapback,
928 * we will get incremented later in board_group_addlib(). */
929 trait_at(board, c, S_BLACK).cap = 0;
930 trait_at(board, c, S_WHITE).cap = 0;
931 board_trait_queue(board, c);
932 #endif
934 /* Increase liberties of surrounding groups */
935 coord_t coord = c;
936 foreach_neighbor(board, coord, {
937 dec_neighbor_count_at(board, c, color);
938 board_trait_queue(board, c);
939 group_t g = group_at(board, c);
940 if (g && g != group)
941 board_group_addlib(board, g, coord);
944 if (DEBUGL(6))
945 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
946 board->f[board->flen++] = coord_raw(c);
949 static int profiling_noinline
950 board_group_capture(struct board *board, group_t group)
952 int stones = 0;
954 foreach_in_group(board, group) {
955 board->captures[stone_other(board_at(board, c))]++;
956 board_remove_stone(board, group, c);
957 stones++;
958 } foreach_in_group_end;
960 struct group *gi = &board_group_info(board, group);
961 if (gi->libs == 2)
962 board_atariable_rm(board, group, gi->lib[0], gi->lib[1]);
963 else if (gi->libs == 1)
964 board_capturable_rm(board, group, gi->lib[0]);
965 memset(gi, 0, sizeof(*gi));
967 return stones;
971 static void profiling_noinline
972 add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord)
974 group_at(board, coord) = group;
975 groupnext_at(board, coord) = groupnext_at(board, prevstone);
976 groupnext_at(board, prevstone) = coord_raw(coord);
978 #ifdef BOARD_TRAITS
979 if (board_group_info(board, group).libs == 1) {
980 /* Our group is temporarily in atari; make sure the capturable
981 * counts also correspond to the newly added stone before we
982 * start adding liberties again so bump-dump ops match. */
983 enum stone capturing_color = stone_other(board_at(board, group));
984 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
985 coord_t lib = board_group_info(board, group).lib[0];
986 if (coord_is_adjecent(lib, coord, board)) {
987 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);
988 trait_at(board, lib, capturing_color).cap++;
989 board_trait_queue(board, lib);
992 #endif
994 foreach_neighbor(board, coord, {
995 if (board_at(board, c) == S_NONE)
996 board_group_addlib(board, group, c);
999 if (DEBUGL(8))
1000 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
1001 coord_x(prevstone, board), coord_y(prevstone, board),
1002 coord_x(coord, board), coord_y(coord, board),
1003 groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
1004 group_base(group));
1007 static void profiling_noinline
1008 merge_groups(struct board *board, group_t group_to, group_t group_from)
1010 if (DEBUGL(7))
1011 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
1012 group_base(group_from), group_base(group_to));
1013 struct group *gi_from = &board_group_info(board, group_from);
1014 struct group *gi_to = &board_group_info(board, group_to);
1016 /* We do this early before the group info is rewritten. */
1017 if (gi_from->libs == 2)
1018 board_atariable_rm(board, group_from, gi_from->lib[0], gi_from->lib[1]);
1019 else if (gi_from->libs == 1)
1020 board_capturable_rm(board, group_from, gi_from->lib[0]);
1022 if (DEBUGL(7))
1023 fprintf(stderr,"---- (froml %d, tol %d)\n", gi_from->libs, gi_to->libs);
1025 if (gi_to->libs < GROUP_KEEP_LIBS) {
1026 for (int i = 0; i < gi_from->libs; i++) {
1027 for (int j = 0; j < gi_to->libs; j++)
1028 if (gi_to->lib[j] == gi_from->lib[i])
1029 goto next_from_lib;
1030 if (gi_to->libs == 0) {
1031 board_capturable_add(board, group_to, gi_from->lib[i]);
1032 } else if (gi_to->libs == 1) {
1033 board_capturable_rm(board, group_to, gi_to->lib[0]);
1034 board_atariable_add(board, group_to, gi_to->lib[0], gi_from->lib[i]);
1035 } else if (gi_to->libs == 2) {
1036 board_atariable_rm(board, group_to, gi_to->lib[0], gi_to->lib[1]);
1038 gi_to->lib[gi_to->libs++] = gi_from->lib[i];
1039 if (gi_to->libs >= GROUP_KEEP_LIBS)
1040 break;
1041 next_from_lib:;
1045 #ifdef BOARD_TRAITS
1046 if (board_group_info(board, group_to).libs == 1) {
1047 /* Our group is currently in atari; make sure we properly
1048 * count in even the neighbors from the other group in the
1049 * capturable counter. */
1050 enum stone capturing_color = stone_other(board_at(board, group_to));
1051 assert(capturing_color == S_BLACK || capturing_color == S_WHITE);
1052 coord_t lib = board_group_info(board, group_to).lib[0];
1053 foreach_neighbor(board, lib, {
1054 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);
1055 trait_at(board, lib, capturing_color).cap += (group_at(board, c) == group_from);
1057 board_trait_queue(board, lib);
1059 #endif
1061 coord_t last_in_group;
1062 foreach_in_group(board, group_from) {
1063 last_in_group = c;
1064 group_at(board, c) = group_to;
1065 } foreach_in_group_end;
1066 groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to));
1067 groupnext_at(board, group_base(group_to)) = group_base(group_from);
1068 memset(gi_from, 0, sizeof(struct group));
1070 if (DEBUGL(7))
1071 fprintf(stderr, "board_play_raw: merged group: %d\n",
1072 group_base(group_to));
1075 static group_t profiling_noinline
1076 new_group(struct board *board, coord_t coord)
1078 group_t group = coord_raw(coord);
1079 struct group *gi = &board_group_info(board, group);
1080 foreach_neighbor(board, coord, {
1081 if (board_at(board, c) == S_NONE)
1082 /* board_group_addlib is ridiculously expensive for us */
1083 #if GROUP_KEEP_LIBS < 4
1084 if (gi->libs < GROUP_KEEP_LIBS)
1085 #endif
1086 gi->lib[gi->libs++] = c;
1089 group_at(board, coord) = group;
1090 groupnext_at(board, coord) = 0;
1092 if (gi->libs == 2)
1093 board_atariable_add(board, group, gi->lib[0], gi->lib[1]);
1094 else if (gi->libs == 1)
1095 board_capturable_add(board, group, gi->lib[0]);
1096 check_libs_consistency(board, group);
1098 if (DEBUGL(8))
1099 fprintf(stderr, "new_group: added %d,%d to group %d\n",
1100 coord_x(coord, board), coord_y(coord, board),
1101 group_base(group));
1103 return group;
1106 static inline group_t
1107 play_one_neighbor(struct board *board,
1108 coord_t coord, enum stone color, enum stone other_color,
1109 coord_t c, group_t group)
1111 enum stone ncolor = board_at(board, c);
1112 group_t ngroup = group_at(board, c);
1114 inc_neighbor_count_at(board, c, color);
1115 /* We can be S_NONE, in that case we need to update the safety
1116 * trait since we might be left with only one liberty. */
1117 board_trait_queue(board, c);
1119 if (!ngroup)
1120 return group;
1122 board_group_rmlib(board, ngroup, coord);
1123 if (DEBUGL(7))
1124 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
1125 group_base(ngroup), ncolor, color, other_color);
1127 if (ncolor == color && ngroup != group) {
1128 if (!group) {
1129 group = ngroup;
1130 add_to_group(board, group, c, coord);
1131 } else {
1132 merge_groups(board, group, ngroup);
1134 } else if (ncolor == other_color) {
1135 if (DEBUGL(8)) {
1136 struct group *gi = &board_group_info(board, ngroup);
1137 fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board));
1138 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
1139 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
1140 fprintf(stderr, "\n");
1142 if (unlikely(board_group_captured(board, ngroup)))
1143 board_group_capture(board, ngroup);
1145 return group;
1148 /* We played on a place with at least one liberty. We will become a member of
1149 * some group for sure. */
1150 static group_t profiling_noinline
1151 board_play_outside(struct board *board, struct move *m, int f)
1153 coord_t coord = m->coord;
1154 enum stone color = m->color;
1155 enum stone other_color = stone_other(color);
1156 group_t group = 0;
1158 board->f[f] = board->f[--board->flen];
1159 if (DEBUGL(6))
1160 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
1162 #if defined(BOARD_TRAITS) && defined(DEBUG)
1163 /* Sanity check that cap matches reality. */
1165 int a = 0;
1166 foreach_neighbor(board, coord, {
1167 group_t g = group_at(board, c);
1168 a += g && (board_at(board, c) == other_color && board_group_info(board, g).libs == 1);
1170 assert(a == trait_at(board, coord, color).cap);
1171 assert(board_trait_safe(board, coord, color) == trait_at(board, coord, color).safe);
1173 #endif
1174 foreach_neighbor(board, coord, {
1175 group = play_one_neighbor(board, coord, color, other_color, c, group);
1178 board_at(board, coord) = color;
1179 if (unlikely(!group))
1180 group = new_group(board, coord);
1181 board_gamma_update(board, coord, S_BLACK);
1182 board_gamma_update(board, coord, S_WHITE);
1184 board->last_move2 = board->last_move;
1185 board->last_move = *m;
1186 board->moves++;
1187 board_hash_update(board, coord, color);
1188 board_symmetry_update(board, &board->symmetry, coord);
1189 struct move ko = { pass, S_NONE };
1190 board->ko = ko;
1192 return group;
1195 /* We played in an eye-like shape. Either we capture at least one of the eye
1196 * sides in the process of playing, or return -1. */
1197 static int profiling_noinline
1198 board_play_in_eye(struct board *board, struct move *m, int f)
1200 coord_t coord = m->coord;
1201 enum stone color = m->color;
1202 /* Check ko: Capture at a position of ko capture one move ago */
1203 if (unlikely(color == board->ko.color && coord_eq(coord, board->ko.coord))) {
1204 if (DEBUGL(5))
1205 fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
1206 return -1;
1207 } else if (DEBUGL(6)) {
1208 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
1209 color, coord_x(coord, board), coord_y(coord, board),
1210 board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
1213 struct move ko = { pass, S_NONE };
1215 int captured_groups = 0;
1217 foreach_neighbor(board, coord, {
1218 group_t g = group_at(board, c);
1219 if (DEBUGL(7))
1220 fprintf(stderr, "board_check: group %d has %d libs\n",
1221 g, board_group_info(board, g).libs);
1222 captured_groups += (board_group_info(board, g).libs == 1);
1225 if (likely(captured_groups == 0)) {
1226 if (DEBUGL(5)) {
1227 if (DEBUGL(6))
1228 board_print(board, stderr);
1229 fprintf(stderr, "board_check: one-stone suicide\n");
1232 return -1;
1234 #ifdef BOARD_TRAITS
1235 /* We _will_ for sure capture something. */
1236 assert(trait_at(board, coord, color).cap > 0);
1237 assert(trait_at(board, coord, color).safe == board_trait_safe(board, coord, color));
1238 #endif
1240 board->f[f] = board->f[--board->flen];
1241 if (DEBUGL(6))
1242 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
1244 foreach_neighbor(board, coord, {
1245 inc_neighbor_count_at(board, c, color);
1246 /* Originally, this could not have changed any trait
1247 * since no neighbors were S_NONE, however by now some
1248 * of them might be removed from the board. */
1249 board_trait_queue(board, c);
1251 group_t group = group_at(board, c);
1252 if (!group)
1253 continue;
1255 board_group_rmlib(board, group, coord);
1256 if (DEBUGL(7))
1257 fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
1258 group_base(group));
1260 if (board_group_captured(board, group)) {
1261 if (board_group_capture(board, group) == 1) {
1262 /* If we captured multiple groups at once,
1263 * we can't be fighting ko so we don't need
1264 * to check for that. */
1265 ko.color = stone_other(color);
1266 ko.coord = c;
1267 board->last_ko = ko;
1268 board->last_ko_age = board->moves;
1269 if (DEBUGL(5))
1270 fprintf(stderr, "guarding ko at %d,%s\n", ko.color, coord2sstr(ko.coord, board));
1275 board_at(board, coord) = color;
1276 group_t group = new_group(board, coord);
1277 board_gamma_update(board, coord, S_BLACK);
1278 board_gamma_update(board, coord, S_WHITE);
1280 board->last_move2 = board->last_move;
1281 board->last_move = *m;
1282 board->moves++;
1283 board_hash_update(board, coord, color);
1284 board_hash_commit(board);
1285 board_traits_recompute(board);
1286 board_symmetry_update(board, &board->symmetry, coord);
1287 board->ko = ko;
1289 return !!group;
1292 static int __attribute__((flatten))
1293 board_play_f(struct board *board, struct move *m, int f)
1295 if (DEBUGL(7)) {
1296 fprintf(stderr, "board_play(): ---- Playing %d,%d\n", coord_x(m->coord, board), coord_y(m->coord, board));
1298 if (likely(!board_is_eyelike(board, m->coord, stone_other(m->color)))) {
1299 /* NOT playing in an eye. Thus this move has to succeed. (This
1300 * is thanks to New Zealand rules. Otherwise, multi-stone
1301 * suicide might fail.) */
1302 group_t group = board_play_outside(board, m, f);
1303 if (unlikely(board_group_captured(board, group))) {
1304 board_group_capture(board, group);
1306 board_hash_commit(board);
1307 board_traits_recompute(board);
1308 return 0;
1309 } else {
1310 return board_play_in_eye(board, m, f);
1315 board_play(struct board *board, struct move *m)
1317 if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
1318 struct move nomove = { pass, S_NONE };
1319 board->ko = nomove;
1320 board->last_move2 = board->last_move;
1321 board->last_move = *m;
1322 return 0;
1325 int f;
1326 for (f = 0; f < board->flen; f++)
1327 if (board->f[f] == coord_raw(m->coord))
1328 return board_play_f(board, m, f);
1330 if (DEBUGL(7))
1331 fprintf(stderr, "board_check: stone exists\n");
1332 return -1;
1336 static inline bool
1337 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f, ppr_permit permit, void *permit_data)
1339 coord_raw(*coord) = b->f[f];
1340 if (unlikely(is_pass(*coord)))
1341 return random_pass;
1342 struct move m = { *coord, color };
1343 if (DEBUGL(6))
1344 fprintf(stderr, "trying random move %d: %d,%d\n", f, coord_x(*coord, b), coord_y(*coord, b));
1345 return (likely(!board_is_one_point_eye(b, *coord, color)) /* bad idea to play into one, usually */
1346 && board_is_valid_move(b, &m)
1347 && (!permit || permit(permit_data, b, &m))
1348 && likely(board_play_f(b, &m, f) >= 0));
1351 void
1352 board_play_random(struct board *b, enum stone color, coord_t *coord, ppr_permit permit, void *permit_data)
1354 int base = fast_random(b->flen);
1355 coord_pos(*coord, base, b);
1356 if (likely(board_try_random_move(b, color, coord, base, permit, permit_data)))
1357 return;
1359 int f;
1360 for (f = base + 1; f < b->flen; f++)
1361 if (board_try_random_move(b, color, coord, f, permit, permit_data))
1362 return;
1363 for (f = 0; f < base; f++)
1364 if (board_try_random_move(b, color, coord, f, permit, permit_data))
1365 return;
1367 *coord = pass;
1368 struct move m = { pass, color };
1369 board_play(b, &m);
1373 bool
1374 board_is_false_eyelike(struct board *board, coord_t coord, enum stone eye_color)
1376 enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
1378 /* XXX: We attempt false eye detection but we will yield false
1379 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
1381 foreach_diag_neighbor(board, coord) {
1382 color_diag_libs[(enum stone) board_at(board, c)]++;
1383 } foreach_diag_neighbor_end;
1384 /* For false eye, we need two enemy stones diagonally in the
1385 * middle of the board, or just one enemy stone at the edge
1386 * or in the corner. */
1387 color_diag_libs[stone_other(eye_color)] += !!color_diag_libs[S_OFFBOARD];
1388 return color_diag_libs[stone_other(eye_color)] >= 2;
1391 bool
1392 board_is_one_point_eye(struct board *board, coord_t coord, enum stone eye_color)
1394 return board_is_eyelike(board, coord, eye_color)
1395 && !board_is_false_eyelike(board, coord, eye_color);
1398 enum stone
1399 board_get_one_point_eye(struct board *board, coord_t coord)
1401 if (board_is_one_point_eye(board, coord, S_WHITE))
1402 return S_WHITE;
1403 else if (board_is_one_point_eye(board, coord, S_BLACK))
1404 return S_BLACK;
1405 else
1406 return S_NONE;
1410 float
1411 board_fast_score(struct board *board)
1413 int scores[S_MAX];
1414 memset(scores, 0, sizeof(scores));
1416 foreach_point(board) {
1417 enum stone color = board_at(board, c);
1418 if (color == S_NONE)
1419 color = board_get_one_point_eye(board, c);
1420 scores[color]++;
1421 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1422 } foreach_point_end;
1424 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
1427 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1429 /* One flood-fill iteration; returns true if next iteration
1430 * is required. */
1431 static bool
1432 board_tromp_taylor_iter(struct board *board, int *ownermap)
1434 bool needs_update = false;
1435 foreach_point(board) {
1436 /* Ignore occupied and already-dame positions. */
1437 if (board_at(board, c) != S_NONE || ownermap[c] == 3)
1438 continue;
1439 /* Count neighbors. */
1440 int nei[4] = {0};
1441 foreach_neighbor(board, c, {
1442 nei[ownermap[c]]++;
1444 /* If we have neighbors of both colors, or dame,
1445 * we are dame too. */
1446 if ((nei[1] && nei[2]) || nei[3]) {
1447 ownermap[c] = 3;
1448 /* Speed up the propagation. */
1449 foreach_neighbor(board, c, {
1450 if (board_at(board, c) == S_NONE)
1451 ownermap[c] = 3;
1453 needs_update = true;
1454 continue;
1456 /* If we have neighbors of one color, we are owned
1457 * by that color, too. */
1458 if (!ownermap[c] && (nei[1] || nei[2])) {
1459 int newowner = nei[1] ? 1 : 2;
1460 ownermap[c] = newowner;
1461 /* Speed up the propagation. */
1462 foreach_neighbor(board, c, {
1463 if (board_at(board, c) == S_NONE && !ownermap[c])
1464 ownermap[c] = newowner;
1466 needs_update = true;
1467 continue;
1469 } foreach_point_end;
1470 return needs_update;
1473 /* Tromp-Taylor Counting */
1474 float
1475 board_official_score(struct board *board, struct move_queue *q)
1478 /* A point P, not colored C, is said to reach C, if there is a path of
1479 * (vertically or horizontally) adjacent points of P's color from P to
1480 * a point of color C.
1482 * A player's score is the number of points of her color, plus the
1483 * number of empty points that reach only her color. */
1485 int ownermap[board_size2(board)];
1486 int s[4] = {0};
1487 const int o[4] = {0, 1, 2, 0};
1488 foreach_point(board) {
1489 ownermap[c] = o[board_at(board, c)];
1490 s[board_at(board, c)]++;
1491 } foreach_point_end;
1493 if (q) {
1494 /* Process dead groups. */
1495 for (int i = 0; i < q->moves; i++) {
1496 foreach_in_group(board, q->move[i]) {
1497 enum stone color = board_at(board, c);
1498 ownermap[c] = o[stone_other(color)];
1499 s[color]--; s[stone_other(color)]++;
1500 } foreach_in_group_end;
1504 /* We need to special-case empty board. */
1505 if (!s[S_BLACK] && !s[S_WHITE])
1506 return board->komi + board->handicap;
1508 while (board_tromp_taylor_iter(board, ownermap))
1509 /* Flood-fill... */;
1511 int scores[S_MAX];
1512 memset(scores, 0, sizeof(scores));
1514 foreach_point(board) {
1515 assert(board_at(board, c) == S_OFFBOARD || ownermap[c] != 0);
1516 if (ownermap[c] == 3)
1517 continue;
1518 scores[ownermap[c]]++;
1519 } foreach_point_end;
1521 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];