pattern.h

   1 #ifndef ZZGO_PATTERN_H
   2 #define ZZGO_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 /* ! NOTE NOTE NOTE ! We provide infrastructure for matching patterns, but we
  16  * also replicate the most bare-bone part of it for tiny subset of features
  17  * in board.c:board_gamma_update() for fast incremental probability
  18  * distribution maintenance. Aside of using the constants defined here, that
  19  * implementation is completely independent and does not call back here. */
  20
  21 /* Each feature is represented by its id and an optional 32-bit payload;
  22  * when matching, discrete (id,payload) pairs are considered. */
  23
  24 /* This is heavily influenced by (Coulom, 2007), of course. */
  25 /* TODO: Try completely separate ko / no-ko features. */
  26
  27 /* See the HACKING file for another description of the pattern matcher and
  28  * instructions on how to harvest and inspect patterns. */
  29
  30 /* XXX: FEAT_PATTERN3 and therefore all the pattern code is currently broken
  31  * after hash3_t atari bit extension!!! */
  32
  33 /* If you add a payload bit for a feature, don't forget to update the value
  34  * in feature_info. */
  35 enum feature_id {
  36         /* Implemented: */
  37
  38         /* This is a pass. */
  39         /* Payload: [bit0] Last move was also pass? */
  40 #define PF_PASS_LASTPASS        0
  41         FEAT_PASS,
  42
  43         /* Simple capture move. */
  44         /* Payload: [bit0] Capturing laddered group? */
  45 #define PF_CAPTURE_LADDER       0
  46         /*          [bit1] Re-capturing last move? */
  47 #define PF_CAPTURE_RECAPTURE    1 /* TODO */
  48         /*          [bit2] Enables our atari group get more libs? */
  49 #define PF_CAPTURE_ATARIDEF     2
  50         /*          [bit3] Capturing ko? */
  51 #define PF_CAPTURE_KO           3
  52         /*          [bit4] Single-stone group? */
  53 #define PF_CAPTURE_1STONE       4
  54         /*          [bit5] Unsafe move for opponent? */
  55 #define PF_CAPTURE_TRAPPED      5
  56         /*          [bit6] Preventing connection to an outside group. */
  57 #define PF_CAPTURE_CONNECTION   6
  58         FEAT_CAPTURE,
  59
  60         /* Atari escape (extension). */
  61         /* Payload: [bit0] Escaping with laddered group? */
  62 #define PF_AESCAPE_LADDER       0
  63         /*          [bit1] Single-stone group? */
  64 #define PF_AESCAPE_1STONE       1
  65         /*          [bit2] Unsafe move for us? */
  66 #define PF_AESCAPE_TRAPPED      2
  67         /*          [bit3] Connecting out to an outside group. */
  68 #define PF_AESCAPE_CONNECTION   3
  69         FEAT_AESCAPE,
  70
  71         /* Self-atari move. */
  72         /* Payload: [bit0] Matched by trivial definition? */
  73         /*          [bit1] Matched by complex definition? (tries to be aware of nakade, throwins, ...) */
  74 #define PF_SELFATARI_STUPID     0
  75 #define PF_SELFATARI_SMART      1
  76         FEAT_SELFATARI,
  77
  78         /* Atari move. */
  79         /* Payload: [bit0] The atari'd group gets laddered? */
  80 #define PF_ATARI_LADDER         0
  81         /*          [bit1] Playing ko? */
  82 #define PF_ATARI_KO             1
  83         FEAT_ATARI,
  84
  85         /* Border distance. */
  86         /* Payload: The distance - "line number". Only up to 4. */
  87         FEAT_BORDER,
  88
  89         /* Last move distance. */
  90         /* Payload: The distance - gridcular metric. */
  91         FEAT_LDIST,
  92
  93         /* Next-to-last move distance. */
  94         /* Payload: The distance - gridcular metric. */
  95         FEAT_LLDIST,
  96
  97         /* Continuity. */
  98         /* Payload: [bit0] The move is in 8-neighborhood of last move (ldist<=3) */
  99         /* This is a fast substitution to ldist/lldist. */
 100         FEAT_CONTIGUITY,
 101
 102         /* Spatial configuration of stones in certain board area,
 103          * with black to play. */
 104         /* Payload: Index in the spatial_dict. */
 105         FEAT_SPATIAL,
 106
 107         /* Spatial configuration of stones in fixed 3x3 square,
 108          * with black to play. */
 109         /* This is a fast substitution to spatial. */
 110         /* Payload: Pattern3 hash (see pattern3.h). */
 111         /* Note that the hash describes only one particular rotation;
 112          * no normalization across rotations and transpositions is done
 113          * during the matching, only color normalization. The patternscan
 114          * and gamma machineries is taking care of the rotations. */
 115         FEAT_PATTERN3,
 116
 117
 118         /* Unimplemented - TODO: */
 119
 120         /* Monte-carlo owner. */
 121         /* Payload: #of playouts owning this point at the final
 122          * position, scaled to 0..15 (lowest 4 bits). */
 123         FEAT_MCOWNER,
 124
 125         FEAT_MAX
 126 };
 127
 128 struct feature {
 129         enum feature_id id;
 130         uint16_t payload;
 131 };
 132
 133 struct pattern {
 134         /* Pattern (matched) is set of features. */
 135         int n;
 136 #define FEATURES 32
 137         struct feature f[FEATURES];
 138 };
 139
 140 struct spatial_dict;
 141 struct pattern_config {
 142         /* FEAT_SPATIAL: Generate patterns only for these sizes (gridcular). */
 143         int spat_min, spat_max;
 144         /* FEAT_BORDER: Generate features only up to this board distance. */
 145         int bdist_max;
 146         /* FEAT_LDIST, FEAT_LLDIST: Generate features only for these move
 147          * distances. */
 148         int ldist_min, ldist_max;
 149         /* FEAT_MCOWNER: Generate feature after this number of simulations. */
 150         int mcsims;
 151
 152         /* The spatial patterns dictionary, used by FEAT_SPATIAL. */
 153         struct spatial_dict *spat_dict;
 154 };
 155 extern struct pattern_config DEFAULT_PATTERN_CONFIG;
 156 extern struct pattern_config FAST_PATTERN_CONFIG;
 157
 158 /* The pattern_spec[] specifies which features to tests for;
 159  * highest bit controls whether to test for the feature at all,
 160  * then for bitmap features (except FEAT_SPATIAL) the rest
 161  * of the bits controls various PF tests; for non-bitmap
 162  * features, you will need to tweak the patternconfig to
 163  * fine-tune them. */
 164 typedef uint16_t pattern_spec[FEAT_MAX];
 165 /* Match all supported features. */
 166 extern pattern_spec PATTERN_SPEC_MATCHALL;
 167 /* Match only "quick" features, suitable for MC simulations. */
 168 extern pattern_spec PATTERN_SPEC_MATCHFAST;
 169
 170
 171 /* Append feature to string. */
 172 char *feature2str(char *str, struct feature *f);
 173 /* Convert string to feature, return pointer after the featurespec. */
 174 char *str2feature(char *str, struct feature *f);
 175 /* Get name of given feature. */
 176 char *feature_name(enum feature_id f);
 177 /* Get number of possible payload values associated with the feature. */
 178 int feature_payloads(struct pattern_config *pc, enum feature_id f);
 179
 180 /* Append pattern as feature spec string. */
 181 char *pattern2str(char *str, struct pattern *p);
 182
 183 /* Initialize p and fill it with features matched by the
 184  * given board move. */
 185 void pattern_match(struct pattern_config *pc, pattern_spec ps, struct pattern *p, struct board *b, struct move *m);
 186
 187
 188 /* Comparative strengths of all feature-payload pairs (initialized to 1 for
 189  * unspecified pairs). */
 190 struct features_gamma {
 191         /* Indexed by feature and payload; each feature array is allocated for
 192          * all possible payloads to fit in. */
 193         double *gamma[FEAT_MAX];
 194         struct pattern_config *pc;
 195 };
 196 /* Default gamma filename to use. */
 197 extern const char *features_gamma_filename;
 198
 199 /* Initializes gamma values, pre-loading existing records from given file
 200  * (NULL for default), falling back to gamma==1 for unspecified values. */
 201 struct features_gamma *features_gamma_init(struct pattern_config *pc, const char *file);
 202
 203 /* Look up gamma of given feature, or set one if gamma is not NULL. */
 204 static double feature_gamma(struct features_gamma *fg, struct feature *f, double *gamma);
 205
 206 /* Destroy the structure. */
 207 void features_gamma_done(struct features_gamma *fg);
 208
 209
 210 static inline double
 211 feature_gamma(struct features_gamma *fg, struct feature *f, double *gamma)
 212 {
 213         if (gamma) fg->gamma[f->id][f->payload] = *gamma;
 214         return fg->gamma[f->id][f->payload];
 215 }
 216
 217 #endif