?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
TESTS: fba31 19x19
[pachi/json.git] / board.c
bloba1ce0108ad1bbef4c19865ce93f867d1d5cd06fa
1 #include <alloca.h>
2 #include <assert.h>
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <string.h>
6
7 #include "board.h"
8 #include "debug.h"
9 #include "random.h"
10
11 int board_group_capture(struct board *board, group_t group);
12
13 bool random_pass = false;
14
15
16 #if 0
17 #define profiling_noinline __attribute__((noinline))
18 #else
19 #define profiling_noinline
20 #endif
21
22 #define gi_granularity 4
23 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
24
25
26 static void
27 board_setup(struct board *b)
28 {
29 memset(b, 0, sizeof(*b));
30
31 struct move m = { pass, S_NONE };
32 b->last_move = b->last_move2 = b->last_ko = b->ko = m;
33 }
34
35 struct board *
36 board_init(void)
37 {
38 struct board *b = malloc(sizeof(struct board));
39 board_setup(b);
40
41 // Default setup
42 b->size = 9 + 2;
43 board_clear(b);
44
45 return b;
46 }
47
48 struct board *
49 board_copy(struct board *b2, struct board *b1)
50 {
51 memcpy(b2, b1, sizeof(struct board));
52
53 int bsize = board_size2(b2) * sizeof(*b2->b);
54 int gsize = board_size2(b2) * sizeof(*b2->g);
55 int fsize = board_size2(b2) * sizeof(*b2->f);
56 int nsize = board_size2(b2) * sizeof(*b2->n);
57 int psize = board_size2(b2) * sizeof(*b2->p);
58 int hsize = board_size2(b2) * 2 * sizeof(*b2->h);
59 int gisize = board_size2(b2) * sizeof(*b2->gi);
60 #ifdef WANT_BOARD_C
61 int csize = board_size2(b2) * sizeof(*b2->c);
62 #else
63 int csize = 0;
64 #endif
65 void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
66 memcpy(x, b1->b, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
67 b2->b = x; x += bsize;
68 b2->g = x; x += gsize;
69 b2->f = x; x += fsize;
70 b2->p = x; x += psize;
71 b2->n = x; x += nsize;
72 b2->h = x; x += hsize;
73 b2->gi = x; x += gisize;
74 #ifdef WANT_BOARD_C
75 b2->c = x; x += csize;
76 #endif
77
78 return b2;
79 }
80
81 void
82 board_done_noalloc(struct board *board)
83 {
84 if (board->b) free(board->b);
85 }
86
87 void
88 board_done(struct board *board)
89 {
90 board_done_noalloc(board);
91 free(board);
92 }
93
94 void
95 board_resize(struct board *board, int size)
96 {
97 #ifdef BOARD_SIZE
98 assert(board_size(board) == size + 2);
99 #else
100 board_size(board) = size + 2 /* S_OFFBOARD margin */;
101 board_size2(board) = board_size(board) * board_size(board);
102 #endif
103 if (board->b)
104 free(board->b);
105
106 int bsize = board_size2(board) * sizeof(*board->b);
107 int gsize = board_size2(board) * sizeof(*board->g);
108 int fsize = board_size2(board) * sizeof(*board->f);
109 int nsize = board_size2(board) * sizeof(*board->n);
110 int psize = board_size2(board) * sizeof(*board->p);
111 int hsize = board_size2(board) * 2 * sizeof(*board->h);
112 int gisize = board_size2(board) * sizeof(*board->gi);
113 #ifdef WANT_BOARD_C
114 int csize = board_size2(board) * sizeof(*board->c);
115 #else
116 int csize = 0;
117 #endif
118 void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
119 memset(x, 0, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
120 board->b = x; x += bsize;
121 board->g = x; x += gsize;
122 board->f = x; x += fsize;
123 board->p = x; x += psize;
124 board->n = x; x += nsize;
125 board->h = x; x += hsize;
126 board->gi = x; x += gisize;
127 #ifdef WANT_BOARD_C
128 board->c = x; x += csize;
129 #endif
130 }
131
132 void
133 board_clear(struct board *board)
134 {
135 int size = board_size(board);
136 float komi = board->komi;
137
138 board_done_noalloc(board);
139 board_setup(board);
140 board_resize(board, size - 2 /* S_OFFBOARD margin */);
141
142 board->komi = komi;
143
144 /* Setup initial symmetry */
145 board->symmetry.d = 1;
146 board->symmetry.x1 = board->symmetry.y1 = board_size(board) / 2;
147 board->symmetry.x2 = board->symmetry.y2 = board_size(board) - 1;
148 board->symmetry.type = SYM_FULL;
149
150 /* Draw the offboard margin */
151 int top_row = board_size2(board) - board_size(board);
152 int i;
153 for (i = 0; i < board_size(board); i++)
154 board->b[i] = board->b[top_row + i] = S_OFFBOARD;
155 for (i = 0; i <= top_row; i += board_size(board))
156 board->b[i] = board->b[board_size(board) - 1 + i] = S_OFFBOARD;
157
158 foreach_point(board) {
159 coord_t coord = c;
160 if (board_at(board, coord) == S_OFFBOARD)
161 continue;
162 foreach_neighbor(board, c, {
163 inc_neighbor_count_at(board, coord, board_at(board, c));
164 } );
165 } foreach_point_end;
166
167 /* First, pass is always a free position. */
168 board->f[board->flen++] = coord_raw(pass);
169 /* All positions are free! Except the margin. */
170 for (i = board_size(board); i < (board_size(board) - 1) * board_size(board); i++)
171 if (i % board_size(board) != 0 && i % board_size(board) != board_size(board) - 1)
172 board->f[board->flen++] = i;
173
174 /* Initialize zobrist hashtable. */
175 foreach_point(board) {
176 int max = (sizeof(hash_t) << history_hash_bits);
177 /* fast_random() is 16-bit only */
178 board->h[coord_raw(c) * 2] = ((hash_t) fast_random(max))
179 | ((hash_t) fast_random(max) << 16)
180 | ((hash_t) fast_random(max) << 32)
181 | ((hash_t) fast_random(max) << 48);
182 if (!board->h[coord_raw(c) * 2])
183 /* Would be kinda "oops". */
184 board->h[coord_raw(c) * 2] = 1;
185 /* And once again for white */
186 board->h[coord_raw(c) * 2 + 1] = ((hash_t) fast_random(max))
187 | ((hash_t) fast_random(max) << 16)
188 | ((hash_t) fast_random(max) << 32)
189 | ((hash_t) fast_random(max) << 48);
190 if (!board->h[coord_raw(c) * 2 + 1])
191 board->h[coord_raw(c) * 2 + 1] = 1;
192 } foreach_point_end;
193 }
194
195
196 static void
197 board_print_top(struct board *board, FILE *f, int c)
198 {
199 for (int i = 0; i < c; i++) {
200 char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
201 fprintf(f, " ");
202 for (int x = 1; x < board_size(board) - 1; x++)
203 fprintf(f, "%c ", asdf[x - 1]);
204 fprintf(f, " ");
205 }
206 fprintf(f, "\n");
207 for (int i = 0; i < c; i++) {
208 fprintf(f, " +-");
209 for (int x = 1; x < board_size(board) - 1; x++)
210 fprintf(f, "--");
211 fprintf(f, "+");
212 }
213 fprintf(f, "\n");
214 }
215
216 static void
217 board_print_bottom(struct board *board, FILE *f, int c)
218 {
219 for (int i = 0; i < c; i++) {
220 fprintf(f, " +-");
221 for (int x = 1; x < board_size(board) - 1; x++)
222 fprintf(f, "--");
223 fprintf(f, "+");
224 }
225 fprintf(f, "\n");
226 }
227
228 typedef void (*board_cprint)(struct board *b, coord_t c, FILE *f);
229
230 static void
231 board_print_row(struct board *board, int y, FILE *f, board_cprint cprint)
232 {
233 fprintf(f, " %2d | ", y);
234 for (int x = 1; x < board_size(board) - 1; x++) {
235 if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
236 fprintf(f, "%c)", stone2char(board_atxy(board, x, y)));
237 else
238 fprintf(f, "%c ", stone2char(board_atxy(board, x, y)));
239 }
240 fprintf(f, "|");
241 if (cprint) {
242 fprintf(f, " %2d | ", y);
243 for (int x = 1; x < board_size(board) - 1; x++) {
244 cprint(board, coord_xy(board, x, y), f);
245 }
246 fprintf(f, "|");
247 }
248 fprintf(f, "\n");
249 }
250
251 static void
252 board_print_x(struct board *board, FILE *f, board_cprint cprint)
253 {
254 fprintf(f, "Move: % 3d Komi: %2.1f Handicap: %d Captures B: %d W: %d\n",
255 board->moves, board->komi, board->handicap,
256 board->captures[S_BLACK], board->captures[S_WHITE]);
257 board_print_top(board, f, 1 + !!cprint);
258 for (int y = board_size(board) - 2; y >= 1; y--)
259 board_print_row(board, y, f, cprint);
260 board_print_bottom(board, f, 1 + !!cprint);
261 fprintf(f, "\n");
262 }
263
264 static void
265 cprint_group(struct board *board, coord_t c, FILE *f)
266 {
267 fprintf(f, "%d ", group_base(group_at(board, c)));
268 }
269
270 void
271 board_print(struct board *board, FILE *f)
272 {
273 board_print_x(board, f, DEBUGL(6) ? cprint_group : NULL);
274 }
275
276
277 /* Update board hash with given coordinate. */
278 static void profiling_noinline
279 board_hash_update(struct board *board, coord_t coord, enum stone color)
280 {
281 board->hash ^= hash_at(board, coord, color);
282 if (DEBUGL(8))
283 fprintf(stderr, "board_hash_update(%d,%d,%d) ^ %llx -> %llx\n", color, coord_x(coord, board), coord_y(coord, board), hash_at(board, coord, color), board->hash);
284 }
285
286 /* Commit current board hash to history. */
287 static void profiling_noinline
288 board_hash_commit(struct board *board)
289 {
290 if (DEBUGL(8))
291 fprintf(stderr, "board_hash_commit %llx\n", board->hash);
292 if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
293 board->history_hash[board->hash & history_hash_mask] = board->hash;
294 } else {
295 hash_t i = board->hash;
296 while (board->history_hash[i & history_hash_mask]) {
297 if (board->history_hash[i & history_hash_mask] == board->hash) {
298 if (DEBUGL(5))
299 fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
300 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
301 board->superko_violation = true;
302 return;
303 }
304 i = history_hash_next(i);
305 }
306 board->history_hash[i & history_hash_mask] = board->hash;
307 }
308 }
309
310
311 void
312 board_symmetry_update(struct board *b, struct board_symmetry *symmetry, coord_t c)
313 {
314 if (likely(symmetry->type == SYM_NONE)) {
315 /* Fully degenerated already. We do not support detection
316 * of restoring of symmetry, assuming that this is too rare
317 * a case to handle. */
318 return;
319 }
320
321 int x = coord_x(c, b), y = coord_y(c, b), t = board_size(b) / 2;
322 int dx = board_size(b) - 1 - x; /* for SYM_DOWN */
323 if (DEBUGL(6)) {
324 fprintf(stderr, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
325 symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
326 symmetry->d, symmetry->type, x, y);
327 }
328
329 switch (symmetry->type) {
330 case SYM_FULL:
331 if (x == t && y == t) {
332 /* Tengen keeps full symmetry. */
333 return;
334 }
335 /* New symmetry now? */
336 if (x == y) {
337 symmetry->type = SYM_DIAG_UP;
338 symmetry->x1 = symmetry->y1 = 1;
339 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
340 symmetry->d = 1;
341 } else if (dx == y) {
342 symmetry->type = SYM_DIAG_DOWN;
343 symmetry->x1 = symmetry->y1 = 1;
344 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
345 symmetry->d = 1;
346 } else if (x == t) {
347 symmetry->type = SYM_HORIZ;
348 symmetry->y1 = 1;
349 symmetry->y2 = board_size(b) - 1;
350 symmetry->d = 0;
351 } else if (y == t) {
352 symmetry->type = SYM_VERT;
353 symmetry->x1 = 1;
354 symmetry->x2 = board_size(b) - 1;
355 symmetry->d = 0;
356 } else {
357 break_symmetry:
358 symmetry->type = SYM_NONE;
359 symmetry->x1 = symmetry->y1 = 1;
360 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
361 symmetry->d = 0;
362 }
363 break;
364 case SYM_DIAG_UP:
365 if (x == y)
366 return;
367 goto break_symmetry;
368 case SYM_DIAG_DOWN:
369 if (dx == y)
370 return;
371 goto break_symmetry;
372 case SYM_HORIZ:
373 if (x == t)
374 return;
375 goto break_symmetry;
376 case SYM_VERT:
377 if (y == t)
378 return;
379 goto break_symmetry;
380 case SYM_NONE:
381 assert(0);
382 break;
383 }
384
385 if (DEBUGL(6)) {
386 fprintf(stderr, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
387 symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
388 symmetry->d, symmetry->type);
389 }
390 /* Whew. */
391 }
392
393
394 void
395 board_handicap_stone(struct board *board, int x, int y, FILE *f)
396 {
397 struct move m;
398 m.color = S_BLACK; m.coord = coord_xy(board, x, y);
399
400 board_play(board, &m);
401 /* Simulate white passing; otherwise, UCT search can get confused since
402 * tree depth parity won't match the color to move. */
403 board->moves++;
404
405 char *str = coord2str(m.coord, board);
406 if (DEBUGL(1))
407 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
408 fprintf(f, "%s ", str);
409 free(str);
410 }
411
412 void
413 board_handicap(struct board *board, int stones, FILE *f)
414 {
415 int margin = 3 + (board_size(board) >= 13);
416 int min = margin;
417 int mid = board_size(board) / 2;
418 int max = board_size(board) - 1 - margin;
419 const int places[][2] = {
420 { min, min }, { max, max }, { max, min }, { min, max },
421 { min, mid }, { max, mid },
422 { mid, min }, { mid, max },
423 { mid, mid },
424 };
425
426 board->handicap = stones;
427
428 if (stones == 5 || stones == 7) {
429 board_handicap_stone(board, mid, mid, f);
430 stones--;
431 }
432
433 int i;
434 for (i = 0; i < stones; i++)
435 board_handicap_stone(board, places[i][0], places[i][1], f);
436 }
437
438
439 static void __attribute__((noinline))
440 check_libs_consistency(struct board *board, group_t g)
441 {
442 #ifdef DEBUG
443 if (!g) return;
444 struct group *gi = &board_group_info(board, g);
445 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
446 if (gi->lib[i] && board_at(board, gi->lib[i]) != S_NONE) {
447 fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(group_base(g), board));
448 assert(0);
449 }
450 #endif
451 }
452
453 static void
454 board_capturable_add(struct board *board, group_t group)
455 {
456 #ifdef WANT_BOARD_C
457 //fprintf(stderr, "add of group %d (%d)\n", group_base(group), board->clen);
458 assert(group);
459 assert(board->clen < board_size2(board));
460 board->c[board->clen++] = group;
461 #endif
462 }
463 static void
464 board_capturable_rm(struct board *board, group_t group)
465 {
466 #ifdef WANT_BOARD_C
467 //fprintf(stderr, "rm of group %d\n", group_base(group));
468 for (int i = 0; i < board->clen; i++) {
469 if (unlikely(board->c[i] == group)) {
470 board->c[i] = board->c[--board->clen];
471 return;
472 }
473 }
474 fprintf(stderr, "rm of bad group %d\n", group_base(group));
475 assert(0);
476 #endif
477 }
478
479 static void
480 board_group_addlib(struct board *board, group_t group, coord_t coord)
481 {
482 if (DEBUGL(7)) {
483 fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n",
484 group_base(group), coord2sstr(group_base(group), board),
485 board_group_info(board, group).libs, coord2sstr(coord, board));
486 }
487
488 check_libs_consistency(board, group);
489
490 struct group *gi = &board_group_info(board, group);
491 if (gi->libs < GROUP_KEEP_LIBS) {
492 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
493 #if 0
494 /* Seems extra branch just slows it down */
495 if (!gi->lib[i])
496 break;
497 #endif
498 if (unlikely(gi->lib[i] == coord))
499 return;
500 }
501 if (gi->libs == 0)
502 board_capturable_add(board, group);
503 else if (gi->libs == 1)
504 board_capturable_rm(board, group);
505 gi->lib[gi->libs++] = coord;
506 }
507
508 check_libs_consistency(board, group);
509 }
510
511 static void
512 board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid)
513 {
514 /* Add extra liberty from the board to our liberty list. */
515 unsigned char watermark[board_size2(board) / 8];
516 memset(watermark, 0, sizeof(watermark));
517 #define watermark_get(c) (watermark[coord_raw(c) >> 3] & (1 << (coord_raw(c) & 7)))
518 #define watermark_set(c) watermark[coord_raw(c) >> 3] |= (1 << (coord_raw(c) & 7))
519
520 for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++)
521 watermark_set(gi->lib[i]);
522 watermark_set(avoid);
523
524 foreach_in_group(board, group) {
525 coord_t coord2 = c;
526 foreach_neighbor(board, coord2, {
527 if (board_at(board, c) + watermark_get(c) != S_NONE)
528 continue;
529 watermark_set(c);
530 gi->lib[gi->libs++] = c;
531 if (unlikely(gi->libs >= GROUP_KEEP_LIBS))
532 return;
533 } );
534 } foreach_in_group_end;
535 #undef watermark_get
536 #undef watermark_set
537 }
538
539 static void
540 board_group_rmlib(struct board *board, group_t group, coord_t coord)
541 {
542 if (DEBUGL(7)) {
543 fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n",
544 group_base(group), coord2sstr(group_base(group), board),
545 board_group_info(board, group).libs, coord2sstr(coord, board));
546 }
547
548 struct group *gi = &board_group_info(board, group);
549 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
550 #if 0
551 /* Seems extra branch just slows it down */
552 if (!gi->lib[i])
553 break;
554 #endif
555 if (likely(gi->lib[i] != coord))
556 continue;
557
558 gi->lib[i] = gi->lib[--gi->libs];
559 gi->lib[gi->libs] = 0;
560
561 check_libs_consistency(board, group);
562
563 /* Postpone refilling lib[] until we need to. */
564 assert(GROUP_REFILL_LIBS > 1);
565 if (gi->libs > GROUP_REFILL_LIBS)
566 return;
567 if (gi->libs == GROUP_REFILL_LIBS)
568 board_group_find_extra_libs(board, group, gi, coord);
569
570 if (gi->libs == 1)
571 board_capturable_add(board, group);
572 else if (gi->libs == 0)
573 board_capturable_rm(board, group);
574 return;
575 }
576
577 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
578 * can call this multiple times per coord. */
579 check_libs_consistency(board, group);
580 return;
581 }
582
583
584 /* This is a low-level routine that doesn't maintain consistency
585 * of all the board data structures. Use board_group_capture() from
586 * your code. */
587 static void
588 board_remove_stone(struct board *board, coord_t c)
589 {
590 enum stone color = board_at(board, c);
591 board_at(board, c) = S_NONE;
592 group_at(board, c) = 0;
593 board_hash_update(board, c, color);
594
595 /* Increase liberties of surrounding groups */
596 coord_t coord = c;
597 foreach_neighbor(board, coord, {
598 dec_neighbor_count_at(board, c, color);
599 group_t g = group_at(board, c);
600 if (g)
601 board_group_addlib(board, g, coord);
602 });
603
604 if (DEBUGL(6))
605 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
606 board->f[board->flen++] = coord_raw(c);
607 }
608
609
610 static void profiling_noinline
611 add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord)
612 {
613 foreach_neighbor(board, coord, {
614 if (board_at(board, c) == S_NONE)
615 board_group_addlib(board, group, c);
616 });
617
618 group_at(board, coord) = group;
619 groupnext_at(board, coord) = groupnext_at(board, prevstone);
620 groupnext_at(board, prevstone) = coord_raw(coord);
621
622 if (DEBUGL(8))
623 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
624 coord_x(prevstone, board), coord_y(prevstone, board),
625 coord_x(coord, board), coord_y(coord, board),
626 groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
627 group_base(group));
628 }
629
630 static void profiling_noinline
631 merge_groups(struct board *board, group_t group_to, group_t group_from)
632 {
633 if (DEBUGL(7))
634 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
635 group_base(group_from), group_base(group_to));
636
637 coord_t last_in_group;
638 foreach_in_group(board, group_from) {
639 last_in_group = c;
640 group_at(board, c) = group_to;
641 } foreach_in_group_end;
642 groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to));
643 groupnext_at(board, group_base(group_to)) = group_base(group_from);
644
645 struct group *gi_from = &board_group_info(board, group_from);
646 struct group *gi_to = &board_group_info(board, group_to);
647 if (gi_to->libs < GROUP_KEEP_LIBS) {
648 for (int i = 0; i < gi_from->libs; i++) {
649 for (int j = 0; j < gi_to->libs; j++)
650 if (gi_to->lib[j] == gi_from->lib[i])
651 goto next_from_lib;
652 if (gi_to->libs == 0)
653 board_capturable_add(board, group_to);
654 else if (gi_to->libs == 1)
655 board_capturable_rm(board, group_to);
656 gi_to->lib[gi_to->libs++] = gi_from->lib[i];
657 if (gi_to->libs >= GROUP_KEEP_LIBS)
658 break;
659 next_from_lib:;
660 }
661 }
662
663 if (gi_from->libs == 1)
664 board_capturable_rm(board, group_from);
665 memset(gi_from, 0, sizeof(struct group));
666
667 if (DEBUGL(7))
668 fprintf(stderr, "board_play_raw: merged group: %d\n",
669 group_base(group_to));
670 }
671
672 static group_t profiling_noinline
673 new_group(struct board *board, coord_t coord)
674 {
675 group_t group = coord_raw(coord);
676 struct group *gi = &board_group_info(board, group);
677 foreach_neighbor(board, coord, {
678 if (board_at(board, c) == S_NONE)
679 /* board_group_addlib is ridiculously expensive for us */
680 #if GROUP_KEEP_LIBS < 4
681 if (gi->libs < GROUP_KEEP_LIBS)
682 #endif
683 gi->lib[gi->libs++] = c;
684 });
685 if (gi->libs == 1)
686 board_capturable_add(board, group);
687 check_libs_consistency(board, group);
688
689 group_at(board, coord) = group;
690 groupnext_at(board, coord) = 0;
691
692 if (DEBUGL(8))
693 fprintf(stderr, "new_group: added %d,%d to group %d\n",
694 coord_x(coord, board), coord_y(coord, board),
695 group_base(group));
696
697 return group;
698 }
699
700 static inline group_t
701 play_one_neighbor(struct board *board,
702 coord_t coord, enum stone color, enum stone other_color,
703 coord_t c, group_t group)
704 {
705 enum stone ncolor = board_at(board, c);
706 group_t ngroup = group_at(board, c);
707
708 inc_neighbor_count_at(board, c, color);
709
710 if (!ngroup)
711 return group;
712
713 board_group_rmlib(board, ngroup, coord);
714 if (DEBUGL(7))
715 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
716 group_base(ngroup), ncolor, color, other_color);
717
718 if (ncolor == color && ngroup != group) {
719 if (!group) {
720 group = ngroup;
721 add_to_group(board, group, c, coord);
722 } else {
723 merge_groups(board, group, ngroup);
724 }
725 } else if (ncolor == other_color) {
726 if (DEBUGL(8)) {
727 struct group *gi = &board_group_info(board, ngroup);
728 fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board));
729 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
730 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
731 fprintf(stderr, "\n");
732 }
733 if (unlikely(board_group_captured(board, ngroup)))
734 board_group_capture(board, ngroup);
735 }
736 return group;
737 }
738
739 /* We played on a place with at least one liberty. We will become a member of
740 * some group for sure. */
741 static group_t profiling_noinline
742 board_play_outside(struct board *board, struct move *m, int f)
743 {
744 coord_t coord = m->coord;
745 enum stone color = m->color;
746 enum stone other_color = stone_other(color);
747 group_t group = 0;
748
749 board->f[f] = board->f[--board->flen];
750 if (DEBUGL(6))
751 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
752
753 foreach_neighbor(board, coord, {
754 group = play_one_neighbor(board, coord, color, other_color, c, group);
755 });
756
757 if (unlikely(!group))
758 group = new_group(board, coord);
759
760 board_at(board, coord) = color;
761 board->last_move2 = board->last_move;
762 board->last_move = *m;
763 board->moves++;
764 board_hash_update(board, coord, color);
765 board_symmetry_update(board, &board->symmetry, coord);
766 struct move ko = { pass, S_NONE };
767 board->ko = ko;
768
769 return group;
770 }
771
772 /* We played in an eye-like shape. Either we capture at least one of the eye
773 * sides in the process of playing, or return -1. */
774 static int profiling_noinline
775 board_play_in_eye(struct board *board, struct move *m, int f)
776 {
777 coord_t coord = m->coord;
778 enum stone color = m->color;
779 /* Check ko: Capture at a position of ko capture one move ago */
780 if (unlikely(color == board->ko.color && coord_eq(coord, board->ko.coord))) {
781 if (DEBUGL(5))
782 fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
783 return -1;
784 } else if (DEBUGL(6)) {
785 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
786 color, coord_x(coord, board), coord_y(coord, board),
787 board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
788 }
789
790 struct move ko = { pass, S_NONE };
791
792 int captured_groups = 0;
793
794 foreach_neighbor(board, coord, {
795 group_t g = group_at(board, c);
796 if (DEBUGL(7))
797 fprintf(stderr, "board_check: group %d has %d libs\n",
798 g, board_group_info(board, g).libs);
799 captured_groups += (board_group_info(board, g).libs == 1);
800 });
801
802 if (likely(captured_groups == 0)) {
803 if (DEBUGL(5)) {
804 if (DEBUGL(6))
805 board_print(board, stderr);
806 fprintf(stderr, "board_check: one-stone suicide\n");
807 }
808
809 return -1;
810 }
811
812 board->f[f] = board->f[--board->flen];
813 if (DEBUGL(6))
814 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
815
816 foreach_neighbor(board, coord, {
817 inc_neighbor_count_at(board, c, color);
818
819 group_t group = group_at(board, c);
820 if (!group)
821 continue;
822
823 board_group_rmlib(board, group, coord);
824 if (DEBUGL(7))
825 fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
826 group_base(group));
827
828 if (board_group_captured(board, group)) {
829 if (board_group_capture(board, group) == 1) {
830 /* If we captured multiple groups at once,
831 * we can't be fighting ko so we don't need
832 * to check for that. */
833 ko.color = stone_other(color);
834 ko.coord = c;
835 board->last_ko = ko;
836 board->last_ko_age = board->moves;
837 if (DEBUGL(5))
838 fprintf(stderr, "guarding ko at %d,%s\n", ko.color, coord2sstr(ko.coord, board));
839 }
840 }
841 });
842
843 board_at(board, coord) = color;
844
845 board->last_move2 = board->last_move;
846 board->last_move = *m;
847 board->moves++;
848 board_hash_update(board, coord, color);
849 board_hash_commit(board);
850 board_symmetry_update(board, &board->symmetry, coord);
851 board->ko = ko;
852
853 return !!new_group(board, coord);
854 }
855
856 static int __attribute__((flatten))
857 board_play_f(struct board *board, struct move *m, int f)
858 {
859 if (DEBUGL(7)) {
860 fprintf(stderr, "board_play(): ---- Playing %d,%d\n", coord_x(m->coord, board), coord_y(m->coord, board));
861 }
862 if (likely(!board_is_eyelike(board, &m->coord, stone_other(m->color)))) {
863 /* NOT playing in an eye. Thus this move has to succeed. (This
864 * is thanks to New Zealand rules. Otherwise, multi-stone
865 * suicide might fail.) */
866 group_t group = board_play_outside(board, m, f);
867 if (unlikely(board_group_captured(board, group))) {
868 board_group_capture(board, group);
869 }
870 board_hash_commit(board);
871 return 0;
872 } else {
873 return board_play_in_eye(board, m, f);
874 }
875 }
876
877 int
878 board_play(struct board *board, struct move *m)
879 {
880 if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
881 board->last_move2 = board->last_move;
882 board->last_move = *m;
883 return 0;
884 }
885
886 int f;
887 for (f = 0; f < board->flen; f++)
888 if (board->f[f] == coord_raw(m->coord))
889 return board_play_f(board, m, f);
890
891 if (DEBUGL(7))
892 fprintf(stderr, "board_check: stone exists\n");
893 return -1;
894 }
895
896
897 static inline bool
898 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f, ppr_permit permit, void *permit_data)
899 {
900 coord_raw(*coord) = b->f[f];
901 if (unlikely(is_pass(*coord)))
902 return random_pass;
903 struct move m = { *coord, color };
904 if (DEBUGL(6))
905 fprintf(stderr, "trying random move %d: %d,%d\n", f, coord_x(*coord, b), coord_y(*coord, b));
906 return (likely(!board_is_one_point_eye(b, coord, color)) /* bad idea to play into one, usually */
907 && board_is_valid_move(b, &m)
908 && (!permit || permit(permit_data, b, &m))
909 && likely(board_play_f(b, &m, f) >= 0));
910 }
911
912 void
913 board_play_random(struct board *b, enum stone color, coord_t *coord, ppr_permit permit, void *permit_data)
914 {
915 int base = fast_random(b->flen);
916 coord_pos(*coord, base, b);
917 if (likely(board_try_random_move(b, color, coord, base, permit, permit_data)))
918 return;
919
920 int f;
921 for (f = base + 1; f < b->flen; f++)
922 if (board_try_random_move(b, color, coord, f, permit, permit_data))
923 return;
924 for (f = 0; f < base; f++)
925 if (board_try_random_move(b, color, coord, f, permit, permit_data))
926 return;
927
928 *coord = pass;
929 }
930
931
932 bool
933 board_is_false_eyelike(struct board *board, coord_t *coord, enum stone eye_color)
934 {
935 enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
936
937 /* XXX: We attempt false eye detection but we will yield false
938 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
939
940 foreach_diag_neighbor(board, *coord) {
941 color_diag_libs[(enum stone) board_at(board, c)]++;
942 } foreach_diag_neighbor_end;
943 /* For false eye, we need two enemy stones diagonally in the
944 * middle of the board, or just one enemy stone at the edge
945 * or in the corner. */
946 color_diag_libs[stone_other(eye_color)] += !!color_diag_libs[S_OFFBOARD];
947 return color_diag_libs[stone_other(eye_color)] >= 2;
948 }
949
950 bool
951 board_is_one_point_eye(struct board *board, coord_t *coord, enum stone eye_color)
952 {
953 return board_is_eyelike(board, coord, eye_color)
954 && !board_is_false_eyelike(board, coord, eye_color);
955 }
956
957 enum stone
958 board_get_one_point_eye(struct board *board, coord_t *coord)
959 {
960 if (board_is_one_point_eye(board, coord, S_WHITE))
961 return S_WHITE;
962 else if (board_is_one_point_eye(board, coord, S_BLACK))
963 return S_BLACK;
964 else
965 return S_NONE;
966 }
967
968
969 int profiling_noinline
970 board_group_capture(struct board *board, group_t group)
971 {
972 int stones = 0;
973
974 foreach_in_group(board, group) {
975 board->captures[stone_other(board_at(board, c))]++;
976 board_remove_stone(board, c);
977 stones++;
978 } foreach_in_group_end;
979
980 if (board_group_info(board, group).libs == 1)
981 board_capturable_rm(board, group);
982 memset(&board_group_info(board, group), 0, sizeof(struct group));
983
984 return stones;
985 }
986
987
988 float
989 board_fast_score(struct board *board)
990 {
991 int scores[S_MAX];
992 memset(scores, 0, sizeof(scores));
993
994 foreach_point(board) {
995 enum stone color = board_at(board, c);
996 if (color == S_NONE)
997 color = board_get_one_point_eye(board, &c);
998 scores[color]++;
999 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1000 } foreach_point_end;
1001
1002 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
1003 }
1004
1005 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1006
1007 /* One flood-fill iteration; returns true if next iteration
1008 * is required. */
1009 static bool
1010 board_tromp_taylor_iter(struct board *board, int *ownermap)
1011 {
1012 bool needs_update = false;
1013 foreach_point(board) {
1014 /* Ignore occupied and already-dame positions. */
1015 if (board_at(board, c) != S_NONE || ownermap[c] == 3)
1016 continue;
1017 /* Count neighbors. */
1018 int nei[4] = {0};
1019 foreach_neighbor(board, c, {
1020 nei[ownermap[c]]++;
1021 });
1022 /* If we have neighbors of both colors, or dame,
1023 * we are dame too. */
1024 if ((nei[1] && nei[2]) || nei[3]) {
1025 ownermap[c] = 3;
1026 /* Speed up the propagation. */
1027 foreach_neighbor(board, c, {
1028 if (board_at(board, c) == S_NONE)
1029 ownermap[c] = 3;
1030 });
1031 needs_update = true;
1032 continue;
1033 }
1034 /* If we have neighbors of one color, we are owned
1035 * by that color, too. */
1036 if (!ownermap[c] && (nei[1] || nei[2])) {
1037 int newowner = nei[1] ? 1 : 2;
1038 ownermap[c] = newowner;
1039 /* Speed up the propagation. */
1040 foreach_neighbor(board, c, {
1041 if (board_at(board, c) == S_NONE && !ownermap[c])
1042 ownermap[c] = newowner;
1043 });
1044 needs_update = true;
1045 continue;
1046 }
1047 } foreach_point_end;
1048 return needs_update;
1049 }
1050
1051 /* Tromp-Taylor Counting */
1052 float
1053 board_official_score(struct board *board)
1054 {
1055
1056 /* A point P, not colored C, is said to reach C, if there is a path of
1057 * (vertically or horizontally) adjacent points of P's color from P to
1058 * a point of color C.
1059 *
1060 * A player's score is the number of points of her color, plus the
1061 * number of empty points that reach only her color. */
1062
1063 int ownermap[board_size2(board)];
1064 int s[4] = {0};
1065 foreach_point(board) {
1066 int o[4] = {0, 1, 2, 0};
1067 ownermap[c] = o[board_at(board, c)];
1068 s[board_at(board, c)]++;
1069 } foreach_point_end;
1070
1071 /* We need to special-case empty board. */
1072 if (!s[S_BLACK] && !s[S_WHITE])
1073 return board->komi + board->handicap;
1074
1075 while (board_tromp_taylor_iter(board, ownermap))
1076 /* Flood-fill... */;
1077
1078 int scores[S_MAX];
1079 memset(scores, 0, sizeof(scores));
1080
1081 foreach_point(board) {
1082 assert(board_at(board, c) == S_OFFBOARD || ownermap[c] != 0);
1083 if (ownermap[c] == 3)
1084 continue;
1085 scores[ownermap[c]]++;
1086 } foreach_point_end;
1087
1088 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
1089 }