pattern.c

   1 #define DEBUG
   2 #include <assert.h>
   3 #include <ctype.h>
   4 #include <inttypes.h>
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7
   8 #include "board.h"
   9 #include "debug.h"
  10 #include "pattern.h"
  11 #include "tactics.h"
  12
  13
  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. */
  19 };
  20
  21 pattern_spec PATTERN_SPEC_MATCHALL = {
  22         [FEAT_PASS] = ~0,
  23         [FEAT_CAPTURE] = ~0,
  24         [FEAT_AESCAPE] = ~0,
  25         [FEAT_SELFATARI] = ~0,
  26         [FEAT_ATARI] = ~0,
  27         [FEAT_BORDER] = ~0,
  28         [FEAT_LDIST] = ~0,
  29         [FEAT_LLDIST] = ~0,
  30         [FEAT_SPATIAL] = ~0,
  31         [FEAT_MCOWNER] = ~0,
  32 };
  33
  34 static const struct feature_info {
  35         char *name;
  36         int payloads;
  37 } features[FEAT_MAX] = {
  38         [FEAT_PASS] = { .name = "pass", .payloads = 2 },
  39         [FEAT_CAPTURE] = { .name = "capture", .payloads = 16 },
  40         [FEAT_AESCAPE] = { .name = "atariescape", .payloads = 2 },
  41         [FEAT_SELFATARI] = { .name = "selfatari", .payloads = 2 },
  42         [FEAT_ATARI] = { .name = "atari", .payloads = 4 },
  43         [FEAT_BORDER] = { .name = "border", .payloads = 1 },
  44         [FEAT_LDIST] = { .name = "ldist", .payloads = -1 },
  45         [FEAT_LLDIST] = { .name = "lldist", .payloads = -1 },
  46         [FEAT_SPATIAL] = { .name = "s", .payloads = -1 },
  47         [FEAT_MCOWNER] = { .name = "mcowner", .payloads = 16 },
  48 };
  49
  50 char *
  51 feature2str(char *str, struct feature *f)
  52 {
  53         return str + sprintf(str + strlen(str), "%s:%"PRIx32, features[f->id].name, f->payload);
  54 }
  55
  56 char *
  57 str2feature(char *str, struct feature *f)
  58 {
  59         while (isspace(*str)) str++;
  60
  61         int flen = strcspn(str, ":");
  62         for (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;
  66                 }
  67         fprintf(stderr, "invalid featurespec: %s[%d]\n", str, flen);
  68         exit(EXIT_FAILURE);
  69
  70 found:
  71         str += flen + 1;
  72         f->payload = strtoull(str, &str, 16);
  73         return str;
  74 }
  75
  76
  77 /* Mapping from point sequence to coordinate offsets (to determine
  78  * coordinates relative to pattern center). The array is ordered
  79  * in the gridcular metric order so that we can go through it
  80  * and incrementally match spatial features in nested circles.
  81  * Within one circle, coordinates are ordered by rows to keep
  82  * good cache behavior. */
  83 static struct { short x, y; } ptcoords[MAX_PATTERN_AREA];
  84 /* For each radius, starting index in ptcoords[]. */
  85 static int ptind[MAX_PATTERN_DIST + 1];
  86 static void __attribute__((constructor)) ptcoords_init(void)
  87 {
  88         int i = 0; /* Indexing ptcoords[] */
  89
  90         /* First, center point. */
  91         ptind[0] = ptind[1] = 0;
  92         ptcoords[i].x = ptcoords[i].y = 0; i++;
  93
  94         for (int d = 2; d < MAX_PATTERN_DIST + 1; d++) {
  95                 ptind[d] = i;
  96                 /* For each y, examine all integer solutions
  97                  * of d = |x| + |y| + max(|x|, |y|). */
  98                 /* TODO: (Stern, 2006) uses a hand-modified
  99                  * circles that are finer for small d. */
 100                 for (short y = d / 2; y >= 0; y--) {
 101                         short x;
 102                         if (y > d / 3) {
 103                                 /* max(|x|, |y|) = |y|, non-zero x */
 104                                 x = d - y * 2;
 105                                 if (x + y * 2 != d) continue;
 106                         } else {
 107                                 /* max(|x|, |y|) = |x| */
 108                                 /* Or, max(|x|, |y|) = |y| and x is zero */
 109                                 x = (d - y) / 2;
 110                                 if (x * 2 + y != d) continue;
 111                         }
 112
 113                         assert((x > y ? x : y) + x + y == d);
 114
 115                         ptcoords[i].x = x; ptcoords[i].y = y; i++;
 116                         if (x != 0) { ptcoords[i].x = -x; ptcoords[i].y = y; i++; }
 117                         if (y != 0) { ptcoords[i].x = x; ptcoords[i].y = -y; i++; }
 118                         if (x != 0 && y != 0) { ptcoords[i].x = -x; ptcoords[i].y = -y; i++; }
 119                 }
 120         }
 121         ptind[MAX_PATTERN_DIST] = i;
 122
 123 #if 0
 124         for (int d = 0; d < MAX_PATTERN_DIST; d++) {
 125                 fprintf(stderr, "d=%d (%d) ", d, ptind[d]);
 126                 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
 127                         fprintf(stderr, "%d,%d ", ptcoords[j].x, ptcoords[j].y);
 128                 }
 129                 fprintf(stderr, "\n");
 130         }
 131 #endif
 132 }
 133
 134
 135 /* pattern_spec helpers */
 136 #define PS_ANY(F) (ps[FEAT_ ## F] & (1 << 31))
 137 #define PS_PF(F, P) (ps[FEAT_ ## F] & (PF_ ## F ## _ ## P))
 138
 139 static struct feature *
 140 pattern_match_capture(struct pattern_config *pc, pattern_spec ps,
 141                       struct pattern *p, struct feature *f,
 142                       struct board *b, struct move *m)
 143 {
 144         foreach_neighbor(b, m->coord, {
 145                 if (board_at(b, c) != stone_other(m->color))
 146                         continue;
 147                 group_t g = group_at(b, c);
 148                 if (!g || board_group_info(b, g).libs != 1)
 149                         continue;
 150
 151                 /* Capture! */
 152                 f->id = FEAT_CAPTURE; f->payload = 0;
 153
 154                 if (PS_PF(CAPTURE, LADDER))
 155                         f->payload |= is_ladder(b, m->coord, g, true, true) << PF_CAPTURE_LADDER;
 156                 /* TODO: is_ladder() is too conservative in some
 157                  * very obvious situations, look at complete.gtp. */
 158
 159                 /* TODO: PF_CAPTURE_RECAPTURE */
 160
 161                 if (PS_PF(CAPTURE, ATARIDEF))
 162                 foreach_in_group(b, g) {
 163                         foreach_neighbor(b, c, {
 164                                 assert(board_at(b, c) != S_NONE || c == m->coord);
 165                                 if (board_at(b, c) != m->color)
 166                                         continue;
 167                                 group_t g = group_at(b, c);
 168                                 if (!g || board_group_info(b, g).libs != 1)
 169                                         continue;
 170                                 /* A neighboring group of ours is in atari. */
 171                                 f->payload |= 1 << PF_CAPTURE_ATARIDEF;
 172                         });
 173                 } foreach_in_group_end;
 174
 175                 if (PS_PF(CAPTURE, KO)
 176                     && group_is_onestone(b, g)
 177                     && neighbor_count_at(b, m->coord, stone_other(m->color))
 178                        + neighbor_count_at(b, m->coord, S_OFFBOARD) == 4)
 179                         f->payload |= 1 << PF_CAPTURE_KO;
 180
 181                 (f++, p->n++);
 182         });
 183         return f;
 184 }
 185
 186 static struct feature *
 187 pattern_match_aescape(struct pattern_config *pc, pattern_spec ps,
 188                       struct pattern *p, struct feature *f,
 189                       struct board *b, struct move *m)
 190 {
 191         foreach_neighbor(b, m->coord, {
 192                 if (board_at(b, c) != m->color)
 193                         continue;
 194                 group_t g = group_at(b, c);
 195                 if (!g || board_group_info(b, g).libs != 1)
 196                         continue;
 197
 198                 /* In atari! */
 199                 f->id = FEAT_AESCAPE; f->payload = 0;
 200
 201                 if (PS_PF(AESCAPE, LADDER))
 202                         f->payload |= is_ladder(b, m->coord, g, true, true) << PF_AESCAPE_LADDER;
 203                 /* TODO: is_ladder() is too conservative in some
 204                  * very obvious situations, look at complete.gtp. */
 205
 206                 (f++, p->n++);
 207         });
 208         return f;
 209 }
 210
 211 static struct feature *
 212 pattern_match_atari(struct pattern_config *pc, pattern_spec ps,
 213                     struct pattern *p, struct feature *f,
 214                     struct board *b, struct move *m)
 215 {
 216         foreach_neighbor(b, m->coord, {
 217                 if (board_at(b, c) != stone_other(m->color))
 218                         continue;
 219                 group_t g = group_at(b, c);
 220                 if (!g || board_group_info(b, g).libs != 2)
 221                         continue;
 222
 223                 /* Can atari! */
 224                 f->id = FEAT_ATARI; f->payload = 0;
 225
 226                 if (PS_PF(ATARI, LADDER)) {
 227                         /* Opponent will escape by the other lib. */
 228                         coord_t lib = board_group_info(b, g).lib[0];
 229                         if (lib == m->coord) lib = board_group_info(b, g).lib[1];
 230                         /* TODO: is_ladder() is too conservative in some
 231                          * very obvious situations, look at complete.gtp. */
 232                         f->payload |= is_ladder(b, lib, g, true, true) << PF_ATARI_LADDER;
 233                 }
 234
 235                 if (PS_PF(ATARI, KO) && !is_pass(b->ko.coord))
 236                         f->payload |= 1 << PF_ATARI_KO;
 237
 238                 (f++, p->n++);
 239         });
 240         return f;
 241 }
 242
 243 static inline hash_t spatial_hash_one(int rotation, int i, enum stone color);
 244
 245 static struct feature *
 246 pattern_match_spatial(struct pattern_config *pc, pattern_spec ps,
 247                       struct pattern *p, struct feature *f,
 248                       struct board *b, struct move *m)
 249 {
 250         assert(pc->spat_min > 0);
 251
 252         /* We record all spatial patterns black-to-play; simply
 253          * reverse all colors if we are white-to-play. */
 254         enum stone bt[4] = { S_NONE, S_BLACK, S_WHITE, S_OFFBOARD };
 255         if (m->color == S_WHITE) {
 256                 bt[1] = S_WHITE; bt[2] = S_BLACK;
 257         }
 258
 259         struct spatial s = { .points = {0} };
 260         hash_t h = spatial_hash_one(0, 0, S_NONE);
 261         for (int d = 2; d < pc->spat_max; d++) {
 262                 /* Go through all points in given distance. */
 263                 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
 264                         int x = coord_x(m->coord, b) + ptcoords[j].x;
 265                         int y = coord_y(m->coord, b) + ptcoords[j].y;
 266                         if (x >= board_size(b)) x = board_size(b) - 1; else if (x < 0) x = 0;
 267                         if (y >= board_size(b)) y = board_size(b) - 1; else if (y < 0) y = 0;
 268                         /* Append point. */
 269                         s.points[j / 4] |= bt[board_atxy(b, x, y)] << ((j % 4) * 2);
 270                         h ^= spatial_hash_one(0, j, bt[board_atxy(b, x, y)]);
 271                 }
 272                 if (d < pc->spat_min)
 273                         continue;
 274                 /* Record spatial feature, one per distance. */
 275                 f->id = FEAT_SPATIAL;
 276                 f->payload = (d << PF_SPATIAL_RADIUS);
 277                 s.dist = d;
 278                 int sid;
 279                 if (unlikely(!!pc->spat_dict->f))
 280                         sid = spatial_dict_put(pc->spat_dict, &s, h & spatial_hash_mask);
 281                 else
 282                         sid = spatial_dict_get(pc->spat_dict, &s, h & spatial_hash_mask);
 283                 if (sid > 0) {
 284                         f->payload |= sid << PF_SPATIAL_INDEX;
 285                         (f++, p->n++);
 286                 } /* else not found, ignore */
 287         }
 288         return f;
 289 }
 290
 291 void
 292 pattern_match(struct pattern_config *pc, pattern_spec ps,
 293               struct pattern *p, struct board *b, struct move *m)
 294 {
 295         p->n = 0;
 296         struct feature *f = &p->f[0];
 297
 298         /* TODO: We should match pretty much all of these features
 299          * incrementally. */
 300
 301         if (is_pass(m->coord)) {
 302                 if (PS_ANY(PASS)) {
 303                         f->id = FEAT_PASS; f->payload = 0;
 304                         if (PS_PF(PASS, LASTPASS))
 305                                 f->payload |= (b->moves > 0 && is_pass(b->last_move.coord))
 306                                                 << PF_PASS_LASTPASS;
 307                         p->n++;
 308                 }
 309                 return;
 310         }
 311
 312         if (PS_ANY(CAPTURE)) {
 313                 f = pattern_match_capture(pc, ps, p, f, b, m);
 314         }
 315
 316         if (PS_ANY(AESCAPE)) {
 317                 f = pattern_match_aescape(pc, ps, p, f, b, m);
 318         }
 319
 320         if (PS_ANY(SELFATARI)) {
 321                 if (is_bad_selfatari(b, m->color, m->coord)) {
 322                         f->id = FEAT_SELFATARI;
 323                         /* TODO: Dumb selfatari detection. */
 324                         f->payload = 1 << PF_SELFATARI_SMART;
 325                         (f++, p->n++);
 326                 }
 327         }
 328
 329         if (PS_ANY(ATARI)) {
 330                 f = pattern_match_atari(pc, ps, p, f, b, m);
 331         }
 332
 333         if (PS_ANY(BORDER)) {
 334                 int bdist = coord_edge_distance(m->coord, b);
 335                 if (bdist <= pc->bdist_max) {
 336                         f->id = FEAT_BORDER;
 337                         f->payload = bdist;
 338                         (f++, p->n++);
 339                 }
 340         }
 341
 342         if (PS_ANY(LDIST) && pc->ldist_max > 0 && !is_pass(b->last_move.coord)) {
 343                 int ldist = coord_gridcular_distance(m->coord, b->last_move.coord, b);
 344                 if (pc->ldist_min <= ldist && ldist <= pc->ldist_max) {
 345                         f->id = FEAT_LDIST;
 346                         f->payload = ldist;
 347                         (f++, p->n++);
 348                 }
 349         }
 350
 351         if (PS_ANY(LLDIST) && pc->ldist_max > 0 && !is_pass(b->last_move2.coord)) {
 352                 int lldist = coord_gridcular_distance(m->coord, b->last_move2.coord, b);
 353                 if (pc->ldist_min <= lldist && lldist <= pc->ldist_max) {
 354                         f->id = FEAT_LLDIST;
 355                         f->payload = lldist;
 356                         (f++, p->n++);
 357                 }
 358         }
 359
 360         if (PS_ANY(SPATIAL) && pc->spat_max > 0 && pc->spat_dict) {
 361                 f = pattern_match_spatial(pc, ps, p, f, b, m);
 362         }
 363
 364         /* FEAT_MCOWNER: TODO */
 365         assert(!pc->mcsims);
 366 }
 367
 368 char *
 369 pattern2str(char *str, struct pattern *p)
 370 {
 371         str = stpcpy(str, "(");
 372         for (int i = 0; i < p->n; i++) {
 373                 if (i > 0) str = stpcpy(str, " ");
 374                 str = feature2str(str, &p->f[i]);
 375         }
 376         str = stpcpy(str, ")");
 377         return str;
 378 }
 379
 380
 381
 382 /*** Features gamma set */
 383
 384 static void
 385 features_gamma_load(struct features_gamma *fg, char *filename)
 386 {
 387         FILE *f = fopen(filename, "r");
 388         if (!f) return;
 389         char buf[256];
 390         while (fgets(buf, 256, f)) {
 391                 char *bufp = buf;
 392                 struct feature f;
 393                 bufp = str2feature(bufp, &f);
 394                 while (isspace(*bufp)) bufp++;
 395                 float gamma = strtof(bufp, &bufp);
 396                 feature_gamma(fg, &f, &gamma);
 397         }
 398         fclose(f);
 399 }
 400
 401 struct features_gamma *
 402 features_gamma_init(struct pattern_config *pc)
 403 {
 404         struct features_gamma *fg = calloc(1, sizeof(*fg));
 405         fg->pc = pc;
 406         for (int i = 0; i < FEAT_MAX; i++) {
 407                 int n = features[i].payloads;
 408                 if (n <= 0) {
 409                         switch (i) {
 410                                 case FEAT_SPATIAL:
 411                                         n = pc->spat_dict->nspatials; break;
 412                                 case FEAT_LDIST:
 413                                 case FEAT_LLDIST:
 414                                         n = pc->ldist_max; break;
 415                                 default:
 416                                         assert(0);
 417                         }
 418                 }
 419                 fg->gamma[i] = malloc(n * sizeof(float));
 420                 for (int j = 0; j < n; j++) {
 421                         fg->gamma[i][j] = 1.0f;
 422                 }
 423         }
 424         features_gamma_load(fg, "patterns.gamma");
 425         return fg;
 426 }
 427
 428 float
 429 feature_gamma(struct features_gamma *fg, struct feature *f, float *gamma)
 430 {
 431         /* XXX: We mask out spatial distance unconditionally since it shouldn't
 432          * affect any other feature. */
 433         int payid = f->payload & ((1<<24)-1);
 434         if (gamma) fg->gamma[f->id][payid] = *gamma;
 435         return fg->gamma[f->id][payid];
 436 }
 437
 438
 439
 440 /*** Spatial patterns dictionary */
 441
 442 /* Zobrist hashes used for black/white stones in patterns. */
 443 #define PTH__ROTATIONS  8
 444 static hash_t pthashes[PTH__ROTATIONS][MAX_PATTERN_AREA][4];
 445 static void __attribute__((constructor)) pthashes_init(void)
 446 {
 447         /* We need fixed hashes for all pattern-relative in
 448          * all pattern users! This is a simple way to generate
 449          * hopefully good ones. Park-Miller powa. :) */
 450
 451         /* We create a virtual board (centered at the sequence start),
 452          * plant the hashes there, then pick them up into the sequence
 453          * with correct coordinates. It would be possible to generate
 454          * the sequence point hashes directly, but the rotations would
 455          * make for enormous headaches. */
 456         hash_t pthboard[MAX_PATTERN_AREA][4];
 457         int pthbc = MAX_PATTERN_AREA / 2; // tengen coord
 458
 459         /* The magic numbers are tuned for minimal collisions. */
 460         hash_t h = 0x313131;
 461         for (int i = 0; i < MAX_PATTERN_AREA; i++) {
 462                 pthboard[i][S_NONE] = (h = h * 16803 - 7);
 463                 pthboard[i][S_BLACK] = (h = h * 16805 + 7);
 464                 pthboard[i][S_WHITE] = (h = h * 16807 + 3);
 465                 pthboard[i][S_OFFBOARD] = (h = h * 16809 - 3);
 466         }
 467
 468         /* Virtual board with hashes created, now fill
 469          * pthashes[] with hashes for points in actual
 470          * sequences, also considering various rotations. */
 471 #define PTH_VMIRROR     1
 472 #define PTH_HMIRROR     2
 473 #define PTH_90ROT       4
 474         for (int r = 0; r < PTH__ROTATIONS; r++) {
 475                 for (int i = 0; i < MAX_PATTERN_AREA; i++) {
 476                         /* Rotate appropriately. */
 477                         int rx = ptcoords[i].x;
 478                         int ry = ptcoords[i].y;
 479                         if (r & PTH_VMIRROR) ry = -ry;
 480                         if (r & PTH_HMIRROR) rx = -rx;
 481                         if (r & PTH_90ROT) {
 482                                 int rs = rx; rx = -ry; ry = rs;
 483                         }
 484                         int bi = pthbc + ry * MAX_PATTERN_DIST + rx;
 485
 486                         /* Copy info. */
 487                         pthashes[r][i][S_NONE] = pthboard[bi][S_NONE];
 488                         pthashes[r][i][S_BLACK] = pthboard[bi][S_BLACK];
 489                         pthashes[r][i][S_WHITE] = pthboard[bi][S_WHITE];
 490                         pthashes[r][i][S_OFFBOARD] = pthboard[bi][S_OFFBOARD];
 491                 }
 492         }
 493 }
 494
 495 static inline hash_t
 496 spatial_hash_one(int rotation, int i, enum stone color)
 497 {
 498         return pthashes[rotation][i][color];
 499 }
 500
 501 inline hash_t
 502 spatial_hash(int rotation, struct spatial *s, int ofs)
 503 {
 504         hash_t h = 0;
 505         for (int i = ofs; i < ptind[s->dist + 1]; i++) {
 506                 h ^= pthashes[rotation][i][spatial_point_at(*s, i)];
 507         }
 508         return h & spatial_hash_mask;
 509 }
 510
 511 static int
 512 spatial_dict_addc(struct spatial_dict *dict, struct spatial *s)
 513 {
 514         /* Allocate space in 1024 blocks. */
 515 #define SPATIALS_ALLOC 1024
 516         if (!(dict->nspatials % SPATIALS_ALLOC)) {
 517                 dict->spatials = realloc(dict->spatials,
 518                                 (dict->nspatials + SPATIALS_ALLOC)
 519                                 * sizeof(*dict->spatials));
 520         }
 521         dict->spatials[dict->nspatials] = *s;
 522         return dict->nspatials++;
 523 }
 524
 525 static bool
 526 spatial_dict_addh(struct spatial_dict *dict, hash_t hash, int id)
 527 {
 528         if (dict->hash[hash]) {
 529                 dict->collisions++;
 530                 /* Give up, not worth the trouble. */
 531                 return false;
 532         }
 533         dict->hash[hash] = id;
 534         return true;
 535 }
 536
 537 /* Spatial dictionary file format:
 538  * /^#/ - comments
 539  * INDEX RADIUS STONES HASH...
 540  * INDEX: index in the spatial table
 541  * RADIUS: @d of the pattern
 542  * STONES: string of ".XO#" chars
 543  * HASH...: space-separated 18bit hash-table indices for the pattern */
 544
 545 static void
 546 spatial_dict_read(struct spatial_dict *dict, char *buf)
 547 {
 548         /* XXX: We trust the data. Bad data will crash us. */
 549         char *bufp = buf;
 550
 551         int index, radius;
 552         index = strtol(bufp, &bufp, 10);
 553         radius = strtol(bufp, &bufp, 10);
 554         while (isspace(*bufp)) bufp++;
 555
 556         /* Load the stone configuration. */
 557         struct spatial s = { .dist = radius };
 558         int sl = 0;
 559         while (!isspace(*bufp)) {
 560                 s.points[sl / 4] |= char2stone(*bufp++) << (sl % 4);
 561                 sl++;
 562         }
 563         while (isspace(*bufp)) bufp++;
 564
 565         /* Sanity check. */
 566         if (sl != ptind[s.dist + 1]) {
 567                 fprintf(stderr, "Spatial dictionary: Invalid number of stones (%d != %d) on this line: %s\n",
 568                         sl, ptind[radius + 1] - 1, buf);
 569                 exit(EXIT_FAILURE);
 570         }
 571
 572         /* Add to collection. */
 573         int id = spatial_dict_addc(dict, &s);
 574
 575         /* Add to specified hash places. */
 576         while (*bufp) {
 577                 int hash = strtol(bufp, &bufp, 16);
 578                 while (isspace(*bufp)) bufp++;
 579                 spatial_dict_addh(dict, hash & spatial_hash_mask, id);
 580         }
 581 }
 582
 583 static char *
 584 spatial2str(struct spatial *s)
 585 {
 586         static char buf[1024];
 587         for (int i = 0; i < ptind[s->dist + 1]; i++) {
 588                 buf[i] = stone2char(spatial_point_at(*s, i));
 589         }
 590         buf[ptind[s->dist + 1]] = 0;
 591         return buf;
 592 }
 593
 594 static void
 595 spatial_dict_write(struct spatial_dict *dict, int id, FILE *f)
 596 {
 597         struct spatial *s = &dict->spatials[id];
 598         fprintf(f, "%d %d ", id, s->dist);
 599         fputs(spatial2str(s), f);
 600         for (int r = 0; r < PTH__ROTATIONS; r++)
 601                 fprintf(f, " %"PRIhash"", spatial_hash(r, s, 0));
 602         fputc('\n', f);
 603 }
 604
 605 static void
 606 spatial_dict_load(struct spatial_dict *dict, FILE *f)
 607 {
 608         char buf[1024];
 609         while (fgets(buf, sizeof(buf), f)) {
 610                 if (buf[0] == '#') continue;
 611                 spatial_dict_read(dict, buf);
 612         }
 613 }
 614
 615 struct spatial_dict *
 616 spatial_dict_init(bool will_append)
 617 {
 618         static const char *filename = "patterns.spat";
 619         FILE *f = fopen(filename, "r");
 620         if (!f && !will_append) {
 621                 if (DEBUGL(1))
 622                         fprintf(stderr, "No spatial dictionary, will not match spatial pattern features.\n");
 623                 return NULL;
 624         }
 625
 626         struct spatial_dict *dict = calloc(1, sizeof(*dict));
 627         /* We create a dummy record for index 0 that we will
 628          * never reference. This is so that hash value 0 can
 629          * represent "no value". */
 630         struct spatial dummy = { .dist = 0 };
 631         spatial_dict_addc(dict, &dummy);
 632
 633         if (f) {
 634                 /* Existing file. Load it up! */
 635                 spatial_dict_load(dict, f);
 636                 fclose(f); f = NULL;
 637                 if (will_append)
 638                         f = fopen(filename, "a");
 639         } else {
 640                 assert(will_append);
 641                 f = fopen(filename, "a");
 642                 /* New file. First, create a comment describing order
 643                  * of points in the array. This is just for purposes
 644                  * of external tools, Pachi never interprets it itself. */
 645                 fprintf(f, "# Pachi spatial patterns dictionary v1.0 maxdist %d\n",
 646                         MAX_PATTERN_DIST);
 647                 for (int d = 0; d < MAX_PATTERN_DIST; d++) {
 648                         fprintf(f, "# Point order: d=%d ", d);
 649                         for (int j = ptind[d]; j < ptind[d + 1]; j++) {
 650                                 fprintf(f, "%d,%d ", ptcoords[j].x, ptcoords[j].y);
 651                         }
 652                         fprintf(f, "\n");
 653                 }
 654         }
 655
 656         dict->f = f;
 657         return dict;
 658 }
 659
 660 int
 661 spatial_dict_get(struct spatial_dict *dict, struct spatial *s, hash_t hash)
 662 {
 663         int id = dict->hash[hash];
 664         if (id && dict->spatials[id].dist != s->dist) {
 665                 if (DEBUGL(6))
 666                         fprintf(stderr, "Collision dist %d vs %d (hash [%d]%"PRIhash")\n",
 667                                 s->dist, dict->spatials[id].dist, id, hash);
 668                 return 0;
 669         }
 670         return id;
 671 }
 672
 673 int
 674 spatial_dict_put(struct spatial_dict *dict, struct spatial *s, hash_t h)
 675 {
 676         int id = spatial_dict_get(dict, s, h);
 677         if (id > 0) {
 678                 /* Check for collisions in append mode. */
 679                 /* Tough job, we simply try if any other rotation
 680                  * is also covered by the existing record. */
 681                 int r; hash_t rhash; int rid;
 682                 for (r = 1; r < PTH__ROTATIONS; r++) {
 683                         rhash = spatial_hash(r, s, 0);
 684                         rid = dict->hash[rhash];
 685                         if (rid != id)
 686                                 goto collision;
 687                 }
 688                 /* All rotations match, id is good to go! */
 689                 return id;
 690
 691 collision:
 692                 if (DEBUGL(1))
 693                         fprintf(stderr, "Collision %d vs %d (hash %d:%"PRIhash")\n",
 694                                 id, dict->nspatials, r, h);
 695                 id = 0;
 696                 /* dict->collisions++; gets done by addh */
 697         }
 698
 699         /* Add new pattern! */
 700         id = spatial_dict_addc(dict, s);
 701         for (int r = 0; r < PTH__ROTATIONS; r++)
 702                 spatial_dict_addh(dict, spatial_hash(r, s, 0), id);
 703         spatial_dict_write(dict, id, dict->f);
 704         return id;
 705 }