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