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