13 #include "patternsp.h"
16 bool random_pass
= false;
20 #define profiling_noinline __attribute__((noinline))
22 #define profiling_noinline
25 #define gi_granularity 4
26 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
30 board_setup(struct board
*b
)
32 memset(b
, 0, sizeof(*b
));
34 struct move m
= { pass
, S_NONE
};
35 b
->last_move
= b
->last_move2
= b
->last_ko
= b
->ko
= m
;
41 struct board
*b
= malloc(sizeof(struct board
));
52 board_copy(struct board
*b2
, struct board
*b1
)
54 memcpy(b2
, b1
, sizeof(struct board
));
56 int bsize
= board_size2(b2
) * sizeof(*b2
->b
);
57 int gsize
= board_size2(b2
) * sizeof(*b2
->g
);
58 int fsize
= board_size2(b2
) * sizeof(*b2
->f
);
59 int nsize
= board_size2(b2
) * sizeof(*b2
->n
);
60 int psize
= board_size2(b2
) * sizeof(*b2
->p
);
61 int hsize
= board_size2(b2
) * 2 * sizeof(*b2
->h
);
62 int gisize
= board_size2(b2
) * sizeof(*b2
->gi
);
64 int csize
= board_size2(b2
) * sizeof(*b2
->c
);
69 int ssize
= board_size2(b2
) * sizeof(*b2
->spathash
);
73 void *x
= malloc(bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
+ ssize
);
74 memcpy(x
, b1
->b
, bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
+ ssize
);
75 b2
->b
= x
; x
+= bsize
;
76 b2
->g
= x
; x
+= gsize
;
77 b2
->f
= x
; x
+= fsize
;
78 b2
->p
= x
; x
+= psize
;
79 b2
->n
= x
; x
+= nsize
;
80 b2
->h
= x
; x
+= hsize
;
81 b2
->gi
= x
; x
+= gisize
;
83 b2
->c
= x
; x
+= csize
;
86 b2
->spathash
= x
; x
+= ssize
;
93 board_done_noalloc(struct board
*board
)
95 if (board
->b
) free(board
->b
);
99 board_done(struct board
*board
)
101 board_done_noalloc(board
);
106 board_resize(struct board
*board
, int size
)
109 assert(board_size(board
) == size
+ 2);
111 board_size(board
) = size
+ 2 /* S_OFFBOARD margin */;
112 board_size2(board
) = board_size(board
) * board_size(board
);
117 int bsize
= board_size2(board
) * sizeof(*board
->b
);
118 int gsize
= board_size2(board
) * sizeof(*board
->g
);
119 int fsize
= board_size2(board
) * sizeof(*board
->f
);
120 int nsize
= board_size2(board
) * sizeof(*board
->n
);
121 int psize
= board_size2(board
) * sizeof(*board
->p
);
122 int hsize
= board_size2(board
) * 2 * sizeof(*board
->h
);
123 int gisize
= board_size2(board
) * sizeof(*board
->gi
);
125 int csize
= board_size2(board
) * sizeof(*board
->c
);
129 #ifdef BOARD_SPATHASH
130 int ssize
= board_size2(board
) * sizeof(*board
->spathash
);
134 void *x
= malloc(bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
+ ssize
);
135 memset(x
, 0, bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
+ ssize
);
136 board
->b
= x
; x
+= bsize
;
137 board
->g
= x
; x
+= gsize
;
138 board
->f
= x
; x
+= fsize
;
139 board
->p
= x
; x
+= psize
;
140 board
->n
= x
; x
+= nsize
;
141 board
->h
= x
; x
+= hsize
;
142 board
->gi
= x
; x
+= gisize
;
144 board
->c
= x
; x
+= csize
;
146 #ifdef BOARD_SPATHASH
147 board
->spathash
= x
; x
+= ssize
;
152 board_clear(struct board
*board
)
154 int size
= board_size(board
);
155 float komi
= board
->komi
;
157 board_done_noalloc(board
);
159 board_resize(board
, size
- 2 /* S_OFFBOARD margin */);
163 /* Setup initial symmetry */
164 board
->symmetry
.d
= 1;
165 board
->symmetry
.x1
= board
->symmetry
.y1
= board_size(board
) / 2;
166 board
->symmetry
.x2
= board
->symmetry
.y2
= board_size(board
) - 1;
167 board
->symmetry
.type
= SYM_FULL
;
169 /* Draw the offboard margin */
170 int top_row
= board_size2(board
) - board_size(board
);
172 for (i
= 0; i
< board_size(board
); i
++)
173 board
->b
[i
] = board
->b
[top_row
+ i
] = S_OFFBOARD
;
174 for (i
= 0; i
<= top_row
; i
+= board_size(board
))
175 board
->b
[i
] = board
->b
[board_size(board
) - 1 + i
] = S_OFFBOARD
;
177 foreach_point(board
) {
179 if (board_at(board
, coord
) == S_OFFBOARD
)
181 foreach_neighbor(board
, c
, {
182 inc_neighbor_count_at(board
, coord
, board_at(board
, c
));
186 /* First, pass is always a free position. */
187 board
->f
[board
->flen
++] = coord_raw(pass
);
188 /* All positions are free! Except the margin. */
189 for (i
= board_size(board
); i
< (board_size(board
) - 1) * board_size(board
); i
++)
190 if (i
% board_size(board
) != 0 && i
% board_size(board
) != board_size(board
) - 1)
191 board
->f
[board
->flen
++] = i
;
193 /* Initialize zobrist hashtable. */
194 foreach_point(board
) {
195 int max
= (sizeof(hash_t
) << history_hash_bits
);
196 /* fast_random() is 16-bit only */
197 board
->h
[coord_raw(c
) * 2] = ((hash_t
) fast_random(max
))
198 | ((hash_t
) fast_random(max
) << 16)
199 | ((hash_t
) fast_random(max
) << 32)
200 | ((hash_t
) fast_random(max
) << 48);
201 if (!board
->h
[coord_raw(c
) * 2])
202 /* Would be kinda "oops". */
203 board
->h
[coord_raw(c
) * 2] = 1;
204 /* And once again for white */
205 board
->h
[coord_raw(c
) * 2 + 1] = ((hash_t
) fast_random(max
))
206 | ((hash_t
) fast_random(max
) << 16)
207 | ((hash_t
) fast_random(max
) << 32)
208 | ((hash_t
) fast_random(max
) << 48);
209 if (!board
->h
[coord_raw(c
) * 2 + 1])
210 board
->h
[coord_raw(c
) * 2 + 1] = 1;
213 #ifdef BOARD_SPATHASH
214 /* Initialize spatial hashes. */
215 foreach_point(board
) {
216 for (int d
= 1; d
<= BOARD_SPATHASH_MAXD
; d
++) {
217 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
218 int x
= coord_x(c
, board
) + ptcoords
[j
].x
;
219 int y
= coord_y(c
, board
) + ptcoords
[j
].y
;
220 if (x
>= board_size(board
)) x
= board_size(board
) - 1; else if (x
< 0) x
= 0;
221 if (y
>= board_size(board
)) y
= board_size(board
) - 1; else if (y
< 0) y
= 0;
222 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1] ^=
223 pthashes
[0][j
][board_at(board
, c
)];
232 board_print_top(struct board
*board
, FILE *f
, int c
)
234 for (int i
= 0; i
< c
; i
++) {
235 char asdf
[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
237 for (int x
= 1; x
< board_size(board
) - 1; x
++)
238 fprintf(f
, "%c ", asdf
[x
- 1]);
242 for (int i
= 0; i
< c
; i
++) {
244 for (int x
= 1; x
< board_size(board
) - 1; x
++)
252 board_print_bottom(struct board
*board
, FILE *f
, int c
)
254 for (int i
= 0; i
< c
; i
++) {
256 for (int x
= 1; x
< board_size(board
) - 1; x
++)
264 board_print_row(struct board
*board
, int y
, FILE *f
, board_cprint cprint
)
266 fprintf(f
, " %2d | ", y
);
267 for (int x
= 1; x
< board_size(board
) - 1; x
++) {
268 if (coord_x(board
->last_move
.coord
, board
) == x
&& coord_y(board
->last_move
.coord
, board
) == y
)
269 fprintf(f
, "%c)", stone2char(board_atxy(board
, x
, y
)));
271 fprintf(f
, "%c ", stone2char(board_atxy(board
, x
, y
)));
275 fprintf(f
, " %2d | ", y
);
276 for (int x
= 1; x
< board_size(board
) - 1; x
++) {
277 cprint(board
, coord_xy(board
, x
, y
), f
);
285 board_print_custom(struct board
*board
, FILE *f
, board_cprint cprint
)
287 fprintf(f
, "Move: % 3d Komi: %2.1f Handicap: %d Captures B: %d W: %d\n",
288 board
->moves
, board
->komi
, board
->handicap
,
289 board
->captures
[S_BLACK
], board
->captures
[S_WHITE
]);
290 board_print_top(board
, f
, 1 + !!cprint
);
291 for (int y
= board_size(board
) - 2; y
>= 1; y
--)
292 board_print_row(board
, y
, f
, cprint
);
293 board_print_bottom(board
, f
, 1 + !!cprint
);
298 cprint_group(struct board
*board
, coord_t c
, FILE *f
)
300 fprintf(f
, "%d ", group_base(group_at(board
, c
)));
304 board_print(struct board
*board
, FILE *f
)
306 board_print_custom(board
, f
, DEBUGL(6) ? cprint_group
: NULL
);
310 /* Update board hash with given coordinate. */
311 static void profiling_noinline
312 board_hash_update(struct board
*board
, coord_t coord
, enum stone color
)
314 board
->hash
^= hash_at(board
, coord
, color
);
316 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
);
318 #ifdef BOARD_SPATHASH
319 /* Gridcular metric is reflective, so we update all hashes
320 * of appropriate ditance in OUR circle. */
321 for (int d
= 1; d
<= BOARD_SPATHASH_MAXD
; d
++) {
322 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
323 int x
= coord_x(coord
, board
) + ptcoords
[j
].x
;
324 int y
= coord_y(coord
, board
) + ptcoords
[j
].y
;
325 if (x
>= board_size(board
)) x
= board_size(board
) - 1; else if (x
< 0) x
= 0;
326 if (y
>= board_size(board
)) y
= board_size(board
) - 1; else if (y
< 0) y
= 0;
327 /* We either changed from S_NONE to color
328 * or vice versa; doesn't matter. */
329 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1] ^=
330 pthashes
[0][j
][color
] ^ pthashes
[0][j
][S_NONE
];
336 /* Commit current board hash to history. */
337 static void profiling_noinline
338 board_hash_commit(struct board
*board
)
341 fprintf(stderr
, "board_hash_commit %"PRIhash
"\n", board
->hash
);
342 if (likely(board
->history_hash
[board
->hash
& history_hash_mask
]) == 0) {
343 board
->history_hash
[board
->hash
& history_hash_mask
] = board
->hash
;
345 hash_t i
= board
->hash
;
346 while (board
->history_hash
[i
& history_hash_mask
]) {
347 if (board
->history_hash
[i
& history_hash_mask
] == board
->hash
) {
349 fprintf(stderr
, "SUPERKO VIOLATION noted at %d,%d\n",
350 coord_x(board
->last_move
.coord
, board
), coord_y(board
->last_move
.coord
, board
));
351 board
->superko_violation
= true;
354 i
= history_hash_next(i
);
356 board
->history_hash
[i
& history_hash_mask
] = board
->hash
;
362 board_symmetry_update(struct board
*b
, struct board_symmetry
*symmetry
, coord_t c
)
364 if (likely(symmetry
->type
== SYM_NONE
)) {
365 /* Fully degenerated already. We do not support detection
366 * of restoring of symmetry, assuming that this is too rare
367 * a case to handle. */
371 int x
= coord_x(c
, b
), y
= coord_y(c
, b
), t
= board_size(b
) / 2;
372 int dx
= board_size(b
) - 1 - x
; /* for SYM_DOWN */
374 fprintf(stderr
, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
375 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
376 symmetry
->d
, symmetry
->type
, x
, y
);
379 switch (symmetry
->type
) {
381 if (x
== t
&& y
== t
) {
382 /* Tengen keeps full symmetry. */
385 /* New symmetry now? */
387 symmetry
->type
= SYM_DIAG_UP
;
388 symmetry
->x1
= symmetry
->y1
= 1;
389 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
391 } else if (dx
== y
) {
392 symmetry
->type
= SYM_DIAG_DOWN
;
393 symmetry
->x1
= symmetry
->y1
= 1;
394 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
397 symmetry
->type
= SYM_HORIZ
;
399 symmetry
->y2
= board_size(b
) - 1;
402 symmetry
->type
= SYM_VERT
;
404 symmetry
->x2
= board_size(b
) - 1;
408 symmetry
->type
= SYM_NONE
;
409 symmetry
->x1
= symmetry
->y1
= 1;
410 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
436 fprintf(stderr
, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
437 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
438 symmetry
->d
, symmetry
->type
);
445 board_handicap_stone(struct board
*board
, int x
, int y
, FILE *f
)
448 m
.color
= S_BLACK
; m
.coord
= coord_xy(board
, x
, y
);
450 board_play(board
, &m
);
451 /* Simulate white passing; otherwise, UCT search can get confused since
452 * tree depth parity won't match the color to move. */
455 char *str
= coord2str(m
.coord
, board
);
457 fprintf(stderr
, "choosing handicap %s (%d,%d)\n", str
, x
, y
);
458 fprintf(f
, "%s ", str
);
463 board_handicap(struct board
*board
, int stones
, FILE *f
)
465 int margin
= 3 + (board_size(board
) >= 13);
467 int mid
= board_size(board
) / 2;
468 int max
= board_size(board
) - 1 - margin
;
469 const int places
[][2] = {
470 { min
, min
}, { max
, max
}, { max
, min
}, { min
, max
},
471 { min
, mid
}, { max
, mid
},
472 { mid
, min
}, { mid
, max
},
476 board
->handicap
= stones
;
478 if (stones
== 5 || stones
== 7) {
479 board_handicap_stone(board
, mid
, mid
, f
);
484 for (i
= 0; i
< stones
; i
++)
485 board_handicap_stone(board
, places
[i
][0], places
[i
][1], f
);
489 static void __attribute__((noinline
))
490 check_libs_consistency(struct board
*board
, group_t g
)
494 struct group
*gi
= &board_group_info(board
, g
);
495 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
496 if (gi
->lib
[i
] && board_at(board
, gi
->lib
[i
]) != S_NONE
) {
497 fprintf(stderr
, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi
->lib
[i
], board
), g
, coord2sstr(group_base(g
), board
));
504 board_capturable_add(struct board
*board
, group_t group
)
507 //fprintf(stderr, "add of group %d (%d)\n", group_base(group), board->clen);
509 assert(board
->clen
< board_size2(board
));
510 board
->c
[board
->clen
++] = group
;
514 board_capturable_rm(struct board
*board
, group_t group
)
517 //fprintf(stderr, "rm of group %d\n", group_base(group));
518 for (int i
= 0; i
< board
->clen
; i
++) {
519 if (unlikely(board
->c
[i
] == group
)) {
520 board
->c
[i
] = board
->c
[--board
->clen
];
524 fprintf(stderr
, "rm of bad group %d\n", group_base(group
));
530 board_group_addlib(struct board
*board
, group_t group
, coord_t coord
)
533 fprintf(stderr
, "Group %d[%s] %d: Adding liberty %s\n",
534 group_base(group
), coord2sstr(group_base(group
), board
),
535 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
538 check_libs_consistency(board
, group
);
540 struct group
*gi
= &board_group_info(board
, group
);
541 if (gi
->libs
< GROUP_KEEP_LIBS
) {
542 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
544 /* Seems extra branch just slows it down */
548 if (unlikely(gi
->lib
[i
] == coord
))
552 board_capturable_add(board
, group
);
553 else if (gi
->libs
== 1)
554 board_capturable_rm(board
, group
);
555 gi
->lib
[gi
->libs
++] = coord
;
558 check_libs_consistency(board
, group
);
562 board_group_find_extra_libs(struct board
*board
, group_t group
, struct group
*gi
, coord_t avoid
)
564 /* Add extra liberty from the board to our liberty list. */
565 unsigned char watermark
[board_size2(board
) / 8];
566 memset(watermark
, 0, sizeof(watermark
));
567 #define watermark_get(c) (watermark[coord_raw(c) >> 3] & (1 << (coord_raw(c) & 7)))
568 #define watermark_set(c) watermark[coord_raw(c) >> 3] |= (1 << (coord_raw(c) & 7))
570 for (int i
= 0; i
< GROUP_KEEP_LIBS
- 1; i
++)
571 watermark_set(gi
->lib
[i
]);
572 watermark_set(avoid
);
574 foreach_in_group(board
, group
) {
576 foreach_neighbor(board
, coord2
, {
577 if (board_at(board
, c
) + watermark_get(c
) != S_NONE
)
580 gi
->lib
[gi
->libs
++] = c
;
581 if (unlikely(gi
->libs
>= GROUP_KEEP_LIBS
))
584 } foreach_in_group_end
;
590 board_group_rmlib(struct board
*board
, group_t group
, coord_t coord
)
593 fprintf(stderr
, "Group %d[%s] %d: Removing liberty %s\n",
594 group_base(group
), coord2sstr(group_base(group
), board
),
595 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
598 struct group
*gi
= &board_group_info(board
, group
);
599 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
601 /* Seems extra branch just slows it down */
605 if (likely(gi
->lib
[i
] != coord
))
608 gi
->lib
[i
] = gi
->lib
[--gi
->libs
];
609 gi
->lib
[gi
->libs
] = 0;
611 check_libs_consistency(board
, group
);
613 /* Postpone refilling lib[] until we need to. */
614 assert(GROUP_REFILL_LIBS
> 1);
615 if (gi
->libs
> GROUP_REFILL_LIBS
)
617 if (gi
->libs
== GROUP_REFILL_LIBS
)
618 board_group_find_extra_libs(board
, group
, gi
, coord
);
621 board_capturable_add(board
, group
);
622 else if (gi
->libs
== 0)
623 board_capturable_rm(board
, group
);
627 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
628 * can call this multiple times per coord. */
629 check_libs_consistency(board
, group
);
634 /* This is a low-level routine that doesn't maintain consistency
635 * of all the board data structures. */
637 board_remove_stone(struct board
*board
, coord_t c
)
639 enum stone color
= board_at(board
, c
);
640 board_at(board
, c
) = S_NONE
;
641 group_at(board
, c
) = 0;
642 board_hash_update(board
, c
, color
);
644 /* Increase liberties of surrounding groups */
646 foreach_neighbor(board
, coord
, {
647 dec_neighbor_count_at(board
, c
, color
);
648 group_t g
= group_at(board
, c
);
650 board_group_addlib(board
, g
, coord
);
654 fprintf(stderr
, "pushing free move [%d]: %d,%d\n", board
->flen
, coord_x(c
, board
), coord_y(c
, board
));
655 board
->f
[board
->flen
++] = coord_raw(c
);
658 static int profiling_noinline
659 board_group_capture(struct board
*board
, group_t group
)
663 foreach_in_group(board
, group
) {
664 board
->captures
[stone_other(board_at(board
, c
))]++;
665 board_remove_stone(board
, c
);
667 } foreach_in_group_end
;
669 if (board_group_info(board
, group
).libs
== 1)
670 board_capturable_rm(board
, group
);
671 memset(&board_group_info(board
, group
), 0, sizeof(struct group
));
677 static void profiling_noinline
678 add_to_group(struct board
*board
, group_t group
, coord_t prevstone
, coord_t coord
)
680 foreach_neighbor(board
, coord
, {
681 if (board_at(board
, c
) == S_NONE
)
682 board_group_addlib(board
, group
, c
);
685 group_at(board
, coord
) = group
;
686 groupnext_at(board
, coord
) = groupnext_at(board
, prevstone
);
687 groupnext_at(board
, prevstone
) = coord_raw(coord
);
690 fprintf(stderr
, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
691 coord_x(prevstone
, board
), coord_y(prevstone
, board
),
692 coord_x(coord
, board
), coord_y(coord
, board
),
693 groupnext_at(board
, coord
) % board_size(board
), groupnext_at(board
, coord
) / board_size(board
),
697 static void profiling_noinline
698 merge_groups(struct board
*board
, group_t group_to
, group_t group_from
)
701 fprintf(stderr
, "board_play_raw: merging groups %d -> %d\n",
702 group_base(group_from
), group_base(group_to
));
704 coord_t last_in_group
;
705 foreach_in_group(board
, group_from
) {
707 group_at(board
, c
) = group_to
;
708 } foreach_in_group_end
;
709 groupnext_at(board
, last_in_group
) = groupnext_at(board
, group_base(group_to
));
710 groupnext_at(board
, group_base(group_to
)) = group_base(group_from
);
712 struct group
*gi_from
= &board_group_info(board
, group_from
);
713 struct group
*gi_to
= &board_group_info(board
, group_to
);
714 if (gi_to
->libs
< GROUP_KEEP_LIBS
) {
715 for (int i
= 0; i
< gi_from
->libs
; i
++) {
716 for (int j
= 0; j
< gi_to
->libs
; j
++)
717 if (gi_to
->lib
[j
] == gi_from
->lib
[i
])
719 if (gi_to
->libs
== 0)
720 board_capturable_add(board
, group_to
);
721 else if (gi_to
->libs
== 1)
722 board_capturable_rm(board
, group_to
);
723 gi_to
->lib
[gi_to
->libs
++] = gi_from
->lib
[i
];
724 if (gi_to
->libs
>= GROUP_KEEP_LIBS
)
730 if (gi_from
->libs
== 1)
731 board_capturable_rm(board
, group_from
);
732 memset(gi_from
, 0, sizeof(struct group
));
735 fprintf(stderr
, "board_play_raw: merged group: %d\n",
736 group_base(group_to
));
739 static group_t profiling_noinline
740 new_group(struct board
*board
, coord_t coord
)
742 group_t group
= coord_raw(coord
);
743 struct group
*gi
= &board_group_info(board
, group
);
744 foreach_neighbor(board
, coord
, {
745 if (board_at(board
, c
) == S_NONE
)
746 /* board_group_addlib is ridiculously expensive for us */
747 #if GROUP_KEEP_LIBS < 4
748 if (gi
->libs
< GROUP_KEEP_LIBS
)
750 gi
->lib
[gi
->libs
++] = c
;
753 board_capturable_add(board
, group
);
754 check_libs_consistency(board
, group
);
756 group_at(board
, coord
) = group
;
757 groupnext_at(board
, coord
) = 0;
760 fprintf(stderr
, "new_group: added %d,%d to group %d\n",
761 coord_x(coord
, board
), coord_y(coord
, board
),
767 static inline group_t
768 play_one_neighbor(struct board
*board
,
769 coord_t coord
, enum stone color
, enum stone other_color
,
770 coord_t c
, group_t group
)
772 enum stone ncolor
= board_at(board
, c
);
773 group_t ngroup
= group_at(board
, c
);
775 inc_neighbor_count_at(board
, c
, color
);
780 board_group_rmlib(board
, ngroup
, coord
);
782 fprintf(stderr
, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
783 group_base(ngroup
), ncolor
, color
, other_color
);
785 if (ncolor
== color
&& ngroup
!= group
) {
788 add_to_group(board
, group
, c
, coord
);
790 merge_groups(board
, group
, ngroup
);
792 } else if (ncolor
== other_color
) {
794 struct group
*gi
= &board_group_info(board
, ngroup
);
795 fprintf(stderr
, "testing captured group %d[%s]: ", group_base(ngroup
), coord2sstr(group_base(ngroup
), board
));
796 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
797 fprintf(stderr
, "%s ", coord2sstr(gi
->lib
[i
], board
));
798 fprintf(stderr
, "\n");
800 if (unlikely(board_group_captured(board
, ngroup
)))
801 board_group_capture(board
, ngroup
);
806 /* We played on a place with at least one liberty. We will become a member of
807 * some group for sure. */
808 static group_t profiling_noinline
809 board_play_outside(struct board
*board
, struct move
*m
, int f
)
811 coord_t coord
= m
->coord
;
812 enum stone color
= m
->color
;
813 enum stone other_color
= stone_other(color
);
816 board
->f
[f
] = board
->f
[--board
->flen
];
818 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
820 foreach_neighbor(board
, coord
, {
821 group
= play_one_neighbor(board
, coord
, color
, other_color
, c
, group
);
824 if (unlikely(!group
))
825 group
= new_group(board
, coord
);
827 board_at(board
, coord
) = color
;
828 board
->last_move2
= board
->last_move
;
829 board
->last_move
= *m
;
831 board_hash_update(board
, coord
, color
);
832 board_symmetry_update(board
, &board
->symmetry
, coord
);
833 struct move ko
= { pass
, S_NONE
};
839 /* We played in an eye-like shape. Either we capture at least one of the eye
840 * sides in the process of playing, or return -1. */
841 static int profiling_noinline
842 board_play_in_eye(struct board
*board
, struct move
*m
, int f
)
844 coord_t coord
= m
->coord
;
845 enum stone color
= m
->color
;
846 /* Check ko: Capture at a position of ko capture one move ago */
847 if (unlikely(color
== board
->ko
.color
&& coord_eq(coord
, board
->ko
.coord
))) {
849 fprintf(stderr
, "board_check: ko at %d,%d color %d\n", coord_x(coord
, board
), coord_y(coord
, board
), color
);
851 } else if (DEBUGL(6)) {
852 fprintf(stderr
, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
853 color
, coord_x(coord
, board
), coord_y(coord
, board
),
854 board
->ko
.color
, coord_x(board
->ko
.coord
, board
), coord_y(board
->ko
.coord
, board
));
857 struct move ko
= { pass
, S_NONE
};
859 int captured_groups
= 0;
861 foreach_neighbor(board
, coord
, {
862 group_t g
= group_at(board
, c
);
864 fprintf(stderr
, "board_check: group %d has %d libs\n",
865 g
, board_group_info(board
, g
).libs
);
866 captured_groups
+= (board_group_info(board
, g
).libs
== 1);
869 if (likely(captured_groups
== 0)) {
872 board_print(board
, stderr
);
873 fprintf(stderr
, "board_check: one-stone suicide\n");
879 board
->f
[f
] = board
->f
[--board
->flen
];
881 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
883 foreach_neighbor(board
, coord
, {
884 inc_neighbor_count_at(board
, c
, color
);
886 group_t group
= group_at(board
, c
);
890 board_group_rmlib(board
, group
, coord
);
892 fprintf(stderr
, "board_play_raw: reducing libs for group %d\n",
895 if (board_group_captured(board
, group
)) {
896 if (board_group_capture(board
, group
) == 1) {
897 /* If we captured multiple groups at once,
898 * we can't be fighting ko so we don't need
899 * to check for that. */
900 ko
.color
= stone_other(color
);
903 board
->last_ko_age
= board
->moves
;
905 fprintf(stderr
, "guarding ko at %d,%s\n", ko
.color
, coord2sstr(ko
.coord
, board
));
910 board_at(board
, coord
) = color
;
912 board
->last_move2
= board
->last_move
;
913 board
->last_move
= *m
;
915 board_hash_update(board
, coord
, color
);
916 board_hash_commit(board
);
917 board_symmetry_update(board
, &board
->symmetry
, coord
);
920 return !!new_group(board
, coord
);
923 static int __attribute__((flatten
))
924 board_play_f(struct board
*board
, struct move
*m
, int f
)
927 fprintf(stderr
, "board_play(): ---- Playing %d,%d\n", coord_x(m
->coord
, board
), coord_y(m
->coord
, board
));
929 if (likely(!board_is_eyelike(board
, &m
->coord
, stone_other(m
->color
)))) {
930 /* NOT playing in an eye. Thus this move has to succeed. (This
931 * is thanks to New Zealand rules. Otherwise, multi-stone
932 * suicide might fail.) */
933 group_t group
= board_play_outside(board
, m
, f
);
934 if (unlikely(board_group_captured(board
, group
))) {
935 board_group_capture(board
, group
);
937 board_hash_commit(board
);
940 return board_play_in_eye(board
, m
, f
);
945 board_play(struct board
*board
, struct move
*m
)
947 if (unlikely(is_pass(m
->coord
) || is_resign(m
->coord
))) {
948 board
->last_move2
= board
->last_move
;
949 board
->last_move
= *m
;
954 for (f
= 0; f
< board
->flen
; f
++)
955 if (board
->f
[f
] == coord_raw(m
->coord
))
956 return board_play_f(board
, m
, f
);
959 fprintf(stderr
, "board_check: stone exists\n");
965 board_try_random_move(struct board
*b
, enum stone color
, coord_t
*coord
, int f
, ppr_permit permit
, void *permit_data
)
967 coord_raw(*coord
) = b
->f
[f
];
968 if (unlikely(is_pass(*coord
)))
970 struct move m
= { *coord
, color
};
972 fprintf(stderr
, "trying random move %d: %d,%d\n", f
, coord_x(*coord
, b
), coord_y(*coord
, b
));
973 return (likely(!board_is_one_point_eye(b
, coord
, color
)) /* bad idea to play into one, usually */
974 && board_is_valid_move(b
, &m
)
975 && (!permit
|| permit(permit_data
, b
, &m
))
976 && likely(board_play_f(b
, &m
, f
) >= 0));
980 board_play_random(struct board
*b
, enum stone color
, coord_t
*coord
, ppr_permit permit
, void *permit_data
)
982 int base
= fast_random(b
->flen
);
983 coord_pos(*coord
, base
, b
);
984 if (likely(board_try_random_move(b
, color
, coord
, base
, permit
, permit_data
)))
988 for (f
= base
+ 1; f
< b
->flen
; f
++)
989 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
991 for (f
= 0; f
< base
; f
++)
992 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
1000 board_is_false_eyelike(struct board
*board
, coord_t
*coord
, enum stone eye_color
)
1002 enum stone color_diag_libs
[S_MAX
] = {0, 0, 0, 0};
1004 /* XXX: We attempt false eye detection but we will yield false
1005 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
1007 foreach_diag_neighbor(board
, *coord
) {
1008 color_diag_libs
[(enum stone
) board_at(board
, c
)]++;
1009 } foreach_diag_neighbor_end
;
1010 /* For false eye, we need two enemy stones diagonally in the
1011 * middle of the board, or just one enemy stone at the edge
1012 * or in the corner. */
1013 color_diag_libs
[stone_other(eye_color
)] += !!color_diag_libs
[S_OFFBOARD
];
1014 return color_diag_libs
[stone_other(eye_color
)] >= 2;
1018 board_is_one_point_eye(struct board
*board
, coord_t
*coord
, enum stone eye_color
)
1020 return board_is_eyelike(board
, coord
, eye_color
)
1021 && !board_is_false_eyelike(board
, coord
, eye_color
);
1025 board_get_one_point_eye(struct board
*board
, coord_t
*coord
)
1027 if (board_is_one_point_eye(board
, coord
, S_WHITE
))
1029 else if (board_is_one_point_eye(board
, coord
, S_BLACK
))
1037 board_fast_score(struct board
*board
)
1040 memset(scores
, 0, sizeof(scores
));
1042 foreach_point(board
) {
1043 enum stone color
= board_at(board
, c
);
1044 if (color
== S_NONE
)
1045 color
= board_get_one_point_eye(board
, &c
);
1047 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1048 } foreach_point_end
;
1050 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];
1053 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1055 /* One flood-fill iteration; returns true if next iteration
1058 board_tromp_taylor_iter(struct board
*board
, int *ownermap
)
1060 bool needs_update
= false;
1061 foreach_point(board
) {
1062 /* Ignore occupied and already-dame positions. */
1063 if (board_at(board
, c
) != S_NONE
|| ownermap
[c
] == 3)
1065 /* Count neighbors. */
1067 foreach_neighbor(board
, c
, {
1070 /* If we have neighbors of both colors, or dame,
1071 * we are dame too. */
1072 if ((nei
[1] && nei
[2]) || nei
[3]) {
1074 /* Speed up the propagation. */
1075 foreach_neighbor(board
, c
, {
1076 if (board_at(board
, c
) == S_NONE
)
1079 needs_update
= true;
1082 /* If we have neighbors of one color, we are owned
1083 * by that color, too. */
1084 if (!ownermap
[c
] && (nei
[1] || nei
[2])) {
1085 int newowner
= nei
[1] ? 1 : 2;
1086 ownermap
[c
] = newowner
;
1087 /* Speed up the propagation. */
1088 foreach_neighbor(board
, c
, {
1089 if (board_at(board
, c
) == S_NONE
&& !ownermap
[c
])
1090 ownermap
[c
] = newowner
;
1092 needs_update
= true;
1095 } foreach_point_end
;
1096 return needs_update
;
1099 /* Tromp-Taylor Counting */
1101 board_official_score(struct board
*board
, struct move_queue
*q
)
1104 /* A point P, not colored C, is said to reach C, if there is a path of
1105 * (vertically or horizontally) adjacent points of P's color from P to
1106 * a point of color C.
1108 * A player's score is the number of points of her color, plus the
1109 * number of empty points that reach only her color. */
1111 int ownermap
[board_size2(board
)];
1113 const int o
[4] = {0, 1, 2, 0};
1114 foreach_point(board
) {
1115 ownermap
[c
] = o
[board_at(board
, c
)];
1116 s
[board_at(board
, c
)]++;
1117 } foreach_point_end
;
1120 /* Process dead groups. */
1121 for (int i
= 0; i
< q
->moves
; i
++) {
1122 foreach_in_group(board
, q
->move
[i
]) {
1123 enum stone color
= board_at(board
, c
);
1124 ownermap
[c
] = o
[stone_other(color
)];
1125 s
[color
]--; s
[stone_other(color
)]++;
1126 } foreach_in_group_end
;
1130 /* We need to special-case empty board. */
1131 if (!s
[S_BLACK
] && !s
[S_WHITE
])
1132 return board
->komi
+ board
->handicap
;
1134 while (board_tromp_taylor_iter(board
, ownermap
))
1135 /* Flood-fill... */;
1138 memset(scores
, 0, sizeof(scores
));
1140 foreach_point(board
) {
1141 assert(board_at(board
, c
) == S_OFFBOARD
|| ownermap
[c
] != 0);
1142 if (ownermap
[c
] == 3)
1144 scores
[ownermap
[c
]]++;
1145 } foreach_point_end
;
1147 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];