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 #include "random.h"
  13
  14
  15 /* The engine has two modes:
  16  *
  17  * * gen_spat_dict=1: patterns.spat file is generated with a list of all
  18  *   encountered spatials
  19  *
  20  * * gen_spat_dict=0,no_pattern_match=1: all encountered patterns are
  21  *   listed on output on each move; the general format is
  22  *      [(winpattern)]
  23  *   but with competition=1 it is
  24  *      [(winpattern)] [(witnesspattern0) (witnesspattern1) ...]
  25  *   and with spat_split_sizes=1 even
  26  *      [(winpattern0) (winpattern1) ...] [(witpattern0) (witpattern1) ...]
  27  */
  28
  29
  30 /* Internal engine state. */
  31 struct patternscan {
  32         int debug_level;
  33
  34         struct pattern_setup pat;
  35         bool competition;
  36         bool spat_split_sizes;
  37         int color_mask;
  38
  39         bool no_pattern_match;
  40         bool gen_spat_dict;
  41         /* Minimal number of occurences for spatial to be saved. */
  42         int spat_threshold;
  43         /* Number of loaded spatials; checkpoint for saving new sids
  44          * in case gen_spat_dict is enabled. */
  45         int loaded_spatials;
  46
  47         /* Book-keeping of spatial occurence count. */
  48         int gameno;
  49         unsigned int nscounts;
  50         int *scounts;
  51         int *sgameno;
  52 };
  53
  54
  55 static void
  56 process_pattern(struct patternscan *ps, struct board *b, struct move *m, char **str)
  57 {
  58         /* First, store the spatial configuration in dictionary
  59          * if applicable. */
  60         if (ps->gen_spat_dict && !is_pass(m->coord)) {
  61                 struct spatial s;
  62                 spatial_from_board(&ps->pat.pc, &s, b, m);
  63                 int dmax = s.dist;
  64                 for (int d = ps->pat.pc.spat_min; d <= dmax; d++) {
  65                         s.dist = d;
  66                         unsigned int sid = spatial_dict_put(ps->pat.pc.spat_dict, &s, spatial_hash(0, &s));
  67                         assert(sid > 0);
  68                         #define SCOUNTS_ALLOC 1048576 // Allocate space in 1M*4 blocks.
  69                         if (sid >= ps->nscounts) {
  70                                 int newnsc = (sid / SCOUNTS_ALLOC + 1) * SCOUNTS_ALLOC;
  71                                 ps->scounts = realloc(ps->scounts, newnsc * sizeof(*ps->scounts));
  72                                 memset(&ps->scounts[ps->nscounts], 0, (newnsc - ps->nscounts) * sizeof(*ps->scounts));
  73                                 ps->sgameno = realloc(ps->sgameno, newnsc * sizeof(*ps->sgameno));
  74                                 memset(&ps->sgameno[ps->nscounts], 0, (newnsc - ps->nscounts) * sizeof(*ps->sgameno));
  75                                 ps->nscounts = newnsc;
  76                         }
  77                         if (ps->debug_level > 1 && !fast_random(65536) && !fast_random(32)) {
  78                                 fprintf(stderr, "%d spatials, %d collisions\n", ps->pat.pc.spat_dict->nspatials, ps->pat.pc.spat_dict->collisions);
  79                         }
  80                         if (ps->sgameno[sid] != ps->gameno) {
  81                                 ps->scounts[sid]++;
  82                                 ps->sgameno[sid] = ps->gameno;
  83                         }
  84                 }
  85         }
  86
  87         /* Now, match the pattern. */
  88         if (!ps->no_pattern_match) {
  89                 struct pattern p;
  90                 pattern_match(&ps->pat.pc, ps->pat.ps, &p, b, m);
  91
  92                 if (!ps->spat_split_sizes) {
  93                         *str = pattern2str(*str, &p);
  94                 } else {
  95                         /* XXX: We assume that FEAT_SPATIAL items
  96                          * are at the end. */
  97                         struct pattern p2;
  98                         int i = 0;
  99                         while (i < p.n && p.f[i].id != FEAT_SPATIAL) {
 100                                 p2.f[i] = p.f[i];
 101                                 i++;
 102                         }
 103                         if (i == p.n) {
 104                                 p2.n = i;
 105                                 *str = pattern2str(*str, &p2);
 106                         } else {
 107                                 p2.n = i + 1;
 108                                 for (int j = i; j < p.n; j++) {
 109                                         assert(p.f[j].id == FEAT_SPATIAL);
 110                                         p2.f[i] = p.f[j];
 111                                         if ((*str)[-1] == ')')
 112                                                 *(*str)++ = ' ';
 113                                         *str = pattern2str(*str, &p2);
 114                                 }
 115                         }
 116                 }
 117         }
 118 }
 119
 120 static char *
 121 patternscan_play(struct engine *e, struct board *b, struct move *m, char *enginearg)
 122 {
 123         struct patternscan *ps = e->data;
 124
 125         if (is_resign(m->coord))
 126                 return NULL;
 127         /* Deal with broken game records that sometimes get fed in. */
 128         if (board_at(b, m->coord) != S_NONE)
 129                 return NULL;
 130
 131         if (b->moves == (b->handicap ? b->handicap * 2 : 1))
 132                 ps->gameno++;
 133
 134         if (!(m->color & ps->color_mask))
 135                 return NULL;
 136         /* The user can request this play to be "silent", to get patterns
 137          * only for a single specific situation. */
 138         if (enginearg && *enginearg == '0')
 139                 return NULL;
 140
 141         static char str[1048576]; // XXX
 142         char *strp = str;
 143         *str = 0;
 144
 145         /* Scan for supported features. */
 146         /* For specifiation of features and their payloads,
 147          * please refer to pattern.h. */
 148         *strp++ = '[';
 149         process_pattern(ps, b, m, &strp);
 150         *strp++ = ']';
 151
 152         if (ps->competition) {
 153                 /* Look at other possible moves as well. */
 154                 *strp++ = ' ';
 155                 *strp++ = '[';
 156                 for (int f = 0; f < b->flen; f++) {
 157                         struct move mo = { .coord = b->f[f], .color = m->color };
 158                         if (is_pass(mo.coord))
 159                                 continue;
 160                         if (!board_is_valid_move(b, &mo))
 161                                 continue;
 162                         if (strp[-1] != '[')
 163                                 *strp++ = ' ';
 164                         process_pattern(ps, b, &mo, &strp);
 165                 }
 166                 *strp++ = ']';
 167         }
 168         *strp++ = 0;
 169
 170         return ps->no_pattern_match ? NULL : str;
 171 }
 172
 173 static coord_t *
 174 patternscan_genmove(struct engine *e, struct board *b, struct time_info *ti, enum stone color, bool pass_all_alive)
 175 {
 176         fprintf(stderr, "genmove command not available during patternscan!\n");
 177         exit(EXIT_FAILURE);
 178 }
 179
 180 void
 181 patternscan_done(struct engine *e)
 182 {
 183         struct patternscan *ps = e->data;
 184         if (!ps->gen_spat_dict)
 185                 return;
 186
 187         /* Save newly found patterns. */
 188
 189         bool newfile = true;
 190         FILE *f = fopen(spatial_dict_filename, "r");
 191         if (f) { fclose(f); newfile = false; }
 192         f = fopen(spatial_dict_filename, "a");
 193         if (newfile)
 194                 spatial_dict_writeinfo(ps->pat.pc.spat_dict, f);
 195
 196         for (unsigned int i = ps->loaded_spatials; i < ps->pat.pc.spat_dict->nspatials; i++) {
 197                 /* By default, threshold is 0 and condition is always true. */
 198                 assert(i < ps->nscounts && ps->scounts[i] > 0);
 199                 if (ps->scounts[i] >= ps->spat_threshold)
 200                         spatial_write(ps->pat.pc.spat_dict, &ps->pat.pc.spat_dict->spatials[i], i, f);
 201         }
 202         fclose(f);
 203 }
 204
 205
 206 struct patternscan *
 207 patternscan_state_init(char *arg)
 208 {
 209         struct patternscan *ps = calloc2(1, sizeof(struct patternscan));
 210         bool pat_setup = false;
 211         int xspat = -1;
 212
 213         ps->debug_level = 1;
 214         ps->color_mask = S_BLACK | S_WHITE;
 215
 216         if (arg) {
 217                 char *optspec, *next = arg;
 218                 while (*next) {
 219                         optspec = next;
 220                         next += strcspn(next, ",");
 221                         if (*next) { *next++ = 0; } else { *next = 0; }
 222
 223                         char *optname = optspec;
 224                         char *optval = strchr(optspec, '=');
 225                         if (optval) *optval++ = 0;
 226
 227                         if (!strcasecmp(optname, "debug")) {
 228                                 if (optval)
 229                                         ps->debug_level = atoi(optval);
 230                                 else
 231                                         ps->debug_level++;
 232
 233                         } else if (!strcasecmp(optname, "gen_spat_dict")) {
 234                                 /* If set, re-generate the spatial patterns
 235                                  * dictionary; you need to have a dictionary
 236                                  * of spatial stone configurations in order
 237                                  * to match any spatial features. */
 238                                 /* XXX: If you specify the 'patterns' option,
 239                                  * this must come first! */
 240                                 ps->gen_spat_dict = !optval || atoi(optval);
 241
 242                         } else if (!strcasecmp(optname, "no_pattern_match")) {
 243                                 /* If set, do not actually match patterns.
 244                                  * Useful only together with gen_spat_dict
 245                                  * when just building spatial dictionary. */
 246                                 ps->no_pattern_match = !optval || atoi(optval);
 247
 248                         } else if (!strcasecmp(optname, "spat_threshold") && optval) {
 249                                 /* Minimal number of times new spatial
 250                                  * feature must occur in this run (!) to
 251                                  * be included in the dictionary. Note that
 252                                  * this will produce discontinuous dictionary
 253                                  * that you should renumber. Also note that
 254                                  * 3x3 patterns are always saved. */
 255                                 ps->spat_threshold = atoi(optval);
 256
 257                         } else if (!strcasecmp(optname, "competition")) {
 258                                 /* In competition mode, first the played
 259                                  * pattern is printed, then all patterns
 260                                  * that could be played (including the played
 261                                  * one). */
 262                                 ps->competition = !optval || atoi(optval);
 263
 264                         } else if (!strcasecmp(optname, "spat_split_sizes")) {
 265                                 /* Generate a separate pattern for each
 266                                  * spatial size. This is important to
 267                                  * preserve good generalization in unknown
 268                                  * situations where the largest pattern
 269                                  * might not match. */
 270                                 ps->spat_split_sizes = 1;
 271
 272                         } else if (!strcasecmp(optname, "color_mask") && optval) {
 273                                 /* Bitmask of move colors to match. Set this
 274                                  * to 2 if you want to match only white moves,
 275                                  * for example. (Useful for processing
 276                                  * handicap games.) */
 277                                 ps->color_mask = atoi(optval);
 278
 279                         } else if (!strcasecmp(optname, "xspat") && optval) {
 280                                 /* xspat==0: don't match spatial features
 281                                  * xspat==1: match *only* spatial features */
 282                                 xspat = atoi(optval);
 283
 284                         } else if (!strcasecmp(optname, "patterns") && optval) {
 285                                 patterns_init(&ps->pat, optval, ps->gen_spat_dict, false);
 286                                 pat_setup = true;
 287
 288                         } else {
 289                                 fprintf(stderr, "patternscan: Invalid engine argument %s or missing value\n", optname);
 290                                 exit(EXIT_FAILURE);
 291                         }
 292                 }
 293         }
 294
 295         if (!pat_setup)
 296                 patterns_init(&ps->pat, NULL, ps->gen_spat_dict, false);
 297         if (ps->spat_split_sizes)
 298                 ps->pat.pc.spat_largest = 0;
 299
 300         for (int i = 0; i < FEAT_MAX; i++) if ((xspat == 0 && i == FEAT_SPATIAL) || (xspat == 1 && i != FEAT_SPATIAL)) ps->pat.ps[i] = 0;
 301         ps->loaded_spatials = ps->pat.pc.spat_dict->nspatials;
 302
 303         ps->gameno = 1;
 304
 305         return ps;
 306 }
 307
 308 struct engine *
 309 engine_patternscan_init(char *arg, struct board *b)
 310 {
 311         struct patternscan *ps = patternscan_state_init(arg);
 312         struct engine *e = calloc2(1, sizeof(struct engine));
 313         e->name = "PatternScan Engine";
 314         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.";
 315         e->genmove = patternscan_genmove;
 316         e->notify_play = patternscan_play;
 317         e->done = patternscan_done;
 318         e->data = ps;
 319         // clear_board does not concern us, we like to work over many games
 320         e->keep_on_clear = true;
 321
 322         return e;
 323 }