patternscan/patternscan.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4
   5 #include "board.h"
   6 #include "debug.h"
   7 #include "engine.h"
   8 #include "move.h"
   9 #include "patternscan/patternscan.h"
  10 #include "pattern.h"
  11 #include "patternsp.h"
  12
  13
  14 /* Internal engine state. */
  15 struct patternscan {
  16         int debug_level;
  17
  18         struct pattern_config pc;
  19         pattern_spec ps;
  20         bool competition;
  21         bool mm;
  22
  23         bool no_pattern_match;
  24         bool gen_spat_dict;
  25         /* Minimal number of occurences for spatial to be saved;
  26          * 3x3 spatials are always saved. */
  27         int spat_threshold;
  28         /* Number of loaded spatials; checkpoint for saving new sids
  29          * in case gen_spat_dict is enabled. */
  30         int loaded_spatials;
  31
  32         /* Book-keeping of spatial occurence count. */
  33         int nscounts;
  34         int *scounts;
  35 };
  36
  37
  38 /* Starting gamma number of each feature. */
  39 static int gammaid[FEAT_MAX + MAX_PATTERN_DIST + 1];
  40 /* For each spatial id, its gamma value. */
  41 static int spatg[65536];
  42 /* Pattern3 hashes sorted by their gamma. */
  43 static int pat3g[65536/8];
  44
  45 /* Print MM-format header - summary of features. Also create patterns.fdict
  46  * containing mapping from gamma numbers to feature:payload pairs. */
  47 static void
  48 mm_header(struct patternscan *ps)
  49 {
  50         FILE *fdict = fopen("patterns.fdict", "w");
  51         if (!fdict) {
  52                 perror("patterns.fdict");
  53                 exit(EXIT_FAILURE);
  54         }
  55
  56         gammaid[0] = 0;
  57         int g = 0;
  58         int features = 0;
  59         for (int i = 0; i < FEAT_MAX; i++) {
  60                 if (ps->ps[i] == 0) {
  61                         /* Feature disabled. */
  62                         /* XXX: Accurately account for payload count
  63                          * of partially disabled features? */
  64                         gammaid[i + 1] = gammaid[i];
  65                         continue;
  66                 }
  67                 if (i == FEAT_SPATIAL) {
  68                         /* Special handling. */
  69                         gammaid[i + 1] = gammaid[i];
  70                         continue;
  71                 }
  72
  73                 features++;
  74
  75                 if (i == FEAT_PATTERN3) {
  76                         /* We need to dynamically allocate gamma numbers
  77                          * of pattern3 hashes, 65536 extra gammas is
  78                          * unbearable. */
  79                         for (int s = 0; s < ps->pc.spat_dict->nspatials; s++) {
  80                                 if (ps->pc.spat_dict->spatials[s].dist != 3)
  81                                         continue;
  82                                 int pat = spatial_to_pattern3(&ps->pc.spat_dict->spatials[s]);
  83                                 struct feature f = { .id = i, .payload = pat };
  84                                 char buf[256] = ""; feature2str(buf, &f);
  85                                 fprintf(fdict, "%d %s\n", g, buf);
  86                                 pat3g[g++ - gammaid[i]] = pat;
  87                         }
  88                         gammaid[i + 1] = g;
  89                         continue;
  90                 }
  91
  92                 gammaid[i + 1] = gammaid[i] + feature_payloads(&ps->pc, i);
  93
  94                 for (int p = 0; p < feature_payloads(&ps->pc, i); p++) {
  95                         struct feature f = { .id = i, .payload = p };
  96                         char buf[256] = ""; feature2str(buf, &f);
  97                         fprintf(fdict, "%d %s\n", g++, buf);
  98                 }
  99                 assert(g == gammaid[i + 1]);
 100         }
 101
 102         /* XXX: We rely on pattern3 being last feature before FEAT_MAX. */
 103
 104         /* We need to break down spatials by their radius, since payloads
 105          * of single feature must be independent. */
 106         if (ps->ps[FEAT_SPATIAL] != 0) {
 107                 for (int d = 0; d <= ps->pc.spat_max - ps->pc.spat_min; d++) {
 108                         for (int i = 0; i < ps->pc.spat_dict->nspatials; i++) {
 109                                 if (ps->pc.spat_dict->spatials[i].dist != ps->pc.spat_min + d)
 110                                         continue;
 111                                 spatg[i] = g++;
 112                                 struct feature f = { .id = FEAT_SPATIAL, .payload = i };
 113                                 char buf[256] = ""; feature2str(buf, &f);
 114                                 fprintf(fdict, "%d %s\n", spatg[i], buf);
 115                         }
 116                         features++;
 117                         gammaid[FEAT_MAX + d + 1] = g;
 118                 }
 119         }
 120
 121         fclose(fdict);
 122
 123         printf("! %d\n", g); // Number of gammas.
 124         printf("%d\n", features); // Number of features.
 125         for (int i = 0; i < FEAT_MAX; i++) {
 126                 if (ps->ps[i] == 0) continue;
 127                 if (i == FEAT_SPATIAL) continue;
 128                 // Number of gammas per feature.
 129                 printf("%d %s\n", gammaid[i + 1] - gammaid[i], feature_name(i));
 130         }
 131         if (ps->ps[FEAT_SPATIAL] != 0) {
 132                 for (int d = 0; d <= ps->pc.spat_max - ps->pc.spat_min; d++) {
 133                         printf("%d %s.%d\n", gammaid[FEAT_MAX + d + 1] - gammaid[FEAT_MAX + d],
 134                                         feature_name(FEAT_SPATIAL), ps->pc.spat_min + d);
 135                 }
 136         }
 137         printf("!\n");
 138 }
 139
 140 static char *
 141 mm_pattern(struct patternscan *ps, char *str, struct pattern *p)
 142 {
 143         for (int i = 0; i < p->n; i++) {
 144                 if (i > 0) str = stpcpy(str, " ");
 145                 switch (p->f[i].id) {
 146                 case FEAT_SPATIAL:
 147                         str += sprintf(str, "%d", spatg[p->f[i].payload]);
 148                         break;
 149                 case FEAT_PATTERN3:
 150                         for (int g = 0; g < gammaid[FEAT_PATTERN3 + 1] - gammaid[FEAT_PATTERN3]; g++)
 151                                 if (pat3g[g] == p->f[i].payload) {
 152                                         str += sprintf(str, "%d", gammaid[p->f[i].id] + g);
 153                                         break;
 154                                 }
 155                         break;
 156                 default:
 157                         str += sprintf(str, "%d", gammaid[p->f[i].id] + p->f[i].payload);
 158                         break;
 159                 }
 160         }
 161         return stpcpy(str, "\n");
 162 }
 163
 164
 165 /* FEAT_PATTERN3-matched patterns do not account for rotations
 166  * and transpositions, but we shold emit only pattern hashes
 167  * in "canonical" form that is the same no matter the rotation.
 168  * To achieve this, we use a trick - the canonical form is the
 169  * one recorded in the spatial dictionary! The dictionary is
 170  * already closed on rotation and transposition. */
 171 void
 172 pattern_p3_normalize(struct patternscan *ps, struct pattern *p)
 173 {
 174         for (int i = 0; i < p->n; i++) {
 175                 if (p->f[i].id != FEAT_PATTERN3)
 176                         continue;
 177                 /* Normalize the pattern hash across rotation and
 178                  * transposition space. */
 179                 p->f[i].payload = pattern3_by_spatial(ps->pc.spat_dict, p->f[i].payload);
 180         }
 181 }
 182
 183
 184 static void
 185 process_pattern(struct patternscan *ps, struct board *b, struct move *m, char **str)
 186 {
 187         /* First, store the spatial configuration in dictionary
 188          * if applicable. */
 189         if (ps->gen_spat_dict && !is_pass(m->coord)) {
 190                 struct spatial s;
 191                 spatial_from_board(&ps->pc, &s, b, m);
 192                 int dmax = s.dist;
 193                 for (int d = ps->pc.spat_min; d <= dmax; d++) {
 194                         s.dist = d;
 195                         int sid = spatial_dict_put(ps->pc.spat_dict, &s, spatial_hash(0, &s));
 196                         assert(sid > 0);
 197                         /* Allocate space in 1024 blocks. */
 198                         #define SCOUNTS_ALLOC 1024
 199                         if (sid >= ps->nscounts) {
 200                                 int newnsc = (sid / SCOUNTS_ALLOC + 1) * SCOUNTS_ALLOC;
 201                                 ps->scounts = realloc(ps->scounts, newnsc * sizeof(*ps->scounts));
 202                                 memset(&ps->scounts[ps->nscounts], 0, (newnsc - ps->nscounts) * sizeof(*ps->scounts));
 203                                 ps->nscounts = newnsc;
 204                         }
 205                         ps->scounts[sid]++;
 206                 }
 207         }
 208
 209         /* Now, match the pattern. */
 210         if (!ps->no_pattern_match) {
 211                 struct pattern p;
 212                 pattern_match(&ps->pc, ps->ps, &p, b, m);
 213                 pattern_p3_normalize(ps, &p);
 214                 *str = ps->mm ? mm_pattern(ps, *str, &p) : pattern2str(*str, &p);
 215         }
 216 }
 217
 218 static char *
 219 patternscan_play(struct engine *e, struct board *b, struct move *m)
 220 {
 221         struct patternscan *ps = e->data;
 222
 223         if (is_resign(m->coord))
 224                 return NULL;
 225
 226         static char str[1048576]; // XXX
 227         char *strp = str;
 228         *str = 0;
 229
 230         /* Scan for supported features. */
 231         /* For specifiation of features and their payloads,
 232          * please refer to pattern.h. */
 233         process_pattern(ps, b, m, &strp);
 234
 235         if (ps->competition) {
 236                 /* Look at other possible moves as well. */
 237                 for (int f = 0; f < b->flen; f++) {
 238                         struct move mo = { .coord = b->f[f], .color = m->color };
 239                         if (is_pass(mo.coord))
 240                                 continue;
 241 #if 0
 242                         /* We want to list again the played move too. This is
 243                          * required by the MM tool. */
 244                         if (mo.coord == m->coord)
 245                                 continue;
 246 #endif
 247                         if (!board_is_valid_move(b, &mo))
 248                                 continue;
 249                         if (!ps->mm) *strp++ = ' ';
 250                         process_pattern(ps, b, &mo, &strp);
 251                 }
 252         }
 253
 254         return ps->no_pattern_match ? NULL : str;
 255 }
 256
 257 static coord_t *
 258 patternscan_genmove(struct engine *e, struct board *b, struct time_info *ti, enum stone color, bool pass_all_alive)
 259 {
 260         fprintf(stderr, "genmove command not available during patternscan!\n");
 261         exit(EXIT_FAILURE);
 262 }
 263
 264 void
 265 patternscan_done(struct engine *e)
 266 {
 267         struct patternscan *ps = e->data;
 268         if (!ps->gen_spat_dict)
 269                 return;
 270
 271         /* Save newly found patterns. */
 272
 273         bool newfile = true;
 274         FILE *f = fopen(spatial_dict_filename, "r");
 275         if (f) { fclose(f); newfile = false; }
 276         f = fopen(spatial_dict_filename, "a");
 277         if (newfile)
 278                 spatial_dict_writeinfo(ps->pc.spat_dict, f);
 279
 280         for (int i = ps->loaded_spatials; i < ps->pc.spat_dict->nspatials; i++) {
 281                 /* By default, threshold is 0 and condition is always true. */
 282                 assert(i < ps->nscounts && ps->scounts[i] > 0);
 283                 if (ps->scounts[i] >= ps->spat_threshold
 284                     || ps->pc.spat_dict->spatials[i].dist == 3)
 285                         spatial_write(ps->pc.spat_dict, &ps->pc.spat_dict->spatials[i], i, f);
 286         }
 287         fclose(f);
 288 }
 289
 290
 291 struct patternscan *
 292 patternscan_state_init(char *arg)
 293 {
 294         struct patternscan *ps = calloc(1, sizeof(struct patternscan));
 295         int xspat = -1;
 296
 297         ps->debug_level = 1;
 298         ps->pc = DEFAULT_PATTERN_CONFIG;
 299         memcpy(&ps->ps, PATTERN_SPEC_MATCHALL, sizeof(pattern_spec));
 300
 301         if (arg) {
 302                 char *optspec, *next = arg;
 303                 while (*next) {
 304                         optspec = next;
 305                         next += strcspn(next, ",");
 306                         if (*next) { *next++ = 0; } else { *next = 0; }
 307
 308                         char *optname = optspec;
 309                         char *optval = strchr(optspec, '=');
 310                         if (optval) *optval++ = 0;
 311
 312                         if (!strcasecmp(optname, "debug")) {
 313                                 if (optval)
 314                                         ps->debug_level = atoi(optval);
 315                                 else
 316                                         ps->debug_level++;
 317
 318                         } else if (!strcasecmp(optname, "gen_spat_dict")) {
 319                                 /* If set, re-generate the spatial patterns
 320                                  * dictionary; you need to have a dictionary
 321                                  * of spatial stone configurations in order
 322                                  * to match any spatial features. */
 323                                 ps->gen_spat_dict = !optval || atoi(optval);
 324
 325                         } else if (!strcasecmp(optname, "no_pattern_match")) {
 326                                 /* If set, do not actually match patterns.
 327                                  * Useful only together with gen_spat_dict
 328                                  * when just building spatial dictionary. */
 329                                 ps->no_pattern_match = !optval || atoi(optval);
 330
 331                         } else if (!strcasecmp(optname, "spat_threshold") && optval) {
 332                                 /* Minimal number of times new spatial
 333                                  * feature must occur in this run (!) to
 334                                  * be included in the dictionary. Note that
 335                                  * this will produce discontinuous dictionary
 336                                  * that you should renumber. Also note that
 337                                  * 3x3 patterns are always saved. */
 338                                 ps->spat_threshold = atoi(optval);
 339
 340                         } else if (!strcasecmp(optname, "competition")) {
 341                                 /* In competition mode, first the played
 342                                  * pattern is printed, then all patterns
 343                                  * that could be played (including the played
 344                                  * one). */
 345                                 ps->competition = !optval || atoi(optval);
 346
 347                         } else if (!strcasecmp(optname, "matchfast")) {
 348                                 /* Limit the matched features only to the
 349                                  * set used in MC simulations. */
 350                                 ps->pc = FAST_PATTERN_CONFIG;
 351                                 memcpy(&ps->ps, PATTERN_SPEC_MATCHFAST, sizeof(pattern_spec));
 352
 353                         } else if (!strcasecmp(optname, "precisesa")) {
 354                                 /* Use precise self-atari detection instead
 355                                  * of quick one; makes sense ONLY with
 356                                  * matchfast, otherwise we always do this. */
 357                                 ps->ps[FEAT_SELFATARI] = ~(1<<PF_SELFATARI_STUPID);
 358
 359                         } else if (!strcasecmp(optname, "mm")) {
 360                                 /* Generate output almost suitable for the
 361                                  * Remi Coulom's MM tool, and auxiliar file
 362                                  * "patterns.fdict" with mapping from gamma ids
 363                                  * back to feature,payload pairs. You will need
 364                                  * to post-process the output, substituting
 365                                  * s/\n\n= /#\n/. */
 366                                 ps->mm = !optval || atoi(optval);
 367
 368                         } else if (!strcasecmp(optname, "xspat") && optval) {
 369                                 /* xspat==0: don't match spatial features
 370                                  * xspat==1: match *only* spatial features */
 371                                 xspat = atoi(optval);
 372
 373                         /* See pattern.h:pattern_config for description and
 374                          * pattern.c:DEFAULT_PATTERN_CONFIG for default values
 375                          * of the following options. */
 376                         } else if (!strcasecmp(optname, "spat_min") && optval) {
 377                                 ps->pc.spat_min = atoi(optval);
 378                         } else if (!strcasecmp(optname, "spat_max") && optval) {
 379                                 ps->pc.spat_max = atoi(optval);
 380                         } else if (!strcasecmp(optname, "bdist_max") && optval) {
 381                                 ps->pc.bdist_max = atoi(optval);
 382                         } else if (!strcasecmp(optname, "ldist_min") && optval) {
 383                                 ps->pc.ldist_min = atoi(optval);
 384                         } else if (!strcasecmp(optname, "ldist_max") && optval) {
 385                                 ps->pc.ldist_max = atoi(optval);
 386                         } else if (!strcasecmp(optname, "mcsims") && optval) {
 387                                 ps->pc.mcsims = atoi(optval);
 388
 389                         } else {
 390                                 fprintf(stderr, "patternscan: Invalid engine argument %s or missing value\n", optname);
 391                                 exit(EXIT_FAILURE);
 392                         }
 393                 }
 394         }
 395         for (int i = 0; i < FEAT_MAX; i++) if ((xspat == 0 && i == FEAT_SPATIAL) || (xspat == 1 && i != FEAT_SPATIAL)) ps->ps[i] = 0;
 396         ps->pc.spat_dict = spatial_dict_init(ps->gen_spat_dict);
 397         ps->loaded_spatials = ps->pc.spat_dict->nspatials;
 398
 399         if (ps->mm)
 400                 mm_header(ps);
 401
 402         return ps;
 403 }
 404
 405 struct engine *
 406 engine_patternscan_init(char *arg, struct board *b)
 407 {
 408         struct patternscan *ps = patternscan_state_init(arg);
 409         struct engine *e = calloc(1, sizeof(struct engine));
 410         e->name = "PatternScan Engine";
 411         e->comment = "You cannot play Pachi with this engine, it is intended for special development use - scanning of games fed to it as GTP streams for various pattern features.";
 412         e->genmove = patternscan_genmove;
 413         e->notify_play = patternscan_play;
 414         e->done = patternscan_done;
 415         e->data = ps;
 416         // clear_board does not concern us, we like to work over many games
 417         e->keep_on_clear = true;
 418
 419         return e;
 420 }