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 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. */
  40                 for (short y = d / 2; y >= 0; y--) {
  41                         short x;
  42                         if (y > d / 3) {
  43                                 /* max(|x|, |y|) = |y|, non-zero x */
  44                                 x = d - y * 2;
  45                                 if (x + y * 2 != d) continue;
  46                         } else {
  47                                 /* max(|x|, |y|) = |x| */
  48                                 /* Or, max(|x|, |y|) = |y| and x is zero */
  49                                 x = (d - y) / 2;
  50                                 if (x * 2 + y != d) continue;
  51                         }
  52
  53                         assert((x > y ? x : y) + x + y == d);
  54
  55                         ptcoords[i].x = x; ptcoords[i].y = y; i++;
  56                         if (x != 0) { ptcoords[i].x = -x; ptcoords[i].y = y; i++; }
  57                         if (y != 0) { ptcoords[i].x = x; ptcoords[i].y = -y; i++; }
  58                         if (x != 0 && y != 0) { ptcoords[i].x = -x; ptcoords[i].y = -y; i++; }
  59                 }
  60         }
  61         ptind[MAX_PATTERN_DIST + 1] = i;
  62
  63 #if 0
  64         for (int d = 0; d <= MAX_PATTERN_DIST; d++) {
  65                 fprintf(stderr, "d=%d (%d) ", d, ptind[d]);
  66                 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
  67                         fprintf(stderr, "%d,%d ", ptcoords[j].x, ptcoords[j].y);
  68                 }
  69                 fprintf(stderr, "\n");
  70         }
  71 #endif
  72 }
  73
  74
  75 /* Zobrist hashes used for points in patterns. */
  76 hash_t pthashes[PTH__ROTATIONS][MAX_PATTERN_AREA][S_MAX];
  77
  78 static void
  79 pthashes_init(void)
  80 {
  81         /* We need fixed hashes for all pattern-relative in
  82          * all pattern users! This is a simple way to generate
  83          * hopefully good ones. Park-Miller powa. :) */
  84
  85         /* We create a virtual board (centered at the sequence start),
  86          * plant the hashes there, then pick them up into the sequence
  87          * with correct coordinates. It would be possible to generate
  88          * the sequence point hashes directly, but the rotations would
  89          * make for enormous headaches. */
  90         hash_t pthboard[MAX_PATTERN_AREA][4];
  91         int pthbc = MAX_PATTERN_AREA / 2; // tengen coord
  92
  93         /* The magic numbers are tuned for minimal collisions. */
  94         hash_t h = 0x313131;
  95         for (int i = 0; i < MAX_PATTERN_AREA; i++) {
  96                 pthboard[i][S_NONE] = (h = h * 16803 - 7);
  97                 pthboard[i][S_BLACK] = (h = h * 16805 + 7);
  98                 pthboard[i][S_WHITE] = (h = h * 16807 + 3);
  99                 pthboard[i][S_OFFBOARD] = (h = h * 16809 - 3);
 100         }
 101
 102         /* Virtual board with hashes created, now fill
 103          * pthashes[] with hashes for points in actual
 104          * sequences, also considering various rotations. */
 105 #define PTH_VMIRROR     1
 106 #define PTH_HMIRROR     2
 107 #define PTH_90ROT       4
 108         for (int r = 0; r < PTH__ROTATIONS; r++) {
 109                 for (int i = 0; i < MAX_PATTERN_AREA; i++) {
 110                         /* Rotate appropriately. */
 111                         int rx = ptcoords[i].x;
 112                         int ry = ptcoords[i].y;
 113                         if (r & PTH_VMIRROR) ry = -ry;
 114                         if (r & PTH_HMIRROR) rx = -rx;
 115                         if (r & PTH_90ROT) {
 116                                 int rs = rx; rx = -ry; ry = rs;
 117                         }
 118                         int bi = pthbc + ry * MAX_PATTERN_DIST + rx;
 119
 120                         /* Copy info. */
 121                         pthashes[r][i][S_NONE] = pthboard[bi][S_NONE];
 122                         pthashes[r][i][S_BLACK] = pthboard[bi][S_BLACK];
 123                         pthashes[r][i][S_WHITE] = pthboard[bi][S_WHITE];
 124                         pthashes[r][i][S_OFFBOARD] = pthboard[bi][S_OFFBOARD];
 125                 }
 126         }
 127 }
 128
 129 static void __attribute__((constructor))
 130 spatial_init(void)
 131 {
 132         /* Initialization of various static data structures for
 133          * fast pattern processing. */
 134         ptcoords_init();
 135         pthashes_init();
 136 }
 137
 138 inline hash_t
 139 spatial_hash(int rotation, struct spatial *s)
 140 {
 141         hash_t h = 0;
 142         for (int i = 0; i < ptind[s->dist + 1]; i++) {
 143                 h ^= pthashes[rotation][i][spatial_point_at(*s, i)];
 144         }
 145         return h & spatial_hash_mask;
 146 }
 147
 148 char *
 149 spatial2str(struct spatial *s)
 150 {
 151         static char buf[1024];
 152         for (int i = 0; i < ptind[s->dist + 1]; i++) {
 153                 buf[i] = stone2char(spatial_point_at(*s, i));
 154         }
 155         buf[ptind[s->dist + 1]] = 0;
 156         return buf;
 157 }
 158
 159 void
 160 spatial_from_board(struct pattern_config *pc, struct spatial *s,
 161                    struct board *b, struct move *m)
 162 {
 163         assert(pc->spat_min > 0);
 164
 165         /* We record all spatial patterns black-to-play; simply
 166          * reverse all colors if we are white-to-play. */
 167         static enum stone bt_black[4] = { S_NONE, S_BLACK, S_WHITE, S_OFFBOARD };
 168         static enum stone bt_white[4] = { S_NONE, S_WHITE, S_BLACK, S_OFFBOARD };
 169         enum stone (*bt)[4] = m->color == S_WHITE ? &bt_white : &bt_black;
 170
 171         memset(s, 0, sizeof(*s));
 172         for (int j = 0; j < ptind[pc->spat_max + 1]; j++) {
 173                 ptcoords_at(x, y, m->coord, b, j);
 174                 s->points[j / 4] |= (*bt)[board_atxy(b, x, y)] << ((j % 4) * 2);
 175         }
 176         s->dist = pc->spat_max;
 177 }
 178
 179 /* Compare two spatials, allowing for differences up to isomorphism.
 180  * True means the spatials are equivalent. */
 181 static bool
 182 spatial_cmp(struct spatial *s1, struct spatial *s2)
 183 {
 184         /* Quick preliminary check. */
 185         if (s1->dist != s2->dist)
 186                 return false;
 187
 188         /* We could create complex transposition tables, but it seems most
 189          * foolproof to just check if the sets of rotation hashes are the
 190          * same for both. */
 191         hash_t s1r[PTH__ROTATIONS];
 192         for (int r = 0; r < PTH__ROTATIONS; r++)
 193                 s1r[r] = spatial_hash(r, s1);
 194         for (int r = 0; r < PTH__ROTATIONS; r++) {
 195                 hash_t s2r = spatial_hash(r, s2);
 196                 for (int p = 0; p < PTH__ROTATIONS; p++)
 197                         if (s2r == s1r[p])
 198                                 goto found_rot;
 199                 /* Rotation hash s2r does not correspond to s1r. */
 200                 return false;
 201 found_rot:;
 202         }
 203
 204         /* All rotation hashes of s2 occur in s1. Hopefully that
 205          * indicates something. */
 206         return true;
 207 }
 208
 209
 210 /* Spatial dict manipulation. */
 211
 212 static unsigned int
 213 spatial_dict_addc(struct spatial_dict *dict, struct spatial *s)
 214 {
 215         /* Allocate space in 1024 blocks. */
 216 #define SPATIALS_ALLOC 1024
 217         if (!(dict->nspatials % SPATIALS_ALLOC)) {
 218                 dict->spatials = realloc(dict->spatials,
 219                                 (dict->nspatials + SPATIALS_ALLOC)
 220                                 * sizeof(*dict->spatials));
 221         }
 222         dict->spatials[dict->nspatials] = *s;
 223         return dict->nspatials++;
 224 }
 225
 226 static bool
 227 spatial_dict_addh(struct spatial_dict *dict, hash_t hash, unsigned int id)
 228 {
 229         if (dict->hash[hash] && dict->hash[hash] != id)
 230                 dict->collisions++;
 231         dict->hash[hash] = id;
 232         return true;
 233 }
 234
 235 /* Spatial dictionary file format:
 236  * /^#/ - comments
 237  * INDEX RADIUS STONES HASH...
 238  * INDEX: index in the spatial table
 239  * RADIUS: @d of the pattern
 240  * STONES: string of ".XO#" chars
 241  * HASH...: space-separated 18bit hash-table indices for the pattern */
 242
 243 static void
 244 spatial_dict_read(struct spatial_dict *dict, char *buf)
 245 {
 246         /* XXX: We trust the data. Bad data will crash us. */
 247         char *bufp = buf;
 248
 249         int index, radius;
 250         index = strtol(bufp, &bufp, 10);
 251         radius = strtol(bufp, &bufp, 10);
 252         while (isspace(*bufp)) bufp++;
 253
 254         /* Load the stone configuration. */
 255         struct spatial s = { .dist = radius };
 256         int sl = 0;
 257         while (!isspace(*bufp)) {
 258                 s.points[sl / 4] |= char2stone(*bufp++) << ((sl % 4)*2);
 259                 sl++;
 260         }
 261         while (isspace(*bufp)) bufp++;
 262
 263         /* Sanity check. */
 264         if (sl != ptind[s.dist + 1]) {
 265                 fprintf(stderr, "Spatial dictionary: Invalid number of stones (%d != %d) on this line: %s\n",
 266                         sl, ptind[radius + 1] - 1, buf);
 267                 exit(EXIT_FAILURE);
 268         }
 269
 270         /* Add to collection. */
 271         unsigned int id = spatial_dict_addc(dict, &s);
 272
 273         /* Add to specified hash places. */
 274         while (*bufp) {
 275                 int hash = strtol(bufp, &bufp, 16);
 276                 while (isspace(*bufp)) bufp++;
 277                 spatial_dict_addh(dict, hash & spatial_hash_mask, id);
 278         }
 279 }
 280
 281 void
 282 spatial_write(struct spatial_dict *dict, struct spatial *s, int id, FILE *f)
 283 {
 284         fprintf(f, "%d %d ", id, s->dist);
 285         fputs(spatial2str(s), f);
 286         for (int r = 0; r < PTH__ROTATIONS; r++) {
 287                 hash_t rhash = spatial_hash(r, s);
 288                 int id2 = dict->hash[rhash];
 289                 if (id2 != id) {
 290                         /* This hash does not belong to us. Decide whether
 291                          * we or the current owner is better owner. */
 292                         /* TODO: Compare also # of patternscan encounters? */
 293                         struct spatial *s2 = &dict->spatials[id2];
 294                         if (s2->dist < s->dist)
 295                                 continue;
 296                         if (s2->dist == s->dist && id2 < id)
 297                                 continue;
 298                 }
 299                 fprintf(f, " %"PRIhash"", spatial_hash(r, s));
 300         }
 301         fputc('\n', f);
 302 }
 303
 304 static void
 305 spatial_dict_load(struct spatial_dict *dict, FILE *f)
 306 {
 307         char buf[1024];
 308         while (fgets(buf, sizeof(buf), f)) {
 309                 if (buf[0] == '#') continue;
 310                 spatial_dict_read(dict, buf);
 311         }
 312 }
 313
 314 void
 315 spatial_dict_writeinfo(struct spatial_dict *dict, FILE *f)
 316 {
 317         /* New file. First, create a comment describing order
 318          * of points in the array. This is just for purposes
 319          * of external tools, Pachi never interprets it itself. */
 320         fprintf(f, "# Pachi spatial patterns dictionary v1.0 maxdist %d\n",
 321                 MAX_PATTERN_DIST);
 322         for (int d = 0; d <= MAX_PATTERN_DIST; d++) {
 323                 fprintf(f, "# Point order: d=%d ", d);
 324                 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
 325                         fprintf(f, "%d,%d ", ptcoords[j].x, ptcoords[j].y);
 326                 }
 327                 fprintf(f, "\n");
 328         }
 329 }
 330
 331 const char *spatial_dict_filename = "patterns.spat";
 332 struct spatial_dict *
 333 spatial_dict_init(bool will_append)
 334 {
 335         FILE *f = fopen(spatial_dict_filename, "r");
 336         if (!f && !will_append) {
 337                 if (DEBUGL(1))
 338                         fprintf(stderr, "No spatial dictionary, will not match spatial pattern features.\n");
 339                 return NULL;
 340         }
 341
 342         struct spatial_dict *dict = calloc2(1, sizeof(*dict));
 343         /* We create a dummy record for index 0 that we will
 344          * never reference. This is so that hash value 0 can
 345          * represent "no value". */
 346         struct spatial dummy = { .dist = 0 };
 347         spatial_dict_addc(dict, &dummy);
 348
 349         if (f) {
 350                 spatial_dict_load(dict, f);
 351                 fclose(f); f = NULL;
 352         } else {
 353                 assert(will_append);
 354         }
 355
 356         return dict;
 357 }
 358
 359 int
 360 spatial_dict_put(struct spatial_dict *dict, struct spatial *s, hash_t h)
 361 {
 362         /* We avoid spatial_dict_get() here, since we want to ignore radius
 363          * differences - we have custom collision detection. */
 364         int id = dict->hash[h];
 365         if (id > 0) {
 366                 /* Is this the same or isomorphous spatial? */
 367                 if (spatial_cmp(s, &dict->spatials[id]))
 368                         return id;
 369
 370                 /* Look a bit harder - perhaps one of our rotations still
 371                  * points at the correct spatial. */
 372                 for (int r = 0; r < PTH__ROTATIONS; r++) {
 373                         hash_t rhash = spatial_hash(r, s);
 374                         int rid = dict->hash[rhash];
 375                         /* No match means we definitely aren't stored yet. */
 376                         if (!rid)
 377                                 break;
 378                         if (id != rid && spatial_cmp(s, &dict->spatials[rid])) {
 379                                 /* Yay, this is us! */
 380                                 if (DEBUGL(3))
 381                                         fprintf(stderr, "Repeated collision %d vs %d\n", id, rid);
 382                                 id = rid;
 383                                 /* Point the hashes back to us. */
 384                                 goto hash_store;
 385                         }
 386                 }
 387
 388                 if (DEBUGL(1))
 389                         fprintf(stderr, "Collision %d vs %d\n", id, dict->nspatials);
 390                 id = 0;
 391                 /* dict->collisions++; gets done by addh */
 392         }
 393
 394         /* Add new pattern! */
 395         id = spatial_dict_addc(dict, s);
 396         if (DEBUGL(4)) {
 397                 fprintf(stderr, "new spat %d(%d) %s <%"PRIhash"> ", id, s->dist, spatial2str(s), h);
 398                 for (int r = 0; r < 8; r++)
 399                         fprintf(stderr,"[%"PRIhash"] ", spatial_hash(r, s));
 400                 fprintf(stderr, "\n");
 401         }
 402
 403         /* Store new pattern in the hash. */
 404 hash_store:
 405         for (int r = 0; r < PTH__ROTATIONS; r++)
 406                 spatial_dict_addh(dict, spatial_hash(r, s), id);
 407
 408         return id;
 409 }
 410
 411
 412 /** Pattern3 helpers */
 413
 414 /* XXX: We have hard-coded this point order:
 415  * # Point order: d=1 0,0
 416  * # Point order: d=2 0,1 0,-1 1,0 -1,0
 417  * # Point order: d=3 1,1 -1,1 1,-1 -1,-1
 418  */
 419 /* p3bits describe location of given point in the
 420  * pattern3 hash word. */
 421 static const int p3bits[] = { -1,  1, 6, 3, 4,  0, 2, 5, 7 };
 422
 423
 424 /* XXX: Spatial patterns do not carry the atari informations;
 425  * we just ignore it when converting to spatial, and assume "no atari"
 426  * when converting from spatial. */
 427
 428 static hash_t
 429 pattern3_to_spatial(int r, hash3_t pat3)
 430 {
 431         hash_t h = pthashes[r][0][S_NONE];
 432         for (int i = 1; i < 9; i++)
 433                 h ^= pthashes[r][i][(pat3 >> (p3bits[i] * 2)) & 0x3];
 434         return h & spatial_hash_mask;
 435 }
 436
 437 hash3_t
 438 spatial_to_pattern3(struct spatial *s)
 439 {
 440         assert(s->dist == 3);
 441         int pat3 = 0;
 442         for (int i = 1; i < 9; i++)
 443                 pat3 |= spatial_point_at(*s, i) << (p3bits[i] * 2);
 444         return pat3;
 445 }
 446
 447 hash3_t
 448 pattern3_by_spatial(struct spatial_dict *dict, hash3_t pat3)
 449 {
 450         /* Just pull pat3 through the spatial database to generate
 451          * hash of its canonical form. */
 452         int s;
 453         for (int r = 0; r < PTH__ROTATIONS; r++) {
 454                 hash_t h = pattern3_to_spatial(r, pat3);
 455                 s = spatial_dict_get(dict, 3, h);
 456                 if (s > 0) break;
 457                 /* We might need to try another rotation in case
 458                  * of a collision. */
 459         }
 460         /* XXX: We assume our spatial dictionary is _sane_, that is,
 461          * all valid 3x3 patterns we could encounter are in the
 462          * dictionary. If you hit this assert(), you probably
 463          * generated the spatial dict over too few games; it is best
 464          * to generate it over the same set of games as you match
 465          * patterns on afterwards. */
 466         assert(s > 0);
 467         return spatial_to_pattern3(&dict->spatials[s]);
 468 }