15 #include "patternsp.h"
21 static void board_trait_recompute(struct board
*board
, coord_t coord
);
22 #include "tactics/selfatari.h"
27 #define profiling_noinline __attribute__((noinline))
29 #define profiling_noinline
32 #define gi_granularity 4
33 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
37 board_setup(struct board
*b
)
39 memset(b
, 0, sizeof(*b
));
41 struct move m
= { pass
, S_NONE
};
42 b
->last_move
= b
->last_move2
= b
->last_move3
= b
->last_move4
= b
->last_ko
= b
->ko
= m
;
46 board_init(char *fbookfile
)
48 struct board
*b
= malloc2(sizeof(struct board
));
51 b
->fbookfile
= fbookfile
;
61 board_alloc(struct board
*board
)
63 /* We do not allocate the board structure itself but we allocate
64 * all the arrays with board contents. */
66 int bsize
= board_size2(board
) * sizeof(*board
->b
);
67 int gsize
= board_size2(board
) * sizeof(*board
->g
);
68 int fsize
= board_size2(board
) * sizeof(*board
->f
);
69 int nsize
= board_size2(board
) * sizeof(*board
->n
);
70 int psize
= board_size2(board
) * sizeof(*board
->p
);
71 int hsize
= board_size2(board
) * 2 * sizeof(*board
->h
);
72 int gisize
= board_size2(board
) * sizeof(*board
->gi
);
74 int csize
= board_size2(board
) * sizeof(*board
->c
);
79 int ssize
= board_size2(board
) * sizeof(*board
->spathash
);
84 int p3size
= board_size2(board
) * sizeof(*board
->pat3
);
89 int tsize
= board_size2(board
) * sizeof(*board
->t
);
90 int tqsize
= board_size2(board
) * sizeof(*board
->t
);
95 int cdsize
= board_size2(board
) * sizeof(*board
->coord
);
97 size_t size
= bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
+ ssize
+ p3size
+ tsize
+ tqsize
+ cdsize
;
98 void *x
= malloc2(size
);
100 /* board->b must come first */
101 board
->b
= x
; x
+= bsize
;
102 board
->g
= x
; x
+= gsize
;
103 board
->f
= x
; x
+= fsize
;
104 board
->p
= x
; x
+= psize
;
105 board
->n
= x
; x
+= nsize
;
106 board
->h
= x
; x
+= hsize
;
107 board
->gi
= x
; x
+= gisize
;
109 board
->c
= x
; x
+= csize
;
111 #ifdef BOARD_SPATHASH
112 board
->spathash
= x
; x
+= ssize
;
115 board
->pat3
= x
; x
+= p3size
;
118 board
->t
= x
; x
+= tsize
;
119 board
->tq
= x
; x
+= tqsize
;
121 board
->coord
= x
; x
+= cdsize
;
127 board_cmp(struct board
*b1
, struct board
*b2
)
129 void **p1
= (void**)b1
, **p2
= (void**)b2
;
130 for (unsigned int i
= 0; i
< sizeof(struct board
) / sizeof(void*); i
++)
131 if (p1
[i
] != p2
[i
] &&
132 &p1
[i
] != (void**)&b1
->b
&&
133 &p1
[i
] != (void**)&b1
->g
&&
134 &p1
[i
] != (void**)&b1
->f
&&
135 &p1
[i
] != (void**)&b1
->n
&&
136 &p1
[i
] != (void**)&b1
->p
&&
137 &p1
[i
] != (void**)&b1
->h
&&
138 &p1
[i
] != (void**)&b1
->gi
&&
140 &p1
[i
] != (void**)&b1
->c
&&
142 #ifdef BOARD_SPATHASH
143 &p1
[i
] != (void**)&b1
->spathash
&&
146 &p1
[i
] != (void**)&b1
->pat3
&&
149 &p1
[i
] != (void**)&b1
->t
&&
150 &p1
[i
] != (void**)&b1
->tq
&&
152 &p1
[i
] != (void**)&b1
->coord
)
155 /* Find alloc size */
158 size_t size
= board_alloc(&tmp
);
159 board_done_noalloc(&tmp
);
161 return memcmp(b1
->b
, b2
->b
, size
);
165 board_quick_cmp(struct board
*b1
, struct board
*b2
)
167 if (b1
->size
!= b2
->size
||
168 b1
->size2
!= b2
->size2
||
169 b1
->bits2
!= b2
->bits2
||
170 b1
->captures
[S_BLACK
] != b2
->captures
[S_BLACK
] ||
171 b1
->captures
[S_WHITE
] != b2
->captures
[S_WHITE
] ||
172 b1
->moves
!= b2
->moves
) {
173 fprintf(stderr
, "differs in main vars\n");
176 if (move_cmp(&b1
->last_move
, &b2
->last_move
) ||
177 move_cmp(&b1
->last_move2
, &b2
->last_move2
)) {
178 fprintf(stderr
, "differs in last_move\n");
181 if (move_cmp(&b1
->ko
, &b2
->ko
) ||
182 move_cmp(&b1
->last_ko
, &b2
->last_ko
) ||
183 b1
->last_ko_age
!= b2
->last_ko_age
) {
184 fprintf(stderr
, "differs in ko\n");
188 int bsize
= board_size2(b1
) * sizeof(*b1
->b
);
189 int gsize
= board_size2(b1
) * sizeof(*b1
->g
);
190 //int fsize = board_size2(b1) * sizeof(*b1->f);
191 int nsize
= board_size2(b1
) * sizeof(*b1
->n
);
192 int psize
= board_size2(b1
) * sizeof(*b1
->p
);
193 //int hsize = board_size2(b1) * 2 * sizeof(*b1->h);
194 int gisize
= board_size2(b1
) * sizeof(*b1
->gi
);
195 //int csize = board_size2(board) * sizeof(*b1->c);
196 //int ssize = board_size2(board) * sizeof(*b1->spathash);
197 //int p3size = board_size2(board) * sizeof(*b1->pat3);
198 //int tsize = board_size2(board) * sizeof(*b1->t);
199 //int tqsize = board_size2(board) * sizeof(*b1->t);
201 //int cdsize = board_size2(b1) * sizeof(*b1->coord);
203 if (memcmp(b1
->b
, b2
->b
, bsize
)) {
204 fprintf(stderr
, "differs in b\n"); return 1; }
205 if (memcmp(b1
->g
, b2
->g
, gsize
)) {
206 fprintf(stderr
, "differs in g\n"); return 1; }
207 if (memcmp(b1
->n
, b2
->n
, nsize
)) {
208 fprintf(stderr
, "differs in n\n"); return 1; }
209 if (memcmp(b1
->p
, b2
->p
, psize
)) {
210 fprintf(stderr
, "differs in p\n"); return 1; }
211 if (memcmp(b1
->gi
, b2
->gi
, gisize
)) {
212 fprintf(stderr
, "differs in gi\n"); return 1; }
219 board_copy(struct board
*b2
, struct board
*b1
)
221 memcpy(b2
, b1
, sizeof(struct board
));
223 size_t size
= board_alloc(b2
);
224 memcpy(b2
->b
, b1
->b
, size
);
226 // XXX: Special semantics.
233 board_done_noalloc(struct board
*board
)
235 if (board
->b
) free(board
->b
);
236 if (board
->fbook
) fbook_done(board
->fbook
);
240 board_done(struct board
*board
)
242 board_done_noalloc(board
);
247 board_resize(struct board
*board
, int size
)
250 assert(board_size(board
) == size
+ 2);
252 assert(size
<= BOARD_MAX_SIZE
);
253 board
->size
= size
+ 2 /* S_OFFBOARD margin */;
254 board
->size2
= board_size(board
) * board_size(board
);
257 while ((1 << board
->bits2
) < board
->size2
) board
->bits2
++;
262 size_t asize
= board_alloc(board
);
263 memset(board
->b
, 0, asize
);
267 board_init_data(struct board
*board
)
269 int size
= board_size(board
);
272 board_resize(board
, size
- 2 /* S_OFFBOARD margin */);
274 /* Setup neighborhood iterators */
275 board
->nei8
[0] = -size
- 1; // (-1,-1)
278 board
->nei8
[3] = size
- 2; // (-1,0)
280 board
->nei8
[5] = size
- 2; // (-1,1)
283 board
->dnei
[0] = -size
- 1;
285 board
->dnei
[2] = size
*2 - 2;
288 /* Setup initial symmetry */
290 board
->symmetry
.d
= 1;
291 board
->symmetry
.x1
= board
->symmetry
.y1
= board_size(board
) / 2;
292 board
->symmetry
.x2
= board
->symmetry
.y2
= board_size(board
) - 1;
293 board
->symmetry
.type
= SYM_FULL
;
295 /* TODO: We do not handle board symmetry on boards
296 * with no tengen yet. */
297 board
->symmetry
.d
= 0;
298 board
->symmetry
.x1
= board
->symmetry
.y1
= 1;
299 board
->symmetry
.x2
= board
->symmetry
.y2
= board_size(board
) - 1;
300 board
->symmetry
.type
= SYM_NONE
;
303 /* Set up coordinate cache */
304 foreach_point(board
) {
305 board
->coord
[c
][0] = c
% board_size(board
);
306 board
->coord
[c
][1] = c
/ board_size(board
);
309 /* Draw the offboard margin */
310 int top_row
= board_size2(board
) - board_size(board
);
312 for (i
= 0; i
< board_size(board
); i
++)
313 board
->b
[i
] = board
->b
[top_row
+ i
] = S_OFFBOARD
;
314 for (i
= 0; i
<= top_row
; i
+= board_size(board
))
315 board
->b
[i
] = board
->b
[board_size(board
) - 1 + i
] = S_OFFBOARD
;
317 foreach_point(board
) {
319 if (board_at(board
, coord
) == S_OFFBOARD
)
321 foreach_neighbor(board
, c
, {
322 inc_neighbor_count_at(board
, coord
, board_at(board
, c
));
326 /* All positions are free! Except the margin. */
327 for (i
= board_size(board
); i
< (board_size(board
) - 1) * board_size(board
); i
++)
328 if (i
% board_size(board
) != 0 && i
% board_size(board
) != board_size(board
) - 1)
329 board
->f
[board
->flen
++] = i
;
331 /* Initialize zobrist hashtable. */
332 /* We will need these to be stable across Pachi runs for
333 * certain kinds of pattern matching, thus we do not use
334 * fast_random() for this. */
335 hash_t hseed
= 0x3121110101112131;
336 foreach_point(board
) {
337 board
->h
[c
* 2] = (hseed
*= 16807);
338 if (!board
->h
[c
* 2])
340 /* And once again for white */
341 board
->h
[c
* 2 + 1] = (hseed
*= 16807);
342 if (!board
->h
[c
* 2 + 1])
343 board
->h
[c
* 2 + 1] = 1;
346 #ifdef BOARD_SPATHASH
347 /* Initialize spatial hashes. */
348 foreach_point(board
) {
349 for (int d
= 1; d
<= BOARD_SPATHASH_MAXD
; d
++) {
350 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
351 ptcoords_at(x
, y
, c
, board
, j
);
352 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][0] ^=
353 pthashes
[0][j
][board_at(board
, c
)];
354 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][1] ^=
355 pthashes
[0][j
][stone_other(board_at(board
, c
))];
361 /* Initialize 3x3 pattern codes. */
362 foreach_point(board
) {
363 if (board_at(board
, c
) == S_NONE
)
364 board
->pat3
[c
] = pattern3_hash(board
, c
);
368 /* Initialize traits. */
369 foreach_point(board
) {
370 trait_at(board
, c
, S_BLACK
).cap
= 0;
371 trait_at(board
, c
, S_WHITE
).cap
= 0;
372 trait_at(board
, c
, S_BLACK
).cap1
= 0;
373 trait_at(board
, c
, S_WHITE
).cap1
= 0;
374 #ifdef BOARD_TRAIT_SAFE
375 trait_at(board
, c
, S_BLACK
).safe
= true;
376 trait_at(board
, c
, S_WHITE
).safe
= true;
383 board_clear(struct board
*board
)
385 int size
= board_size(board
);
386 floating_t komi
= board
->komi
;
387 char *fbookfile
= board
->fbookfile
;
388 enum go_ruleset rules
= board
->rules
;
390 board_done_noalloc(board
);
392 static struct board bcache
[BOARD_MAX_SIZE
+ 2];
393 assert(size
> 0 && size
<= BOARD_MAX_SIZE
+ 2);
394 if (bcache
[size
- 1].size
== size
) {
395 board_copy(board
, &bcache
[size
- 1]);
397 board_init_data(board
);
398 board_copy(&bcache
[size
- 1], board
);
402 board
->fbookfile
= fbookfile
;
403 board
->rules
= rules
;
405 if (board
->fbookfile
) {
406 board
->fbook
= fbook_init(board
->fbookfile
, board
);
411 board_print_top(struct board
*board
, char *s
, char *end
, int c
)
413 for (int i
= 0; i
< c
; i
++) {
414 char asdf
[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
415 s
+= snprintf(s
, end
- s
, " ");
416 for (int x
= 1; x
< board_size(board
) - 1; x
++)
417 s
+= snprintf(s
, end
- s
, "%c ", asdf
[x
- 1]);
418 s
+= snprintf(s
, end
-s
, " ");
420 s
+= snprintf(s
, end
- s
, "\n");
421 for (int i
= 0; i
< c
; i
++) {
422 s
+= snprintf(s
, end
- s
, " +-");
423 for (int x
= 1; x
< board_size(board
) - 1; x
++)
424 s
+= snprintf(s
, end
- s
, "--");
425 s
+= snprintf(s
, end
- s
, "+");
427 s
+= snprintf(s
, end
- s
, "\n");
432 board_print_bottom(struct board
*board
, char *s
, char *end
, int c
)
434 for (int i
= 0; i
< c
; i
++) {
435 s
+= snprintf(s
, end
- s
, " +-");
436 for (int x
= 1; x
< board_size(board
) - 1; x
++)
437 s
+= snprintf(s
, end
- s
, "--");
438 s
+= snprintf(s
, end
- s
, "+");
440 s
+= snprintf(s
, end
- s
, "\n");
445 board_print_row(struct board
*board
, int y
, char *s
, char *end
, board_cprint cprint
, void *data
)
447 s
+= snprintf(s
, end
- s
, " %2d | ", y
);
448 for (int x
= 1; x
< board_size(board
) - 1; x
++) {
449 if (coord_x(board
->last_move
.coord
, board
) == x
&& coord_y(board
->last_move
.coord
, board
) == y
)
450 s
+= snprintf(s
, end
- s
, "%c)", stone2char(board_atxy(board
, x
, y
)));
452 s
+= snprintf(s
, end
- s
, "%c ", stone2char(board_atxy(board
, x
, y
)));
454 s
+= snprintf(s
, end
- s
, "|");
456 s
+= snprintf(s
, end
- s
, " %2d | ", y
);
457 for (int x
= 1; x
< board_size(board
) - 1; x
++) {
458 s
= cprint(board
, coord_xy(board
, x
, y
), s
, end
, data
);
460 s
+= snprintf(s
, end
- s
, "|");
462 s
+= snprintf(s
, end
- s
, "\n");
467 board_print_custom(struct board
*board
, FILE *f
, board_cprint cprint
, void *data
)
471 char *end
= buf
+ sizeof(buf
);
472 s
+= snprintf(s
, end
- s
, "Move: % 3d Komi: %2.1f Handicap: %d Captures B: %d W: %d\n",
473 board
->moves
, board
->komi
, board
->handicap
,
474 board
->captures
[S_BLACK
], board
->captures
[S_WHITE
]);
475 s
= board_print_top(board
, s
, end
, 1 + !!cprint
);
476 for (int y
= board_size(board
) - 2; y
>= 1; y
--)
477 s
= board_print_row(board
, y
, s
, end
, cprint
, data
);
478 board_print_bottom(board
, s
, end
, 1 + !!cprint
);
479 fprintf(f
, "%s\n", buf
);
483 cprint_group(struct board
*board
, coord_t c
, char *s
, char *end
, void *data
)
485 s
+= snprintf(s
, end
- s
, "%d ", group_base(group_at(board
, c
)));
490 board_print(struct board
*board
, FILE *f
)
492 board_print_custom(board
, f
, DEBUGL(6) ? cprint_group
: NULL
, NULL
);
498 #if BOARD_TRAIT_SAFE == 1
500 board_trait_safe(struct board
*board
, coord_t coord
, enum stone color
)
502 return board_safe_to_play(board
, coord
, color
);
504 #elif BOARD_TRAIT_SAFE == 2
506 board_trait_safe(struct board
*board
, coord_t coord
, enum stone color
)
508 return !is_bad_selfatari(board
, color
, coord
);
513 board_trait_recompute(struct board
*board
, coord_t coord
)
515 int sfb
= -1, sfw
= -1;
516 #ifdef BOARD_TRAIT_SAFE
517 sfb
= trait_at(board
, coord
, S_BLACK
).safe
= board_trait_safe(board
, coord
, S_BLACK
);
518 sfw
= trait_at(board
, coord
, S_WHITE
).safe
= board_trait_safe(board
, coord
, S_WHITE
);
521 fprintf(stderr
, "traits[%s:%s lib=%d] (black cap=%d cap1=%d safe=%d) (white cap=%d cap1=%d safe=%d)\n",
522 coord2sstr(coord
, board
), stone2str(board_at(board
, coord
)), immediate_liberty_count(board
, coord
),
523 trait_at(board
, coord
, S_BLACK
).cap
, trait_at(board
, coord
, S_BLACK
).cap1
, sfb
,
524 trait_at(board
, coord
, S_WHITE
).cap
, trait_at(board
, coord
, S_WHITE
).cap1
, sfw
);
529 /* Recompute traits for dirty points that we have previously touched
530 * somehow (libs of their neighbors changed or so). */
532 board_traits_recompute(struct board
*board
)
535 for (int i
= 0; i
< board
->tqlen
; i
++) {
536 coord_t coord
= board
->tq
[i
];
537 trait_at(board
, coord
, S_BLACK
).dirty
= false;
538 if (board_at(board
, coord
) != S_NONE
)
540 board_trait_recompute(board
, coord
);
546 /* Queue traits of given point for recomputing. */
548 board_trait_queue(struct board
*board
, coord_t coord
)
551 if (trait_at(board
, coord
, S_BLACK
).dirty
)
553 board
->tq
[board
->tqlen
++] = coord
;
554 trait_at(board
, coord
, S_BLACK
).dirty
= true;
559 /* Update board hash with given coordinate. */
560 static void profiling_noinline
561 board_hash_update(struct board
*board
, coord_t coord
, enum stone color
)
563 board
->hash
^= hash_at(board
, coord
, color
);
564 board
->qhash
[coord_quadrant(coord
, board
)] ^= hash_at(board
, coord
, color
);
566 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
);
568 #ifdef BOARD_SPATHASH
569 /* Gridcular metric is reflective, so we update all hashes
570 * of appropriate ditance in OUR circle. */
571 for (int d
= 1; d
<= BOARD_SPATHASH_MAXD
; d
++) {
572 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
573 ptcoords_at(x
, y
, coord
, board
, j
);
574 /* We either changed from S_NONE to color
575 * or vice versa; doesn't matter. */
576 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][0] ^=
577 pthashes
[0][j
][color
] ^ pthashes
[0][j
][S_NONE
];
578 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][1] ^=
579 pthashes
[0][j
][stone_other(color
)] ^ pthashes
[0][j
][S_NONE
];
584 #if defined(BOARD_PAT3)
585 /* @color is not what we need in case of capture. */
586 static const int ataribits
[8] = { -1, 0, -1, 1, 2, -1, 3, -1 };
587 enum stone new_color
= board_at(board
, coord
);
588 bool in_atari
= false;
589 if (new_color
== S_NONE
) {
590 board
->pat3
[coord
] = pattern3_hash(board
, coord
);
592 in_atari
= (board_group_info(board
, group_at(board
, coord
)).libs
== 1);
594 foreach_8neighbor(board
, coord
) {
595 /* Internally, the loop uses fn__i=[0..7]. We can use
596 * it directly to address bits within the bitmap of the
597 * neighbors since the bitmap order is reverse to the
599 if (board_at(board
, c
) != S_NONE
)
601 board
->pat3
[c
] &= ~(3 << (fn__i
*2));
602 board
->pat3
[c
] |= new_color
<< (fn__i
*2);
603 if (ataribits
[fn__i
] >= 0) {
604 board
->pat3
[c
] &= ~(1 << (16 + ataribits
[fn__i
]));
605 board
->pat3
[c
] |= in_atari
<< (16 + ataribits
[fn__i
]);
607 #if defined(BOARD_TRAITS)
608 board_trait_queue(board
, c
);
610 } foreach_8neighbor_end
;
614 /* Commit current board hash to history. */
615 static void profiling_noinline
616 board_hash_commit(struct board
*board
)
619 fprintf(stderr
, "board_hash_commit %"PRIhash
"\n", board
->hash
);
620 if (likely(board
->history_hash
[board
->hash
& history_hash_mask
]) == 0) {
621 board
->history_hash
[board
->hash
& history_hash_mask
] = board
->hash
;
623 hash_t i
= board
->hash
;
624 while (board
->history_hash
[i
& history_hash_mask
]) {
625 if (board
->history_hash
[i
& history_hash_mask
] == board
->hash
) {
627 fprintf(stderr
, "SUPERKO VIOLATION noted at %d,%d\n",
628 coord_x(board
->last_move
.coord
, board
), coord_y(board
->last_move
.coord
, board
));
629 board
->superko_violation
= true;
632 i
= history_hash_next(i
);
634 board
->history_hash
[i
& history_hash_mask
] = board
->hash
;
640 board_symmetry_update(struct board
*b
, struct board_symmetry
*symmetry
, coord_t c
)
642 if (likely(symmetry
->type
== SYM_NONE
)) {
643 /* Fully degenerated already. We do not support detection
644 * of restoring of symmetry, assuming that this is too rare
645 * a case to handle. */
649 int x
= coord_x(c
, b
), y
= coord_y(c
, b
), t
= board_size(b
) / 2;
650 int dx
= board_size(b
) - 1 - x
; /* for SYM_DOWN */
652 fprintf(stderr
, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
653 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
654 symmetry
->d
, symmetry
->type
, x
, y
);
657 switch (symmetry
->type
) {
659 if (x
== t
&& y
== t
) {
660 /* Tengen keeps full symmetry. */
663 /* New symmetry now? */
665 symmetry
->type
= SYM_DIAG_UP
;
666 symmetry
->x1
= symmetry
->y1
= 1;
667 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
669 } else if (dx
== y
) {
670 symmetry
->type
= SYM_DIAG_DOWN
;
671 symmetry
->x1
= symmetry
->y1
= 1;
672 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
675 symmetry
->type
= SYM_HORIZ
;
677 symmetry
->y2
= board_size(b
) - 1;
680 symmetry
->type
= SYM_VERT
;
682 symmetry
->x2
= board_size(b
) - 1;
686 symmetry
->type
= SYM_NONE
;
687 symmetry
->x1
= symmetry
->y1
= 1;
688 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
714 fprintf(stderr
, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
715 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
716 symmetry
->d
, symmetry
->type
);
723 board_handicap_stone(struct board
*board
, int x
, int y
, FILE *f
)
726 m
.color
= S_BLACK
; m
.coord
= coord_xy(board
, x
, y
);
728 board_play(board
, &m
);
729 /* Simulate white passing; otherwise, UCT search can get confused since
730 * tree depth parity won't match the color to move. */
733 char *str
= coord2str(m
.coord
, board
);
735 fprintf(stderr
, "choosing handicap %s (%d,%d)\n", str
, x
, y
);
736 if (f
) fprintf(f
, "%s ", str
);
741 board_handicap(struct board
*board
, int stones
, FILE *f
)
743 int margin
= 3 + (board_size(board
) >= 13);
745 int mid
= board_size(board
) / 2;
746 int max
= board_size(board
) - 1 - margin
;
747 const int places
[][2] = {
748 { min
, min
}, { max
, max
}, { min
, max
}, { max
, min
},
749 { min
, mid
}, { max
, mid
},
750 { mid
, min
}, { mid
, max
},
754 board
->handicap
= stones
;
756 if (stones
== 5 || stones
== 7) {
757 board_handicap_stone(board
, mid
, mid
, f
);
762 for (i
= 0; i
< stones
; i
++)
763 board_handicap_stone(board
, places
[i
][0], places
[i
][1], f
);
767 static void __attribute__((noinline
))
768 check_libs_consistency(struct board
*board
, group_t g
)
772 struct group
*gi
= &board_group_info(board
, g
);
773 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
774 if (gi
->lib
[i
] && board_at(board
, gi
->lib
[i
]) != S_NONE
) {
775 fprintf(stderr
, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi
->lib
[i
], board
), g
, coord2sstr(group_base(g
), board
));
782 check_pat3_consistency(struct board
*board
, coord_t coord
)
785 foreach_8neighbor(board
, coord
) {
786 if (board_at(board
, c
) == S_NONE
&& pattern3_hash(board
, c
) != board
->pat3
[c
]) {
787 board_print(board
, stderr
);
788 fprintf(stderr
, "%s(%d)->%s(%d) computed %x != stored %x (%d)\n", coord2sstr(coord
, board
), coord
, coord2sstr(c
, board
), c
, pattern3_hash(board
, c
), board
->pat3
[c
], fn__i
);
791 } foreach_8neighbor_end
;
796 board_capturable_add(struct board
*board
, group_t group
, coord_t lib
, bool onestone
)
798 //fprintf(stderr, "group %s cap %s\n", coord2sstr(group, board), coord2sstr(lib, boarD));
800 /* Increase capturable count trait of my last lib. */
801 enum stone capturing_color
= stone_other(board_at(board
, group
));
802 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
803 foreach_neighbor(board
, lib
, {
804 if (DEBUGL(8) && group_at(board
, c
) == group
)
805 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
);
806 trait_at(board
, lib
, capturing_color
).cap
+= (group_at(board
, c
) == group
);
807 trait_at(board
, lib
, capturing_color
).cap1
+= (group_at(board
, c
) == group
&& onestone
);
809 board_trait_queue(board
, lib
);
814 foreach_neighbor(board
, lib
, {
815 board
->pat3
[lib
] |= (group_at(board
, c
) == group
) << (16 + 3 - fn__i
);
821 /* Update the list of capturable groups. */
823 assert(board
->clen
< board_size2(board
));
824 board
->c
[board
->clen
++] = group
;
828 board_capturable_rm(struct board
*board
, group_t group
, coord_t lib
, bool onestone
)
830 //fprintf(stderr, "group %s nocap %s\n", coord2sstr(group, board), coord2sstr(lib, board));
832 /* Decrease capturable count trait of my previously-last lib. */
833 enum stone capturing_color
= stone_other(board_at(board
, group
));
834 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
835 foreach_neighbor(board
, lib
, {
836 if (DEBUGL(8) && group_at(board
, c
) == group
)
837 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
);
838 trait_at(board
, lib
, capturing_color
).cap
-= (group_at(board
, c
) == group
);
839 trait_at(board
, lib
, capturing_color
).cap1
-= (group_at(board
, c
) == group
&& onestone
);
841 board_trait_queue(board
, lib
);
846 foreach_neighbor(board
, lib
, {
847 board
->pat3
[lib
] &= ~((group_at(board
, c
) == group
) << (16 + 3 - fn__i
));
853 /* Update the list of capturable groups. */
854 for (int i
= 0; i
< board
->clen
; i
++) {
855 if (unlikely(board
->c
[i
] == group
)) {
856 board
->c
[i
] = board
->c
[--board
->clen
];
860 fprintf(stderr
, "rm of bad group %d\n", group_base(group
));
866 board_atariable_add(struct board
*board
, group_t group
, coord_t lib1
, coord_t lib2
)
869 board_trait_queue(board
, lib1
);
870 board_trait_queue(board
, lib2
);
874 board_atariable_rm(struct board
*board
, group_t group
, coord_t lib1
, coord_t lib2
)
877 board_trait_queue(board
, lib1
);
878 board_trait_queue(board
, lib2
);
883 board_group_addlib(struct board
*board
, group_t group
, coord_t coord
, struct board_undo
*u
)
886 fprintf(stderr
, "Group %d[%s] %d: Adding liberty %s\n",
887 group_base(group
), coord2sstr(group_base(group
), board
),
888 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
891 if (!u
) check_libs_consistency(board
, group
);
893 struct group
*gi
= &board_group_info(board
, group
);
894 bool onestone
= group_is_onestone(board
, group
);
895 if (gi
->libs
< GROUP_KEEP_LIBS
) {
896 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
898 /* Seems extra branch just slows it down */
902 if (unlikely(gi
->lib
[i
] == coord
))
907 board_capturable_add(board
, group
, coord
, onestone
);
908 } else if (gi
->libs
== 1) {
909 board_capturable_rm(board
, group
, gi
->lib
[0], onestone
);
910 board_atariable_add(board
, group
, gi
->lib
[0], coord
);
911 } else if (gi
->libs
== 2) {
912 board_atariable_rm(board
, group
, gi
->lib
[0], gi
->lib
[1]);
915 gi
->lib
[gi
->libs
++] = coord
;
918 if (!u
) check_libs_consistency(board
, group
);
922 board_group_find_extra_libs(struct board
*board
, group_t group
, struct group
*gi
, coord_t avoid
)
924 /* Add extra liberty from the board to our liberty list. */
925 unsigned char watermark
[board_size2(board
) / 8];
926 memset(watermark
, 0, sizeof(watermark
));
927 #define watermark_get(c) (watermark[c >> 3] & (1 << (c & 7)))
928 #define watermark_set(c) watermark[c >> 3] |= (1 << (c & 7))
930 for (int i
= 0; i
< GROUP_KEEP_LIBS
- 1; i
++)
931 watermark_set(gi
->lib
[i
]);
932 watermark_set(avoid
);
934 foreach_in_group(board
, group
) {
936 foreach_neighbor(board
, coord2
, {
937 if (board_at(board
, c
) + watermark_get(c
) != S_NONE
)
940 gi
->lib
[gi
->libs
++] = c
;
941 if (unlikely(gi
->libs
>= GROUP_KEEP_LIBS
))
944 } foreach_in_group_end
;
950 board_group_rmlib(struct board
*board
, group_t group
, coord_t coord
, struct board_undo
*u
)
953 fprintf(stderr
, "Group %d[%s] %d: Removing liberty %s\n",
954 group_base(group
), coord2sstr(group_base(group
), board
),
955 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
958 struct group
*gi
= &board_group_info(board
, group
);
959 bool onestone
= group_is_onestone(board
, group
);
960 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
962 /* Seems extra branch just slows it down */
966 if (likely(gi
->lib
[i
] != coord
))
969 coord_t lib
= gi
->lib
[i
] = gi
->lib
[--gi
->libs
];
970 gi
->lib
[gi
->libs
] = 0;
972 if (!u
) check_libs_consistency(board
, group
);
974 /* Postpone refilling lib[] until we need to. */
975 assert(GROUP_REFILL_LIBS
> 1);
976 if (gi
->libs
> GROUP_REFILL_LIBS
)
978 if (gi
->libs
== GROUP_REFILL_LIBS
)
979 board_group_find_extra_libs(board
, group
, gi
, coord
);
983 board_atariable_add(board
, group
, gi
->lib
[0], gi
->lib
[1]);
984 } else if (gi
->libs
== 1) {
985 board_capturable_add(board
, group
, gi
->lib
[0], onestone
);
986 board_atariable_rm(board
, group
, gi
->lib
[0], lib
);
987 } else if (gi
->libs
== 0)
988 board_capturable_rm(board
, group
, lib
, onestone
);
992 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
993 * can call this multiple times per coord. */
994 if (!u
) check_libs_consistency(board
, group
);
999 /* This is a low-level routine that doesn't maintain consistency
1000 * of all the board data structures. */
1002 board_remove_stone(struct board
*board
, group_t group
, coord_t c
, struct board_undo
*u
)
1004 enum stone color
= board_at(board
, c
);
1005 board_at(board
, c
) = S_NONE
;
1006 group_at(board
, c
) = 0;
1008 board_hash_update(board
, c
, color
);
1010 /* We mark as cannot-capture now. If this is a ko/snapback,
1011 * we will get incremented later in board_group_addlib(). */
1012 trait_at(board
, c
, S_BLACK
).cap
= trait_at(board
, c
, S_BLACK
).cap1
= 0;
1013 trait_at(board
, c
, S_WHITE
).cap
= trait_at(board
, c
, S_WHITE
).cap1
= 0;
1014 board_trait_queue(board
, c
);
1018 /* Increase liberties of surrounding groups */
1020 foreach_neighbor(board
, coord
, {
1021 dec_neighbor_count_at(board
, c
, color
);
1022 if (!u
) board_trait_queue(board
, c
);
1023 group_t g
= group_at(board
, c
);
1024 if (g
&& g
!= group
)
1025 board_group_addlib(board
, g
, coord
, u
);
1030 /* board_hash_update() might have seen the freed up point as able
1031 * to capture another group in atari that only after the loop
1032 * above gained enough liberties. Reset pat3 again. */
1033 board
->pat3
[c
] = pattern3_hash(board
, c
);
1037 fprintf(stderr
, "pushing free move [%d]: %d,%d\n", board
->flen
, coord_x(c
, board
), coord_y(c
, board
));
1038 board
->f
[board
->flen
++] = c
;
1041 static int profiling_noinline
1042 board_group_capture(struct board
*board
, group_t group
, struct board_undo
*u
)
1046 foreach_in_group(board
, group
) {
1047 board
->captures
[stone_other(board_at(board
, c
))]++;
1048 board_remove_stone(board
, group
, c
, u
);
1050 } foreach_in_group_end
;
1052 struct group
*gi
= &board_group_info(board
, group
);
1053 assert(gi
->libs
== 0);
1054 memset(gi
, 0, sizeof(*gi
));
1060 static void profiling_noinline
1061 add_to_group(struct board
*board
, group_t group
, coord_t prevstone
, coord_t coord
, struct board_undo
*u
)
1064 struct group
*gi
= &board_group_info(board
, group
);
1065 bool onestone
= group_is_onestone(board
, group
);
1067 if (!u
&& gi
->libs
== 1) {
1068 /* Our group is temporarily in atari; make sure the capturable
1069 * counts also correspond to the newly added stone before we
1070 * start adding liberties again so bump-dump ops match. */
1071 enum stone capturing_color
= stone_other(board_at(board
, group
));
1072 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
1074 coord_t lib
= board_group_info(board
, group
).lib
[0];
1075 if (coord_is_adjecent(lib
, coord
, board
)) {
1077 fprintf(stderr
, "add_to_group %s: %s[%d] bump\n", coord2sstr(group
, board
), coord2sstr(lib
, board
), trait_at(board
, lib
, capturing_color
).cap
);
1078 trait_at(board
, lib
, capturing_color
).cap
++;
1079 /* This is never a 1-stone group, obviously. */
1080 board_trait_queue(board
, lib
);
1084 /* We are not 1-stone group anymore, update the cap1
1085 * counter specifically. */
1086 foreach_neighbor(board
, group
, {
1087 if (board_at(board
, c
) != S_NONE
) continue;
1088 trait_at(board
, c
, capturing_color
).cap1
--;
1089 board_trait_queue(board
, c
);
1095 group_at(board
, coord
) = group
;
1096 groupnext_at(board
, coord
) = groupnext_at(board
, prevstone
);
1097 groupnext_at(board
, prevstone
) = coord
;
1099 foreach_neighbor(board
, coord
, {
1100 if (board_at(board
, c
) == S_NONE
)
1101 board_group_addlib(board
, group
, c
, u
);
1105 fprintf(stderr
, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
1106 coord_x(prevstone
, board
), coord_y(prevstone
, board
),
1107 coord_x(coord
, board
), coord_y(coord
, board
),
1108 groupnext_at(board
, coord
) % board_size(board
), groupnext_at(board
, coord
) / board_size(board
),
1112 static void profiling_noinline
1113 merge_groups(struct board
*board
, group_t group_to
, group_t group_from
, struct board_undo
*u
)
1116 fprintf(stderr
, "board_play_raw: merging groups %d -> %d\n",
1117 group_base(group_from
), group_base(group_to
));
1118 struct group
*gi_from
= &board_group_info(board
, group_from
);
1119 struct group
*gi_to
= &board_group_info(board
, group_to
);
1120 bool onestone_from
= group_is_onestone(board
, group_from
);
1121 bool onestone_to
= group_is_onestone(board
, group_to
);
1124 /* We do this early before the group info is rewritten. */
1125 if (gi_from
->libs
== 2)
1126 board_atariable_rm(board
, group_from
, gi_from
->lib
[0], gi_from
->lib
[1]);
1127 else if (gi_from
->libs
== 1)
1128 board_capturable_rm(board
, group_from
, gi_from
->lib
[0], onestone_from
);
1132 fprintf(stderr
,"---- (froml %d, tol %d)\n", gi_from
->libs
, gi_to
->libs
);
1134 if (gi_to
->libs
< GROUP_KEEP_LIBS
) {
1135 for (int i
= 0; i
< gi_from
->libs
; i
++) {
1136 for (int j
= 0; j
< gi_to
->libs
; j
++)
1137 if (gi_to
->lib
[j
] == gi_from
->lib
[i
])
1140 if (gi_to
->libs
== 0) {
1141 board_capturable_add(board
, group_to
, gi_from
->lib
[i
], onestone_to
);
1142 } else if (gi_to
->libs
== 1) {
1143 board_capturable_rm(board
, group_to
, gi_to
->lib
[0], onestone_to
);
1144 board_atariable_add(board
, group_to
, gi_to
->lib
[0], gi_from
->lib
[i
]);
1145 } else if (gi_to
->libs
== 2) {
1146 board_atariable_rm(board
, group_to
, gi_to
->lib
[0], gi_to
->lib
[1]);
1149 gi_to
->lib
[gi_to
->libs
++] = gi_from
->lib
[i
];
1150 if (gi_to
->libs
>= GROUP_KEEP_LIBS
)
1156 if (!u
&& gi_to
->libs
== 1) {
1157 coord_t lib
= board_group_info(board
, group_to
).lib
[0];
1159 enum stone capturing_color
= stone_other(board_at(board
, group_to
));
1160 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
1162 /* Our group is currently in atari; make sure we properly
1163 * count in even the neighbors from the other group in the
1164 * capturable counter. */
1165 foreach_neighbor(board
, lib
, {
1166 if (DEBUGL(8) && group_at(board
, c
) == group_from
)
1167 fprintf(stderr
, "%s[%d] cap bump\n", coord2sstr(lib
, board
), trait_at(board
, lib
, capturing_color
).cap
);
1168 trait_at(board
, lib
, capturing_color
).cap
+= (group_at(board
, c
) == group_from
);
1169 /* This is never a 1-stone group, obviously. */
1171 board_trait_queue(board
, lib
);
1174 /* We are not 1-stone group anymore, update the cap1
1175 * counter specifically. */
1176 foreach_neighbor(board
, group_to
, {
1177 if (board_at(board
, c
) != S_NONE
) continue;
1178 trait_at(board
, c
, capturing_color
).cap1
--;
1179 board_trait_queue(board
, c
);
1184 if (gi_from
->libs
== 1) {
1185 /* We removed group_from from capturable groups,
1186 * therefore switching the atari flag off.
1187 * We need to set it again since group_to is also
1190 foreach_neighbor(board
, lib
, {
1191 board
->pat3
[lib
] |= (group_at(board
, c
) == group_from
) << (16 + 3 - fn__i
);
1198 coord_t last_in_group
;
1199 foreach_in_group(board
, group_from
) {
1201 group_at(board
, c
) = group_to
;
1202 } foreach_in_group_end
;
1204 if (u
) u
->merged
[++u
->nmerged_tmp
].last
= last_in_group
;
1205 groupnext_at(board
, last_in_group
) = groupnext_at(board
, group_base(group_to
));
1206 groupnext_at(board
, group_base(group_to
)) = group_base(group_from
);
1207 memset(gi_from
, 0, sizeof(struct group
));
1210 fprintf(stderr
, "board_play_raw: merged group: %d\n",
1211 group_base(group_to
));
1214 static group_t profiling_noinline
1215 new_group(struct board
*board
, coord_t coord
, struct board_undo
*u
)
1217 group_t group
= coord
;
1218 struct group
*gi
= &board_group_info(board
, group
);
1219 foreach_neighbor(board
, coord
, {
1220 if (board_at(board
, c
) == S_NONE
)
1221 /* board_group_addlib is ridiculously expensive for us */
1222 #if GROUP_KEEP_LIBS < 4
1223 if (gi
->libs
< GROUP_KEEP_LIBS
)
1225 gi
->lib
[gi
->libs
++] = c
;
1228 group_at(board
, coord
) = group
;
1229 groupnext_at(board
, coord
) = 0;
1233 board_atariable_add(board
, group
, gi
->lib
[0], gi
->lib
[1]);
1234 else if (gi
->libs
== 1)
1235 board_capturable_add(board
, group
, gi
->lib
[0], true);
1236 check_libs_consistency(board
, group
);
1240 fprintf(stderr
, "new_group: added %d,%d to group %d\n",
1241 coord_x(coord
, board
), coord_y(coord
, board
),
1248 undo_save_merge(struct board
*b
, struct board_undo
*u
, group_t g
, coord_t c
)
1250 if (g
== u
->merged
[0].group
|| g
== u
->merged
[1].group
||
1251 g
== u
->merged
[2].group
|| g
== u
->merged
[3].group
)
1254 int i
= u
->nmerged
++;
1257 u
->merged
[i
].group
= g
;
1258 u
->merged
[i
].last
= 0; // can remove
1259 u
->merged
[i
].info
= board_group_info(b
, g
);
1263 undo_save_enemy(struct board
*b
, struct board_undo
*u
, group_t g
)
1265 if (g
== u
->enemies
[0].group
|| g
== u
->enemies
[1].group
||
1266 g
== u
->enemies
[2].group
|| g
== u
->enemies
[3].group
)
1269 int i
= u
->nenemies
++;
1270 u
->enemies
[i
].group
= g
;
1271 u
->enemies
[i
].info
= board_group_info(b
, g
);
1274 coord_t
*stones
= u
->enemies
[i
].stones
;
1275 if (board_group_info(b
, g
).libs
<= 1) { // Will be captured
1276 foreach_in_group(b
, g
) {
1278 } foreach_in_group_end
;
1285 undo_save_group_info(struct board
*b
, coord_t coord
, enum stone color
, struct board_undo
*u
)
1287 u
->next_at
= groupnext_at(b
, coord
);
1289 foreach_neighbor(b
, coord
, {
1290 group_t g
= group_at(b
, c
);
1292 if (board_at(b
, c
) == color
)
1293 undo_save_merge(b
, u
, g
, c
);
1294 else if (board_at(b
, c
) == stone_other(color
))
1295 undo_save_enemy(b
, u
, g
);
1300 undo_save_suicide(struct board
*b
, coord_t coord
, enum stone color
, struct board_undo
*u
)
1302 foreach_neighbor(b
, coord
, {
1303 if (board_at(b
, c
) == color
) {
1304 // Handle suicide as a capture ...
1305 undo_save_enemy(b
, u
, group_at(b
, c
));
1312 static inline group_t
1313 play_one_neighbor(struct board
*board
,
1314 coord_t coord
, enum stone color
, enum stone other_color
,
1315 coord_t c
, group_t group
, struct board_undo
*u
)
1317 enum stone ncolor
= board_at(board
, c
);
1318 group_t ngroup
= group_at(board
, c
);
1320 inc_neighbor_count_at(board
, c
, color
);
1321 /* We can be S_NONE, in that case we need to update the safety
1322 * trait since we might be left with only one liberty. */
1323 if (!u
) board_trait_queue(board
, c
);
1328 board_group_rmlib(board
, ngroup
, coord
, u
);
1330 fprintf(stderr
, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
1331 group_base(ngroup
), ncolor
, color
, other_color
);
1333 if (ncolor
== color
&& ngroup
!= group
) {
1336 add_to_group(board
, group
, c
, coord
, u
);
1338 merge_groups(board
, group
, ngroup
, u
);
1340 } else if (ncolor
== other_color
) {
1342 struct group
*gi
= &board_group_info(board
, ngroup
);
1343 fprintf(stderr
, "testing captured group %d[%s]: ", group_base(ngroup
), coord2sstr(group_base(ngroup
), board
));
1344 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
1345 fprintf(stderr
, "%s ", coord2sstr(gi
->lib
[i
], board
));
1346 fprintf(stderr
, "\n");
1348 if (unlikely(board_group_captured(board
, ngroup
)))
1349 board_group_capture(board
, ngroup
, u
);
1354 /* We played on a place with at least one liberty. We will become a member of
1355 * some group for sure. */
1356 static group_t profiling_noinline
1357 board_play_outside(struct board
*board
, struct move
*m
, int f
, struct board_undo
*u
)
1359 coord_t coord
= m
->coord
;
1360 enum stone color
= m
->color
;
1361 enum stone other_color
= stone_other(color
);
1365 undo_save_group_info(board
, coord
, color
, u
);
1367 board
->f
[f
] = board
->f
[--board
->flen
];
1369 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
1371 #if defined(BOARD_TRAITS) && defined(DEBUG)
1372 /* Sanity check that cap matches reality. */
1375 foreach_neighbor(board
, coord
, {
1376 group_t g
= group_at(board
, c
);
1377 a
+= g
&& (board_at(board
, c
) == other_color
&& board_group_info(board
, g
).libs
== 1);
1378 b
+= g
&& (board_at(board
, c
) == other_color
&& board_group_info(board
, g
).libs
== 1) && group_is_onestone(board
, g
);
1380 assert(a
== trait_at(board
, coord
, color
).cap
);
1381 assert(b
== trait_at(board
, coord
, color
).cap1
);
1382 #ifdef BOARD_TRAIT_SAFE
1383 assert(board_trait_safe(board
, coord
, color
) == trait_at(board
, coord
, color
).safe
);
1388 foreach_neighbor(board
, coord
, {
1389 group
= play_one_neighbor(board
, coord
, color
, other_color
, c
, group
, u
);
1392 board_at(board
, coord
) = color
;
1393 if (unlikely(!group
))
1394 group
= new_group(board
, coord
, u
);
1397 board
->last_move4
= board
->last_move3
;
1398 board
->last_move3
= board
->last_move2
;
1400 board
->last_move2
= board
->last_move
;
1401 board
->last_move
= *m
;
1404 board_hash_update(board
, coord
, color
);
1405 board_symmetry_update(board
, &board
->symmetry
, coord
);
1407 struct move ko
= { pass
, S_NONE
};
1410 if (!u
) check_pat3_consistency(board
, coord
);
1415 /* We played in an eye-like shape. Either we capture at least one of the eye
1416 * sides in the process of playing, or return -1. */
1417 static int profiling_noinline
1418 board_play_in_eye(struct board
*board
, struct move
*m
, int f
, struct board_undo
*u
)
1420 coord_t coord
= m
->coord
;
1421 enum stone color
= m
->color
;
1422 /* Check ko: Capture at a position of ko capture one move ago */
1423 if (unlikely(color
== board
->ko
.color
&& coord
== board
->ko
.coord
)) {
1425 fprintf(stderr
, "board_check: ko at %d,%d color %d\n", coord_x(coord
, board
), coord_y(coord
, board
), color
);
1427 } else if (DEBUGL(6)) {
1428 fprintf(stderr
, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
1429 color
, coord_x(coord
, board
), coord_y(coord
, board
),
1430 board
->ko
.color
, coord_x(board
->ko
.coord
, board
), coord_y(board
->ko
.coord
, board
));
1433 struct move ko
= { pass
, S_NONE
};
1435 int captured_groups
= 0;
1437 foreach_neighbor(board
, coord
, {
1438 group_t g
= group_at(board
, c
);
1440 fprintf(stderr
, "board_check: group %d has %d libs\n",
1441 g
, board_group_info(board
, g
).libs
);
1442 captured_groups
+= (board_group_info(board
, g
).libs
== 1);
1445 if (likely(captured_groups
== 0)) {
1448 board_print(board
, stderr
);
1449 fprintf(stderr
, "board_check: one-stone suicide\n");
1457 /* We _will_ for sure capture something. */
1458 assert(trait_at(board
, coord
, color
).cap
> 0);
1459 #ifdef BOARD_TRAIT_SAFE
1460 assert(trait_at(board
, coord
, color
).safe
== board_trait_safe(board
, coord
, color
));
1464 board
->f
[f
] = board
->f
[--board
->flen
];
1466 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
1469 undo_save_group_info(board
, coord
, color
, u
);
1472 coord_t cap_at
= pass
;
1473 foreach_neighbor(board
, coord
, {
1474 inc_neighbor_count_at(board
, c
, color
);
1475 /* Originally, this could not have changed any trait
1476 * since no neighbors were S_NONE, however by now some
1477 * of them might be removed from the board. */
1478 if (!u
) board_trait_queue(board
, c
);
1480 group_t group
= group_at(board
, c
);
1484 board_group_rmlib(board
, group
, coord
, u
);
1486 fprintf(stderr
, "board_play_raw: reducing libs for group %d\n",
1489 if (board_group_captured(board
, group
)) {
1490 ko_caps
+= board_group_capture(board
, group
, u
);
1495 ko
.color
= stone_other(color
);
1496 ko
.coord
= cap_at
; // unique
1497 board
->last_ko
= ko
;
1498 board
->last_ko_age
= board
->moves
;
1500 fprintf(stderr
, "guarding ko at %d,%s\n", ko
.color
, coord2sstr(ko
.coord
, board
));
1503 board_at(board
, coord
) = color
;
1504 group_t group
= new_group(board
, coord
, u
);
1507 board
->last_move4
= board
->last_move3
;
1508 board
->last_move3
= board
->last_move2
;
1510 board
->last_move2
= board
->last_move
;
1511 board
->last_move
= *m
;
1514 board_hash_update(board
, coord
, color
);
1515 board_hash_commit(board
);
1516 board_traits_recompute(board
);
1517 board_symmetry_update(board
, &board
->symmetry
, coord
);
1521 if (!u
) check_pat3_consistency(board
, coord
);
1526 static int __attribute__((flatten
))
1527 board_play_f(struct board
*board
, struct move
*m
, int f
, struct board_undo
*u
)
1530 fprintf(stderr
, "board_play(%s): ---- Playing %d,%d\n", coord2sstr(m
->coord
, board
), coord_x(m
->coord
, board
), coord_y(m
->coord
, board
));
1532 if (likely(!board_is_eyelike(board
, m
->coord
, stone_other(m
->color
)))) {
1533 /* NOT playing in an eye. Thus this move has to succeed. (This
1534 * is thanks to New Zealand rules. Otherwise, multi-stone
1535 * suicide might fail.) */
1536 group_t group
= board_play_outside(board
, m
, f
, u
);
1537 if (unlikely(board_group_captured(board
, group
))) {
1538 if (u
) undo_save_suicide(board
, m
->coord
, m
->color
, u
);
1539 board_group_capture(board
, group
, u
);
1542 board_hash_commit(board
);
1543 board_traits_recompute(board
);
1547 return board_play_in_eye(board
, m
, f
, u
);
1552 undo_init(struct board
*b
, struct move
*m
, struct board_undo
*u
)
1554 // Paranoid uninitialized mem test
1555 // memset(u, 0xff, sizeof(*u));
1557 u
->last_move2
= b
->last_move2
;
1559 u
->last_ko
= b
->last_ko
;
1560 u
->last_ko_age
= b
->last_ko_age
;
1563 u
->nmerged
= u
->nmerged_tmp
= u
->nenemies
= 0;
1564 for (int i
= 0; i
< 4; i
++)
1565 u
->merged
[i
].group
= u
->enemies
[i
].group
= 0;
1569 board_play_(struct board
*board
, struct move
*m
, struct board_undo
*u
)
1571 #ifdef BOARD_UNDO_CHECKS
1572 assert(u
|| !board
->quicked
);
1575 if (u
) undo_init(board
, m
, u
);
1577 if (unlikely(is_pass(m
->coord
) || is_resign(m
->coord
))) {
1578 if (is_pass(m
->coord
) && board
->rules
== RULES_SIMING
) {
1579 /* On pass, the player gives a pass stone
1580 * to the opponent. */
1581 board
->captures
[stone_other(m
->color
)]++;
1583 struct move nomove
= { pass
, S_NONE
};
1586 board
->last_move4
= board
->last_move3
;
1587 board
->last_move3
= board
->last_move2
;
1589 board
->last_move2
= board
->last_move
;
1590 board
->last_move
= *m
;
1595 return board_play_f(board
, m
, -1, u
);
1598 for (f
= 0; f
< board
->flen
; f
++)
1599 if (board
->f
[f
] == m
->coord
)
1600 return board_play_f(board
, m
, f
, u
);
1603 fprintf(stderr
, "board_check: stone exists\n");
1608 board_play(struct board
*board
, struct move
*m
)
1610 return board_play_(board
, m
, NULL
);
1614 board_quick_play(struct board
*board
, struct move
*m
, struct board_undo
*u
)
1616 int r
= board_play_(board
, m
, u
);
1617 #ifdef BOARD_UNDO_CHECKS
1625 undo_merge(struct board
*b
, struct board_undo
*u
, struct move
*m
)
1627 coord_t coord
= m
->coord
;
1628 group_t group
= group_at(b
, coord
);
1629 struct undo_merge
*merged
= u
->merged
;
1631 // Others groups, in reverse order ...
1632 for (int i
= u
->nmerged
- 1; i
> 0; i
--) {
1633 group_t old_group
= merged
[i
].group
;
1635 board_group_info(b
, old_group
) = merged
[i
].info
;
1637 groupnext_at(b
, group_base(group
)) = groupnext_at(b
, merged
[i
].last
);
1638 groupnext_at(b
, merged
[i
].last
) = 0;
1641 printf("merged_group[%i]: (last: %s)", i
, coord2sstr(merged
[i
].last
, b
));
1642 foreach_in_group(b
, old_group
) {
1643 printf("%s ", coord2sstr(c
, b
));
1644 } foreach_in_group_end
;
1648 foreach_in_group(b
, old_group
) {
1649 group_at(b
, c
) = old_group
;
1650 } foreach_in_group_end
;
1653 // Restore first group
1654 groupnext_at(b
, u
->inserted
) = groupnext_at(b
, coord
);
1655 board_group_info(b
, merged
[0].group
) = merged
[0].info
;
1658 printf("merged_group[0]: ");
1659 foreach_in_group(b
, merged
[0].group
) {
1660 printf("%s ", coord2sstr(c
, b
));
1661 } foreach_in_group_end
;
1668 restore_enemies(struct board
*b
, struct board_undo
*u
, struct move
*m
)
1670 enum stone color
= m
->color
;
1671 enum stone other_color
= stone_other(m
->color
);
1673 struct undo_enemy
*enemy
= u
->enemies
;
1674 for (int i
= 0; i
< u
->nenemies
; i
++) {
1675 group_t old_group
= enemy
[i
].group
;
1677 board_group_info(b
, old_group
) = enemy
[i
].info
;
1679 coord_t
*stones
= enemy
[i
].stones
;
1680 for (int j
= 0; stones
[j
]; j
++) {
1681 board_at(b
, stones
[j
]) = other_color
;
1682 group_at(b
, stones
[j
]) = old_group
;
1683 groupnext_at(b
, stones
[j
]) = stones
[j
+ 1];
1685 foreach_neighbor(b
, stones
[j
], {
1686 inc_neighbor_count_at(b
, c
, other_color
);
1689 // Update liberties of neighboring groups
1690 foreach_neighbor(b
, stones
[j
], {
1691 if (board_at(b
, c
) != color
)
1693 group_t g
= group_at(b
, c
);
1694 if (g
== u
->merged
[0].group
|| g
== u
->merged
[1].group
|| g
== u
->merged
[2].group
|| g
== u
->merged
[3].group
)
1696 board_group_rmlib(b
, g
, stones
[j
], u
);
1703 board_undo_stone(struct board
*b
, struct board_undo
*u
, struct move
*m
)
1705 coord_t coord
= m
->coord
;
1706 enum stone color
= m
->color
;
1708 * - put captures back
1711 //printf("nmerged: %i\n", u->nmerged);
1713 // Restore merged groups
1715 undo_merge(b
, u
, m
);
1716 else // Single stone group undo
1717 memset(&board_group_info(b
, group_at(b
, coord
)), 0, sizeof(struct group
));
1719 board_at(b
, coord
) = S_NONE
;
1720 group_at(b
, coord
) = 0;
1721 groupnext_at(b
, coord
) = u
->next_at
;
1723 foreach_neighbor(b
, coord
, {
1724 dec_neighbor_count_at(b
, c
, color
);
1727 // Restore enemy groups
1729 b
->captures
[color
] -= u
->captures
;
1730 restore_enemies(b
, u
, m
);
1735 restore_suicide(struct board
*b
, struct board_undo
*u
, struct move
*m
)
1737 enum stone color
= m
->color
;
1738 enum stone other_color
= stone_other(m
->color
);
1740 struct undo_enemy
*enemy
= u
->enemies
;
1741 for (int i
= 0; i
< u
->nenemies
; i
++) {
1742 group_t old_group
= enemy
[i
].group
;
1744 board_group_info(b
, old_group
) = enemy
[i
].info
;
1746 coord_t
*stones
= enemy
[i
].stones
;
1747 for (int j
= 0; stones
[j
]; j
++) {
1748 board_at(b
, stones
[j
]) = other_color
;
1749 group_at(b
, stones
[j
]) = old_group
;
1750 groupnext_at(b
, stones
[j
]) = stones
[j
+ 1];
1752 foreach_neighbor(b
, stones
[j
], {
1753 inc_neighbor_count_at(b
, c
, other_color
);
1756 // Update liberties of neighboring groups
1757 foreach_neighbor(b
, stones
[j
], {
1758 if (board_at(b
, c
) != color
)
1760 group_t g
= group_at(b
, c
);
1761 if (g
== u
->enemies
[0].group
|| g
== u
->enemies
[1].group
||
1762 g
== u
->enemies
[2].group
|| g
== u
->enemies
[3].group
)
1764 board_group_rmlib(b
, g
, stones
[j
], u
);
1772 board_undo_suicide(struct board
*b
, struct board_undo
*u
, struct move
*m
)
1774 coord_t coord
= m
->coord
;
1775 enum stone other_color
= stone_other(m
->color
);
1777 // Pretend it's capture ...
1778 struct move m2
= { .coord
= m
->coord
, .color
= other_color
};
1779 b
->captures
[other_color
] -= u
->captures
;
1781 restore_suicide(b
, u
, &m2
);
1783 undo_merge(b
, u
, m
);
1785 board_at(b
, coord
) = S_NONE
;
1786 group_at(b
, coord
) = 0;
1787 groupnext_at(b
, coord
) = u
->next_at
;
1789 foreach_neighbor(b
, coord
, {
1790 dec_neighbor_count_at(b
, c
, m
->color
);
1797 board_quick_undo(struct board
*b
, struct move
*m
, struct board_undo
*u
)
1799 #ifdef BOARD_UNDO_CHECKS
1803 b
->last_move
= b
->last_move2
;
1804 b
->last_move2
= u
->last_move2
;
1806 b
->last_ko
= u
->last_ko
;
1807 b
->last_ko_age
= u
->last_ko_age
;
1809 if (unlikely(is_pass(m
->coord
) || is_resign(m
->coord
)))
1814 if (likely(board_at(b
, m
->coord
) == m
->color
))
1815 board_undo_stone(b
, u
, m
);
1816 else if (board_at(b
, m
->coord
) == S_NONE
)
1817 board_undo_suicide(b
, u
, m
);
1819 assert(0); /* Anything else doesn't make sense */
1823 /* Undo, supported only for pass moves. This form of undo is required by KGS
1824 * to settle disputes on dead groups. See also fast_board_undo() */
1825 int board_undo(struct board
*board
)
1827 if (!is_pass(board
->last_move
.coord
))
1829 if (board
->rules
== RULES_SIMING
) {
1830 /* Return pass stone to the passing player. */
1831 board
->captures
[stone_other(board
->last_move
.color
)]--;
1833 board
->last_move
= board
->last_move2
;
1834 board
->last_move2
= board
->last_move3
;
1835 board
->last_move3
= board
->last_move4
;
1836 if (board
->last_ko_age
== board
->moves
)
1837 board
->ko
= board
->last_ko
;
1842 board_try_random_move(struct board
*b
, enum stone color
, coord_t
*coord
, int f
, ppr_permit permit
, void *permit_data
)
1845 struct move m
= { *coord
, color
};
1847 fprintf(stderr
, "trying random move %d: %d,%d %s %d\n", f
, coord_x(*coord
, b
), coord_y(*coord
, b
), coord2sstr(*coord
, b
), board_is_valid_move(b
, &m
));
1848 if (unlikely(board_is_one_point_eye(b
, *coord
, color
)) /* bad idea to play into one, usually */
1849 || !board_is_valid_move(b
, &m
)
1850 || (permit
&& !permit(permit_data
, b
, &m
)))
1852 if (m
.coord
== *coord
) {
1853 return likely(board_play_f(b
, &m
, f
, NULL
) >= 0);
1855 *coord
= m
.coord
; // permit modified the coordinate
1856 return likely(board_play(b
, &m
) >= 0);
1861 board_play_random(struct board
*b
, enum stone color
, coord_t
*coord
, ppr_permit permit
, void *permit_data
)
1863 if (unlikely(b
->flen
== 0))
1866 int base
= fast_random(b
->flen
), f
;
1867 for (f
= base
; f
< b
->flen
; f
++)
1868 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
1870 for (f
= 0; f
< base
; f
++)
1871 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
1876 struct move m
= { pass
, color
};
1882 board_is_false_eyelike(struct board
*board
, coord_t coord
, enum stone eye_color
)
1884 enum stone color_diag_libs
[S_MAX
] = {0, 0, 0, 0};
1886 /* XXX: We attempt false eye detection but we will yield false
1887 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
1889 foreach_diag_neighbor(board
, coord
) {
1890 color_diag_libs
[(enum stone
) board_at(board
, c
)]++;
1891 } foreach_diag_neighbor_end
;
1892 /* For false eye, we need two enemy stones diagonally in the
1893 * middle of the board, or just one enemy stone at the edge
1894 * or in the corner. */
1895 color_diag_libs
[stone_other(eye_color
)] += !!color_diag_libs
[S_OFFBOARD
];
1896 return color_diag_libs
[stone_other(eye_color
)] >= 2;
1900 board_is_one_point_eye(struct board
*board
, coord_t coord
, enum stone eye_color
)
1902 return board_is_eyelike(board
, coord
, eye_color
)
1903 && !board_is_false_eyelike(board
, coord
, eye_color
);
1907 board_get_one_point_eye(struct board
*board
, coord_t coord
)
1909 if (board_is_one_point_eye(board
, coord
, S_WHITE
))
1911 else if (board_is_one_point_eye(board
, coord
, S_BLACK
))
1919 board_fast_score(struct board
*board
)
1922 memset(scores
, 0, sizeof(scores
));
1924 foreach_point(board
) {
1925 enum stone color
= board_at(board
, c
);
1926 if (color
== S_NONE
&& board
->rules
!= RULES_STONES_ONLY
)
1927 color
= board_get_one_point_eye(board
, c
);
1929 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1930 } foreach_point_end
;
1932 return board
->komi
+ (board
->rules
!= RULES_SIMING
? board
->handicap
: 0) + scores
[S_WHITE
] - scores
[S_BLACK
];
1935 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1937 /* One flood-fill iteration; returns true if next iteration
1940 board_tromp_taylor_iter(struct board
*board
, int *ownermap
)
1942 bool needs_update
= false;
1943 foreach_free_point(board
) {
1944 /* Ignore occupied and already-dame positions. */
1945 assert(board_at(board
, c
) == S_NONE
);
1946 if (board
->rules
== RULES_STONES_ONLY
)
1948 if (ownermap
[c
] == 3)
1950 /* Count neighbors. */
1952 foreach_neighbor(board
, c
, {
1955 /* If we have neighbors of both colors, or dame,
1956 * we are dame too. */
1957 if ((nei
[1] && nei
[2]) || nei
[3]) {
1959 /* Speed up the propagation. */
1960 foreach_neighbor(board
, c
, {
1961 if (board_at(board
, c
) == S_NONE
)
1964 needs_update
= true;
1967 /* If we have neighbors of one color, we are owned
1968 * by that color, too. */
1969 if (!ownermap
[c
] && (nei
[1] || nei
[2])) {
1970 int newowner
= nei
[1] ? 1 : 2;
1971 ownermap
[c
] = newowner
;
1972 /* Speed up the propagation. */
1973 foreach_neighbor(board
, c
, {
1974 if (board_at(board
, c
) == S_NONE
&& !ownermap
[c
])
1975 ownermap
[c
] = newowner
;
1977 needs_update
= true;
1980 } foreach_free_point_end
;
1981 return needs_update
;
1984 /* Tromp-Taylor Counting */
1986 board_official_score(struct board
*board
, struct move_queue
*q
)
1989 /* A point P, not colored C, is said to reach C, if there is a path of
1990 * (vertically or horizontally) adjacent points of P's color from P to
1991 * a point of color C.
1993 * A player's score is the number of points of her color, plus the
1994 * number of empty points that reach only her color. */
1996 int ownermap
[board_size2(board
)];
1998 const int o
[4] = {0, 1, 2, 0};
1999 foreach_point(board
) {
2000 ownermap
[c
] = o
[board_at(board
, c
)];
2001 s
[board_at(board
, c
)]++;
2002 } foreach_point_end
;
2005 /* Process dead groups. */
2006 for (unsigned int i
= 0; i
< q
->moves
; i
++) {
2007 foreach_in_group(board
, q
->move
[i
]) {
2008 enum stone color
= board_at(board
, c
);
2009 ownermap
[c
] = o
[stone_other(color
)];
2010 s
[color
]--; s
[stone_other(color
)]++;
2011 } foreach_in_group_end
;
2015 /* We need to special-case empty board. */
2016 if (!s
[S_BLACK
] && !s
[S_WHITE
])
2019 while (board_tromp_taylor_iter(board
, ownermap
))
2020 /* Flood-fill... */;
2023 memset(scores
, 0, sizeof(scores
));
2025 foreach_point(board
) {
2026 assert(board_at(board
, c
) == S_OFFBOARD
|| ownermap
[c
] != 0);
2027 if (ownermap
[c
] == 3)
2029 scores
[ownermap
[c
]]++;
2030 } foreach_point_end
;
2032 return board
->komi
+ (board
->rules
!= RULES_SIMING
? board
->handicap
: 0) + scores
[S_WHITE
] - scores
[S_BLACK
];
2036 board_set_rules(struct board
*board
, char *name
)
2038 if (!strcasecmp(name
, "japanese")) {
2039 board
->rules
= RULES_JAPANESE
;
2040 } else if (!strcasecmp(name
, "chinese")) {
2041 board
->rules
= RULES_CHINESE
;
2042 } else if (!strcasecmp(name
, "aga")) {
2043 board
->rules
= RULES_AGA
;
2044 } else if (!strcasecmp(name
, "new_zealand")) {
2045 board
->rules
= RULES_NEW_ZEALAND
;
2046 } else if (!strcasecmp(name
, "siming") || !strcasecmp(name
, "simplified_ing")) {
2047 board
->rules
= RULES_SIMING
;