11 #include "tactics/goals.h"
16 #include "patternsp.h"
22 static void board_trait_recompute(struct board
*board
, coord_t coord
);
23 #include "tactics/selfatari.h"
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_move3
= b
->last_move4
= b
->last_ko
= b
->ko
= m
;
47 board_init(char *fbookfile
)
49 struct board
*b
= malloc2(sizeof(struct board
));
52 b
->fbookfile
= fbookfile
;
62 board_alloc(struct board
*board
)
64 /* We do not allocate the board structure itself but we allocate
65 * all the arrays with board contents. */
67 int bsize
= board_size2(board
) * sizeof(*board
->b
);
68 int gsize
= board_size2(board
) * sizeof(*board
->g
);
69 int fsize
= board_size2(board
) * sizeof(*board
->f
);
70 int nsize
= board_size2(board
) * sizeof(*board
->n
);
71 int psize
= board_size2(board
) * sizeof(*board
->p
);
72 int hsize
= board_size2(board
) * 2 * sizeof(*board
->h
);
73 int gisize
= board_size2(board
) * sizeof(*board
->gi
);
75 int csize
= board_size2(board
) * sizeof(*board
->c
);
80 int ssize
= board_size2(board
) * sizeof(*board
->spathash
);
85 int p3size
= board_size2(board
) * sizeof(*board
->pat3
);
90 int tsize
= board_size2(board
) * sizeof(*board
->t
);
91 int tqsize
= board_size2(board
) * sizeof(*board
->t
);
96 int cdsize
= board_size2(board
) * sizeof(*board
->coord
);
98 size_t size
= bsize
+ gsize
+ fsize
+ psize
+ nsize
+ hsize
+ gisize
+ csize
+ ssize
+ p3size
+ tsize
+ tqsize
+ cdsize
;
99 void *x
= malloc2(size
);
101 /* board->b must come first */
102 board
->b
= x
; x
+= bsize
;
103 board
->g
= x
; x
+= gsize
;
104 board
->f
= x
; x
+= fsize
;
105 board
->p
= x
; x
+= psize
;
106 board
->n
= x
; x
+= nsize
;
107 board
->h
= x
; x
+= hsize
;
108 board
->gi
= x
; x
+= gisize
;
110 board
->c
= x
; x
+= csize
;
112 #ifdef BOARD_SPATHASH
113 board
->spathash
= x
; x
+= ssize
;
116 board
->pat3
= x
; x
+= p3size
;
119 board
->t
= x
; x
+= tsize
;
120 board
->tq
= x
; x
+= tqsize
;
122 board
->coord
= x
; x
+= cdsize
;
128 board_copy(struct board
*b2
, struct board
*b1
)
130 memcpy(b2
, b1
, sizeof(struct board
));
132 size_t size
= board_alloc(b2
);
133 memcpy(b2
->b
, b1
->b
, size
);
135 b2
->fbook
= NULL
; // XXX: Special semantics.
137 /* This is not 100% correct, but we can do away without
138 * locking as libmap cannot go away in the course of
139 * copy - b1 will still keep holding refcount at 1
141 __sync_fetch_and_add(&b2
->libmap
->refcount
, 1);
149 board_done_noalloc(struct board
*board
)
151 if (board
->b
) free(board
->b
);
152 if (board
->fbook
) fbook_done(board
->fbook
);
153 if (board
->libmap
) libmap_put(board
->libmap
);
157 board_done(struct board
*board
)
159 board_done_noalloc(board
);
164 board_resize(struct board
*board
, int size
)
167 libmap_put(board
->libmap
);
168 board
->libmap
= NULL
;
172 assert(board_size(board
) == size
+ 2);
174 assert(size
<= BOARD_MAX_SIZE
);
175 board
->size
= size
+ 2 /* S_OFFBOARD margin */;
176 board
->size2
= board_size(board
) * board_size(board
);
179 while ((1 << board
->bits2
) < board
->size2
) board
->bits2
++;
184 size_t asize
= board_alloc(board
);
185 memset(board
->b
, 0, asize
);
189 board_init_data(struct board
*board
)
191 int size
= board_size(board
);
194 board_resize(board
, size
- 2 /* S_OFFBOARD margin */);
196 /* Setup neighborhood iterators */
197 board
->nei8
[0] = -size
- 1; // (-1,-1)
200 board
->nei8
[3] = size
- 2; // (-1,0)
202 board
->nei8
[5] = size
- 2; // (-1,1)
205 board
->dnei
[0] = -size
- 1;
207 board
->dnei
[2] = size
*2 - 2;
210 /* Setup initial symmetry */
212 board
->symmetry
.d
= 1;
213 board
->symmetry
.x1
= board
->symmetry
.y1
= board_size(board
) / 2;
214 board
->symmetry
.x2
= board
->symmetry
.y2
= board_size(board
) - 1;
215 board
->symmetry
.type
= SYM_FULL
;
217 /* TODO: We do not handle board symmetry on boards
218 * with no tengen yet. */
219 board
->symmetry
.d
= 0;
220 board
->symmetry
.x1
= board
->symmetry
.y1
= 1;
221 board
->symmetry
.x2
= board
->symmetry
.y2
= board_size(board
) - 1;
222 board
->symmetry
.type
= SYM_NONE
;
225 /* Set up coordinate cache */
226 foreach_point(board
) {
227 board
->coord
[c
][0] = c
% board_size(board
);
228 board
->coord
[c
][1] = c
/ board_size(board
);
231 /* Draw the offboard margin */
232 int top_row
= board_size2(board
) - board_size(board
);
234 for (i
= 0; i
< board_size(board
); i
++)
235 board
->b
[i
] = board
->b
[top_row
+ i
] = S_OFFBOARD
;
236 for (i
= 0; i
<= top_row
; i
+= board_size(board
))
237 board
->b
[i
] = board
->b
[board_size(board
) - 1 + i
] = S_OFFBOARD
;
239 foreach_point(board
) {
241 if (board_at(board
, coord
) == S_OFFBOARD
)
243 foreach_neighbor(board
, c
, {
244 inc_neighbor_count_at(board
, coord
, board_at(board
, c
));
248 /* All positions are free! Except the margin. */
249 for (i
= board_size(board
); i
< (board_size(board
) - 1) * board_size(board
); i
++)
250 if (i
% board_size(board
) != 0 && i
% board_size(board
) != board_size(board
) - 1)
251 board
->f
[board
->flen
++] = i
;
253 /* Initialize zobrist hashtable. */
254 /* We will need these to be stable across Pachi runs for
255 * certain kinds of pattern matching, thus we do not use
256 * fast_random() for this. */
257 hash_t hseed
= 0x3121110101112131;
258 foreach_point(board
) {
259 board
->h
[c
* 2] = (hseed
*= 16807);
260 if (!board
->h
[c
* 2])
262 /* And once again for white */
263 board
->h
[c
* 2 + 1] = (hseed
*= 16807);
264 if (!board
->h
[c
* 2 + 1])
265 board
->h
[c
* 2 + 1] = 1;
268 #ifdef BOARD_SPATHASH
269 /* Initialize spatial hashes. */
270 foreach_point(board
) {
271 for (int d
= 1; d
<= BOARD_SPATHASH_MAXD
; d
++) {
272 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
273 ptcoords_at(x
, y
, c
, board
, j
);
274 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][0] ^=
275 pthashes
[0][j
][board_at(board
, c
)];
276 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][1] ^=
277 pthashes
[0][j
][stone_other(board_at(board
, c
))];
283 /* Initialize 3x3 pattern codes. */
284 foreach_point(board
) {
285 if (board_at(board
, c
) == S_NONE
)
286 board
->pat3
[c
] = pattern3_hash(board
, c
);
290 /* Initialize traits. */
291 foreach_point(board
) {
292 trait_at(board
, c
, S_BLACK
).cap
= 0;
293 trait_at(board
, c
, S_WHITE
).cap
= 0;
294 trait_at(board
, c
, S_BLACK
).cap1
= 0;
295 trait_at(board
, c
, S_WHITE
).cap1
= 0;
296 #ifdef BOARD_TRAIT_SAFE
297 trait_at(board
, c
, S_BLACK
).safe
= true;
298 trait_at(board
, c
, S_WHITE
).safe
= true;
303 board
->libmap_init_groups
= true;
307 board_clear(struct board
*board
)
309 int size
= board_size(board
);
310 floating_t komi
= board
->komi
;
311 char *fbookfile
= board
->fbookfile
;
312 enum go_ruleset rules
= board
->rules
;
314 board_done_noalloc(board
);
316 static struct board bcache
[BOARD_MAX_SIZE
+ 2];
317 assert(size
> 0 && size
<= BOARD_MAX_SIZE
+ 2);
318 if (bcache
[size
- 1].size
== size
) {
319 board_copy(board
, &bcache
[size
- 1]);
321 board_init_data(board
);
322 board_copy(&bcache
[size
- 1], board
);
326 board
->fbookfile
= fbookfile
;
327 board
->rules
= rules
;
329 if (board
->fbookfile
) {
330 board
->fbook
= fbook_init(board
->fbookfile
, board
);
333 libmap_put(board
->libmap
);
334 board
->libmap
= NULL
;
336 board
->lmqueue
= NULL
;
340 board_print_top(struct board
*board
, char *s
, char *end
, int c
)
342 for (int i
= 0; i
< c
; i
++) {
343 char asdf
[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
344 s
+= snprintf(s
, end
- s
, " ");
345 for (int x
= 1; x
< board_size(board
) - 1; x
++)
346 s
+= snprintf(s
, end
- s
, "%c ", asdf
[x
- 1]);
347 s
+= snprintf(s
, end
-s
, " ");
349 s
+= snprintf(s
, end
- s
, "\n");
350 for (int i
= 0; i
< c
; i
++) {
351 s
+= snprintf(s
, end
- s
, " +-");
352 for (int x
= 1; x
< board_size(board
) - 1; x
++)
353 s
+= snprintf(s
, end
- s
, "--");
354 s
+= snprintf(s
, end
- s
, "+");
356 s
+= snprintf(s
, end
- s
, "\n");
361 board_print_bottom(struct board
*board
, char *s
, char *end
, int c
)
363 for (int i
= 0; i
< c
; i
++) {
364 s
+= snprintf(s
, end
- s
, " +-");
365 for (int x
= 1; x
< board_size(board
) - 1; x
++)
366 s
+= snprintf(s
, end
- s
, "--");
367 s
+= snprintf(s
, end
- s
, "+");
369 s
+= snprintf(s
, end
- s
, "\n");
374 board_print_row(struct board
*board
, int y
, char *s
, char *end
, board_cprint cprint
)
376 s
+= snprintf(s
, end
- s
, " %2d | ", y
);
377 for (int x
= 1; x
< board_size(board
) - 1; x
++) {
378 if (coord_x(board
->last_move
.coord
, board
) == x
&& coord_y(board
->last_move
.coord
, board
) == y
)
379 s
+= snprintf(s
, end
- s
, "%c)", stone2char(board_atxy(board
, x
, y
)));
381 s
+= snprintf(s
, end
- s
, "%c ", stone2char(board_atxy(board
, x
, y
)));
383 s
+= snprintf(s
, end
- s
, "|");
385 s
+= snprintf(s
, end
- s
, " %2d | ", y
);
386 for (int x
= 1; x
< board_size(board
) - 1; x
++) {
387 s
= cprint(board
, coord_xy(board
, x
, y
), s
, end
);
389 s
+= snprintf(s
, end
- s
, "|");
391 s
+= snprintf(s
, end
- s
, "\n");
396 board_print_custom(struct board
*board
, FILE *f
, board_cprint cprint
)
400 char *end
= buf
+ sizeof(buf
);
401 s
+= snprintf(s
, end
- s
, "Move: % 3d Komi: %2.1f Handicap: %d Captures B: %d W: %d\n",
402 board
->moves
, board
->komi
, board
->handicap
,
403 board
->captures
[S_BLACK
], board
->captures
[S_WHITE
]);
404 s
= board_print_top(board
, s
, end
, 1 + !!cprint
);
405 for (int y
= board_size(board
) - 2; y
>= 1; y
--)
406 s
= board_print_row(board
, y
, s
, end
, cprint
);
407 board_print_bottom(board
, s
, end
, 1 + !!cprint
);
408 fprintf(f
, "%s\n", buf
);
412 cprint_group(struct board
*board
, coord_t c
, char *s
, char *end
)
414 s
+= snprintf(s
, end
- s
, "%d ", group_base(group_at(board
, c
)));
419 board_print(struct board
*board
, FILE *f
)
421 board_print_custom(board
, f
, DEBUGL(6) ? cprint_group
: NULL
);
427 #if BOARD_TRAIT_SAFE == 1
429 board_trait_safe(struct board
*board
, coord_t coord
, enum stone color
)
431 return board_safe_to_play(board
, coord
, color
);
433 #elif BOARD_TRAIT_SAFE == 2
435 board_trait_safe(struct board
*board
, coord_t coord
, enum stone color
)
437 return !is_bad_selfatari(board
, color
, coord
);
442 board_trait_recompute(struct board
*board
, coord_t coord
)
444 int sfb
= -1, sfw
= -1;
445 #ifdef BOARD_TRAIT_SAFE
446 sfb
= trait_at(board
, coord
, S_BLACK
).safe
= board_trait_safe(board
, coord
, S_BLACK
);
447 sfw
= trait_at(board
, coord
, S_WHITE
).safe
= board_trait_safe(board
, coord
, S_WHITE
);
450 fprintf(stderr
, "traits[%s:%s lib=%d] (black cap=%d cap1=%d safe=%d) (white cap=%d cap1=%d safe=%d)\n",
451 coord2sstr(coord
, board
), stone2str(board_at(board
, coord
)), immediate_liberty_count(board
, coord
),
452 trait_at(board
, coord
, S_BLACK
).cap
, trait_at(board
, coord
, S_BLACK
).cap1
, sfb
,
453 trait_at(board
, coord
, S_WHITE
).cap
, trait_at(board
, coord
, S_WHITE
).cap1
, sfw
);
458 /* Recompute traits for dirty points that we have previously touched
459 * somehow (libs of their neighbors changed or so). */
461 board_traits_recompute(struct board
*board
)
464 for (int i
= 0; i
< board
->tqlen
; i
++) {
465 coord_t coord
= board
->tq
[i
];
466 trait_at(board
, coord
, S_BLACK
).dirty
= false;
467 if (board_at(board
, coord
) != S_NONE
)
469 board_trait_recompute(board
, coord
);
475 /* Queue traits of given point for recomputing. */
477 board_trait_queue(struct board
*board
, coord_t coord
)
480 if (trait_at(board
, coord
, S_BLACK
).dirty
)
482 board
->tq
[board
->tqlen
++] = coord
;
483 trait_at(board
, coord
, S_BLACK
).dirty
= true;
488 /* Update board hash with given coordinate. */
489 static void profiling_noinline
490 board_hash_update(struct board
*board
, coord_t coord
, enum stone color
)
492 board
->hash
^= hash_at(board
, coord
, color
);
493 board
->qhash
[coord_quadrant(coord
, board
)] ^= hash_at(board
, coord
, color
);
495 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
);
497 #ifdef BOARD_SPATHASH
498 /* Gridcular metric is reflective, so we update all hashes
499 * of appropriate ditance in OUR circle. */
500 for (int d
= 1; d
<= BOARD_SPATHASH_MAXD
; d
++) {
501 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
502 ptcoords_at(x
, y
, coord
, board
, j
);
503 /* We either changed from S_NONE to color
504 * or vice versa; doesn't matter. */
505 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][0] ^=
506 pthashes
[0][j
][color
] ^ pthashes
[0][j
][S_NONE
];
507 board
->spathash
[coord_xy(board
, x
, y
)][d
- 1][1] ^=
508 pthashes
[0][j
][stone_other(color
)] ^ pthashes
[0][j
][S_NONE
];
513 #if defined(BOARD_PAT3)
514 /* @color is not what we need in case of capture. */
515 static const int ataribits
[8] = { -1, 0, -1, 1, 2, -1, 3, -1 };
516 enum stone new_color
= board_at(board
, coord
);
517 bool in_atari
= false;
518 if (new_color
== S_NONE
) {
519 board
->pat3
[coord
] = pattern3_hash(board
, coord
);
521 in_atari
= (board_group_info(board
, group_at(board
, coord
)).libs
== 1);
523 foreach_8neighbor(board
, coord
) {
524 /* Internally, the loop uses fn__i=[0..7]. We can use
525 * it directly to address bits within the bitmap of the
526 * neighbors since the bitmap order is reverse to the
528 if (board_at(board
, c
) != S_NONE
)
530 board
->pat3
[c
] &= ~(3 << (fn__i
*2));
531 board
->pat3
[c
] |= new_color
<< (fn__i
*2);
532 if (ataribits
[fn__i
] >= 0) {
533 board
->pat3
[c
] &= ~(1 << (16 + ataribits
[fn__i
]));
534 board
->pat3
[c
] |= in_atari
<< (16 + ataribits
[fn__i
]);
536 #if defined(BOARD_TRAITS)
537 board_trait_queue(board
, c
);
539 } foreach_8neighbor_end
;
543 /* Commit current board hash to history. */
544 static void profiling_noinline
545 board_hash_commit(struct board
*board
)
548 fprintf(stderr
, "board_hash_commit %"PRIhash
"\n", board
->hash
);
549 if (likely(board
->history_hash
[board
->hash
& history_hash_mask
]) == 0) {
550 board
->history_hash
[board
->hash
& history_hash_mask
] = board
->hash
;
552 hash_t i
= board
->hash
;
553 while (board
->history_hash
[i
& history_hash_mask
]) {
554 if (board
->history_hash
[i
& history_hash_mask
] == board
->hash
) {
556 fprintf(stderr
, "SUPERKO VIOLATION noted at %d,%d\n",
557 coord_x(board
->last_move
.coord
, board
), coord_y(board
->last_move
.coord
, board
));
558 board
->superko_violation
= true;
561 i
= history_hash_next(i
);
563 board
->history_hash
[i
& history_hash_mask
] = board
->hash
;
569 board_symmetry_update(struct board
*b
, struct board_symmetry
*symmetry
, coord_t c
)
571 if (likely(symmetry
->type
== SYM_NONE
)) {
572 /* Fully degenerated already. We do not support detection
573 * of restoring of symmetry, assuming that this is too rare
574 * a case to handle. */
578 int x
= coord_x(c
, b
), y
= coord_y(c
, b
), t
= board_size(b
) / 2;
579 int dx
= board_size(b
) - 1 - x
; /* for SYM_DOWN */
581 fprintf(stderr
, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
582 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
583 symmetry
->d
, symmetry
->type
, x
, y
);
586 switch (symmetry
->type
) {
588 if (x
== t
&& y
== t
) {
589 /* Tengen keeps full symmetry. */
592 /* New symmetry now? */
594 symmetry
->type
= SYM_DIAG_UP
;
595 symmetry
->x1
= symmetry
->y1
= 1;
596 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
598 } else if (dx
== y
) {
599 symmetry
->type
= SYM_DIAG_DOWN
;
600 symmetry
->x1
= symmetry
->y1
= 1;
601 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
604 symmetry
->type
= SYM_HORIZ
;
606 symmetry
->y2
= board_size(b
) - 1;
609 symmetry
->type
= SYM_VERT
;
611 symmetry
->x2
= board_size(b
) - 1;
615 symmetry
->type
= SYM_NONE
;
616 symmetry
->x1
= symmetry
->y1
= 1;
617 symmetry
->x2
= symmetry
->y2
= board_size(b
) - 1;
643 fprintf(stderr
, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
644 symmetry
->x1
, symmetry
->y1
, symmetry
->x2
, symmetry
->y2
,
645 symmetry
->d
, symmetry
->type
);
652 board_handicap_stone(struct board
*board
, int x
, int y
, FILE *f
)
655 m
.color
= S_BLACK
; m
.coord
= coord_xy(board
, x
, y
);
657 board_play(board
, &m
);
658 /* Simulate white passing; otherwise, UCT search can get confused since
659 * tree depth parity won't match the color to move. */
662 char *str
= coord2str(m
.coord
, board
);
664 fprintf(stderr
, "choosing handicap %s (%d,%d)\n", str
, x
, y
);
665 if (f
) fprintf(f
, "%s ", str
);
670 board_handicap(struct board
*board
, int stones
, FILE *f
)
672 int margin
= 3 + (board_size(board
) >= 13);
674 int mid
= board_size(board
) / 2;
675 int max
= board_size(board
) - 1 - margin
;
676 const int places
[][2] = {
677 { min
, min
}, { max
, max
}, { min
, max
}, { max
, min
},
678 { min
, mid
}, { max
, mid
},
679 { mid
, min
}, { mid
, max
},
683 board
->handicap
= stones
;
685 if (stones
== 5 || stones
== 7) {
686 board_handicap_stone(board
, mid
, mid
, f
);
691 for (i
= 0; i
< stones
; i
++)
692 board_handicap_stone(board
, places
[i
][0], places
[i
][1], f
);
696 static void __attribute__((noinline
))
697 check_libs_consistency(struct board
*board
, group_t g
)
701 struct group
*gi
= &board_group_info(board
, g
);
702 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
703 if (gi
->lib
[i
] && board_at(board
, gi
->lib
[i
]) != S_NONE
) {
704 fprintf(stderr
, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi
->lib
[i
], board
), g
, coord2sstr(group_base(g
), board
));
711 check_pat3_consistency(struct board
*board
, coord_t coord
)
714 foreach_8neighbor(board
, coord
) {
715 if (board_at(board
, c
) == S_NONE
&& pattern3_hash(board
, c
) != board
->pat3
[c
]) {
716 board_print(board
, stderr
);
717 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
);
720 } foreach_8neighbor_end
;
725 board_capturable_add(struct board
*board
, group_t group
, coord_t lib
, bool onestone
)
727 //fprintf(stderr, "group %s cap %s\n", coord2sstr(group, board), coord2sstr(lib, boarD));
729 /* Increase capturable count trait of my last lib. */
730 enum stone capturing_color
= stone_other(board_at(board
, group
));
731 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
732 foreach_neighbor(board
, lib
, {
733 if (DEBUGL(8) && group_at(board
, c
) == group
)
734 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
);
735 trait_at(board
, lib
, capturing_color
).cap
+= (group_at(board
, c
) == group
);
736 trait_at(board
, lib
, capturing_color
).cap1
+= (group_at(board
, c
) == group
&& onestone
);
738 board_trait_queue(board
, lib
);
743 foreach_neighbor(board
, lib
, {
744 board
->pat3
[lib
] |= (group_at(board
, c
) == group
) << (16 + 3 - fn__i
);
750 /* Update the list of capturable groups. */
752 assert(board
->clen
< board_size2(board
));
753 board
->c
[board
->clen
++] = group
;
757 board_capturable_rm(struct board
*board
, group_t group
, coord_t lib
, bool onestone
)
759 //fprintf(stderr, "group %s nocap %s\n", coord2sstr(group, board), coord2sstr(lib, board));
761 /* Decrease capturable count trait of my previously-last lib. */
762 enum stone capturing_color
= stone_other(board_at(board
, group
));
763 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
764 foreach_neighbor(board
, lib
, {
765 if (DEBUGL(8) && group_at(board
, c
) == group
)
766 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
);
767 trait_at(board
, lib
, capturing_color
).cap
-= (group_at(board
, c
) == group
);
768 trait_at(board
, lib
, capturing_color
).cap1
-= (group_at(board
, c
) == group
&& onestone
);
770 board_trait_queue(board
, lib
);
775 foreach_neighbor(board
, lib
, {
776 board
->pat3
[lib
] &= ~((group_at(board
, c
) == group
) << (16 + 3 - fn__i
));
782 /* Update the list of capturable groups. */
783 for (int i
= 0; i
< board
->clen
; i
++) {
784 if (unlikely(board
->c
[i
] == group
)) {
785 board
->c
[i
] = board
->c
[--board
->clen
];
789 fprintf(stderr
, "rm of bad group %d\n", group_base(group
));
795 board_atariable_add(struct board
*board
, group_t group
, coord_t lib1
, coord_t lib2
)
798 board_trait_queue(board
, lib1
);
799 board_trait_queue(board
, lib2
);
803 board_atariable_rm(struct board
*board
, group_t group
, coord_t lib1
, coord_t lib2
)
806 board_trait_queue(board
, lib1
);
807 board_trait_queue(board
, lib2
);
812 board_group_addlib(struct board
*board
, group_t group
, coord_t coord
)
815 fprintf(stderr
, "Group %d[%s] %d: Adding liberty %s\n",
816 group_base(group
), coord2sstr(group_base(group
), board
),
817 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
820 check_libs_consistency(board
, group
);
822 struct group
*gi
= &board_group_info(board
, group
);
823 bool onestone
= group_is_onestone(board
, group
);
824 if (gi
->libs
< GROUP_KEEP_LIBS
) {
825 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
827 /* Seems extra branch just slows it down */
831 if (unlikely(gi
->lib
[i
] == coord
))
835 board_capturable_add(board
, group
, coord
, onestone
);
836 } else if (gi
->libs
== 1) {
837 board_capturable_rm(board
, group
, gi
->lib
[0], onestone
);
838 board_atariable_add(board
, group
, gi
->lib
[0], coord
);
839 } else if (gi
->libs
== 2) {
840 board_atariable_rm(board
, group
, gi
->lib
[0], gi
->lib
[1]);
842 gi
->lib
[gi
->libs
++] = coord
;
845 check_libs_consistency(board
, group
);
849 board_group_find_extra_libs(struct board
*board
, group_t group
, struct group
*gi
, coord_t avoid
)
851 /* Add extra liberty from the board to our liberty list. */
852 unsigned char watermark
[board_size2(board
) / 8];
853 memset(watermark
, 0, sizeof(watermark
));
854 #define watermark_get(c) (watermark[c >> 3] & (1 << (c & 7)))
855 #define watermark_set(c) watermark[c >> 3] |= (1 << (c & 7))
857 for (int i
= 0; i
< GROUP_KEEP_LIBS
- 1; i
++)
858 watermark_set(gi
->lib
[i
]);
859 watermark_set(avoid
);
861 foreach_in_group(board
, group
) {
863 foreach_neighbor(board
, coord2
, {
864 if (board_at(board
, c
) + watermark_get(c
) != S_NONE
)
867 gi
->lib
[gi
->libs
++] = c
;
868 if (unlikely(gi
->libs
>= GROUP_KEEP_LIBS
))
871 } foreach_in_group_end
;
877 board_group_rmlib(struct board
*board
, group_t group
, coord_t coord
)
880 fprintf(stderr
, "Group %d[%s] %d: Removing liberty %s\n",
881 group_base(group
), coord2sstr(group_base(group
), board
),
882 board_group_info(board
, group
).libs
, coord2sstr(coord
, board
));
885 struct group
*gi
= &board_group_info(board
, group
);
886 bool onestone
= group_is_onestone(board
, group
);
887 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++) {
889 /* Seems extra branch just slows it down */
893 if (likely(gi
->lib
[i
] != coord
))
896 coord_t lib
= gi
->lib
[i
] = gi
->lib
[--gi
->libs
];
897 gi
->lib
[gi
->libs
] = 0;
899 check_libs_consistency(board
, group
);
901 /* Postpone refilling lib[] until we need to. */
902 assert(GROUP_REFILL_LIBS
> 1);
903 if (gi
->libs
> GROUP_REFILL_LIBS
)
905 if (gi
->libs
== GROUP_REFILL_LIBS
)
906 board_group_find_extra_libs(board
, group
, gi
, coord
);
909 board_atariable_add(board
, group
, gi
->lib
[0], gi
->lib
[1]);
910 } else if (gi
->libs
== 1) {
911 board_capturable_add(board
, group
, gi
->lib
[0], onestone
);
912 board_atariable_rm(board
, group
, gi
->lib
[0], lib
);
913 } else if (gi
->libs
== 0)
914 board_capturable_rm(board
, group
, lib
, onestone
);
918 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
919 * can call this multiple times per coord. */
920 check_libs_consistency(board
, group
);
925 /* This is a low-level routine that doesn't maintain consistency
926 * of all the board data structures. */
928 board_remove_stone(struct board
*board
, group_t group
, coord_t c
)
930 enum stone color
= board_at(board
, c
);
931 board_at(board
, c
) = S_NONE
;
932 group_at(board
, c
) = 0;
933 board_hash_update(board
, c
, color
);
935 /* We mark as cannot-capture now. If this is a ko/snapback,
936 * we will get incremented later in board_group_addlib(). */
937 trait_at(board
, c
, S_BLACK
).cap
= trait_at(board
, c
, S_BLACK
).cap1
= 0;
938 trait_at(board
, c
, S_WHITE
).cap
= trait_at(board
, c
, S_WHITE
).cap1
= 0;
939 board_trait_queue(board
, c
);
942 /* Increase liberties of surrounding groups */
944 foreach_neighbor(board
, coord
, {
945 dec_neighbor_count_at(board
, c
, color
);
946 board_trait_queue(board
, c
);
947 group_t g
= group_at(board
, c
);
949 board_group_addlib(board
, g
, coord
);
953 /* board_hash_update() might have seen the freed up point as able
954 * to capture another group in atari that only after the loop
955 * above gained enough liberties. Reset pat3 again. */
956 board
->pat3
[c
] = pattern3_hash(board
, c
);
960 fprintf(stderr
, "pushing free move [%d]: %d,%d\n", board
->flen
, coord_x(c
, board
), coord_y(c
, board
));
961 board
->f
[board
->flen
++] = c
;
964 static int profiling_noinline
965 board_group_capture(struct board
*board
, group_t group
)
969 foreach_in_group(board
, group
) {
970 board
->captures
[stone_other(board_at(board
, c
))]++;
971 board_remove_stone(board
, group
, c
);
973 } foreach_in_group_end
;
975 struct group
*gi
= &board_group_info(board
, group
);
976 assert(gi
->libs
== 0);
977 memset(gi
, 0, sizeof(*gi
));
983 static void profiling_noinline
984 add_to_group(struct board
*board
, group_t group
, coord_t prevstone
, coord_t coord
)
987 struct group
*gi
= &board_group_info(board
, group
);
988 bool onestone
= group_is_onestone(board
, group
);
991 /* Our group is temporarily in atari; make sure the capturable
992 * counts also correspond to the newly added stone before we
993 * start adding liberties again so bump-dump ops match. */
994 enum stone capturing_color
= stone_other(board_at(board
, group
));
995 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
997 coord_t lib
= board_group_info(board
, group
).lib
[0];
998 if (coord_is_adjecent(lib
, coord
, board
)) {
1000 fprintf(stderr
, "add_to_group %s: %s[%d] bump\n", coord2sstr(group
, board
), coord2sstr(lib
, board
), trait_at(board
, lib
, capturing_color
).cap
);
1001 trait_at(board
, lib
, capturing_color
).cap
++;
1002 /* This is never a 1-stone group, obviously. */
1003 board_trait_queue(board
, lib
);
1007 /* We are not 1-stone group anymore, update the cap1
1008 * counter specifically. */
1009 foreach_neighbor(board
, group
, {
1010 if (board_at(board
, c
) != S_NONE
) continue;
1011 trait_at(board
, c
, capturing_color
).cap1
--;
1012 board_trait_queue(board
, c
);
1018 group_at(board
, coord
) = group
;
1019 groupnext_at(board
, coord
) = groupnext_at(board
, prevstone
);
1020 groupnext_at(board
, prevstone
) = coord
;
1022 foreach_neighbor(board
, coord
, {
1023 if (board_at(board
, c
) == S_NONE
)
1024 board_group_addlib(board
, group
, c
);
1028 fprintf(stderr
, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
1029 coord_x(prevstone
, board
), coord_y(prevstone
, board
),
1030 coord_x(coord
, board
), coord_y(coord
, board
),
1031 groupnext_at(board
, coord
) % board_size(board
), groupnext_at(board
, coord
) / board_size(board
),
1035 static void profiling_noinline
1036 merge_groups(struct board
*board
, group_t group_to
, group_t group_from
)
1039 fprintf(stderr
, "board_play_raw: merging groups %d -> %d\n",
1040 group_base(group_from
), group_base(group_to
));
1041 struct group
*gi_from
= &board_group_info(board
, group_from
);
1042 struct group
*gi_to
= &board_group_info(board
, group_to
);
1043 bool onestone_from
= group_is_onestone(board
, group_from
);
1044 bool onestone_to
= group_is_onestone(board
, group_to
);
1046 /* We do this early before the group info is rewritten. */
1047 if (gi_from
->libs
== 2)
1048 board_atariable_rm(board
, group_from
, gi_from
->lib
[0], gi_from
->lib
[1]);
1049 else if (gi_from
->libs
== 1)
1050 board_capturable_rm(board
, group_from
, gi_from
->lib
[0], onestone_from
);
1053 fprintf(stderr
,"---- (froml %d, tol %d)\n", gi_from
->libs
, gi_to
->libs
);
1055 if (gi_to
->libs
< GROUP_KEEP_LIBS
) {
1056 for (int i
= 0; i
< gi_from
->libs
; i
++) {
1057 for (int j
= 0; j
< gi_to
->libs
; j
++)
1058 if (gi_to
->lib
[j
] == gi_from
->lib
[i
])
1060 if (gi_to
->libs
== 0) {
1061 board_capturable_add(board
, group_to
, gi_from
->lib
[i
], onestone_to
);
1062 } else if (gi_to
->libs
== 1) {
1063 board_capturable_rm(board
, group_to
, gi_to
->lib
[0], onestone_to
);
1064 board_atariable_add(board
, group_to
, gi_to
->lib
[0], gi_from
->lib
[i
]);
1065 } else if (gi_to
->libs
== 2) {
1066 board_atariable_rm(board
, group_to
, gi_to
->lib
[0], gi_to
->lib
[1]);
1068 gi_to
->lib
[gi_to
->libs
++] = gi_from
->lib
[i
];
1069 if (gi_to
->libs
>= GROUP_KEEP_LIBS
)
1075 if (gi_to
->libs
== 1) {
1076 coord_t lib
= board_group_info(board
, group_to
).lib
[0];
1078 enum stone capturing_color
= stone_other(board_at(board
, group_to
));
1079 assert(capturing_color
== S_BLACK
|| capturing_color
== S_WHITE
);
1081 /* Our group is currently in atari; make sure we properly
1082 * count in even the neighbors from the other group in the
1083 * capturable counter. */
1084 foreach_neighbor(board
, lib
, {
1085 if (DEBUGL(8) && group_at(board
, c
) == group_from
)
1086 fprintf(stderr
, "%s[%d] cap bump\n", coord2sstr(lib
, board
), trait_at(board
, lib
, capturing_color
).cap
);
1087 trait_at(board
, lib
, capturing_color
).cap
+= (group_at(board
, c
) == group_from
);
1088 /* This is never a 1-stone group, obviously. */
1090 board_trait_queue(board
, lib
);
1093 /* We are not 1-stone group anymore, update the cap1
1094 * counter specifically. */
1095 foreach_neighbor(board
, group_to
, {
1096 if (board_at(board
, c
) != S_NONE
) continue;
1097 trait_at(board
, c
, capturing_color
).cap1
--;
1098 board_trait_queue(board
, c
);
1103 if (gi_from
->libs
== 1) {
1104 /* We removed group_from from capturable groups,
1105 * therefore switching the atari flag off.
1106 * We need to set it again since group_to is also
1109 foreach_neighbor(board
, lib
, {
1110 board
->pat3
[lib
] |= (group_at(board
, c
) == group_from
) << (16 + 3 - fn__i
);
1117 coord_t last_in_group
;
1118 foreach_in_group(board
, group_from
) {
1120 group_at(board
, c
) = group_to
;
1121 } foreach_in_group_end
;
1122 groupnext_at(board
, last_in_group
) = groupnext_at(board
, group_base(group_to
));
1123 groupnext_at(board
, group_base(group_to
)) = group_base(group_from
);
1124 memset(gi_from
, 0, sizeof(struct group
));
1127 fprintf(stderr
, "board_play_raw: merged group: %d\n",
1128 group_base(group_to
));
1131 static group_t profiling_noinline
1132 new_group(struct board
*board
, coord_t coord
)
1134 group_t group
= coord
;
1135 struct group
*gi
= &board_group_info(board
, group
);
1136 foreach_neighbor(board
, coord
, {
1137 if (board_at(board
, c
) == S_NONE
)
1138 /* board_group_addlib is ridiculously expensive for us */
1139 #if GROUP_KEEP_LIBS < 4
1140 if (gi
->libs
< GROUP_KEEP_LIBS
)
1142 gi
->lib
[gi
->libs
++] = c
;
1145 group_at(board
, coord
) = group
;
1146 groupnext_at(board
, coord
) = 0;
1149 board_atariable_add(board
, group
, gi
->lib
[0], gi
->lib
[1]);
1150 else if (gi
->libs
== 1)
1151 board_capturable_add(board
, group
, gi
->lib
[0], true);
1152 check_libs_consistency(board
, group
);
1155 fprintf(stderr
, "new_group: added %d,%d to group %d\n",
1156 coord_x(coord
, board
), coord_y(coord
, board
),
1162 static inline group_t
1163 play_one_neighbor(struct board
*board
,
1164 coord_t coord
, enum stone color
, enum stone other_color
,
1165 coord_t c
, group_t group
)
1167 enum stone ncolor
= board_at(board
, c
);
1168 group_t ngroup
= group_at(board
, c
);
1170 inc_neighbor_count_at(board
, c
, color
);
1171 /* We can be S_NONE, in that case we need to update the safety
1172 * trait since we might be left with only one liberty. */
1173 board_trait_queue(board
, c
);
1178 board_group_rmlib(board
, ngroup
, coord
);
1180 fprintf(stderr
, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
1181 group_base(ngroup
), ncolor
, color
, other_color
);
1183 if (ncolor
== color
&& ngroup
!= group
) {
1186 add_to_group(board
, group
, c
, coord
);
1188 merge_groups(board
, group
, ngroup
);
1190 } else if (ncolor
== other_color
) {
1192 struct group
*gi
= &board_group_info(board
, ngroup
);
1193 fprintf(stderr
, "testing captured group %d[%s]: ", group_base(ngroup
), coord2sstr(group_base(ngroup
), board
));
1194 for (int i
= 0; i
< GROUP_KEEP_LIBS
; i
++)
1195 fprintf(stderr
, "%s ", coord2sstr(gi
->lib
[i
], board
));
1196 fprintf(stderr
, "\n");
1198 if (unlikely(board_group_captured(board
, ngroup
)))
1199 board_group_capture(board
, ngroup
);
1204 /* We played on a place with at least one liberty. We will become a member of
1205 * some group for sure. */
1206 static group_t profiling_noinline
1207 board_play_outside(struct board
*board
, struct move
*m
, int f
)
1209 coord_t coord
= m
->coord
;
1210 enum stone color
= m
->color
;
1211 enum stone other_color
= stone_other(color
);
1214 board
->f
[f
] = board
->f
[--board
->flen
];
1216 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
1218 #if defined(BOARD_TRAITS) && defined(DEBUG)
1219 /* Sanity check that cap matches reality. */
1222 foreach_neighbor(board
, coord
, {
1223 group_t g
= group_at(board
, c
);
1224 a
+= g
&& (board_at(board
, c
) == other_color
&& board_group_info(board
, g
).libs
== 1);
1225 b
+= g
&& (board_at(board
, c
) == other_color
&& board_group_info(board
, g
).libs
== 1) && group_is_onestone(board
, g
);
1227 assert(a
== trait_at(board
, coord
, color
).cap
);
1228 assert(b
== trait_at(board
, coord
, color
).cap1
);
1229 #ifdef BOARD_TRAIT_SAFE
1230 assert(board_trait_safe(board
, coord
, color
) == trait_at(board
, coord
, color
).safe
);
1234 foreach_neighbor(board
, coord
, {
1235 group
= play_one_neighbor(board
, coord
, color
, other_color
, c
, group
);
1238 board_at(board
, coord
) = color
;
1239 if (unlikely(!group
)) {
1240 group
= new_group(board
, coord
);
1242 /* Make sure the new group has a libmap entry. */
1243 if (board
->libmap
&& board
->libmap_init_groups
)
1244 libmap_group_init(board
->libmap
, board
, coord
, color
);
1247 board
->last_move2
= board
->last_move
;
1248 board
->last_move
= *m
;
1250 board_hash_update(board
, coord
, color
);
1251 board_symmetry_update(board
, &board
->symmetry
, coord
);
1252 struct move ko
= { pass
, S_NONE
};
1255 check_pat3_consistency(board
, coord
);
1260 /* We played in an eye-like shape. Either we capture at least one of the eye
1261 * sides in the process of playing, or return -1. */
1262 static int profiling_noinline
1263 board_play_in_eye(struct board
*board
, struct move
*m
, int f
)
1265 coord_t coord
= m
->coord
;
1266 enum stone color
= m
->color
;
1267 /* Check ko: Capture at a position of ko capture one move ago */
1268 if (unlikely(color
== board
->ko
.color
&& coord
== board
->ko
.coord
)) {
1270 fprintf(stderr
, "board_check: ko at %d,%d color %d\n", coord_x(coord
, board
), coord_y(coord
, board
), color
);
1272 } else if (DEBUGL(6)) {
1273 fprintf(stderr
, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
1274 color
, coord_x(coord
, board
), coord_y(coord
, board
),
1275 board
->ko
.color
, coord_x(board
->ko
.coord
, board
), coord_y(board
->ko
.coord
, board
));
1278 struct move ko
= { pass
, S_NONE
};
1280 int captured_groups
= 0;
1282 foreach_neighbor(board
, coord
, {
1283 group_t g
= group_at(board
, c
);
1285 fprintf(stderr
, "board_check: group %d has %d libs\n",
1286 g
, board_group_info(board
, g
).libs
);
1287 captured_groups
+= (board_group_info(board
, g
).libs
== 1);
1290 if (likely(captured_groups
== 0)) {
1293 board_print(board
, stderr
);
1294 fprintf(stderr
, "board_check: one-stone suicide\n");
1300 /* We _will_ for sure capture something. */
1301 assert(trait_at(board
, coord
, color
).cap
> 0);
1302 #ifdef BOARD_TRAIT_SAFE
1303 assert(trait_at(board
, coord
, color
).safe
== board_trait_safe(board
, coord
, color
));
1307 board
->f
[f
] = board
->f
[--board
->flen
];
1309 fprintf(stderr
, "popping free move [%d->%d]: %d\n", board
->flen
, f
, board
->f
[f
]);
1312 coord_t cap_at
= pass
;
1313 foreach_neighbor(board
, coord
, {
1314 inc_neighbor_count_at(board
, c
, color
);
1315 /* Originally, this could not have changed any trait
1316 * since no neighbors were S_NONE, however by now some
1317 * of them might be removed from the board. */
1318 board_trait_queue(board
, c
);
1320 group_t group
= group_at(board
, c
);
1324 board_group_rmlib(board
, group
, coord
);
1326 fprintf(stderr
, "board_play_raw: reducing libs for group %d\n",
1329 if (board_group_captured(board
, group
)) {
1330 ko_caps
+= board_group_capture(board
, group
);
1335 ko
.color
= stone_other(color
);
1336 ko
.coord
= cap_at
; // unique
1337 board
->last_ko
= ko
;
1338 board
->last_ko_age
= board
->moves
;
1340 fprintf(stderr
, "guarding ko at %d,%s\n", ko
.color
, coord2sstr(ko
.coord
, board
));
1343 board_at(board
, coord
) = color
;
1344 group_t group
= new_group(board
, coord
);
1346 /* Make sure the new group has a libmap entry. */
1347 if (board
->libmap
&& board
->libmap_init_groups
)
1348 libmap_group_init(board
->libmap
, board
, coord
, color
);
1350 board
->last_move2
= board
->last_move
;
1351 board
->last_move
= *m
;
1353 board_hash_update(board
, coord
, color
);
1354 board_hash_commit(board
);
1355 board_traits_recompute(board
);
1356 board_symmetry_update(board
, &board
->symmetry
, coord
);
1359 check_pat3_consistency(board
, coord
);
1364 static int __attribute__((flatten
))
1365 board_play_f(struct board
*board
, struct move
*m
, int f
)
1368 fprintf(stderr
, "board_play(%s): ---- Playing %d,%d\n", coord2sstr(m
->coord
, board
), coord_x(m
->coord
, board
), coord_y(m
->coord
, board
));
1370 if (likely(!board_is_eyelike(board
, m
->coord
, stone_other(m
->color
)))) {
1371 /* NOT playing in an eye. Thus this move has to succeed. (This
1372 * is thanks to New Zealand rules. Otherwise, multi-stone
1373 * suicide might fail.) */
1374 group_t group
= board_play_outside(board
, m
, f
);
1375 if (unlikely(board_group_captured(board
, group
))) {
1376 board_group_capture(board
, group
);
1378 board_hash_commit(board
);
1379 board_traits_recompute(board
);
1382 return board_play_in_eye(board
, m
, f
);
1387 board_play(struct board
*board
, struct move
*m
)
1389 if (unlikely(is_pass(m
->coord
) || is_resign(m
->coord
))) {
1390 if (is_pass(m
->coord
) && board
->rules
== RULES_SIMING
) {
1391 /* On pass, the player gives a pass stone
1392 * to the opponent. */
1393 board
->captures
[stone_other(m
->color
)]++;
1395 struct move nomove
= { pass
, S_NONE
};
1397 board
->last_move4
= board
->last_move3
;
1398 board
->last_move3
= board
->last_move2
;
1399 board
->last_move2
= board
->last_move
;
1400 board
->last_move
= *m
;
1405 for (f
= 0; f
< board
->flen
; f
++)
1406 if (board
->f
[f
] == m
->coord
)
1407 return board_play_f(board
, m
, f
);
1410 fprintf(stderr
, "board_check: stone exists\n");
1414 /* Undo, supported only for pass moves. This form of undo is required by KGS
1415 * to settle disputes on dead groups. (Undo of real moves would be more complex
1416 * particularly for capturing moves.) */
1417 int board_undo(struct board
*board
)
1419 if (!is_pass(board
->last_move
.coord
))
1421 if (board
->rules
== RULES_SIMING
) {
1422 /* Return pass stone to the passing player. */
1423 board
->captures
[stone_other(board
->last_move
.color
)]--;
1425 board
->last_move
= board
->last_move2
;
1426 board
->last_move2
= board
->last_move3
;
1427 board
->last_move3
= board
->last_move4
;
1428 if (board
->last_ko_age
== board
->moves
)
1429 board
->ko
= board
->last_ko
;
1434 board_try_random_move(struct board
*b
, enum stone color
, coord_t
*coord
, int f
, ppr_permit permit
, void *permit_data
)
1437 struct move m
= { *coord
, color
};
1439 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
));
1440 if (unlikely(board_is_one_point_eye(b
, *coord
, color
)) /* bad idea to play into one, usually */
1441 || !board_is_valid_move(b
, &m
)
1442 || (permit
&& !permit(permit_data
, b
, &m
)))
1444 if (m
.coord
== *coord
) {
1445 return likely(board_play_f(b
, &m
, f
) >= 0);
1447 *coord
= m
.coord
; // permit modified the coordinate
1448 return likely(board_play(b
, &m
) >= 0);
1453 board_play_random(struct board
*b
, enum stone color
, coord_t
*coord
, ppr_permit permit
, void *permit_data
)
1455 if (unlikely(b
->flen
== 0))
1458 int base
= fast_random(b
->flen
), f
;
1459 for (f
= base
; f
< b
->flen
; f
++)
1460 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
1462 for (f
= 0; f
< base
; f
++)
1463 if (board_try_random_move(b
, color
, coord
, f
, permit
, permit_data
))
1468 struct move m
= { pass
, color
};
1474 board_is_false_eyelike(struct board
*board
, coord_t coord
, enum stone eye_color
)
1476 enum stone color_diag_libs
[S_MAX
] = {0, 0, 0, 0};
1478 /* XXX: We attempt false eye detection but we will yield false
1479 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
1481 foreach_diag_neighbor(board
, coord
) {
1482 color_diag_libs
[(enum stone
) board_at(board
, c
)]++;
1483 } foreach_diag_neighbor_end
;
1484 /* For false eye, we need two enemy stones diagonally in the
1485 * middle of the board, or just one enemy stone at the edge
1486 * or in the corner. */
1487 color_diag_libs
[stone_other(eye_color
)] += !!color_diag_libs
[S_OFFBOARD
];
1488 return color_diag_libs
[stone_other(eye_color
)] >= 2;
1492 board_is_one_point_eye(struct board
*board
, coord_t coord
, enum stone eye_color
)
1494 return board_is_eyelike(board
, coord
, eye_color
)
1495 && !board_is_false_eyelike(board
, coord
, eye_color
);
1499 board_get_one_point_eye(struct board
*board
, coord_t coord
)
1501 if (board_is_one_point_eye(board
, coord
, S_WHITE
))
1503 else if (board_is_one_point_eye(board
, coord
, S_BLACK
))
1511 board_fast_score(struct board
*board
)
1514 memset(scores
, 0, sizeof(scores
));
1516 foreach_point(board
) {
1517 enum stone color
= board_at(board
, c
);
1518 if (color
== S_NONE
&& board
->rules
!= RULES_STONES_ONLY
)
1519 color
= board_get_one_point_eye(board
, c
);
1521 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1522 } foreach_point_end
;
1524 return board
->komi
+ (board
->rules
!= RULES_SIMING
? board
->handicap
: 0) + scores
[S_WHITE
] - scores
[S_BLACK
];
1527 /* Owner map: 0: undecided; 1: black; 2: white; 3: dame */
1529 /* One flood-fill iteration; returns true if next iteration
1532 board_tromp_taylor_iter(struct board
*board
, int *ownermap
)
1534 bool needs_update
= false;
1535 foreach_free_point(board
) {
1536 /* Ignore occupied and already-dame positions. */
1537 assert(board_at(board
, c
) == S_NONE
);
1538 if (board
->rules
== RULES_STONES_ONLY
)
1540 if (ownermap
[c
] == 3)
1542 /* Count neighbors. */
1544 foreach_neighbor(board
, c
, {
1547 /* If we have neighbors of both colors, or dame,
1548 * we are dame too. */
1549 if ((nei
[1] && nei
[2]) || nei
[3]) {
1551 /* Speed up the propagation. */
1552 foreach_neighbor(board
, c
, {
1553 if (board_at(board
, c
) == S_NONE
)
1556 needs_update
= true;
1559 /* If we have neighbors of one color, we are owned
1560 * by that color, too. */
1561 if (!ownermap
[c
] && (nei
[1] || nei
[2])) {
1562 int newowner
= nei
[1] ? 1 : 2;
1563 ownermap
[c
] = newowner
;
1564 /* Speed up the propagation. */
1565 foreach_neighbor(board
, c
, {
1566 if (board_at(board
, c
) == S_NONE
&& !ownermap
[c
])
1567 ownermap
[c
] = newowner
;
1569 needs_update
= true;
1572 } foreach_free_point_end
;
1573 return needs_update
;
1576 /* Tromp-Taylor Counting */
1578 board_official_score(struct board
*board
, struct move_queue
*q
)
1581 /* A point P, not colored C, is said to reach C, if there is a path of
1582 * (vertically or horizontally) adjacent points of P's color from P to
1583 * a point of color C.
1585 * A player's score is the number of points of her color, plus the
1586 * number of empty points that reach only her color. */
1588 int ownermap
[board_size2(board
)];
1590 const int o
[4] = {0, 1, 2, 0};
1591 foreach_point(board
) {
1592 ownermap
[c
] = o
[board_at(board
, c
)];
1593 s
[board_at(board
, c
)]++;
1594 } foreach_point_end
;
1597 /* Process dead groups. */
1598 for (unsigned int i
= 0; i
< q
->moves
; i
++) {
1599 foreach_in_group(board
, q
->move
[i
]) {
1600 enum stone color
= board_at(board
, c
);
1601 ownermap
[c
] = o
[stone_other(color
)];
1602 s
[color
]--; s
[stone_other(color
)]++;
1603 } foreach_in_group_end
;
1607 /* We need to special-case empty board. */
1608 if (!s
[S_BLACK
] && !s
[S_WHITE
])
1611 while (board_tromp_taylor_iter(board
, ownermap
))
1612 /* Flood-fill... */;
1615 memset(scores
, 0, sizeof(scores
));
1617 foreach_point(board
) {
1618 assert(board_at(board
, c
) == S_OFFBOARD
|| ownermap
[c
] != 0);
1619 if (ownermap
[c
] == 3)
1621 scores
[ownermap
[c
]]++;
1622 } foreach_point_end
;
1624 return board
->komi
+ (board
->rules
!= RULES_SIMING
? board
->handicap
: 0) + scores
[S_WHITE
] - scores
[S_BLACK
];
1628 board_set_rules(struct board
*board
, char *name
)
1630 if (!strcasecmp(name
, "japanese")) {
1631 board
->rules
= RULES_JAPANESE
;
1632 } else if (!strcasecmp(name
, "chinese")) {
1633 board
->rules
= RULES_CHINESE
;
1634 } else if (!strcasecmp(name
, "aga")) {
1635 board
->rules
= RULES_AGA
;
1636 } else if (!strcasecmp(name
, "new_zealand")) {
1637 board
->rules
= RULES_NEW_ZEALAND
;
1638 } else if (!strcasecmp(name
, "siming") || !strcasecmp(name
, "simplified_ing")) {
1639 board
->rules
= RULES_SIMING
;