Merge branch 'master' of git+ssh://repo.or.cz/srv/git/pachi
[pachi/json.git] / pattern.c
blob34031d39f0b3a5fe968379abc1f6429efbea10c6
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 "pattern3.h"
13 #include "tactics/ladder.h"
14 #include "tactics/selfatari.h"
15 #include "tactics/util.h"
18 struct pattern_config DEFAULT_PATTERN_CONFIG = {
19 .spat_min = 3, .spat_max = MAX_PATTERN_DIST,
20 .bdist_max = 4,
21 .ldist_min = 0, .ldist_max = 256,
22 .mcsims = 0, /* Unsupported. */
25 struct pattern_config FAST_PATTERN_CONFIG = {
26 .spat_min = 3, .spat_max = 3,
27 .bdist_max = -1,
28 .ldist_min = 0, .ldist_max = 256,
29 .mcsims = 0,
32 #define PF_MATCH 15
34 pattern_spec PATTERN_SPEC_MATCHALL = {
35 [FEAT_PASS] = ~0,
36 [FEAT_CAPTURE] = ~0,
37 [FEAT_AESCAPE] = ~0,
38 [FEAT_SELFATARI] = ~0,
39 [FEAT_ATARI] = ~0,
40 [FEAT_BORDER] = ~0,
41 [FEAT_LDIST] = ~0,
42 [FEAT_LLDIST] = ~0,
43 [FEAT_CONTIGUITY] = 0,
44 [FEAT_SPATIAL] = ~0,
45 [FEAT_PATTERN3] = 0,
46 [FEAT_MCOWNER] = ~0,
49 /* !!! Note that in order for ELO playout policy to work correctly, this
50 * pattern specification MUST exactly match the features matched by the
51 * BOARD_GAMMA code! You cannot just tinker with this spec freely. */
52 pattern_spec PATTERN_SPEC_MATCHFAST = {
53 [FEAT_PASS] = 0,
54 [FEAT_CAPTURE] = (1<<PF_MATCH | 1<<PF_CAPTURE_1STONE | 1<<PF_CAPTURE_TRAPPED | 1<<PF_CAPTURE_CONNECTION),
55 [FEAT_AESCAPE] = (1<<PF_MATCH | 1<<PF_AESCAPE_1STONE | 1<<PF_AESCAPE_TRAPPED | 1<<PF_AESCAPE_CONNECTION),
56 [FEAT_SELFATARI] = (1<<PF_MATCH | 1<<PF_SELFATARI_STUPID),
57 [FEAT_ATARI] = 0,
58 [FEAT_BORDER] = 0,
59 [FEAT_LDIST] = 0,
60 [FEAT_LLDIST] = 0,
61 [FEAT_CONTIGUITY] = ~0,
62 [FEAT_SPATIAL] = 0,
63 [FEAT_PATTERN3] = ~0,
64 [FEAT_MCOWNER] = 0,
67 static const struct feature_info {
68 char *name;
69 int payloads;
70 } features[FEAT_MAX] = {
71 [FEAT_PASS] = { .name = "pass", .payloads = 2 },
72 [FEAT_CAPTURE] = { .name = "capture", .payloads = 128 },
73 [FEAT_AESCAPE] = { .name = "atariescape", .payloads = 16 },
74 [FEAT_SELFATARI] = { .name = "selfatari", .payloads = 4 },
75 [FEAT_ATARI] = { .name = "atari", .payloads = 4 },
76 [FEAT_BORDER] = { .name = "border", .payloads = -1 },
77 [FEAT_LDIST] = { .name = "ldist", .payloads = -1 },
78 [FEAT_LLDIST] = { .name = "lldist", .payloads = -1 },
79 [FEAT_CONTIGUITY] = { .name = "cont", .payloads = 2 },
80 [FEAT_SPATIAL] = { .name = "s", .payloads = -1 },
81 [FEAT_PATTERN3] = { .name = "p", .payloads = 2<<16 },
82 [FEAT_MCOWNER] = { .name = "mcowner", .payloads = 16 },
85 char *
86 feature2str(char *str, struct feature *f)
88 return str + sprintf(str + strlen(str), "%s:%d", features[f->id].name, f->payload);
91 char *
92 str2feature(char *str, struct feature *f)
94 while (isspace(*str)) str++;
96 int unsigned flen = strcspn(str, ":");
97 for (unsigned int i = 0; i < sizeof(features)/sizeof(features[0]); i++)
98 if (strlen(features[i].name) == flen && !strncmp(features[i].name, str, flen)) {
99 f->id = i;
100 goto found;
102 fprintf(stderr, "invalid featurespec: %s[%d]\n", str, flen);
103 exit(EXIT_FAILURE);
105 found:
106 str += flen + 1;
107 f->payload = strtoull(str, &str, 10);
108 return str;
111 char *
112 feature_name(enum feature_id f)
114 return features[f].name;
118 feature_payloads(struct pattern_config *pc, enum feature_id f)
120 switch (f) {
121 case FEAT_SPATIAL:
122 assert(features[f].payloads < 0);
123 return pc->spat_dict->nspatials;
124 case FEAT_LDIST:
125 case FEAT_LLDIST:
126 assert(features[f].payloads < 0);
127 return pc->ldist_max + 1;
128 case FEAT_BORDER:
129 assert(features[f].payloads < 0);
130 return pc->bdist_max + 1;
131 default:
132 assert(features[f].payloads > 0);
133 return features[f].payloads;
138 /* pattern_spec helpers */
139 #define PS_ANY(F) (ps[FEAT_ ## F] & (1 << PF_MATCH))
140 #define PS_PF(F, P) (ps[FEAT_ ## F] & (1 << PF_ ## F ## _ ## P))
142 //#undef BOARD_TRAITS // for cross-testing of pattern matchers - enable also elo_check_probdist()
144 static struct feature *
145 pattern_match_capture(struct pattern_config *pc, pattern_spec ps,
146 struct pattern *p, struct feature *f,
147 struct board *b, struct move *m)
149 f->id = FEAT_CAPTURE; f->payload = 0;
150 #ifdef BOARD_TRAITS
151 if (!trait_at(b, m->coord, m->color).cap)
152 return f;
153 /* Capturable! */
154 if ((ps[FEAT_CAPTURE] & ~(1<<PF_CAPTURE_1STONE | 1<<PF_CAPTURE_TRAPPED | 1<<PF_CAPTURE_CONNECTION)) == 1<<PF_MATCH) {
155 if (PS_PF(CAPTURE, 1STONE))
156 f->payload |= (trait_at(b, m->coord, m->color).cap1 == trait_at(b, m->coord, m->color).cap) << PF_CAPTURE_1STONE;
157 if (PS_PF(CAPTURE, TRAPPED))
158 f->payload |= (!trait_at(b, m->coord, stone_other(m->color)).safe) << PF_CAPTURE_TRAPPED;
159 if (PS_PF(CAPTURE, CONNECTION))
160 f->payload |= (trait_at(b, m->coord, m->color).cap < neighbor_count_at(b, m->coord, stone_other(m->color))) << PF_CAPTURE_CONNECTION;
161 (f++, p->n++);
162 return f;
164 /* We need to know details, so we still have to go through
165 * the neighbors. */
166 #endif
168 /* We look at neighboring groups we could capture, and also if the
169 * opponent could save them. */
170 /* This is very similar in spirit to board_safe_to_play(), and almost
171 * a color inverse of pattern_match_aescape(). */
173 /* Whether an escape move would be safe for the opponent. */
174 int captures = 0;
175 coord_t onelib = -1;
176 int extra_libs = 0, connectable_groups = 0;
177 bool onestone = false, multistone = false;
179 foreach_neighbor(b, m->coord, {
180 if (board_at(b, c) != stone_other(m->color)) {
181 if (board_at(b, c) == S_NONE)
182 extra_libs++; // free point
183 else if (board_at(b, c) == m->color && board_group_info(b, group_at(b, c)).libs == 1)
184 extra_libs += 2; // capturable enemy group
185 continue;
188 group_t g = group_at(b, c); assert(g);
189 if (board_group_info(b, g).libs > 1) {
190 connectable_groups++;
191 if (board_group_info(b, g).libs > 2) {
192 extra_libs += 2; // connected out
193 } else {
194 /* This is a bit tricky; we connect our 2-lib
195 * group to another 2-lib group, which counts
196 * as one liberty, but only if the other lib
197 * is not shared too. */
198 if (onelib == -1) {
199 onelib = board_group_other_lib(b, g, c);
200 extra_libs++;
201 } else {
202 if (c == onelib)
203 extra_libs--; // take that back
204 else
205 extra_libs++;
208 continue;
211 /* Capture! */
212 captures++;
214 if (PS_PF(CAPTURE, LADDER))
215 f->payload |= is_ladder(b, m->coord, g) << PF_CAPTURE_LADDER;
216 /* TODO: is_ladder() is too conservative in some
217 * very obvious situations, look at complete.gtp. */
219 /* TODO: PF_CAPTURE_RECAPTURE */
221 if (PS_PF(CAPTURE, ATARIDEF))
222 foreach_in_group(b, g) {
223 foreach_neighbor(b, c, {
224 assert(board_at(b, c) != S_NONE || c == m->coord);
225 if (board_at(b, c) != m->color)
226 continue;
227 group_t g = group_at(b, c);
228 if (!g || board_group_info(b, g).libs != 1)
229 continue;
230 /* A neighboring group of ours is in atari. */
231 f->payload |= 1 << PF_CAPTURE_ATARIDEF;
233 } foreach_in_group_end;
235 if (PS_PF(CAPTURE, KO)
236 && group_is_onestone(b, g)
237 && neighbor_count_at(b, m->coord, stone_other(m->color))
238 + neighbor_count_at(b, m->coord, S_OFFBOARD) == 4)
239 f->payload |= 1 << PF_CAPTURE_KO;
241 if (group_is_onestone(b, g))
242 onestone = true;
243 else
244 multistone = true;
247 if (captures > 0) {
248 if (PS_PF(CAPTURE, 1STONE))
249 f->payload |= (onestone && !multistone) << PF_CAPTURE_1STONE;
250 if (PS_PF(CAPTURE, TRAPPED))
251 f->payload |= (extra_libs < 2) << PF_CAPTURE_TRAPPED;
252 if (PS_PF(CAPTURE, CONNECTION))
253 f->payload |= (connectable_groups > 0) << PF_CAPTURE_CONNECTION;
254 (f++, p->n++);
256 return f;
259 static struct feature *
260 pattern_match_aescape(struct pattern_config *pc, pattern_spec ps,
261 struct pattern *p, struct feature *f,
262 struct board *b, struct move *m)
264 f->id = FEAT_AESCAPE; f->payload = 0;
265 #ifdef BOARD_TRAITS
266 if (!trait_at(b, m->coord, stone_other(m->color)).cap)
267 return f;
268 /* Opponent can capture something! */
269 if ((ps[FEAT_AESCAPE] & ~(1<<PF_AESCAPE_1STONE | 1<<PF_AESCAPE_TRAPPED | 1<<PF_AESCAPE_CONNECTION)) == 1<<PF_MATCH) {
270 if (PS_PF(AESCAPE, 1STONE))
271 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;
272 if (PS_PF(AESCAPE, TRAPPED))
273 f->payload |= (!trait_at(b, m->coord, m->color).safe) << PF_AESCAPE_TRAPPED;
274 if (PS_PF(AESCAPE, CONNECTION))
275 f->payload |= (trait_at(b, m->coord, stone_other(m->color)).cap < neighbor_count_at(b, m->coord, m->color)) << PF_AESCAPE_CONNECTION;
276 (f++, p->n++);
277 return f;
279 /* We need to know details, so we still have to go through
280 * the neighbors. */
281 #endif
283 /* Find if a neighboring group of ours is in atari, AND that we provide
284 * a liberty to connect out. XXX: No connect-and-die check. */
285 /* This is very similar in spirit to board_safe_to_play(). */
286 group_t in_atari = -1;
287 coord_t onelib = -1;
288 int extra_libs = 0, connectable_groups = 0;
289 bool onestone = false, multistone = false;
291 foreach_neighbor(b, m->coord, {
292 if (board_at(b, c) != m->color) {
293 if (board_at(b, c) == S_NONE)
294 extra_libs++; // free point
295 else if (board_at(b, c) == stone_other(m->color) && board_group_info(b, group_at(b, c)).libs == 1) {
296 extra_libs += 2; // capturable enemy group
297 /* XXX: We just consider this move safe
298 * unconditionally. */
300 continue;
302 group_t g = group_at(b, c); assert(g);
303 if (board_group_info(b, g).libs > 1) {
304 connectable_groups++;
305 if (board_group_info(b, g).libs > 2) {
306 extra_libs += 2; // connected out
307 } else {
308 /* This is a bit tricky; we connect our 2-lib
309 * group to another 2-lib group, which counts
310 * as one liberty, but only if the other lib
311 * is not shared too. */
312 if (onelib == -1) {
313 onelib = board_group_other_lib(b, g, c);
314 extra_libs++;
315 } else {
316 if (c == onelib)
317 extra_libs--; // take that back
318 else
319 extra_libs++;
322 continue;
325 /* In atari! */
326 in_atari = g;
328 if (PS_PF(AESCAPE, LADDER))
329 f->payload |= is_ladder(b, m->coord, g) << PF_AESCAPE_LADDER;
330 /* TODO: is_ladder() is too conservative in some
331 * very obvious situations, look at complete.gtp. */
333 if (group_is_onestone(b, g))
334 onestone = true;
335 else
336 multistone = true;
339 if (in_atari >= 0) {
340 if (PS_PF(AESCAPE, 1STONE))
341 f->payload |= (onestone && !multistone) << PF_AESCAPE_1STONE;
342 if (PS_PF(AESCAPE, TRAPPED))
343 f->payload |= (extra_libs < 2) << PF_AESCAPE_TRAPPED;
344 if (PS_PF(AESCAPE, CONNECTION))
345 f->payload |= (connectable_groups > 0) << PF_AESCAPE_CONNECTION;
346 (f++, p->n++);
348 return f;
351 static struct feature *
352 pattern_match_atari(struct pattern_config *pc, pattern_spec ps,
353 struct pattern *p, struct feature *f,
354 struct board *b, struct move *m)
356 foreach_neighbor(b, m->coord, {
357 if (board_at(b, c) != stone_other(m->color))
358 continue;
359 group_t g = group_at(b, c);
360 if (!g || board_group_info(b, g).libs != 2)
361 continue;
363 /* Can atari! */
364 f->id = FEAT_ATARI; f->payload = 0;
366 if (PS_PF(ATARI, LADDER)) {
367 /* Opponent will escape by the other lib. */
368 coord_t lib = board_group_other_lib(b, g, m->coord);
369 /* TODO: is_ladder() is too conservative in some
370 * very obvious situations, look at complete.gtp. */
371 f->payload |= is_ladder(b, lib, g) << PF_ATARI_LADDER;
374 if (PS_PF(ATARI, KO) && !is_pass(b->ko.coord))
375 f->payload |= 1 << PF_ATARI_KO;
377 (f++, p->n++);
379 return f;
382 #ifndef BOARD_SPATHASH
383 #undef BOARD_SPATHASH_MAXD
384 #define BOARD_SPATHASH_MAXD 1
385 #endif
387 /* Match spatial features that are too distant to be pre-matched
388 * incrementally. */
389 struct feature *
390 pattern_match_spatial_outer(struct pattern_config *pc, pattern_spec ps,
391 struct pattern *p, struct feature *f,
392 struct board *b, struct move *m, hash_t h)
394 /* We record all spatial patterns black-to-play; simply
395 * reverse all colors if we are white-to-play. */
396 static enum stone bt_black[4] = { S_NONE, S_BLACK, S_WHITE, S_OFFBOARD };
397 static enum stone bt_white[4] = { S_NONE, S_WHITE, S_BLACK, S_OFFBOARD };
398 enum stone (*bt)[4] = m->color == S_WHITE ? &bt_white : &bt_black;
400 for (int d = BOARD_SPATHASH_MAXD + 1; d <= pc->spat_max; d++) {
401 /* Recompute missing outer circles:
402 * Go through all points in given distance. */
403 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
404 ptcoords_at(x, y, m->coord, b, j);
405 h ^= pthashes[0][j][(*bt)[board_atxy(b, x, y)]];
407 if (d < pc->spat_min)
408 continue;
409 /* Record spatial feature, one per distance. */
410 int sid = spatial_dict_get(pc->spat_dict, d, h & spatial_hash_mask);
411 if (sid > 0) {
412 f->id = FEAT_SPATIAL;
413 f->payload = sid;
414 (f++, p->n++);
415 } /* else not found, ignore */
417 return f;
420 struct feature *
421 pattern_match_spatial(struct pattern_config *pc, pattern_spec ps,
422 struct pattern *p, struct feature *f,
423 struct board *b, struct move *m)
425 /* XXX: This is partially duplicated from spatial_from_board(), but
426 * we build a hash instead of spatial record. */
428 assert(pc->spat_min > 0);
430 hash_t h = pthashes[0][0][S_NONE];
431 #ifdef BOARD_SPATHASH
432 bool w_to_play = m->color == S_WHITE;
433 for (int d = 2; d <= BOARD_SPATHASH_MAXD; d++) {
434 /* Reuse all incrementally matched data. */
435 h ^= b->spathash[m->coord][d - 1][w_to_play];
436 if (d < pc->spat_min)
437 continue;
438 /* Record spatial feature, one per distance. */
439 int sid = spatial_dict_get(pc->spat_dict, d, h & spatial_hash_mask);
440 if (sid > 0) {
441 f->id = FEAT_SPATIAL;
442 f->payload = sid;
443 (f++, p->n++);
444 } /* else not found, ignore */
446 #else
447 assert(BOARD_SPATHASH_MAXD < 2);
448 #endif
449 if (unlikely(pc->spat_max > BOARD_SPATHASH_MAXD))
450 f = pattern_match_spatial_outer(pc, ps, p, f, b, m, h);
451 return f;
455 void
456 pattern_match(struct pattern_config *pc, pattern_spec ps,
457 struct pattern *p, struct board *b, struct move *m)
459 p->n = 0;
460 struct feature *f = &p->f[0];
462 /* TODO: We should match pretty much all of these features
463 * incrementally. */
465 if (is_pass(m->coord)) {
466 if (PS_ANY(PASS)) {
467 f->id = FEAT_PASS; f->payload = 0;
468 if (PS_PF(PASS, LASTPASS))
469 f->payload |= (b->moves > 0 && is_pass(b->last_move.coord))
470 << PF_PASS_LASTPASS;
471 p->n++;
473 return;
476 if (PS_ANY(CAPTURE)) {
477 f = pattern_match_capture(pc, ps, p, f, b, m);
480 if (PS_ANY(AESCAPE)) {
481 f = pattern_match_aescape(pc, ps, p, f, b, m);
484 if (PS_ANY(SELFATARI)) {
485 bool simple = false;
486 if (PS_PF(SELFATARI, STUPID)) {
487 #ifdef BOARD_TRAITS
488 if (!b->precise_selfatari)
489 simple = !trait_at(b, m->coord, m->color).safe;
490 else
491 #endif
492 simple = !board_safe_to_play(b, m->coord, m->color);
494 bool thorough = false;
495 if (PS_PF(SELFATARI, SMART)) {
496 #ifdef BOARD_TRAITS
497 if (b->precise_selfatari)
498 thorough = !trait_at(b, m->coord, m->color).safe;
499 else
500 #endif
501 thorough = is_bad_selfatari(b, m->color, m->coord);
503 if (simple || thorough) {
504 f->id = FEAT_SELFATARI;
505 f->payload = simple << PF_SELFATARI_STUPID;
506 f->payload |= thorough << PF_SELFATARI_SMART;
507 (f++, p->n++);
511 if (PS_ANY(ATARI)) {
512 f = pattern_match_atari(pc, ps, p, f, b, m);
515 if (PS_ANY(BORDER)) {
516 int bdist = coord_edge_distance(m->coord, b);
517 if (bdist <= pc->bdist_max) {
518 f->id = FEAT_BORDER;
519 f->payload = bdist;
520 (f++, p->n++);
524 if (PS_ANY(CONTIGUITY) && !is_pass(b->last_move.coord)
525 && coord_is_8adjecent(m->coord, b->last_move.coord, b)) {
526 f->id = FEAT_CONTIGUITY;
527 f->payload = 1;
528 (f++, p->n++);
531 if (PS_ANY(LDIST) && pc->ldist_max > 0 && !is_pass(b->last_move.coord)) {
532 int ldist = coord_gridcular_distance(m->coord, b->last_move.coord, b);
533 if (pc->ldist_min <= ldist && ldist <= pc->ldist_max) {
534 f->id = FEAT_LDIST;
535 f->payload = ldist;
536 (f++, p->n++);
540 if (PS_ANY(LLDIST) && pc->ldist_max > 0 && !is_pass(b->last_move2.coord)) {
541 int lldist = coord_gridcular_distance(m->coord, b->last_move2.coord, b);
542 if (pc->ldist_min <= lldist && lldist <= pc->ldist_max) {
543 f->id = FEAT_LLDIST;
544 f->payload = lldist;
545 (f++, p->n++);
549 if (PS_ANY(SPATIAL) && pc->spat_max > 0 && pc->spat_dict) {
550 f = pattern_match_spatial(pc, ps, p, f, b, m);
553 if (PS_ANY(PATTERN3) && !is_pass(m->coord)) {
554 #ifdef BOARD_PAT3
555 hash3_t pat = b->pat3[m->coord];
556 #else
557 hash3_t pat = pattern3_hash(b, m->coord);
558 #endif
559 if (m->color == S_WHITE) {
560 /* We work with the pattern3s as black-to-play. */
561 pat = pattern3_reverse(pat);
563 f->id = FEAT_PATTERN3;
564 f->payload = pat;
565 (f++, p->n++);
568 /* FEAT_MCOWNER: TODO */
569 assert(!pc->mcsims);
572 char *
573 pattern2str(char *str, struct pattern *p)
575 str = stpcpy(str, "(");
576 for (int i = 0; i < p->n; i++) {
577 if (i > 0) str = stpcpy(str, " ");
578 str = feature2str(str, &p->f[i]);
580 str = stpcpy(str, ")");
581 return str;
586 /*** Features gamma set */
588 static void
589 features_gamma_load(struct features_gamma *fg, const char *filename)
591 FILE *f = fopen(filename, "r");
592 if (!f) return;
593 char buf[256];
594 while (fgets(buf, 256, f)) {
595 char *bufp = buf;
596 struct feature f;
597 bufp = str2feature(bufp, &f);
598 while (isspace(*bufp)) bufp++;
599 double gamma = strtod(bufp, &bufp);
600 /* Record feature's gamma. */
601 feature_gamma(fg, &f, &gamma);
602 /* In case of 3x3 patterns, record gamma also
603 * for all rotations and transpositions. */
604 if (f.id == FEAT_PATTERN3) {
605 hash3_t transp[8];
606 pattern3_transpose(f.payload, &transp);
607 for (int i = 1; i < 8; i++) {
608 f.payload = transp[i];
609 feature_gamma(fg, &f, &gamma);
611 f.payload = transp[0];
614 fclose(f);
617 const char *features_gamma_filename = "patterns.gamma";
619 struct features_gamma *
620 features_gamma_init(struct pattern_config *pc, const char *file)
622 struct features_gamma *fg = calloc2(1, sizeof(*fg));
623 fg->pc = pc;
624 for (int i = 0; i < FEAT_MAX; i++) {
625 int n = feature_payloads(pc, i);
626 fg->gamma[i] = malloc2(n * sizeof(fg->gamma[0][0]));
627 for (int j = 0; j < n; j++) {
628 fg->gamma[i][j] = 1.0f;
631 features_gamma_load(fg, file ? file : features_gamma_filename);
632 return fg;
635 void
636 features_gamma_done(struct features_gamma *fg)
638 for (int i = 0; i < FEAT_MAX; i++)
639 free(fg->gamma[i]);
640 free(fg);