Pattern: Tune for minimal collisions
[pachi.git] / pattern.c
blob99d1be9a1398a05bc3da0a52326c761ce0923c3a
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 "tactics.h"
14 struct pattern_config DEFAULT_PATTERN_CONFIG = {
15 .spat_min = 2, .spat_max = MAX_PATTERN_DIST,
16 .bdist_max = 4,
17 .ldist_min = 0, .ldist_max = 256,
18 .mcsims = 0, /* Unsupported. */
22 static const char *fnames[] = {
23 [FEAT_SPATIAL] = "s",
24 [FEAT_PASS] = "pass",
25 [FEAT_CAPTURE] = "capture",
26 [FEAT_AESCAPE] = "atariescape",
27 [FEAT_SELFATARI] = "selfatari",
28 [FEAT_ATARI] = "atari",
29 [FEAT_BORDER] = "border",
30 [FEAT_LDIST] = "ldist",
31 [FEAT_LLDIST] = "lldist",
32 [FEAT_MCOWNER] = "mcowner",
35 char *
36 feature2str(char *str, struct feature *f)
38 return str + sprintf(str + strlen(str), "%s:%"PRIx32, fnames[f->id], f->payload);
41 char *
42 str2feature(char *str, struct feature *f)
44 while (isspace(*str)) str++;
46 int flen = strcspn(str, ":");
47 for (int i = 0; i < sizeof(fnames)/sizeof(fnames[0]); i++)
48 if (strlen(fnames[i]) == flen && strncmp(fnames[i], str, flen)) {
49 f->id = i;
50 goto found;
52 fprintf(stderr, "invalid featurespec: %s\n", str);
53 exit(EXIT_FAILURE);
55 found:
56 str += flen + 1;
57 f->payload = strtoull(str, &str, 10);
58 return str;
62 /* Mapping from point sequence to coordinate offsets (to determine
63 * coordinates relative to pattern center). The array is ordered
64 * in the gridcular metric order so that we can go through it
65 * and incrementally match spatial features in nested circles.
66 * Within one circle, coordinates are ordered by rows to keep
67 * good cache behavior. */
68 static struct { short x, y; } ptcoords[MAX_PATTERN_AREA];
69 /* For each radius, starting index in ptcoords[]. */
70 static int ptind[MAX_PATTERN_DIST + 1];
71 static void __attribute__((constructor)) ptcoords_init(void)
73 int i = 0; /* Indexing ptcoords[] */
75 /* First, center point. */
76 ptind[0] = ptind[1] = 0;
77 ptcoords[i].x = ptcoords[i].y = 0; i++;
79 for (int d = 2; d < MAX_PATTERN_DIST + 1; d++) {
80 ptind[d] = i;
81 /* For each y, examine all integer solutions
82 * of d = |x| + |y| + max(|x|, |y|). */
83 /* TODO: (Stern, 2006) uses a hand-modified
84 * circles that are finer for small d. */
85 for (short y = d / 2; y >= 0; y--) {
86 short x;
87 if (y > d / 3) {
88 /* max(|x|, |y|) = |y|, non-zero x */
89 x = d - y * 2;
90 if (x + y * 2 != d) continue;
91 } else {
92 /* max(|x|, |y|) = |x| */
93 /* Or, max(|x|, |y|) = |y| and x is zero */
94 x = (d - y) / 2;
95 if (x * 2 + y != d) continue;
98 assert((x > y ? x : y) + x + y == d);
100 ptcoords[i].x = x; ptcoords[i].y = y; i++;
101 if (x != 0) { ptcoords[i].x = -x; ptcoords[i].y = y; i++; }
102 if (y != 0) { ptcoords[i].x = x; ptcoords[i].y = -y; i++; }
103 if (x != 0 && y != 0) { ptcoords[i].x = -x; ptcoords[i].y = -y; i++; }
106 ptind[MAX_PATTERN_DIST] = i;
108 #if 0
109 for (int d = 0; d < MAX_PATTERN_DIST; d++) {
110 fprintf(stderr, "d=%d (%d) ", d, ptind[d]);
111 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
112 fprintf(stderr, "%d,%d ", ptcoords[j].x, ptcoords[j].y);
114 fprintf(stderr, "\n");
116 #endif
120 void
121 pattern_match(struct pattern_config *pc, struct pattern *p, struct board *b, struct move *m)
123 p->n = 0;
124 struct feature *f = &p->f[0];
126 /* TODO: We should match pretty much all of these features
127 * incrementally. */
129 /* FEAT_PASS */
130 if (is_pass(m->coord)) {
131 f->id = FEAT_PASS; f->payload = 0;
132 f->payload |= (b->moves > 0 && is_pass(b->last_move.coord)) << PF_PASS_LASTPASS;
133 p->n++;
134 return;
137 /* FEAT_CAPTURE */
139 foreach_neighbor(b, m->coord, {
140 if (board_at(b, c) != stone_other(m->color))
141 continue;
142 group_t g = group_at(b, c);
143 if (!g || board_group_info(b, g).libs != 1)
144 continue;
146 /* Capture! */
147 f->id = FEAT_CAPTURE; f->payload = 0;
149 f->payload |= is_ladder(b, m->coord, g, true, true) << PF_CAPTURE_LADDER;
150 /* TODO: is_ladder() is too conservative in some
151 * very obvious situations, look at complete.gtp. */
153 /* TODO: PF_CAPTURE_RECAPTURE */
155 foreach_in_group(b, g) {
156 foreach_neighbor(b, c, {
157 assert(board_at(b, c) != S_NONE || c == m->coord);
158 if (board_at(b, c) != m->color)
159 continue;
160 group_t g = group_at(b, c);
161 if (!g || board_group_info(b, g).libs != 1)
162 continue;
163 /* A neighboring group of ours is in atari. */
164 f->payload |= 1 << PF_CAPTURE_ATARIDEF;
166 } foreach_in_group_end;
168 if (group_is_onestone(b, g)
169 && neighbor_count_at(b, m->coord, stone_other(m->color))
170 + neighbor_count_at(b, m->coord, S_OFFBOARD) == 4)
171 f->payload |= 1 << PF_CAPTURE_KO;
173 (f++, p->n++);
178 /* FEAT_AESCAPE */
180 foreach_neighbor(b, m->coord, {
181 if (board_at(b, c) != m->color)
182 continue;
183 group_t g = group_at(b, c);
184 if (!g || board_group_info(b, g).libs != 1)
185 continue;
187 /* In atari! */
188 f->id = FEAT_AESCAPE; f->payload = 0;
190 f->payload |= is_ladder(b, m->coord, g, true, true) << PF_AESCAPE_LADDER;
191 /* TODO: is_ladder() is too conservative in some
192 * very obvious situations, look at complete.gtp. */
194 (f++, p->n++);
199 /* FEAT_SELFATARI */
200 if (is_bad_selfatari(b, m->color, m->coord)) {
201 f->id = FEAT_SELFATARI;
202 /* TODO: Dumb selfatari detection. */
203 f->payload = 1 << PF_SELFATARI_SMART;
206 /* FEAT_ATARI */
208 foreach_neighbor(b, m->coord, {
209 if (board_at(b, c) != stone_other(m->color))
210 continue;
211 group_t g = group_at(b, c);
212 if (!g || board_group_info(b, g).libs != 2)
213 continue;
215 /* Can atari! */
216 f->id = FEAT_ATARI; f->payload = 0;
218 f->payload |= is_ladder(b, m->coord, g, true, true) << PF_ATARI_LADDER;
219 /* TODO: is_ladder() is too conservative in some
220 * very obvious situations, look at complete.gtp. */
222 if (!is_pass(b->ko.coord))
223 f->payload |= 1 << PF_CAPTURE_KO;
225 (f++, p->n++);
229 /* FEAT_BORDER */
230 int bdist = coord_edge_distance(m->coord, b);
231 if (bdist <= pc->bdist_max) {
232 f->id = FEAT_BORDER;
233 f->payload = bdist;
234 (f++, p->n++);
237 /* FEAT_LDIST */
238 if (pc->ldist_max > 0 && !is_pass(b->last_move.coord)) {
239 int ldist = coord_gridcular_distance(m->coord, b->last_move.coord, b);
240 if (pc->ldist_min <= ldist && ldist <= pc->ldist_max) {
241 f->id = FEAT_LDIST;
242 f->payload = ldist;
243 (f++, p->n++);
247 /* FEAT_LLDIST */
248 if (pc->ldist_max > 0 && !is_pass(b->last_move.coord)) {
249 int lldist = coord_gridcular_distance(m->coord, b->last_move2.coord, b);
250 if (pc->ldist_min <= lldist && lldist <= pc->ldist_max) {
251 f->id = FEAT_LLDIST;
252 f->payload = lldist;
253 (f++, p->n++);
257 /* FEAT_SPATIAL */
258 if (pc->spat_max > 0 && pc->spat_dict) {
259 assert(pc->spat_min > 0);
261 struct spatial s = { .points = {0} };
262 for (int d = 2; d < pc->spat_max; d++) {
263 /* Go through all points in given distance. */
264 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
265 int x = coord_x(m->coord, b) + ptcoords[j].x;
266 int y = coord_y(m->coord, b) + ptcoords[j].y;
267 if (x >= board_size(b)) x = board_size(b) - 1; else if (x < 0) x = 0;
268 if (y >= board_size(b)) y = board_size(b) - 1; else if (y < 0) y = 0;
269 /* Append point. */
270 s.points[j / 4] |= board_atxy(b, x, y) << ((j % 4) * 2);
272 if (d < pc->spat_min)
273 continue;
274 /* Record spatial feature, one per distance. */
275 f->id = FEAT_SPATIAL;
276 f->payload = (d << 24) | ((m->color == S_WHITE) << 23);
277 s.dist = d;
278 f->payload |= spatial_dict_get(pc->spat_dict, &s);
279 (f++, p->n++);
283 /* FEAT_MCOWNER */
284 /* TODO */
285 assert(!pc->mcsims);
288 char *
289 pattern2str(char *str, struct pattern *p)
291 strcat(str++, "(");
292 for (int i = 0; i < p->n; i++) {
293 if (i > 0) strcat(str++, " ");
294 str = feature2str(str, &p->f[i]);
296 strcat(str++, ")");
297 return str;
302 /*** Spatial patterns dictionary */
304 /* Zobrist hashes used for black/white stones in patterns. */
305 #define PTH__ROTATIONS 16
306 static hash_t pthashes[PTH__ROTATIONS][MAX_PATTERN_AREA][4];
307 static void __attribute__((constructor)) pthashes_init(void)
309 /* We need fixed hashes for all pattern-relative in
310 * all pattern users! This is a simple way to generate
311 * hopefully good ones. Park-Miller powa. :) */
313 /* We create a virtual board (centered at the sequence start),
314 * plant the hashes there, then pick them up into the sequence
315 * with correct coordinates. It would be possible to generate
316 * the sequence point hashes directly, but the rotations would
317 * make for enormous headaches. */
318 hash_t pthboard[MAX_PATTERN_AREA][4];
319 int pthbc = MAX_PATTERN_AREA / 2; // tengen coord
321 /* The magic numbers are tuned for minimal collisions. */
322 hash_t h = 0x313131;
323 for (int i = 0; i < MAX_PATTERN_AREA; i++) {
324 pthboard[i][S_NONE] = (h = h * 16803 - 7);
325 pthboard[i][S_BLACK] = (h = h * 16805 + 7);
326 pthboard[i][S_WHITE] = (h = h * 16807 + 3);
327 pthboard[i][S_OFFBOARD] = (h = h * 16809 - 3);
330 /* Virtual board with hashes created, now fill
331 * pthashes[] with hashes for points in actual
332 * sequences, also considering various rotations. */
333 #define PTH_VMIRROR 1
334 #define PTH_HMIRROR 2
335 #define PTH_90ROT 4
336 #define PTH_REVCOLOR 8
337 for (int r = 0; r < PTH__ROTATIONS; r++) {
338 for (int i = 0; i < MAX_PATTERN_AREA; i++) {
339 /* Rotate appropriately. */
340 int rx = ptcoords[i].x;
341 int ry = ptcoords[i].y;
342 if (r & PTH_VMIRROR) ry = -ry;
343 if (r & PTH_HMIRROR) rx = -rx;
344 if (r & PTH_90ROT) {
345 int rs = rx; rx = -ry; ry = rs;
347 int bi = pthbc + ry * MAX_PATTERN_DIST + rx;
349 /* Copy info. */
350 pthashes[r][i][S_NONE] = pthboard[bi][S_NONE];
351 if (r & PTH_REVCOLOR) {
352 pthashes[r][i][S_WHITE] = pthboard[bi][S_BLACK];
353 pthashes[r][i][S_BLACK] = pthboard[bi][S_WHITE];
354 } else {
355 pthashes[r][i][S_BLACK] = pthboard[bi][S_BLACK];
356 pthashes[r][i][S_WHITE] = pthboard[bi][S_WHITE];
358 pthashes[r][i][S_OFFBOARD] = pthboard[bi][S_OFFBOARD];
363 static hash_t
364 spatial_hash(int rotation, struct spatial *s)
366 hash_t h = 0;
367 for (int i = 0; i < ptind[s->dist + 1]; i++) {
368 h ^= pthashes[rotation][i][spatial_point_at(*s, i)];
370 return h & spatial_hash_mask;
373 static int
374 spatial_dict_addc(struct spatial_dict *dict, struct spatial *s)
376 /* Allocate space in 1024 blocks. */
377 #define SPATIALS_ALLOC 1024
378 if (!(dict->nspatials % SPATIALS_ALLOC)) {
379 dict->spatials = realloc(dict->spatials,
380 (dict->nspatials + SPATIALS_ALLOC)
381 * sizeof(*dict->spatials));
383 dict->spatials[dict->nspatials] = *s;
384 return dict->nspatials++;
387 static bool
388 spatial_dict_addh(struct spatial_dict *dict, hash_t hash, int id)
390 if (dict->hash[hash]) {
391 dict->collisions++;
392 /* Give up, not worth the trouble. */
393 return false;
395 dict->hash[hash] = id;
396 return true;
399 /* Spatial dictionary file format:
400 * /^#/ - comments
401 * INDEX RADIUS STONES HASH...
402 * INDEX: index in the spatial table
403 * RADIUS: @d of the pattern
404 * STONES: string of ".XO#" chars
405 * HASH...: space-separated 18bit hash-table indices for the pattern */
407 static void
408 spatial_dict_read(struct spatial_dict *dict, char *buf)
410 /* XXX: We trust the data. Bad data will crash us. */
411 char *bufp = buf;
413 int index, radius;
414 index = strtol(bufp, &bufp, 10);
415 radius = strtol(bufp, &bufp, 10);
416 while (isspace(*bufp)) bufp++;
418 /* Load the stone configuration. */
419 struct spatial s = { .dist = radius };
420 int sl = 0;
421 while (!isspace(*bufp)) {
422 s.points[sl / 4] |= char2stone(*bufp++) << (sl % 4);
423 sl++;
425 while (isspace(*bufp)) bufp++;
427 /* Sanity check. */
428 if (sl != ptind[s.dist + 1]) {
429 fprintf(stderr, "Spatial dictionary: Invalid number of stones (%d != %d) on this line: %s\n",
430 sl, ptind[radius + 1] - 1, buf);
431 exit(EXIT_FAILURE);
434 /* Add to collection. */
435 int id = spatial_dict_addc(dict, &s);
437 /* Add to specified hash places. */
438 while (*bufp) {
439 int hash = strtol(bufp, &bufp, 16);
440 while (isspace(*bufp)) bufp++;
441 spatial_dict_addh(dict, hash & spatial_hash_mask, id);
445 static char *
446 spatial2str(struct spatial *s)
448 static char buf[1024];
449 for (int i = 0; i < ptind[s->dist + 1]; i++) {
450 buf[i] = stone2char(spatial_point_at(*s, i));
452 buf[ptind[s->dist + 1]] = 0;
453 return buf;
456 static void
457 spatial_dict_write(struct spatial_dict *dict, int id, FILE *f)
459 struct spatial *s = &dict->spatials[id];
460 fprintf(f, "%d %d ", id, s->dist);
461 fputs(spatial2str(s), f);
462 for (int r = 0; r < PTH__ROTATIONS; r++)
463 fprintf(f, " %"PRIhash"", spatial_hash(r, s));
464 fputc('\n', f);
467 static void
468 spatial_dict_load(struct spatial_dict *dict, FILE *f)
470 char buf[1024];
471 while (fgets(buf, sizeof(buf), f)) {
472 if (buf[0] == '#') continue;
473 spatial_dict_read(dict, buf);
477 struct spatial_dict *
478 spatial_dict_init(bool will_append)
480 static const char *filename = "spatial.dict";
481 FILE *f = fopen(filename, "r");
482 if (!f && !will_append) {
483 if (DEBUGL(2))
484 fprintf(stderr, "No spatial dictionary, will not match spatial pattern features.\n");
485 return NULL;
488 struct spatial_dict *dict = calloc(1, sizeof(*dict));
489 /* We create a dummy record for index 0 that we will
490 * never reference. This is so that hash value 0 can
491 * represent "no value". */
492 struct spatial dummy = { .dist = 0 };
493 spatial_dict_addc(dict, &dummy);
495 if (f) {
496 /* Existing file. Load it up! */
497 spatial_dict_load(dict, f);
498 fclose(f); f = NULL;
499 if (will_append)
500 f = fopen(filename, "a");
501 } else {
502 assert(will_append);
503 f = fopen(filename, "a");
504 /* New file. First, create a comment describing order
505 * of points in the array. This is just for purposes
506 * of external tools, Pachi never interprets it itself. */
507 fprintf(f, "# Pachi spatial patterns dictionary v1.0 maxdist %d\n",
508 MAX_PATTERN_DIST);
509 for (int d = 0; d < MAX_PATTERN_DIST; d++) {
510 fprintf(f, "# Point order: d=%d ", d);
511 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
512 fprintf(f, "%d,%d ", ptcoords[j].x, ptcoords[j].y);
514 fprintf(f, "\n");
518 dict->f = f;
519 return dict;
523 spatial_dict_get(struct spatial_dict *dict, struct spatial *s)
525 hash_t hash = spatial_hash(0, s);
526 int id = dict->hash[hash];
527 if (id && dict->f) {
528 /* Check for collisions in append mode. */
529 /* Tough job, we simply try if all rotations
530 * are also covered by the existing record. */
531 for (int r = 0; r < PTH__ROTATIONS; r++) {
532 hash_t rhash = spatial_hash(r, s);
533 int rid = dict->hash[rhash];
534 if (rid == id)
535 continue;
536 if (DEBUGL(2))
537 fprintf(stderr, "Collision %d vs %d (hash %d:%"PRIhash")\n",
538 rid, dict->nspatials, r, rhash);
539 id = 0;
540 /* dict->collisions++; gets done by addh */
543 if (id) return id;
544 if (!dict->f) return -1;
546 /* Add new pattern! */
547 id = spatial_dict_addc(dict, s);
548 for (int r = 0; r < PTH__ROTATIONS; r++)
549 spatial_dict_addh(dict, spatial_hash(r, s), id);
550 spatial_dict_write(dict, id, dict->f);
551 return id;