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