1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\\ 2 * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * 3 * http://www.gnu.org/software/gnugo/ for more information. * 4 * * 5 * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * 6 * 2008 and 2009 by the Free Software Foundation. * 7 * * 8 * This program is free software; you can redistribute it and/or * 9 * modify it under the terms of the GNU General Public License as * 10 * published by the Free Software Foundation - version 3 or * 11 * (at your option) any later version. * 12 * * 13 * This program is distributed in the hope that it will be useful, * 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 16 * GNU General Public License in file COPYING for more details. * 17 * * 18 * You should have received a copy of the GNU General Public * 19 * License along with this program; if not, write to the Free * 20 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * 21 * Boston, MA 02111, USA. * 22 \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 23 24 /* This file describes the compiled form of the pattern database. 25 * mkpat is used to compile various source files <name>.db into 26 * intermediate files <name>.c which define data structures 27 * describing the patterns. 28 */ 29 30 #ifndef _PATTERN_H_ 31 #define _PATTERN_H_ 32 33 #ifdef HAVE_CONFIG_H 34 #include <config.h> 35 #endif 36 37 /* local versions of absolute value, min and max */ 38 39 #define gg_abs(x) ((x) < 0 ? -(x) : (x)) 40 #define gg_min(a, b) ((a)<(b) ? (a) : (b)) 41 #define gg_max(a, b) ((a)<(b) ? (b) : (a)) 42 43 /* This tells Alpha OSF/1 not to define a getopt prototype in <stdio.h>. 44 * Ditto for AIX 3.2 and <stdlib.h>. 45 */ 46 #ifndef _NO_PROTO 47 #define _NO_PROTO 48 #endif 49 50 #ifdef HAVE_CONFIG_H 51 #include <config.h> 52 #else 53 #define GRID_OPT 0 54 #endif 55 56 #ifndef GRID_OPT 57 #error GRID_OPT should be defined as 0, 1 or 2 58 #endif 59 60 61 /* Include support for pattern profiling. May be turned off in stable 62 * releases to save some memory. 63 * 64 * FIXME: should probably be included in config.h 65 */ 66 #define PROFILE_PATTERNS 0 67 68 /* this trick forces a compile error if ints are not at least 32-bit */ 69 struct _unused_patterns_h { 70 int unused[sizeof(unsigned int) >= 4 ? 1 : -1]; 71 }; 72 73 74 #define ATTACK_MACRO(pos) ((stackp == 0) ? (worm[pos].attack_codes[0]) : attack(pos, NULL)) 75 #define DEFEND_MACRO(pos) ((stackp == 0) ? (worm[pos].defense_codes[0]) : find_defense(pos, NULL)) 76 77 struct pattern; /* forward reference to keep gcc happy */ 78 79 /* this is the type of a function which the matcher can 80 * call to evaluate the score of a move. 81 * parameters: 82 * pattern and rotation are the current pattern being considered 83 * ti, tj: IN = posn of the 7, 8 or 9 marker 84 * OUT = recommended move 85 * return value : weight of move, or 0 if match failed 86 */ 87 88 typedef int (*pattern_helper_fn_ptr)(struct pattern *, int rotation, 89 int move, int color); 90 91 typedef int (*autohelper_fn_ptr)(int rotation, int move, 92 int color, int action); 93 94 95 /* each pattern is compiled into a sequence of these elements. 96 * Each describes a relative x, y from the pattern origin, 97 * and a description of what should be there. 98 * Current attributes are 99 * 0 = . 100 * 1 = X 101 * 2 = O 102 * 3 = x 103 * 4 = o 104 * 5 = , (barriers only) 105 * 6 = a (half-eye only, OBSOLETE) 106 * 7 = ! (connection and barriers only) 107 */ 108 109 #define ATT_dot 0 110 #define ATT_X 1 111 #define ATT_O 2 112 #define ATT_x 3 113 #define ATT_o 4 114 #define ATT_comma 5 115 #define ATT_a 6 116 #define ATT_not 7 117 118 /* Pattern classes. The semantics of these varies between different 119 * databases. The descriptions here mostly relate to patterns in 120 * patterns.db and other databases which are handled by shapes.c. 121 */ 122 #define CLASS_O 0x0001 /* O stones must be alive or unknown */ 123 #define CLASS_o 0x0002 /* O stones must be dead or unknown */ 124 #define CLASS_X 0x0004 /* X stones must be alive or unknown */ 125 #define CLASS_x 0x0008 /* X stones must be dead or unknown */ 126 #define CLASS_s 0x0010 /* move is a sacrifice */ 127 #define CLASS_n 0x0020 /* X could also make this move if we do not */ 128 #define CLASS_D 0x0040 /* defense pattern */ 129 #define CLASS_C 0x0080 /* move connects two worms */ 130 #define CLASS_c 0x0100 /* move weakly connects two worms */ 131 /* for owl databases: combinable pattern */ 132 #define CLASS_B 0x0200 /* move breaks connection between enemy worms */ 133 #define CLASS_A 0x0400 /* attack pattern */ 134 #define CLASS_b 0x0800 /* move is intended to block opponent */ 135 #define CLASS_e 0x1000 /* move is intended to expand territory */ 136 #define CLASS_E 0x2000 /* move is intended to expand moyo */ 137 #define CLASS_a 0x4000 /* strategical level attack */ 138 #define CLASS_d 0x8000 /* strategical level defense */ 139 #define CLASS_I 0x00010000 /* invasions patterns (influence.db) */ 140 #define CLASS_J 0x00020000 /* joseki standard move */ 141 #define CLASS_j 0x00040000 /* joseki move, slightly less urgent */ 142 #define CLASS_t 0x00080000 /* minor joseki move (tenuki OK) */ 143 #define CLASS_U 0x00100000 /* very urgent joseki move */ 144 #define CLASS_T 0x00200000 /* joseki trick move */ 145 #define CLASS_W 0x00400000 /* worthwhile threat move */ 146 #define CLASS_F 0x00800000 /* for joseki moves: a fuseki pattern */ 147 #define CLASS_N 0x01000000 /* antisuji move (do _not_ play) */ 148 #define CLASS_Y 0x80000000 /* used for experimental patterns */ 149 150 /* Collection of the classes inducing move reasons. */ 151 #define CLASS_MOVE_REASONS (CLASS_C | CLASS_B | CLASS_b | \ 152 CLASS_e | CLASS_E | CLASS_I | CLASS_a | CLASS_d | \ 153 CLASS_J | CLASS_j | CLASS_U | CLASS_T | CLASS_t | \ 154 CLASS_W | CLASS_c | CLASS_F) 155 156 /* directions for applying edge-constraints */ 157 #define NORTH_EDGE 1 158 #define SOUTH_EDGE 2 159 #define EAST_EDGE 4 160 #define WEST_EDGE 8 161 162 /* different kinds of autohelpers */ 163 #define HAVE_CONSTRAINT 1 164 #define HAVE_ACTION 2 165 166 /* Values of the action parameter to indicate where an influence autohelper 167 * is called from. 168 */ 169 #define INFLUENCE_CALLBACK 1 170 #define FOLLOWUP_INFLUENCE_CALLBACK 2 171 172 173 typedef struct patval { 174 short offset; 175 unsigned char att; 176 } Patval; 177 178 /* Build-time version of patval structure. */ 179 typedef struct patval_b { 180 int x; 181 int y; 182 int att; 183 } Patval_b; 184 185 186 enum attribute_type { 187 MIN_VALUE, 188 MAX_VALUE, 189 MIN_TERRITORY, 190 MAX_TERRITORY, 191 SHAPE, 192 FOLLOWUP, 193 REVERSE_FOLLOWUP, 194 195 /* For `mkpat'. */ 196 FIRST_OFFSET_ATTRIBUTE, 197 198 THREATENS_TO_CAPTURE = FIRST_OFFSET_ATTRIBUTE, 199 THREATENS_EYE, 200 REVERSE_SENTE, 201 202 NUM_ATTRIBUTES, 203 LAST_ATTRIBUTE = NUM_ATTRIBUTES 204 }; 205 206 207 #ifdef HAVE_TRANSPARENT_UNIONS 208 209 struct pattern_attribute { 210 enum attribute_type type; 211 212 /* GCC allows unnamed (and transparent) unions. */ 213 union { 214 float value; 215 int offset; 216 }; 217 }; 218 219 #else 220 221 struct pattern_attribute { 222 enum attribute_type type; 223 float value; 224 int offset; 225 }; 226 227 #endif 228 229 230 /* 231 * Each pattern as a whole is compiled to an instance of this structure. 232 */ 233 struct pattern { 234 struct patval *patn; /* array of elements */ 235 int patlen; /* number of elements */ 236 int trfno; /* number of transformations (rotations and reflections) */ 237 const char *name; /* short description of pattern (optional) */ 238 239 int mini, minj; /* min and max (relative to anchor) extent of ... */ 240 int maxi, maxj; /* ...the pattern */ 241 int height, width; /* differences between max and min extents */ 242 unsigned int edge_constraints; /* and combinations of NORTH, EAST etc. 243 * for edges */ 244 245 int move_offset; /* offset of the suggested move (relative to anchor) */ 246 247 #if GRID_OPT 248 unsigned int and_mask[8]; /* for each rotation, masks for a */ 249 unsigned int val_mask[8]; /* 4x4 grid around anchor */ 250 #endif 251 252 unsigned int class; /* classification of pattern */ 253 254 /* Value (owl-style, used for pattern sorting) is not stored as an 255 * attribute, because it is very common. 256 */ 257 float value; 258 259 /* Pattern attributes like shape, followup etc. */ 260 struct pattern_attribute *attributes; 261 262 int autohelper_flag; /* whether autohelper has constraint and/or action */ 263 pattern_helper_fn_ptr helper; /* helper function, or NULL */ 264 autohelper_fn_ptr autohelper; /* automatically generated helper */ 265 /* function, or NULL */ 266 267 int anchored_at_X; /* 3 if the pattern has 'X' at the anchor posn */ 268 269 float constraint_cost; /* mkpat's estimate of the constraint complexity.*/ 270 271 #if PROFILE_PATTERNS 272 int hits; 273 int dfa_hits; 274 int reading_nodes; 275 #endif 276 }; 277 278 279 struct pattern_db { 280 int fixed_for_size; 281 const int fixed_anchor; 282 struct pattern *patterns; 283 struct dfa_rt *pdfa; 284 }; 285 286 287 struct fullboard_pattern { 288 Hash_data fullboard_hash; /* Hash of the full board position. */ 289 int number_of_stones; /* Number of stones on board. */ 290 const char *name; /* Pattern identifier. */ 291 int move_offset; /* position of the move relative to tengen */ 292 int value; /* value for pattern, if matched */ 293 }; 294 295 296 /* Monte Carlo local patterns. */ 297 struct mc_pattern_database { 298 const char *name; 299 const unsigned int *values; 300 }; 301 302 303 /* helper functions */ 304 305 #define DECLARE(x) int x(struct pattern *pattern, int transformation, int move, int color) 306 307 DECLARE(jump_out_helper); 308 DECLARE(jump_out_far_helper); 309 DECLARE(high_handicap_helper); 310 DECLARE(reinforce_helper); 311 DECLARE(throw_in_atari_helper); 312 DECLARE(cutstone2_helper); 313 DECLARE(thrash_around_helper); 314 315 /* autohelper fns */ 316 int seki_helper(int str); 317 void threaten_to_save_helper(int move, int str); 318 void threaten_to_capture_helper(int move, int str); 319 void prevent_attack_threat_helper(int move, int str); 320 void defend_against_atari_helper(int move, int str); 321 void amalgamate_most_valuable_helper(int apos, int bpos, int cpos); 322 int finish_ko_helper(int apos); 323 int squeeze_ko_helper(int apos); 324 int backfill_helper(int apos, int bpos, int cpos); 325 int owl_threatens_attack(int apos, int bpos); 326 int connect_and_cut_helper(int Apos, int bpos, int cpos); 327 int connect_and_cut_helper2(int Apos, int bpos, int cpos, int color); 328 int edge_double_sente_helper(int move, int apos, int bpos, int cpos); 329 void test_attack_either_move(int move, int color, int worma, int wormb); 330 int adjacent_to_stone_in_atari(int str); 331 int adjacent_to_defendable_stone_in_atari(int str); 332 void backfill_replace(int move, int str); 333 int break_mirror_helper(int str, int color); 334 int distrust_tactics_helper(int str); 335 int disconnect_helper(int apos, int bpos); 336 337 338 /* pattern arrays themselves */ 339 extern struct pattern_db pat_db; 340 extern struct pattern_db aa_attackpat_db; 341 extern struct pattern_db owl_attackpat_db; 342 extern struct pattern_db owl_vital_apat_db; 343 extern struct pattern_db owl_defendpat_db; 344 extern struct pattern_db conn_db; 345 extern struct pattern_db attpat_db; 346 extern struct pattern_db defpat_db; 347 extern struct pattern_db endpat_db; 348 extern struct pattern_db influencepat_db; 349 extern struct pattern_db barrierspat_db; 350 extern struct pattern_db fusekipat_db; 351 extern struct pattern_db handipat_db; 352 extern struct pattern_db oracle_db; 353 354 extern struct corner_db joseki_db; 355 356 extern struct fullboard_pattern fuseki19[]; 357 extern struct fullboard_pattern fuseki13[]; 358 extern struct fullboard_pattern fuseki9[]; 359 360 extern struct mc_pattern_database mc_pattern_databases[]; 361 362 struct corner_db; 363 struct corner_variation; 364 struct corner_pattern; 365 366 struct corner_db { 367 int max_width; /* Largest possible width and... */ 368 int max_height; /* ... largest possible height of database patterns. */ 369 370 unsigned char num_top_variations; /* Number of top level variations. */ 371 struct corner_variation *top_variations; 372 }; 373 374 struct corner_variation { 375 int move_offset; /* Offset of the move in this variation. */ 376 signed char xor_att; /* 0 - the same color as the first matched stone, 377 * 3 - the opposite color. 378 */ 379 unsigned char num_stones; /* Number of stones in the `move_offset' rectangle. */ 380 381 unsigned char num_variations; /* Number of subvariations. */ 382 struct corner_variation *variations; /* Pointer to subvariation array. */ 383 384 struct corner_pattern *pattern; /* Address of matched pattern (if any). */ 385 }; 386 387 struct corner_pattern { 388 int second_corner_offset; /* Offset of pattern's second corner. */ 389 int symmetric; /* If the pattern is symmetric ('/' symmetry). */ 390 391 unsigned int class; /* Pattern class. */ 392 const char *name; /* Pattern name (optional). */ 393 394 /* Pattern attributes like shape (the only one used currently). */ 395 struct pattern_attribute *attributes; 396 397 int autohelper_flag; /* Whether autohelper has constraint and/or action. */ 398 autohelper_fn_ptr autohelper; /* Automatically generated helper (or NULL). */ 399 }; 400 401 /* Build time version of corner_variation structure. */ 402 struct corner_variation_b { 403 int move_offset; 404 signed char xor_att; 405 unsigned char num_stones; 406 407 unsigned char num_variations; 408 struct corner_variation_b *next; 409 struct corner_variation_b *child; 410 int child_num; 411 412 int pattern_num; 413 }; 414 415 416 #endif /* _PATTERN_H_ */ 417 418 419 /* 420 * Local Variables: 421 * tab-width: 8 422 * c-basic-offset: 2 423 * End: 424 */ 425