1 /* probdist.h must be included before the include goard since we require
2 * proper including order. */
16 struct features_gamma
;
19 /* The board implementation has bunch of optional features.
20 * Turn them on below: */
22 #define WANT_BOARD_C // capturable groups queue
24 //#define BOARD_SIZE 9 // constant board size, allows better optimization
26 //#define BOARD_SPATHASH // incremental patternsp.h hashes
27 #define BOARD_SPATHASH_MAXD 3 // maximal diameter
29 #define BOARD_PAT3 // incremental 3x3 pattern codes
31 //#define BOARD_TRAITS 1 // incremental point traits (see struct btraits)
32 //#define BOARD_GAMMA 1 // incremental probability distribution (requires BOARD_TRAITS, BOARD_PAT3)
35 /* Some engines might normalize their reading and skip symmetrical
36 * moves. We will tell them how can they do it. */
37 struct board_symmetry
{
38 /* Playground is in this rectangle. */
40 /* d == 0: Full rectangle
41 * d == 1: Top triangle */
43 /* General symmetry type. */
44 /* Note that the above is redundant to this, but just provided
45 * for easier usage. */
57 typedef uint64_t hash_t
;
58 #define PRIhash PRIx64
61 /* Note that "group" is only chain of stones that is solidly
62 * connected for us. */
63 typedef coord_t group_t
;
66 /* We keep track of only up to GROUP_KEEP_LIBS; over that, we
68 /* _Combination_ of these two values can make some difference
69 * in performance - fine-tune. */
70 #define GROUP_KEEP_LIBS 10
71 // refill lib[] only when we hit this; this must be at least 2!
72 // Moggy requires at least 3 - see below for semantic impact.
73 #define GROUP_REFILL_LIBS 5
74 coord_t lib
[GROUP_KEEP_LIBS
];
75 /* libs is only LOWER BOUND for the number of real liberties!!!
76 * It denotes only number of items in lib[], thus you can rely
77 * on it to store real liberties only up to <= GROUP_REFILL_LIBS. */
81 struct neighbor_colors
{
86 /* Point traits bitmap; we update this information incrementally,
87 * it can be used e.g. for fast pattern.h features matching. */
89 /* Number of neighbors we can capture. 0=this move is
90 * not capturing, 1..4=this many neighbors we can capture
91 * (can be multiple neighbors of same group). */
93 /* Whether it is SAFE to play here. This is essentially just
94 * cached result of board_safe_to_play(). (Of course the concept
95 * of "safety" is not perfect here, but it's the cheapest
96 * reasonable thing we can do.) */
98 /* Whether we need to re-compute this coordinate; used to
99 * weed out duplicates. Maintained only for S_BLACK. */
104 /* You should treat this struct as read-only. Always call functions below if
105 * you want to change it. */
108 int size
; /* Including S_OFFBOARD margin - see below. */
109 int size2
; /* size^2 */
110 int bits2
; /* ceiling(log2(size2)) */
114 /* The ruleset is currently almost never taken into account;
115 * the board implementation is basically Chinese rules (handicap
116 * stones compensation) w/ suicide (or you can look at it as
117 * New Zealand w/o handi stones compensation), while the engine
118 * enforces no-suicide, making for real Chinese rules. */
120 RULES_CHINESE
, /* default value */
126 /* Iterator offsets for foreach_neighbor*() */
127 int nei8
[8], dnei
[4];
130 struct move last_move
;
131 struct move last_move2
; /* second-to-last move */
132 /* Whether we tried to add a hash twice; board_play*() can
133 * set this, but it will still carry out the move as well! */
134 bool superko_violation
;
136 /* The following two structures are goban maps and are indexed by
137 * coord.pos. The map is surrounded by a one-point margin from
138 * S_OFFBOARD stones in order to speed up some internal loops.
139 * Some of the foreach iterators below might include these points;
140 * you need to handle them yourselves, if you need to. */
142 /* Stones played on the board */
143 enum stone
*b
; /* enum stone */
144 /* Group id the stones are part of; 0 == no group */
146 /* Positions of next stones in the stone group; 0 == last stone */
148 /* Neighboring colors; numbers of neighbors of index color */
149 struct neighbor_colors
*n
;
150 /* Zobrist hash for each position */
152 #ifdef BOARD_SPATHASH
153 /* For spatial hashes, we use only 24 bits. */
154 /* [0] is d==1, we don't keep hash for d==0. */
155 /* We keep hashes for black-to-play ([][0]) and white-to-play
156 * ([][1], reversed stone colors since we match all patterns as
158 uint32_t (*spathash
)[BOARD_SPATHASH_MAXD
][2];
161 /* 3x3 pattern code for each position; see pattern3.h for encoding
162 * specification. The information is only valid for empty points. */
166 /* Incrementally matched point traits information, black-to-play
167 * ([][0]) and white-to-play ([][1]). */
168 /* The information is only valid for empty points. */
169 struct btraits (*t
)[2];
172 /* Relative probabilities of moves being played next, computed by
173 * multiplying gammas of the appropriate pattern features based on
174 * pat3 and traits (see pattern.h). The probability distribution
175 * is maintained over the full board grid. */
176 /* - Always invalid moves are guaranteed to have zero probability.
177 * - Self-eye-filling moves will always have zero probability.
178 * - Ko-prohibited moves might have non-zero probability.
179 * - FEAT_CONTIGUITY is not accounted for in the probability. */
180 struct probdist prob
[2];
182 /* Cached information on x-y coordinates so that we avoid division. */
185 /* Group information - indexed by gid (which is coord of base group stone) */
188 /* Positions of free positions - queue (not map) */
189 /* Note that free position here is any valid move; including single-point eyes!
190 * However, pass is not included. */
191 coord_t
*f
; int flen
;
194 /* Queue of capturable groups */
195 group_t
*c
; int clen
;
199 /* Queue of positions that need their traits updated */
200 coord_t
*tq
; int tqlen
;
203 /* Symmetry information */
204 struct board_symmetry symmetry
;
206 /* Last ko played on the board. */
213 /* Engine-specific state; persistent through board development,
214 * is reset only at clear_board. */
217 /* Playout-specific state; persistent through board development,
218 * but its lifetime is maintained in play_random_game(); it should
219 * not be set outside of it. */
223 /* Gamma values for probability distribution; user must setup
224 * this pointer before any move is played, using board_gamma_set(). */
225 struct features_gamma
*gamma
;
226 /* Whether to compute the 'safe' trait using board_safe_to_play()
227 * (false) or is_bad_selfatari() (true, much slower). */
228 bool precise_selfatari
;
232 /* --- PRIVATE DATA --- */
234 /* For superko check: */
236 /* Board "history" - hashes encountered. Size of the hash should be
237 * >> board_size^2. */
238 #define history_hash_bits 12
239 #define history_hash_mask ((1 << history_hash_bits) - 1)
240 #define history_hash_prev(i) ((i - 1) & history_hash_mask)
241 #define history_hash_next(i) ((i + 1) & history_hash_mask)
242 hash_t history_hash
[1 << history_hash_bits
];
243 /* Hash of current board position. */
248 /* Avoid unused variable warnings */
249 #define board_size(b_) (((b_) == (b_)) ? BOARD_SIZE + 2 : 0)
250 #define board_size2(b_) (board_size(b_) * board_size(b_))
252 #define board_size(b_) ((b_)->size)
253 #define board_size2(b_) ((b_)->size2)
257 # define board_bits2(b_) 9
258 #elif BOARD_SIZE == 13
259 # define board_bits2(b_) 8
260 #elif BOARD_SIZE == 9
261 # define board_bits2(b_) 7
263 # define board_bits2(b_) ((b_)->bits2)
266 #define board_at(b_, c) ((b_)->b[c])
267 #define board_atxy(b_, x, y) ((b_)->b[(x) + board_size(b_) * (y)])
269 #define group_at(b_, c) ((b_)->g[c])
270 #define group_atxy(b_, x, y) ((b_)->g[(x) + board_size(b_) * (y)])
272 /* Warning! Neighbor count is kept up-to-date for S_NONE! */
273 #define neighbor_count_at(b_, coord, color) ((b_)->n[coord].colors[(enum stone) color])
274 #define set_neighbor_count_at(b_, coord, color, count) (neighbor_count_at(b_, coord, color) = (count))
275 #define inc_neighbor_count_at(b_, coord, color) (neighbor_count_at(b_, coord, color)++)
276 #define dec_neighbor_count_at(b_, coord, color) (neighbor_count_at(b_, coord, color)--)
277 #define immediate_liberty_count(b_, coord) (4 - neighbor_count_at(b_, coord, S_BLACK) - neighbor_count_at(b_, coord, S_WHITE) - neighbor_count_at(b_, coord, S_OFFBOARD))
279 #define trait_at(b_, coord, color) (b_)->t[coord][(color) - 1]
281 #define groupnext_at(b_, c) ((b_)->p[c])
282 #define groupnext_atxy(b_, x, y) ((b_)->p[(x) + board_size(b_) * (y)])
284 #define group_base(g_) (g_)
285 #define board_group_info(b_, g_) ((b_)->gi[(g_)])
286 #define board_group_captured(b_, g_) (board_group_info(b_, g_).libs == 0)
287 #define group_is_onestone(b_, g_) (groupnext_at(b_, group_base(g_)) == 0)
289 #define hash_at(b_, coord, color) ((b_)->h[((color) == S_BLACK ? board_size2(b_) : 0) + coord])
291 struct board
*board_init(void);
292 struct board
*board_copy(struct board
*board2
, struct board
*board1
);
293 void board_done_noalloc(struct board
*board
);
294 void board_done(struct board
*board
);
295 /* size here is without the S_OFFBOARD margin. */
296 void board_resize(struct board
*board
, int size
);
297 void board_clear(struct board
*board
);
300 typedef char *(*board_cprint
)(struct board
*b
, coord_t c
, char *s
, char *end
);
301 void board_print(struct board
*board
, FILE *f
);
302 void board_print_custom(struct board
*board
, FILE *f
, board_cprint cprint
);
304 /* Place given handicap on the board; coordinates are printed to f. */
305 void board_handicap(struct board
*board
, int stones
, FILE *f
);
307 /* Returns group id, 0 on allowed suicide, pass or resign, -1 on error */
308 int board_play(struct board
*board
, struct move
*m
);
309 /* Like above, but plays random move; the move coordinate is recorded
310 * to *coord. This method will never fill your own eye. pass is played
311 * when no move can be played. You can impose extra restrictions if you
312 * supply your own permit function; the permit function can also modify
313 * the move coordinate to redirect the move elsewhere. */
314 typedef bool (*ppr_permit
)(void *data
, struct board
*b
, struct move
*m
);
315 void board_play_random(struct board
*b
, enum stone color
, coord_t
*coord
, ppr_permit permit
, void *permit_data
);
317 /* Returns true if given move can be played. */
318 static bool board_is_valid_play(struct board
*b
, enum stone color
, coord_t coord
);
319 static bool board_is_valid_move(struct board
*b
, struct move
*m
);
320 /* Returns true if ko was just taken. */
321 static bool board_playing_ko_threat(struct board
*b
);
322 /* Returns 0 or ID of neighboring group in atari. */
323 static group_t
board_get_atari_neighbor(struct board
*b
, coord_t coord
, enum stone group_color
);
324 /* Returns true if the move is not obvious self-atari. */
325 static bool board_safe_to_play(struct board
*b
, coord_t coord
, enum stone color
);
327 /* Adjust symmetry information as if given coordinate has been played. */
328 void board_symmetry_update(struct board
*b
, struct board_symmetry
*symmetry
, coord_t c
);
329 /* Associate a set of feature gamma values (for pd building) with the board. */
330 void board_gamma_set(struct board
*b
, struct features_gamma
*gamma
, bool precise_selfatari
);
331 /* Force re-compute of a probability distribution item. */
332 void board_gamma_update(struct board
*b
, coord_t coord
, enum stone color
);
334 /* Returns true if given coordinate has all neighbors of given color or the edge. */
335 static bool board_is_eyelike(struct board
*board
, coord_t coord
, enum stone eye_color
);
336 /* Returns true if given coordinate could be a false eye; this check makes
337 * sense only if you already know the coordinate is_eyelike(). */
338 bool board_is_false_eyelike(struct board
*board
, coord_t coord
, enum stone eye_color
);
339 /* Returns true if given coordinate is a 1-pt eye (checks against false eyes, or
340 * at least tries to). */
341 bool board_is_one_point_eye(struct board
*board
, coord_t c
, enum stone eye_color
);
342 /* Returns color of a 1pt eye owner, S_NONE if not an eye. */
343 enum stone
board_get_one_point_eye(struct board
*board
, coord_t c
);
345 /* board_official_score() is the scoring method for yielding score suitable
346 * for external presentation. For fast scoring of entirely filled boards
347 * (e.g. playouts), use board_fast_score(). */
348 /* Positive: W wins */
349 /* Compare number of stones + 1pt eyes. */
350 float board_fast_score(struct board
*board
);
351 /* Tromp-Taylor scoring, assuming given groups are actually dead. */
353 float board_official_score(struct board
*board
, struct move_queue
*mq
);
357 #define foreach_point(board_) \
360 for (; c < board_size(board_) * board_size(board_); c++)
361 #define foreach_point_and_pass(board_) \
364 for (; c < board_size(board_) * board_size(board_); c++)
365 #define foreach_point_end \
368 #define foreach_in_group(board_, group_) \
370 struct board *board__ = board_; \
371 coord_t c = group_base(group_); \
372 coord_t c2 = c; c2 = groupnext_at(board__, c2); \
374 #define foreach_in_group_end \
375 c = c2; c2 = groupnext_at(board__, c2); \
379 /* NOT VALID inside of foreach_point() or another foreach_neighbor(), or rather
380 * on S_OFFBOARD coordinates. */
381 #define foreach_neighbor(board_, coord_, loop_body) \
383 struct board *board__ = board_; \
384 coord_t coord__ = coord_; \
386 c = coord__ - 1; do { loop_body } while (0); \
387 c = coord__ - board_size(board__); do { loop_body } while (0); \
388 c = coord__ + 1; do { loop_body } while (0); \
389 c = coord__ + board_size(board__); do { loop_body } while (0); \
392 #define foreach_8neighbor(board_, coord_) \
395 coord_t c = (coord_); \
396 for (fn__i = 0; fn__i < 8; fn__i++) { \
397 c += (board_)->nei8[fn__i];
398 #define foreach_8neighbor_end \
402 #define foreach_diag_neighbor(board_, coord_) \
405 coord_t c = (coord_); \
406 for (fn__i = 0; fn__i < 4; fn__i++) { \
407 c += (board_)->dnei[fn__i];
408 #define foreach_diag_neighbor_end \
414 board_is_eyelike(struct board
*board
, coord_t coord
, enum stone eye_color
)
416 return (neighbor_count_at(board
, coord
, eye_color
)
417 + neighbor_count_at(board
, coord
, S_OFFBOARD
)) == 4;
421 board_is_valid_play(struct board
*board
, enum stone color
, coord_t coord
)
423 if (board_at(board
, coord
) != S_NONE
)
425 if (!board_is_eyelike(board
, coord
, stone_other(color
)))
427 /* Play within {true,false} eye-ish formation */
428 if (board
->ko
.coord
== coord
&& board
->ko
.color
== color
)
431 /* XXX: Disallows suicide. */
432 return trait_at(board
, coord
, color
).cap
> 0;
434 int groups_in_atari
= 0;
435 foreach_neighbor(board
, coord
, {
436 group_t g
= group_at(board
, c
);
437 groups_in_atari
+= (board_group_info(board
, g
).libs
== 1);
439 return !!groups_in_atari
;
444 board_is_valid_move(struct board
*board
, struct move
*m
)
446 return board_is_valid_play(board
, m
->color
, m
->coord
);
450 board_playing_ko_threat(struct board
*b
)
452 return !is_pass(b
->ko
.coord
);
455 static inline group_t
456 board_get_atari_neighbor(struct board
*b
, coord_t coord
, enum stone group_color
)
459 if (!trait_at(b
, coord
, stone_other(group_color
)).cap
) return 0;
461 foreach_neighbor(b
, coord
, {
462 group_t g
= group_at(b
, c
);
463 if (g
&& board_at(b
, c
) == group_color
&& board_group_info(b
, g
).libs
== 1)
465 /* We return first match. */
471 board_safe_to_play(struct board
*b
, coord_t coord
, enum stone color
)
473 /* number of free neighbors */
474 int libs
= immediate_liberty_count(b
, coord
);
479 /* number of capturable enemy groups */
480 if (trait_at(b
, coord
, color
).cap
> 0)
481 return true; // XXX: We don't account for snapback.
482 /* number of non-capturable friendly groups */
483 int noncap_ours
= neighbor_count_at(b
, coord
, color
) - trait_at(b
, coord
, stone_other(color
)).cap
;
489 /* ok, but we need to check if they don't have just two libs. */
491 foreach_neighbor(b
, coord
, {
493 if (board_at(b
, c
) == stone_other(color
) && board_group_info(b
, group_at(b
, c
)).libs
== 1)
494 return true; // can capture; no snapback check
496 if (board_at(b
, c
) != color
) continue;
497 group_t g
= group_at(b
, c
);
498 if (board_group_info(b
, g
).libs
== 1) continue; // in atari
499 if (board_group_info(b
, g
).libs
== 2) { // two liberties
500 if (libs
> 0) return true; // we already have one real liberty
501 // get the other liberty
502 coord_t lib
= board_group_info(b
, g
).lib
[0];
503 if (lib
== coord
) lib
= board_group_info(b
, g
).lib
[0];
504 /* we might be connecting two 2-lib groups, which is ok;
505 * so remember the other liberty and just make sure it's
506 * not the same one */
507 if (onelib
>= 0 && lib
!= onelib
) return true;
514 // no good support group