11 int board_group_capture(struct board
*board
, group_t group
);
13 bool random_pass
= false;
17 #define profiling_noinline __attribute__((noinline))
19 #define profiling_noinline
22 #define gi_granularity 4
23 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
27 board_setup(struct board
*b
)
29 memset(b
, 0, sizeof(*b
));
31 struct move m
= { pass
, S_NONE
};
32 b
->last_move
= b
->ko
= m
;
38 struct board
*b
= malloc(sizeof(struct board
));
44 board_copy(struct board
*b2
, struct board
*b1
)
46 memcpy(b2
, b1
, sizeof(struct board
));
48 int bsize
= board_size2(b2
) * sizeof(*b2
->b
);
49 int gsize
= board_size2(b2
) * sizeof(*b2
->g
);
50 int fsize
= board_size2(b2
) * sizeof(*b2
->f
);
51 int nsize
= board_size2(b2
) * sizeof(*b2
->n
);
52 int psize
= board_size2(b2
) * sizeof(*b2
->p
);
53 int hsize
= board_size2(b2
) * 2 * sizeof(*b2
->h
);
54 int gisize
= board_size2(b2
) * sizeof(*b2
->gi
);
56 int csize
= board_size2(b2
) * sizeof(*b2
->c
);
60 void *x
= malloc(bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
);
61 memcpy(x
, b1
->b
, bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
);
62 b2
->b
= x
; x
+= bsize
;
63 b2
->g
= x
; x
+= gsize
;
64 b2
->f
= x
; x
+= fsize
;
65 b2
->p
= x
; x
+= psize
;
66 b2
->n
= x
; x
+= nsize
;
67 b2
->h
= x
; x
+= hsize
;
68 b2
->gi
= x
; x
+= gisize
;
70 b2
->c
= x
; x
+= csize
;
77 board_done_noalloc(struct board
*board
)
79 if (board
->b
) free(board
->b
);
83 board_done(struct board
*board
)
85 board_done_noalloc(board
);
90 board_resize(struct board
*board
, int size
)
93 assert(board_size(board
) == size
+ 2);
95 board_size(board
) = size
+ 2 /* S_OFFBOARD margin */;
96 board_size2(board
) = board_size(board
) * board_size(board
);
101 int bsize
= board_size2(board
) * sizeof(*board
->b
);
102 int gsize
= board_size2(board
) * sizeof(*board
->g
);
103 int fsize
= board_size2(board
) * sizeof(*board
->f
);
104 int nsize
= board_size2(board
) * sizeof(*board
->n
);
105 int psize
= board_size2(board
) * sizeof(*board
->p
);
106 int hsize
= board_size2(board
) * 2 * sizeof(*board
->h
);
107 int gisize
= board_size2(board
) * sizeof(*board
->gi
);
109 int csize
= board_size2(board
) * sizeof(*board
->c
);
113 void *x
= malloc(bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
);
114 memset(x
, 0, bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
);
115 board
->b
= x
; x
+= bsize
;
116 board
->g
= x
; x
+= gsize
;
117 board
->f
= x
; x
+= fsize
;
118 board
->p
= x
; x
+= psize
;
119 board
->n
= x
; x
+= nsize
;
120 board
->h
= x
; x
+= hsize
;
121 board
->gi
= x
; x
+= gisize
;
123 board
->c
= x
; x
+= csize
;
128 board_clear(struct board
*board
)
130 int size
= board_size(board
);
132 board_done_noalloc(board
);
134 board_resize(board
, size
- 2 /* S_OFFBOARD margin */);
136 /* Draw the offboard margin */
137 int top_row
= board_size2(board
) - board_size(board
);
139 for (i
= 0; i
< board_size(board
); i
++)
140 board
->b
[i
] = board
->b
[top_row
+ i
] = S_OFFBOARD
;
141 for (i
= 0; i
<= top_row
; i
+= board_size(board
))
142 board
->b
[i
] = board
->b
[board_size(board
) - 1 + i
] = S_OFFBOARD
;
144 foreach_point(board
) {
146 if (board_at(board
, coord
) == S_OFFBOARD
)
148 foreach_neighbor(board
, c
, {
149 inc_neighbor_count_at(board
, coord
, board_at(board
, c
));
153 /* First, pass is always a free position. */
154 board
->f
[board
->flen
++] = coord_raw(pass
);
155 /* All positions are free! Except the margin. */
156 for (i
= board_size(board
); i
< (board_size(board
) - 1) * board_size(board
); i
++)
157 if (i
% board_size(board
) != 0 && i
% board_size(board
) != board_size(board
) - 1)
158 board
->f
[board
->flen
++] = i
;
160 /* Initialize zobrist hashtable. */
161 foreach_point(board
) {
162 int max
= (sizeof(hash_t
) << history_hash_bits
);
163 /* fast_random() is 16-bit only */
164 board
->h
[coord_raw(c
) * 2] = ((hash_t
) fast_random(max
))
165 | ((hash_t
) fast_random(max
) << 16)
166 | ((hash_t
) fast_random(max
) << 32)
167 | ((hash_t
) fast_random(max
) << 48);
168 if (!board
->h
[coord_raw(c
) * 2])
169 /* Would be kinda "oops". */
170 board
->h
[coord_raw(c
) * 2] = 1;
171 /* And once again for white */
172 board
->h
[coord_raw(c
) * 2 + 1] = ((hash_t
) fast_random(max
))
173 | ((hash_t
) fast_random(max
) << 16)
174 | ((hash_t
) fast_random(max
) << 32)
175 | ((hash_t
) fast_random(max
) << 48);
176 if (!board
->h
[coord_raw(c
) * 2 + 1])
177 board
->h
[coord_raw(c
) * 2 + 1] = 1;
183 board_print(struct board
*board
, FILE *f
)
185 fprintf(f
, "Move: % 3d Komi: %2.1f Captures B: %d W: %d\n ",
186 board
->moves
, board
->komi
,
187 board
->captures
[S_BLACK
], board
->captures
[S_WHITE
]);
189 char asdf
[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
190 for (x
= 1; x
< board_size(board
) - 1; x
++)
191 fprintf(f
, "%c ", asdf
[x
- 1]);
193 for (x
= 1; x
< board_size(board
) - 1; x
++)
196 for (y
= board_size(board
) - 2; y
>= 1; y
--) {
197 fprintf(f
, "%2d | ", y
);
198 for (x
= 1; x
< board_size(board
) - 1; x
++) {
199 if (coord_x(board
->last_move
.coord
, board
) == x
&& coord_y(board
->last_move
.coord
, board
) == y
)
200 fprintf(f
, "%c)", stone2char(board_atxy(board
, x
, y
)));
202 fprintf(f
, "%c ", stone2char(board_atxy(board
, x
, y
)));
206 for (x
= 1; x
< board_size(board
) - 1; x
++) {
207 fprintf(f
, "%d ", group_base(group_atxy(board
, x
, y
)));
213 for (x
= 1; x
< board_size(board
) - 1; x
++)
219 /* Update board hash with given coordinate. */
220 static void profiling_noinline
221 board_hash_update(struct board
*board
, coord_t coord
, enum stone color
)
223 board
->hash
^= hash_at(board
, coord
, color
);
225 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
);
228 /* Commit current board hash to history. */
229 static void profiling_noinline
230 board_hash_commit(struct board
*board
)
233 fprintf(stderr
, "board_hash_commit %llx\n", board
->hash
);
234 if (likely(board
->history_hash
[board
->hash
& history_hash_mask
]) == 0) {
235 board
->history_hash
[board
->hash
& history_hash_mask
] = board
->hash
;
237 hash_t i
= board
->hash
;
238 while (board
->history_hash
[i
& history_hash_mask
]) {
239 if (board
->history_hash
[i
& history_hash_mask
] == board
->hash
) {
241 fprintf(stderr
, "SUPERKO VIOLATION noted at %d,%d\n",
242 coord_x(board
->last_move
.coord
, board
), coord_y(board
->last_move
.coord
, board
));
243 board
->superko_violation
= true;
246 i
= history_hash_next(i
);
248 board
->history_hash
[i
& history_hash_mask
] = board
->hash
;
254 board_handicap_stone(struct board
*board
, int x
, int y
, FILE *f
)
258 coord_xy(m
.coord
, x
, y
, board
);
260 board_play(board
, &m
);
262 char *str
= coord2str(m
.coord
, board
);
264 fprintf(stderr
, "choosing handicap %s (%d,%d)\n", str
, x
, y
);
265 fprintf(f
, "%s ", str
);
270 board_handicap(struct board
*board
, int stones
, FILE *f
)
272 int margin
= 3 + (board_size(board
) >= 13);
274 int mid
= board_size(board
) / 2;
275 int max
= board_size(board
) - 1 - margin
;
276 const int places
[][2] = {
277 { min
, min
}, { max
, max
}, { max
, min
}, { min
, max
},
278 { min
, mid
}, { max
, mid
},
279 { mid
, min
}, { mid
, max
},
283 board
->handicap
= stones
;
285 if (stones
== 5 || stones
== 7) {
286 board_handicap_stone(board
, mid
, mid
, f
);
291 for (i
= 0; i
< stones
; i
++)
292 board_handicap_stone(board
, places
[i
][0], places
[i
][1], f
);
296 static void __attribute__((noinline
))
297 check_libs_consistency(struct board
*board
, group_t g
)
301 struct group
*gi
= &board_group_info(board
, g
);
302 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
303 if (gi
->lib
[i
] && board_at(board
, gi
->lib
[i
]) != S_NONE
) {
304 fprintf(stderr
, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi
->lib
[i
], board
), g
, coord2sstr(group_base(g
), board
));
311 board_capturable_add(struct board
*board
, group_t group
)
314 //fprintf(stderr, "add of group %d (%d)\n", group_base(group), board->clen);
316 assert(board
->clen
< board_size2(board
));
317 board
->c
[board
->clen
++] = group
;
321 board_capturable_rm(struct board
*board
, group_t group
)
324 //fprintf(stderr, "rm of group %d\n", group_base(group));
325 for (int i
= 0; i
< board
->clen
; i
++) {
326 if (unlikely(board
->c
[i
] == group
)) {
327 board
->c
[i
] = board
->c
[--board
->clen
];
331 fprintf(stderr
, "rm of bad group %d\n", group_base(group
));
337 board_group_addlib(struct board
*board
, group_t group
, coord_t coord
, bool fresh
)
340 fprintf(stderr
, "Group %d[%s] %d: Adding liberty %s\n",
341 group_base(group
), coord2sstr(group_base(group
), board
),
342 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
345 check_libs_consistency(board
, group
);
347 struct group
*gi
= &board_group_info(board
, group
);
348 if (gi
->libs
< GROUP_KEEP_LIBS
) {
350 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
352 /* Seems extra branch just slows it down */
356 if (unlikely(gi
->lib
[i
] == coord
))
360 board_capturable_add(board
, group
);
361 else if (gi
->libs
== 1)
362 board_capturable_rm(board
, group
);
363 gi
->lib
[gi
->libs
++] = coord
;
366 check_libs_consistency(board
, group
);
370 board_group_find_extra_libs(struct board
*board
, group_t group
, struct group
*gi
, coord_t avoid
)
372 /* Add extra liberty from the board to our liberty list. */
373 enum stone watermark
[board_size2(board
)];
374 memcpy(watermark
, board
->b
, sizeof(watermark
));
376 for (int i
= 0; i
< GROUP_KEEP_LIBS
- 1; i
++)
377 watermark
[coord_raw(gi
->lib
[i
])] = S_OFFBOARD
;
378 watermark
[coord_raw(avoid
)] = S_OFFBOARD
;
380 foreach_in_group(board
, group
) {
382 foreach_neighbor(board
, coord2
, {
383 if (likely(watermark
[coord_raw(c
)] != S_NONE
))
385 watermark
[coord_raw(c
)] = S_OFFBOARD
;
386 gi
->lib
[gi
->libs
++] = c
;
387 if (unlikely(gi
->libs
>= GROUP_KEEP_LIBS
))
390 } foreach_in_group_end
;
394 board_group_rmlib(struct board
*board
, group_t group
, coord_t coord
)
397 fprintf(stderr
, "Group %d[%s] %d: Removing liberty %s\n",
398 group_base(group
), coord2sstr(group_base(group
), board
),
399 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
402 struct group
*gi
= &board_group_info(board
, group
);
403 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
405 /* Seems extra branch just slows it down */
409 if (likely(gi
->lib
[i
] != coord
))
412 gi
->lib
[i
] = gi
->lib
[--gi
->libs
];
413 gi
->lib
[gi
->libs
] = 0;
415 check_libs_consistency(board
, group
);
417 /* Postpone refilling lib[] until we need to. */
418 assert(GROUP_REFILL_LIBS
> 1);
419 if (gi
->libs
> GROUP_REFILL_LIBS
)
421 if (gi
->libs
== GROUP_REFILL_LIBS
)
422 board_group_find_extra_libs(board
, group
, gi
, coord
);
425 board_capturable_add(board
, group
);
426 else if (gi
->libs
== 0)
427 board_capturable_rm(board
, group
);
431 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
432 * can call this multiple times per coord. */
433 check_libs_consistency(board
, group
);
438 /* This is a low-level routine that doesn't maintain consistency
439 * of all the board data structures. Use board_group_capture() from
442 board_remove_stone(struct board
*board
, coord_t c
)
444 enum stone color
= board_at(board
, c
);
445 board_at(board
, c
) = S_NONE
;
446 group_at(board
, c
) = 0;
447 board_hash_update(board
, c
, color
);
449 /* Increase liberties of surrounding groups */
451 foreach_neighbor(board
, coord
, {
452 dec_neighbor_count_at(board
, c
, color
);
453 group_t g
= group_at(board
, c
);
455 board_group_addlib(board
, g
, coord
, true);
459 fprintf(stderr
, "pushing free move [%d]: %d,%d\n", board
->flen
, coord_x(c
, board
), coord_y(c
, board
));
460 board
->f
[board
->flen
++] = coord_raw(c
);
464 static void profiling_noinline
465 add_to_group(struct board
*board
, group_t group
, coord_t prevstone
, coord_t coord
)
467 foreach_neighbor(board
, coord
, {
468 if (board_at(board
, c
) == S_NONE
)
469 board_group_addlib(board
, group
, c
, false);
472 group_at(board
, coord
) = group
;
473 groupnext_at(board
, coord
) = groupnext_at(board
, prevstone
);
474 groupnext_at(board
, prevstone
) = coord_raw(coord
);
477 fprintf(stderr
, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
478 coord_x(prevstone
, board
), coord_y(prevstone
, board
),
479 coord_x(coord
, board
), coord_y(coord
, board
),
480 groupnext_at(board
, coord
) % board_size(board
), groupnext_at(board
, coord
) / board_size(board
),
484 static void profiling_noinline
485 merge_groups(struct board
*board
, group_t group_to
, group_t group_from
)
488 fprintf(stderr
, "board_play_raw: merging groups %d -> %d\n",
489 group_base(group_from
), group_base(group_to
));
491 coord_t last_in_group
;
492 foreach_in_group(board
, group_from
) {
494 group_at(board
, c
) = group_to
;
495 } foreach_in_group_end
;
496 groupnext_at(board
, last_in_group
) = groupnext_at(board
, group_base(group_to
));
497 groupnext_at(board
, group_base(group_to
)) = group_base(group_from
);
499 struct group
*gi_from
= &board_group_info(board
, group_from
);
500 struct group
*gi_to
= &board_group_info(board
, group_to
);
501 if (gi_to
->libs
< GROUP_KEEP_LIBS
) {
502 for (int i
= 0; i
< gi_from
->libs
; i
++) {
503 for (int j
= 0; j
< gi_to
->libs
; j
++)
504 if (gi_to
->lib
[j
] == gi_from
->lib
[i
])
506 if (gi_to
->libs
== 0)
507 board_capturable_add(board
, group_to
);
508 else if (gi_to
->libs
== 1)
509 board_capturable_rm(board
, group_to
);
510 gi_to
->lib
[gi_to
->libs
++] = gi_from
->lib
[i
];
511 if (gi_to
->libs
>= GROUP_KEEP_LIBS
)
517 if (gi_from
->libs
== 1)
518 board_capturable_rm(board
, group_from
);
519 memset(gi_from
, 0, sizeof(struct group
));
522 fprintf(stderr
, "board_play_raw: merged group: %d\n",
523 group_base(group_to
));
526 static group_t profiling_noinline
527 new_group(struct board
*board
, coord_t coord
)
529 group_t group
= coord_raw(coord
);
530 struct group
*gi
= &board_group_info(board
, group
);
531 foreach_neighbor(board
, coord
, {
532 if (board_at(board
, c
) == S_NONE
)
533 /* board_group_addlib is ridiculously expensive for us */
534 #if GROUP_KEEP_LIBS < 4
535 if (gi
->libs
< GROUP_KEEP_LIBS
)
537 gi
->lib
[gi
->libs
++] = c
;
540 board_capturable_add(board
, group
);
541 check_libs_consistency(board
, group
);
543 group_at(board
, coord
) = group
;
544 groupnext_at(board
, coord
) = 0;
547 fprintf(stderr
, "new_group: added %d,%d to group %d\n",
548 coord_x(coord
, board
), coord_y(coord
, board
),
554 static inline group_t
555 play_one_neighbor(struct board
*board
,
556 coord_t coord
, enum stone color
, enum stone other_color
,
557 coord_t c
, group_t group
)
559 enum stone ncolor
= board_at(board
, c
);
560 group_t ngroup
= group_at(board
, c
);
562 inc_neighbor_count_at(board
, c
, color
);
567 board_group_rmlib(board
, ngroup
, coord
);
569 fprintf(stderr
, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
570 group_base(ngroup
), ncolor
, color
, other_color
);
572 if (ncolor
== color
&& ngroup
!= group
) {
575 add_to_group(board
, group
, c
, coord
);
577 merge_groups(board
, group
, ngroup
);
579 } else if (ncolor
== other_color
) {
581 struct group
*gi
= &board_group_info(board
, ngroup
);
582 fprintf(stderr
, "testing captured group %d[%s]: ", group_base(ngroup
), coord2sstr(group_base(ngroup
), board
));
583 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
584 fprintf(stderr
, "%s ", coord2sstr(gi
->lib
[i
], board
));
585 fprintf(stderr
, "\n");
587 if (unlikely(board_group_captured(board
, ngroup
)))
588 board_group_capture(board
, ngroup
);
593 /* We played on a place with at least one liberty. We will become a member of
594 * some group for sure. */
595 static group_t profiling_noinline
596 board_play_outside(struct board
*board
, struct move
*m
, int f
)
598 coord_t coord
= m
->coord
;
599 enum stone color
= m
->color
;
600 enum stone other_color
= stone_other(color
);
603 board
->f
[f
] = board
->f
[--board
->flen
];
605 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
607 foreach_neighbor(board
, coord
, {
608 group
= play_one_neighbor(board
, coord
, color
, other_color
, c
, group
);
611 if (unlikely(!group
))
612 group
= new_group(board
, coord
);
614 board_at(board
, coord
) = color
;
615 board
->last_move
= *m
;
617 board_hash_update(board
, coord
, color
);
618 struct move ko
= { pass
, S_NONE
};
624 /* We played in an eye-like shape. Either we capture at least one of the eye
625 * sides in the process of playing, or return -1. */
626 static int profiling_noinline
627 board_play_in_eye(struct board
*board
, struct move
*m
, int f
)
629 coord_t coord
= m
->coord
;
630 enum stone color
= m
->color
;
631 /* Check ko: Capture at a position of ko capture one move ago */
632 if (unlikely(color
== board
->ko
.color
&& coord_eq(coord
, board
->ko
.coord
))) {
634 fprintf(stderr
, "board_check: ko at %d,%d color %d\n", coord_x(coord
, board
), coord_y(coord
, board
), color
);
636 } else if (DEBUGL(6)) {
637 fprintf(stderr
, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
638 color
, coord_x(coord
, board
), coord_y(coord
, board
),
639 board
->ko
.color
, coord_x(board
->ko
.coord
, board
), coord_y(board
->ko
.coord
, board
));
642 struct move ko
= { pass
, S_NONE
};
644 int captured_groups
= 0;
646 foreach_neighbor(board
, coord
, {
647 captured_groups
+= (board_group_info(board
, group_at(board
, c
)).libs
== 1);
650 if (likely(captured_groups
== 0)) {
653 board_print(board
, stderr
);
654 fprintf(stderr
, "board_check: one-stone suicide\n");
660 board
->f
[f
] = board
->f
[--board
->flen
];
662 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
664 foreach_neighbor(board
, coord
, {
665 inc_neighbor_count_at(board
, c
, color
);
667 group_t group
= group_at(board
, c
);
671 board_group_rmlib(board
, group
, coord
);
673 fprintf(stderr
, "board_play_raw: reducing libs for group %d\n",
676 if (board_group_captured(board
, group
)) {
677 if (board_group_capture(board
, group
) == 1) {
678 /* If we captured multiple groups at once,
679 * we can't be fighting ko so we don't need
680 * to check for that. */
681 ko
.color
= stone_other(color
);
684 fprintf(stderr
, "guarding ko at %d,%d,%d\n", ko
.color
, coord_x(ko
.coord
, board
), coord_y(ko
.coord
, board
));
689 board_at(board
, coord
) = color
;
691 board
->last_move
= *m
;
693 board_hash_update(board
, coord
, color
);
694 board_hash_commit(board
);
697 return !!new_group(board
, coord
);
700 static int __attribute__((flatten
))
701 board_play_f(struct board
*board
, struct move
*m
, int f
)
704 fprintf(stderr
, "board_play(): ---- Playing %d,%d\n", coord_x(m
->coord
, board
), coord_y(m
->coord
, board
));
706 if (likely(!board_is_eyelike(board
, &m
->coord
, stone_other(m
->color
)))) {
707 /* NOT playing in an eye. Thus this move has to succeed. (This
708 * is thanks to New Zealand rules. Otherwise, multi-stone
709 * suicide might fail.) */
710 group_t group
= board_play_outside(board
, m
, f
);
711 if (unlikely(board_group_captured(board
, group
))) {
712 board_group_capture(board
, group
);
714 board_hash_commit(board
);
717 return board_play_in_eye(board
, m
, f
);
722 board_play(struct board
*board
, struct move
*m
)
724 if (unlikely(is_pass(m
->coord
) || is_resign(m
->coord
))) {
725 board
->last_move
= *m
;
730 for (f
= 0; f
< board
->flen
; f
++)
731 if (board
->f
[f
] == coord_raw(m
->coord
))
732 return board_play_f(board
, m
, f
);
735 fprintf(stderr
, "board_check: stone exists\n");
741 board_try_random_move(struct board
*b
, enum stone color
, coord_t
*coord
, int f
)
743 coord_raw(*coord
) = b
->f
[f
];
744 if (unlikely(is_pass(*coord
)))
746 struct move m
= { *coord
, color
};
748 fprintf(stderr
, "trying random move %d: %d,%d\n", f
, coord_x(*coord
, b
), coord_y(*coord
, b
));
749 return (likely(!board_is_one_point_eye(b
, coord
, color
)) /* bad idea to play into one, usually */
750 && likely(board_play_f(b
, &m
, f
) >= 0));
754 board_play_random(struct board
*b
, enum stone color
, coord_t
*coord
)
756 int base
= fast_random(b
->flen
);
757 coord_pos(*coord
, base
, b
);
758 if (likely(board_try_random_move(b
, color
, coord
, base
)))
762 for (f
= base
+ 1; f
< b
->flen
; f
++)
763 if (board_try_random_move(b
, color
, coord
, f
))
765 for (f
= 0; f
< base
; f
++)
766 if (board_try_random_move(b
, color
, coord
, f
))
774 board_is_eyelike(struct board
*board
, coord_t
*coord
, enum stone eye_color
)
776 return (neighbor_count_at(board
, *coord
, eye_color
) + neighbor_count_at(board
, *coord
, S_OFFBOARD
)) == 4;
780 board_is_one_point_eye(struct board
*board
, coord_t
*coord
, enum stone eye_color
)
782 enum stone color_diag_libs
[S_MAX
] = {0, 0, 0, 0};
784 if (likely(neighbor_count_at(board
, *coord
, eye_color
) + neighbor_count_at(board
, *coord
, S_OFFBOARD
) < 4)) {
788 /* XXX: We attempt false eye detection but we will yield false
789 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
791 foreach_diag_neighbor(board
, *coord
) {
792 color_diag_libs
[(enum stone
) board_at(board
, c
)]++;
793 } foreach_diag_neighbor_end
;
794 color_diag_libs
[stone_other(eye_color
)] += !!color_diag_libs
[S_OFFBOARD
];
795 return likely(color_diag_libs
[stone_other(eye_color
)] < 2);
799 board_get_one_point_eye(struct board
*board
, coord_t
*coord
)
801 if (board_is_one_point_eye(board
, coord
, S_WHITE
))
803 else if (board_is_one_point_eye(board
, coord
, S_BLACK
))
810 int profiling_noinline
811 board_group_capture(struct board
*board
, group_t group
)
815 foreach_in_group(board
, group
) {
816 board
->captures
[stone_other(board_at(board
, c
))]++;
817 board_remove_stone(board
, c
);
819 } foreach_in_group_end
;
821 if (board_group_info(board
, group
).libs
== 1)
822 board_capturable_rm(board
, group
);
823 memset(&board_group_info(board
, group
), 0, sizeof(struct group
));
829 board_group_in_atari(struct board
*board
, group_t group
, coord_t
*lastlib
)
831 if (board_group_info(board
, group
).libs
!= 1)
833 *lastlib
= board_group_info(board
, group
).lib
[0];
838 board_group_can_atari(struct board
*board
, group_t group
, coord_t lastlib
[2])
840 if (board_group_info(board
, group
).libs
!= 2)
842 lastlib
[0] = board_group_info(board
, group
).lib
[0];
843 lastlib
[1] = board_group_info(board
, group
).lib
[1];
849 board_tromp_taylor_owner(struct board
*board
, coord_t c
)
851 int x
= coord_x(c
, board
), y
= coord_y(c
, board
);
852 enum stone color
= S_NONE
;
853 #define TEST_REACH(xx, yy) \
855 enum stone c2 = board_atxy(board, xx, yy); \
856 if (c2 != S_NONE) { \
857 if (color != S_NONE && color != c2) \
863 for (int i
= x
; i
> 0; i
--)
865 for (int i
= x
; i
< board_size(board
) - 1; i
++)
867 for (int i
= y
; i
> 0; i
--)
869 for (int i
= y
; i
< board_size(board
) - 1; i
++)
874 /* Tromp-Taylor Counting */
876 board_official_score(struct board
*board
)
879 /* A point P, not colored C, is said to reach C, if there is a path of
880 * (vertically or horizontally) adjacent points of P's color from P to
881 * a point of color C.
883 * A player's score is the number of points of her color, plus the
884 * number of empty points that reach only her color. */
887 memset(scores
, 0, sizeof(scores
));
889 foreach_point(board
) {
890 enum stone color
= board_at(board
, c
);
892 color
= board_tromp_taylor_owner(board
, c
);
896 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];
900 board_fast_score(struct board
*board
)
903 memset(scores
, 0, sizeof(scores
));
905 foreach_point(board
) {
906 enum stone color
= board_at(board
, c
);
908 color
= board_get_one_point_eye(board
, &c
);
910 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
913 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];
918 valid_escape_route(struct board
*b
, enum stone color
, coord_t to
)
920 /* Assess if we actually gain any liberties by this escape route.
921 * Note that this is not 100% as we cannot check whether we are
922 * connecting out or just to ourselves. */
923 /* Also, we prohibit 1-1 here:
930 int friends
= neighbor_count_at(b
, to
, color
);
931 int borders
= neighbor_count_at(b
, to
, S_OFFBOARD
);
932 int libs
= immediate_liberty_count(b
, to
);
933 return (friends
> 1 && friends
+ borders
< 4) || (libs
> 1);
938 board_stone_radar(struct board
*b
, coord_t coord
, int distance
)
941 coord_x(coord
, b
) - distance
,
942 coord_y(coord
, b
) - distance
,
943 coord_x(coord
, b
) + distance
,
944 coord_y(coord
, b
) + distance
946 for (int i
= 0; i
< 4; i
++)
949 else if (bounds
[i
] > board_size(b
) - 2)
950 bounds
[i
] = board_size(b
) - 2;
951 for (int x
= bounds
[0]; x
<= bounds
[2]; x
++)
952 for (int y
= bounds
[1]; y
<= bounds
[3]; y
++)
953 if (board_atxy(b
, x
, y
) != S_NONE
) {
954 //fprintf(stderr, "radar %d,%d,%d: %d,%d (%d)\n", coord_x(coord, b), coord_y(coord, b), distance, x, y, board_atxy(b, x, y));