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