11 #include "patternsp.h"
16 struct pattern_config DEFAULT_PATTERN_CONFIG
= {
17 .spat_min
= 3, .spat_max
= MAX_PATTERN_DIST
,
19 .ldist_min
= 0, .ldist_max
= 256,
20 .mcsims
= 0, /* Unsupported. */
23 struct pattern_config FAST_PATTERN_CONFIG
= {
24 .spat_min
= 3, .spat_max
= 3,
26 .ldist_min
= 0, .ldist_max
= 256,
32 pattern_spec PATTERN_SPEC_MATCHALL
= {
36 [FEAT_SELFATARI
] = ~0,
41 [FEAT_CONTIGUITY
] = 0,
47 /* !!! Note that in order for ELO playout policy to work correctly, this
48 * pattern specification MUST exactly match the features matched by the
49 * BOARD_GAMMA code! You cannot just tinker with this spec freely. */
50 pattern_spec PATTERN_SPEC_MATCHFAST
= {
52 [FEAT_CAPTURE
] = (1<<PF_MATCH
| 1<<PF_CAPTURE_1STONE
| 1<<PF_CAPTURE_TRAPPED
),
53 [FEAT_AESCAPE
] = (1<<PF_MATCH
| 1<<PF_AESCAPE_1STONE
| 1<<PF_AESCAPE_TRAPPED
),
54 [FEAT_SELFATARI
] = (1<<PF_MATCH
| 1<<PF_SELFATARI_STUPID
),
59 [FEAT_CONTIGUITY
] = ~0,
65 static const struct feature_info
{
68 } features
[FEAT_MAX
] = {
69 [FEAT_PASS
] = { .name
= "pass", .payloads
= 2 },
70 [FEAT_CAPTURE
] = { .name
= "capture", .payloads
= 64 },
71 [FEAT_AESCAPE
] = { .name
= "atariescape", .payloads
= 8 },
72 [FEAT_SELFATARI
] = { .name
= "selfatari", .payloads
= 4 },
73 [FEAT_ATARI
] = { .name
= "atari", .payloads
= 4 },
74 [FEAT_BORDER
] = { .name
= "border", .payloads
= -1 },
75 [FEAT_LDIST
] = { .name
= "ldist", .payloads
= -1 },
76 [FEAT_LLDIST
] = { .name
= "lldist", .payloads
= -1 },
77 [FEAT_CONTIGUITY
] = { .name
= "cont", .payloads
= 2 },
78 [FEAT_SPATIAL
] = { .name
= "s", .payloads
= -1 },
79 [FEAT_PATTERN3
] = { .name
= "p", .payloads
= 2<<16 },
80 [FEAT_MCOWNER
] = { .name
= "mcowner", .payloads
= 16 },
84 feature2str(char *str
, struct feature
*f
)
86 return str
+ sprintf(str
+ strlen(str
), "%s:%d", features
[f
->id
].name
, f
->payload
);
90 str2feature(char *str
, struct feature
*f
)
92 while (isspace(*str
)) str
++;
94 int unsigned flen
= strcspn(str
, ":");
95 for (unsigned int i
= 0; i
< sizeof(features
)/sizeof(features
[0]); i
++)
96 if (strlen(features
[i
].name
) == flen
&& !strncmp(features
[i
].name
, str
, flen
)) {
100 fprintf(stderr
, "invalid featurespec: %s[%d]\n", str
, flen
);
105 f
->payload
= strtoull(str
, &str
, 10);
110 feature_name(enum feature_id f
)
112 return features
[f
].name
;
116 feature_payloads(struct pattern_config
*pc
, enum feature_id f
)
120 assert(features
[f
].payloads
< 0);
121 return pc
->spat_dict
->nspatials
;
124 assert(features
[f
].payloads
< 0);
125 return pc
->ldist_max
+ 1;
127 assert(features
[f
].payloads
< 0);
128 return pc
->bdist_max
+ 1;
130 assert(features
[f
].payloads
> 0);
131 return features
[f
].payloads
;
136 /* pattern_spec helpers */
137 #define PS_ANY(F) (ps[FEAT_ ## F] & (1 << PF_MATCH))
138 #define PS_PF(F, P) (ps[FEAT_ ## F] & (1 << PF_ ## F ## _ ## P))
140 static struct feature
*
141 pattern_match_capture(struct pattern_config
*pc
, pattern_spec ps
,
142 struct pattern
*p
, struct feature
*f
,
143 struct board
*b
, struct move
*m
)
145 f
->id
= FEAT_CAPTURE
; f
->payload
= 0;
147 if (!trait_at(b
, m
->coord
, m
->color
).cap
)
150 if (!(ps
[FEAT_CAPTURE
] & ~PATTERN_SPEC_MATCHFAST
[FEAT_CAPTURE
])) {
151 if (PS_PF(CAPTURE
, 1STONE
))
152 f
->payload
|= (trait_at(b
, m
->coord
, m
->color
).cap1
== trait_at(b
, m
->coord
, m
->color
).cap
) << PF_CAPTURE_1STONE
;
153 if (PS_PF(CAPTURE
, TRAPPED
))
154 f
->payload
|= (!trait_at(b
, m
->coord
, stone_other(m
->color
)).safe
) << PF_CAPTURE_TRAPPED
;
158 /* We need to know details, so we still have to go through
162 /* We look at neighboring groups we could capture, and also if the
163 * opponent could save them. */
164 /* This is very similar in spirit to board_safe_to_play(), and almost
165 * a color inverse of pattern_match_aescape(). */
167 /* Whether an escape move would be safe for the opponent. */
171 bool onestone
= false, multistone
= false;
173 foreach_neighbor(b
, m
->coord
, {
174 if (board_at(b
, c
) != stone_other(m
->color
)) {
175 if (board_at(b
, c
) == S_NONE
)
176 extra_libs
++; // free point
177 else if (board_at(b
, c
) == m
->color
&& board_group_info(b
, group_at(b
, c
)).libs
== 1)
178 extra_libs
+= 2; // capturable enemy group
182 group_t g
= group_at(b
, c
); assert(g
);
183 if (board_group_info(b
, g
).libs
> 1) {
184 if (board_group_info(b
, g
).libs
> 2) {
185 extra_libs
+= 2; // connected out
187 /* This is a bit tricky; we connect our 2-lib
188 * group to another 2-lib group, which counts
189 * as one liberty, but only if the other lib
190 * is not shared too. */
192 onelib
= board_group_other_lib(b
, g
, c
);
196 extra_libs
--; // take that back
207 if (PS_PF(CAPTURE
, LADDER
))
208 f
->payload
|= is_ladder(b
, m
->coord
, g
, true, true) << PF_CAPTURE_LADDER
;
209 /* TODO: is_ladder() is too conservative in some
210 * very obvious situations, look at complete.gtp. */
212 /* TODO: PF_CAPTURE_RECAPTURE */
214 if (PS_PF(CAPTURE
, ATARIDEF
))
215 foreach_in_group(b
, g
) {
216 foreach_neighbor(b
, c
, {
217 assert(board_at(b
, c
) != S_NONE
|| c
== m
->coord
);
218 if (board_at(b
, c
) != m
->color
)
220 group_t g
= group_at(b
, c
);
221 if (!g
|| board_group_info(b
, g
).libs
!= 1)
223 /* A neighboring group of ours is in atari. */
224 f
->payload
|= 1 << PF_CAPTURE_ATARIDEF
;
226 } foreach_in_group_end
;
228 if (PS_PF(CAPTURE
, KO
)
229 && group_is_onestone(b
, g
)
230 && neighbor_count_at(b
, m
->coord
, stone_other(m
->color
))
231 + neighbor_count_at(b
, m
->coord
, S_OFFBOARD
) == 4)
232 f
->payload
|= 1 << PF_CAPTURE_KO
;
234 if (group_is_onestone(b
, g
))
241 if (PS_PF(CAPTURE
, 1STONE
))
242 f
->payload
|= (onestone
&& !multistone
) << PF_CAPTURE_1STONE
;
243 if (PS_PF(CAPTURE
, TRAPPED
))
244 f
->payload
|= (extra_libs
< 2) << PF_CAPTURE_TRAPPED
;
250 static struct feature
*
251 pattern_match_aescape(struct pattern_config
*pc
, pattern_spec ps
,
252 struct pattern
*p
, struct feature
*f
,
253 struct board
*b
, struct move
*m
)
255 f
->id
= FEAT_AESCAPE
; f
->payload
= 0;
257 if (!trait_at(b
, m
->coord
, stone_other(m
->color
)).cap
)
259 /* Opponent can capture something! */
260 if (!(ps
[FEAT_AESCAPE
] & ~PATTERN_SPEC_MATCHFAST
[FEAT_AESCAPE
])) {
261 if (PS_PF(AESCAPE
, 1STONE
))
262 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
;
263 if (PS_PF(AESCAPE
, TRAPPED
))
264 f
->payload
|= (!trait_at(b
, m
->coord
, m
->color
).safe
) << PF_AESCAPE_TRAPPED
;
268 /* We need to know details, so we still have to go through
272 /* Find if a neighboring group of ours is in atari, AND that we provide
273 * a liberty to connect out. XXX: No connect-and-die check. */
274 /* This is very similar in spirit to board_safe_to_play(). */
275 group_t in_atari
= -1;
278 bool onestone
= false, multistone
= false;
280 foreach_neighbor(b
, m
->coord
, {
281 if (board_at(b
, c
) != m
->color
) {
282 if (board_at(b
, c
) == S_NONE
)
283 extra_libs
++; // free point
284 else if (board_at(b
, c
) == stone_other(m
->color
) && board_group_info(b
, group_at(b
, c
)).libs
== 1) {
285 extra_libs
+= 2; // capturable enemy group
286 /* XXX: We just consider this move safe
287 * unconditionally. */
291 group_t g
= group_at(b
, c
); assert(g
);
292 if (board_group_info(b
, g
).libs
> 1) {
293 if (board_group_info(b
, g
).libs
> 2) {
294 extra_libs
+= 2; // connected out
296 /* This is a bit tricky; we connect our 2-lib
297 * group to another 2-lib group, which counts
298 * as one liberty, but only if the other lib
299 * is not shared too. */
301 onelib
= board_group_other_lib(b
, g
, c
);
305 extra_libs
--; // take that back
316 if (PS_PF(AESCAPE
, LADDER
))
317 f
->payload
|= is_ladder(b
, m
->coord
, g
, true, true) << PF_AESCAPE_LADDER
;
318 /* TODO: is_ladder() is too conservative in some
319 * very obvious situations, look at complete.gtp. */
321 if (group_is_onestone(b
, g
))
328 if (PS_PF(AESCAPE
, 1STONE
))
329 f
->payload
|= (onestone
&& !multistone
) << PF_AESCAPE_1STONE
;
330 if (PS_PF(AESCAPE
, TRAPPED
))
331 f
->payload
|= (extra_libs
< 2) << PF_AESCAPE_TRAPPED
;
337 static struct feature
*
338 pattern_match_atari(struct pattern_config
*pc
, pattern_spec ps
,
339 struct pattern
*p
, struct feature
*f
,
340 struct board
*b
, struct move
*m
)
342 foreach_neighbor(b
, m
->coord
, {
343 if (board_at(b
, c
) != stone_other(m
->color
))
345 group_t g
= group_at(b
, c
);
346 if (!g
|| board_group_info(b
, g
).libs
!= 2)
350 f
->id
= FEAT_ATARI
; f
->payload
= 0;
352 if (PS_PF(ATARI
, LADDER
)) {
353 /* Opponent will escape by the other lib. */
354 coord_t lib
= board_group_other_lib(b
, g
, m
->coord
);
355 /* TODO: is_ladder() is too conservative in some
356 * very obvious situations, look at complete.gtp. */
357 f
->payload
|= is_ladder(b
, lib
, g
, true, true) << PF_ATARI_LADDER
;
360 if (PS_PF(ATARI
, KO
) && !is_pass(b
->ko
.coord
))
361 f
->payload
|= 1 << PF_ATARI_KO
;
368 #ifndef BOARD_SPATHASH
369 #undef BOARD_SPATHASH_MAXD
370 #define BOARD_SPATHASH_MAXD 1
373 /* Match spatial features that are too distant to be pre-matched
376 pattern_match_spatial_outer(struct pattern_config
*pc
, pattern_spec ps
,
377 struct pattern
*p
, struct feature
*f
,
378 struct board
*b
, struct move
*m
, hash_t h
)
380 /* We record all spatial patterns black-to-play; simply
381 * reverse all colors if we are white-to-play. */
382 static enum stone bt_black
[4] = { S_NONE
, S_BLACK
, S_WHITE
, S_OFFBOARD
};
383 static enum stone bt_white
[4] = { S_NONE
, S_WHITE
, S_BLACK
, S_OFFBOARD
};
384 enum stone (*bt
)[4] = m
->color
== S_WHITE
? &bt_white
: &bt_black
;
386 for (int d
= BOARD_SPATHASH_MAXD
+ 1; d
<= pc
->spat_max
; d
++) {
387 /* Recompute missing outer circles:
388 * Go through all points in given distance. */
389 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
390 ptcoords_at(x
, y
, m
->coord
, b
, j
);
391 h
^= pthashes
[0][j
][(*bt
)[board_atxy(b
, x
, y
)]];
393 if (d
< pc
->spat_min
)
395 /* Record spatial feature, one per distance. */
396 int sid
= spatial_dict_get(pc
->spat_dict
, d
, h
& spatial_hash_mask
);
398 f
->id
= FEAT_SPATIAL
;
401 } /* else not found, ignore */
407 pattern_match_spatial(struct pattern_config
*pc
, pattern_spec ps
,
408 struct pattern
*p
, struct feature
*f
,
409 struct board
*b
, struct move
*m
)
411 /* XXX: This is partially duplicated from spatial_from_board(), but
412 * we build a hash instead of spatial record. */
414 assert(pc
->spat_min
> 0);
416 hash_t h
= pthashes
[0][0][S_NONE
];
417 #ifdef BOARD_SPATHASH
418 bool w_to_play
= m
->color
== S_WHITE
;
419 for (int d
= 2; d
<= BOARD_SPATHASH_MAXD
; d
++) {
420 /* Reuse all incrementally matched data. */
421 h
^= b
->spathash
[m
->coord
][d
- 1][w_to_play
];
422 if (d
< pc
->spat_min
)
424 /* Record spatial feature, one per distance. */
425 int sid
= spatial_dict_get(pc
->spat_dict
, d
, h
& spatial_hash_mask
);
427 f
->id
= FEAT_SPATIAL
;
430 } /* else not found, ignore */
433 assert(BOARD_SPATHASH_MAXD
< 2);
435 if (unlikely(pc
->spat_max
> BOARD_SPATHASH_MAXD
))
436 f
= pattern_match_spatial_outer(pc
, ps
, p
, f
, b
, m
, h
);
442 pattern_match(struct pattern_config
*pc
, pattern_spec ps
,
443 struct pattern
*p
, struct board
*b
, struct move
*m
)
446 struct feature
*f
= &p
->f
[0];
448 /* TODO: We should match pretty much all of these features
451 if (is_pass(m
->coord
)) {
453 f
->id
= FEAT_PASS
; f
->payload
= 0;
454 if (PS_PF(PASS
, LASTPASS
))
455 f
->payload
|= (b
->moves
> 0 && is_pass(b
->last_move
.coord
))
462 if (PS_ANY(CAPTURE
)) {
463 f
= pattern_match_capture(pc
, ps
, p
, f
, b
, m
);
466 if (PS_ANY(AESCAPE
)) {
467 f
= pattern_match_aescape(pc
, ps
, p
, f
, b
, m
);
470 if (PS_ANY(SELFATARI
)) {
472 if (PS_PF(SELFATARI
, STUPID
)) {
474 if (!b
->precise_selfatari
)
475 simple
= !trait_at(b
, m
->coord
, m
->color
).safe
;
478 simple
= !board_safe_to_play(b
, m
->coord
, m
->color
);
480 bool thorough
= false;
481 if (PS_PF(SELFATARI
, SMART
)) {
483 if (b
->precise_selfatari
)
484 thorough
= !trait_at(b
, m
->coord
, m
->color
).safe
;
487 thorough
= is_bad_selfatari(b
, m
->color
, m
->coord
);
489 if (simple
|| thorough
) {
490 f
->id
= FEAT_SELFATARI
;
491 f
->payload
= simple
<< PF_SELFATARI_STUPID
;
492 f
->payload
|= thorough
<< PF_SELFATARI_SMART
;
498 f
= pattern_match_atari(pc
, ps
, p
, f
, b
, m
);
501 if (PS_ANY(BORDER
)) {
502 int bdist
= coord_edge_distance(m
->coord
, b
);
503 if (bdist
<= pc
->bdist_max
) {
510 if (PS_ANY(CONTIGUITY
) && !is_pass(b
->last_move
.coord
)
511 && coord_is_8adjecent(m
->coord
, b
->last_move
.coord
, b
)) {
512 f
->id
= FEAT_CONTIGUITY
;
517 if (PS_ANY(LDIST
) && pc
->ldist_max
> 0 && !is_pass(b
->last_move
.coord
)) {
518 int ldist
= coord_gridcular_distance(m
->coord
, b
->last_move
.coord
, b
);
519 if (pc
->ldist_min
<= ldist
&& ldist
<= pc
->ldist_max
) {
526 if (PS_ANY(LLDIST
) && pc
->ldist_max
> 0 && !is_pass(b
->last_move2
.coord
)) {
527 int lldist
= coord_gridcular_distance(m
->coord
, b
->last_move2
.coord
, b
);
528 if (pc
->ldist_min
<= lldist
&& lldist
<= pc
->ldist_max
) {
535 if (PS_ANY(SPATIAL
) && pc
->spat_max
> 0 && pc
->spat_dict
) {
536 f
= pattern_match_spatial(pc
, ps
, p
, f
, b
, m
);
539 if (PS_ANY(PATTERN3
) && !is_pass(m
->coord
)) {
541 hash3_t pat
= b
->pat3
[m
->coord
];
543 hash3_t pat
= pattern3_hash(b
, m
->coord
);
545 if (m
->color
== S_WHITE
) {
546 /* We work with the pattern3s as black-to-play. */
547 pat
= pattern3_reverse(pat
);
549 f
->id
= FEAT_PATTERN3
;
554 /* FEAT_MCOWNER: TODO */
559 pattern2str(char *str
, struct pattern
*p
)
561 str
= stpcpy(str
, "(");
562 for (int i
= 0; i
< p
->n
; i
++) {
563 if (i
> 0) str
= stpcpy(str
, " ");
564 str
= feature2str(str
, &p
->f
[i
]);
566 str
= stpcpy(str
, ")");
572 /*** Features gamma set */
575 features_gamma_load(struct features_gamma
*fg
, const char *filename
)
577 FILE *f
= fopen(filename
, "r");
580 while (fgets(buf
, 256, f
)) {
583 bufp
= str2feature(bufp
, &f
);
584 while (isspace(*bufp
)) bufp
++;
585 double gamma
= strtod(bufp
, &bufp
);
586 /* Record feature's gamma. */
587 feature_gamma(fg
, &f
, &gamma
);
588 /* In case of 3x3 patterns, record gamma also
589 * for all rotations and transpositions. */
590 if (f
.id
== FEAT_PATTERN3
) {
592 pattern3_transpose(f
.payload
, &transp
);
593 for (int i
= 1; i
< 8; i
++) {
594 f
.payload
= transp
[i
];
595 feature_gamma(fg
, &f
, &gamma
);
597 f
.payload
= transp
[0];
603 const char *features_gamma_filename
= "patterns.gamma";
605 struct features_gamma
*
606 features_gamma_init(struct pattern_config
*pc
, const char *file
)
608 struct features_gamma
*fg
= calloc2(1, sizeof(*fg
));
610 for (int i
= 0; i
< FEAT_MAX
; i
++) {
611 int n
= feature_payloads(pc
, i
);
612 fg
->gamma
[i
] = malloc2(n
* sizeof(fg
->gamma
[0][0]));
613 for (int j
= 0; j
< n
; j
++) {
614 fg
->gamma
[i
][j
] = 1.0f
;
617 features_gamma_load(fg
, file
? file
: features_gamma_filename
);
622 features_gamma_done(struct features_gamma
*fg
)
624 for (int i
= 0; i
< FEAT_MAX
; i
++)