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
);
131 float komi
= board
->komi
;
133 board_done_noalloc(board
);
135 board_resize(board
, size
- 2 /* S_OFFBOARD margin */);
139 /* Setup initial symmetry */
140 board
->symmetry
.d
= 1;
141 board
->symmetry
.x1
= board
->symmetry
.y1
= board
->size
/ 2;
142 board
->symmetry
.x2
= board
->symmetry
.y2
= board
->size
- 1;
143 board
->symmetry
.type
= SYM_FULL
;
145 /* Draw the offboard margin */
146 int top_row
= board_size2(board
) - board_size(board
);
148 for (i
= 0; i
< board_size(board
); i
++)
149 board
->b
[i
] = board
->b
[top_row
+ i
] = S_OFFBOARD
;
150 for (i
= 0; i
<= top_row
; i
+= board_size(board
))
151 board
->b
[i
] = board
->b
[board_size(board
) - 1 + i
] = S_OFFBOARD
;
153 foreach_point(board
) {
155 if (board_at(board
, coord
) == S_OFFBOARD
)
157 foreach_neighbor(board
, c
, {
158 inc_neighbor_count_at(board
, coord
, board_at(board
, c
));
162 /* First, pass is always a free position. */
163 board
->f
[board
->flen
++] = coord_raw(pass
);
164 /* All positions are free! Except the margin. */
165 for (i
= board_size(board
); i
< (board_size(board
) - 1) * board_size(board
); i
++)
166 if (i
% board_size(board
) != 0 && i
% board_size(board
) != board_size(board
) - 1)
167 board
->f
[board
->flen
++] = i
;
169 /* Initialize zobrist hashtable. */
170 foreach_point(board
) {
171 int max
= (sizeof(hash_t
) << history_hash_bits
);
172 /* fast_random() is 16-bit only */
173 board
->h
[coord_raw(c
) * 2] = ((hash_t
) fast_random(max
))
174 | ((hash_t
) fast_random(max
) << 16)
175 | ((hash_t
) fast_random(max
) << 32)
176 | ((hash_t
) fast_random(max
) << 48);
177 if (!board
->h
[coord_raw(c
) * 2])
178 /* Would be kinda "oops". */
179 board
->h
[coord_raw(c
) * 2] = 1;
180 /* And once again for white */
181 board
->h
[coord_raw(c
) * 2 + 1] = ((hash_t
) fast_random(max
))
182 | ((hash_t
) fast_random(max
) << 16)
183 | ((hash_t
) fast_random(max
) << 32)
184 | ((hash_t
) fast_random(max
) << 48);
185 if (!board
->h
[coord_raw(c
) * 2 + 1])
186 board
->h
[coord_raw(c
) * 2 + 1] = 1;
192 board_print(struct board
*board
, FILE *f
)
194 fprintf(f
, "Move: % 3d Komi: %2.1f Captures B: %d W: %d\n ",
195 board
->moves
, board
->komi
,
196 board
->captures
[S_BLACK
], board
->captures
[S_WHITE
]);
198 char asdf
[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
199 for (x
= 1; x
< board_size(board
) - 1; x
++)
200 fprintf(f
, "%c ", asdf
[x
- 1]);
202 for (x
= 1; x
< board_size(board
) - 1; x
++)
205 for (y
= board_size(board
) - 2; y
>= 1; y
--) {
206 fprintf(f
, "%2d | ", y
);
207 for (x
= 1; x
< board_size(board
) - 1; x
++) {
208 if (coord_x(board
->last_move
.coord
, board
) == x
&& coord_y(board
->last_move
.coord
, board
) == y
)
209 fprintf(f
, "%c)", stone2char(board_atxy(board
, x
, y
)));
211 fprintf(f
, "%c ", stone2char(board_atxy(board
, x
, y
)));
215 for (x
= 1; x
< board_size(board
) - 1; x
++) {
216 fprintf(f
, "%d ", group_base(group_atxy(board
, x
, y
)));
222 for (x
= 1; x
< board_size(board
) - 1; x
++)
228 /* Update board hash with given coordinate. */
229 static void profiling_noinline
230 board_hash_update(struct board
*board
, coord_t coord
, enum stone color
)
232 board
->hash
^= hash_at(board
, coord
, color
);
234 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
);
237 /* Commit current board hash to history. */
238 static void profiling_noinline
239 board_hash_commit(struct board
*board
)
242 fprintf(stderr
, "board_hash_commit %llx\n", board
->hash
);
243 if (likely(board
->history_hash
[board
->hash
& history_hash_mask
]) == 0) {
244 board
->history_hash
[board
->hash
& history_hash_mask
] = board
->hash
;
246 hash_t i
= board
->hash
;
247 while (board
->history_hash
[i
& history_hash_mask
]) {
248 if (board
->history_hash
[i
& history_hash_mask
] == board
->hash
) {
250 fprintf(stderr
, "SUPERKO VIOLATION noted at %d,%d\n",
251 coord_x(board
->last_move
.coord
, board
), coord_y(board
->last_move
.coord
, board
));
252 board
->superko_violation
= true;
255 i
= history_hash_next(i
);
257 board
->history_hash
[i
& history_hash_mask
] = board
->hash
;
263 board_symmetry_update(struct board
*b
, struct board_symmetry
*symmetry
, coord_t c
)
265 if (likely(symmetry
->type
== SYM_NONE
)) {
266 /* Fully degenerated already. We do not support detection
267 * of restoring of symmetry, assuming that this is too rare
268 * a case to handle. */
272 int x
= coord_x(c
, b
), y
= coord_y(c
, b
), t
= board_size(b
) / 2;
273 int dx
= board_size(b
) - 1 - x
; /* for SYM_DOWN */
275 fprintf(stderr
, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
276 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
277 symmetry
->d
, symmetry
->type
, x
, y
);
280 switch (symmetry
->type
) {
282 if (x
== t
&& y
== t
) {
283 /* Tengen keeps full symmetry. */
286 /* New symmetry now? */
288 symmetry
->type
= SYM_DIAG_UP
;
289 symmetry
->x1
= symmetry
->y1
= 1;
290 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
292 } else if (dx
== y
) {
293 symmetry
->type
= SYM_DIAG_DOWN
;
294 symmetry
->x1
= symmetry
->y1
= 1;
295 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
298 symmetry
->type
= SYM_HORIZ
;
300 symmetry
->y2
= board_size(b
) - 1;
303 symmetry
->type
= SYM_VERT
;
305 symmetry
->x2
= board_size(b
) - 1;
309 symmetry
->type
= SYM_NONE
;
310 symmetry
->x1
= symmetry
->y1
= 1;
311 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
337 fprintf(stderr
, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
338 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
339 symmetry
->d
, symmetry
->type
);
346 board_handicap_stone(struct board
*board
, int x
, int y
, FILE *f
)
349 m
.color
= S_BLACK
; m
.coord
= coord_xy(board
, x
, y
);
351 board_play(board
, &m
);
352 /* Simulate white passing; otherwise, UCT search can get confused since
353 * tree depth parity won't match the color to move. */
356 char *str
= coord2str(m
.coord
, board
);
358 fprintf(stderr
, "choosing handicap %s (%d,%d)\n", str
, x
, y
);
359 fprintf(f
, "%s ", str
);
364 board_handicap(struct board
*board
, int stones
, FILE *f
)
366 int margin
= 3 + (board_size(board
) >= 13);
368 int mid
= board_size(board
) / 2;
369 int max
= board_size(board
) - 1 - margin
;
370 const int places
[][2] = {
371 { min
, min
}, { max
, max
}, { max
, min
}, { min
, max
},
372 { min
, mid
}, { max
, mid
},
373 { mid
, min
}, { mid
, max
},
377 board
->handicap
= stones
;
379 if (stones
== 5 || stones
== 7) {
380 board_handicap_stone(board
, mid
, mid
, f
);
385 for (i
= 0; i
< stones
; i
++)
386 board_handicap_stone(board
, places
[i
][0], places
[i
][1], f
);
390 static void __attribute__((noinline
))
391 check_libs_consistency(struct board
*board
, group_t g
)
395 struct group
*gi
= &board_group_info(board
, g
);
396 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
397 if (gi
->lib
[i
] && board_at(board
, gi
->lib
[i
]) != S_NONE
) {
398 fprintf(stderr
, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi
->lib
[i
], board
), g
, coord2sstr(group_base(g
), board
));
405 board_capturable_add(struct board
*board
, group_t group
)
408 //fprintf(stderr, "add of group %d (%d)\n", group_base(group), board->clen);
410 assert(board
->clen
< board_size2(board
));
411 board
->c
[board
->clen
++] = group
;
415 board_capturable_rm(struct board
*board
, group_t group
)
418 //fprintf(stderr, "rm of group %d\n", group_base(group));
419 for (int i
= 0; i
< board
->clen
; i
++) {
420 if (unlikely(board
->c
[i
] == group
)) {
421 board
->c
[i
] = board
->c
[--board
->clen
];
425 fprintf(stderr
, "rm of bad group %d\n", group_base(group
));
431 board_group_addlib(struct board
*board
, group_t group
, coord_t coord
)
434 fprintf(stderr
, "Group %d[%s] %d: Adding liberty %s\n",
435 group_base(group
), coord2sstr(group_base(group
), board
),
436 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
439 check_libs_consistency(board
, group
);
441 struct group
*gi
= &board_group_info(board
, group
);
442 if (gi
->libs
< GROUP_KEEP_LIBS
) {
443 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
445 /* Seems extra branch just slows it down */
449 if (unlikely(gi
->lib
[i
] == coord
))
453 board_capturable_add(board
, group
);
454 else if (gi
->libs
== 1)
455 board_capturable_rm(board
, group
);
456 gi
->lib
[gi
->libs
++] = coord
;
459 check_libs_consistency(board
, group
);
463 board_group_find_extra_libs(struct board
*board
, group_t group
, struct group
*gi
, coord_t avoid
)
465 /* Add extra liberty from the board to our liberty list. */
466 enum stone watermark
[board_size2(board
)];
467 memcpy(watermark
, board
->b
, sizeof(watermark
));
469 for (int i
= 0; i
< GROUP_KEEP_LIBS
- 1; i
++)
470 watermark
[coord_raw(gi
->lib
[i
])] = S_OFFBOARD
;
471 watermark
[coord_raw(avoid
)] = S_OFFBOARD
;
473 foreach_in_group(board
, group
) {
475 foreach_neighbor(board
, coord2
, {
476 if (likely(watermark
[coord_raw(c
)] != S_NONE
))
478 watermark
[coord_raw(c
)] = S_OFFBOARD
;
479 gi
->lib
[gi
->libs
++] = c
;
480 if (unlikely(gi
->libs
>= GROUP_KEEP_LIBS
))
483 } foreach_in_group_end
;
487 board_group_rmlib(struct board
*board
, group_t group
, coord_t coord
)
490 fprintf(stderr
, "Group %d[%s] %d: Removing liberty %s\n",
491 group_base(group
), coord2sstr(group_base(group
), board
),
492 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
495 struct group
*gi
= &board_group_info(board
, group
);
496 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
498 /* Seems extra branch just slows it down */
502 if (likely(gi
->lib
[i
] != coord
))
505 gi
->lib
[i
] = gi
->lib
[--gi
->libs
];
506 gi
->lib
[gi
->libs
] = 0;
508 check_libs_consistency(board
, group
);
510 /* Postpone refilling lib[] until we need to. */
511 assert(GROUP_REFILL_LIBS
> 1);
512 if (gi
->libs
> GROUP_REFILL_LIBS
)
514 if (gi
->libs
== GROUP_REFILL_LIBS
)
515 board_group_find_extra_libs(board
, group
, gi
, coord
);
518 board_capturable_add(board
, group
);
519 else if (gi
->libs
== 0)
520 board_capturable_rm(board
, group
);
524 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
525 * can call this multiple times per coord. */
526 check_libs_consistency(board
, group
);
531 /* This is a low-level routine that doesn't maintain consistency
532 * of all the board data structures. Use board_group_capture() from
535 board_remove_stone(struct board
*board
, coord_t c
)
537 enum stone color
= board_at(board
, c
);
538 board_at(board
, c
) = S_NONE
;
539 group_at(board
, c
) = 0;
540 board_hash_update(board
, c
, color
);
542 /* Increase liberties of surrounding groups */
544 foreach_neighbor(board
, coord
, {
545 dec_neighbor_count_at(board
, c
, color
);
546 group_t g
= group_at(board
, c
);
548 board_group_addlib(board
, g
, coord
);
552 fprintf(stderr
, "pushing free move [%d]: %d,%d\n", board
->flen
, coord_x(c
, board
), coord_y(c
, board
));
553 board
->f
[board
->flen
++] = coord_raw(c
);
557 static void profiling_noinline
558 add_to_group(struct board
*board
, group_t group
, coord_t prevstone
, coord_t coord
)
560 foreach_neighbor(board
, coord
, {
561 if (board_at(board
, c
) == S_NONE
)
562 board_group_addlib(board
, group
, c
);
565 group_at(board
, coord
) = group
;
566 groupnext_at(board
, coord
) = groupnext_at(board
, prevstone
);
567 groupnext_at(board
, prevstone
) = coord_raw(coord
);
570 fprintf(stderr
, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
571 coord_x(prevstone
, board
), coord_y(prevstone
, board
),
572 coord_x(coord
, board
), coord_y(coord
, board
),
573 groupnext_at(board
, coord
) % board_size(board
), groupnext_at(board
, coord
) / board_size(board
),
577 static void profiling_noinline
578 merge_groups(struct board
*board
, group_t group_to
, group_t group_from
)
581 fprintf(stderr
, "board_play_raw: merging groups %d -> %d\n",
582 group_base(group_from
), group_base(group_to
));
584 coord_t last_in_group
;
585 foreach_in_group(board
, group_from
) {
587 group_at(board
, c
) = group_to
;
588 } foreach_in_group_end
;
589 groupnext_at(board
, last_in_group
) = groupnext_at(board
, group_base(group_to
));
590 groupnext_at(board
, group_base(group_to
)) = group_base(group_from
);
592 struct group
*gi_from
= &board_group_info(board
, group_from
);
593 struct group
*gi_to
= &board_group_info(board
, group_to
);
594 if (gi_to
->libs
< GROUP_KEEP_LIBS
) {
595 for (int i
= 0; i
< gi_from
->libs
; i
++) {
596 for (int j
= 0; j
< gi_to
->libs
; j
++)
597 if (gi_to
->lib
[j
] == gi_from
->lib
[i
])
599 if (gi_to
->libs
== 0)
600 board_capturable_add(board
, group_to
);
601 else if (gi_to
->libs
== 1)
602 board_capturable_rm(board
, group_to
);
603 gi_to
->lib
[gi_to
->libs
++] = gi_from
->lib
[i
];
604 if (gi_to
->libs
>= GROUP_KEEP_LIBS
)
610 if (gi_from
->libs
== 1)
611 board_capturable_rm(board
, group_from
);
612 memset(gi_from
, 0, sizeof(struct group
));
615 fprintf(stderr
, "board_play_raw: merged group: %d\n",
616 group_base(group_to
));
619 static group_t profiling_noinline
620 new_group(struct board
*board
, coord_t coord
)
622 group_t group
= coord_raw(coord
);
623 struct group
*gi
= &board_group_info(board
, group
);
624 foreach_neighbor(board
, coord
, {
625 if (board_at(board
, c
) == S_NONE
)
626 /* board_group_addlib is ridiculously expensive for us */
627 #if GROUP_KEEP_LIBS < 4
628 if (gi
->libs
< GROUP_KEEP_LIBS
)
630 gi
->lib
[gi
->libs
++] = c
;
633 board_capturable_add(board
, group
);
634 check_libs_consistency(board
, group
);
636 group_at(board
, coord
) = group
;
637 groupnext_at(board
, coord
) = 0;
640 fprintf(stderr
, "new_group: added %d,%d to group %d\n",
641 coord_x(coord
, board
), coord_y(coord
, board
),
647 static inline group_t
648 play_one_neighbor(struct board
*board
,
649 coord_t coord
, enum stone color
, enum stone other_color
,
650 coord_t c
, group_t group
)
652 enum stone ncolor
= board_at(board
, c
);
653 group_t ngroup
= group_at(board
, c
);
655 inc_neighbor_count_at(board
, c
, color
);
660 board_group_rmlib(board
, ngroup
, coord
);
662 fprintf(stderr
, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
663 group_base(ngroup
), ncolor
, color
, other_color
);
665 if (ncolor
== color
&& ngroup
!= group
) {
668 add_to_group(board
, group
, c
, coord
);
670 merge_groups(board
, group
, ngroup
);
672 } else if (ncolor
== other_color
) {
674 struct group
*gi
= &board_group_info(board
, ngroup
);
675 fprintf(stderr
, "testing captured group %d[%s]: ", group_base(ngroup
), coord2sstr(group_base(ngroup
), board
));
676 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
677 fprintf(stderr
, "%s ", coord2sstr(gi
->lib
[i
], board
));
678 fprintf(stderr
, "\n");
680 if (unlikely(board_group_captured(board
, ngroup
)))
681 board_group_capture(board
, ngroup
);
686 /* We played on a place with at least one liberty. We will become a member of
687 * some group for sure. */
688 static group_t profiling_noinline
689 board_play_outside(struct board
*board
, struct move
*m
, int f
)
691 coord_t coord
= m
->coord
;
692 enum stone color
= m
->color
;
693 enum stone other_color
= stone_other(color
);
696 board
->f
[f
] = board
->f
[--board
->flen
];
698 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
700 foreach_neighbor(board
, coord
, {
701 group
= play_one_neighbor(board
, coord
, color
, other_color
, c
, group
);
704 if (unlikely(!group
))
705 group
= new_group(board
, coord
);
707 board_at(board
, coord
) = color
;
708 board
->last_move
= *m
;
710 board_hash_update(board
, coord
, color
);
711 board_symmetry_update(board
, &board
->symmetry
, coord
);
712 struct move ko
= { pass
, S_NONE
};
718 /* We played in an eye-like shape. Either we capture at least one of the eye
719 * sides in the process of playing, or return -1. */
720 static int profiling_noinline
721 board_play_in_eye(struct board
*board
, struct move
*m
, int f
)
723 coord_t coord
= m
->coord
;
724 enum stone color
= m
->color
;
725 /* Check ko: Capture at a position of ko capture one move ago */
726 if (unlikely(color
== board
->ko
.color
&& coord_eq(coord
, board
->ko
.coord
))) {
728 fprintf(stderr
, "board_check: ko at %d,%d color %d\n", coord_x(coord
, board
), coord_y(coord
, board
), color
);
730 } else if (DEBUGL(6)) {
731 fprintf(stderr
, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
732 color
, coord_x(coord
, board
), coord_y(coord
, board
),
733 board
->ko
.color
, coord_x(board
->ko
.coord
, board
), coord_y(board
->ko
.coord
, board
));
736 struct move ko
= { pass
, S_NONE
};
738 int captured_groups
= 0;
740 foreach_neighbor(board
, coord
, {
741 group_t g
= group_at(board
, c
);
743 fprintf(stderr
, "board_check: group %d has %d libs\n",
744 g
, board_group_info(board
, g
).libs
);
745 captured_groups
+= (board_group_info(board
, g
).libs
== 1);
748 if (likely(captured_groups
== 0)) {
751 board_print(board
, stderr
);
752 fprintf(stderr
, "board_check: one-stone suicide\n");
758 board
->f
[f
] = board
->f
[--board
->flen
];
760 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
762 foreach_neighbor(board
, coord
, {
763 inc_neighbor_count_at(board
, c
, color
);
765 group_t group
= group_at(board
, c
);
769 board_group_rmlib(board
, group
, coord
);
771 fprintf(stderr
, "board_play_raw: reducing libs for group %d\n",
774 if (board_group_captured(board
, group
)) {
775 if (board_group_capture(board
, group
) == 1) {
776 /* If we captured multiple groups at once,
777 * we can't be fighting ko so we don't need
778 * to check for that. */
779 ko
.color
= stone_other(color
);
782 fprintf(stderr
, "guarding ko at %d,%d,%d\n", ko
.color
, coord_x(ko
.coord
, board
), coord_y(ko
.coord
, board
));
787 board_at(board
, coord
) = color
;
789 board
->last_move
= *m
;
791 board_hash_update(board
, coord
, color
);
792 board_hash_commit(board
);
793 board_symmetry_update(board
, &board
->symmetry
, coord
);
796 return !!new_group(board
, coord
);
799 static int __attribute__((flatten
))
800 board_play_f(struct board
*board
, struct move
*m
, int f
)
803 fprintf(stderr
, "board_play(): ---- Playing %d,%d\n", coord_x(m
->coord
, board
), coord_y(m
->coord
, board
));
805 if (likely(!board_is_eyelike(board
, &m
->coord
, stone_other(m
->color
)))) {
806 /* NOT playing in an eye. Thus this move has to succeed. (This
807 * is thanks to New Zealand rules. Otherwise, multi-stone
808 * suicide might fail.) */
809 group_t group
= board_play_outside(board
, m
, f
);
810 if (unlikely(board_group_captured(board
, group
))) {
811 board_group_capture(board
, group
);
813 board_hash_commit(board
);
816 return board_play_in_eye(board
, m
, f
);
821 board_play(struct board
*board
, struct move
*m
)
823 if (unlikely(is_pass(m
->coord
) || is_resign(m
->coord
))) {
824 board
->last_move
= *m
;
829 for (f
= 0; f
< board
->flen
; f
++)
830 if (board
->f
[f
] == coord_raw(m
->coord
))
831 return board_play_f(board
, m
, f
);
834 fprintf(stderr
, "board_check: stone exists\n");
840 board_try_random_move(struct board
*b
, enum stone color
, coord_t
*coord
, int f
, ppr_permit permit
, void *permit_data
)
842 coord_raw(*coord
) = b
->f
[f
];
843 if (unlikely(is_pass(*coord
)))
845 struct move m
= { *coord
, color
};
847 fprintf(stderr
, "trying random move %d: %d,%d\n", f
, coord_x(*coord
, b
), coord_y(*coord
, b
));
848 return (likely(!board_is_one_point_eye(b
, coord
, color
)) /* bad idea to play into one, usually */
849 && (!permit
|| permit(permit_data
, b
, &m
))
850 && likely(board_play_f(b
, &m
, f
) >= 0));
854 board_play_random(struct board
*b
, enum stone color
, coord_t
*coord
, ppr_permit permit
, void *permit_data
)
856 int base
= fast_random(b
->flen
);
857 coord_pos(*coord
, base
, b
);
858 if (likely(board_try_random_move(b
, color
, coord
, base
, permit
, permit_data
)))
862 for (f
= base
+ 1; f
< b
->flen
; f
++)
863 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
865 for (f
= 0; f
< base
; f
++)
866 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
874 board_is_valid_move(struct board
*board
, struct move
*m
)
876 if (board_at(board
, m
->coord
) != S_NONE
)
878 if (!board_is_eyelike(board
, &m
->coord
, stone_other(m
->color
)))
880 /* Play within {true,false} eye-ish formation */
881 if (board
->ko
.coord
== m
->coord
&& board
->ko
.color
== m
->coord
)
883 int groups_in_atari
= 0;
884 foreach_neighbor(board
, m
->coord
, {
885 group_t g
= group_at(board
, c
);
886 groups_in_atari
+= (board_group_info(board
, g
).libs
== 1);
888 return !!groups_in_atari
;
893 board_is_eyelike(struct board
*board
, coord_t
*coord
, enum stone eye_color
)
895 return (neighbor_count_at(board
, *coord
, eye_color
)
896 + neighbor_count_at(board
, *coord
, S_OFFBOARD
)) == 4;
900 board_is_false_eyelike(struct board
*board
, coord_t
*coord
, enum stone eye_color
)
902 enum stone color_diag_libs
[S_MAX
] = {0, 0, 0, 0};
904 /* XXX: We attempt false eye detection but we will yield false
905 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
907 foreach_diag_neighbor(board
, *coord
) {
908 color_diag_libs
[(enum stone
) board_at(board
, c
)]++;
909 } foreach_diag_neighbor_end
;
910 /* For false eye, we need two enemy stones diagonally in the
911 * middle of the board, or just one enemy stone at the edge
912 * or in the corner. */
913 color_diag_libs
[stone_other(eye_color
)] += !!color_diag_libs
[S_OFFBOARD
];
914 return color_diag_libs
[stone_other(eye_color
)] >= 2;
918 board_is_one_point_eye(struct board
*board
, coord_t
*coord
, enum stone eye_color
)
920 return board_is_eyelike(board
, coord
, eye_color
)
921 && !board_is_false_eyelike(board
, coord
, eye_color
);
925 board_get_one_point_eye(struct board
*board
, coord_t
*coord
)
927 if (board_is_one_point_eye(board
, coord
, S_WHITE
))
929 else if (board_is_one_point_eye(board
, coord
, S_BLACK
))
936 int profiling_noinline
937 board_group_capture(struct board
*board
, group_t group
)
941 foreach_in_group(board
, group
) {
942 board
->captures
[stone_other(board_at(board
, c
))]++;
943 board_remove_stone(board
, c
);
945 } foreach_in_group_end
;
947 if (board_group_info(board
, group
).libs
== 1)
948 board_capturable_rm(board
, group
);
949 memset(&board_group_info(board
, group
), 0, sizeof(struct group
));
955 board_group_in_atari(struct board
*board
, group_t group
, coord_t
*lastlib
)
957 if (board_group_info(board
, group
).libs
!= 1)
959 *lastlib
= board_group_info(board
, group
).lib
[0];
964 board_group_can_atari(struct board
*board
, group_t group
, coord_t lastlib
[2])
966 if (board_group_info(board
, group
).libs
!= 2)
968 lastlib
[0] = board_group_info(board
, group
).lib
[0];
969 lastlib
[1] = board_group_info(board
, group
).lib
[1];
975 board_tromp_taylor_owner(struct board
*board
, coord_t c
)
977 int x
= coord_x(c
, board
), y
= coord_y(c
, board
);
978 enum stone color
= S_NONE
;
979 #define TEST_REACH(xx, yy) \
981 enum stone c2 = board_atxy(board, xx, yy); \
982 if (c2 != S_NONE) { \
983 if (color != S_NONE && color != c2) \
989 for (int i
= x
; i
> 0; i
--)
991 for (int i
= x
; i
< board_size(board
) - 1; i
++)
993 for (int i
= y
; i
> 0; i
--)
995 for (int i
= y
; i
< board_size(board
) - 1; i
++)
1000 /* Tromp-Taylor Counting */
1002 board_official_score(struct board
*board
)
1005 /* A point P, not colored C, is said to reach C, if there is a path of
1006 * (vertically or horizontally) adjacent points of P's color from P to
1007 * a point of color C.
1009 * A player's score is the number of points of her color, plus the
1010 * number of empty points that reach only her color. */
1013 memset(scores
, 0, sizeof(scores
));
1015 foreach_point(board
) {
1016 enum stone color
= board_at(board
, c
);
1017 if (color
== S_NONE
)
1018 color
= board_tromp_taylor_owner(board
, c
);
1020 } foreach_point_end
;
1022 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];
1026 board_fast_score(struct board
*board
)
1029 memset(scores
, 0, sizeof(scores
));
1031 foreach_point(board
) {
1032 enum stone color
= board_at(board
, c
);
1033 if (color
== S_NONE
)
1034 color
= board_get_one_point_eye(board
, &c
);
1036 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1037 } foreach_point_end
;
1039 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];
1044 is_bad_selfatari(struct board
*b
, enum stone color
, coord_t to
)
1046 //fprintf(stderr, "sar check %s %s\n", stone2str(color), coord2sstr(to, b));
1047 /* Assess if we actually gain any liberties by this escape route.
1048 * Note that this is not 100% as we cannot check whether we are
1049 * connecting out or just to ourselves. */
1050 int groupcts
[S_MAX
] = {};
1051 group_t groupids
[S_MAX
][4] = {};
1052 foreach_neighbor(b
, to
, {
1053 enum stone s
= board_at(b
, c
);
1054 groupids
[s
][groupcts
[s
]++] = group_at(b
, c
);
1057 /* More than one immediate liberty, thumbs up! */
1058 if (groupcts
[S_NONE
] > 1)
1061 /* Quickly weed out suicides. */
1062 if (board_is_one_point_eye(b
, &to
, stone_other(color
))
1063 && board_group_info(b
, groupids
[stone_other(color
)][0]).libs
> 1)
1066 /* This is set if this move puts a group out of _all_
1067 * liberties; we need to watch out for snapback then. */
1068 bool friend_has_no_libs
= false;
1069 /* We may have one liberty, but be looking for one more.
1070 * In that case, @needs_more_lib is id of group
1071 * already providing one, don't consider it again. */
1072 group_t needs_more_lib
= 0;
1073 /* ID of the first liberty, providing it again is not
1075 coord_t needs_more_lib_except
= 0;
1077 /* Examine friendly groups: */
1078 for (int i
= 0; i
< 4; i
++) {
1079 /* We can escape by connecting to this group if it's
1081 group_t g
= groupids
[color
][i
];
1084 if (board_group_info(b
, g
).libs
== 1) {
1085 if (!needs_more_lib
)
1086 friend_has_no_libs
= true;
1087 // or we already have a friend with 1 lib
1091 /* Could we self-atari the group here? */
1092 if (board_group_info(b
, g
).libs
> 2)
1095 /* We need to have another liberty, and
1096 * it must not be the other liberty of
1098 int lib2
= board_group_info(b
, g
).lib
[0];
1099 if (lib2
== to
) lib2
= board_group_info(b
, g
).lib
[1];
1100 /* Maybe we already looked at another
1101 * group providing one liberty? */
1102 if (needs_more_lib
&& needs_more_lib
!= g
1103 && needs_more_lib_except
!= lib2
)
1106 /* Can we get the liberty locally? */
1107 /* Yes if we are route to more liberties... */
1108 if (groupcts
[S_NONE
] > 1)
1110 /* ...or one liberty, but not lib2. */
1111 if (groupcts
[S_NONE
] > 0
1112 && abs(lib2
- to
) != 1
1113 && abs(lib2
- to
) != board_size(b
))
1116 /* ...ok, then we can still contribute a liberty
1117 * later by capturing something. */
1119 needs_more_lib_except
= lib2
;
1120 friend_has_no_libs
= false;
1123 //fprintf(stderr, "no friendly group\n");
1125 /* We may be able to gain a liberty by capturing this group. */
1126 group_t can_capture
= 0;
1128 /* Examine enemy groups: */
1129 for (int i
= 0; i
< 4; i
++) {
1130 /* We can escape by capturing this group if it's in atari. */
1131 group_t g
= groupids
[stone_other(color
)][i
];
1132 if (!g
|| board_group_info(b
, g
).libs
> 1)
1135 /* But we need to get to at least two liberties by this;
1136 * we already have one outside liberty, or the group is
1137 * more than 1 stone (in that case, capturing is always
1139 if (groupcts
[S_NONE
] > 0 || !group_is_onestone(b
, g
))
1141 /* ...or, it's a ko stone, */
1142 if (neighbor_count_at(b
, g
, color
) + neighbor_count_at(b
, g
, S_OFFBOARD
) == 3) {
1143 /* and we don't have a group to save: then, just taking
1144 * single stone means snapback! */
1145 if (!friend_has_no_libs
)
1148 /* ...or, we already have one indirect liberty provided
1149 * by another group. */
1150 if (needs_more_lib
|| (can_capture
&& can_capture
!= g
))
1156 //fprintf(stderr, "no cap group\n");
1158 if (!needs_more_lib
&& !can_capture
) {
1159 /* We have no hope for more fancy tactics - this move is simply
1160 * a suicide, not even a self-atari. */
1163 /* XXX: I wonder if it makes sense to continue if we actually
1164 * just !needs_more_lib. */
1166 /* There is another possibility - we can self-atari if it is
1167 * a nakade: we put an enemy group in atari from the inside. */
1168 /* This branch also allows eyes falsification:
1169 * O O O . . (This is different from throw-in to false eye
1170 * X X O O . checked below in that there is no X stone at the
1171 * X . X O . right of the star point in this diagram.)
1174 /* TODO: Allow to only nakade if the created shape is dead
1175 * (http://senseis.xmp.net/?Nakade). */
1177 /* The nakade is valid only if it's valid for all surrounding
1178 * enemy groups, thus we do the check only once - for the
1180 group_t g
= groupids
[stone_other(color
)][0];
1181 if (g
&& board_group_info(b
, g
).libs
== 2) {
1182 /* We must make sure the other liberty of that group:
1183 * (i) is an internal liberty
1184 * (ii) filling it to capture our group will not gain
1187 /* Let's look at the other liberty neighbors: */
1188 int lib2
= board_group_info(b
, g
).lib
[0];
1189 if (lib2
== to
) lib2
= board_group_info(b
, g
).lib
[1];
1190 foreach_neighbor(b
, lib2
, {
1191 /* This neighbor of course does not contribute
1192 * anything to the enemy. */
1193 if (board_at(b
, c
) == S_OFFBOARD
)
1196 /* If the other liberty has empty neighbor,
1197 * it must be the original liberty; otherwise,
1198 * since the whole group has only 2 liberties,
1199 * the other liberty may not be internal and
1200 * we are nakade'ing eyeless group from outside,
1201 * which is stupid. */
1202 if (board_at(b
, c
) == S_NONE
) {
1206 goto invalid_nakade
;
1209 int g2
= group_at(b
, c
);
1210 /* If the neighbor is of our color, it must
1211 * be our group; if it is a different group,
1212 * we won't allow the self-atari. */
1213 /* X X X X We will not allow play on 'a',
1214 * X X a X because 'b' would capture two
1215 * X O b X different groups, forming two
1217 if (board_at(b
, c
) == color
) {
1218 /* Our group == one of the groups
1219 * we (@to) are connected to. */
1221 for (j
= 0; j
< 4; j
++)
1222 if (groupids
[color
][j
] == g2
)
1225 goto invalid_nakade
;
1229 /* The neighbor is enemy color. It's ok if
1230 * it's still the same group or this is its
1232 if (g
== g2
|| board_group_info(b
, g2
).libs
== 1)
1234 /* Otherwise, it must have the exact same
1235 * liberties as the original enemy group. */
1236 if (board_group_info(b
, g2
).libs
> 2
1237 || board_group_info(b
, g2
).lib
[0] == to
1238 || board_group_info(b
, g2
).lib
[1] == to
)
1239 goto invalid_nakade
;
1242 /* Now, we must distinguish between nakade and eye
1243 * falsification; we must not falsify an eye by more
1244 * than two stones. */
1245 if (groupcts
[color
] < 1 ||
1246 (groupcts
[color
] == 1 && group_is_onestone(b
, groupids
[color
][0])))
1249 /* We would create more than 2-stone group; in that
1250 * case, the liberty of our result must be lib2,
1251 * indicating this really is a nakade. */
1252 for (int j
= 0; j
< 4; j
++) {
1253 group_t g2
= groupids
[color
][j
];
1255 assert(board_group_info(b
, g2
).libs
<= 2);
1256 if (board_group_info(b
, g2
).libs
== 2) {
1257 if (board_group_info(b
, g2
).lib
[0] != lib2
1258 && board_group_info(b
, g2
).lib
[1] != lib2
)
1259 goto invalid_nakade
;
1261 assert(board_group_info(b
, g2
).lib
[0] == to
);
1270 //fprintf(stderr, "no nakade group\n");
1272 /* We can be throwing-in to false eye:
1273 * X X X O X X X O X X X X X
1274 * X . * X * O . X * O O . X
1275 * # # # # # # # # # # # # # */
1276 /* We cannot sensibly throw-in into a corner. */
1277 if (neighbor_count_at(b
, to
, S_OFFBOARD
) < 2
1278 && neighbor_count_at(b
, to
, stone_other(color
))
1279 + neighbor_count_at(b
, to
, S_OFFBOARD
) == 3
1280 && board_is_false_eyelike(b
, &to
, stone_other(color
))) {
1281 assert(groupcts
[color
] <= 1);
1282 /* Single-stone throw-in may be ok... */
1283 if (groupcts
[color
] == 0) {
1284 /* O X . There is one problem - when it's
1285 * . * X actually not a throw-in!
1287 foreach_neighbor(b
, to
, {
1288 if (board_at(b
, c
) == S_NONE
) {
1289 /* Is the empty neighbor an escape path? */
1290 /* (Note that one S_NONE neighbor is already @to.) */
1291 if (neighbor_count_at(b
, c
, stone_other(color
))
1292 + neighbor_count_at(b
, c
, S_OFFBOARD
) < 2)
1293 goto invalid_throwin
;
1299 /* Multi-stone throwin...? */
1300 assert(groupcts
[color
] == 1);
1301 group_t g
= groupids
[color
][0];
1303 assert(board_group_info(b
, g
).libs
<= 2);
1304 /* Suicide is definitely NOT ok, no matter what else
1306 if (board_group_info(b
, g
).libs
== 1)
1309 /* In that case, we must be connected to at most one stone,
1310 * or throwin will not destroy any eyes. */
1311 if (group_is_onestone(b
, g
))
1316 //fprintf(stderr, "no throw-in group\n");
1318 /* No way to pull out, no way to connect out. This really
1319 * is a bad self-atari! */
1325 board_stone_radar(struct board
*b
, coord_t coord
, int distance
)
1328 coord_x(coord
, b
) - distance
,
1329 coord_y(coord
, b
) - distance
,
1330 coord_x(coord
, b
) + distance
,
1331 coord_y(coord
, b
) + distance
1333 for (int i
= 0; i
< 4; i
++)
1336 else if (bounds
[i
] > board_size(b
) - 2)
1337 bounds
[i
] = board_size(b
) - 2;
1338 for (int x
= bounds
[0]; x
<= bounds
[2]; x
++)
1339 for (int y
= bounds
[1]; y
<= bounds
[3]; y
++)
1340 if (board_atxy(b
, x
, y
) != S_NONE
) {
1341 //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));