patternsp.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 "patternsp.h"
  12
  13 /* Mapping from point sequence to coordinate offsets (to determine
  14  * coordinates relative to pattern center). The array is ordered
  15  * in the gridcular metric order so that we can go through it
  16  * and incrementally match spatial features in nested circles.
  17  * Within one circle, coordinates are ordered by rows to keep
  18  * good cache behavior. */
  19 struct ptcoord ptcoords[MAX_PATTERN_AREA];
  20
  21 /* For each radius, starting index in ptcoords[]. */
  22 unsigned int ptind[MAX_PATTERN_DIST + 2];
  23
  24 /* ptcoords[], ptind[] setup */
  25 static void
  26 ptcoords_init(void)
  27 {
  28         int i = 0; /* Indexing ptcoords[] */
  29
  30         /* First, center point. */
  31         ptind[0] = ptind[1] = 0;
  32         ptcoords[i].x = ptcoords[i].y = 0; i++;
  33
  34         for (int d = 2; d <= MAX_PATTERN_DIST; d++) {
  35                 ptind[d] = i;
  36                 /* For each y, examine all integer solutions
  37                  * of d = |x| + |y| + max(|x|, |y|). */
  38                 /* TODO: (Stern, 2006) uses a hand-modified
  39                  * circles that are finer for small d and more
  40                  * coarse for large d. */
  41                 for (short y = d / 2; y >= 0; y--) {
  42                         short x;
  43                         if (y > d / 3) {
  44                                 /* max(|x|, |y|) = |y|, non-zero x */
  45                                 x = d - y * 2;
  46                                 if (x + y * 2 != d) continue;
  47                         } else {
  48                                 /* max(|x|, |y|) = |x| */
  49                                 /* Or, max(|x|, |y|) = |y| and x is zero */
  50                                 x = (d - y) / 2;
  51                                 if (x * 2 + y != d) continue;
  52                         }
  53
  54                         assert((x > y ? x : y) + x + y == d);
  55
  56                         ptcoords[i].x = x; ptcoords[i].y = y; i++;
  57                         if (x != 0) { ptcoords[i].x = -x; ptcoords[i].y = y; i++; }
  58                         if (y != 0) { ptcoords[i].x = x; ptcoords[i].y = -y; i++; }
  59                         if (x != 0 && y != 0) { ptcoords[i].x = -x; ptcoords[i].y = -y; i++; }
  60                 }
  61         }
  62         ptind[MAX_PATTERN_DIST + 1] = i;
  63
  64 #if 0
  65         for (int d = 0; d <= MAX_PATTERN_DIST; d++) {
  66                 fprintf(stderr, "d=%d (%d) ", d, ptind[d]);
  67                 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
  68                         fprintf(stderr, "%d,%d ", ptcoords[j].x, ptcoords[j].y);
  69                 }
  70                 fprintf(stderr, "\n");
  71         }
  72 #endif
  73 }
  74
  75
  76 /* Zobrist hashes used for points in patterns. */
  77 hash_t pthashes[PTH__ROTATIONS][MAX_PATTERN_AREA][S_MAX];
  78
  79 static void
  80 pthashes_init(void)
  81 {
  82         /* We need fixed hashes for all pattern-relative in
  83          * all pattern users! This is a simple way to generate
  84          * hopefully good ones. Park-Miller powa. :) */
  85
  86         /* We create a virtual board (centered at the sequence start),
  87          * plant the hashes there, then pick them up into the sequence
  88          * with correct coordinates. It would be possible to generate
  89          * the sequence point hashes directly, but the rotations would
  90          * make for enormous headaches. */
  91 #define PATTERN_BOARD_SIZE ((MAX_PATTERN_DIST + 1) * (MAX_PATTERN_DIST + 1))
  92         hash_t pthboard[PATTERN_BOARD_SIZE][4];
  93         int pthbc = PATTERN_BOARD_SIZE / 2; // tengen coord
  94
  95         /* The magic numbers are tuned for minimal collisions. */
  96         hash_t h1 = 0xd6d6d6d1;
  97         hash_t h2 = 0xd6d6d6d2;
  98         hash_t h3 = 0xd6d6d6d3;
  99         hash_t h4 = 0xd6d6d6d4;
 100 #if 0
 101         /* TODO: Uncomment this version the next time we are regenerating
 102          * our pattern base. It should result in less collisions. */
 103         for (int i = 1; i < PATTERN_BOARD_SIZE; i++) {
 104                 pthboard[i][S_NONE] = (h1 = h1 * 16787);
 105                 pthboard[i][S_BLACK] = (h2 = h2 * 16823);
 106                 pthboard[i][S_WHITE] = (h3 = h3 * 16811 - 13);
 107                 pthboard[i][S_OFFBOARD] = (h4 = h4 * 16811);
 108         }
 109         hash_t hs = 0xc3f;
 110         for (int i = 1; i < PATTERN_BOARD_SIZE; i++) {
 111                 hs = hs * 16783;
 112                 pthboard[i][S_NONE] = (pthboard[i][S_NONE] >> (hs % 64)) | (pthboard[i][S_NONE] << (64 - hs % 64));
 113                 hs = hs * 16783;
 114                 pthboard[i][S_BLACK] = (pthboard[i][S_BLACK] >> (hs % 64)) | (pthboard[i][S_BLACK] << (64 - hs % 64));
 115                 hs = hs * 16783;
 116                 pthboard[i][S_WHITE] = (pthboard[i][S_WHITE] >> (hs % 64)) | (pthboard[i][S_WHITE] << (64 - hs % 64));
 117                 hs = hs * 16783;
 118                 pthboard[i][S_OFFBOARD] = (pthboard[i][S_OFFBOARD] >> (hs % 64)) | (pthboard[i][S_OFFBOARD] << (64 - hs % 64));
 119         }
 120 #else
 121         for (int i = 0; i < PATTERN_BOARD_SIZE; i++) {
 122                 pthboard[i][S_NONE] = (h1 = h1 * 16787);
 123                 pthboard[i][S_BLACK] = (h2 = h2 * 16823);
 124                 pthboard[i][S_WHITE] = (h3 = h3 * 16811 - 13);
 125                 pthboard[i][S_OFFBOARD] = (h4 = h4 * 16811);
 126         }
 127 #endif
 128
 129         /* Virtual board with hashes created, now fill
 130          * pthashes[] with hashes for points in actual
 131          * sequences, also considering various rotations. */
 132 #define PTH_VMIRROR     1
 133 #define PTH_HMIRROR     2
 134 #define PTH_90ROT       4
 135         for (int r = 0; r < PTH__ROTATIONS; r++) {
 136                 for (int i = 0; i < MAX_PATTERN_AREA; i++) {
 137                         /* Rotate appropriately. */
 138                         int rx = ptcoords[i].x;
 139                         int ry = ptcoords[i].y;
 140                         if (r & PTH_VMIRROR) ry = -ry;
 141                         if (r & PTH_HMIRROR) rx = -rx;
 142                         if (r & PTH_90ROT) {
 143                                 int rs = rx; rx = -ry; ry = rs;
 144                         }
 145                         int bi = pthbc + ry * (MAX_PATTERN_DIST + 1) + rx;
 146
 147                         /* Copy info. */
 148                         pthashes[r][i][S_NONE] = pthboard[bi][S_NONE];
 149                         pthashes[r][i][S_BLACK] = pthboard[bi][S_BLACK];
 150                         pthashes[r][i][S_WHITE] = pthboard[bi][S_WHITE];
 151                         pthashes[r][i][S_OFFBOARD] = pthboard[bi][S_OFFBOARD];
 152                 }
 153         }
 154 }
 155
 156 static void __attribute__((constructor))
 157 spatial_init(void)
 158 {
 159         /* Initialization of various static data structures for
 160          * fast pattern processing. */
 161         ptcoords_init();
 162         pthashes_init();
 163 }
 164
 165 inline hash_t
 166 spatial_hash(unsigned int rotation, struct spatial *s)
 167 {
 168         hash_t h = 0;
 169         for (unsigned int i = 0; i < ptind[s->dist + 1]; i++) {
 170                 h ^= pthashes[rotation][i][spatial_point_at(*s, i)];
 171         }
 172         return h & spatial_hash_mask;
 173 }
 174
 175 char *
 176 spatial2str(struct spatial *s)
 177 {
 178         static char buf[1024];
 179         for (unsigned int i = 0; i < ptind[s->dist + 1]; i++) {
 180                 buf[i] = stone2char(spatial_point_at(*s, i));
 181         }
 182         buf[ptind[s->dist + 1]] = 0;
 183         return buf;
 184 }
 185
 186 void
 187 spatial_from_board(struct pattern_config *pc, struct spatial *s,
 188                    struct board *b, struct move *m)
 189 {
 190         assert(pc->spat_min > 0);
 191
 192         /* We record all spatial patterns black-to-play; simply
 193          * reverse all colors if we are white-to-play. */
 194         static enum stone bt_black[4] = { S_NONE, S_BLACK, S_WHITE, S_OFFBOARD };
 195         static enum stone bt_white[4] = { S_NONE, S_WHITE, S_BLACK, S_OFFBOARD };
 196         enum stone (*bt)[4] = m->color == S_WHITE ? &bt_white : &bt_black;
 197
 198         memset(s, 0, sizeof(*s));
 199         for (unsigned int j = 0; j < ptind[pc->spat_max + 1]; j++) {
 200                 ptcoords_at(x, y, m->coord, b, j);
 201                 s->points[j / 4] |= (*bt)[board_atxy(b, x, y)] << ((j % 4) * 2);
 202         }
 203         s->dist = pc->spat_max;
 204 }
 205
 206 /* Compare two spatials, allowing for differences up to isomorphism.
 207  * True means the spatials are equivalent. */
 208 static bool
 209 spatial_cmp(struct spatial *s1, struct spatial *s2)
 210 {
 211         /* Quick preliminary check. */
 212         if (s1->dist != s2->dist)
 213                 return false;
 214
 215         /* We could create complex transposition tables, but it seems most
 216          * foolproof to just check if the sets of rotation hashes are the
 217          * same for both. */
 218         hash_t s1r[PTH__ROTATIONS];
 219         for (unsigned int r = 0; r < PTH__ROTATIONS; r++)
 220                 s1r[r] = spatial_hash(r, s1);
 221         for (unsigned int r = 0; r < PTH__ROTATIONS; r++) {
 222                 hash_t s2r = spatial_hash(r, s2);
 223                 for (unsigned int p = 0; p < PTH__ROTATIONS; p++)
 224                         if (s2r == s1r[p])
 225                                 goto found_rot;
 226                 /* Rotation hash s2r does not correspond to s1r. */
 227                 return false;
 228 found_rot:;
 229         }
 230
 231         /* All rotation hashes of s2 occur in s1. Hopefully that
 232          * indicates something. */
 233         return true;
 234 }
 235
 236
 237 /* Spatial dict manipulation. */
 238
 239 static unsigned int
 240 spatial_dict_addc(struct spatial_dict *dict, struct spatial *s)
 241 {
 242         /* Allocate space in 1024 blocks. */
 243 #define SPATIALS_ALLOC 1024
 244         if (!(dict->nspatials % SPATIALS_ALLOC)) {
 245                 dict->spatials = realloc(dict->spatials,
 246                                 (dict->nspatials + SPATIALS_ALLOC)
 247                                 * sizeof(*dict->spatials));
 248         }
 249         dict->spatials[dict->nspatials] = *s;
 250         return dict->nspatials++;
 251 }
 252
 253 bool
 254 spatial_dict_addh(struct spatial_dict *dict, hash_t hash, unsigned int id)
 255 {
 256         if (dict->hash[hash]) {
 257                 if (dict->hash[hash] != id)
 258                         dict->collisions++;
 259         } else {
 260                 dict->fills++;
 261         }
 262         dict->hash[hash] = id;
 263         return true;
 264 }
 265
 266 /* Spatial dictionary file format:
 267  * /^#/ - comments
 268  * INDEX RADIUS STONES HASH...
 269  * INDEX: index in the spatial table
 270  * RADIUS: @d of the pattern
 271  * STONES: string of ".XO#" chars
 272  * HASH...: space-separated 18bit hash-table indices for the pattern */
 273
 274 static void
 275 spatial_dict_read(struct spatial_dict *dict, char *buf, bool hash)
 276 {
 277         /* XXX: We trust the data. Bad data will crash us. */
 278         char *bufp = buf;
 279
 280         unsigned int index, radius;
 281         index = strtoul(bufp, &bufp, 10);
 282         radius = strtoul(bufp, &bufp, 10);
 283         while (isspace(*bufp)) bufp++;
 284
 285         if (radius > MAX_PATTERN_DIST) {
 286                 /* Too large spatial, skip. */
 287                 struct spatial s = { .dist = 0 };
 288                 unsigned int id = spatial_dict_addc(dict, &s);
 289                 assert(id == index);
 290                 return;
 291         }
 292
 293         /* Load the stone configuration. */
 294         struct spatial s = { .dist = radius };
 295         unsigned int sl = 0;
 296         while (!isspace(*bufp)) {
 297                 s.points[sl / 4] |= char2stone(*bufp++) << ((sl % 4)*2);
 298                 sl++;
 299         }
 300         while (isspace(*bufp)) bufp++;
 301
 302         /* Sanity check. */
 303         if (sl != ptind[s.dist + 1]) {
 304                 fprintf(stderr, "Spatial dictionary: Invalid number of stones (%d != %d) on this line: %s\n",
 305                         sl, ptind[radius + 1] - 1, buf);
 306                 exit(EXIT_FAILURE);
 307         }
 308
 309         /* Add to collection. */
 310         unsigned int id = spatial_dict_addc(dict, &s);
 311         assert(id == index);
 312
 313         /* Add to specified hash places. */
 314         if (hash)
 315                 for (unsigned int r = 0; r < PTH__ROTATIONS; r++)
 316                         spatial_dict_addh(dict, spatial_hash(r, &s), id);
 317 }
 318
 319 void
 320 spatial_write(struct spatial_dict *dict, struct spatial *s, unsigned int id, FILE *f)
 321 {
 322         fprintf(f, "%d %d ", id, s->dist);
 323         fputs(spatial2str(s), f);
 324         for (unsigned int r = 0; r < PTH__ROTATIONS; r++) {
 325                 hash_t rhash = spatial_hash(r, s);
 326                 unsigned int id2 = dict->hash[rhash];
 327                 if (id2 != id) {
 328                         /* This hash does not belong to us. Decide whether
 329                          * we or the current owner is better owner. */
 330                         /* TODO: Compare also # of patternscan encounters? */
 331                         struct spatial *s2 = &dict->spatials[id2];
 332                         if (s2->dist < s->dist)
 333                                 continue;
 334                         if (s2->dist == s->dist && id2 < id)
 335                                 continue;
 336                 }
 337                 fprintf(f, " %"PRIhash"", spatial_hash(r, s));
 338         }
 339         fputc('\n', f);
 340 }
 341
 342 static void
 343 spatial_dict_load(struct spatial_dict *dict, FILE *f, bool hash)
 344 {
 345         char buf[1024];
 346         while (fgets(buf, sizeof(buf), f)) {
 347                 if (buf[0] == '#') continue;
 348                 spatial_dict_read(dict, buf, hash);
 349         }
 350         if (DEBUGL(1)) {
 351                 fprintf(stderr, "Loaded spatial dictionary of %d patterns.\n", dict->nspatials);
 352                 if (hash)
 353                         spatial_dict_hashstats(dict);
 354         }
 355 }
 356
 357 void
 358 spatial_dict_hashstats(struct spatial_dict *dict)
 359 {
 360         /* m hash size, n number of patterns; is zobrist universal hash?
 361          *
 362          * Not so rigorous analysis, but it should give a good approximation:
 363          * Probability of empty bucket is (1-1/m)^n ~ e^(-n/m)
 364          * Probability of non-empty bucket is 1-e^(-n/m)
 365          * Expected number of non-empty buckets is m*(1-e^(-n/m))
 366          * Number of collisions is n-m*(1-e^(-n/m)). */
 367
 368         /* The result: Reality matches these expectations pretty well!
 369          *
 370          * Actual:
 371          *      Loaded spatial dictionary of 1064482 patterns.
 372          *      (Spatial dictionary hash: 513997 collisions (incl. repetitions), 11.88% (7970033/67108864) fill rate).
 373          *
 374          * Theoretical:
 375          *      m = 2^26
 376          *      n <= 8*1064482 (some patterns may have some identical rotations)
 377          *      n = 513997+7970033 = 8484030 should be the correct number
 378          *      n-m*(1-e^(-n/m)) = 514381
 379          *
 380          * To verify, make sure to turn patternprob off (e.g. use
 381          * -e patternscan), since it will insert a pattern multiple times,
 382          * multiplying the reported number of collisions. */
 383
 384         unsigned long buckets = (sizeof(dict->hash) / sizeof(dict->hash[0]));
 385         fprintf(stderr, "\t(Spatial dictionary hash: %d collisions (incl. repetitions), %.2f%% (%d/%lu) fill rate).\n",
 386                         dict->collisions,
 387                         (double) dict->fills * 100 / buckets,
 388                         dict->fills, buckets);
 389 }
 390
 391 void
 392 spatial_dict_writeinfo(struct spatial_dict *dict, FILE *f)
 393 {
 394         /* New file. First, create a comment describing order
 395          * of points in the array. This is just for purposes
 396          * of external tools, Pachi never interprets it itself. */
 397         fprintf(f, "# Pachi spatial patterns dictionary v1.0 maxdist %d\n",
 398                 MAX_PATTERN_DIST);
 399         for (unsigned int d = 0; d <= MAX_PATTERN_DIST; d++) {
 400                 fprintf(f, "# Point order: d=%d ", d);
 401                 for (unsigned int j = ptind[d]; j < ptind[d + 1]; j++) {
 402                         fprintf(f, "%d,%d ", ptcoords[j].x, ptcoords[j].y);
 403                 }
 404                 fprintf(f, "\n");
 405         }
 406 }
 407
 408 /* We try to avoid needlessly reloading spatial dictionary
 409  * since it may take rather long time. */
 410 static struct spatial_dict *cached_dict;
 411
 412 const char *spatial_dict_filename = "patterns.spat";
 413 struct spatial_dict *
 414 spatial_dict_init(bool will_append, bool hash)
 415 {
 416         if (cached_dict && !will_append)
 417                 return cached_dict;
 418
 419         FILE *f = fopen(spatial_dict_filename, "r");
 420         if (!f && !will_append) {
 421                 if (DEBUGL(1))
 422                         fprintf(stderr, "No spatial dictionary, will not match spatial pattern features.\n");
 423                 return NULL;
 424         }
 425
 426         struct spatial_dict *dict = calloc2(1, sizeof(*dict));
 427         /* We create a dummy record for index 0 that we will
 428          * never reference. This is so that hash value 0 can
 429          * represent "no value". */
 430         struct spatial dummy = { .dist = 0 };
 431         spatial_dict_addc(dict, &dummy);
 432
 433         if (f) {
 434                 spatial_dict_load(dict, f, hash);
 435                 fclose(f); f = NULL;
 436         } else {
 437                 assert(will_append);
 438         }
 439
 440         cached_dict = dict;
 441         return dict;
 442 }
 443
 444 unsigned int
 445 spatial_dict_put(struct spatial_dict *dict, struct spatial *s, hash_t h)
 446 {
 447         /* We avoid spatial_dict_get() here, since we want to ignore radius
 448          * differences - we have custom collision detection. */
 449         unsigned int id = dict->hash[h];
 450         if (id > 0) {
 451                 /* Is this the same or isomorphous spatial? */
 452                 if (spatial_cmp(s, &dict->spatials[id]))
 453                         return id;
 454
 455                 /* Look a bit harder - perhaps one of our rotations still
 456                  * points at the correct spatial. */
 457                 for (unsigned int r = 0; r < PTH__ROTATIONS; r++) {
 458                         hash_t rhash = spatial_hash(r, s);
 459                         unsigned int rid = dict->hash[rhash];
 460                         /* No match means we definitely aren't stored yet. */
 461                         if (!rid)
 462                                 break;
 463                         if (id != rid && spatial_cmp(s, &dict->spatials[rid])) {
 464                                 /* Yay, this is us! */
 465                                 if (DEBUGL(3))
 466                                         fprintf(stderr, "Repeated collision %d vs %d\n", id, rid);
 467                                 id = rid;
 468                                 /* Point the hashes back to us. */
 469                                 goto hash_store;
 470                         }
 471                 }
 472
 473                 if (DEBUGL(1))
 474                         fprintf(stderr, "Collision %d vs %d\n", id, dict->nspatials);
 475                 id = 0;
 476                 /* dict->collisions++; gets done by addh */
 477         }
 478
 479         /* Add new pattern! */
 480         id = spatial_dict_addc(dict, s);
 481         if (DEBUGL(4)) {
 482                 fprintf(stderr, "new spat %d(%d) %s <%"PRIhash"> ", id, s->dist, spatial2str(s), h);
 483                 for (unsigned int r = 0; r < 8; r++)
 484                         fprintf(stderr,"[%"PRIhash"] ", spatial_hash(r, s));
 485                 fprintf(stderr, "\n");
 486         }
 487
 488         /* Store new pattern in the hash. */
 489 hash_store:
 490         for (unsigned int r = 0; r < PTH__ROTATIONS; r++)
 491                 spatial_dict_addh(dict, spatial_hash(r, s), id);
 492
 493         return id;
 494 }