pattern.h

   1 #ifndef PACHI_PATTERN_H
   2 #define PACHI_PATTERN_H
   3
   4 /* Matching of multi-featured patterns. */
   5
   6 #include "board.h"
   7 #include "move.h"
   8
   9 /* When someone says "pattern", you imagine a configuration of stones in given
  10  * area (e.g. as matched very efficiently by pattern3 in case of 3x3 area).
  11  * However, we use a richer definition of pattern, where this is merely one
  12  * pattern _feature_. Another features may be is-a-selfatari, is-a-capture,
  13  * number of liberties, distance from last move, etc. */
  14
  15 /* Each feature is represented by its id and an optional 32-bit payload;
  16  * when matching, discrete (id,payload) pairs are considered. */
  17
  18 /* This is heavily influenced by (Coulom, 2007), of course. In addition,
  19  * the work of van der Werf, de Groot, Stern et al. and possibly others
  20  * inspired this pattern matcher. */
  21 /* TODO: Try completely separate ko / no-ko features. And many other
  22  * features described in the literature. */
  23
  24 /* See the HACKING file for another description of the pattern matcher and
  25  * instructions on how to harvest and inspect patterns. */
  26
  27 /* If you add a payload bit for a feature, don't forget to update the value
  28  * in feature_info. */
  29 enum feature_id {
  30         /* Implemented: */
  31
  32         /* Simple capture move. */
  33         /* Payload: [bit0] Capturing laddered group? */
  34 #define PF_CAPTURE_LADDER       0
  35         /*          [bit1] Enables our atari group get more libs? */
  36 #define PF_CAPTURE_ATARIDEF     1
  37         /*          [bit2] Capturing ko? */
  38 #define PF_CAPTURE_KO           2
  39         /*          [bit3] Single-stone group? */
  40 #define PF_CAPTURE_1STONE       3
  41         /*          [bit4] Unsafe move for opponent? */
  42 #define PF_CAPTURE_TRAPPED      4
  43         /*          [bit5] Preventing connection to an outside group. */
  44 #define PF_CAPTURE_CONNECTION   5
  45         /*          [bit6] Are we counting captured stones? */
  46 #define PF_CAPTURE_COUNTSTONES  6
  47         /* How many bits of payload are used for counting captured stones. */
  48 #define CAPTURE_COUNTSTONES_PAYLOAD_SIZE 4              /* that is, payload bits 6,7,8,9 */
  49         FEAT_CAPTURE,
  50
  51         /* Atari escape (extension). */
  52         /* Payload: [bit0] Escaping with laddered group? */
  53 #define PF_AESCAPE_LADDER       0
  54         /*          [bit1] Single-stone group? */
  55 #define PF_AESCAPE_1STONE       1
  56         /*          [bit2] Unsafe move for us? */
  57 #define PF_AESCAPE_TRAPPED      2
  58         /*          [bit3] Connecting out to an outside group. */
  59 #define PF_AESCAPE_CONNECTION   3
  60         FEAT_AESCAPE,
  61
  62         /* Self-atari move. */
  63         /* Payload: [bit0] Matched by trivial definition? */
  64         /*          [bit1] Matched by complex definition? (tries to be aware of nakade, throwins, ...) */
  65 #define PF_SELFATARI_STUPID     0
  66 #define PF_SELFATARI_SMART      1
  67         FEAT_SELFATARI,
  68
  69         /* Atari move. */
  70         /* Payload: [bit0] The atari'd group gets laddered? */
  71 #define PF_ATARI_LADDER         0
  72         /*          [bit1] Playing ko? */
  73 #define PF_ATARI_KO             1
  74         FEAT_ATARI,
  75
  76         /* Border distance. */
  77         /* Payload: The distance - "line number". Only up to 4. */
  78         FEAT_BORDER,
  79
  80         /* Continuity. */
  81         /* Payload: [bit0] The move is in 8-neighborhood of last move. */
  82         FEAT_CONTIGUITY,
  83
  84         /* Spatial configuration of stones in certain board area,
  85          * with black to play. */
  86         /* Payload: Index in the spatial_dict. */
  87         FEAT_SPATIAL,
  88
  89         /* TODO: MC owner, playing ko, #liberties, #libs of opponent, ... */
  90
  91         FEAT_MAX
  92 };
  93
  94 struct feature {
  95         enum feature_id id:8;
  96         unsigned int payload:24;
  97 };
  98
  99 struct pattern {
 100         /* Pattern (matched) is set of features. */
 101         int n;
 102         /* XXX: Should be at least 6 + spat_max-spat_min if spat_largest
 103          * is false! However, this has large effect on consumed memory. */
 104 #define FEATURES 18 // XXX: can be just 8 if spat_largest is true
 105         struct feature f[FEATURES];
 106 };
 107
 108 struct spatial_dict;
 109 struct pattern_config {
 110         /* FEAT_BORDER: Generate features only up to this board distance. */
 111         unsigned int bdist_max;
 112
 113         /* FEAT_SPATIAL: Generate patterns only for these sizes (gridcular).
 114          * TODO: Special-case high values to match larger areas or the
 115          * whole board. */
 116         unsigned int spat_min, spat_max;
 117         /* Produce only a single spatial feature per pattern, corresponding
 118          * to the largest matched spatial pattern. */
 119         bool spat_largest;
 120         /* The spatial patterns dictionary used by FEAT_SPATIAL. */
 121         struct spatial_dict *spat_dict;
 122 };
 123 extern struct pattern_config DEFAULT_PATTERN_CONFIG;
 124
 125 /* The pattern_spec[] specifies which features to tests for;
 126  * highest bit controls whether to test for the feature at all,
 127  * then for bitmap features (except FEAT_SPATIAL) the rest
 128  * of the bits controls various PF tests; for non-bitmap
 129  * features, you will need to tweak the patternconfig to
 130  * fine-tune them. */
 131 typedef uint16_t pattern_spec[FEAT_MAX];
 132 /* Match (almost?) all supported features. */
 133 extern pattern_spec PATTERN_SPEC_MATCH_DEFAULT;
 134
 135
 136 /* General structure describing a loaded pattern configuration
 137  * with all its attributes. */
 138 struct pattern_pdict;
 139 struct pattern_setup {
 140         struct pattern_config pc;
 141         pattern_spec ps;
 142         struct pattern_pdict *pd;
 143 };
 144
 145 void patterns_init(struct pattern_setup *pat, char *arg, bool will_append, bool load_prob);
 146
 147
 148 /* Append feature to string. */
 149 char *feature2str(char *str, struct feature *f);
 150 /* Convert string to feature, return pointer after the featurespec. */
 151 char *str2feature(char *str, struct feature *f);
 152 /* Get name of given feature. */
 153 char *feature_name(enum feature_id f);
 154 /* Get number of possible payload values associated with the feature. */
 155 int feature_payloads(struct pattern_config *pc, enum feature_id f);
 156
 157 /* Append pattern as feature spec string. */
 158 char *pattern2str(char *str, struct pattern *p);
 159 /* Convert string to pattern, return pointer after the patternspec. */
 160 char *str2pattern(char *str, struct pattern *p);
 161 /* Compare two patterns for equality. Assumes fixed feature order. */
 162 static bool pattern_eq(struct pattern *p1, struct pattern *p2);
 163
 164 /* Initialize p and fill it with features matched by the
 165  * given board move. */
 166 void pattern_match(struct pattern_config *pc, pattern_spec ps, struct pattern *p, struct board *b, struct move *m);
 167
 168
 169 static inline bool
 170 pattern_eq(struct pattern *p1, struct pattern *p2)
 171 {
 172         if (p1->n != p2->n) return false;
 173         for (int i = 0; i < p1->n; i++)
 174                 if (p1->f[i].id != p2->f[i].id || p1->f[i].payload != p2->f[i].payload)
 175                         return false;
 176         return true;
 177 }
 178
 179 #endif