11 #include "patternsp.h"
12 #include "patternprob.h"
13 #include "tactics/ladder.h"
14 #include "tactics/selfatari.h"
15 #include "tactics/util.h"
17 #define CAPTURE_COUNTSTONES_MAX ((1 << CAPTURE_COUNTSTONES_PAYLOAD_SIZE) - 1)
20 struct pattern_config DEFAULT_PATTERN_CONFIG
= {
23 .spat_min
= 3, .spat_max
= MAX_PATTERN_DIST
,
29 pattern_spec PATTERN_SPEC_MATCH_DEFAULT
= {
32 [FEAT_SELFATARI
] = ~0,
35 [FEAT_CONTIGUITY
] = 0,
39 static const struct feature_info
{
42 } features
[FEAT_MAX
] = {
43 [FEAT_CAPTURE
] = { .name
= "capture", .payloads
= 64 * (CAPTURE_COUNTSTONES_MAX
+ 1) },
44 [FEAT_AESCAPE
] = { .name
= "atariescape", .payloads
= 16 },
45 [FEAT_SELFATARI
] = { .name
= "selfatari", .payloads
= 4 },
46 [FEAT_ATARI
] = { .name
= "atari", .payloads
= 4 },
47 [FEAT_BORDER
] = { .name
= "border", .payloads
= -1 },
48 [FEAT_CONTIGUITY
] = { .name
= "cont", .payloads
= 2 },
49 [FEAT_SPATIAL
] = { .name
= "s", .payloads
= -1 },
53 feature2str(char *str
, struct feature
*f
)
55 return str
+ sprintf(str
+ strlen(str
), "%s:%d", features
[f
->id
].name
, f
->payload
);
59 str2feature(char *str
, struct feature
*f
)
61 while (isspace(*str
)) str
++;
63 int unsigned flen
= strcspn(str
, ":");
64 for (unsigned int i
= 0; i
< sizeof(features
)/sizeof(features
[0]); i
++)
65 if (strlen(features
[i
].name
) == flen
&& !strncmp(features
[i
].name
, str
, flen
)) {
69 fprintf(stderr
, "invalid featurespec: %s[%d]\n", str
, flen
);
74 f
->payload
= strtoull(str
, &str
, 10);
79 feature_name(enum feature_id f
)
81 return features
[f
].name
;
85 feature_payloads(struct pattern_config
*pc
, enum feature_id f
)
89 assert(features
[f
].payloads
< 0);
90 return pc
->spat_dict
->nspatials
;
92 assert(features
[f
].payloads
< 0);
93 return pc
->bdist_max
+ 1;
95 assert(features
[f
].payloads
> 0);
96 return features
[f
].payloads
;
102 patterns_init(struct pattern_setup
*pat
, char *arg
, bool will_append
, bool load_prob
)
104 char *pdict_file
= NULL
;
106 memset(pat
, 0, sizeof(*pat
));
108 pat
->pc
= DEFAULT_PATTERN_CONFIG
;
109 pat
->pc
.spat_dict
= spatial_dict_init(will_append
, !load_prob
);
111 memcpy(&pat
->ps
, PATTERN_SPEC_MATCH_DEFAULT
, sizeof(pattern_spec
));
114 char *optspec
, *next
= arg
;
117 next
+= strcspn(next
, ":");
118 if (*next
) { *next
++ = 0; } else { *next
= 0; }
120 char *optname
= optspec
;
121 char *optval
= strchr(optspec
, '=');
122 if (optval
) *optval
++ = 0;
124 /* See pattern.h:pattern_config for description and
125 * pattern.c:DEFAULT_PATTERN_CONFIG for default values
126 * of the following options. */
127 if (!strcasecmp(optname
, "bdist_max") && optval
) {
128 pat
->pc
.bdist_max
= atoi(optval
);
129 } else if (!strcasecmp(optname
, "spat_min") && optval
) {
130 pat
->pc
.spat_min
= atoi(optval
);
131 } else if (!strcasecmp(optname
, "spat_max") && optval
) {
132 pat
->pc
.spat_max
= atoi(optval
);
133 } else if (!strcasecmp(optname
, "spat_largest")) {
134 pat
->pc
.spat_largest
= !optval
|| atoi(optval
);
136 } else if (!strcasecmp(optname
, "pdict_file") && optval
) {
140 fprintf(stderr
, "patterns: Invalid argument %s or missing value\n", optname
);
146 if (load_prob
&& pat
->pc
.spat_dict
) {
147 pat
->pd
= pattern_pdict_init(pdict_file
, &pat
->pc
);
152 /* pattern_spec helpers */
153 #define PS_ANY(F) (ps[FEAT_ ## F] & (1 << PF_MATCH))
154 #define PS_PF(F, P) (ps[FEAT_ ## F] & (1 << PF_ ## F ## _ ## P))
156 static struct feature
*
157 pattern_match_capture(struct pattern_config
*pc
, pattern_spec ps
,
158 struct pattern
*p
, struct feature
*f
,
159 struct board
*b
, struct move
*m
)
161 f
->id
= FEAT_CAPTURE
; f
->payload
= 0;
163 if (!trait_at(b
, m
->coord
, m
->color
).cap
)
166 if ((ps
[FEAT_CAPTURE
] & ~(1<<PF_CAPTURE_1STONE
| 1<<PF_CAPTURE_TRAPPED
| 1<<PF_CAPTURE_CONNECTION
)) == 1<<PF_MATCH
) {
167 if (PS_PF(CAPTURE
, 1STONE
))
168 f
->payload
|= (trait_at(b
, m
->coord
, m
->color
).cap1
== trait_at(b
, m
->coord
, m
->color
).cap
) << PF_CAPTURE_1STONE
;
169 if (PS_PF(CAPTURE
, TRAPPED
))
170 f
->payload
|= (!trait_at(b
, m
->coord
, stone_other(m
->color
)).safe
) << PF_CAPTURE_TRAPPED
;
171 if (PS_PF(CAPTURE
, CONNECTION
))
172 f
->payload
|= (trait_at(b
, m
->coord
, m
->color
).cap
< neighbor_count_at(b
, m
->coord
, stone_other(m
->color
))) << PF_CAPTURE_CONNECTION
;
176 /* We need to know details, so we still have to go through
180 /* We look at neighboring groups we could capture, and also if the
181 * opponent could save them. */
182 /* This is very similar in spirit to board_safe_to_play(), and almost
183 * a color inverse of pattern_match_aescape(). */
185 /* Whether an escape move would be safe for the opponent. */
188 int extra_libs
= 0, connectable_groups
= 0;
189 bool onestone
= false, multistone
= false;
190 int captured_stones
= 0;
192 foreach_neighbor(b
, m
->coord
, {
193 if (board_at(b
, c
) != stone_other(m
->color
)) {
194 if (board_at(b
, c
) == S_NONE
)
195 extra_libs
++; // free point
196 else if (board_at(b
, c
) == m
->color
&& board_group_info(b
, group_at(b
, c
)).libs
== 1)
197 extra_libs
+= 2; // capturable enemy group
201 group_t g
= group_at(b
, c
); assert(g
);
202 if (board_group_info(b
, g
).libs
> 1) {
203 connectable_groups
++;
204 if (board_group_info(b
, g
).libs
> 2) {
205 extra_libs
+= 2; // connected out
207 /* This is a bit tricky; we connect our 2-lib
208 * group to another 2-lib group, which counts
209 * as one liberty, but only if the other lib
210 * is not shared too. */
212 onelib
= board_group_other_lib(b
, g
, c
);
216 extra_libs
--; // take that back
227 if (PS_PF(CAPTURE
, LADDER
))
228 f
->payload
|= is_ladder(b
, m
->coord
, g
, true) << PF_CAPTURE_LADDER
;
229 /* TODO: is_ladder() is too conservative in some
230 * very obvious situations, look at complete.gtp. */
232 if (PS_PF(CAPTURE
, ATARIDEF
))
233 foreach_in_group(b
, g
) {
234 foreach_neighbor(b
, c
, {
235 assert(board_at(b
, c
) != S_NONE
|| c
== m
->coord
);
236 if (board_at(b
, c
) != m
->color
)
238 group_t g
= group_at(b
, c
);
239 if (!g
|| board_group_info(b
, g
).libs
!= 1)
241 /* A neighboring group of ours is in atari. */
242 f
->payload
|= 1 << PF_CAPTURE_ATARIDEF
;
244 } foreach_in_group_end
;
246 if (PS_PF(CAPTURE
, KO
)
247 && group_is_onestone(b
, g
)
248 && neighbor_count_at(b
, m
->coord
, stone_other(m
->color
))
249 + neighbor_count_at(b
, m
->coord
, S_OFFBOARD
) == 4)
250 f
->payload
|= 1 << PF_CAPTURE_KO
;
252 if (PS_PF(CAPTURE
, COUNTSTONES
)
253 && captured_stones
< CAPTURE_COUNTSTONES_MAX
)
254 captured_stones
+= group_stone_count(b
, g
, CAPTURE_COUNTSTONES_MAX
- captured_stones
);
256 if (group_is_onestone(b
, g
))
263 if (PS_PF(CAPTURE
, 1STONE
))
264 f
->payload
|= (onestone
&& !multistone
) << PF_CAPTURE_1STONE
;
265 if (PS_PF(CAPTURE
, TRAPPED
))
266 f
->payload
|= (extra_libs
< 2) << PF_CAPTURE_TRAPPED
;
267 if (PS_PF(CAPTURE
, CONNECTION
))
268 f
->payload
|= (connectable_groups
> 0) << PF_CAPTURE_CONNECTION
;
269 if (PS_PF(CAPTURE
, COUNTSTONES
))
270 f
->payload
|= captured_stones
<< PF_CAPTURE_COUNTSTONES
;
276 static struct feature
*
277 pattern_match_aescape(struct pattern_config
*pc
, pattern_spec ps
,
278 struct pattern
*p
, struct feature
*f
,
279 struct board
*b
, struct move
*m
)
281 f
->id
= FEAT_AESCAPE
; f
->payload
= 0;
283 if (!trait_at(b
, m
->coord
, stone_other(m
->color
)).cap
)
285 /* Opponent can capture something! */
286 if ((ps
[FEAT_AESCAPE
] & ~(1<<PF_AESCAPE_1STONE
| 1<<PF_AESCAPE_TRAPPED
| 1<<PF_AESCAPE_CONNECTION
)) == 1<<PF_MATCH
) {
287 if (PS_PF(AESCAPE
, 1STONE
))
288 f
->payload
|= (trait_at(b
, m
->coord
, stone_other(m
->color
)).cap1
== trait_at(b
, m
->coord
, stone_other(m
->color
)).cap
) << PF_AESCAPE_1STONE
;
289 if (PS_PF(AESCAPE
, TRAPPED
))
290 f
->payload
|= (!trait_at(b
, m
->coord
, m
->color
).safe
) << PF_AESCAPE_TRAPPED
;
291 if (PS_PF(AESCAPE
, CONNECTION
))
292 f
->payload
|= (trait_at(b
, m
->coord
, stone_other(m
->color
)).cap
< neighbor_count_at(b
, m
->coord
, m
->color
)) << PF_AESCAPE_CONNECTION
;
296 /* We need to know details, so we still have to go through
300 /* Find if a neighboring group of ours is in atari, AND that we provide
301 * a liberty to connect out. XXX: No connect-and-die check. */
302 /* This is very similar in spirit to board_safe_to_play(). */
303 group_t in_atari
= -1;
305 int extra_libs
= 0, connectable_groups
= 0;
306 bool onestone
= false, multistone
= false;
308 foreach_neighbor(b
, m
->coord
, {
309 if (board_at(b
, c
) != m
->color
) {
310 if (board_at(b
, c
) == S_NONE
)
311 extra_libs
++; // free point
312 else if (board_at(b
, c
) == stone_other(m
->color
) && board_group_info(b
, group_at(b
, c
)).libs
== 1) {
313 extra_libs
+= 2; // capturable enemy group
314 /* XXX: We just consider this move safe
315 * unconditionally. */
319 group_t g
= group_at(b
, c
); assert(g
);
320 if (board_group_info(b
, g
).libs
> 1) {
321 connectable_groups
++;
322 if (board_group_info(b
, g
).libs
> 2) {
323 extra_libs
+= 2; // connected out
325 /* This is a bit tricky; we connect our 2-lib
326 * group to another 2-lib group, which counts
327 * as one liberty, but only if the other lib
328 * is not shared too. */
330 onelib
= board_group_other_lib(b
, g
, c
);
334 extra_libs
--; // take that back
345 if (PS_PF(AESCAPE
, LADDER
))
346 f
->payload
|= is_ladder(b
, m
->coord
, g
, true) << PF_AESCAPE_LADDER
;
347 /* TODO: is_ladder() is too conservative in some
348 * very obvious situations, look at complete.gtp. */
350 if (group_is_onestone(b
, g
))
357 if (PS_PF(AESCAPE
, 1STONE
))
358 f
->payload
|= (onestone
&& !multistone
) << PF_AESCAPE_1STONE
;
359 if (PS_PF(AESCAPE
, TRAPPED
))
360 f
->payload
|= (extra_libs
< 2) << PF_AESCAPE_TRAPPED
;
361 if (PS_PF(AESCAPE
, CONNECTION
))
362 f
->payload
|= (connectable_groups
> 0) << PF_AESCAPE_CONNECTION
;
368 static struct feature
*
369 pattern_match_atari(struct pattern_config
*pc
, pattern_spec ps
,
370 struct pattern
*p
, struct feature
*f
,
371 struct board
*b
, struct move
*m
)
373 foreach_neighbor(b
, m
->coord
, {
374 if (board_at(b
, c
) != stone_other(m
->color
))
376 group_t g
= group_at(b
, c
);
377 if (!g
|| board_group_info(b
, g
).libs
!= 2)
381 f
->id
= FEAT_ATARI
; f
->payload
= 0;
383 if (PS_PF(ATARI
, LADDER
)) {
384 /* Opponent will escape by the other lib. */
385 coord_t lib
= board_group_other_lib(b
, g
, m
->coord
);
386 /* TODO: is_ladder() is too conservative in some
387 * very obvious situations, look at complete.gtp. */
388 f
->payload
|= wouldbe_ladder(b
, g
, lib
, m
->coord
, stone_other(m
->color
)) << PF_ATARI_LADDER
;
391 if (PS_PF(ATARI
, KO
) && !is_pass(b
->ko
.coord
))
392 f
->payload
|= 1 << PF_ATARI_KO
;
399 #ifndef BOARD_SPATHASH
400 #undef BOARD_SPATHASH_MAXD
401 #define BOARD_SPATHASH_MAXD 1
404 /* Match spatial features that are too distant to be pre-matched
407 pattern_match_spatial_outer(struct pattern_config
*pc
, pattern_spec ps
,
408 struct pattern
*p
, struct feature
*f
,
409 struct board
*b
, struct move
*m
, hash_t h
)
411 /* We record all spatial patterns black-to-play; simply
412 * reverse all colors if we are white-to-play. */
413 static enum stone bt_black
[4] = { S_NONE
, S_BLACK
, S_WHITE
, S_OFFBOARD
};
414 static enum stone bt_white
[4] = { S_NONE
, S_WHITE
, S_BLACK
, S_OFFBOARD
};
415 enum stone (*bt
)[4] = m
->color
== S_WHITE
? &bt_white
: &bt_black
;
417 for (unsigned int d
= BOARD_SPATHASH_MAXD
+ 1; d
<= pc
->spat_max
; d
++) {
418 /* Recompute missing outer circles:
419 * Go through all points in given distance. */
420 for (unsigned int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
421 ptcoords_at(x
, y
, m
->coord
, b
, j
);
422 h
^= pthashes
[0][j
][(*bt
)[board_atxy(b
, x
, y
)]];
424 if (d
< pc
->spat_min
)
426 /* Record spatial feature, one per distance. */
427 unsigned int sid
= spatial_dict_get(pc
->spat_dict
, d
, h
& spatial_hash_mask
);
429 f
->id
= FEAT_SPATIAL
;
431 if (!pc
->spat_largest
)
433 } /* else not found, ignore */
439 pattern_match_spatial(struct pattern_config
*pc
, pattern_spec ps
,
440 struct pattern
*p
, struct feature
*f
,
441 struct board
*b
, struct move
*m
)
443 /* XXX: This is partially duplicated from spatial_from_board(), but
444 * we build a hash instead of spatial record. */
446 assert(pc
->spat_min
> 0);
449 hash_t h
= pthashes
[0][0][S_NONE
];
450 #ifdef BOARD_SPATHASH
451 bool w_to_play
= m
->color
== S_WHITE
;
452 for (int d
= 2; d
<= BOARD_SPATHASH_MAXD
; d
++) {
453 /* Reuse all incrementally matched data. */
454 h
^= b
->spathash
[m
->coord
][d
- 1][w_to_play
];
455 if (d
< pc
->spat_min
)
457 /* Record spatial feature, one per distance. */
458 unsigned int sid
= spatial_dict_get(pc
->spat_dict
, d
, h
& spatial_hash_mask
);
460 f
->id
= FEAT_SPATIAL
;
462 if (!pc
->spat_largest
)
464 } /* else not found, ignore */
467 assert(BOARD_SPATHASH_MAXD
< 2);
469 if (unlikely(pc
->spat_max
> BOARD_SPATHASH_MAXD
))
470 f
= pattern_match_spatial_outer(pc
, ps
, p
, f
, b
, m
, h
);
471 if (pc
->spat_largest
&& f
->id
== FEAT_SPATIAL
)
478 pattern_match(struct pattern_config
*pc
, pattern_spec ps
,
479 struct pattern
*p
, struct board
*b
, struct move
*m
)
482 struct feature
*f
= &p
->f
[0];
484 /* TODO: We should match pretty much all of these features
487 if (PS_ANY(CAPTURE
)) {
488 f
= pattern_match_capture(pc
, ps
, p
, f
, b
, m
);
491 if (PS_ANY(AESCAPE
)) {
492 f
= pattern_match_aescape(pc
, ps
, p
, f
, b
, m
);
495 if (PS_ANY(SELFATARI
)) {
497 if (PS_PF(SELFATARI
, STUPID
)) {
499 if (!b
->precise_selfatari
)
500 simple
= !trait_at(b
, m
->coord
, m
->color
).safe
;
503 simple
= !board_safe_to_play(b
, m
->coord
, m
->color
);
505 bool thorough
= false;
506 if (PS_PF(SELFATARI
, SMART
)) {
508 if (b
->precise_selfatari
)
509 thorough
= !trait_at(b
, m
->coord
, m
->color
).safe
;
512 thorough
= is_bad_selfatari(b
, m
->color
, m
->coord
);
514 if (simple
|| thorough
) {
515 f
->id
= FEAT_SELFATARI
;
516 f
->payload
= simple
<< PF_SELFATARI_STUPID
;
517 f
->payload
|= thorough
<< PF_SELFATARI_SMART
;
523 f
= pattern_match_atari(pc
, ps
, p
, f
, b
, m
);
526 if (PS_ANY(BORDER
)) {
527 unsigned int bdist
= coord_edge_distance(m
->coord
, b
);
528 if (bdist
<= pc
->bdist_max
) {
535 if (PS_ANY(CONTIGUITY
) && !is_pass(b
->last_move
.coord
)
536 && coord_is_8adjecent(m
->coord
, b
->last_move
.coord
, b
)) {
537 f
->id
= FEAT_CONTIGUITY
;
542 if (PS_ANY(SPATIAL
) && pc
->spat_max
> 0 && pc
->spat_dict
) {
543 f
= pattern_match_spatial(pc
, ps
, p
, f
, b
, m
);
548 pattern2str(char *str
, struct pattern
*p
)
550 str
= stpcpy(str
, "(");
551 for (int i
= 0; i
< p
->n
; i
++) {
552 if (i
> 0) str
= stpcpy(str
, " ");
553 str
= feature2str(str
, &p
->f
[i
]);
555 str
= stpcpy(str
, ")");
560 str2pattern(char *str
, struct pattern
*p
)
563 while (isspace(*str
)) str
++;
565 fprintf(stderr
, "invalid patternspec: %s\n", str
);
569 while (*str
!= ')') {
570 str
= str2feature(str
, &p
->f
[p
->n
++]);