pattern.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 #include "tactics.h"
  13
  14
  15 struct pattern_config DEFAULT_PATTERN_CONFIG = {
  16         .spat_min = 3, .spat_max = MAX_PATTERN_DIST,
  17         .bdist_max = 4,
  18         .ldist_min = 0, .ldist_max = 256,
  19         .mcsims = 0, /* Unsupported. */
  20 };
  21
  22 struct pattern_config FAST_PATTERN_CONFIG = {
  23         .spat_min = 3, .spat_max = 5,
  24         .bdist_max = 4,
  25         .ldist_min = 0, .ldist_max = 256,
  26         .mcsims = 0,
  27 };
  28
  29 pattern_spec PATTERN_SPEC_MATCHALL = {
  30         [FEAT_PASS] = ~0,
  31         [FEAT_CAPTURE] = ~0,
  32         [FEAT_AESCAPE] = ~0,
  33         [FEAT_SELFATARI] = ~0,
  34         [FEAT_ATARI] = ~0,
  35         [FEAT_BORDER] = ~0,
  36         [FEAT_LDIST] = ~0,
  37         [FEAT_LLDIST] = ~0,
  38         [FEAT_SPATIAL] = ~0,
  39         [FEAT_MCOWNER] = ~0,
  40 };
  41
  42 pattern_spec PATTERN_SPEC_MATCHFAST = {
  43         [FEAT_PASS] = ~0,
  44         [FEAT_CAPTURE] = ~(1<<PF_CAPTURE_ATARIDEF)|~(1<<PF_CAPTURE_RECAPTURE),
  45         [FEAT_AESCAPE] = ~0,
  46         [FEAT_SELFATARI] = ~(1<<PF_SELFATARI_SMART),
  47         [FEAT_ATARI] = ~0,
  48         [FEAT_BORDER] = ~0,
  49         [FEAT_LDIST] = ~0,
  50         [FEAT_LLDIST] = ~0,
  51         [FEAT_SPATIAL] = ~0,
  52         [FEAT_MCOWNER] = ~0,
  53 };
  54
  55 static const struct feature_info {
  56         char *name;
  57         int payloads;
  58 } features[FEAT_MAX] = {
  59         [FEAT_PASS] = { .name = "pass", .payloads = 2 },
  60         [FEAT_CAPTURE] = { .name = "capture", .payloads = 16 },
  61         [FEAT_AESCAPE] = { .name = "atariescape", .payloads = 2 },
  62         [FEAT_SELFATARI] = { .name = "selfatari", .payloads = 2 },
  63         [FEAT_ATARI] = { .name = "atari", .payloads = 4 },
  64         [FEAT_BORDER] = { .name = "border", .payloads = 1 },
  65         [FEAT_LDIST] = { .name = "ldist", .payloads = -1 },
  66         [FEAT_LLDIST] = { .name = "lldist", .payloads = -1 },
  67         [FEAT_SPATIAL] = { .name = "s", .payloads = -1 },
  68         [FEAT_MCOWNER] = { .name = "mcowner", .payloads = 16 },
  69 };
  70
  71 char *
  72 feature2str(char *str, struct feature *f)
  73 {
  74         return str + sprintf(str + strlen(str), "%s:%"PRIx32, features[f->id].name, f->payload);
  75 }
  76
  77 char *
  78 str2feature(char *str, struct feature *f)
  79 {
  80         while (isspace(*str)) str++;
  81
  82         int flen = strcspn(str, ":");
  83         for (int i = 0; i < sizeof(features)/sizeof(features[0]); i++)
  84                 if (strlen(features[i].name) == flen && !strncmp(features[i].name, str, flen)) {
  85                         f->id = i;
  86                         goto found;
  87                 }
  88         fprintf(stderr, "invalid featurespec: %s[%d]\n", str, flen);
  89         exit(EXIT_FAILURE);
  90
  91 found:
  92         str += flen + 1;
  93         f->payload = strtoull(str, &str, 16);
  94         return str;
  95 }
  96
  97
  98 /* pattern_spec helpers */
  99 #define PS_ANY(F) (ps[FEAT_ ## F] & (1 << 31))
 100 #define PS_PF(F, P) (ps[FEAT_ ## F] & (1 << PF_ ## F ## _ ## P))
 101
 102 static struct feature *
 103 pattern_match_capture(struct pattern_config *pc, pattern_spec ps,
 104                       struct pattern *p, struct feature *f,
 105                       struct board *b, struct move *m)
 106 {
 107         foreach_neighbor(b, m->coord, {
 108                 if (board_at(b, c) != stone_other(m->color))
 109                         continue;
 110                 group_t g = group_at(b, c);
 111                 if (!g || board_group_info(b, g).libs != 1)
 112                         continue;
 113
 114                 /* Capture! */
 115                 f->id = FEAT_CAPTURE; f->payload = 0;
 116
 117                 if (PS_PF(CAPTURE, LADDER))
 118                         f->payload |= is_ladder(b, m->coord, g, true, true) << PF_CAPTURE_LADDER;
 119                 /* TODO: is_ladder() is too conservative in some
 120                  * very obvious situations, look at complete.gtp. */
 121
 122                 /* TODO: PF_CAPTURE_RECAPTURE */
 123
 124                 if (PS_PF(CAPTURE, ATARIDEF))
 125                 foreach_in_group(b, g) {
 126                         foreach_neighbor(b, c, {
 127                                 assert(board_at(b, c) != S_NONE || c == m->coord);
 128                                 if (board_at(b, c) != m->color)
 129                                         continue;
 130                                 group_t g = group_at(b, c);
 131                                 if (!g || board_group_info(b, g).libs != 1)
 132                                         continue;
 133                                 /* A neighboring group of ours is in atari. */
 134                                 f->payload |= 1 << PF_CAPTURE_ATARIDEF;
 135                         });
 136                 } foreach_in_group_end;
 137
 138                 if (PS_PF(CAPTURE, KO)
 139                     && group_is_onestone(b, g)
 140                     && neighbor_count_at(b, m->coord, stone_other(m->color))
 141                        + neighbor_count_at(b, m->coord, S_OFFBOARD) == 4)
 142                         f->payload |= 1 << PF_CAPTURE_KO;
 143
 144                 (f++, p->n++);
 145         });
 146         return f;
 147 }
 148
 149 static struct feature *
 150 pattern_match_aescape(struct pattern_config *pc, pattern_spec ps,
 151                       struct pattern *p, struct feature *f,
 152                       struct board *b, struct move *m)
 153 {
 154         /* Find if a neighboring group of ours is in atari, AND that we provide
 155          * a liberty to connect out. XXX: No connect-and-die check. */
 156         group_t in_atari = -1;
 157         bool has_extra_lib = false;
 158         int payload = 0;
 159
 160         foreach_neighbor(b, m->coord, {
 161                 if (board_at(b, c) != m->color) {
 162                         if (board_at(b, c) == S_NONE)
 163                                 has_extra_lib = true; // free point
 164                         else if (board_at(b, c) == stone_other(m->color) && board_group_info(b, group_at(b, c)).libs == 1)
 165                                 has_extra_lib = true; // capturable enemy group
 166                         continue;
 167                 }
 168                 group_t g = group_at(b, c); assert(g);
 169                 if (board_group_info(b, g).libs != 1) {
 170                         has_extra_lib = true;
 171                         continue;
 172                 }
 173
 174                 /* In atari! */
 175                 in_atari = g;
 176
 177                 if (PS_PF(AESCAPE, LADDER))
 178                         payload |= is_ladder(b, m->coord, g, true, true) << PF_AESCAPE_LADDER;
 179                 /* TODO: is_ladder() is too conservative in some
 180                  * very obvious situations, look at complete.gtp. */
 181         });
 182         if (in_atari >= 0 && has_extra_lib) {
 183                 f->id = FEAT_AESCAPE; f->payload = payload;
 184                 (f++, p->n++);
 185         }
 186         return f;
 187 }
 188
 189 static struct feature *
 190 pattern_match_atari(struct pattern_config *pc, pattern_spec ps,
 191                     struct pattern *p, struct feature *f,
 192                     struct board *b, struct move *m)
 193 {
 194         foreach_neighbor(b, m->coord, {
 195                 if (board_at(b, c) != stone_other(m->color))
 196                         continue;
 197                 group_t g = group_at(b, c);
 198                 if (!g || board_group_info(b, g).libs != 2)
 199                         continue;
 200
 201                 /* Can atari! */
 202                 f->id = FEAT_ATARI; f->payload = 0;
 203
 204                 if (PS_PF(ATARI, LADDER)) {
 205                         /* Opponent will escape by the other lib. */
 206                         coord_t lib = board_group_info(b, g).lib[0];
 207                         if (lib == m->coord) lib = board_group_info(b, g).lib[1];
 208                         /* TODO: is_ladder() is too conservative in some
 209                          * very obvious situations, look at complete.gtp. */
 210                         f->payload |= is_ladder(b, lib, g, true, true) << PF_ATARI_LADDER;
 211                 }
 212
 213                 if (PS_PF(ATARI, KO) && !is_pass(b->ko.coord))
 214                         f->payload |= 1 << PF_ATARI_KO;
 215
 216                 (f++, p->n++);
 217         });
 218         return f;
 219 }
 220
 221 struct feature *
 222 pattern_match_spatial(struct pattern_config *pc, pattern_spec ps,
 223                       struct pattern *p, struct feature *f,
 224                       struct board *b, struct move *m)
 225 {
 226         /* XXX: This is partially duplicated from spatial_from_board(), but
 227          * we build a hash instead of spatial record. */
 228
 229         assert(pc->spat_min > 0);
 230
 231         /* We record all spatial patterns black-to-play; simply
 232          * reverse all colors if we are white-to-play. */
 233         static enum stone bt_black[4] = { S_NONE, S_BLACK, S_WHITE, S_OFFBOARD };
 234         static enum stone bt_white[4] = { S_NONE, S_WHITE, S_BLACK, S_OFFBOARD };
 235         enum stone (*bt)[4] = m->color == S_WHITE ? &bt_white : &bt_black;
 236
 237         hash_t h = pthashes[0][0][S_NONE];
 238 #ifdef BOARD_SPATHASH
 239         for (int d = 2; d <= BOARD_SPATHASH_MAXD; d++) {
 240                 /* Reuse all incrementally matched data. */
 241                 h ^= b->spathash[m->coord][d - 1];
 242                 if (d < pc->spat_min)
 243                         continue;
 244                 /* Record spatial feature, one per distance. */
 245                 f->id = FEAT_SPATIAL;
 246                 f->payload = (d << PF_SPATIAL_RADIUS);
 247                 int sid = spatial_dict_get(pc->spat_dict, d, h & spatial_hash_mask);
 248                 if (sid > 0) {
 249                         f->payload |= sid << PF_SPATIAL_INDEX;
 250                         (f++, p->n++);
 251                 } /* else not found, ignore */
 252         }
 253 #else
 254 #undef BOARD_SPATHASH_MAXD
 255 #define BOARD_SPATHASH_MAXD 1
 256 #endif
 257         for (int d = BOARD_SPATHASH_MAXD + 1; d <= pc->spat_max; d++) {
 258                 /* Recompute missing outer circles:
 259                  * Go through all points in given distance. */
 260                 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
 261                         int x = coord_x(m->coord, b) + ptcoords[j].x;
 262                         int y = coord_y(m->coord, b) + ptcoords[j].y;
 263                         if (x >= board_size(b)) x = board_size(b) - 1; else if (x < 0) x = 0;
 264                         if (y >= board_size(b)) y = board_size(b) - 1; else if (y < 0) y = 0;
 265                         h ^= pthashes[0][j][(*bt)[board_atxy(b, x, y)]];
 266                 }
 267                 if (d < pc->spat_min)
 268                         continue;
 269                 /* Record spatial feature, one per distance. */
 270                 f->id = FEAT_SPATIAL;
 271                 f->payload = (d << PF_SPATIAL_RADIUS);
 272                 int sid = spatial_dict_get(pc->spat_dict, d, h & spatial_hash_mask);
 273                 if (sid > 0) {
 274                         f->payload |= sid << PF_SPATIAL_INDEX;
 275                         (f++, p->n++);
 276                 } /* else not found, ignore */
 277         }
 278         return f;
 279 }
 280
 281
 282 static bool
 283 is_simple_selfatari(struct board *b, enum stone color, coord_t coord)
 284 {
 285         /* Very rough check, no connect-and-die checks or other trickery. */
 286         int libs = immediate_liberty_count(b, coord);
 287         if (libs >= 2) return false; // open space
 288
 289         group_t seen = -1;
 290         foreach_neighbor(b, coord, {
 291                 if (board_at(b, c) == stone_other(color) && board_group_info(b, group_at(b, c)).libs == 1) {
 292                         return false; // can capture
 293
 294                 } else if (board_at(b, c) == color) {
 295                         // friendly group, does it have liberties?
 296                         group_t g = group_at(b, c);
 297                         if (board_group_info(b, g).libs == 1 || seen == g)
 298                                 continue;
 299                         libs += board_group_info(b, g).libs - 1;
 300                         if (libs >= 2) return false;
 301                         // don't consider the same group twice
 302                         seen = g;
 303                 }
 304         });
 305         return true;
 306 }
 307
 308 void
 309 pattern_match(struct pattern_config *pc, pattern_spec ps,
 310               struct pattern *p, struct board *b, struct move *m)
 311 {
 312         p->n = 0;
 313         struct feature *f = &p->f[0];
 314
 315         /* TODO: We should match pretty much all of these features
 316          * incrementally. */
 317
 318         if (is_pass(m->coord)) {
 319                 if (PS_ANY(PASS)) {
 320                         f->id = FEAT_PASS; f->payload = 0;
 321                         if (PS_PF(PASS, LASTPASS))
 322                                 f->payload |= (b->moves > 0 && is_pass(b->last_move.coord))
 323                                                 << PF_PASS_LASTPASS;
 324                         p->n++;
 325                 }
 326                 return;
 327         }
 328
 329         if (PS_ANY(CAPTURE)) {
 330                 f = pattern_match_capture(pc, ps, p, f, b, m);
 331         }
 332
 333         if (PS_ANY(AESCAPE)) {
 334                 f = pattern_match_aescape(pc, ps, p, f, b, m);
 335         }
 336
 337         if (PS_ANY(SELFATARI)) {
 338                 bool simple = is_simple_selfatari(b, m->color, m->coord);
 339                 bool thorough = false;
 340                 if (PS_PF(SELFATARI, SMART)) {
 341                         thorough = is_bad_selfatari(b, m->color, m->coord);
 342                 }
 343                 if (simple || thorough) {
 344                         f->id = FEAT_SELFATARI;
 345                         f->payload = thorough << PF_SELFATARI_SMART;
 346                         (f++, p->n++);
 347                 }
 348         }
 349
 350         if (PS_ANY(ATARI)) {
 351                 f = pattern_match_atari(pc, ps, p, f, b, m);
 352         }
 353
 354         if (PS_ANY(BORDER)) {
 355                 int bdist = coord_edge_distance(m->coord, b);
 356                 if (bdist <= pc->bdist_max) {
 357                         f->id = FEAT_BORDER;
 358                         f->payload = bdist;
 359                         (f++, p->n++);
 360                 }
 361         }
 362
 363         if (PS_ANY(LDIST) && pc->ldist_max > 0 && !is_pass(b->last_move.coord)) {
 364                 int ldist = coord_gridcular_distance(m->coord, b->last_move.coord, b);
 365                 if (pc->ldist_min <= ldist && ldist <= pc->ldist_max) {
 366                         f->id = FEAT_LDIST;
 367                         f->payload = ldist;
 368                         (f++, p->n++);
 369                 }
 370         }
 371
 372         if (PS_ANY(LLDIST) && pc->ldist_max > 0 && !is_pass(b->last_move2.coord)) {
 373                 int lldist = coord_gridcular_distance(m->coord, b->last_move2.coord, b);
 374                 if (pc->ldist_min <= lldist && lldist <= pc->ldist_max) {
 375                         f->id = FEAT_LLDIST;
 376                         f->payload = lldist;
 377                         (f++, p->n++);
 378                 }
 379         }
 380
 381         if (PS_ANY(SPATIAL) && pc->spat_max > 0 && pc->spat_dict) {
 382                 f = pattern_match_spatial(pc, ps, p, f, b, m);
 383         }
 384
 385         /* FEAT_MCOWNER: TODO */
 386         assert(!pc->mcsims);
 387 }
 388
 389 char *
 390 pattern2str(char *str, struct pattern *p)
 391 {
 392         str = stpcpy(str, "(");
 393         for (int i = 0; i < p->n; i++) {
 394                 if (i > 0) str = stpcpy(str, " ");
 395                 str = feature2str(str, &p->f[i]);
 396         }
 397         str = stpcpy(str, ")");
 398         return str;
 399 }
 400
 401
 402
 403 /*** Features gamma set */
 404
 405 static void
 406 features_gamma_load(struct features_gamma *fg, const char *filename)
 407 {
 408         FILE *f = fopen(filename, "r");
 409         if (!f) return;
 410         char buf[256];
 411         while (fgets(buf, 256, f)) {
 412                 char *bufp = buf;
 413                 struct feature f;
 414                 bufp = str2feature(bufp, &f);
 415                 while (isspace(*bufp)) bufp++;
 416                 float gamma = strtof(bufp, &bufp);
 417                 feature_gamma(fg, &f, &gamma);
 418         }
 419         fclose(f);
 420 }
 421
 422 const char *features_gamma_filename = "patterns.gamma";
 423
 424 struct features_gamma *
 425 features_gamma_init(struct pattern_config *pc, const char *file)
 426 {
 427         struct features_gamma *fg = calloc(1, sizeof(*fg));
 428         fg->pc = pc;
 429         for (int i = 0; i < FEAT_MAX; i++) {
 430                 int n = features[i].payloads;
 431                 if (n <= 0) {
 432                         switch (i) {
 433                                 case FEAT_SPATIAL:
 434                                         n = pc->spat_dict->nspatials; break;
 435                                 case FEAT_LDIST:
 436                                 case FEAT_LLDIST:
 437                                         n = pc->ldist_max; break;
 438                                 default:
 439                                         assert(0);
 440                         }
 441                 }
 442                 fg->gamma[i] = malloc(n * sizeof(float));
 443                 for (int j = 0; j < n; j++) {
 444                         fg->gamma[i][j] = 1.0f;
 445                 }
 446         }
 447         features_gamma_load(fg, file ? file : features_gamma_filename);
 448         return fg;
 449 }
 450
 451 float
 452 feature_gamma(struct features_gamma *fg, struct feature *f, float *gamma)
 453 {
 454         /* XXX: We mask out spatial distance unconditionally since it shouldn't
 455          * affect any other feature. */
 456         int payid = f->payload & ((1<<24)-1);
 457         if (gamma) fg->gamma[f->id][payid] = *gamma;
 458         return fg->gamma[f->id][payid];
 459 }