Moggy middle_ladder: Support for turning off middle ladder reading
[pachi/nmclean.git] / pattern.c
blob4bfe66c1271985836afafca151a994127478b76a
1 #define DEBUG
2 #include <assert.h>
3 #include <ctype.h>
4 #include <inttypes.h>
5 #include <stdio.h>
6 #include <stdlib.h>
8 #include "board.h"
9 #include "debug.h"
10 #include "pattern.h"
11 #include "patternsp.h"
12 #include "patternprob.h"
13 #include "tactics/ladder.h"
14 #include "tactics/selfatari.h"
15 #include "tactics/util.h"
18 struct pattern_config DEFAULT_PATTERN_CONFIG = {
19 .bdist_max = 4,
21 .spat_min = 3, .spat_max = MAX_PATTERN_DIST,
22 .spat_largest = true,
25 #define PF_MATCH 15
27 pattern_spec PATTERN_SPEC_MATCH_DEFAULT = {
28 [FEAT_CAPTURE] = ~0,
29 [FEAT_AESCAPE] = ~0,
30 [FEAT_SELFATARI] = ~0,
31 [FEAT_ATARI] = ~0,
32 [FEAT_BORDER] = ~0,
33 [FEAT_CONTIGUITY] = 0,
34 [FEAT_SPATIAL] = ~0,
37 static const struct feature_info {
38 char *name;
39 int payloads;
40 } features[FEAT_MAX] = {
41 [FEAT_CAPTURE] = { .name = "capture", .payloads = 64 },
42 [FEAT_AESCAPE] = { .name = "atariescape", .payloads = 16 },
43 [FEAT_SELFATARI] = { .name = "selfatari", .payloads = 4 },
44 [FEAT_ATARI] = { .name = "atari", .payloads = 4 },
45 [FEAT_BORDER] = { .name = "border", .payloads = -1 },
46 [FEAT_CONTIGUITY] = { .name = "cont", .payloads = 2 },
47 [FEAT_SPATIAL] = { .name = "s", .payloads = -1 },
50 char *
51 feature2str(char *str, struct feature *f)
53 return str + sprintf(str + strlen(str), "%s:%d", features[f->id].name, f->payload);
56 char *
57 str2feature(char *str, struct feature *f)
59 while (isspace(*str)) str++;
61 int unsigned flen = strcspn(str, ":");
62 for (unsigned int i = 0; i < sizeof(features)/sizeof(features[0]); i++)
63 if (strlen(features[i].name) == flen && !strncmp(features[i].name, str, flen)) {
64 f->id = i;
65 goto found;
67 fprintf(stderr, "invalid featurespec: %s[%d]\n", str, flen);
68 exit(EXIT_FAILURE);
70 found:
71 str += flen + 1;
72 f->payload = strtoull(str, &str, 10);
73 return str;
76 char *
77 feature_name(enum feature_id f)
79 return features[f].name;
82 int
83 feature_payloads(struct pattern_config *pc, enum feature_id f)
85 switch (f) {
86 case FEAT_SPATIAL:
87 assert(features[f].payloads < 0);
88 return pc->spat_dict->nspatials;
89 case FEAT_BORDER:
90 assert(features[f].payloads < 0);
91 return pc->bdist_max + 1;
92 default:
93 assert(features[f].payloads > 0);
94 return features[f].payloads;
99 void
100 patterns_init(struct pattern_setup *pat, char *arg, bool will_append, bool load_prob)
102 char *pdict_file = NULL;
104 memset(pat, 0, sizeof(*pat));
106 pat->pc = DEFAULT_PATTERN_CONFIG;
107 pat->pc.spat_dict = spatial_dict_init(will_append, !load_prob);
109 memcpy(&pat->ps, PATTERN_SPEC_MATCH_DEFAULT, sizeof(pattern_spec));
111 if (arg) {
112 char *optspec, *next = arg;
113 while (*next) {
114 optspec = next;
115 next += strcspn(next, ":");
116 if (*next) { *next++ = 0; } else { *next = 0; }
118 char *optname = optspec;
119 char *optval = strchr(optspec, '=');
120 if (optval) *optval++ = 0;
122 /* See pattern.h:pattern_config for description and
123 * pattern.c:DEFAULT_PATTERN_CONFIG for default values
124 * of the following options. */
125 if (!strcasecmp(optname, "bdist_max") && optval) {
126 pat->pc.bdist_max = atoi(optval);
127 } else if (!strcasecmp(optname, "spat_min") && optval) {
128 pat->pc.spat_min = atoi(optval);
129 } else if (!strcasecmp(optname, "spat_max") && optval) {
130 pat->pc.spat_max = atoi(optval);
131 } else if (!strcasecmp(optname, "spat_largest")) {
132 pat->pc.spat_largest = !optval || atoi(optval);
134 } else if (!strcasecmp(optname, "pdict_file") && optval) {
135 pdict_file = optval;
137 } else {
138 fprintf(stderr, "patterns: Invalid argument %s or missing value\n", optname);
139 exit(EXIT_FAILURE);
144 if (load_prob && pat->pc.spat_dict) {
145 pat->pd = pattern_pdict_init(pdict_file, &pat->pc);
150 /* pattern_spec helpers */
151 #define PS_ANY(F) (ps[FEAT_ ## F] & (1 << PF_MATCH))
152 #define PS_PF(F, P) (ps[FEAT_ ## F] & (1 << PF_ ## F ## _ ## P))
154 static struct feature *
155 pattern_match_capture(struct pattern_config *pc, pattern_spec ps,
156 struct pattern *p, struct feature *f,
157 struct board *b, struct move *m)
159 f->id = FEAT_CAPTURE; f->payload = 0;
160 #ifdef BOARD_TRAITS
161 if (!trait_at(b, m->coord, m->color).cap)
162 return f;
163 /* Capturable! */
164 if ((ps[FEAT_CAPTURE] & ~(1<<PF_CAPTURE_1STONE | 1<<PF_CAPTURE_TRAPPED | 1<<PF_CAPTURE_CONNECTION)) == 1<<PF_MATCH) {
165 if (PS_PF(CAPTURE, 1STONE))
166 f->payload |= (trait_at(b, m->coord, m->color).cap1 == trait_at(b, m->coord, m->color).cap) << PF_CAPTURE_1STONE;
167 if (PS_PF(CAPTURE, TRAPPED))
168 f->payload |= (!trait_at(b, m->coord, stone_other(m->color)).safe) << PF_CAPTURE_TRAPPED;
169 if (PS_PF(CAPTURE, CONNECTION))
170 f->payload |= (trait_at(b, m->coord, m->color).cap < neighbor_count_at(b, m->coord, stone_other(m->color))) << PF_CAPTURE_CONNECTION;
171 (f++, p->n++);
172 return f;
174 /* We need to know details, so we still have to go through
175 * the neighbors. */
176 #endif
178 /* We look at neighboring groups we could capture, and also if the
179 * opponent could save them. */
180 /* This is very similar in spirit to board_safe_to_play(), and almost
181 * a color inverse of pattern_match_aescape(). */
183 /* Whether an escape move would be safe for the opponent. */
184 int captures = 0;
185 coord_t onelib = -1;
186 int extra_libs = 0, connectable_groups = 0;
187 bool onestone = false, multistone = false;
189 foreach_neighbor(b, m->coord, {
190 if (board_at(b, c) != stone_other(m->color)) {
191 if (board_at(b, c) == S_NONE)
192 extra_libs++; // free point
193 else if (board_at(b, c) == m->color && board_group_info(b, group_at(b, c)).libs == 1)
194 extra_libs += 2; // capturable enemy group
195 continue;
198 group_t g = group_at(b, c); assert(g);
199 if (board_group_info(b, g).libs > 1) {
200 connectable_groups++;
201 if (board_group_info(b, g).libs > 2) {
202 extra_libs += 2; // connected out
203 } else {
204 /* This is a bit tricky; we connect our 2-lib
205 * group to another 2-lib group, which counts
206 * as one liberty, but only if the other lib
207 * is not shared too. */
208 if (onelib == -1) {
209 onelib = board_group_other_lib(b, g, c);
210 extra_libs++;
211 } else {
212 if (c == onelib)
213 extra_libs--; // take that back
214 else
215 extra_libs++;
218 continue;
221 /* Capture! */
222 captures++;
224 if (PS_PF(CAPTURE, LADDER))
225 f->payload |= is_ladder(b, m->coord, g, true) << PF_CAPTURE_LADDER;
226 /* TODO: is_ladder() is too conservative in some
227 * very obvious situations, look at complete.gtp. */
229 if (PS_PF(CAPTURE, ATARIDEF))
230 foreach_in_group(b, g) {
231 foreach_neighbor(b, c, {
232 assert(board_at(b, c) != S_NONE || c == m->coord);
233 if (board_at(b, c) != m->color)
234 continue;
235 group_t g = group_at(b, c);
236 if (!g || board_group_info(b, g).libs != 1)
237 continue;
238 /* A neighboring group of ours is in atari. */
239 f->payload |= 1 << PF_CAPTURE_ATARIDEF;
241 } foreach_in_group_end;
243 if (PS_PF(CAPTURE, KO)
244 && group_is_onestone(b, g)
245 && neighbor_count_at(b, m->coord, stone_other(m->color))
246 + neighbor_count_at(b, m->coord, S_OFFBOARD) == 4)
247 f->payload |= 1 << PF_CAPTURE_KO;
249 if (group_is_onestone(b, g))
250 onestone = true;
251 else
252 multistone = true;
255 if (captures > 0) {
256 if (PS_PF(CAPTURE, 1STONE))
257 f->payload |= (onestone && !multistone) << PF_CAPTURE_1STONE;
258 if (PS_PF(CAPTURE, TRAPPED))
259 f->payload |= (extra_libs < 2) << PF_CAPTURE_TRAPPED;
260 if (PS_PF(CAPTURE, CONNECTION))
261 f->payload |= (connectable_groups > 0) << PF_CAPTURE_CONNECTION;
262 (f++, p->n++);
264 return f;
267 static struct feature *
268 pattern_match_aescape(struct pattern_config *pc, pattern_spec ps,
269 struct pattern *p, struct feature *f,
270 struct board *b, struct move *m)
272 f->id = FEAT_AESCAPE; f->payload = 0;
273 #ifdef BOARD_TRAITS
274 if (!trait_at(b, m->coord, stone_other(m->color)).cap)
275 return f;
276 /* Opponent can capture something! */
277 if ((ps[FEAT_AESCAPE] & ~(1<<PF_AESCAPE_1STONE | 1<<PF_AESCAPE_TRAPPED | 1<<PF_AESCAPE_CONNECTION)) == 1<<PF_MATCH) {
278 if (PS_PF(AESCAPE, 1STONE))
279 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;
280 if (PS_PF(AESCAPE, TRAPPED))
281 f->payload |= (!trait_at(b, m->coord, m->color).safe) << PF_AESCAPE_TRAPPED;
282 if (PS_PF(AESCAPE, CONNECTION))
283 f->payload |= (trait_at(b, m->coord, stone_other(m->color)).cap < neighbor_count_at(b, m->coord, m->color)) << PF_AESCAPE_CONNECTION;
284 (f++, p->n++);
285 return f;
287 /* We need to know details, so we still have to go through
288 * the neighbors. */
289 #endif
291 /* Find if a neighboring group of ours is in atari, AND that we provide
292 * a liberty to connect out. XXX: No connect-and-die check. */
293 /* This is very similar in spirit to board_safe_to_play(). */
294 group_t in_atari = -1;
295 coord_t onelib = -1;
296 int extra_libs = 0, connectable_groups = 0;
297 bool onestone = false, multistone = false;
299 foreach_neighbor(b, m->coord, {
300 if (board_at(b, c) != m->color) {
301 if (board_at(b, c) == S_NONE)
302 extra_libs++; // free point
303 else if (board_at(b, c) == stone_other(m->color) && board_group_info(b, group_at(b, c)).libs == 1) {
304 extra_libs += 2; // capturable enemy group
305 /* XXX: We just consider this move safe
306 * unconditionally. */
308 continue;
310 group_t g = group_at(b, c); assert(g);
311 if (board_group_info(b, g).libs > 1) {
312 connectable_groups++;
313 if (board_group_info(b, g).libs > 2) {
314 extra_libs += 2; // connected out
315 } else {
316 /* This is a bit tricky; we connect our 2-lib
317 * group to another 2-lib group, which counts
318 * as one liberty, but only if the other lib
319 * is not shared too. */
320 if (onelib == -1) {
321 onelib = board_group_other_lib(b, g, c);
322 extra_libs++;
323 } else {
324 if (c == onelib)
325 extra_libs--; // take that back
326 else
327 extra_libs++;
330 continue;
333 /* In atari! */
334 in_atari = g;
336 if (PS_PF(AESCAPE, LADDER))
337 f->payload |= is_ladder(b, m->coord, g, true) << PF_AESCAPE_LADDER;
338 /* TODO: is_ladder() is too conservative in some
339 * very obvious situations, look at complete.gtp. */
341 if (group_is_onestone(b, g))
342 onestone = true;
343 else
344 multistone = true;
347 if (in_atari >= 0) {
348 if (PS_PF(AESCAPE, 1STONE))
349 f->payload |= (onestone && !multistone) << PF_AESCAPE_1STONE;
350 if (PS_PF(AESCAPE, TRAPPED))
351 f->payload |= (extra_libs < 2) << PF_AESCAPE_TRAPPED;
352 if (PS_PF(AESCAPE, CONNECTION))
353 f->payload |= (connectable_groups > 0) << PF_AESCAPE_CONNECTION;
354 (f++, p->n++);
356 return f;
359 static struct feature *
360 pattern_match_atari(struct pattern_config *pc, pattern_spec ps,
361 struct pattern *p, struct feature *f,
362 struct board *b, struct move *m)
364 foreach_neighbor(b, m->coord, {
365 if (board_at(b, c) != stone_other(m->color))
366 continue;
367 group_t g = group_at(b, c);
368 if (!g || board_group_info(b, g).libs != 2)
369 continue;
371 /* Can atari! */
372 f->id = FEAT_ATARI; f->payload = 0;
374 if (PS_PF(ATARI, LADDER)) {
375 /* Opponent will escape by the other lib. */
376 coord_t lib = board_group_other_lib(b, g, m->coord);
377 /* TODO: is_ladder() is too conservative in some
378 * very obvious situations, look at complete.gtp. */
379 f->payload |= is_ladder(b, lib, g, true) << PF_ATARI_LADDER;
382 if (PS_PF(ATARI, KO) && !is_pass(b->ko.coord))
383 f->payload |= 1 << PF_ATARI_KO;
385 (f++, p->n++);
387 return f;
390 #ifndef BOARD_SPATHASH
391 #undef BOARD_SPATHASH_MAXD
392 #define BOARD_SPATHASH_MAXD 1
393 #endif
395 /* Match spatial features that are too distant to be pre-matched
396 * incrementally. */
397 struct feature *
398 pattern_match_spatial_outer(struct pattern_config *pc, pattern_spec ps,
399 struct pattern *p, struct feature *f,
400 struct board *b, struct move *m, hash_t h)
402 /* We record all spatial patterns black-to-play; simply
403 * reverse all colors if we are white-to-play. */
404 static enum stone bt_black[4] = { S_NONE, S_BLACK, S_WHITE, S_OFFBOARD };
405 static enum stone bt_white[4] = { S_NONE, S_WHITE, S_BLACK, S_OFFBOARD };
406 enum stone (*bt)[4] = m->color == S_WHITE ? &bt_white : &bt_black;
408 for (int d = BOARD_SPATHASH_MAXD + 1; d <= pc->spat_max; d++) {
409 /* Recompute missing outer circles:
410 * Go through all points in given distance. */
411 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
412 ptcoords_at(x, y, m->coord, b, j);
413 h ^= pthashes[0][j][(*bt)[board_atxy(b, x, y)]];
415 if (d < pc->spat_min)
416 continue;
417 /* Record spatial feature, one per distance. */
418 unsigned int sid = spatial_dict_get(pc->spat_dict, d, h & spatial_hash_mask);
419 if (sid > 0) {
420 f->id = FEAT_SPATIAL;
421 f->payload = sid;
422 if (!pc->spat_largest)
423 (f++, p->n++);
424 } /* else not found, ignore */
426 return f;
429 struct feature *
430 pattern_match_spatial(struct pattern_config *pc, pattern_spec ps,
431 struct pattern *p, struct feature *f,
432 struct board *b, struct move *m)
434 /* XXX: This is partially duplicated from spatial_from_board(), but
435 * we build a hash instead of spatial record. */
437 assert(pc->spat_min > 0);
438 f->id = -1;
440 hash_t h = pthashes[0][0][S_NONE];
441 #ifdef BOARD_SPATHASH
442 bool w_to_play = m->color == S_WHITE;
443 for (int d = 2; d <= BOARD_SPATHASH_MAXD; d++) {
444 /* Reuse all incrementally matched data. */
445 h ^= b->spathash[m->coord][d - 1][w_to_play];
446 if (d < pc->spat_min)
447 continue;
448 /* Record spatial feature, one per distance. */
449 unsigned int sid = spatial_dict_get(pc->spat_dict, d, h & spatial_hash_mask);
450 if (sid > 0) {
451 f->id = FEAT_SPATIAL;
452 f->payload = sid;
453 if (!pc->spat_largest)
454 (f++, p->n++);
455 } /* else not found, ignore */
457 #else
458 assert(BOARD_SPATHASH_MAXD < 2);
459 #endif
460 if (unlikely(pc->spat_max > BOARD_SPATHASH_MAXD))
461 f = pattern_match_spatial_outer(pc, ps, p, f, b, m, h);
462 if (pc->spat_largest && f->id == FEAT_SPATIAL)
463 (f++, p->n++);
464 return f;
468 void
469 pattern_match(struct pattern_config *pc, pattern_spec ps,
470 struct pattern *p, struct board *b, struct move *m)
472 p->n = 0;
473 struct feature *f = &p->f[0];
475 /* TODO: We should match pretty much all of these features
476 * incrementally. */
478 if (PS_ANY(CAPTURE)) {
479 f = pattern_match_capture(pc, ps, p, f, b, m);
482 if (PS_ANY(AESCAPE)) {
483 f = pattern_match_aescape(pc, ps, p, f, b, m);
486 if (PS_ANY(SELFATARI)) {
487 bool simple = false;
488 if (PS_PF(SELFATARI, STUPID)) {
489 #ifdef BOARD_TRAITS
490 if (!b->precise_selfatari)
491 simple = !trait_at(b, m->coord, m->color).safe;
492 else
493 #endif
494 simple = !board_safe_to_play(b, m->coord, m->color);
496 bool thorough = false;
497 if (PS_PF(SELFATARI, SMART)) {
498 #ifdef BOARD_TRAITS
499 if (b->precise_selfatari)
500 thorough = !trait_at(b, m->coord, m->color).safe;
501 else
502 #endif
503 thorough = is_bad_selfatari(b, m->color, m->coord);
505 if (simple || thorough) {
506 f->id = FEAT_SELFATARI;
507 f->payload = simple << PF_SELFATARI_STUPID;
508 f->payload |= thorough << PF_SELFATARI_SMART;
509 (f++, p->n++);
513 if (PS_ANY(ATARI)) {
514 f = pattern_match_atari(pc, ps, p, f, b, m);
517 if (PS_ANY(BORDER)) {
518 int bdist = coord_edge_distance(m->coord, b);
519 if (bdist <= pc->bdist_max) {
520 f->id = FEAT_BORDER;
521 f->payload = bdist;
522 (f++, p->n++);
526 if (PS_ANY(CONTIGUITY) && !is_pass(b->last_move.coord)
527 && coord_is_8adjecent(m->coord, b->last_move.coord, b)) {
528 f->id = FEAT_CONTIGUITY;
529 f->payload = 1;
530 (f++, p->n++);
533 if (PS_ANY(SPATIAL) && pc->spat_max > 0 && pc->spat_dict) {
534 f = pattern_match_spatial(pc, ps, p, f, b, m);
538 char *
539 pattern2str(char *str, struct pattern *p)
541 str = stpcpy(str, "(");
542 for (int i = 0; i < p->n; i++) {
543 if (i > 0) str = stpcpy(str, " ");
544 str = feature2str(str, &p->f[i]);
546 str = stpcpy(str, ")");
547 return str;
550 char *
551 str2pattern(char *str, struct pattern *p)
553 p->n = 0;
554 while (isspace(*str)) str++;
555 if (*str++ != '(') {
556 fprintf(stderr, "invalid patternspec: %s\n", str);
557 exit(EXIT_FAILURE);
560 while (*str != ')') {
561 str = str2feature(str, &p->f[p->n++]);
564 str++;
565 return str;