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