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_alloc(struct board
*board
)
62 /* We do not allocate the board structure itself but we allocate
63 * all the arrays with board contents. */
65 int bsize
= board_size2(board
) * sizeof(*board
->b
);
66 int gsize
= board_size2(board
) * sizeof(*board
->g
);
67 int fsize
= board_size2(board
) * sizeof(*board
->f
);
68 int nsize
= board_size2(board
) * sizeof(*board
->n
);
69 int psize
= board_size2(board
) * sizeof(*board
->p
);
70 int hsize
= board_size2(board
) * 2 * sizeof(*board
->h
);
71 int gisize
= board_size2(board
) * sizeof(*board
->gi
);
73 int csize
= board_size2(board
) * sizeof(*board
->c
);
78 int ssize
= board_size2(board
) * sizeof(*board
->spathash
);
83 int p3size
= board_size2(board
) * sizeof(*board
->pat3
);
88 int tsize
= board_size2(board
) * sizeof(*board
->t
);
89 int tqsize
= board_size2(board
) * sizeof(*board
->t
);
95 int pbsize
= board_size2(board
) * sizeof(*board
->prob
[0].items
);
96 int rowpbsize
= board_size(board
) * sizeof(*board
->prob
[0].rowtotals
);
101 int cdsize
= board_size2(board
) * sizeof(*board
->coord
);
103 size_t size
= bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
+ ssize
+ p3size
+ tsize
+ tqsize
+ (pbsize
+ rowpbsize
) * 2 + cdsize
;
104 void *x
= malloc2(size
);
106 /* board->b must come first */
107 board
->b
= x
; x
+= bsize
;
108 board
->g
= x
; x
+= gsize
;
109 board
->f
= x
; x
+= fsize
;
110 board
->p
= x
; x
+= psize
;
111 board
->n
= x
; x
+= nsize
;
112 board
->h
= x
; x
+= hsize
;
113 board
->gi
= x
; x
+= gisize
;
115 board
->c
= x
; x
+= csize
;
117 #ifdef BOARD_SPATHASH
118 board
->spathash
= x
; x
+= ssize
;
121 board
->pat3
= x
; x
+= p3size
;
124 board
->t
= x
; x
+= tsize
;
125 board
->tq
= x
; x
+= tqsize
;
128 board
->prob
[0].items
= x
; x
+= pbsize
;
129 board
->prob
[1].items
= x
; x
+= pbsize
;
130 board
->prob
[0].rowtotals
= x
; x
+= rowpbsize
;
131 board
->prob
[1].rowtotals
= x
; x
+= rowpbsize
;
133 board
->coord
= x
; x
+= cdsize
;
139 board_copy(struct board
*b2
, struct board
*b1
)
141 memcpy(b2
, b1
, sizeof(struct board
));
143 size_t size
= board_alloc(b2
);
144 memcpy(b2
->b
, b1
->b
, size
);
150 board_done_noalloc(struct board
*board
)
152 if (board
->b
) free(board
->b
);
156 board_done(struct board
*board
)
158 board_done_noalloc(board
);
163 board_resize(struct board
*board
, int size
)
166 assert(board_size(board
) == size
+ 2);
168 board
->size
= size
+ 2 /* S_OFFBOARD margin */;
169 board
->size2
= board_size(board
) * board_size(board
);
172 while ((1 << board
->bits2
) < board
->size2
) board
->bits2
++;
177 size_t asize
= board_alloc(board
);
178 memset(board
->b
, 0, asize
);
182 board_clear(struct board
*board
)
184 int size
= board_size(board
);
185 float komi
= board
->komi
;
187 board_done_noalloc(board
);
189 board_resize(board
, size
- 2 /* S_OFFBOARD margin */);
193 /* Setup neighborhood iterators */
194 board
->nei8
[0] = -size
- 1; // (-1,-1)
197 board
->nei8
[3] = size
- 2; // (-1,0)
199 board
->nei8
[5] = size
- 2; // (-1,1)
202 board
->dnei
[0] = -size
- 1;
204 board
->dnei
[2] = size
*2 - 2;
207 /* Setup initial symmetry */
208 board
->symmetry
.d
= 1;
209 board
->symmetry
.x1
= board
->symmetry
.y1
= board_size(board
) / 2;
210 board
->symmetry
.x2
= board
->symmetry
.y2
= board_size(board
) - 1;
211 board
->symmetry
.type
= SYM_FULL
;
213 /* Set up coordinate cache */
214 foreach_point(board
) {
215 board
->coord
[c
][0] = c
% board_size(board
);
216 board
->coord
[c
][1] = c
/ board_size(board
);
219 /* Draw the offboard margin */
220 int top_row
= board_size2(board
) - board_size(board
);
222 for (i
= 0; i
< board_size(board
); i
++)
223 board
->b
[i
] = board
->b
[top_row
+ i
] = S_OFFBOARD
;
224 for (i
= 0; i
<= top_row
; i
+= board_size(board
))
225 board
->b
[i
] = board
->b
[board_size(board
) - 1 + i
] = S_OFFBOARD
;
227 foreach_point(board
) {
229 if (board_at(board
, coord
) == S_OFFBOARD
)
231 foreach_neighbor(board
, c
, {
232 inc_neighbor_count_at(board
, coord
, board_at(board
, c
));
236 /* All positions are free! Except the margin. */
237 for (i
= board_size(board
); i
< (board_size(board
) - 1) * board_size(board
); i
++)
238 if (i
% board_size(board
) != 0 && i
% board_size(board
) != board_size(board
) - 1)
239 board
->f
[board
->flen
++] = i
;
241 /* Initialize zobrist hashtable. */
242 foreach_point(board
) {
243 int max
= (sizeof(hash_t
) << history_hash_bits
);
244 /* fast_random() is 16-bit only */
245 board
->h
[c
* 2] = ((hash_t
) fast_random(max
))
246 | ((hash_t
) fast_random(max
) << 16)
247 | ((hash_t
) fast_random(max
) << 32)
248 | ((hash_t
) fast_random(max
) << 48);
249 if (!board
->h
[c
* 2])
250 /* Would be kinda "oops". */
252 /* And once again for white */
253 board
->h
[c
* 2 + 1] = ((hash_t
) fast_random(max
))
254 | ((hash_t
) fast_random(max
) << 16)
255 | ((hash_t
) fast_random(max
) << 32)
256 | ((hash_t
) fast_random(max
) << 48);
257 if (!board
->h
[c
* 2 + 1])
258 board
->h
[c
* 2 + 1] = 1;
261 #ifdef BOARD_SPATHASH
262 /* Initialize spatial hashes. */
263 foreach_point(board
) {
264 for (int d
= 1; d
<= BOARD_SPATHASH_MAXD
; d
++) {
265 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
266 ptcoords_at(x
, y
, c
, board
, j
);
267 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][0] ^=
268 pthashes
[0][j
][board_at(board
, c
)];
269 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][1] ^=
270 pthashes
[0][j
][stone_other(board_at(board
, c
))];
276 /* Initialize 3x3 pattern codes. */
277 foreach_point(board
) {
278 if (board_at(board
, c
) == S_NONE
)
279 board
->pat3
[c
] = pattern3_hash(board
, c
);
283 /* Initialize traits. */
284 foreach_point(board
) {
285 trait_at(board
, c
, S_BLACK
).cap
= 0;
286 trait_at(board
, c
, S_BLACK
).safe
= true;
287 trait_at(board
, c
, S_WHITE
).cap
= 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
, (board_at(board
, c
) == S_NONE
) * 1.0f
);
295 probdist_set(&board
->prob
[1], c
, (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
)
425 value
*= board
->gamma
->gamma
[FEAT_CAPTURE
][0];
426 if (trait_at(board
, coord
, stone_other(color
)).cap
427 && trait_at(board
, coord
, color
).safe
)
428 value
*= board
->gamma
->gamma
[FEAT_AESCAPE
][0];
429 if (!trait_at(board
, coord
, color
).safe
)
430 value
*= board
->gamma
->gamma
[FEAT_SELFATARI
][1 + board
->precise_selfatari
];
431 probdist_set(&board
->prob
[color
- 1], coord
, value
);
437 board_trait_safe(struct board
*board
, coord_t coord
, enum stone color
)
440 if (board
->precise_selfatari
)
441 return is_bad_selfatari(board
, color
, coord
);
443 return board_safe_to_play(board
, coord
, color
);
447 board_trait_recompute(struct board
*board
, coord_t coord
)
449 trait_at(board
, coord
, S_BLACK
).safe
= board_trait_safe(board
, coord
, S_BLACK
);;
450 trait_at(board
, coord
, S_WHITE
).safe
= board_trait_safe(board
, coord
, S_WHITE
);
452 fprintf(stderr
, "traits[%s:%s lib=%d] (black cap=%d safe=%d) (white cap=%d safe=%d)\n",
453 coord2sstr(coord
, board
), stone2str(board_at(board
, coord
)), immediate_liberty_count(board
, coord
),
454 trait_at(board
, coord
, S_BLACK
).cap
, trait_at(board
, coord
, S_BLACK
).safe
,
455 trait_at(board
, coord
, S_WHITE
).cap
, trait_at(board
, coord
, S_WHITE
).safe
);
457 board_gamma_update(board
, coord
, S_BLACK
);
458 board_gamma_update(board
, coord
, S_WHITE
);
462 /* Recompute traits for dirty points that we have previously touched
463 * somehow (libs of their neighbors changed or so). */
465 board_traits_recompute(struct board
*board
)
468 for (int i
= 0; i
< board
->tqlen
; i
++) {
469 coord_t coord
= board
->tq
[i
];
470 if (!trait_at(board
, coord
, S_BLACK
).dirty
) continue;
471 if (board_at(board
, coord
) != S_NONE
) continue;
472 board_trait_recompute(board
, coord
);
473 trait_at(board
, coord
, S_BLACK
).dirty
= false;
479 /* Queue traits of given point for recomputing. */
481 board_trait_queue(struct board
*board
, coord_t coord
)
484 board
->tq
[board
->tqlen
++] = coord
;
485 trait_at(board
, coord
, S_BLACK
).dirty
= true;
490 /* Update board hash with given coordinate. */
491 static void profiling_noinline
492 board_hash_update(struct board
*board
, coord_t coord
, enum stone color
)
494 board
->hash
^= hash_at(board
, coord
, color
);
496 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
);
498 #ifdef BOARD_SPATHASH
499 /* Gridcular metric is reflective, so we update all hashes
500 * of appropriate ditance in OUR circle. */
501 for (int d
= 1; d
<= BOARD_SPATHASH_MAXD
; d
++) {
502 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
503 ptcoords_at(x
, y
, coord
, board
, j
);
504 /* We either changed from S_NONE to color
505 * or vice versa; doesn't matter. */
506 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][0] ^=
507 pthashes
[0][j
][color
] ^ pthashes
[0][j
][S_NONE
];
508 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][1] ^=
509 pthashes
[0][j
][stone_other(color
)] ^ pthashes
[0][j
][S_NONE
];
514 #if defined(BOARD_PAT3)
515 /* @color is not what we need in case of capture. */
516 enum stone new_color
= board_at(board
, coord
);
517 if (new_color
== S_NONE
)
518 board
->pat3
[coord
] = pattern3_hash(board
, coord
);
519 foreach_8neighbor(board
, coord
) { // internally, the loop uses fn__i=[0..7]
520 if (board_at(board
, c
) != S_NONE
)
522 board
->pat3
[c
] &= ~(3 << (fn__i
*2));
523 board
->pat3
[c
] |= new_color
<< (fn__i
*2);
525 if (board_at(board
, c
) != S_OFFBOARD
&& pattern3_hash(board
, c
) != board
->pat3
[c
]) {
526 board_print(board
, stderr
);
527 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
);
531 board_trait_queue(board
, c
);
532 } foreach_8neighbor_end
;
536 /* Commit current board hash to history. */
537 static void profiling_noinline
538 board_hash_commit(struct board
*board
)
541 fprintf(stderr
, "board_hash_commit %"PRIhash
"\n", board
->hash
);
542 if (likely(board
->history_hash
[board
->hash
& history_hash_mask
]) == 0) {
543 board
->history_hash
[board
->hash
& history_hash_mask
] = board
->hash
;
545 hash_t i
= board
->hash
;
546 while (board
->history_hash
[i
& history_hash_mask
]) {
547 if (board
->history_hash
[i
& history_hash_mask
] == board
->hash
) {
549 fprintf(stderr
, "SUPERKO VIOLATION noted at %d,%d\n",
550 coord_x(board
->last_move
.coord
, board
), coord_y(board
->last_move
.coord
, board
));
551 board
->superko_violation
= true;
554 i
= history_hash_next(i
);
556 board
->history_hash
[i
& history_hash_mask
] = board
->hash
;
562 board_symmetry_update(struct board
*b
, struct board_symmetry
*symmetry
, coord_t c
)
564 if (likely(symmetry
->type
== SYM_NONE
)) {
565 /* Fully degenerated already. We do not support detection
566 * of restoring of symmetry, assuming that this is too rare
567 * a case to handle. */
571 int x
= coord_x(c
, b
), y
= coord_y(c
, b
), t
= board_size(b
) / 2;
572 int dx
= board_size(b
) - 1 - x
; /* for SYM_DOWN */
574 fprintf(stderr
, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
575 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
576 symmetry
->d
, symmetry
->type
, x
, y
);
579 switch (symmetry
->type
) {
581 if (x
== t
&& y
== t
) {
582 /* Tengen keeps full symmetry. */
585 /* New symmetry now? */
587 symmetry
->type
= SYM_DIAG_UP
;
588 symmetry
->x1
= symmetry
->y1
= 1;
589 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
591 } else if (dx
== y
) {
592 symmetry
->type
= SYM_DIAG_DOWN
;
593 symmetry
->x1
= symmetry
->y1
= 1;
594 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
597 symmetry
->type
= SYM_HORIZ
;
599 symmetry
->y2
= board_size(b
) - 1;
602 symmetry
->type
= SYM_VERT
;
604 symmetry
->x2
= board_size(b
) - 1;
608 symmetry
->type
= SYM_NONE
;
609 symmetry
->x1
= symmetry
->y1
= 1;
610 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
636 fprintf(stderr
, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
637 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
638 symmetry
->d
, symmetry
->type
);
645 board_handicap_stone(struct board
*board
, int x
, int y
, FILE *f
)
648 m
.color
= S_BLACK
; m
.coord
= coord_xy(board
, x
, y
);
650 board_play(board
, &m
);
651 /* Simulate white passing; otherwise, UCT search can get confused since
652 * tree depth parity won't match the color to move. */
655 char *str
= coord2str(m
.coord
, board
);
657 fprintf(stderr
, "choosing handicap %s (%d,%d)\n", str
, x
, y
);
658 if (f
) fprintf(f
, "%s ", str
);
663 board_handicap(struct board
*board
, int stones
, FILE *f
)
665 int margin
= 3 + (board_size(board
) >= 13);
667 int mid
= board_size(board
) / 2;
668 int max
= board_size(board
) - 1 - margin
;
669 const int places
[][2] = {
670 { min
, min
}, { max
, max
}, { max
, min
}, { min
, max
},
671 { min
, mid
}, { max
, mid
},
672 { mid
, min
}, { mid
, max
},
676 board
->handicap
= stones
;
678 if (stones
== 5 || stones
== 7) {
679 board_handicap_stone(board
, mid
, mid
, f
);
684 for (i
= 0; i
< stones
; i
++)
685 board_handicap_stone(board
, places
[i
][0], places
[i
][1], f
);
689 static void __attribute__((noinline
))
690 check_libs_consistency(struct board
*board
, group_t g
)
694 struct group
*gi
= &board_group_info(board
, g
);
695 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
696 if (gi
->lib
[i
] && board_at(board
, gi
->lib
[i
]) != S_NONE
) {
697 fprintf(stderr
, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi
->lib
[i
], board
), g
, coord2sstr(group_base(g
), board
));
704 board_capturable_add(struct board
*board
, group_t group
, coord_t lib
)
706 //fprintf(stderr, "group %s cap %s\n", coord2sstr(group, board), coord2sstr(lib, boarD));
708 /* Increase capturable count trait of my last lib. */
709 enum stone capturing_color
= stone_other(board_at(board
, group
));
710 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
711 foreach_neighbor(board
, lib
, {
712 if (DEBUGL(8) && group_at(board
, c
) == group
)
713 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
));
714 trait_at(board
, lib
, capturing_color
).cap
+= (group_at(board
, c
) == group
);
716 board_trait_queue(board
, lib
);
720 /* Update the list of capturable groups. */
722 assert(board
->clen
< board_size2(board
));
723 board
->c
[board
->clen
++] = group
;
727 board_capturable_rm(struct board
*board
, group_t group
, coord_t lib
)
729 //fprintf(stderr, "group %s nocap %s\n", coord2sstr(group, board), coord2sstr(lib, board));
731 /* Decrease capturable count trait of my previously-last lib. */
732 enum stone capturing_color
= stone_other(board_at(board
, group
));
733 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
734 foreach_neighbor(board
, lib
, {
735 if (DEBUGL(8) && group_at(board
, c
) == group
)
736 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
));
737 trait_at(board
, lib
, capturing_color
).cap
-= (group_at(board
, c
) == group
);
739 board_trait_queue(board
, lib
);
743 /* Update the list of capturable groups. */
744 for (int i
= 0; i
< board
->clen
; i
++) {
745 if (unlikely(board
->c
[i
] == group
)) {
746 board
->c
[i
] = board
->c
[--board
->clen
];
750 fprintf(stderr
, "rm of bad group %d\n", group_base(group
));
756 board_atariable_add(struct board
*board
, group_t group
, coord_t lib1
, coord_t lib2
)
759 board_trait_queue(board
, lib1
);
760 board_trait_queue(board
, lib2
);
764 board_atariable_rm(struct board
*board
, group_t group
, coord_t lib1
, coord_t lib2
)
767 board_trait_queue(board
, lib1
);
768 board_trait_queue(board
, lib2
);
773 board_group_addlib(struct board
*board
, group_t group
, coord_t coord
)
776 fprintf(stderr
, "Group %d[%s] %d: Adding liberty %s\n",
777 group_base(group
), coord2sstr(group_base(group
), board
),
778 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
781 check_libs_consistency(board
, group
);
783 struct group
*gi
= &board_group_info(board
, group
);
784 if (gi
->libs
< GROUP_KEEP_LIBS
) {
785 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
787 /* Seems extra branch just slows it down */
791 if (unlikely(gi
->lib
[i
] == coord
))
795 board_capturable_add(board
, group
, coord
);
796 } else if (gi
->libs
== 1) {
797 board_capturable_rm(board
, group
, gi
->lib
[0]);
798 board_atariable_add(board
, group
, gi
->lib
[0], coord
);
799 } else if (gi
->libs
== 2) {
800 board_atariable_rm(board
, group
, gi
->lib
[0], gi
->lib
[1]);
802 gi
->lib
[gi
->libs
++] = coord
;
805 check_libs_consistency(board
, group
);
809 board_group_find_extra_libs(struct board
*board
, group_t group
, struct group
*gi
, coord_t avoid
)
811 /* Add extra liberty from the board to our liberty list. */
812 unsigned char watermark
[board_size2(board
) / 8];
813 memset(watermark
, 0, sizeof(watermark
));
814 #define watermark_get(c) (watermark[c >> 3] & (1 << (c & 7)))
815 #define watermark_set(c) watermark[c >> 3] |= (1 << (c & 7))
817 for (int i
= 0; i
< GROUP_KEEP_LIBS
- 1; i
++)
818 watermark_set(gi
->lib
[i
]);
819 watermark_set(avoid
);
821 foreach_in_group(board
, group
) {
823 foreach_neighbor(board
, coord2
, {
824 if (board_at(board
, c
) + watermark_get(c
) != S_NONE
)
827 gi
->lib
[gi
->libs
++] = c
;
828 if (unlikely(gi
->libs
>= GROUP_KEEP_LIBS
))
831 } foreach_in_group_end
;
837 board_group_rmlib(struct board
*board
, group_t group
, coord_t coord
)
840 fprintf(stderr
, "Group %d[%s] %d: Removing liberty %s\n",
841 group_base(group
), coord2sstr(group_base(group
), board
),
842 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
845 struct group
*gi
= &board_group_info(board
, group
);
846 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
848 /* Seems extra branch just slows it down */
852 if (likely(gi
->lib
[i
] != coord
))
855 coord_t lib
= gi
->lib
[i
] = gi
->lib
[--gi
->libs
];
856 gi
->lib
[gi
->libs
] = 0;
858 check_libs_consistency(board
, group
);
860 /* Postpone refilling lib[] until we need to. */
861 assert(GROUP_REFILL_LIBS
> 1);
862 if (gi
->libs
> GROUP_REFILL_LIBS
)
864 if (gi
->libs
== GROUP_REFILL_LIBS
)
865 board_group_find_extra_libs(board
, group
, gi
, coord
);
868 board_atariable_add(board
, group
, gi
->lib
[0], gi
->lib
[1]);
869 } else if (gi
->libs
== 1) {
870 board_capturable_add(board
, group
, gi
->lib
[0]);
871 board_atariable_rm(board
, group
, gi
->lib
[0], lib
);
872 } else if (gi
->libs
== 0)
873 board_capturable_rm(board
, group
, lib
);
877 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
878 * can call this multiple times per coord. */
879 check_libs_consistency(board
, group
);
884 /* This is a low-level routine that doesn't maintain consistency
885 * of all the board data structures. */
887 board_remove_stone(struct board
*board
, group_t group
, coord_t c
)
889 enum stone color
= board_at(board
, c
);
890 board_at(board
, c
) = S_NONE
;
891 group_at(board
, c
) = 0;
892 board_hash_update(board
, c
, color
);
894 /* We mark as cannot-capture now. If this is a ko/snapback,
895 * we will get incremented later in board_group_addlib(). */
896 trait_at(board
, c
, S_BLACK
).cap
= 0;
897 trait_at(board
, c
, S_WHITE
).cap
= 0;
898 board_trait_queue(board
, c
);
901 /* Increase liberties of surrounding groups */
903 foreach_neighbor(board
, coord
, {
904 dec_neighbor_count_at(board
, c
, color
);
905 board_trait_queue(board
, c
);
906 group_t g
= group_at(board
, c
);
908 board_group_addlib(board
, g
, coord
);
912 fprintf(stderr
, "pushing free move [%d]: %d,%d\n", board
->flen
, coord_x(c
, board
), coord_y(c
, board
));
913 board
->f
[board
->flen
++] = c
;
916 static int profiling_noinline
917 board_group_capture(struct board
*board
, group_t group
)
921 foreach_in_group(board
, group
) {
922 board
->captures
[stone_other(board_at(board
, c
))]++;
923 board_remove_stone(board
, group
, c
);
925 } foreach_in_group_end
;
927 struct group
*gi
= &board_group_info(board
, group
);
929 board_atariable_rm(board
, group
, gi
->lib
[0], gi
->lib
[1]);
930 else if (gi
->libs
== 1)
931 board_capturable_rm(board
, group
, gi
->lib
[0]);
932 memset(gi
, 0, sizeof(*gi
));
938 static void profiling_noinline
939 add_to_group(struct board
*board
, group_t group
, coord_t prevstone
, coord_t coord
)
941 group_at(board
, coord
) = group
;
942 groupnext_at(board
, coord
) = groupnext_at(board
, prevstone
);
943 groupnext_at(board
, prevstone
) = coord
;
946 if (board_group_info(board
, group
).libs
== 1) {
947 /* Our group is temporarily in atari; make sure the capturable
948 * counts also correspond to the newly added stone before we
949 * start adding liberties again so bump-dump ops match. */
950 enum stone capturing_color
= stone_other(board_at(board
, group
));
951 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
952 coord_t lib
= board_group_info(board
, group
).lib
[0];
953 if (coord_is_adjecent(lib
, coord
, board
)) {
954 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
);
955 trait_at(board
, lib
, capturing_color
).cap
++;
956 board_trait_queue(board
, lib
);
961 foreach_neighbor(board
, coord
, {
962 if (board_at(board
, c
) == S_NONE
)
963 board_group_addlib(board
, group
, c
);
967 fprintf(stderr
, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
968 coord_x(prevstone
, board
), coord_y(prevstone
, board
),
969 coord_x(coord
, board
), coord_y(coord
, board
),
970 groupnext_at(board
, coord
) % board_size(board
), groupnext_at(board
, coord
) / board_size(board
),
974 static void profiling_noinline
975 merge_groups(struct board
*board
, group_t group_to
, group_t group_from
)
978 fprintf(stderr
, "board_play_raw: merging groups %d -> %d\n",
979 group_base(group_from
), group_base(group_to
));
980 struct group
*gi_from
= &board_group_info(board
, group_from
);
981 struct group
*gi_to
= &board_group_info(board
, group_to
);
983 /* We do this early before the group info is rewritten. */
984 if (gi_from
->libs
== 2)
985 board_atariable_rm(board
, group_from
, gi_from
->lib
[0], gi_from
->lib
[1]);
986 else if (gi_from
->libs
== 1)
987 board_capturable_rm(board
, group_from
, gi_from
->lib
[0]);
990 fprintf(stderr
,"---- (froml %d, tol %d)\n", gi_from
->libs
, gi_to
->libs
);
992 if (gi_to
->libs
< GROUP_KEEP_LIBS
) {
993 for (int i
= 0; i
< gi_from
->libs
; i
++) {
994 for (int j
= 0; j
< gi_to
->libs
; j
++)
995 if (gi_to
->lib
[j
] == gi_from
->lib
[i
])
997 if (gi_to
->libs
== 0) {
998 board_capturable_add(board
, group_to
, gi_from
->lib
[i
]);
999 } else if (gi_to
->libs
== 1) {
1000 board_capturable_rm(board
, group_to
, gi_to
->lib
[0]);
1001 board_atariable_add(board
, group_to
, gi_to
->lib
[0], gi_from
->lib
[i
]);
1002 } else if (gi_to
->libs
== 2) {
1003 board_atariable_rm(board
, group_to
, gi_to
->lib
[0], gi_to
->lib
[1]);
1005 gi_to
->lib
[gi_to
->libs
++] = gi_from
->lib
[i
];
1006 if (gi_to
->libs
>= GROUP_KEEP_LIBS
)
1013 if (board_group_info(board
, group_to
).libs
== 1) {
1014 /* Our group is currently in atari; make sure we properly
1015 * count in even the neighbors from the other group in the
1016 * capturable counter. */
1017 enum stone capturing_color
= stone_other(board_at(board
, group_to
));
1018 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
1019 coord_t lib
= board_group_info(board
, group_to
).lib
[0];
1020 foreach_neighbor(board
, lib
, {
1021 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
);
1022 trait_at(board
, lib
, capturing_color
).cap
+= (group_at(board
, c
) == group_from
);
1024 board_trait_queue(board
, lib
);
1028 coord_t last_in_group
;
1029 foreach_in_group(board
, group_from
) {
1031 group_at(board
, c
) = group_to
;
1032 } foreach_in_group_end
;
1033 groupnext_at(board
, last_in_group
) = groupnext_at(board
, group_base(group_to
));
1034 groupnext_at(board
, group_base(group_to
)) = group_base(group_from
);
1035 memset(gi_from
, 0, sizeof(struct group
));
1038 fprintf(stderr
, "board_play_raw: merged group: %d\n",
1039 group_base(group_to
));
1042 static group_t profiling_noinline
1043 new_group(struct board
*board
, coord_t coord
)
1045 group_t group
= coord
;
1046 struct group
*gi
= &board_group_info(board
, group
);
1047 foreach_neighbor(board
, coord
, {
1048 if (board_at(board
, c
) == S_NONE
)
1049 /* board_group_addlib is ridiculously expensive for us */
1050 #if GROUP_KEEP_LIBS < 4
1051 if (gi
->libs
< GROUP_KEEP_LIBS
)
1053 gi
->lib
[gi
->libs
++] = c
;
1056 group_at(board
, coord
) = group
;
1057 groupnext_at(board
, coord
) = 0;
1060 board_atariable_add(board
, group
, gi
->lib
[0], gi
->lib
[1]);
1061 else if (gi
->libs
== 1)
1062 board_capturable_add(board
, group
, gi
->lib
[0]);
1063 check_libs_consistency(board
, group
);
1066 fprintf(stderr
, "new_group: added %d,%d to group %d\n",
1067 coord_x(coord
, board
), coord_y(coord
, board
),
1073 static inline group_t
1074 play_one_neighbor(struct board
*board
,
1075 coord_t coord
, enum stone color
, enum stone other_color
,
1076 coord_t c
, group_t group
)
1078 enum stone ncolor
= board_at(board
, c
);
1079 group_t ngroup
= group_at(board
, c
);
1081 inc_neighbor_count_at(board
, c
, color
);
1082 /* We can be S_NONE, in that case we need to update the safety
1083 * trait since we might be left with only one liberty. */
1084 board_trait_queue(board
, c
);
1089 board_group_rmlib(board
, ngroup
, coord
);
1091 fprintf(stderr
, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
1092 group_base(ngroup
), ncolor
, color
, other_color
);
1094 if (ncolor
== color
&& ngroup
!= group
) {
1097 add_to_group(board
, group
, c
, coord
);
1099 merge_groups(board
, group
, ngroup
);
1101 } else if (ncolor
== other_color
) {
1103 struct group
*gi
= &board_group_info(board
, ngroup
);
1104 fprintf(stderr
, "testing captured group %d[%s]: ", group_base(ngroup
), coord2sstr(group_base(ngroup
), board
));
1105 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
1106 fprintf(stderr
, "%s ", coord2sstr(gi
->lib
[i
], board
));
1107 fprintf(stderr
, "\n");
1109 if (unlikely(board_group_captured(board
, ngroup
)))
1110 board_group_capture(board
, ngroup
);
1115 /* We played on a place with at least one liberty. We will become a member of
1116 * some group for sure. */
1117 static group_t profiling_noinline
1118 board_play_outside(struct board
*board
, struct move
*m
, int f
)
1120 coord_t coord
= m
->coord
;
1121 enum stone color
= m
->color
;
1122 enum stone other_color
= stone_other(color
);
1125 board
->f
[f
] = board
->f
[--board
->flen
];
1127 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
1129 #if defined(BOARD_TRAITS) && defined(DEBUG)
1130 /* Sanity check that cap matches reality. */
1133 foreach_neighbor(board
, coord
, {
1134 group_t g
= group_at(board
, c
);
1135 a
+= g
&& (board_at(board
, c
) == other_color
&& board_group_info(board
, g
).libs
== 1);
1137 assert(a
== trait_at(board
, coord
, color
).cap
);
1138 assert(board_trait_safe(board
, coord
, color
) == trait_at(board
, coord
, color
).safe
);
1141 foreach_neighbor(board
, coord
, {
1142 group
= play_one_neighbor(board
, coord
, color
, other_color
, c
, group
);
1145 board_at(board
, coord
) = color
;
1146 if (unlikely(!group
))
1147 group
= new_group(board
, coord
);
1148 board_gamma_update(board
, coord
, S_BLACK
);
1149 board_gamma_update(board
, coord
, S_WHITE
);
1151 board
->last_move2
= board
->last_move
;
1152 board
->last_move
= *m
;
1154 board_hash_update(board
, coord
, color
);
1155 board_symmetry_update(board
, &board
->symmetry
, coord
);
1156 struct move ko
= { pass
, S_NONE
};
1162 /* We played in an eye-like shape. Either we capture at least one of the eye
1163 * sides in the process of playing, or return -1. */
1164 static int profiling_noinline
1165 board_play_in_eye(struct board
*board
, struct move
*m
, int f
)
1167 coord_t coord
= m
->coord
;
1168 enum stone color
= m
->color
;
1169 /* Check ko: Capture at a position of ko capture one move ago */
1170 if (unlikely(color
== board
->ko
.color
&& coord
== board
->ko
.coord
)) {
1172 fprintf(stderr
, "board_check: ko at %d,%d color %d\n", coord_x(coord
, board
), coord_y(coord
, board
), color
);
1174 } else if (DEBUGL(6)) {
1175 fprintf(stderr
, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
1176 color
, coord_x(coord
, board
), coord_y(coord
, board
),
1177 board
->ko
.color
, coord_x(board
->ko
.coord
, board
), coord_y(board
->ko
.coord
, board
));
1180 struct move ko
= { pass
, S_NONE
};
1182 int captured_groups
= 0;
1184 foreach_neighbor(board
, coord
, {
1185 group_t g
= group_at(board
, c
);
1187 fprintf(stderr
, "board_check: group %d has %d libs\n",
1188 g
, board_group_info(board
, g
).libs
);
1189 captured_groups
+= (board_group_info(board
, g
).libs
== 1);
1192 if (likely(captured_groups
== 0)) {
1195 board_print(board
, stderr
);
1196 fprintf(stderr
, "board_check: one-stone suicide\n");
1202 /* We _will_ for sure capture something. */
1203 assert(trait_at(board
, coord
, color
).cap
> 0);
1204 assert(trait_at(board
, coord
, color
).safe
== board_trait_safe(board
, coord
, color
));
1207 board
->f
[f
] = board
->f
[--board
->flen
];
1209 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
1211 foreach_neighbor(board
, coord
, {
1212 inc_neighbor_count_at(board
, c
, color
);
1213 /* Originally, this could not have changed any trait
1214 * since no neighbors were S_NONE, however by now some
1215 * of them might be removed from the board. */
1216 board_trait_queue(board
, c
);
1218 group_t group
= group_at(board
, c
);
1222 board_group_rmlib(board
, group
, coord
);
1224 fprintf(stderr
, "board_play_raw: reducing libs for group %d\n",
1227 if (board_group_captured(board
, group
)) {
1228 if (board_group_capture(board
, group
) == 1) {
1229 /* If we captured multiple groups at once,
1230 * we can't be fighting ko so we don't need
1231 * to check for that. */
1232 ko
.color
= stone_other(color
);
1234 board
->last_ko
= ko
;
1235 board
->last_ko_age
= board
->moves
;
1237 fprintf(stderr
, "guarding ko at %d,%s\n", ko
.color
, coord2sstr(ko
.coord
, board
));
1242 board_at(board
, coord
) = color
;
1243 group_t group
= new_group(board
, coord
);
1244 board_gamma_update(board
, coord
, S_BLACK
);
1245 board_gamma_update(board
, coord
, S_WHITE
);
1247 board
->last_move2
= board
->last_move
;
1248 board
->last_move
= *m
;
1250 board_hash_update(board
, coord
, color
);
1251 board_hash_commit(board
);
1252 board_traits_recompute(board
);
1253 board_symmetry_update(board
, &board
->symmetry
, coord
);
1259 static int __attribute__((flatten
))
1260 board_play_f(struct board
*board
, struct move
*m
, int f
)
1263 fprintf(stderr
, "board_play(): ---- Playing %d,%d\n", coord_x(m
->coord
, board
), coord_y(m
->coord
, board
));
1265 if (likely(!board_is_eyelike(board
, m
->coord
, stone_other(m
->color
)))) {
1266 /* NOT playing in an eye. Thus this move has to succeed. (This
1267 * is thanks to New Zealand rules. Otherwise, multi-stone
1268 * suicide might fail.) */
1269 group_t group
= board_play_outside(board
, m
, f
);
1270 if (unlikely(board_group_captured(board
, group
))) {
1271 board_group_capture(board
, group
);
1273 board_hash_commit(board
);
1274 board_traits_recompute(board
);
1277 return board_play_in_eye(board
, m
, f
);
1282 board_play(struct board
*board
, struct move
*m
)
1284 if (unlikely(is_pass(m
->coord
) || is_resign(m
->coord
))) {
1285 struct move nomove
= { pass
, S_NONE
};
1287 board
->last_move2
= board
->last_move
;
1288 board
->last_move
= *m
;
1293 for (f
= 0; f
< board
->flen
; f
++)
1294 if (board
->f
[f
] == m
->coord
)
1295 return board_play_f(board
, m
, f
);
1298 fprintf(stderr
, "board_check: stone exists\n");
1304 board_try_random_move(struct board
*b
, enum stone color
, coord_t
*coord
, int f
, ppr_permit permit
, void *permit_data
)
1307 struct move m
= { *coord
, color
};
1309 fprintf(stderr
, "trying random move %d: %d,%d\n", f
, coord_x(*coord
, b
), coord_y(*coord
, b
));
1310 if (unlikely(board_is_one_point_eye(b
, *coord
, color
)) /* bad idea to play into one, usually */
1311 || !board_is_valid_move(b
, &m
)
1312 || (permit
&& !permit(permit_data
, b
, &m
)))
1314 *coord
= m
.coord
; // permit might modify it
1315 return likely(board_play_f(b
, &m
, f
) >= 0);
1319 board_play_random(struct board
*b
, enum stone color
, coord_t
*coord
, ppr_permit permit
, void *permit_data
)
1321 if (unlikely(b
->flen
== 0))
1324 int base
= fast_random(b
->flen
), f
;
1325 for (f
= base
; f
< b
->flen
; f
++)
1326 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
1328 for (f
= 0; f
< base
; f
++)
1329 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
1334 struct move m
= { pass
, color
};
1340 board_is_false_eyelike(struct board
*board
, coord_t coord
, enum stone eye_color
)
1342 enum stone color_diag_libs
[S_MAX
] = {0, 0, 0, 0};
1344 /* XXX: We attempt false eye detection but we will yield false
1345 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
1347 foreach_diag_neighbor(board
, coord
) {
1348 color_diag_libs
[(enum stone
) board_at(board
, c
)]++;
1349 } foreach_diag_neighbor_end
;
1350 /* For false eye, we need two enemy stones diagonally in the
1351 * middle of the board, or just one enemy stone at the edge
1352 * or in the corner. */
1353 color_diag_libs
[stone_other(eye_color
)] += !!color_diag_libs
[S_OFFBOARD
];
1354 return color_diag_libs
[stone_other(eye_color
)] >= 2;
1358 board_is_one_point_eye(struct board
*board
, coord_t coord
, enum stone eye_color
)
1360 return board_is_eyelike(board
, coord
, eye_color
)
1361 && !board_is_false_eyelike(board
, coord
, eye_color
);
1365 board_get_one_point_eye(struct board
*board
, coord_t coord
)
1367 if (board_is_one_point_eye(board
, coord
, S_WHITE
))
1369 else if (board_is_one_point_eye(board
, coord
, S_BLACK
))
1377 board_fast_score(struct board
*board
)
1380 memset(scores
, 0, sizeof(scores
));
1382 foreach_point(board
) {
1383 enum stone color
= board_at(board
, c
);
1384 if (color
== S_NONE
)
1385 color
= board_get_one_point_eye(board
, c
);
1387 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1388 } foreach_point_end
;
1390 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];
1393 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1395 /* One flood-fill iteration; returns true if next iteration
1398 board_tromp_taylor_iter(struct board
*board
, int *ownermap
)
1400 bool needs_update
= false;
1401 foreach_point(board
) {
1402 /* Ignore occupied and already-dame positions. */
1403 if (board_at(board
, c
) != S_NONE
|| ownermap
[c
] == 3)
1405 /* Count neighbors. */
1407 foreach_neighbor(board
, c
, {
1410 /* If we have neighbors of both colors, or dame,
1411 * we are dame too. */
1412 if ((nei
[1] && nei
[2]) || nei
[3]) {
1414 /* Speed up the propagation. */
1415 foreach_neighbor(board
, c
, {
1416 if (board_at(board
, c
) == S_NONE
)
1419 needs_update
= true;
1422 /* If we have neighbors of one color, we are owned
1423 * by that color, too. */
1424 if (!ownermap
[c
] && (nei
[1] || nei
[2])) {
1425 int newowner
= nei
[1] ? 1 : 2;
1426 ownermap
[c
] = newowner
;
1427 /* Speed up the propagation. */
1428 foreach_neighbor(board
, c
, {
1429 if (board_at(board
, c
) == S_NONE
&& !ownermap
[c
])
1430 ownermap
[c
] = newowner
;
1432 needs_update
= true;
1435 } foreach_point_end
;
1436 return needs_update
;
1439 /* Tromp-Taylor Counting */
1441 board_official_score(struct board
*board
, struct move_queue
*q
)
1444 /* A point P, not colored C, is said to reach C, if there is a path of
1445 * (vertically or horizontally) adjacent points of P's color from P to
1446 * a point of color C.
1448 * A player's score is the number of points of her color, plus the
1449 * number of empty points that reach only her color. */
1451 int ownermap
[board_size2(board
)];
1453 const int o
[4] = {0, 1, 2, 0};
1454 foreach_point(board
) {
1455 ownermap
[c
] = o
[board_at(board
, c
)];
1456 s
[board_at(board
, c
)]++;
1457 } foreach_point_end
;
1460 /* Process dead groups. */
1461 for (unsigned int i
= 0; i
< q
->moves
; i
++) {
1462 foreach_in_group(board
, q
->move
[i
]) {
1463 enum stone color
= board_at(board
, c
);
1464 ownermap
[c
] = o
[stone_other(color
)];
1465 s
[color
]--; s
[stone_other(color
)]++;
1466 } foreach_in_group_end
;
1470 /* We need to special-case empty board. */
1471 if (!s
[S_BLACK
] && !s
[S_WHITE
])
1472 return board
->komi
+ board
->handicap
;
1474 while (board_tromp_taylor_iter(board
, ownermap
))
1475 /* Flood-fill... */;
1478 memset(scores
, 0, sizeof(scores
));
1480 foreach_point(board
) {
1481 assert(board_at(board
, c
) == S_OFFBOARD
|| ownermap
[c
] != 0);
1482 if (ownermap
[c
] == 3)
1484 scores
[ownermap
[c
]]++;
1485 } foreach_point_end
;
1487 return board
->komi
+ board
->handicap
+ scores
[S_WHITE
] - scores
[S_BLACK
];