15 #include "patternsp.h"
21 static void board_trait_recompute(struct board
*board
, coord_t coord
);
30 #define profiling_noinline __attribute__((noinline))
32 #define profiling_noinline
35 #define gi_granularity 4
36 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
40 board_setup(struct board
*b
)
42 memset(b
, 0, sizeof(*b
));
44 struct move m
= { pass
, S_NONE
};
45 b
->last_move
= b
->last_move2
= b
->last_ko
= b
->ko
= m
;
51 struct board
*b
= malloc2(sizeof(struct board
));
62 board_alloc(struct board
*board
)
64 /* We do not allocate the board structure itself but we allocate
65 * all the arrays with board contents. */
67 int bsize
= board_size2(board
) * sizeof(*board
->b
);
68 int gsize
= board_size2(board
) * sizeof(*board
->g
);
69 int fsize
= board_size2(board
) * sizeof(*board
->f
);
70 int nsize
= board_size2(board
) * sizeof(*board
->n
);
71 int psize
= board_size2(board
) * sizeof(*board
->p
);
72 int hsize
= board_size2(board
) * 2 * sizeof(*board
->h
);
73 int gisize
= board_size2(board
) * sizeof(*board
->gi
);
75 int csize
= board_size2(board
) * sizeof(*board
->c
);
80 int ssize
= board_size2(board
) * sizeof(*board
->spathash
);
85 int p3size
= board_size2(board
) * sizeof(*board
->pat3
);
90 int tsize
= board_size2(board
) * sizeof(*board
->t
);
91 int tqsize
= board_size2(board
) * sizeof(*board
->t
);
97 int pbsize
= board_size2(board
) * sizeof(*board
->prob
[0].items
);
98 int rowpbsize
= board_size(board
) * sizeof(*board
->prob
[0].rowtotals
);
103 int cdsize
= board_size2(board
) * sizeof(*board
->coord
);
105 size_t size
= bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
+ ssize
+ p3size
+ tsize
+ tqsize
+ (pbsize
+ rowpbsize
) * 2 + cdsize
;
106 void *x
= malloc2(size
);
108 /* board->b must come first */
109 board
->b
= x
; x
+= bsize
;
110 board
->g
= x
; x
+= gsize
;
111 board
->f
= x
; x
+= fsize
;
112 board
->p
= x
; x
+= psize
;
113 board
->n
= x
; x
+= nsize
;
114 board
->h
= x
; x
+= hsize
;
115 board
->gi
= x
; x
+= gisize
;
117 board
->c
= x
; x
+= csize
;
119 #ifdef BOARD_SPATHASH
120 board
->spathash
= x
; x
+= ssize
;
123 board
->pat3
= x
; x
+= p3size
;
126 board
->t
= x
; x
+= tsize
;
127 board
->tq
= x
; x
+= tqsize
;
130 board
->prob
[0].items
= x
; x
+= pbsize
;
131 board
->prob
[1].items
= x
; x
+= pbsize
;
132 board
->prob
[0].rowtotals
= x
; x
+= rowpbsize
;
133 board
->prob
[1].rowtotals
= x
; x
+= rowpbsize
;
135 board
->coord
= x
; x
+= cdsize
;
141 board_copy(struct board
*b2
, struct board
*b1
)
143 memcpy(b2
, b1
, sizeof(struct board
));
145 size_t size
= board_alloc(b2
);
146 memcpy(b2
->b
, b1
->b
, size
);
152 board_done_noalloc(struct board
*board
)
154 if (board
->b
) free(board
->b
);
158 board_done(struct board
*board
)
160 board_done_noalloc(board
);
165 board_resize(struct board
*board
, int size
)
168 assert(board_size(board
) == size
+ 2);
170 assert(size
<= BOARD_MAX_SIZE
);
171 board
->size
= size
+ 2 /* S_OFFBOARD margin */;
172 board
->size2
= board_size(board
) * board_size(board
);
175 while ((1 << board
->bits2
) < board
->size2
) board
->bits2
++;
180 size_t asize
= board_alloc(board
);
181 memset(board
->b
, 0, asize
);
185 board_clear(struct board
*board
)
187 int size
= board_size(board
);
188 float komi
= board
->komi
;
190 board_done_noalloc(board
);
192 board_resize(board
, size
- 2 /* S_OFFBOARD margin */);
196 /* Setup neighborhood iterators */
197 board
->nei8
[0] = -size
- 1; // (-1,-1)
200 board
->nei8
[3] = size
- 2; // (-1,0)
202 board
->nei8
[5] = size
- 2; // (-1,1)
205 board
->dnei
[0] = -size
- 1;
207 board
->dnei
[2] = size
*2 - 2;
210 /* Setup initial symmetry */
211 board
->symmetry
.d
= 1;
212 board
->symmetry
.x1
= board
->symmetry
.y1
= board_size(board
) / 2;
213 board
->symmetry
.x2
= board
->symmetry
.y2
= board_size(board
) - 1;
214 board
->symmetry
.type
= SYM_FULL
;
216 /* Set up coordinate cache */
217 foreach_point(board
) {
218 board
->coord
[c
][0] = c
% board_size(board
);
219 board
->coord
[c
][1] = c
/ board_size(board
);
222 /* Draw the offboard margin */
223 int top_row
= board_size2(board
) - board_size(board
);
225 for (i
= 0; i
< board_size(board
); i
++)
226 board
->b
[i
] = board
->b
[top_row
+ i
] = S_OFFBOARD
;
227 for (i
= 0; i
<= top_row
; i
+= board_size(board
))
228 board
->b
[i
] = board
->b
[board_size(board
) - 1 + i
] = S_OFFBOARD
;
230 foreach_point(board
) {
232 if (board_at(board
, coord
) == S_OFFBOARD
)
234 foreach_neighbor(board
, c
, {
235 inc_neighbor_count_at(board
, coord
, board_at(board
, c
));
239 /* All positions are free! Except the margin. */
240 for (i
= board_size(board
); i
< (board_size(board
) - 1) * board_size(board
); i
++)
241 if (i
% board_size(board
) != 0 && i
% board_size(board
) != board_size(board
) - 1)
242 board
->f
[board
->flen
++] = i
;
244 /* Initialize zobrist hashtable. */
245 /* We will need these to be stable across Pachi runs for
246 * certain kinds of pattern matching, thus we do not use
247 * fast_random() for this. */
248 hash_t hseed
= 0x3121110101112131;
249 foreach_point(board
) {
250 board
->h
[c
* 2] = (hseed
*= 16807);
251 if (!board
->h
[c
* 2])
253 /* And once again for white */
254 board
->h
[c
* 2 + 1] = (hseed
*= 16807);
255 if (!board
->h
[c
* 2 + 1])
256 board
->h
[c
* 2 + 1] = 1;
259 #ifdef BOARD_SPATHASH
260 /* Initialize spatial hashes. */
261 foreach_point(board
) {
262 for (int d
= 1; d
<= BOARD_SPATHASH_MAXD
; d
++) {
263 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
264 ptcoords_at(x
, y
, c
, board
, j
);
265 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][0] ^=
266 pthashes
[0][j
][board_at(board
, c
)];
267 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][1] ^=
268 pthashes
[0][j
][stone_other(board_at(board
, c
))];
274 /* Initialize 3x3 pattern codes. */
275 foreach_point(board
) {
276 if (board_at(board
, c
) == S_NONE
)
277 board
->pat3
[c
] = pattern3_hash(board
, c
);
281 /* Initialize traits. */
282 foreach_point(board
) {
283 trait_at(board
, c
, S_BLACK
).cap
= 0;
284 trait_at(board
, c
, S_BLACK
).cap1
= 0;
285 trait_at(board
, c
, S_BLACK
).safe
= true;
286 trait_at(board
, c
, S_WHITE
).cap
= 0;
287 trait_at(board
, c
, S_WHITE
).cap1
= 0;
288 trait_at(board
, c
, S_WHITE
).safe
= true;
292 board
->prob
[0].b
= board
->prob
[1].b
= board
;
293 foreach_point(board
) {
294 probdist_set(&board
->prob
[0], c
, double_to_fixp((board_at(board
, c
) == S_NONE
) * 1.0f
));
295 probdist_set(&board
->prob
[1], c
, double_to_fixp((board_at(board
, c
) == S_NONE
) * 1.0f
));
301 board_print_top(struct board
*board
, char *s
, char *end
, int c
)
303 for (int i
= 0; i
< c
; i
++) {
304 char asdf
[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
305 s
+= snprintf(s
, end
- s
, " ");
306 for (int x
= 1; x
< board_size(board
) - 1; x
++)
307 s
+= snprintf(s
, end
- s
, "%c ", asdf
[x
- 1]);
308 s
+= snprintf(s
, end
-s
, " ");
310 s
+= snprintf(s
, end
- s
, "\n");
311 for (int i
= 0; i
< c
; i
++) {
312 s
+= snprintf(s
, end
- s
, " +-");
313 for (int x
= 1; x
< board_size(board
) - 1; x
++)
314 s
+= snprintf(s
, end
- s
, "--");
315 s
+= snprintf(s
, end
- s
, "+");
317 s
+= snprintf(s
, end
- s
, "\n");
322 board_print_bottom(struct board
*board
, char *s
, char *end
, int c
)
324 for (int i
= 0; i
< c
; i
++) {
325 s
+= snprintf(s
, end
- s
, " +-");
326 for (int x
= 1; x
< board_size(board
) - 1; x
++)
327 s
+= snprintf(s
, end
- s
, "--");
328 s
+= snprintf(s
, end
- s
, "+");
330 s
+= snprintf(s
, end
- s
, "\n");
335 board_print_row(struct board
*board
, int y
, char *s
, char *end
, board_cprint cprint
)
337 s
+= snprintf(s
, end
- s
, " %2d | ", y
);
338 for (int x
= 1; x
< board_size(board
) - 1; x
++) {
339 if (coord_x(board
->last_move
.coord
, board
) == x
&& coord_y(board
->last_move
.coord
, board
) == y
)
340 s
+= snprintf(s
, end
- s
, "%c)", stone2char(board_atxy(board
, x
, y
)));
342 s
+= snprintf(s
, end
- s
, "%c ", stone2char(board_atxy(board
, x
, y
)));
344 s
+= snprintf(s
, end
- s
, "|");
346 s
+= snprintf(s
, end
- s
, " %2d | ", y
);
347 for (int x
= 1; x
< board_size(board
) - 1; x
++) {
348 s
= cprint(board
, coord_xy(board
, x
, y
), s
, end
);
350 s
+= snprintf(s
, end
- s
, "|");
352 s
+= snprintf(s
, end
- s
, "\n");
357 board_print_custom(struct board
*board
, FILE *f
, board_cprint cprint
)
361 char *end
= buf
+ sizeof(buf
);
362 s
+= snprintf(s
, end
- s
, "Move: % 3d Komi: %2.1f Handicap: %d Captures B: %d W: %d\n",
363 board
->moves
, board
->komi
, board
->handicap
,
364 board
->captures
[S_BLACK
], board
->captures
[S_WHITE
]);
365 s
= board_print_top(board
, s
, end
, 1 + !!cprint
);
366 for (int y
= board_size(board
) - 2; y
>= 1; y
--)
367 s
= board_print_row(board
, y
, s
, end
, cprint
);
368 board_print_bottom(board
, s
, end
, 1 + !!cprint
);
369 fprintf(f
, "%s\n", buf
);
373 cprint_group(struct board
*board
, coord_t c
, char *s
, char *end
)
375 s
+= snprintf(s
, end
- s
, "%d ", group_base(group_at(board
, c
)));
380 board_print(struct board
*board
, FILE *f
)
382 board_print_custom(board
, f
, DEBUGL(6) ? cprint_group
: NULL
);
386 board_gamma_set(struct board
*b
, struct features_gamma
*gamma
, bool precise_selfatari
)
390 b
->precise_selfatari
= precise_selfatari
;
391 for (int i
= 0; i
< b
->flen
; i
++) {
392 board_trait_recompute(b
, b
->f
[i
]);
398 /* Update the probability distribution we maintain incrementally. */
400 board_gamma_update(struct board
*board
, coord_t coord
, enum stone color
)
406 /* Punch out invalid moves and moves filling our own eyes. */
407 if (board_at(board
, coord
) != S_NONE
408 || (board_is_eyelike(board
, coord
, stone_other(color
))
409 && !trait_at(board
, coord
, color
).cap
)
410 || (board_is_one_point_eye(board
, coord
, color
))) {
411 probdist_set(&board
->prob
[color
- 1], coord
, 0);
415 hash3_t pat
= board
->pat3
[coord
];
416 if (color
== S_WHITE
) {
417 /* We work with the pattern3s as black-to-play. */
418 pat
= pattern3_reverse(pat
);
421 /* We just quickly replicate the general pattern matcher stuff
422 * here in the most bare-bone way. */
423 double value
= board
->gamma
->gamma
[FEAT_PATTERN3
][pat
];
424 if (trait_at(board
, coord
, color
).cap
) {
426 i
|= (trait_at(board
, coord
, color
).cap1
== trait_at(board
, coord
, color
).cap
) << PF_CAPTURE_1STONE
;
427 i
|= (!trait_at(board
, coord
, stone_other(color
)).safe
) << PF_CAPTURE_TRAPPED
;
428 i
|= (trait_at(board
, coord
, color
).cap
< neighbor_count_at(board
, coord
, stone_other(color
))) << PF_CAPTURE_CONNECTION
;
429 value
*= board
->gamma
->gamma
[FEAT_CAPTURE
][i
];
431 if (trait_at(board
, coord
, stone_other(color
)).cap
) {
433 i
|= (trait_at(board
, coord
, stone_other(color
)).cap1
== trait_at(board
, coord
, stone_other(color
)).cap
) << PF_AESCAPE_1STONE
;
434 i
|= (!trait_at(board
, coord
, color
).safe
) << PF_AESCAPE_TRAPPED
;
435 i
|= (trait_at(board
, coord
, stone_other(color
)).cap
< neighbor_count_at(board
, coord
, color
)) << PF_AESCAPE_CONNECTION
;
436 value
*= board
->gamma
->gamma
[FEAT_AESCAPE
][i
];
438 if (!trait_at(board
, coord
, color
).safe
)
439 value
*= board
->gamma
->gamma
[FEAT_SELFATARI
][1 + board
->precise_selfatari
];
440 probdist_set(&board
->prob
[color
- 1], coord
, double_to_fixp(value
));
446 board_trait_safe(struct board
*board
, coord_t coord
, enum stone color
)
448 if (board
->precise_selfatari
)
449 return !is_bad_selfatari(board
, color
, coord
);
451 return board_safe_to_play(board
, coord
, color
);
455 board_trait_recompute(struct board
*board
, coord_t coord
)
457 trait_at(board
, coord
, S_BLACK
).safe
= board_trait_safe(board
, coord
, S_BLACK
);;
458 trait_at(board
, coord
, S_WHITE
).safe
= board_trait_safe(board
, coord
, S_WHITE
);
460 fprintf(stderr
, "traits[%s:%s lib=%d] (black cap=%d cap1=%d safe=%d) (white cap=%d cap1=%d safe=%d)\n",
461 coord2sstr(coord
, board
), stone2str(board_at(board
, coord
)), immediate_liberty_count(board
, coord
),
462 trait_at(board
, coord
, S_BLACK
).cap
, trait_at(board
, coord
, S_BLACK
).cap1
, trait_at(board
, coord
, S_BLACK
).safe
,
463 trait_at(board
, coord
, S_WHITE
).cap
, trait_at(board
, coord
, S_WHITE
).cap1
, trait_at(board
, coord
, S_WHITE
).safe
);
465 board_gamma_update(board
, coord
, S_BLACK
);
466 board_gamma_update(board
, coord
, S_WHITE
);
470 /* Recompute traits for dirty points that we have previously touched
471 * somehow (libs of their neighbors changed or so). */
473 board_traits_recompute(struct board
*board
)
476 for (int i
= 0; i
< board
->tqlen
; i
++) {
477 coord_t coord
= board
->tq
[i
];
478 trait_at(board
, coord
, S_BLACK
).dirty
= false;
479 if (board_at(board
, coord
) != S_NONE
)
481 board_trait_recompute(board
, coord
);
487 /* Queue traits of given point for recomputing. */
489 board_trait_queue(struct board
*board
, coord_t coord
)
492 if (trait_at(board
, coord
, S_BLACK
).dirty
)
494 board
->tq
[board
->tqlen
++] = coord
;
495 trait_at(board
, coord
, S_BLACK
).dirty
= true;
500 /* Update board hash with given coordinate. */
501 static void profiling_noinline
502 board_hash_update(struct board
*board
, coord_t coord
, enum stone color
)
504 board
->hash
^= hash_at(board
, coord
, color
);
506 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
);
508 #ifdef BOARD_SPATHASH
509 /* Gridcular metric is reflective, so we update all hashes
510 * of appropriate ditance in OUR circle. */
511 for (int d
= 1; d
<= BOARD_SPATHASH_MAXD
; d
++) {
512 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
513 ptcoords_at(x
, y
, coord
, board
, j
);
514 /* We either changed from S_NONE to color
515 * or vice versa; doesn't matter. */
516 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][0] ^=
517 pthashes
[0][j
][color
] ^ pthashes
[0][j
][S_NONE
];
518 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][1] ^=
519 pthashes
[0][j
][stone_other(color
)] ^ pthashes
[0][j
][S_NONE
];
524 #if defined(BOARD_PAT3)
525 /* @color is not what we need in case of capture. */
526 enum stone new_color
= board_at(board
, coord
);
527 if (new_color
== S_NONE
)
528 board
->pat3
[coord
] = pattern3_hash(board
, coord
);
529 foreach_8neighbor(board
, coord
) { // internally, the loop uses fn__i=[0..7]
530 if (board_at(board
, c
) != S_NONE
)
532 board
->pat3
[c
] &= ~(3 << (fn__i
*2));
533 board
->pat3
[c
] |= new_color
<< (fn__i
*2);
535 if (board_at(board
, c
) != S_OFFBOARD
&& pattern3_hash(board
, c
) != board
->pat3
[c
]) {
536 board_print(board
, stderr
);
537 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
);
541 board_trait_queue(board
, c
);
542 } foreach_8neighbor_end
;
546 /* Commit current board hash to history. */
547 static void profiling_noinline
548 board_hash_commit(struct board
*board
)
551 fprintf(stderr
, "board_hash_commit %"PRIhash
"\n", board
->hash
);
552 if (likely(board
->history_hash
[board
->hash
& history_hash_mask
]) == 0) {
553 board
->history_hash
[board
->hash
& history_hash_mask
] = board
->hash
;
555 hash_t i
= board
->hash
;
556 while (board
->history_hash
[i
& history_hash_mask
]) {
557 if (board
->history_hash
[i
& history_hash_mask
] == board
->hash
) {
559 fprintf(stderr
, "SUPERKO VIOLATION noted at %d,%d\n",
560 coord_x(board
->last_move
.coord
, board
), coord_y(board
->last_move
.coord
, board
));
561 board
->superko_violation
= true;
564 i
= history_hash_next(i
);
566 board
->history_hash
[i
& history_hash_mask
] = board
->hash
;
572 board_symmetry_update(struct board
*b
, struct board_symmetry
*symmetry
, coord_t c
)
574 if (likely(symmetry
->type
== SYM_NONE
)) {
575 /* Fully degenerated already. We do not support detection
576 * of restoring of symmetry, assuming that this is too rare
577 * a case to handle. */
581 int x
= coord_x(c
, b
), y
= coord_y(c
, b
), t
= board_size(b
) / 2;
582 int dx
= board_size(b
) - 1 - x
; /* for SYM_DOWN */
584 fprintf(stderr
, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
585 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
586 symmetry
->d
, symmetry
->type
, x
, y
);
589 switch (symmetry
->type
) {
591 if (x
== t
&& y
== t
) {
592 /* Tengen keeps full symmetry. */
595 /* New symmetry now? */
597 symmetry
->type
= SYM_DIAG_UP
;
598 symmetry
->x1
= symmetry
->y1
= 1;
599 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
601 } else if (dx
== y
) {
602 symmetry
->type
= SYM_DIAG_DOWN
;
603 symmetry
->x1
= symmetry
->y1
= 1;
604 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
607 symmetry
->type
= SYM_HORIZ
;
609 symmetry
->y2
= board_size(b
) - 1;
612 symmetry
->type
= SYM_VERT
;
614 symmetry
->x2
= board_size(b
) - 1;
618 symmetry
->type
= SYM_NONE
;
619 symmetry
->x1
= symmetry
->y1
= 1;
620 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
646 fprintf(stderr
, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
647 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
648 symmetry
->d
, symmetry
->type
);
655 board_handicap_stone(struct board
*board
, int x
, int y
, FILE *f
)
658 m
.color
= S_BLACK
; m
.coord
= coord_xy(board
, x
, y
);
660 board_play(board
, &m
);
661 /* Simulate white passing; otherwise, UCT search can get confused since
662 * tree depth parity won't match the color to move. */
665 char *str
= coord2str(m
.coord
, board
);
667 fprintf(stderr
, "choosing handicap %s (%d,%d)\n", str
, x
, y
);
668 if (f
) fprintf(f
, "%s ", str
);
673 board_handicap(struct board
*board
, int stones
, FILE *f
)
675 int margin
= 3 + (board_size(board
) >= 13);
677 int mid
= board_size(board
) / 2;
678 int max
= board_size(board
) - 1 - margin
;
679 const int places
[][2] = {
680 { min
, min
}, { max
, max
}, { max
, min
}, { min
, max
},
681 { min
, mid
}, { max
, mid
},
682 { mid
, min
}, { mid
, max
},
686 board
->handicap
= stones
;
688 if (stones
== 5 || stones
== 7) {
689 board_handicap_stone(board
, mid
, mid
, f
);
694 for (i
= 0; i
< stones
; i
++)
695 board_handicap_stone(board
, places
[i
][0], places
[i
][1], f
);
699 static void __attribute__((noinline
))
700 check_libs_consistency(struct board
*board
, group_t g
)
704 struct group
*gi
= &board_group_info(board
, g
);
705 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
706 if (gi
->lib
[i
] && board_at(board
, gi
->lib
[i
]) != S_NONE
) {
707 fprintf(stderr
, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi
->lib
[i
], board
), g
, coord2sstr(group_base(g
), board
));
714 board_capturable_add(struct board
*board
, group_t group
, coord_t lib
, bool onestone
)
716 //fprintf(stderr, "group %s cap %s\n", coord2sstr(group, board), coord2sstr(lib, boarD));
718 /* Increase capturable count trait of my last lib. */
719 enum stone capturing_color
= stone_other(board_at(board
, group
));
720 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
721 foreach_neighbor(board
, lib
, {
722 if (DEBUGL(8) && group_at(board
, c
) == group
)
723 fprintf(stderr
, "%s[%d] %s cap bump bc of %s(%d) member %s onestone %d\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
), onestone
);
724 trait_at(board
, lib
, capturing_color
).cap
+= (group_at(board
, c
) == group
);
725 trait_at(board
, lib
, capturing_color
).cap1
+= (group_at(board
, c
) == group
&& onestone
);
727 board_trait_queue(board
, lib
);
731 /* Update the list of capturable groups. */
733 assert(board
->clen
< board_size2(board
));
734 board
->c
[board
->clen
++] = group
;
738 board_capturable_rm(struct board
*board
, group_t group
, coord_t lib
, bool onestone
)
740 //fprintf(stderr, "group %s nocap %s\n", coord2sstr(group, board), coord2sstr(lib, board));
742 /* Decrease capturable count trait of my previously-last lib. */
743 enum stone capturing_color
= stone_other(board_at(board
, group
));
744 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
745 foreach_neighbor(board
, lib
, {
746 if (DEBUGL(8) && group_at(board
, c
) == group
)
747 fprintf(stderr
, "%s[%d] cap dump bc of %s(%d) member %s onestone %d\n", coord2sstr(lib
, board
), trait_at(board
, lib
, capturing_color
).cap
, coord2sstr(group
, board
), board_group_info(board
, group
).libs
, coord2sstr(c
, board
), onestone
);
748 trait_at(board
, lib
, capturing_color
).cap
-= (group_at(board
, c
) == group
);
749 trait_at(board
, lib
, capturing_color
).cap1
-= (group_at(board
, c
) == group
&& onestone
);
751 board_trait_queue(board
, lib
);
755 /* Update the list of capturable groups. */
756 for (int i
= 0; i
< board
->clen
; i
++) {
757 if (unlikely(board
->c
[i
] == group
)) {
758 board
->c
[i
] = board
->c
[--board
->clen
];
762 fprintf(stderr
, "rm of bad group %d\n", group_base(group
));
768 board_atariable_add(struct board
*board
, group_t group
, coord_t lib1
, coord_t lib2
)
771 board_trait_queue(board
, lib1
);
772 board_trait_queue(board
, lib2
);
776 board_atariable_rm(struct board
*board
, group_t group
, coord_t lib1
, coord_t lib2
)
779 board_trait_queue(board
, lib1
);
780 board_trait_queue(board
, lib2
);
785 board_group_addlib(struct board
*board
, group_t group
, coord_t coord
)
788 fprintf(stderr
, "Group %d[%s] %d: Adding liberty %s\n",
789 group_base(group
), coord2sstr(group_base(group
), board
),
790 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
793 check_libs_consistency(board
, group
);
795 struct group
*gi
= &board_group_info(board
, group
);
796 bool onestone
= group_is_onestone(board
, group
);
797 if (gi
->libs
< GROUP_KEEP_LIBS
) {
798 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
800 /* Seems extra branch just slows it down */
804 if (unlikely(gi
->lib
[i
] == coord
))
808 board_capturable_add(board
, group
, coord
, onestone
);
809 } else if (gi
->libs
== 1) {
810 board_capturable_rm(board
, group
, gi
->lib
[0], onestone
);
811 board_atariable_add(board
, group
, gi
->lib
[0], coord
);
812 } else if (gi
->libs
== 2) {
813 board_atariable_rm(board
, group
, gi
->lib
[0], gi
->lib
[1]);
815 gi
->lib
[gi
->libs
++] = coord
;
818 check_libs_consistency(board
, group
);
822 board_group_find_extra_libs(struct board
*board
, group_t group
, struct group
*gi
, coord_t avoid
)
824 /* Add extra liberty from the board to our liberty list. */
825 unsigned char watermark
[board_size2(board
) / 8];
826 memset(watermark
, 0, sizeof(watermark
));
827 #define watermark_get(c) (watermark[c >> 3] & (1 << (c & 7)))
828 #define watermark_set(c) watermark[c >> 3] |= (1 << (c & 7))
830 for (int i
= 0; i
< GROUP_KEEP_LIBS
- 1; i
++)
831 watermark_set(gi
->lib
[i
]);
832 watermark_set(avoid
);
834 foreach_in_group(board
, group
) {
836 foreach_neighbor(board
, coord2
, {
837 if (board_at(board
, c
) + watermark_get(c
) != S_NONE
)
840 gi
->lib
[gi
->libs
++] = c
;
841 if (unlikely(gi
->libs
>= GROUP_KEEP_LIBS
))
844 } foreach_in_group_end
;
850 board_group_rmlib(struct board
*board
, group_t group
, coord_t coord
)
853 fprintf(stderr
, "Group %d[%s] %d: Removing liberty %s\n",
854 group_base(group
), coord2sstr(group_base(group
), board
),
855 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
858 struct group
*gi
= &board_group_info(board
, group
);
859 bool onestone
= group_is_onestone(board
, group
);
860 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
862 /* Seems extra branch just slows it down */
866 if (likely(gi
->lib
[i
] != coord
))
869 coord_t lib
= gi
->lib
[i
] = gi
->lib
[--gi
->libs
];
870 gi
->lib
[gi
->libs
] = 0;
872 check_libs_consistency(board
, group
);
874 /* Postpone refilling lib[] until we need to. */
875 assert(GROUP_REFILL_LIBS
> 1);
876 if (gi
->libs
> GROUP_REFILL_LIBS
)
878 if (gi
->libs
== GROUP_REFILL_LIBS
)
879 board_group_find_extra_libs(board
, group
, gi
, coord
);
882 board_atariable_add(board
, group
, gi
->lib
[0], gi
->lib
[1]);
883 } else if (gi
->libs
== 1) {
884 board_capturable_add(board
, group
, gi
->lib
[0], onestone
);
885 board_atariable_rm(board
, group
, gi
->lib
[0], lib
);
886 } else if (gi
->libs
== 0)
887 board_capturable_rm(board
, group
, lib
, onestone
);
891 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
892 * can call this multiple times per coord. */
893 check_libs_consistency(board
, group
);
898 /* This is a low-level routine that doesn't maintain consistency
899 * of all the board data structures. */
901 board_remove_stone(struct board
*board
, group_t group
, coord_t c
)
903 enum stone color
= board_at(board
, c
);
904 board_at(board
, c
) = S_NONE
;
905 group_at(board
, c
) = 0;
906 board_hash_update(board
, c
, color
);
908 /* We mark as cannot-capture now. If this is a ko/snapback,
909 * we will get incremented later in board_group_addlib(). */
910 trait_at(board
, c
, S_BLACK
).cap
= trait_at(board
, c
, S_BLACK
).cap1
= 0;
911 trait_at(board
, c
, S_WHITE
).cap
= trait_at(board
, c
, S_WHITE
).cap1
= 0;
912 board_trait_queue(board
, c
);
915 /* Increase liberties of surrounding groups */
917 foreach_neighbor(board
, coord
, {
918 dec_neighbor_count_at(board
, c
, color
);
919 board_trait_queue(board
, c
);
920 group_t g
= group_at(board
, c
);
922 board_group_addlib(board
, g
, coord
);
926 fprintf(stderr
, "pushing free move [%d]: %d,%d\n", board
->flen
, coord_x(c
, board
), coord_y(c
, board
));
927 board
->f
[board
->flen
++] = c
;
930 static int profiling_noinline
931 board_group_capture(struct board
*board
, group_t group
)
935 foreach_in_group(board
, group
) {
936 board
->captures
[stone_other(board_at(board
, c
))]++;
937 board_remove_stone(board
, group
, c
);
939 } foreach_in_group_end
;
941 struct group
*gi
= &board_group_info(board
, group
);
942 assert(gi
->libs
== 0);
943 memset(gi
, 0, sizeof(*gi
));
949 static void profiling_noinline
950 add_to_group(struct board
*board
, group_t group
, coord_t prevstone
, coord_t coord
)
953 struct group
*gi
= &board_group_info(board
, group
);
954 bool onestone
= group_is_onestone(board
, group
);
957 /* Our group is temporarily in atari; make sure the capturable
958 * counts also correspond to the newly added stone before we
959 * start adding liberties again so bump-dump ops match. */
960 enum stone capturing_color
= stone_other(board_at(board
, group
));
961 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
963 coord_t lib
= board_group_info(board
, group
).lib
[0];
964 if (coord_is_adjecent(lib
, coord
, board
)) {
966 fprintf(stderr
, "add_to_group %s: %s[%d] bump\n", coord2sstr(group
, board
), coord2sstr(lib
, board
), trait_at(board
, lib
, capturing_color
).cap
);
967 trait_at(board
, lib
, capturing_color
).cap
++;
968 /* This is never a 1-stone group, obviously. */
969 board_trait_queue(board
, lib
);
973 /* We are not 1-stone group anymore, update the cap1
974 * counter specifically. */
975 foreach_neighbor(board
, group
, {
976 if (board_at(board
, c
) != S_NONE
) continue;
977 trait_at(board
, c
, capturing_color
).cap1
--;
978 board_trait_queue(board
, c
);
984 group_at(board
, coord
) = group
;
985 groupnext_at(board
, coord
) = groupnext_at(board
, prevstone
);
986 groupnext_at(board
, prevstone
) = coord
;
988 foreach_neighbor(board
, coord
, {
989 if (board_at(board
, c
) == S_NONE
)
990 board_group_addlib(board
, group
, c
);
994 fprintf(stderr
, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
995 coord_x(prevstone
, board
), coord_y(prevstone
, board
),
996 coord_x(coord
, board
), coord_y(coord
, board
),
997 groupnext_at(board
, coord
) % board_size(board
), groupnext_at(board
, coord
) / board_size(board
),
1001 static void profiling_noinline
1002 merge_groups(struct board
*board
, group_t group_to
, group_t group_from
)
1005 fprintf(stderr
, "board_play_raw: merging groups %d -> %d\n",
1006 group_base(group_from
), group_base(group_to
));
1007 struct group
*gi_from
= &board_group_info(board
, group_from
);
1008 struct group
*gi_to
= &board_group_info(board
, group_to
);
1009 bool onestone_from
= group_is_onestone(board
, group_from
);
1010 bool onestone_to
= group_is_onestone(board
, group_to
);
1012 /* We do this early before the group info is rewritten. */
1013 if (gi_from
->libs
== 2)
1014 board_atariable_rm(board
, group_from
, gi_from
->lib
[0], gi_from
->lib
[1]);
1015 else if (gi_from
->libs
== 1)
1016 board_capturable_rm(board
, group_from
, gi_from
->lib
[0], onestone_from
);
1019 fprintf(stderr
,"---- (froml %d, tol %d)\n", gi_from
->libs
, gi_to
->libs
);
1021 if (gi_to
->libs
< GROUP_KEEP_LIBS
) {
1022 for (int i
= 0; i
< gi_from
->libs
; i
++) {
1023 for (int j
= 0; j
< gi_to
->libs
; j
++)
1024 if (gi_to
->lib
[j
] == gi_from
->lib
[i
])
1026 if (gi_to
->libs
== 0) {
1027 board_capturable_add(board
, group_to
, gi_from
->lib
[i
], onestone_to
);
1028 } else if (gi_to
->libs
== 1) {
1029 board_capturable_rm(board
, group_to
, gi_to
->lib
[0], onestone_to
);
1030 board_atariable_add(board
, group_to
, gi_to
->lib
[0], gi_from
->lib
[i
]);
1031 } else if (gi_to
->libs
== 2) {
1032 board_atariable_rm(board
, group_to
, gi_to
->lib
[0], gi_to
->lib
[1]);
1034 gi_to
->lib
[gi_to
->libs
++] = gi_from
->lib
[i
];
1035 if (gi_to
->libs
>= GROUP_KEEP_LIBS
)
1042 if (gi_to
->libs
== 1) {
1043 enum stone capturing_color
= stone_other(board_at(board
, group_to
));
1044 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
1046 /* Our group is currently in atari; make sure we properly
1047 * count in even the neighbors from the other group in the
1048 * capturable counter. */
1049 coord_t lib
= board_group_info(board
, group_to
).lib
[0];
1050 foreach_neighbor(board
, lib
, {
1051 if (DEBUGL(8) && group_at(board
, c
) == group_from
)
1052 fprintf(stderr
, "%s[%d] cap bump\n", coord2sstr(lib
, board
), trait_at(board
, lib
, capturing_color
).cap
);
1053 trait_at(board
, lib
, capturing_color
).cap
+= (group_at(board
, c
) == group_from
);
1054 /* This is never a 1-stone group, obviously. */
1056 board_trait_queue(board
, lib
);
1059 /* We are not 1-stone group anymore, update the cap1
1060 * counter specifically. */
1061 foreach_neighbor(board
, group_to
, {
1062 if (board_at(board
, c
) != S_NONE
) continue;
1063 trait_at(board
, c
, capturing_color
).cap1
--;
1064 board_trait_queue(board
, c
);
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], true);
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);
1178 b
+= g
&& (board_at(board
, c
) == other_color
&& board_group_info(board
, g
).libs
== 1) && group_is_onestone(board
, g
);
1180 assert(a
== trait_at(board
, coord
, color
).cap
);
1181 assert(b
== trait_at(board
, coord
, color
).cap1
);
1182 assert(board_trait_safe(board
, coord
, color
) == trait_at(board
, coord
, color
).safe
);
1185 foreach_neighbor(board
, coord
, {
1186 group
= play_one_neighbor(board
, coord
, color
, other_color
, c
, group
);
1189 board_at(board
, coord
) = color
;
1190 if (unlikely(!group
))
1191 group
= new_group(board
, coord
);
1192 board_gamma_update(board
, coord
, S_BLACK
);
1193 board_gamma_update(board
, coord
, S_WHITE
);
1195 board
->last_move2
= board
->last_move
;
1196 board
->last_move
= *m
;
1198 board_hash_update(board
, coord
, color
);
1199 board_symmetry_update(board
, &board
->symmetry
, coord
);
1200 struct move ko
= { pass
, S_NONE
};
1206 /* We played in an eye-like shape. Either we capture at least one of the eye
1207 * sides in the process of playing, or return -1. */
1208 static int profiling_noinline
1209 board_play_in_eye(struct board
*board
, struct move
*m
, int f
)
1211 coord_t coord
= m
->coord
;
1212 enum stone color
= m
->color
;
1213 /* Check ko: Capture at a position of ko capture one move ago */
1214 if (unlikely(color
== board
->ko
.color
&& coord
== board
->ko
.coord
)) {
1216 fprintf(stderr
, "board_check: ko at %d,%d color %d\n", coord_x(coord
, board
), coord_y(coord
, board
), color
);
1218 } else if (DEBUGL(6)) {
1219 fprintf(stderr
, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
1220 color
, coord_x(coord
, board
), coord_y(coord
, board
),
1221 board
->ko
.color
, coord_x(board
->ko
.coord
, board
), coord_y(board
->ko
.coord
, board
));
1224 struct move ko
= { pass
, S_NONE
};
1226 int captured_groups
= 0;
1228 foreach_neighbor(board
, coord
, {
1229 group_t g
= group_at(board
, c
);
1231 fprintf(stderr
, "board_check: group %d has %d libs\n",
1232 g
, board_group_info(board
, g
).libs
);
1233 captured_groups
+= (board_group_info(board
, g
).libs
== 1);
1236 if (likely(captured_groups
== 0)) {
1239 board_print(board
, stderr
);
1240 fprintf(stderr
, "board_check: one-stone suicide\n");
1246 /* We _will_ for sure capture something. */
1247 assert(trait_at(board
, coord
, color
).cap
> 0);
1248 assert(trait_at(board
, coord
, color
).safe
== board_trait_safe(board
, coord
, color
));
1251 board
->f
[f
] = board
->f
[--board
->flen
];
1253 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
1255 foreach_neighbor(board
, coord
, {
1256 inc_neighbor_count_at(board
, c
, color
);
1257 /* Originally, this could not have changed any trait
1258 * since no neighbors were S_NONE, however by now some
1259 * of them might be removed from the board. */
1260 board_trait_queue(board
, c
);
1262 group_t group
= group_at(board
, c
);
1266 board_group_rmlib(board
, group
, coord
);
1268 fprintf(stderr
, "board_play_raw: reducing libs for group %d\n",
1271 if (board_group_captured(board
, group
)) {
1272 if (board_group_capture(board
, group
) == 1) {
1273 /* If we captured multiple groups at once,
1274 * we can't be fighting ko so we don't need
1275 * to check for that. */
1276 ko
.color
= stone_other(color
);
1278 board
->last_ko
= ko
;
1279 board
->last_ko_age
= board
->moves
;
1281 fprintf(stderr
, "guarding ko at %d,%s\n", ko
.color
, coord2sstr(ko
.coord
, board
));
1286 board_at(board
, coord
) = color
;
1287 group_t group
= new_group(board
, coord
);
1288 board_gamma_update(board
, coord
, S_BLACK
);
1289 board_gamma_update(board
, coord
, S_WHITE
);
1291 board
->last_move2
= board
->last_move
;
1292 board
->last_move
= *m
;
1294 board_hash_update(board
, coord
, color
);
1295 board_hash_commit(board
);
1296 board_traits_recompute(board
);
1297 board_symmetry_update(board
, &board
->symmetry
, coord
);
1303 static int __attribute__((flatten
))
1304 board_play_f(struct board
*board
, struct move
*m
, int f
)
1307 fprintf(stderr
, "board_play(%s): ---- Playing %d,%d\n", coord2sstr(m
->coord
, board
), coord_x(m
->coord
, board
), coord_y(m
->coord
, board
));
1309 if (likely(!board_is_eyelike(board
, m
->coord
, stone_other(m
->color
)))) {
1310 /* NOT playing in an eye. Thus this move has to succeed. (This
1311 * is thanks to New Zealand rules. Otherwise, multi-stone
1312 * suicide might fail.) */
1313 group_t group
= board_play_outside(board
, m
, f
);
1314 if (unlikely(board_group_captured(board
, group
))) {
1315 board_group_capture(board
, group
);
1317 board_hash_commit(board
);
1318 board_traits_recompute(board
);
1321 return board_play_in_eye(board
, m
, f
);
1326 board_play(struct board
*board
, struct move
*m
)
1328 if (unlikely(is_pass(m
->coord
) || is_resign(m
->coord
))) {
1329 struct move nomove
= { pass
, S_NONE
};
1331 board
->last_move2
= board
->last_move
;
1332 board
->last_move
= *m
;
1337 for (f
= 0; f
< board
->flen
; f
++)
1338 if (board
->f
[f
] == m
->coord
)
1339 return board_play_f(board
, m
, f
);
1342 fprintf(stderr
, "board_check: stone exists\n");
1348 board_try_random_move(struct board
*b
, enum stone color
, coord_t
*coord
, int f
, ppr_permit permit
, void *permit_data
)
1351 struct move m
= { *coord
, color
};
1353 fprintf(stderr
, "trying random move %d: %d,%d\n", f
, coord_x(*coord
, b
), coord_y(*coord
, b
));
1354 if (unlikely(board_is_one_point_eye(b
, *coord
, color
)) /* bad idea to play into one, usually */
1355 || !board_is_valid_move(b
, &m
)
1356 || (permit
&& !permit(permit_data
, b
, &m
)))
1358 *coord
= m
.coord
; // permit might modify it
1359 return likely(board_play_f(b
, &m
, f
) >= 0);
1363 board_play_random(struct board
*b
, enum stone color
, coord_t
*coord
, ppr_permit permit
, void *permit_data
)
1365 if (unlikely(b
->flen
== 0))
1368 int base
= fast_random(b
->flen
), f
;
1369 for (f
= base
; f
< b
->flen
; f
++)
1370 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
1372 for (f
= 0; f
< base
; f
++)
1373 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
1378 struct move m
= { pass
, color
};
1384 board_is_false_eyelike(struct board
*board
, coord_t coord
, enum stone eye_color
)
1386 enum stone color_diag_libs
[S_MAX
] = {0, 0, 0, 0};
1388 /* XXX: We attempt false eye detection but we will yield false
1389 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
1391 foreach_diag_neighbor(board
, coord
) {
1392 color_diag_libs
[(enum stone
) board_at(board
, c
)]++;
1393 } foreach_diag_neighbor_end
;
1394 /* For false eye, we need two enemy stones diagonally in the
1395 * middle of the board, or just one enemy stone at the edge
1396 * or in the corner. */
1397 color_diag_libs
[stone_other(eye_color
)] += !!color_diag_libs
[S_OFFBOARD
];
1398 return color_diag_libs
[stone_other(eye_color
)] >= 2;
1402 board_is_one_point_eye(struct board
*board
, coord_t coord
, enum stone eye_color
)
1404 return board_is_eyelike(board
, coord
, eye_color
)
1405 && !board_is_false_eyelike(board
, coord
, eye_color
);
1409 board_get_one_point_eye(struct board
*board
, coord_t coord
)
1411 if (board_is_one_point_eye(board
, coord
, S_WHITE
))
1413 else if (board_is_one_point_eye(board
, coord
, S_BLACK
))
1421 board_fast_score(struct board
*board
)
1424 memset(scores
, 0, sizeof(scores
));
1426 foreach_point(board
) {
1427 enum stone color
= board_at(board
, c
);
1428 if (color
== S_NONE
)
1429 color
= board_get_one_point_eye(board
, c
);
1431 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1432 } foreach_point_end
;
1434 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];
1437 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1439 /* One flood-fill iteration; returns true if next iteration
1442 board_tromp_taylor_iter(struct board
*board
, int *ownermap
)
1444 bool needs_update
= false;
1445 foreach_free_point(board
) {
1446 /* Ignore occupied and already-dame positions. */
1447 assert(board_at(board
, c
) == S_NONE
);
1448 if (ownermap
[c
] == 3)
1450 /* Count neighbors. */
1452 foreach_neighbor(board
, c
, {
1455 /* If we have neighbors of both colors, or dame,
1456 * we are dame too. */
1457 if ((nei
[1] && nei
[2]) || nei
[3]) {
1459 /* Speed up the propagation. */
1460 foreach_neighbor(board
, c
, {
1461 if (board_at(board
, c
) == S_NONE
)
1464 needs_update
= true;
1467 /* If we have neighbors of one color, we are owned
1468 * by that color, too. */
1469 if (!ownermap
[c
] && (nei
[1] || nei
[2])) {
1470 int newowner
= nei
[1] ? 1 : 2;
1471 ownermap
[c
] = newowner
;
1472 /* Speed up the propagation. */
1473 foreach_neighbor(board
, c
, {
1474 if (board_at(board
, c
) == S_NONE
&& !ownermap
[c
])
1475 ownermap
[c
] = newowner
;
1477 needs_update
= true;
1480 } foreach_free_point_end
;
1481 return needs_update
;
1484 /* Tromp-Taylor Counting */
1486 board_official_score(struct board
*board
, struct move_queue
*q
)
1489 /* A point P, not colored C, is said to reach C, if there is a path of
1490 * (vertically or horizontally) adjacent points of P's color from P to
1491 * a point of color C.
1493 * A player's score is the number of points of her color, plus the
1494 * number of empty points that reach only her color. */
1496 int ownermap
[board_size2(board
)];
1498 const int o
[4] = {0, 1, 2, 0};
1499 foreach_point(board
) {
1500 ownermap
[c
] = o
[board_at(board
, c
)];
1501 s
[board_at(board
, c
)]++;
1502 } foreach_point_end
;
1505 /* Process dead groups. */
1506 for (unsigned int i
= 0; i
< q
->moves
; i
++) {
1507 foreach_in_group(board
, q
->move
[i
]) {
1508 enum stone color
= board_at(board
, c
);
1509 ownermap
[c
] = o
[stone_other(color
)];
1510 s
[color
]--; s
[stone_other(color
)]++;
1511 } foreach_in_group_end
;
1515 /* We need to special-case empty board. */
1516 if (!s
[S_BLACK
] && !s
[S_WHITE
])
1517 return board
->komi
+ board
->handicap
;
1519 while (board_tromp_taylor_iter(board
, ownermap
))
1520 /* Flood-fill... */;
1523 memset(scores
, 0, sizeof(scores
));
1525 foreach_point(board
) {
1526 assert(board_at(board
, c
) == S_OFFBOARD
|| ownermap
[c
] != 0);
1527 if (ownermap
[c
] == 3)
1529 scores
[ownermap
[c
]]++;
1530 } foreach_point_end
;
1532 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];