13 #include "patternsp.h"
19 static void board_trait_recompute(struct board
*board
, coord_t coord
);
28 #define profiling_noinline __attribute__((noinline))
30 #define profiling_noinline
33 #define gi_granularity 4
34 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
38 board_setup(struct board
*b
)
40 memset(b
, 0, sizeof(*b
));
42 struct move m
= { pass
, S_NONE
};
43 b
->last_move
= b
->last_move2
= b
->last_ko
= b
->ko
= m
;
49 struct board
*b
= malloc2(sizeof(struct board
));
60 board_copy(struct board
*b2
, struct board
*b1
)
62 memcpy(b2
, b1
, sizeof(struct board
));
64 int bsize
= board_size2(b2
) * sizeof(*b2
->b
);
65 int gsize
= board_size2(b2
) * sizeof(*b2
->g
);
66 int fsize
= board_size2(b2
) * sizeof(*b2
->f
);
67 int nsize
= board_size2(b2
) * sizeof(*b2
->n
);
68 int psize
= board_size2(b2
) * sizeof(*b2
->p
);
69 int hsize
= board_size2(b2
) * 2 * sizeof(*b2
->h
);
70 int gisize
= board_size2(b2
) * sizeof(*b2
->gi
);
72 int csize
= board_size2(b2
) * sizeof(*b2
->c
);
77 int ssize
= board_size2(b2
) * sizeof(*b2
->spathash
);
82 int p3size
= board_size2(b2
) * sizeof(*b2
->pat3
);
87 int tsize
= board_size2(b2
) * sizeof(*b2
->t
);
88 int tqsize
= board_size2(b2
) * sizeof(*b2
->t
);
94 int pbsize
= board_size2(b2
) * sizeof(*b2
->prob
[0].items
);
98 int cdsize
= board_size2(b2
) * sizeof(*b2
->coord
);
99 void *x
= malloc2(bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
+ ssize
+ p3size
+ tsize
+ tqsize
+ pbsize
* 2 + cdsize
);
100 memcpy(x
, b1
->b
, bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
+ ssize
+ p3size
+ tsize
+ tqsize
+ pbsize
* 2 + cdsize
);
101 b2
->b
= x
; x
+= bsize
;
102 b2
->g
= x
; x
+= gsize
;
103 b2
->f
= x
; x
+= fsize
;
104 b2
->p
= x
; x
+= psize
;
105 b2
->n
= x
; x
+= nsize
;
106 b2
->h
= x
; x
+= hsize
;
107 b2
->gi
= x
; x
+= gisize
;
109 b2
->c
= x
; x
+= csize
;
111 #ifdef BOARD_SPATHASH
112 b2
->spathash
= x
; x
+= ssize
;
115 b2
->pat3
= x
; x
+= p3size
;
118 b2
->t
= x
; x
+= tsize
;
119 b2
->tq
= x
; x
+= tqsize
;
122 b2
->prob
[0].items
= x
; x
+= pbsize
;
123 b2
->prob
[1].items
= x
; x
+= pbsize
;
125 b2
->coord
= x
; x
+= cdsize
;
131 board_done_noalloc(struct board
*board
)
133 if (board
->b
) free(board
->b
);
137 board_done(struct board
*board
)
139 board_done_noalloc(board
);
144 board_resize(struct board
*board
, int size
)
147 assert(board_size(board
) == size
+ 2);
149 board
->size
= size
+ 2 /* S_OFFBOARD margin */;
150 board
->size2
= board_size(board
) * board_size(board
);
153 while ((1 << board
->bits2
) < board
->size2
) board
->bits2
++;
158 int bsize
= board_size2(board
) * sizeof(*board
->b
);
159 int gsize
= board_size2(board
) * sizeof(*board
->g
);
160 int fsize
= board_size2(board
) * sizeof(*board
->f
);
161 int nsize
= board_size2(board
) * sizeof(*board
->n
);
162 int psize
= board_size2(board
) * sizeof(*board
->p
);
163 int hsize
= board_size2(board
) * 2 * sizeof(*board
->h
);
164 int gisize
= board_size2(board
) * sizeof(*board
->gi
);
166 int csize
= board_size2(board
) * sizeof(*board
->c
);
170 #ifdef BOARD_SPATHASH
171 int ssize
= board_size2(board
) * sizeof(*board
->spathash
);
176 int p3size
= board_size2(board
) * sizeof(*board
->pat3
);
181 int tsize
= board_size2(board
) * sizeof(*board
->t
);
182 int tqsize
= board_size2(board
) * sizeof(*board
->t
);
188 int pbsize
= board_size2(board
) * sizeof(*board
->prob
[0].items
);
192 int cdsize
= board_size2(board
) * sizeof(*board
->coord
);
193 void *x
= malloc2(bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
+ ssize
+ p3size
+ tsize
+ tqsize
+ pbsize
* 2 + cdsize
);
194 memset(x
, 0, bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
+ ssize
+ p3size
+ tsize
+ tqsize
+ pbsize
* 2 + cdsize
);
195 board
->b
= x
; x
+= bsize
;
196 board
->g
= x
; x
+= gsize
;
197 board
->f
= x
; x
+= fsize
;
198 board
->p
= x
; x
+= psize
;
199 board
->n
= x
; x
+= nsize
;
200 board
->h
= x
; x
+= hsize
;
201 board
->gi
= x
; x
+= gisize
;
203 board
->c
= x
; x
+= csize
;
205 #ifdef BOARD_SPATHASH
206 board
->spathash
= x
; x
+= ssize
;
209 board
->pat3
= x
; x
+= p3size
;
212 board
->t
= x
; x
+= tsize
;
213 board
->tq
= x
; x
+= tqsize
;
216 board
->prob
[0].items
= x
; x
+= pbsize
;
217 board
->prob
[1].items
= x
; x
+= pbsize
;
219 board
->coord
= x
; x
+= cdsize
;
223 board_clear(struct board
*board
)
225 int size
= board_size(board
);
226 float komi
= board
->komi
;
228 board_done_noalloc(board
);
230 board_resize(board
, size
- 2 /* S_OFFBOARD margin */);
234 /* Setup neighborhood iterators */
235 board
->nei8
[0] = -size
- 1; // (-1,-1)
238 board
->nei8
[3] = size
- 2; // (-1,0)
240 board
->nei8
[5] = size
- 2; // (-1,1)
243 board
->dnei
[0] = -size
- 1;
245 board
->dnei
[2] = size
*2 - 2;
248 /* Setup initial symmetry */
249 board
->symmetry
.d
= 1;
250 board
->symmetry
.x1
= board
->symmetry
.y1
= board_size(board
) / 2;
251 board
->symmetry
.x2
= board
->symmetry
.y2
= board_size(board
) - 1;
252 board
->symmetry
.type
= SYM_FULL
;
254 /* Set up coordinate cache */
255 foreach_point(board
) {
256 board
->coord
[c
][0] = c
% board_size(board
);
257 board
->coord
[c
][1] = c
/ board_size(board
);
260 /* Draw the offboard margin */
261 int top_row
= board_size2(board
) - board_size(board
);
263 for (i
= 0; i
< board_size(board
); i
++)
264 board
->b
[i
] = board
->b
[top_row
+ i
] = S_OFFBOARD
;
265 for (i
= 0; i
<= top_row
; i
+= board_size(board
))
266 board
->b
[i
] = board
->b
[board_size(board
) - 1 + i
] = S_OFFBOARD
;
268 foreach_point(board
) {
270 if (board_at(board
, coord
) == S_OFFBOARD
)
272 foreach_neighbor(board
, c
, {
273 inc_neighbor_count_at(board
, coord
, board_at(board
, c
));
277 /* All positions are free! Except the margin. */
278 for (i
= board_size(board
); i
< (board_size(board
) - 1) * board_size(board
); i
++)
279 if (i
% board_size(board
) != 0 && i
% board_size(board
) != board_size(board
) - 1)
280 board
->f
[board
->flen
++] = i
;
282 /* Initialize zobrist hashtable. */
283 foreach_point(board
) {
284 int max
= (sizeof(hash_t
) << history_hash_bits
);
285 /* fast_random() is 16-bit only */
286 board
->h
[c
* 2] = ((hash_t
) fast_random(max
))
287 | ((hash_t
) fast_random(max
) << 16)
288 | ((hash_t
) fast_random(max
) << 32)
289 | ((hash_t
) fast_random(max
) << 48);
290 if (!board
->h
[c
* 2])
291 /* Would be kinda "oops". */
293 /* And once again for white */
294 board
->h
[c
* 2 + 1] = ((hash_t
) fast_random(max
))
295 | ((hash_t
) fast_random(max
) << 16)
296 | ((hash_t
) fast_random(max
) << 32)
297 | ((hash_t
) fast_random(max
) << 48);
298 if (!board
->h
[c
* 2 + 1])
299 board
->h
[c
* 2 + 1] = 1;
302 #ifdef BOARD_SPATHASH
303 /* Initialize spatial hashes. */
304 foreach_point(board
) {
305 for (int d
= 1; d
<= BOARD_SPATHASH_MAXD
; d
++) {
306 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
307 ptcoords_at(x
, y
, c
, board
, j
);
308 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][0] ^=
309 pthashes
[0][j
][board_at(board
, c
)];
310 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][1] ^=
311 pthashes
[0][j
][stone_other(board_at(board
, c
))];
317 /* Initialize 3x3 pattern codes. */
318 foreach_point(board
) {
319 if (board_at(board
, c
) == S_NONE
)
320 board
->pat3
[c
] = pattern3_hash(board
, c
);
324 /* Initialize traits. */
325 foreach_point(board
) {
326 trait_at(board
, c
, S_BLACK
).cap
= 0;
327 trait_at(board
, c
, S_BLACK
).safe
= true;
328 trait_at(board
, c
, S_WHITE
).cap
= 0;
329 trait_at(board
, c
, S_WHITE
).safe
= true;
333 board
->prob
[0].n
= board
->prob
[1].n
= board_size2(board
);
334 foreach_point(board
) {
335 probdist_set(&board
->prob
[0], c
, (board_at(board
, c
) == S_NONE
) * 1.0f
);
336 probdist_set(&board
->prob
[1], c
, (board_at(board
, c
) == S_NONE
) * 1.0f
);
342 board_print_top(struct board
*board
, char *s
, char *end
, int c
)
344 for (int i
= 0; i
< c
; i
++) {
345 char asdf
[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
346 s
+= snprintf(s
, end
- s
, " ");
347 for (int x
= 1; x
< board_size(board
) - 1; x
++)
348 s
+= snprintf(s
, end
- s
, "%c ", asdf
[x
- 1]);
349 s
+= snprintf(s
, end
-s
, " ");
351 s
+= snprintf(s
, end
- s
, "\n");
352 for (int i
= 0; i
< c
; i
++) {
353 s
+= snprintf(s
, end
- s
, " +-");
354 for (int x
= 1; x
< board_size(board
) - 1; x
++)
355 s
+= snprintf(s
, end
- s
, "--");
356 s
+= snprintf(s
, end
- s
, "+");
358 s
+= snprintf(s
, end
- s
, "\n");
363 board_print_bottom(struct board
*board
, char *s
, char *end
, int c
)
365 for (int i
= 0; i
< c
; i
++) {
366 s
+= snprintf(s
, end
- s
, " +-");
367 for (int x
= 1; x
< board_size(board
) - 1; x
++)
368 s
+= snprintf(s
, end
- s
, "--");
369 s
+= snprintf(s
, end
- s
, "+");
371 s
+= snprintf(s
, end
- s
, "\n");
376 board_print_row(struct board
*board
, int y
, char *s
, char *end
, board_cprint cprint
)
378 s
+= snprintf(s
, end
- s
, " %2d | ", y
);
379 for (int x
= 1; x
< board_size(board
) - 1; x
++) {
380 if (coord_x(board
->last_move
.coord
, board
) == x
&& coord_y(board
->last_move
.coord
, board
) == y
)
381 s
+= snprintf(s
, end
- s
, "%c)", stone2char(board_atxy(board
, x
, y
)));
383 s
+= snprintf(s
, end
- s
, "%c ", stone2char(board_atxy(board
, x
, y
)));
385 s
+= snprintf(s
, end
- s
, "|");
387 s
+= snprintf(s
, end
- s
, " %2d | ", y
);
388 for (int x
= 1; x
< board_size(board
) - 1; x
++) {
389 s
= cprint(board
, coord_xy(board
, x
, y
), s
, end
);
391 s
+= snprintf(s
, end
- s
, "|");
393 s
+= snprintf(s
, end
- s
, "\n");
398 board_print_custom(struct board
*board
, FILE *f
, board_cprint cprint
)
402 char *end
= buf
+ sizeof(buf
);
403 s
+= snprintf(s
, end
- s
, "Move: % 3d Komi: %2.1f Handicap: %d Captures B: %d W: %d\n",
404 board
->moves
, board
->komi
, board
->handicap
,
405 board
->captures
[S_BLACK
], board
->captures
[S_WHITE
]);
406 s
= board_print_top(board
, s
, end
, 1 + !!cprint
);
407 for (int y
= board_size(board
) - 2; y
>= 1; y
--)
408 s
= board_print_row(board
, y
, s
, end
, cprint
);
409 board_print_bottom(board
, s
, end
, 1 + !!cprint
);
410 fprintf(f
, "%s\n", buf
);
414 cprint_group(struct board
*board
, coord_t c
, char *s
, char *end
)
416 s
+= snprintf(s
, end
- s
, "%d ", group_base(group_at(board
, c
)));
421 board_print(struct board
*board
, FILE *f
)
423 board_print_custom(board
, f
, DEBUGL(6) ? cprint_group
: NULL
);
427 board_gamma_set(struct board
*b
, struct features_gamma
*gamma
, bool precise_selfatari
)
431 b
->precise_selfatari
= precise_selfatari
;
432 for (int i
= 0; i
< b
->flen
; i
++) {
433 board_trait_recompute(b
, b
->f
[i
]);
439 /* Update the probability distribution we maintain incrementally. */
441 board_gamma_update(struct board
*board
, coord_t coord
, enum stone color
)
447 /* Punch out invalid moves and moves filling our own eyes. */
448 if (board_at(board
, coord
) != S_NONE
449 || (board_is_eyelike(board
, coord
, stone_other(color
))
450 && !trait_at(board
, coord
, color
).cap
)
451 || (board_is_one_point_eye(board
, coord
, color
))) {
452 probdist_set(&board
->prob
[color
- 1], coord
, 0);
456 int pat
= board
->pat3
[coord
];
457 if (color
== S_WHITE
) {
458 /* We work with the pattern3s as black-to-play. */
459 pat
= pattern3_reverse(pat
);
462 /* We just quickly replicate the general pattern matcher stuff
463 * here in the most bare-bone way. */
464 double value
= board
->gamma
->gamma
[FEAT_PATTERN3
][pat
];
465 if (trait_at(board
, coord
, color
).cap
)
466 value
*= board
->gamma
->gamma
[FEAT_CAPTURE
][0];
467 if (trait_at(board
, coord
, stone_other(color
)).cap
468 && trait_at(board
, coord
, color
).safe
)
469 value
*= board
->gamma
->gamma
[FEAT_AESCAPE
][0];
470 if (!trait_at(board
, coord
, color
).safe
)
471 value
*= board
->gamma
->gamma
[FEAT_SELFATARI
][1 + board
->precise_selfatari
];
472 probdist_set(&board
->prob
[color
- 1], coord
, value
);
478 board_trait_safe(struct board
*board
, coord_t coord
, enum stone color
)
481 if (board
->precise_selfatari
)
482 return is_bad_selfatari(board
, color
, coord
);
484 return board_safe_to_play(board
, coord
, color
);
488 board_trait_recompute(struct board
*board
, coord_t coord
)
490 trait_at(board
, coord
, S_BLACK
).safe
= board_trait_safe(board
, coord
, S_BLACK
);;
491 trait_at(board
, coord
, S_WHITE
).safe
= board_trait_safe(board
, coord
, S_WHITE
);
493 fprintf(stderr
, "traits[%s:%s lib=%d] (black cap=%d safe=%d) (white cap=%d safe=%d)\n",
494 coord2sstr(coord
, board
), stone2str(board_at(board
, coord
)), immediate_liberty_count(board
, coord
),
495 trait_at(board
, coord
, S_BLACK
).cap
, trait_at(board
, coord
, S_BLACK
).safe
,
496 trait_at(board
, coord
, S_WHITE
).cap
, trait_at(board
, coord
, S_WHITE
).safe
);
498 board_gamma_update(board
, coord
, S_BLACK
);
499 board_gamma_update(board
, coord
, S_WHITE
);
503 /* Recompute traits for dirty points that we have previously touched
504 * somehow (libs of their neighbors changed or so). */
506 board_traits_recompute(struct board
*board
)
509 for (int i
= 0; i
< board
->tqlen
; i
++) {
510 coord_t coord
= board
->tq
[i
];
511 if (!trait_at(board
, coord
, S_BLACK
).dirty
) continue;
512 if (board_at(board
, coord
) != S_NONE
) continue;
513 board_trait_recompute(board
, coord
);
514 trait_at(board
, coord
, S_BLACK
).dirty
= false;
520 /* Queue traits of given point for recomputing. */
522 board_trait_queue(struct board
*board
, coord_t coord
)
525 board
->tq
[board
->tqlen
++] = coord
;
526 trait_at(board
, coord
, S_BLACK
).dirty
= true;
531 /* Update board hash with given coordinate. */
532 static void profiling_noinline
533 board_hash_update(struct board
*board
, coord_t coord
, enum stone color
)
535 board
->hash
^= hash_at(board
, coord
, color
);
537 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
);
539 #ifdef BOARD_SPATHASH
540 /* Gridcular metric is reflective, so we update all hashes
541 * of appropriate ditance in OUR circle. */
542 for (int d
= 1; d
<= BOARD_SPATHASH_MAXD
; d
++) {
543 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
544 ptcoords_at(x
, y
, coord
, board
, j
);
545 /* We either changed from S_NONE to color
546 * or vice versa; doesn't matter. */
547 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][0] ^=
548 pthashes
[0][j
][color
] ^ pthashes
[0][j
][S_NONE
];
549 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][1] ^=
550 pthashes
[0][j
][stone_other(color
)] ^ pthashes
[0][j
][S_NONE
];
555 #if defined(BOARD_PAT3)
556 /* @color is not what we need in case of capture. */
557 enum stone new_color
= board_at(board
, coord
);
558 if (new_color
== S_NONE
)
559 board
->pat3
[coord
] = pattern3_hash(board
, coord
);
560 foreach_8neighbor(board
, coord
) { // internally, the loop uses fn__i=[0..7]
561 if (board_at(board
, c
) != S_NONE
)
563 board
->pat3
[c
] &= ~(3 << (fn__i
*2));
564 board
->pat3
[c
] |= new_color
<< (fn__i
*2);
566 if (board_at(board
, c
) != S_OFFBOARD
&& pattern3_hash(board
, c
) != board
->pat3
[c
]) {
567 board_print(board
, stderr
);
568 fprintf(stderr
, "%s->%s %x != %x (%d-%d:%d)\n", coord2sstr(coord
, board
), coord2sstr(c
, board
), pattern3_hash(board
, c
), board
->pat3
[c
], coord
, c
, fn__i
);
572 board_gamma_update(board
, c
, S_BLACK
);
573 board_gamma_update(board
, c
, S_WHITE
);
574 } foreach_8neighbor_end
;
578 /* Commit current board hash to history. */
579 static void profiling_noinline
580 board_hash_commit(struct board
*board
)
583 fprintf(stderr
, "board_hash_commit %"PRIhash
"\n", board
->hash
);
584 if (likely(board
->history_hash
[board
->hash
& history_hash_mask
]) == 0) {
585 board
->history_hash
[board
->hash
& history_hash_mask
] = board
->hash
;
587 hash_t i
= board
->hash
;
588 while (board
->history_hash
[i
& history_hash_mask
]) {
589 if (board
->history_hash
[i
& history_hash_mask
] == board
->hash
) {
591 fprintf(stderr
, "SUPERKO VIOLATION noted at %d,%d\n",
592 coord_x(board
->last_move
.coord
, board
), coord_y(board
->last_move
.coord
, board
));
593 board
->superko_violation
= true;
596 i
= history_hash_next(i
);
598 board
->history_hash
[i
& history_hash_mask
] = board
->hash
;
604 board_symmetry_update(struct board
*b
, struct board_symmetry
*symmetry
, coord_t c
)
606 if (likely(symmetry
->type
== SYM_NONE
)) {
607 /* Fully degenerated already. We do not support detection
608 * of restoring of symmetry, assuming that this is too rare
609 * a case to handle. */
613 int x
= coord_x(c
, b
), y
= coord_y(c
, b
), t
= board_size(b
) / 2;
614 int dx
= board_size(b
) - 1 - x
; /* for SYM_DOWN */
616 fprintf(stderr
, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
617 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
618 symmetry
->d
, symmetry
->type
, x
, y
);
621 switch (symmetry
->type
) {
623 if (x
== t
&& y
== t
) {
624 /* Tengen keeps full symmetry. */
627 /* New symmetry now? */
629 symmetry
->type
= SYM_DIAG_UP
;
630 symmetry
->x1
= symmetry
->y1
= 1;
631 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
633 } else if (dx
== y
) {
634 symmetry
->type
= SYM_DIAG_DOWN
;
635 symmetry
->x1
= symmetry
->y1
= 1;
636 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
639 symmetry
->type
= SYM_HORIZ
;
641 symmetry
->y2
= board_size(b
) - 1;
644 symmetry
->type
= SYM_VERT
;
646 symmetry
->x2
= board_size(b
) - 1;
650 symmetry
->type
= SYM_NONE
;
651 symmetry
->x1
= symmetry
->y1
= 1;
652 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
678 fprintf(stderr
, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
679 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
680 symmetry
->d
, symmetry
->type
);
687 board_handicap_stone(struct board
*board
, int x
, int y
, FILE *f
)
690 m
.color
= S_BLACK
; m
.coord
= coord_xy(board
, x
, y
);
692 board_play(board
, &m
);
693 /* Simulate white passing; otherwise, UCT search can get confused since
694 * tree depth parity won't match the color to move. */
697 char *str
= coord2str(m
.coord
, board
);
699 fprintf(stderr
, "choosing handicap %s (%d,%d)\n", str
, x
, y
);
700 if (f
) fprintf(f
, "%s ", str
);
705 board_handicap(struct board
*board
, int stones
, FILE *f
)
707 int margin
= 3 + (board_size(board
) >= 13);
709 int mid
= board_size(board
) / 2;
710 int max
= board_size(board
) - 1 - margin
;
711 const int places
[][2] = {
712 { min
, min
}, { max
, max
}, { max
, min
}, { min
, max
},
713 { min
, mid
}, { max
, mid
},
714 { mid
, min
}, { mid
, max
},
718 board
->handicap
= stones
;
720 if (stones
== 5 || stones
== 7) {
721 board_handicap_stone(board
, mid
, mid
, f
);
726 for (i
= 0; i
< stones
; i
++)
727 board_handicap_stone(board
, places
[i
][0], places
[i
][1], f
);
731 static void __attribute__((noinline
))
732 check_libs_consistency(struct board
*board
, group_t g
)
736 struct group
*gi
= &board_group_info(board
, g
);
737 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
738 if (gi
->lib
[i
] && board_at(board
, gi
->lib
[i
]) != S_NONE
) {
739 fprintf(stderr
, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi
->lib
[i
], board
), g
, coord2sstr(group_base(g
), board
));
746 board_capturable_add(struct board
*board
, group_t group
, coord_t lib
)
748 //fprintf(stderr, "group %s cap %s\n", coord2sstr(group, board), coord2sstr(lib, boarD));
750 /* Increase capturable count trait of my last lib. */
751 enum stone capturing_color
= stone_other(board_at(board
, group
));
752 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
753 foreach_neighbor(board
, lib
, {
754 if (DEBUGL(8) && group_at(board
, c
) == group
)
755 fprintf(stderr
, "%s[%d] %s cap bump bc of %s(%d) member %s\n", coord2sstr(lib
, board
), trait_at(board
, lib
, capturing_color
).cap
, stone2str(capturing_color
), coord2sstr(group
, board
), board_group_info(board
, group
).libs
, coord2sstr(c
, board
));
756 trait_at(board
, lib
, capturing_color
).cap
+= (group_at(board
, c
) == group
);
758 board_trait_queue(board
, lib
);
762 /* Update the list of capturable groups. */
764 assert(board
->clen
< board_size2(board
));
765 board
->c
[board
->clen
++] = group
;
769 board_capturable_rm(struct board
*board
, group_t group
, coord_t lib
)
771 //fprintf(stderr, "group %s nocap %s\n", coord2sstr(group, board), coord2sstr(lib, board));
773 /* Decrease capturable count trait of my previously-last lib. */
774 enum stone capturing_color
= stone_other(board_at(board
, group
));
775 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
776 foreach_neighbor(board
, lib
, {
777 if (DEBUGL(8) && group_at(board
, c
) == group
)
778 fprintf(stderr
, "%s[%d] cap dump bc of %s(%d) member %s\n", coord2sstr(lib
, board
), trait_at(board
, lib
, capturing_color
).cap
, coord2sstr(group
, board
), board_group_info(board
, group
).libs
, coord2sstr(c
, board
));
779 trait_at(board
, lib
, capturing_color
).cap
-= (group_at(board
, c
) == group
);
781 board_trait_queue(board
, lib
);
785 /* Update the list of capturable groups. */
786 for (int i
= 0; i
< board
->clen
; i
++) {
787 if (unlikely(board
->c
[i
] == group
)) {
788 board
->c
[i
] = board
->c
[--board
->clen
];
792 fprintf(stderr
, "rm of bad group %d\n", group_base(group
));
798 board_atariable_add(struct board
*board
, group_t group
, coord_t lib1
, coord_t lib2
)
801 board_trait_queue(board
, lib1
);
802 board_trait_queue(board
, lib2
);
806 board_atariable_rm(struct board
*board
, group_t group
, coord_t lib1
, coord_t lib2
)
809 board_trait_queue(board
, lib1
);
810 board_trait_queue(board
, lib2
);
815 board_group_addlib(struct board
*board
, group_t group
, coord_t coord
)
818 fprintf(stderr
, "Group %d[%s] %d: Adding liberty %s\n",
819 group_base(group
), coord2sstr(group_base(group
), board
),
820 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
823 check_libs_consistency(board
, group
);
825 struct group
*gi
= &board_group_info(board
, group
);
826 if (gi
->libs
< GROUP_KEEP_LIBS
) {
827 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
829 /* Seems extra branch just slows it down */
833 if (unlikely(gi
->lib
[i
] == coord
))
837 board_capturable_add(board
, group
, coord
);
838 } else if (gi
->libs
== 1) {
839 board_capturable_rm(board
, group
, gi
->lib
[0]);
840 board_atariable_add(board
, group
, gi
->lib
[0], coord
);
841 } else if (gi
->libs
== 2) {
842 board_atariable_rm(board
, group
, gi
->lib
[0], gi
->lib
[1]);
844 gi
->lib
[gi
->libs
++] = coord
;
847 check_libs_consistency(board
, group
);
851 board_group_find_extra_libs(struct board
*board
, group_t group
, struct group
*gi
, coord_t avoid
)
853 /* Add extra liberty from the board to our liberty list. */
854 unsigned char watermark
[board_size2(board
) / 8];
855 memset(watermark
, 0, sizeof(watermark
));
856 #define watermark_get(c) (watermark[c >> 3] & (1 << (c & 7)))
857 #define watermark_set(c) watermark[c >> 3] |= (1 << (c & 7))
859 for (int i
= 0; i
< GROUP_KEEP_LIBS
- 1; i
++)
860 watermark_set(gi
->lib
[i
]);
861 watermark_set(avoid
);
863 foreach_in_group(board
, group
) {
865 foreach_neighbor(board
, coord2
, {
866 if (board_at(board
, c
) + watermark_get(c
) != S_NONE
)
869 gi
->lib
[gi
->libs
++] = c
;
870 if (unlikely(gi
->libs
>= GROUP_KEEP_LIBS
))
873 } foreach_in_group_end
;
879 board_group_rmlib(struct board
*board
, group_t group
, coord_t coord
)
882 fprintf(stderr
, "Group %d[%s] %d: Removing liberty %s\n",
883 group_base(group
), coord2sstr(group_base(group
), board
),
884 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
887 struct group
*gi
= &board_group_info(board
, group
);
888 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
890 /* Seems extra branch just slows it down */
894 if (likely(gi
->lib
[i
] != coord
))
897 coord_t lib
= gi
->lib
[i
] = gi
->lib
[--gi
->libs
];
898 gi
->lib
[gi
->libs
] = 0;
900 check_libs_consistency(board
, group
);
902 /* Postpone refilling lib[] until we need to. */
903 assert(GROUP_REFILL_LIBS
> 1);
904 if (gi
->libs
> GROUP_REFILL_LIBS
)
906 if (gi
->libs
== GROUP_REFILL_LIBS
)
907 board_group_find_extra_libs(board
, group
, gi
, coord
);
910 board_atariable_add(board
, group
, gi
->lib
[0], gi
->lib
[1]);
911 } else if (gi
->libs
== 1) {
912 board_capturable_add(board
, group
, gi
->lib
[0]);
913 board_atariable_rm(board
, group
, gi
->lib
[0], lib
);
914 } else if (gi
->libs
== 0)
915 board_capturable_rm(board
, group
, lib
);
919 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
920 * can call this multiple times per coord. */
921 check_libs_consistency(board
, group
);
926 /* This is a low-level routine that doesn't maintain consistency
927 * of all the board data structures. */
929 board_remove_stone(struct board
*board
, group_t group
, coord_t c
)
931 enum stone color
= board_at(board
, c
);
932 board_at(board
, c
) = S_NONE
;
933 group_at(board
, c
) = 0;
934 board_hash_update(board
, c
, color
);
936 /* We mark as cannot-capture now. If this is a ko/snapback,
937 * we will get incremented later in board_group_addlib(). */
938 trait_at(board
, c
, S_BLACK
).cap
= 0;
939 trait_at(board
, c
, S_WHITE
).cap
= 0;
940 board_trait_queue(board
, c
);
943 /* Increase liberties of surrounding groups */
945 foreach_neighbor(board
, coord
, {
946 dec_neighbor_count_at(board
, c
, color
);
947 board_trait_queue(board
, c
);
948 group_t g
= group_at(board
, c
);
950 board_group_addlib(board
, g
, coord
);
954 fprintf(stderr
, "pushing free move [%d]: %d,%d\n", board
->flen
, coord_x(c
, board
), coord_y(c
, board
));
955 board
->f
[board
->flen
++] = c
;
958 static int profiling_noinline
959 board_group_capture(struct board
*board
, group_t group
)
963 foreach_in_group(board
, group
) {
964 board
->captures
[stone_other(board_at(board
, c
))]++;
965 board_remove_stone(board
, group
, c
);
967 } foreach_in_group_end
;
969 struct group
*gi
= &board_group_info(board
, group
);
971 board_atariable_rm(board
, group
, gi
->lib
[0], gi
->lib
[1]);
972 else if (gi
->libs
== 1)
973 board_capturable_rm(board
, group
, gi
->lib
[0]);
974 memset(gi
, 0, sizeof(*gi
));
980 static void profiling_noinline
981 add_to_group(struct board
*board
, group_t group
, coord_t prevstone
, coord_t coord
)
983 group_at(board
, coord
) = group
;
984 groupnext_at(board
, coord
) = groupnext_at(board
, prevstone
);
985 groupnext_at(board
, prevstone
) = coord
;
988 if (board_group_info(board
, group
).libs
== 1) {
989 /* Our group is temporarily in atari; make sure the capturable
990 * counts also correspond to the newly added stone before we
991 * start adding liberties again so bump-dump ops match. */
992 enum stone capturing_color
= stone_other(board_at(board
, group
));
993 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
994 coord_t lib
= board_group_info(board
, group
).lib
[0];
995 if (coord_is_adjecent(lib
, coord
, board
)) {
996 if (DEBUGL(8)) fprintf(stderr
, "add_to_group %s: %s[%d] bump\n", coord2sstr(group
, board
), coord2sstr(lib
, board
), trait_at(board
, lib
, capturing_color
).cap
);
997 trait_at(board
, lib
, capturing_color
).cap
++;
998 board_trait_queue(board
, lib
);
1003 foreach_neighbor(board
, coord
, {
1004 if (board_at(board
, c
) == S_NONE
)
1005 board_group_addlib(board
, group
, c
);
1009 fprintf(stderr
, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
1010 coord_x(prevstone
, board
), coord_y(prevstone
, board
),
1011 coord_x(coord
, board
), coord_y(coord
, board
),
1012 groupnext_at(board
, coord
) % board_size(board
), groupnext_at(board
, coord
) / board_size(board
),
1016 static void profiling_noinline
1017 merge_groups(struct board
*board
, group_t group_to
, group_t group_from
)
1020 fprintf(stderr
, "board_play_raw: merging groups %d -> %d\n",
1021 group_base(group_from
), group_base(group_to
));
1022 struct group
*gi_from
= &board_group_info(board
, group_from
);
1023 struct group
*gi_to
= &board_group_info(board
, group_to
);
1025 /* We do this early before the group info is rewritten. */
1026 if (gi_from
->libs
== 2)
1027 board_atariable_rm(board
, group_from
, gi_from
->lib
[0], gi_from
->lib
[1]);
1028 else if (gi_from
->libs
== 1)
1029 board_capturable_rm(board
, group_from
, gi_from
->lib
[0]);
1032 fprintf(stderr
,"---- (froml %d, tol %d)\n", gi_from
->libs
, gi_to
->libs
);
1034 if (gi_to
->libs
< GROUP_KEEP_LIBS
) {
1035 for (int i
= 0; i
< gi_from
->libs
; i
++) {
1036 for (int j
= 0; j
< gi_to
->libs
; j
++)
1037 if (gi_to
->lib
[j
] == gi_from
->lib
[i
])
1039 if (gi_to
->libs
== 0) {
1040 board_capturable_add(board
, group_to
, gi_from
->lib
[i
]);
1041 } else if (gi_to
->libs
== 1) {
1042 board_capturable_rm(board
, group_to
, gi_to
->lib
[0]);
1043 board_atariable_add(board
, group_to
, gi_to
->lib
[0], gi_from
->lib
[i
]);
1044 } else if (gi_to
->libs
== 2) {
1045 board_atariable_rm(board
, group_to
, gi_to
->lib
[0], gi_to
->lib
[1]);
1047 gi_to
->lib
[gi_to
->libs
++] = gi_from
->lib
[i
];
1048 if (gi_to
->libs
>= GROUP_KEEP_LIBS
)
1055 if (board_group_info(board
, group_to
).libs
== 1) {
1056 /* Our group is currently in atari; make sure we properly
1057 * count in even the neighbors from the other group in the
1058 * capturable counter. */
1059 enum stone capturing_color
= stone_other(board_at(board
, group_to
));
1060 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
1061 coord_t lib
= board_group_info(board
, group_to
).lib
[0];
1062 foreach_neighbor(board
, lib
, {
1063 if (DEBUGL(8) && group_at(board
, c
) == group_from
) fprintf(stderr
, "%s[%d] cap bump\n", coord2sstr(lib
, board
), trait_at(board
, lib
, capturing_color
).cap
);
1064 trait_at(board
, lib
, capturing_color
).cap
+= (group_at(board
, c
) == group_from
);
1066 board_trait_queue(board
, lib
);
1070 coord_t last_in_group
;
1071 foreach_in_group(board
, group_from
) {
1073 group_at(board
, c
) = group_to
;
1074 } foreach_in_group_end
;
1075 groupnext_at(board
, last_in_group
) = groupnext_at(board
, group_base(group_to
));
1076 groupnext_at(board
, group_base(group_to
)) = group_base(group_from
);
1077 memset(gi_from
, 0, sizeof(struct group
));
1080 fprintf(stderr
, "board_play_raw: merged group: %d\n",
1081 group_base(group_to
));
1084 static group_t profiling_noinline
1085 new_group(struct board
*board
, coord_t coord
)
1087 group_t group
= coord
;
1088 struct group
*gi
= &board_group_info(board
, group
);
1089 foreach_neighbor(board
, coord
, {
1090 if (board_at(board
, c
) == S_NONE
)
1091 /* board_group_addlib is ridiculously expensive for us */
1092 #if GROUP_KEEP_LIBS < 4
1093 if (gi
->libs
< GROUP_KEEP_LIBS
)
1095 gi
->lib
[gi
->libs
++] = c
;
1098 group_at(board
, coord
) = group
;
1099 groupnext_at(board
, coord
) = 0;
1102 board_atariable_add(board
, group
, gi
->lib
[0], gi
->lib
[1]);
1103 else if (gi
->libs
== 1)
1104 board_capturable_add(board
, group
, gi
->lib
[0]);
1105 check_libs_consistency(board
, group
);
1108 fprintf(stderr
, "new_group: added %d,%d to group %d\n",
1109 coord_x(coord
, board
), coord_y(coord
, board
),
1115 static inline group_t
1116 play_one_neighbor(struct board
*board
,
1117 coord_t coord
, enum stone color
, enum stone other_color
,
1118 coord_t c
, group_t group
)
1120 enum stone ncolor
= board_at(board
, c
);
1121 group_t ngroup
= group_at(board
, c
);
1123 inc_neighbor_count_at(board
, c
, color
);
1124 /* We can be S_NONE, in that case we need to update the safety
1125 * trait since we might be left with only one liberty. */
1126 board_trait_queue(board
, c
);
1131 board_group_rmlib(board
, ngroup
, coord
);
1133 fprintf(stderr
, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
1134 group_base(ngroup
), ncolor
, color
, other_color
);
1136 if (ncolor
== color
&& ngroup
!= group
) {
1139 add_to_group(board
, group
, c
, coord
);
1141 merge_groups(board
, group
, ngroup
);
1143 } else if (ncolor
== other_color
) {
1145 struct group
*gi
= &board_group_info(board
, ngroup
);
1146 fprintf(stderr
, "testing captured group %d[%s]: ", group_base(ngroup
), coord2sstr(group_base(ngroup
), board
));
1147 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
1148 fprintf(stderr
, "%s ", coord2sstr(gi
->lib
[i
], board
));
1149 fprintf(stderr
, "\n");
1151 if (unlikely(board_group_captured(board
, ngroup
)))
1152 board_group_capture(board
, ngroup
);
1157 /* We played on a place with at least one liberty. We will become a member of
1158 * some group for sure. */
1159 static group_t profiling_noinline
1160 board_play_outside(struct board
*board
, struct move
*m
, int f
)
1162 coord_t coord
= m
->coord
;
1163 enum stone color
= m
->color
;
1164 enum stone other_color
= stone_other(color
);
1167 board
->f
[f
] = board
->f
[--board
->flen
];
1169 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
1171 #if defined(BOARD_TRAITS) && defined(DEBUG)
1172 /* Sanity check that cap matches reality. */
1175 foreach_neighbor(board
, coord
, {
1176 group_t g
= group_at(board
, c
);
1177 a
+= g
&& (board_at(board
, c
) == other_color
&& board_group_info(board
, g
).libs
== 1);
1179 assert(a
== trait_at(board
, coord
, color
).cap
);
1180 assert(board_trait_safe(board
, coord
, color
) == trait_at(board
, coord
, color
).safe
);
1183 foreach_neighbor(board
, coord
, {
1184 group
= play_one_neighbor(board
, coord
, color
, other_color
, c
, group
);
1187 board_at(board
, coord
) = color
;
1188 if (unlikely(!group
))
1189 group
= new_group(board
, coord
);
1190 board_gamma_update(board
, coord
, S_BLACK
);
1191 board_gamma_update(board
, coord
, S_WHITE
);
1193 board
->last_move2
= board
->last_move
;
1194 board
->last_move
= *m
;
1196 board_hash_update(board
, coord
, color
);
1197 board_symmetry_update(board
, &board
->symmetry
, coord
);
1198 struct move ko
= { pass
, S_NONE
};
1204 /* We played in an eye-like shape. Either we capture at least one of the eye
1205 * sides in the process of playing, or return -1. */
1206 static int profiling_noinline
1207 board_play_in_eye(struct board
*board
, struct move
*m
, int f
)
1209 coord_t coord
= m
->coord
;
1210 enum stone color
= m
->color
;
1211 /* Check ko: Capture at a position of ko capture one move ago */
1212 if (unlikely(color
== board
->ko
.color
&& coord
== board
->ko
.coord
)) {
1214 fprintf(stderr
, "board_check: ko at %d,%d color %d\n", coord_x(coord
, board
), coord_y(coord
, board
), color
);
1216 } else if (DEBUGL(6)) {
1217 fprintf(stderr
, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
1218 color
, coord_x(coord
, board
), coord_y(coord
, board
),
1219 board
->ko
.color
, coord_x(board
->ko
.coord
, board
), coord_y(board
->ko
.coord
, board
));
1222 struct move ko
= { pass
, S_NONE
};
1224 int captured_groups
= 0;
1226 foreach_neighbor(board
, coord
, {
1227 group_t g
= group_at(board
, c
);
1229 fprintf(stderr
, "board_check: group %d has %d libs\n",
1230 g
, board_group_info(board
, g
).libs
);
1231 captured_groups
+= (board_group_info(board
, g
).libs
== 1);
1234 if (likely(captured_groups
== 0)) {
1237 board_print(board
, stderr
);
1238 fprintf(stderr
, "board_check: one-stone suicide\n");
1244 /* We _will_ for sure capture something. */
1245 assert(trait_at(board
, coord
, color
).cap
> 0);
1246 assert(trait_at(board
, coord
, color
).safe
== board_trait_safe(board
, coord
, color
));
1249 board
->f
[f
] = board
->f
[--board
->flen
];
1251 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
1253 foreach_neighbor(board
, coord
, {
1254 inc_neighbor_count_at(board
, c
, color
);
1255 /* Originally, this could not have changed any trait
1256 * since no neighbors were S_NONE, however by now some
1257 * of them might be removed from the board. */
1258 board_trait_queue(board
, c
);
1260 group_t group
= group_at(board
, c
);
1264 board_group_rmlib(board
, group
, coord
);
1266 fprintf(stderr
, "board_play_raw: reducing libs for group %d\n",
1269 if (board_group_captured(board
, group
)) {
1270 if (board_group_capture(board
, group
) == 1) {
1271 /* If we captured multiple groups at once,
1272 * we can't be fighting ko so we don't need
1273 * to check for that. */
1274 ko
.color
= stone_other(color
);
1276 board
->last_ko
= ko
;
1277 board
->last_ko_age
= board
->moves
;
1279 fprintf(stderr
, "guarding ko at %d,%s\n", ko
.color
, coord2sstr(ko
.coord
, board
));
1284 board_at(board
, coord
) = color
;
1285 group_t group
= new_group(board
, coord
);
1286 board_gamma_update(board
, coord
, S_BLACK
);
1287 board_gamma_update(board
, coord
, S_WHITE
);
1289 board
->last_move2
= board
->last_move
;
1290 board
->last_move
= *m
;
1292 board_hash_update(board
, coord
, color
);
1293 board_hash_commit(board
);
1294 board_traits_recompute(board
);
1295 board_symmetry_update(board
, &board
->symmetry
, coord
);
1301 static int __attribute__((flatten
))
1302 board_play_f(struct board
*board
, struct move
*m
, int f
)
1305 fprintf(stderr
, "board_play(): ---- Playing %d,%d\n", coord_x(m
->coord
, board
), coord_y(m
->coord
, board
));
1307 if (likely(!board_is_eyelike(board
, m
->coord
, stone_other(m
->color
)))) {
1308 /* NOT playing in an eye. Thus this move has to succeed. (This
1309 * is thanks to New Zealand rules. Otherwise, multi-stone
1310 * suicide might fail.) */
1311 group_t group
= board_play_outside(board
, m
, f
);
1312 if (unlikely(board_group_captured(board
, group
))) {
1313 board_group_capture(board
, group
);
1315 board_hash_commit(board
);
1316 board_traits_recompute(board
);
1319 return board_play_in_eye(board
, m
, f
);
1324 board_play(struct board
*board
, struct move
*m
)
1326 if (unlikely(is_pass(m
->coord
) || is_resign(m
->coord
))) {
1327 struct move nomove
= { pass
, S_NONE
};
1329 board
->last_move2
= board
->last_move
;
1330 board
->last_move
= *m
;
1335 for (f
= 0; f
< board
->flen
; f
++)
1336 if (board
->f
[f
] == m
->coord
)
1337 return board_play_f(board
, m
, f
);
1340 fprintf(stderr
, "board_check: stone exists\n");
1346 board_try_random_move(struct board
*b
, enum stone color
, coord_t
*coord
, int f
, ppr_permit permit
, void *permit_data
)
1349 struct move m
= { *coord
, color
};
1351 fprintf(stderr
, "trying random move %d: %d,%d\n", f
, coord_x(*coord
, b
), coord_y(*coord
, b
));
1352 return (likely(!board_is_one_point_eye(b
, *coord
, color
)) /* bad idea to play into one, usually */
1353 && board_is_valid_move(b
, &m
)
1354 && (!permit
|| permit(permit_data
, b
, &m
))
1355 && likely(board_play_f(b
, &m
, f
) >= 0));
1359 board_play_random(struct board
*b
, enum stone color
, coord_t
*coord
, ppr_permit permit
, void *permit_data
)
1361 if (unlikely(b
->flen
== 0))
1364 int base
= fast_random(b
->flen
), f
;
1365 for (f
= base
; f
< b
->flen
; f
++)
1366 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
1368 for (f
= 0; f
< base
; f
++)
1369 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
1374 struct move m
= { pass
, color
};
1380 board_is_false_eyelike(struct board
*board
, coord_t coord
, enum stone eye_color
)
1382 enum stone color_diag_libs
[S_MAX
] = {0, 0, 0, 0};
1384 /* XXX: We attempt false eye detection but we will yield false
1385 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
1387 foreach_diag_neighbor(board
, coord
) {
1388 color_diag_libs
[(enum stone
) board_at(board
, c
)]++;
1389 } foreach_diag_neighbor_end
;
1390 /* For false eye, we need two enemy stones diagonally in the
1391 * middle of the board, or just one enemy stone at the edge
1392 * or in the corner. */
1393 color_diag_libs
[stone_other(eye_color
)] += !!color_diag_libs
[S_OFFBOARD
];
1394 return color_diag_libs
[stone_other(eye_color
)] >= 2;
1398 board_is_one_point_eye(struct board
*board
, coord_t coord
, enum stone eye_color
)
1400 return board_is_eyelike(board
, coord
, eye_color
)
1401 && !board_is_false_eyelike(board
, coord
, eye_color
);
1405 board_get_one_point_eye(struct board
*board
, coord_t coord
)
1407 if (board_is_one_point_eye(board
, coord
, S_WHITE
))
1409 else if (board_is_one_point_eye(board
, coord
, S_BLACK
))
1417 board_fast_score(struct board
*board
)
1420 memset(scores
, 0, sizeof(scores
));
1422 foreach_point(board
) {
1423 enum stone color
= board_at(board
, c
);
1424 if (color
== S_NONE
)
1425 color
= board_get_one_point_eye(board
, c
);
1427 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1428 } foreach_point_end
;
1430 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];
1433 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1435 /* One flood-fill iteration; returns true if next iteration
1438 board_tromp_taylor_iter(struct board
*board
, int *ownermap
)
1440 bool needs_update
= false;
1441 foreach_point(board
) {
1442 /* Ignore occupied and already-dame positions. */
1443 if (board_at(board
, c
) != S_NONE
|| ownermap
[c
] == 3)
1445 /* Count neighbors. */
1447 foreach_neighbor(board
, c
, {
1450 /* If we have neighbors of both colors, or dame,
1451 * we are dame too. */
1452 if ((nei
[1] && nei
[2]) || nei
[3]) {
1454 /* Speed up the propagation. */
1455 foreach_neighbor(board
, c
, {
1456 if (board_at(board
, c
) == S_NONE
)
1459 needs_update
= true;
1462 /* If we have neighbors of one color, we are owned
1463 * by that color, too. */
1464 if (!ownermap
[c
] && (nei
[1] || nei
[2])) {
1465 int newowner
= nei
[1] ? 1 : 2;
1466 ownermap
[c
] = newowner
;
1467 /* Speed up the propagation. */
1468 foreach_neighbor(board
, c
, {
1469 if (board_at(board
, c
) == S_NONE
&& !ownermap
[c
])
1470 ownermap
[c
] = newowner
;
1472 needs_update
= true;
1475 } foreach_point_end
;
1476 return needs_update
;
1479 /* Tromp-Taylor Counting */
1481 board_official_score(struct board
*board
, struct move_queue
*q
)
1484 /* A point P, not colored C, is said to reach C, if there is a path of
1485 * (vertically or horizontally) adjacent points of P's color from P to
1486 * a point of color C.
1488 * A player's score is the number of points of her color, plus the
1489 * number of empty points that reach only her color. */
1491 int ownermap
[board_size2(board
)];
1493 const int o
[4] = {0, 1, 2, 0};
1494 foreach_point(board
) {
1495 ownermap
[c
] = o
[board_at(board
, c
)];
1496 s
[board_at(board
, c
)]++;
1497 } foreach_point_end
;
1500 /* Process dead groups. */
1501 for (unsigned int i
= 0; i
< q
->moves
; i
++) {
1502 foreach_in_group(board
, q
->move
[i
]) {
1503 enum stone color
= board_at(board
, c
);
1504 ownermap
[c
] = o
[stone_other(color
)];
1505 s
[color
]--; s
[stone_other(color
)]++;
1506 } foreach_in_group_end
;
1510 /* We need to special-case empty board. */
1511 if (!s
[S_BLACK
] && !s
[S_WHITE
])
1512 return board
->komi
+ board
->handicap
;
1514 while (board_tromp_taylor_iter(board
, ownermap
))
1515 /* Flood-fill... */;
1518 memset(scores
, 0, sizeof(scores
));
1520 foreach_point(board
) {
1521 assert(board_at(board
, c
) == S_OFFBOARD
|| ownermap
[c
] != 0);
1522 if (ownermap
[c
] == 3)
1524 scores
[ownermap
[c
]]++;
1525 } foreach_point_end
;
1527 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];