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