12 int board_group_capture(struct board
*board
, group_t group
);
14 bool random_pass
= false;
18 #define profiling_noinline __attribute__((noinline))
20 #define profiling_noinline
23 #define gi_granularity 4
24 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
28 board_setup(struct board
*b
)
30 memset(b
, 0, sizeof(*b
));
32 struct move m
= { pass
, S_NONE
};
33 b
->last_move
= b
->last_move2
= b
->last_ko
= b
->ko
= m
;
39 struct board
*b
= malloc(sizeof(struct board
));
50 board_copy(struct board
*b2
, struct board
*b1
)
52 memcpy(b2
, b1
, sizeof(struct board
));
54 int bsize
= board_size2(b2
) * sizeof(*b2
->b
);
55 int gsize
= board_size2(b2
) * sizeof(*b2
->g
);
56 int fsize
= board_size2(b2
) * sizeof(*b2
->f
);
57 int nsize
= board_size2(b2
) * sizeof(*b2
->n
);
58 int psize
= board_size2(b2
) * sizeof(*b2
->p
);
59 int hsize
= board_size2(b2
) * 2 * sizeof(*b2
->h
);
60 int gisize
= board_size2(b2
) * sizeof(*b2
->gi
);
62 int csize
= board_size2(b2
) * sizeof(*b2
->c
);
66 void *x
= malloc(bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
);
67 memcpy(x
, b1
->b
, bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
);
68 b2
->b
= x
; x
+= bsize
;
69 b2
->g
= x
; x
+= gsize
;
70 b2
->f
= x
; x
+= fsize
;
71 b2
->p
= x
; x
+= psize
;
72 b2
->n
= x
; x
+= nsize
;
73 b2
->h
= x
; x
+= hsize
;
74 b2
->gi
= x
; x
+= gisize
;
76 b2
->c
= x
; x
+= csize
;
83 board_done_noalloc(struct board
*board
)
85 if (board
->b
) free(board
->b
);
89 board_done(struct board
*board
)
91 board_done_noalloc(board
);
96 board_resize(struct board
*board
, int size
)
99 assert(board_size(board
) == size
+ 2);
101 board_size(board
) = size
+ 2 /* S_OFFBOARD margin */;
102 board_size2(board
) = board_size(board
) * board_size(board
);
107 int bsize
= board_size2(board
) * sizeof(*board
->b
);
108 int gsize
= board_size2(board
) * sizeof(*board
->g
);
109 int fsize
= board_size2(board
) * sizeof(*board
->f
);
110 int nsize
= board_size2(board
) * sizeof(*board
->n
);
111 int psize
= board_size2(board
) * sizeof(*board
->p
);
112 int hsize
= board_size2(board
) * 2 * sizeof(*board
->h
);
113 int gisize
= board_size2(board
) * sizeof(*board
->gi
);
115 int csize
= board_size2(board
) * sizeof(*board
->c
);
119 void *x
= malloc(bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
);
120 memset(x
, 0, bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
);
121 board
->b
= x
; x
+= bsize
;
122 board
->g
= x
; x
+= gsize
;
123 board
->f
= x
; x
+= fsize
;
124 board
->p
= x
; x
+= psize
;
125 board
->n
= x
; x
+= nsize
;
126 board
->h
= x
; x
+= hsize
;
127 board
->gi
= x
; x
+= gisize
;
129 board
->c
= x
; x
+= csize
;
134 board_clear(struct board
*board
)
136 int size
= board_size(board
);
137 float komi
= board
->komi
;
139 board_done_noalloc(board
);
141 board_resize(board
, size
- 2 /* S_OFFBOARD margin */);
145 /* Setup initial symmetry */
146 board
->symmetry
.d
= 1;
147 board
->symmetry
.x1
= board
->symmetry
.y1
= board_size(board
) / 2;
148 board
->symmetry
.x2
= board
->symmetry
.y2
= board_size(board
) - 1;
149 board
->symmetry
.type
= SYM_FULL
;
151 /* Draw the offboard margin */
152 int top_row
= board_size2(board
) - board_size(board
);
154 for (i
= 0; i
< board_size(board
); i
++)
155 board
->b
[i
] = board
->b
[top_row
+ i
] = S_OFFBOARD
;
156 for (i
= 0; i
<= top_row
; i
+= board_size(board
))
157 board
->b
[i
] = board
->b
[board_size(board
) - 1 + i
] = S_OFFBOARD
;
159 foreach_point(board
) {
161 if (board_at(board
, coord
) == S_OFFBOARD
)
163 foreach_neighbor(board
, c
, {
164 inc_neighbor_count_at(board
, coord
, board_at(board
, c
));
168 /* First, pass is always a free position. */
169 board
->f
[board
->flen
++] = coord_raw(pass
);
170 /* All positions are free! Except the margin. */
171 for (i
= board_size(board
); i
< (board_size(board
) - 1) * board_size(board
); i
++)
172 if (i
% board_size(board
) != 0 && i
% board_size(board
) != board_size(board
) - 1)
173 board
->f
[board
->flen
++] = i
;
175 /* Initialize zobrist hashtable. */
176 foreach_point(board
) {
177 int max
= (sizeof(hash_t
) << history_hash_bits
);
178 /* fast_random() is 16-bit only */
179 board
->h
[coord_raw(c
) * 2] = ((hash_t
) fast_random(max
))
180 | ((hash_t
) fast_random(max
) << 16)
181 | ((hash_t
) fast_random(max
) << 32)
182 | ((hash_t
) fast_random(max
) << 48);
183 if (!board
->h
[coord_raw(c
) * 2])
184 /* Would be kinda "oops". */
185 board
->h
[coord_raw(c
) * 2] = 1;
186 /* And once again for white */
187 board
->h
[coord_raw(c
) * 2 + 1] = ((hash_t
) fast_random(max
))
188 | ((hash_t
) fast_random(max
) << 16)
189 | ((hash_t
) fast_random(max
) << 32)
190 | ((hash_t
) fast_random(max
) << 48);
191 if (!board
->h
[coord_raw(c
) * 2 + 1])
192 board
->h
[coord_raw(c
) * 2 + 1] = 1;
198 board_print_top(struct board
*board
, FILE *f
, int c
)
200 for (int i
= 0; i
< c
; i
++) {
201 char asdf
[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
203 for (int x
= 1; x
< board_size(board
) - 1; x
++)
204 fprintf(f
, "%c ", asdf
[x
- 1]);
208 for (int i
= 0; i
< c
; i
++) {
210 for (int x
= 1; x
< board_size(board
) - 1; x
++)
218 board_print_bottom(struct board
*board
, FILE *f
, int c
)
220 for (int i
= 0; i
< c
; i
++) {
222 for (int x
= 1; x
< board_size(board
) - 1; x
++)
230 board_print_row(struct board
*board
, int y
, FILE *f
, board_cprint cprint
)
232 fprintf(f
, " %2d | ", y
);
233 for (int x
= 1; x
< board_size(board
) - 1; x
++) {
234 if (coord_x(board
->last_move
.coord
, board
) == x
&& coord_y(board
->last_move
.coord
, board
) == y
)
235 fprintf(f
, "%c)", stone2char(board_atxy(board
, x
, y
)));
237 fprintf(f
, "%c ", stone2char(board_atxy(board
, x
, y
)));
241 fprintf(f
, " %2d | ", y
);
242 for (int x
= 1; x
< board_size(board
) - 1; x
++) {
243 cprint(board
, coord_xy(board
, x
, y
), f
);
251 board_print_custom(struct board
*board
, FILE *f
, board_cprint cprint
)
253 fprintf(f
, "Move: % 3d Komi: %2.1f Handicap: %d Captures B: %d W: %d\n",
254 board
->moves
, board
->komi
, board
->handicap
,
255 board
->captures
[S_BLACK
], board
->captures
[S_WHITE
]);
256 board_print_top(board
, f
, 1 + !!cprint
);
257 for (int y
= board_size(board
) - 2; y
>= 1; y
--)
258 board_print_row(board
, y
, f
, cprint
);
259 board_print_bottom(board
, f
, 1 + !!cprint
);
264 cprint_group(struct board
*board
, coord_t c
, FILE *f
)
266 fprintf(f
, "%d ", group_base(group_at(board
, c
)));
270 board_print(struct board
*board
, FILE *f
)
272 board_print_custom(board
, f
, DEBUGL(6) ? cprint_group
: NULL
);
276 /* Update board hash with given coordinate. */
277 static void profiling_noinline
278 board_hash_update(struct board
*board
, coord_t coord
, enum stone color
)
280 board
->hash
^= hash_at(board
, coord
, color
);
282 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
);
285 /* Commit current board hash to history. */
286 static void profiling_noinline
287 board_hash_commit(struct board
*board
)
290 fprintf(stderr
, "board_hash_commit %"PRIhash
"\n", board
->hash
);
291 if (likely(board
->history_hash
[board
->hash
& history_hash_mask
]) == 0) {
292 board
->history_hash
[board
->hash
& history_hash_mask
] = board
->hash
;
294 hash_t i
= board
->hash
;
295 while (board
->history_hash
[i
& history_hash_mask
]) {
296 if (board
->history_hash
[i
& history_hash_mask
] == board
->hash
) {
298 fprintf(stderr
, "SUPERKO VIOLATION noted at %d,%d\n",
299 coord_x(board
->last_move
.coord
, board
), coord_y(board
->last_move
.coord
, board
));
300 board
->superko_violation
= true;
303 i
= history_hash_next(i
);
305 board
->history_hash
[i
& history_hash_mask
] = board
->hash
;
311 board_symmetry_update(struct board
*b
, struct board_symmetry
*symmetry
, coord_t c
)
313 if (likely(symmetry
->type
== SYM_NONE
)) {
314 /* Fully degenerated already. We do not support detection
315 * of restoring of symmetry, assuming that this is too rare
316 * a case to handle. */
320 int x
= coord_x(c
, b
), y
= coord_y(c
, b
), t
= board_size(b
) / 2;
321 int dx
= board_size(b
) - 1 - x
; /* for SYM_DOWN */
323 fprintf(stderr
, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
324 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
325 symmetry
->d
, symmetry
->type
, x
, y
);
328 switch (symmetry
->type
) {
330 if (x
== t
&& y
== t
) {
331 /* Tengen keeps full symmetry. */
334 /* New symmetry now? */
336 symmetry
->type
= SYM_DIAG_UP
;
337 symmetry
->x1
= symmetry
->y1
= 1;
338 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
340 } else if (dx
== y
) {
341 symmetry
->type
= SYM_DIAG_DOWN
;
342 symmetry
->x1
= symmetry
->y1
= 1;
343 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
346 symmetry
->type
= SYM_HORIZ
;
348 symmetry
->y2
= board_size(b
) - 1;
351 symmetry
->type
= SYM_VERT
;
353 symmetry
->x2
= board_size(b
) - 1;
357 symmetry
->type
= SYM_NONE
;
358 symmetry
->x1
= symmetry
->y1
= 1;
359 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
385 fprintf(stderr
, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
386 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
387 symmetry
->d
, symmetry
->type
);
394 board_handicap_stone(struct board
*board
, int x
, int y
, FILE *f
)
397 m
.color
= S_BLACK
; m
.coord
= coord_xy(board
, x
, y
);
399 board_play(board
, &m
);
400 /* Simulate white passing; otherwise, UCT search can get confused since
401 * tree depth parity won't match the color to move. */
404 char *str
= coord2str(m
.coord
, board
);
406 fprintf(stderr
, "choosing handicap %s (%d,%d)\n", str
, x
, y
);
407 fprintf(f
, "%s ", str
);
412 board_handicap(struct board
*board
, int stones
, FILE *f
)
414 int margin
= 3 + (board_size(board
) >= 13);
416 int mid
= board_size(board
) / 2;
417 int max
= board_size(board
) - 1 - margin
;
418 const int places
[][2] = {
419 { min
, min
}, { max
, max
}, { max
, min
}, { min
, max
},
420 { min
, mid
}, { max
, mid
},
421 { mid
, min
}, { mid
, max
},
425 board
->handicap
= stones
;
427 if (stones
== 5 || stones
== 7) {
428 board_handicap_stone(board
, mid
, mid
, f
);
433 for (i
= 0; i
< stones
; i
++)
434 board_handicap_stone(board
, places
[i
][0], places
[i
][1], f
);
438 static void __attribute__((noinline
))
439 check_libs_consistency(struct board
*board
, group_t g
)
443 struct group
*gi
= &board_group_info(board
, g
);
444 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
445 if (gi
->lib
[i
] && board_at(board
, gi
->lib
[i
]) != S_NONE
) {
446 fprintf(stderr
, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi
->lib
[i
], board
), g
, coord2sstr(group_base(g
), board
));
453 board_capturable_add(struct board
*board
, group_t group
)
456 //fprintf(stderr, "add of group %d (%d)\n", group_base(group), board->clen);
458 assert(board
->clen
< board_size2(board
));
459 board
->c
[board
->clen
++] = group
;
463 board_capturable_rm(struct board
*board
, group_t group
)
466 //fprintf(stderr, "rm of group %d\n", group_base(group));
467 for (int i
= 0; i
< board
->clen
; i
++) {
468 if (unlikely(board
->c
[i
] == group
)) {
469 board
->c
[i
] = board
->c
[--board
->clen
];
473 fprintf(stderr
, "rm of bad group %d\n", group_base(group
));
479 board_group_addlib(struct board
*board
, group_t group
, coord_t coord
)
482 fprintf(stderr
, "Group %d[%s] %d: Adding liberty %s\n",
483 group_base(group
), coord2sstr(group_base(group
), board
),
484 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
487 check_libs_consistency(board
, group
);
489 struct group
*gi
= &board_group_info(board
, group
);
490 if (gi
->libs
< GROUP_KEEP_LIBS
) {
491 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
493 /* Seems extra branch just slows it down */
497 if (unlikely(gi
->lib
[i
] == coord
))
501 board_capturable_add(board
, group
);
502 else if (gi
->libs
== 1)
503 board_capturable_rm(board
, group
);
504 gi
->lib
[gi
->libs
++] = coord
;
507 check_libs_consistency(board
, group
);
511 board_group_find_extra_libs(struct board
*board
, group_t group
, struct group
*gi
, coord_t avoid
)
513 /* Add extra liberty from the board to our liberty list. */
514 unsigned char watermark
[board_size2(board
) / 8];
515 memset(watermark
, 0, sizeof(watermark
));
516 #define watermark_get(c) (watermark[coord_raw(c) >> 3] & (1 << (coord_raw(c) & 7)))
517 #define watermark_set(c) watermark[coord_raw(c) >> 3] |= (1 << (coord_raw(c) & 7))
519 for (int i
= 0; i
< GROUP_KEEP_LIBS
- 1; i
++)
520 watermark_set(gi
->lib
[i
]);
521 watermark_set(avoid
);
523 foreach_in_group(board
, group
) {
525 foreach_neighbor(board
, coord2
, {
526 if (board_at(board
, c
) + watermark_get(c
) != S_NONE
)
529 gi
->lib
[gi
->libs
++] = c
;
530 if (unlikely(gi
->libs
>= GROUP_KEEP_LIBS
))
533 } foreach_in_group_end
;
539 board_group_rmlib(struct board
*board
, group_t group
, coord_t coord
)
542 fprintf(stderr
, "Group %d[%s] %d: Removing liberty %s\n",
543 group_base(group
), coord2sstr(group_base(group
), board
),
544 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
547 struct group
*gi
= &board_group_info(board
, group
);
548 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
550 /* Seems extra branch just slows it down */
554 if (likely(gi
->lib
[i
] != coord
))
557 gi
->lib
[i
] = gi
->lib
[--gi
->libs
];
558 gi
->lib
[gi
->libs
] = 0;
560 check_libs_consistency(board
, group
);
562 /* Postpone refilling lib[] until we need to. */
563 assert(GROUP_REFILL_LIBS
> 1);
564 if (gi
->libs
> GROUP_REFILL_LIBS
)
566 if (gi
->libs
== GROUP_REFILL_LIBS
)
567 board_group_find_extra_libs(board
, group
, gi
, coord
);
570 board_capturable_add(board
, group
);
571 else if (gi
->libs
== 0)
572 board_capturable_rm(board
, group
);
576 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
577 * can call this multiple times per coord. */
578 check_libs_consistency(board
, group
);
583 /* This is a low-level routine that doesn't maintain consistency
584 * of all the board data structures. Use board_group_capture() from
587 board_remove_stone(struct board
*board
, coord_t c
)
589 enum stone color
= board_at(board
, c
);
590 board_at(board
, c
) = S_NONE
;
591 group_at(board
, c
) = 0;
592 board_hash_update(board
, c
, color
);
594 /* Increase liberties of surrounding groups */
596 foreach_neighbor(board
, coord
, {
597 dec_neighbor_count_at(board
, c
, color
);
598 group_t g
= group_at(board
, c
);
600 board_group_addlib(board
, g
, coord
);
604 fprintf(stderr
, "pushing free move [%d]: %d,%d\n", board
->flen
, coord_x(c
, board
), coord_y(c
, board
));
605 board
->f
[board
->flen
++] = coord_raw(c
);
609 static void profiling_noinline
610 add_to_group(struct board
*board
, group_t group
, coord_t prevstone
, coord_t coord
)
612 foreach_neighbor(board
, coord
, {
613 if (board_at(board
, c
) == S_NONE
)
614 board_group_addlib(board
, group
, c
);
617 group_at(board
, coord
) = group
;
618 groupnext_at(board
, coord
) = groupnext_at(board
, prevstone
);
619 groupnext_at(board
, prevstone
) = coord_raw(coord
);
622 fprintf(stderr
, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
623 coord_x(prevstone
, board
), coord_y(prevstone
, board
),
624 coord_x(coord
, board
), coord_y(coord
, board
),
625 groupnext_at(board
, coord
) % board_size(board
), groupnext_at(board
, coord
) / board_size(board
),
629 static void profiling_noinline
630 merge_groups(struct board
*board
, group_t group_to
, group_t group_from
)
633 fprintf(stderr
, "board_play_raw: merging groups %d -> %d\n",
634 group_base(group_from
), group_base(group_to
));
636 coord_t last_in_group
;
637 foreach_in_group(board
, group_from
) {
639 group_at(board
, c
) = group_to
;
640 } foreach_in_group_end
;
641 groupnext_at(board
, last_in_group
) = groupnext_at(board
, group_base(group_to
));
642 groupnext_at(board
, group_base(group_to
)) = group_base(group_from
);
644 struct group
*gi_from
= &board_group_info(board
, group_from
);
645 struct group
*gi_to
= &board_group_info(board
, group_to
);
646 if (gi_to
->libs
< GROUP_KEEP_LIBS
) {
647 for (int i
= 0; i
< gi_from
->libs
; i
++) {
648 for (int j
= 0; j
< gi_to
->libs
; j
++)
649 if (gi_to
->lib
[j
] == gi_from
->lib
[i
])
651 if (gi_to
->libs
== 0)
652 board_capturable_add(board
, group_to
);
653 else if (gi_to
->libs
== 1)
654 board_capturable_rm(board
, group_to
);
655 gi_to
->lib
[gi_to
->libs
++] = gi_from
->lib
[i
];
656 if (gi_to
->libs
>= GROUP_KEEP_LIBS
)
662 if (gi_from
->libs
== 1)
663 board_capturable_rm(board
, group_from
);
664 memset(gi_from
, 0, sizeof(struct group
));
667 fprintf(stderr
, "board_play_raw: merged group: %d\n",
668 group_base(group_to
));
671 static group_t profiling_noinline
672 new_group(struct board
*board
, coord_t coord
)
674 group_t group
= coord_raw(coord
);
675 struct group
*gi
= &board_group_info(board
, group
);
676 foreach_neighbor(board
, coord
, {
677 if (board_at(board
, c
) == S_NONE
)
678 /* board_group_addlib is ridiculously expensive for us */
679 #if GROUP_KEEP_LIBS < 4
680 if (gi
->libs
< GROUP_KEEP_LIBS
)
682 gi
->lib
[gi
->libs
++] = c
;
685 board_capturable_add(board
, group
);
686 check_libs_consistency(board
, group
);
688 group_at(board
, coord
) = group
;
689 groupnext_at(board
, coord
) = 0;
692 fprintf(stderr
, "new_group: added %d,%d to group %d\n",
693 coord_x(coord
, board
), coord_y(coord
, board
),
699 static inline group_t
700 play_one_neighbor(struct board
*board
,
701 coord_t coord
, enum stone color
, enum stone other_color
,
702 coord_t c
, group_t group
)
704 enum stone ncolor
= board_at(board
, c
);
705 group_t ngroup
= group_at(board
, c
);
707 inc_neighbor_count_at(board
, c
, color
);
712 board_group_rmlib(board
, ngroup
, coord
);
714 fprintf(stderr
, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
715 group_base(ngroup
), ncolor
, color
, other_color
);
717 if (ncolor
== color
&& ngroup
!= group
) {
720 add_to_group(board
, group
, c
, coord
);
722 merge_groups(board
, group
, ngroup
);
724 } else if (ncolor
== other_color
) {
726 struct group
*gi
= &board_group_info(board
, ngroup
);
727 fprintf(stderr
, "testing captured group %d[%s]: ", group_base(ngroup
), coord2sstr(group_base(ngroup
), board
));
728 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
729 fprintf(stderr
, "%s ", coord2sstr(gi
->lib
[i
], board
));
730 fprintf(stderr
, "\n");
732 if (unlikely(board_group_captured(board
, ngroup
)))
733 board_group_capture(board
, ngroup
);
738 /* We played on a place with at least one liberty. We will become a member of
739 * some group for sure. */
740 static group_t profiling_noinline
741 board_play_outside(struct board
*board
, struct move
*m
, int f
)
743 coord_t coord
= m
->coord
;
744 enum stone color
= m
->color
;
745 enum stone other_color
= stone_other(color
);
748 board
->f
[f
] = board
->f
[--board
->flen
];
750 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
752 foreach_neighbor(board
, coord
, {
753 group
= play_one_neighbor(board
, coord
, color
, other_color
, c
, group
);
756 if (unlikely(!group
))
757 group
= new_group(board
, coord
);
759 board_at(board
, coord
) = color
;
760 board
->last_move2
= board
->last_move
;
761 board
->last_move
= *m
;
763 board_hash_update(board
, coord
, color
);
764 board_symmetry_update(board
, &board
->symmetry
, coord
);
765 struct move ko
= { pass
, S_NONE
};
771 /* We played in an eye-like shape. Either we capture at least one of the eye
772 * sides in the process of playing, or return -1. */
773 static int profiling_noinline
774 board_play_in_eye(struct board
*board
, struct move
*m
, int f
)
776 coord_t coord
= m
->coord
;
777 enum stone color
= m
->color
;
778 /* Check ko: Capture at a position of ko capture one move ago */
779 if (unlikely(color
== board
->ko
.color
&& coord_eq(coord
, board
->ko
.coord
))) {
781 fprintf(stderr
, "board_check: ko at %d,%d color %d\n", coord_x(coord
, board
), coord_y(coord
, board
), color
);
783 } else if (DEBUGL(6)) {
784 fprintf(stderr
, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
785 color
, coord_x(coord
, board
), coord_y(coord
, board
),
786 board
->ko
.color
, coord_x(board
->ko
.coord
, board
), coord_y(board
->ko
.coord
, board
));
789 struct move ko
= { pass
, S_NONE
};
791 int captured_groups
= 0;
793 foreach_neighbor(board
, coord
, {
794 group_t g
= group_at(board
, c
);
796 fprintf(stderr
, "board_check: group %d has %d libs\n",
797 g
, board_group_info(board
, g
).libs
);
798 captured_groups
+= (board_group_info(board
, g
).libs
== 1);
801 if (likely(captured_groups
== 0)) {
804 board_print(board
, stderr
);
805 fprintf(stderr
, "board_check: one-stone suicide\n");
811 board
->f
[f
] = board
->f
[--board
->flen
];
813 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
815 foreach_neighbor(board
, coord
, {
816 inc_neighbor_count_at(board
, c
, color
);
818 group_t group
= group_at(board
, c
);
822 board_group_rmlib(board
, group
, coord
);
824 fprintf(stderr
, "board_play_raw: reducing libs for group %d\n",
827 if (board_group_captured(board
, group
)) {
828 if (board_group_capture(board
, group
) == 1) {
829 /* If we captured multiple groups at once,
830 * we can't be fighting ko so we don't need
831 * to check for that. */
832 ko
.color
= stone_other(color
);
835 board
->last_ko_age
= board
->moves
;
837 fprintf(stderr
, "guarding ko at %d,%s\n", ko
.color
, coord2sstr(ko
.coord
, board
));
842 board_at(board
, coord
) = color
;
844 board
->last_move2
= board
->last_move
;
845 board
->last_move
= *m
;
847 board_hash_update(board
, coord
, color
);
848 board_hash_commit(board
);
849 board_symmetry_update(board
, &board
->symmetry
, coord
);
852 return !!new_group(board
, coord
);
855 static int __attribute__((flatten
))
856 board_play_f(struct board
*board
, struct move
*m
, int f
)
859 fprintf(stderr
, "board_play(): ---- Playing %d,%d\n", coord_x(m
->coord
, board
), coord_y(m
->coord
, board
));
861 if (likely(!board_is_eyelike(board
, &m
->coord
, stone_other(m
->color
)))) {
862 /* NOT playing in an eye. Thus this move has to succeed. (This
863 * is thanks to New Zealand rules. Otherwise, multi-stone
864 * suicide might fail.) */
865 group_t group
= board_play_outside(board
, m
, f
);
866 if (unlikely(board_group_captured(board
, group
))) {
867 board_group_capture(board
, group
);
869 board_hash_commit(board
);
872 return board_play_in_eye(board
, m
, f
);
877 board_play(struct board
*board
, struct move
*m
)
879 if (unlikely(is_pass(m
->coord
) || is_resign(m
->coord
))) {
880 board
->last_move2
= board
->last_move
;
881 board
->last_move
= *m
;
886 for (f
= 0; f
< board
->flen
; f
++)
887 if (board
->f
[f
] == coord_raw(m
->coord
))
888 return board_play_f(board
, m
, f
);
891 fprintf(stderr
, "board_check: stone exists\n");
897 board_try_random_move(struct board
*b
, enum stone color
, coord_t
*coord
, int f
, ppr_permit permit
, void *permit_data
)
899 coord_raw(*coord
) = b
->f
[f
];
900 if (unlikely(is_pass(*coord
)))
902 struct move m
= { *coord
, color
};
904 fprintf(stderr
, "trying random move %d: %d,%d\n", f
, coord_x(*coord
, b
), coord_y(*coord
, b
));
905 return (likely(!board_is_one_point_eye(b
, coord
, color
)) /* bad idea to play into one, usually */
906 && board_is_valid_move(b
, &m
)
907 && (!permit
|| permit(permit_data
, b
, &m
))
908 && likely(board_play_f(b
, &m
, f
) >= 0));
912 board_play_random(struct board
*b
, enum stone color
, coord_t
*coord
, ppr_permit permit
, void *permit_data
)
914 int base
= fast_random(b
->flen
);
915 coord_pos(*coord
, base
, b
);
916 if (likely(board_try_random_move(b
, color
, coord
, base
, permit
, permit_data
)))
920 for (f
= base
+ 1; f
< b
->flen
; f
++)
921 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
923 for (f
= 0; f
< base
; f
++)
924 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
932 board_is_false_eyelike(struct board
*board
, coord_t
*coord
, enum stone eye_color
)
934 enum stone color_diag_libs
[S_MAX
] = {0, 0, 0, 0};
936 /* XXX: We attempt false eye detection but we will yield false
937 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
939 foreach_diag_neighbor(board
, *coord
) {
940 color_diag_libs
[(enum stone
) board_at(board
, c
)]++;
941 } foreach_diag_neighbor_end
;
942 /* For false eye, we need two enemy stones diagonally in the
943 * middle of the board, or just one enemy stone at the edge
944 * or in the corner. */
945 color_diag_libs
[stone_other(eye_color
)] += !!color_diag_libs
[S_OFFBOARD
];
946 return color_diag_libs
[stone_other(eye_color
)] >= 2;
950 board_is_one_point_eye(struct board
*board
, coord_t
*coord
, enum stone eye_color
)
952 return board_is_eyelike(board
, coord
, eye_color
)
953 && !board_is_false_eyelike(board
, coord
, eye_color
);
957 board_get_one_point_eye(struct board
*board
, coord_t
*coord
)
959 if (board_is_one_point_eye(board
, coord
, S_WHITE
))
961 else if (board_is_one_point_eye(board
, coord
, S_BLACK
))
968 int profiling_noinline
969 board_group_capture(struct board
*board
, group_t group
)
973 foreach_in_group(board
, group
) {
974 board
->captures
[stone_other(board_at(board
, c
))]++;
975 board_remove_stone(board
, c
);
977 } foreach_in_group_end
;
979 if (board_group_info(board
, group
).libs
== 1)
980 board_capturable_rm(board
, group
);
981 memset(&board_group_info(board
, group
), 0, sizeof(struct group
));
988 board_fast_score(struct board
*board
)
991 memset(scores
, 0, sizeof(scores
));
993 foreach_point(board
) {
994 enum stone color
= board_at(board
, c
);
996 color
= board_get_one_point_eye(board
, &c
);
998 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1001 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];
1004 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1006 /* One flood-fill iteration; returns true if next iteration
1009 board_tromp_taylor_iter(struct board
*board
, int *ownermap
)
1011 bool needs_update
= false;
1012 foreach_point(board
) {
1013 /* Ignore occupied and already-dame positions. */
1014 if (board_at(board
, c
) != S_NONE
|| ownermap
[c
] == 3)
1016 /* Count neighbors. */
1018 foreach_neighbor(board
, c
, {
1021 /* If we have neighbors of both colors, or dame,
1022 * we are dame too. */
1023 if ((nei
[1] && nei
[2]) || nei
[3]) {
1025 /* Speed up the propagation. */
1026 foreach_neighbor(board
, c
, {
1027 if (board_at(board
, c
) == S_NONE
)
1030 needs_update
= true;
1033 /* If we have neighbors of one color, we are owned
1034 * by that color, too. */
1035 if (!ownermap
[c
] && (nei
[1] || nei
[2])) {
1036 int newowner
= nei
[1] ? 1 : 2;
1037 ownermap
[c
] = newowner
;
1038 /* Speed up the propagation. */
1039 foreach_neighbor(board
, c
, {
1040 if (board_at(board
, c
) == S_NONE
&& !ownermap
[c
])
1041 ownermap
[c
] = newowner
;
1043 needs_update
= true;
1046 } foreach_point_end
;
1047 return needs_update
;
1050 /* Tromp-Taylor Counting */
1052 board_official_score(struct board
*board
, struct move_queue
*q
)
1055 /* A point P, not colored C, is said to reach C, if there is a path of
1056 * (vertically or horizontally) adjacent points of P's color from P to
1057 * a point of color C.
1059 * A player's score is the number of points of her color, plus the
1060 * number of empty points that reach only her color. */
1062 int ownermap
[board_size2(board
)];
1064 const int o
[4] = {0, 1, 2, 0};
1065 foreach_point(board
) {
1066 ownermap
[c
] = o
[board_at(board
, c
)];
1067 s
[board_at(board
, c
)]++;
1068 } foreach_point_end
;
1071 /* Process dead groups. */
1072 for (int i
= 0; i
< q
->moves
; i
++) {
1073 foreach_in_group(board
, q
->move
[i
]) {
1074 enum stone color
= board_at(board
, c
);
1075 ownermap
[c
] = o
[stone_other(color
)];
1076 s
[color
]--; s
[stone_other(color
)]++;
1077 } foreach_in_group_end
;
1081 /* We need to special-case empty board. */
1082 if (!s
[S_BLACK
] && !s
[S_WHITE
])
1083 return board
->komi
+ board
->handicap
;
1085 while (board_tromp_taylor_iter(board
, ownermap
))
1086 /* Flood-fill... */;
1089 memset(scores
, 0, sizeof(scores
));
1091 foreach_point(board
) {
1092 assert(board_at(board
, c
) == S_OFFBOARD
|| ownermap
[c
] != 0);
1093 if (ownermap
[c
] == 3)
1095 scores
[ownermap
[c
]]++;
1096 } foreach_point_end
;
1098 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];