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 #ifndef _LIBERTY_H_ 25 #define _LIBERTY_H_ 26 27 #include "board.h" 28 #include "hash.h" 29 #include "gnugo.h" 30 #include "winsocket.h" 31 32 /* ================================================================ */ 33 /* public variables */ 34 /* ================================================================ */ 35 36 37 /* ================================================================ */ 38 39 40 #define FALSE_EYE 1 41 #define HALF_EYE 2 42 43 44 #define REVERSE_RESULT(result) (WIN - result) 45 46 47 void start_timer(int n); 48 double time_report(int n, const char *occupation, int move, double mintime); 49 void showstats(void); 50 void clearstats(void); 51 52 void transformation_init(void); 53 54 void ascii_report_worm(char *string); 55 void report_dragon(FILE *outfile, int pos); 56 void ascii_report_dragon(char *string); 57 struct dragon_data2 *dragon2_func(int pos); 58 59 /* Routine names used by persistent and non-persistent caching schemes. */ 60 enum routine_id { 61 OWL_ATTACK, 62 OWL_DEFEND, 63 SEMEAI, 64 FIND_DEFENSE, 65 ATTACK, 66 CONNECT, 67 DISCONNECT, 68 BREAK_IN, 69 BLOCK_OFF, 70 OWL_THREATEN_ATTACK, 71 OWL_THREATEN_DEFENSE, 72 OWL_DOES_DEFEND, 73 OWL_DOES_ATTACK, 74 OWL_CONNECTION_DEFENDS, 75 OWL_SUBSTANTIAL, 76 OWL_CONFIRM_SAFETY, 77 ANALYZE_SEMEAI, 78 NUM_CACHE_ROUTINES 79 }; 80 81 #define ROUTINE_NAMES \ 82 "owl_attack", \ 83 "owl_defend", \ 84 "semeai", \ 85 "find_defense", \ 86 "attack", \ 87 "connect", \ 88 "disconnect", \ 89 "break_in", \ 90 "block_off", \ 91 "owl_threaten_attack", \ 92 "owl_threatend_defense", \ 93 "owl_does_defend", \ 94 "owl_does_attack", \ 95 "owl_connection_defends", \ 96 "owl_substantial", \ 97 "owl_confirm_safety", \ 98 "analyze_semeai" 99 100 /* To prioritize between different types of reading, we give a cost 101 * ranking to each of the routines above: 102 * 103 * 4 semeai 104 * 3 owl 105 * 2 break-in 106 * 1 connection 107 * 0 tactical reading 108 * 109 * -1 is left at the end for a consistency check. 110 */ 111 #define ROUTINE_COSTS \ 112 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, -1 113 114 115 const char *routine_id_to_string(enum routine_id routine); 116 117 118 /* This is used for both the dragon status and safety fields. 119 * Also used for unconditional status in struct worm_data and for the 120 * final status computed by the aftermath code. 121 */ 122 enum dragon_status { 123 DEAD, 124 ALIVE, 125 CRITICAL, 126 UNKNOWN, 127 UNCHECKED, 128 CAN_THREATEN_ATTACK, 129 CAN_THREATEN_DEFENSE, 130 INESSENTIAL, 131 TACTICALLY_DEAD, 132 ALIVE_IN_SEKI, 133 STRONGLY_ALIVE, 134 INVINCIBLE, 135 INSUBSTANTIAL, 136 WHITE_TERRITORY, 137 BLACK_TERRITORY, 138 DAME, 139 NUM_DRAGON_STATUS 140 }; 141 142 #define DRAGON_STATUS_NAMES \ 143 "dead", \ 144 "alive", \ 145 "critical", \ 146 "unknown", \ 147 "unchecked", \ 148 "can threaten attack", \ 149 "can threaten defense", \ 150 "inessential", \ 151 "tactically dead", \ 152 "alive in seki", \ 153 "strongly alive", \ 154 "invincible", \ 155 "insubstantial", \ 156 "white_territory", \ 157 "black_territory", \ 158 "dame" 159 160 const char *status_to_string(enum dragon_status status); 161 162 163 /* Forward struct declarations. */ 164 struct pattern; 165 struct pattern_db; 166 struct fullboard_pattern; 167 struct corner_pattern; 168 struct corner_db; 169 struct half_eye_data; 170 struct movelist; 171 172 /* 173 * Try to match a pattern in the database to the board. Callbacks for 174 * each match. 175 */ 176 typedef void (*matchpat_callback_fn_ptr)(int anchor, int color, 177 struct pattern *, int rotation, 178 void *data); 179 typedef void (*fullboard_matchpat_callback_fn_ptr)(int move, 180 struct fullboard_pattern *, 181 int rotation); 182 typedef void (*corner_matchpat_callback_fn_ptr)(int move, int color, 183 struct corner_pattern *pattern, 184 int trans, 185 int *stones, int num_stones); 186 void matchpat(matchpat_callback_fn_ptr callback, int color, 187 struct pattern_db *pdb, void *callback_data, 188 signed char goal[BOARDMAX]); 189 void matchpat_goal_anchor(matchpat_callback_fn_ptr callback, int color, 190 struct pattern_db *pdb, void *callback_data, 191 signed char goal[BOARDMAX], int anchor_in_goal); 192 void fullboard_matchpat(fullboard_matchpat_callback_fn_ptr callback, 193 int color, struct fullboard_pattern *pattern); 194 void corner_matchpat(corner_matchpat_callback_fn_ptr callback, int color, 195 struct corner_db *database); 196 void dfa_match_init(void); 197 198 void reading_cache_init(int bytes); 199 void reading_cache_clear(void); 200 float reading_cache_default_size(void); 201 202 /* reading.c */ 203 int attack(int str, int *move); 204 int find_defense(int str, int *move); 205 int attack_and_defend(int str, 206 int *attack_code, int *attack_point, 207 int *defend_code, int *defense_point); 208 int attack_either(int astr, int bstr); 209 int defend_both(int astr, int bstr); 210 int break_through(int apos, int bpos, int cpos); 211 int attack_threats(int pos, int max_points, int moves[], int codes[]); 212 213 int restricted_defend1(int str, int *move, 214 int num_forbidden_moves, int *forbidden_moves); 215 int restricted_attack2(int str, int *move, 216 int num_forbidden_moves, int *forbidden_moves); 217 218 int simple_ladder(int str, int *move); 219 #define MOVE_ORDERING_PARAMETERS 67 220 void tune_move_ordering(int params[MOVE_ORDERING_PARAMETERS]); 221 void draw_reading_shadow(void); 222 223 /* persistent.c */ 224 void persistent_cache_init(void); 225 void purge_persistent_caches(void); 226 void clear_persistent_caches(void); 227 228 int search_persistent_reading_cache(enum routine_id routine, int str, 229 int *result, int *move); 230 void store_persistent_reading_cache(enum routine_id routine, int str, 231 int result, int move, int nodes); 232 void reading_hotspots(float values[BOARDMAX]); 233 int search_persistent_connection_cache(enum routine_id routine, 234 int str1, int str2, 235 int *result, int *move); 236 void store_persistent_connection_cache(enum routine_id routine, 237 int str1, int str2, 238 int result, int move, 239 int tactical_nodes, 240 signed char connection_shadow[BOARDMAX]); 241 int search_persistent_breakin_cache(enum routine_id routine, 242 int str, Hash_data *goal_hash, 243 int breakin_node_limit, 244 int *result, int *move); 245 void store_persistent_breakin_cache(enum routine_id routine, 246 int str, Hash_data *goal_hash, 247 int result, int move, 248 int tactical_nodes, 249 int breakin_node_limit, 250 signed char breakin_shadow[BOARDMAX]); 251 int search_persistent_owl_cache(enum routine_id routine, 252 int apos, int bpos, int cpos, 253 int *result, int *move, int *move2, 254 int *certain); 255 void store_persistent_owl_cache(enum routine_id routine, 256 int apos, int bpos, int cpos, 257 int result, int move, int move2, int certain, 258 int tactical_nodes, signed char goal[BOARDMAX], 259 int goal_color); 260 void owl_hotspots(float values[BOARDMAX]); 261 int search_persistent_semeai_cache(enum routine_id routine, 262 int apos, int bpos, int cpos, int color, 263 Hash_data *goal_hash, 264 int *resulta, int *resultb, 265 int *move, int *certain); 266 void store_persistent_semeai_cache(enum routine_id routine, 267 int apos, int bpos, int cpos, int color, 268 Hash_data *goal_hash, 269 int resulta, int resultb, 270 int move, int certain, int tactical_nodes, 271 signed char goala[BOARDMAX], 272 signed char goalb[BOARDMAX]); 273 274 275 /* readconnect.c */ 276 int string_connect(int str1, int str2, int *move); 277 int disconnect(int str1, int str2, int *move); 278 int fast_disconnect(int str1, int str2, int *move); 279 int non_transitivity(int str1, int str2, int str3, int *move); 280 281 int break_in(int str, const signed char goal[BOARDMAX], int *move); 282 int block_off(int str1, const signed char goal[BOARDMAX], int *move); 283 284 int obvious_false_eye(int pos, int color); 285 void estimate_lunch_eye_value(int lunch, int *min, int *probable, int *max, 286 int appreciate_one_two_lunches); 287 int owl_topological_eye(int pos, int color); 288 int vital_chain(int pos); 289 int confirm_safety(int move, int color, int *defense_point, 290 signed char safe_stones[BOARDMAX]); 291 int dragon_weak(int pos); 292 float dragon_weakness(int pos, int ignore_dead_dragons); 293 int size_of_biggest_critical_dragon(void); 294 void change_dragon_status(int dr, enum dragon_status status); 295 float blunder_size(int move, int color, int *defense_point, 296 signed char safe_stones[BOARDMAX]); 297 void set_depth_values(int level, int report_levels); 298 void modify_depth_values(int n); 299 void increase_depth_values(void); 300 void decrease_depth_values(void); 301 int get_depth_modification(void); 302 303 int safe_move(int move, int color); 304 int does_secure(int color, int move, int pos); 305 306 void compute_new_dragons(int dragon_origins[BOARDMAX]); 307 void join_dragons(int d1, int d2); 308 int dragon_escape(signed char goal[BOARDMAX], int color, 309 signed char escape_value[BOARDMAX]); 310 void compute_refined_dragon_weaknesses(void); 311 void compute_strategic_sizes(void); 312 313 struct eyevalue; 314 void compute_dragon_genus(int d, struct eyevalue *genus, int eye_to_exclude); 315 float crude_dragon_weakness(int safety, struct eyevalue *genus, int has_lunch, 316 float moyo_value, float escape_route); 317 318 int is_same_dragon(int d1, int d2); 319 int are_neighbor_dragons(int d1, int d2); 320 void mark_dragon(int pos, signed char mx[BOARDMAX], signed char mark); 321 int first_worm_in_dragon(int d); 322 int next_worm_in_dragon(int w); 323 int lively_dragon_exists(int color); 324 void compute_dragon_influence(void); 325 void set_strength_data(int color, signed char safe_stones[BOARDMAX], 326 float strength[BOARDMAX]); 327 void mark_inessential_stones(int color, signed char safe_stones[BOARDMAX]); 328 329 void add_cut(int apos, int bpos, int move); 330 void cut_reasons(int color); 331 332 void get_lively_stones(int color, signed char safe_stones[BOARDMAX]); 333 int is_same_worm(int w1, int w2); 334 int is_worm_origin(int w, int pos); 335 void propagate_worm(int pos); 336 void find_cuts(void); 337 void find_connections(void); 338 339 /* movelist.c */ 340 int movelist_move_known(int move, int max_points, int points[], int codes[]); 341 void movelist_change_point(int move, int code, int max_points, 342 int points[], int codes[]); 343 344 /* surround.c */ 345 int compute_surroundings(int pos, int apos, int showboard, 346 int *surround_size); 347 int is_surrounded(int pos); 348 int does_surround(int move, int dragon); 349 void reset_surround_data(void); 350 int surround_map(int dr, int pos); 351 352 /* functions to add (or remove) move reasons */ 353 void collect_move_reasons(int color); 354 355 void clear_move_reasons(void); 356 void add_lunch(int eater, int food); 357 void add_attack_move(int pos, int ww, int code); 358 void add_defense_move(int pos, int ww, int code); 359 void add_attack_threat_move(int pos, int ww, int code); 360 void remove_attack_threat_move(int pos, int ww); 361 void add_defense_threat_move(int pos, int ww, int code); 362 void add_connection_move(int pos, int dr1, int dr2); 363 void add_cut_move(int pos, int dr1, int dr2); 364 void add_antisuji_move(int pos); 365 void add_semeai_move(int pos, int dr); 366 void add_potential_semeai_attack(int pos, int dr1, int dr2); 367 void add_potential_semeai_defense(int pos, int dr1, int dr2); 368 void add_semeai_threat(int pos, int dr); 369 370 void add_owl_attack_move(int pos, int dr, int kworm, int code); 371 void add_owl_defense_move(int pos, int dr, int code); 372 void add_owl_attack_threat_move(int pos, int dr, int code); 373 void add_owl_defense_threat_move(int pos, int dr, int code); 374 void add_owl_prevent_threat_move(int pos, int dr); 375 void add_owl_uncertain_defense_move(int pos, int dr); 376 void add_owl_uncertain_attack_move(int pos, int dr); 377 void add_gain_move(int pos, int target1, int target2); 378 void add_loss_move(int pos, int target1, int target2); 379 380 void add_my_atari_atari_move(int pos, int size); 381 void add_your_atari_atari_move(int pos, int size); 382 void add_vital_eye_move(int pos, int eyespace, int color); 383 void add_invasion_move(int pos); 384 void add_expand_territory_move(int pos); 385 void add_expand_moyo_move(int pos); 386 void add_strategical_attack_move(int pos, int dr); 387 void add_strategical_defense_move(int pos, int dr); 388 void add_worthwhile_threat_move(int pos); 389 void add_replacement_move(int from, int to, int color); 390 391 /* Parameters to add_either_move and add_all_move */ 392 #define ATTACK_STRING 1 393 #define DEFEND_STRING 2 394 void add_either_move(int pos, int reason1, int target1, 395 int reason2, int target2); 396 void add_all_move(int pos, int reason1, int target1, 397 int reason2, int target2); 398 399 int set_minimum_move_value(int pos, float value); 400 void set_maximum_move_value(int pos, float value); 401 void set_minimum_territorial_value(int pos, float value); 402 void set_maximum_territorial_value(int pos, float value); 403 void add_shape_value(int pos, float value); 404 void add_followup_value(int pos, float value); 405 void add_reverse_followup_value(int pos, float value); 406 int list_move_reasons(FILE *out, int pos); 407 void print_all_move_values(FILE *output); 408 void record_top_move(int move, float val); 409 void remove_top_move(int move); 410 void scale_randomness(int pos, float scaling); 411 void compute_move_probabilities(float probabilities[BOARDMAX]); 412 413 void register_good_attack_threat(int move, int target); 414 int is_known_good_attack_threat(int move, int target); 415 416 void register_known_safe_move(int move); 417 int is_known_safe_move(int move); 418 419 int get_attack_threats(int pos, int max_strings, int strings[]); 420 int get_defense_threats(int pos, int max_strings, int strings[]); 421 void get_saved_worms(int pos, signed char saved[BOARDMAX]); 422 void get_saved_dragons(int pos, signed char saved[BOARDMAX]); 423 void mark_safe_stones(int color, int move_pos, 424 const signed char saved_dragons[BOARDMAX], 425 const signed char saved_worms[BOARDMAX], 426 signed char safe_stones[BOARDMAX]); 427 428 429 int owl_lively(int pos); 430 int owl_escape_value(int pos); 431 int owl_goal_dragon(int pos); 432 int owl_eyespace(int pos); 433 int owl_big_eyespace(int pos); 434 int owl_mineye(int pos); 435 int owl_maxeye(int pos); 436 int owl_proper_eye(int pos); 437 int owl_eye_size(int pos); 438 int owl_lunch(int str); 439 int owl_strong_dragon(int pos); 440 void owl_reasons(int color); 441 442 void unconditional_life(int unconditional_territory[BOARDMAX], int color); 443 void clear_unconditionally_meaningless_moves(void); 444 void find_unconditionally_meaningless_moves(int unconditional_territory[BOARDMAX], 445 int color); 446 int unconditionally_meaningless_move(int pos, int color, 447 int *replacement_move); 448 void unconditional_move_reasons(int color); 449 450 void find_superstring(int str, int *num_stones, int *stones); 451 void find_superstring_conservative(int str, int *num_stones, int *stones); 452 void find_superstring_liberties(int str, int *liberties, int *libs, 453 int liberty_cap); 454 void find_proper_superstring_liberties(int str, int *liberties, int *libs, 455 int liberty_cap); 456 void find_superstring_stones_and_liberties(int str, int *num_stones, 457 int *stones, int *liberties, 458 int *libs, int liberty_cap); 459 void superstring_chainlinks(int str, int *num_adj, int adj[MAXCHAIN], 460 int liberty_cap); 461 void proper_superstring_chainlinks(int str, int *num_adj, 462 int adj[MAXCHAIN], int liberty_cap); 463 464 int place_fixed_handicap(int handicap); /* place stones on board only */ 465 int place_free_handicap(int handicap); /* place stones on board only */ 466 int free_handicap_remaining_stones(void); 467 int free_handicap_total_stones(void); 468 469 470 /* Various different strategies for finding a move */ 471 void fuseki(int color); 472 void semeai(void); 473 void semeai_move_reasons(int color); 474 void shapes(int color); 475 void endgame(int color); 476 void endgame_shapes(int color); 477 478 void combinations(int color); 479 int atari_atari(int color, int *attack_move, 480 signed char defense_moves[BOARDMAX], 481 int save_verbose); 482 int atari_atari_confirm_safety(int color, int tpos, int *move, int minsize, 483 const signed char saved_dragons[BOARDMAX], 484 const signed char saved_worms[BOARDMAX]); 485 486 int atari_atari_blunder_size(int color, int tpos, 487 signed char defense_moves[BOARDMAX], 488 const signed char safe_stones[BOARDMAX]); 489 490 int review_move_reasons(int *move, float *value, int color, 491 float pure_threat_value, float our_score, 492 int allowed_moves[BOARDMAX], 493 int use_thrashing_dragon_heuristics); 494 void prepare_move_influence_debugging(int pos, int color); 495 int fill_liberty(int *move, int color); 496 int aftermath_genmove(int color, int do_capture_dead_stones, 497 int allowed_moves[BOARDMAX]); 498 enum dragon_status aftermath_final_status(int color, int pos); 499 500 int mc_get_size_of_pattern_values_table(void); 501 int mc_load_patterns_from_db(const char *filename, unsigned int *values); 502 void mc_init_patterns(const unsigned int *values); 503 int choose_mc_patterns(char *name); 504 void list_mc_patterns(void); 505 506 void uct_genmove(int color, int *move, int *forbidden_moves, 507 int *allowed_moves, int nodes, float *move_values, 508 int *move_frequencies); 509 510 int owl_attack(int target, int *attack_point, int *certain, int *kworm); 511 int owl_defend(int target, int *defense_point, int *certain, int *kworm); 512 int owl_threaten_attack(int target, int *attack1, int *attack2); 513 int owl_threaten_defense(int target, int *defend1, int *defend2); 514 int owl_does_defend(int move, int target, int *kworm); 515 int owl_confirm_safety(int move, int target, int *defense_point, int *kworm); 516 int owl_does_attack(int move, int target, int *kworm); 517 int owl_connection_defends(int move, int target1, int target2); 518 int owl_substantial(int str); 519 void owl_analyze_semeai(int apos, int bpos, 520 int *resulta, int *resultb, int *semeai_move, 521 int owl, int *semeai_result_certain); 522 void owl_analyze_semeai_after_move(int move, int color, int apos, int bpos, 523 int *resulta, int *resultb, 524 int *semeai_move, int owl, 525 int *semeai_result_certain, 526 int recompute_dragons); 527 528 void set_limit_search(int value); 529 void set_search_diamond(int pos); 530 void reset_search_mask(void); 531 void set_search_mask(int pos, int value); 532 int oracle_play_move(int pos, int color); 533 void consult_oracle(int color); 534 void summon_oracle(void); 535 void oracle_loadsgf(char *infilename, char *untilstring); 536 int oracle_threatens(int move, int target); 537 int within_search_area(int pos); 538 int metamachine_genmove(int color, float *value); 539 void draw_search_area(void); 540 541 int genmove_restricted(int color, int allowed_moves[BOARDMAX]); 542 543 void change_attack(int str, int move, int acode); 544 void change_defense(int str, int move, int dcode); 545 void change_attack_threat(int str, int move, int acode); 546 void change_defense_threat(int str, int move, int dcode); 547 int attack_move_known(int move, int str); 548 int defense_move_known(int move, int str); 549 int attack_threat_move_known(int move, int str); 550 int defense_threat_move_known(int move, int str); 551 void worm_reasons(int color); 552 553 int semeai_move_reason_known(int move, int dr); 554 555 int does_attack(int move, int str); 556 int does_defend(int move, int str); 557 int double_atari(int move, int color, float *value, 558 signed char safe_stones[BOARDMAX]); 559 int playing_into_snapback(int move, int color); 560 int play_attack_defend_n(int color, int do_attack, int num_moves, ...); 561 int play_attack_defend2_n(int color, int do_attack, int num_moves, ...); 562 int play_break_through_n(int color, int num_moves, ...); 563 int play_connect_n(int color, int do_connect, int num_moves, ...); 564 int play_lib_n(int color, int num_moves, ...); 565 int cut_possible(int pos, int color); 566 int defend_against(int move, int color, int apos); 567 int somewhere(int color, int check_alive, int num_moves, ...); 568 int visible_along_edge(int color, int apos, int bpos); 569 int test_symmetry_after_move(int move, int color, int strict); 570 571 /* Printmoyo values, specified by -m flag. */ 572 #define PRINTMOYO_TERRITORY 0x01 573 #define PRINTMOYO_MOYO 0x02 574 #define PRINTMOYO_AREA 0x04 575 /* The following have been borrowed by the influence functions below. */ 576 #define PRINTMOYO_INITIAL_INFLUENCE 0x08 577 #define PRINTMOYO_PRINT_INFLUENCE 0x10 578 #define PRINTMOYO_NUMERIC_INFLUENCE 0x20 579 #define PRINTMOYO_PERMEABILITY 0x40 580 #define PRINTMOYO_STRENGTH 0x80 581 #define PRINTMOYO_ATTENUATION 0x100 582 #define PRINTMOYO_VALUE_TERRITORY 0x200 583 584 /* These values are used to communicate whether stones are safe or 585 * have been saved, when computing influence. 586 */ 587 #define INFLUENCE_SAFE_STONE 1 588 #define INFLUENCE_SAVED_STONE 2 589 590 /* These values are used to communicate the status of stones when analyzing 591 * a move for potentially being a blunder. 592 */ 593 /* dead 0 */ 594 #define SAFE_STONE 1 595 #define OWL_SAVED_STONE 2 596 597 /* This format is used when exporting the moyo segmentation. */ 598 #define MAX_MOYOS MAX_BOARD*MAX_BOARD 599 600 struct moyo_data 601 { 602 int number; /* Number of moyos. */ 603 int segmentation[BOARDMAX]; /* Numbers the moyos. */ 604 int size[MAX_MOYOS]; 605 int owner[MAX_MOYOS]; 606 float territorial_value[MAX_MOYOS]; 607 }; 608 609 /* We use a forward declaration of influence_data so that the rest 610 * of the engine can reference influence data. It can only be accessed 611 * in influence.c, however! 612 */ 613 struct influence_data; 614 extern struct influence_data initial_black_influence; 615 extern struct influence_data initial_white_influence; 616 extern struct influence_data move_influence; 617 extern struct influence_data followup_influence; 618 619 #define INITIAL_INFLUENCE(color) ((color) == WHITE ? \ 620 &initial_white_influence \ 621 : &initial_black_influence) 622 #define OPPOSITE_INFLUENCE(color) (INITIAL_INFLUENCE(OTHER_COLOR(color))) 623 624 #define DEFAULT_STRENGTH 100.0 625 626 /* Influence functions. */ 627 void compute_influence(int color, const signed char safe_stones[BOARDMAX], 628 const float strength[BOARDMAX], 629 struct influence_data *q, 630 int move, const char *trace_message); 631 void compute_followup_influence(const struct influence_data *base, 632 struct influence_data *q, 633 int move, const char *trace_message); 634 void compute_escape_influence(int color, 635 const signed char safe_stones[BOARDMAX], 636 const signed char goal[BOARDMAX], 637 const float strength[BOARDMAX], 638 signed char escape_value[BOARDMAX]); 639 640 float influence_delta_territory(const struct influence_data *base, 641 const struct influence_data *q, int color, 642 int move); 643 int retrieve_delta_territory_cache(int pos, int color, float *move_value, 644 float *followup_value, 645 const struct influence_data *base, 646 Hash_data safety_hash); 647 void store_delta_territory_cache(int pos, int color, float move_value, 648 float followup_value, 649 const struct influence_data *base, 650 Hash_data safety_hash); 651 652 int whose_territory(const struct influence_data *q, int pos); 653 int whose_moyo(const struct influence_data *q, int pos); 654 int whose_moyo_restricted(const struct influence_data *q, int pos); 655 int whose_area(const struct influence_data *q, int pos); 656 float influence_territory(const struct influence_data *q, int pos, int color); 657 void influence_get_territory_segmentation(struct influence_data *q, 658 struct moyo_data *moyo); 659 void get_influence(const struct influence_data *q, 660 float white_influence[BOARDMAX], 661 float black_influence[BOARDMAX], 662 float white_strength[BOARDMAX], 663 float black_strength[BOARDMAX], 664 float white_attenuation[BOARDMAX], 665 float black_attenuation[BOARDMAX], 666 float white_permeability[BOARDMAX], 667 float black_permeability[BOARDMAX], 668 float territory_value[BOARDMAX], 669 int influence_regions[BOARDMAX], 670 int non_territory[BOARDMAX]); 671 float influence_score(const struct influence_data *q, int chinese_rules); 672 float game_status(int color); 673 void influence_mark_non_territory(int pos, int color); 674 int influence_considered_lively(const struct influence_data *q, int pos); 675 void influence_erase_territory(struct influence_data *q, int pos, int color); 676 677 void break_territories(int color_to_move, struct influence_data *q, 678 int store, int pos); 679 void clear_break_in_list(void); 680 void break_in_move_reasons(int color); 681 682 void choose_strategy(int color, float our_score, float game_status); 683 684 /* Eye space functions. */ 685 int is_eye_space(int pos); 686 int is_proper_eye_space(int pos); 687 int is_marginal_eye_space(int pos); 688 int max_eye_value(int pos); 689 void test_eyeshape(int eyesize, int *eye_vertices); 690 int analyze_eyegraph(const char *coded_eyegraph, struct eyevalue *value, 691 char *analyzed_eyegraph); 692 693 694 /* debugging support */ 695 void goaldump(const signed char goal[BOARDMAX]); 696 void move_considered(int move, float value); 697 698 699 /* Transformation stuff. */ 700 #define MAX_OFFSET (2*MAX_BOARD - 1) * (2*MAX_BOARD - 1) 701 #define OFFSET(dx, dy)\ 702 ((dy + MAX_BOARD - 1) * (2*MAX_BOARD - 1) + (dx + MAX_BOARD - 1)) 703 #define OFFSET_DELTA(dx, dy) (OFFSET(dx, dy) - OFFSET(0, 0)) 704 #define CENTER_OFFSET(offset) (offset - OFFSET(0, 0)) 705 #define TRANSFORM(offset, trans) (transformation[offset][trans]) 706 #define AFFINE_TRANSFORM(offset, trans, delta)\ 707 (transformation[offset][trans] + delta) 708 #define TRANSFORM2(x, y, tx, ty, trans)\ 709 do {\ 710 *tx = transformation2[trans][0][0] * (x) + transformation2[trans][0][1] * (y);\ 711 *ty = transformation2[trans][1][0] * (x) + transformation2[trans][1][1] * (y);\ 712 } while (0) 713 714 715 /* ================================================================ */ 716 /* global variables */ 717 /* ================================================================ */ 718 719 extern int disable_threat_computation; 720 extern int disable_endgame_patterns; 721 extern int doing_scoring; 722 723 /* Reading parameters */ 724 extern int depth; /* deep reading cutoff */ 725 extern int backfill_depth; /* deep reading cutoff */ 726 extern int backfill2_depth; /* deep reading cutoff */ 727 extern int break_chain_depth; /* deep reading cutoff */ 728 extern int superstring_depth; /* deep reading cutoff */ 729 extern int branch_depth; /* deep reading cutoff */ 730 extern int fourlib_depth; /* deep reading cutoff */ 731 extern int ko_depth; /* deep ko reading cutoff */ 732 extern int aa_depth; /* deep global reading cutoff */ 733 extern int depth_offset; /* keeps track of temporary depth changes */ 734 extern int owl_distrust_depth; /* below this owl trusts the optics code */ 735 extern int owl_branch_depth; /* below this owl tries only one variation */ 736 extern int owl_reading_depth; /* owl does not read below this depth */ 737 extern int owl_node_limit; /* maximum number of nodes considered */ 738 extern int semeai_branch_depth; 739 extern int semeai_branch_depth2; 740 extern int semeai_node_limit; 741 extern int connect_depth; 742 extern int connect_depth2; 743 extern int connection_node_limit; 744 extern int breakin_depth; 745 extern int breakin_node_limit; 746 extern int semeai_variations; /* max variations considered reading semeai */ 747 extern float best_move_values[10]; 748 extern int best_moves[10]; 749 750 extern int experimental_owl_ext; /* use experimental owl (GAIN/LOSS) */ 751 extern int experimental_semeai; /* use experimental semeai module */ 752 extern int experimental_connections; /* use experimental connection module */ 753 extern int alternate_connections; /* use alternate connection module */ 754 extern int owl_threats; /* compute owl threats */ 755 extern int experimental_break_in; /* use experimental module breakin.c */ 756 extern int cosmic_gnugo; /* use center oriented influence */ 757 extern int large_scale; /* seek large scale captures */ 758 759 extern int thrashing_dragon; /* Dead opponent's dragon trying to live */ 760 extern signed char thrashing_stone[BOARDMAX]; /* All thrashing stones. */ 761 762 extern int transformation[MAX_OFFSET][8]; 763 extern const int transformation2[8][2][2]; 764 765 766 /* Arrays pointing out the closest worms from each vertex. The first 767 * one is the closest worms of either color, the last two ones ignore 768 * worms of the other color. Beyond a certain distance from any worm 769 * no close worm is listed at all. Only the closest worm is listed 770 * and if more than one are equally close they are all listed. The 771 * number of equally close worms is given in the number_*_worms 772 * arrays. If more than MAX_CLOSE_WORMS are equally close, none is 773 * listed. 774 * 775 * See compute_effective_worm_sizes() in worm.c for details. 776 */ 777 #define MAX_CLOSE_WORMS 4 778 extern int close_worms[BOARDMAX][MAX_CLOSE_WORMS]; 779 extern int number_close_worms[BOARDMAX]; 780 extern int close_black_worms[BOARDMAX][MAX_CLOSE_WORMS]; 781 extern int number_close_black_worms[BOARDMAX]; 782 extern int close_white_worms[BOARDMAX][MAX_CLOSE_WORMS]; 783 extern int number_close_white_worms[BOARDMAX]; 784 785 extern int false_eye_territory[BOARDMAX]; 786 extern int forced_backfilling_moves[BOARDMAX]; 787 788 extern double slowest_time; /* Timing statistics */ 789 extern int slowest_move; 790 extern int slowest_movenum; 791 extern double total_time; 792 793 794 struct eyevalue { 795 unsigned char a; /* number of eyes if attacker plays first twice */ 796 unsigned char b; /* number of eyes if attacker plays first */ 797 unsigned char c; /* number of eyes if defender plays first */ 798 unsigned char d; /* number of eyes if defender plays first twice */ 799 }; 800 801 802 struct half_eye_data { 803 float value; /* Topological eye value. */ 804 unsigned char type; /* HALF_EYE or FALSE_EYE; */ 805 int num_attacks; /* number of attacking points */ 806 int attack_point[4]; /* the moves to attack a topological halfeye */ 807 int num_defenses; /* number of defending points */ 808 int defense_point[4]; /* the moves to defend a topological halfeye */ 809 }; 810 811 /* array of half-eye data */ 812 extern struct half_eye_data half_eye[BOARDMAX]; 813 814 /* 815 * data concerning a worm. A copy is kept at each vertex of the worm. 816 */ 817 818 #define MAX_TACTICAL_POINTS 10 819 820 struct worm_data { 821 int color; /* its color */ 822 int size; /* its cardinality */ 823 float effective_size; /* stones and surrounding spaces */ 824 int origin; /* the origin of the string. Two vertices are in */ 825 /* the same worm iff they have same origin. */ 826 int liberties; /* number of liberties */ 827 int liberties2; /* number of second order liberties */ 828 int liberties3; /* third order liberties (empty vertices at distance 3) */ 829 int liberties4; /* fourth order liberties */ 830 int lunch; /* if lunch != 0 then lunch points to a boundary */ 831 /* worm which can be captured easily. */ 832 int cutstone; /* 1=potential cutting stone; 2=cutting stone */ 833 int cutstone2; /* Number of potential cuts involving the worm. */ 834 int genus; /* number of connected components of the complement, less one */ 835 int inessential; /* 1=inessential worm */ 836 int invincible; /* 1=strongly unconditionally non-capturable */ 837 enum dragon_status unconditional_status; /* ALIVE, DEAD, WHITE_TERRITORY, 838 BLACK_TERRITORY, UNKNOWN */ 839 840 /* The following arrays keeps track of up to MAX_TACTICAL_POINTS 841 * different attack, defense, attack threat, and defense threat 842 * points with corresponding result codes. (0 = loss, 1 = bad ko, 2 843 * = good ko, 3 = win). The arrays are guaranteed to be sorted with 844 * respect to the codes so that the first element contains the best 845 * result. 846 */ 847 int attack_points[MAX_TACTICAL_POINTS]; 848 int attack_codes[MAX_TACTICAL_POINTS]; 849 int defense_points[MAX_TACTICAL_POINTS]; 850 int defense_codes[MAX_TACTICAL_POINTS]; 851 int attack_threat_points[MAX_TACTICAL_POINTS]; 852 int attack_threat_codes[MAX_TACTICAL_POINTS]; 853 int defense_threat_points[MAX_TACTICAL_POINTS]; 854 int defense_threat_codes[MAX_TACTICAL_POINTS]; 855 }; 856 857 extern struct worm_data worm[BOARDMAX]; 858 859 /* Surround cache (see surround.c) */ 860 861 #define MAX_SURROUND 10 862 863 struct surround_data { 864 int dragon_number; /* number of the (surrounded) beast */ 865 signed char surround_map[BOARDMAX]; /* surround map */ 866 }; 867 868 extern struct surround_data surroundings[MAX_SURROUND]; 869 extern int surround_pointer; 870 871 /* 872 * data concerning a dragon. A copy is kept at each stone of the string. 873 */ 874 875 struct dragon_data { 876 int color; /* its color */ 877 int id; /* the index into the dragon2 array */ 878 int origin; /* the origin of the dragon. Two vertices are in the same */ 879 /* dragon iff they have same origin. */ 880 int size; /* size of the dragon */ 881 float effective_size; /* stones and surrounding spaces */ 882 enum dragon_status crude_status; /* (ALIVE, DEAD, UNKNOWN, CRITICAL) */ 883 enum dragon_status status; /* best trusted status */ 884 }; 885 886 extern struct dragon_data dragon[BOARDMAX]; 887 888 /* Supplementary data concerning a dragon. Only one copy is stored per 889 * dragon in the dragon2 array. 890 */ 891 892 #define MAX_NEIGHBOR_DRAGONS 10 893 894 struct dragon_data2 { 895 int origin; /* the origin of the dragon */ 896 int adjacent[MAX_NEIGHBOR_DRAGONS]; /* adjacent dragons */ 897 int neighbors; /* number of adjacent dragons */ 898 int hostile_neighbors; /* neighbors of opposite color */ 899 900 int moyo_size; /* size of surrounding influence moyo, */ 901 float moyo_territorial_value; /* ...and its territorial value */ 902 enum dragon_status safety; /* a more detailed status estimate */ 903 float weakness; /* a continuous estimate of the dragon's safety */ 904 float weakness_pre_owl; /* dragon safety based on pre-owl computations */ 905 float strategic_size; /* An effective size including weakness of neighbors */ 906 int escape_route; /* a measurement of likelihood of escape */ 907 struct eyevalue genus; /* the number of eyes (approximately) */ 908 int heye; /* coordinates of a half eye */ 909 int lunch; /* if lunch != 0 then lunch points to a boundary worm which */ 910 /* can be captured easily. */ 911 int surround_status; /* Is it surrounded? */ 912 int surround_size; /* Size of the surrounding area */ 913 914 int semeais; /* number of semeais in which the dragon is involved */ 915 int semeai_defense_code ;/* Result code for semeai defense. */ 916 int semeai_defense_point;/* Move found by semeai code to rescue dragon */ 917 int semeai_defense_certain; 918 int semeai_defense_target; /* The opponent dragon involved in the semeai */ 919 int semeai_attack_code ; /* Result code for semeai attack. */ 920 int semeai_attack_point; /* Move found by semeai code to kill dragon */ 921 int semeai_attack_certain; 922 int semeai_attack_target; /* The opponent dragon involved in the semeai */ 923 enum dragon_status owl_threat_status; /* CAN_THREATEN_ATTACK/DEFENSE */ 924 enum dragon_status owl_status; /* (ALIVE, DEAD, UNKNOWN, CRITICAL, UNCHECKED) */ 925 int owl_attack_point; /* vital point for attack */ 926 int owl_attack_code; /* ko result code */ 927 int owl_attack_certain; /* 0 if owl reading node limit is reached */ 928 int owl_attack_node_count; 929 int owl_second_attack_point;/* if attacker gets both attack points, wins */ 930 int owl_defense_point; /* vital point for defense */ 931 int owl_defense_code; /* ko result code */ 932 int owl_defense_certain; /* 0 if owl reading node limit is reached */ 933 int owl_second_defense_point;/* if defender gets both attack points, wins */ 934 int owl_attack_kworm; /* only valid when owl_attack_code is GAIN */ 935 int owl_defense_kworm; /* only valid when owl_defense_code is LOSS */ 936 }; 937 938 /* dragon2 is dynamically allocated */ 939 extern int number_of_dragons; 940 extern struct dragon_data2 *dragon2; 941 942 /* Macros for accessing the dragon2 data with board coordinates and 943 * the dragon data with a dragon id. 944 */ 945 #if 1 /* Trust DRAGON2 accesses */ 946 #define DRAGON2(pos) dragon2[dragon[pos].id] 947 #else 948 struct dragon_data2 *dragon2_func(int pos); 949 #define DRAGON2(pos) (*dragon2_func(pos)) 950 #endif 951 952 #define DRAGON(d) dragon[dragon2[d].origin] 953 954 extern float white_score, black_score; 955 956 /* Global variables to tune strategy. */ 957 958 extern float minimum_value_weight; 959 extern float maximum_value_weight; 960 extern float invasion_malus_weight; 961 extern float strategical_weight; 962 extern float territorial_weight; 963 extern float attack_dragon_weight; 964 extern float followup_weight; 965 966 struct aftermath_data { 967 int white_captured; 968 int black_captured; 969 int white_prisoners; 970 int black_prisoners; 971 int white_territory; 972 int black_territory; 973 int white_area; 974 int black_area; 975 int white_control[BOARDMAX]; 976 int black_control[BOARDMAX]; 977 enum dragon_status final_status[BOARDMAX]; 978 }; 979 980 #define MAX_EYE_ATTACKS 3 981 982 struct eye_data { 983 int color; /* BLACK, WHITE, or GRAY */ 984 int esize; /* size of the eyespace */ 985 int msize; /* number of marginal vertices */ 986 int origin; /* The origin */ 987 struct eyevalue value; /* Number of eyes. */ 988 989 /* The above fields are constant on the whole eyespace. */ 990 /* ---------------------------------------------------------------- */ 991 /* The below fields are not. */ 992 993 unsigned char marginal; /* This vertex is marginal */ 994 unsigned char neighbors; /* number of neighbors in eyespace */ 995 unsigned char marginal_neighbors; /* number of marginal neighbors */ 996 }; 997 998 struct vital_eye_points { 999 int attack_points[MAX_EYE_ATTACKS]; 1000 int defense_points[MAX_EYE_ATTACKS]; 1001 }; 1002 1003 extern struct vital_eye_points black_vital_points[BOARDMAX]; 1004 extern struct vital_eye_points white_vital_points[BOARDMAX]; 1005 1006 extern struct eye_data white_eye[BOARDMAX]; 1007 extern struct eye_data black_eye[BOARDMAX]; 1008 1009 /* Array with the information which was previously stored in the cut 1010 * field and in the INHIBIT_CONNECTION bit of the type field in struct 1011 * eye_data. 1012 */ 1013 extern int cutting_points[BOARDMAX]; 1014 1015 /* The following declarations have to be postponed until after the 1016 * definition of struct eye_data or struct half_eye_data. 1017 */ 1018 1019 void compute_eyes(int pos, struct eyevalue *value, 1020 int *attack_point, int *defense_point, 1021 struct eye_data eye[BOARDMAX], 1022 struct half_eye_data heye[BOARDMAX], 1023 int add_moves); 1024 void compute_eyes_pessimistic(int pos, struct eyevalue *value, 1025 int *pessimistic_min, 1026 int *attack_point, int *defense_point, 1027 struct eye_data eye[BOARDMAX], 1028 struct half_eye_data heye[BOARDMAX]); 1029 void propagate_eye(int pos, struct eye_data eye[BOARDMAX]); 1030 int find_eye_dragons(int origin, struct eye_data eye[BOARDMAX], int eye_color, 1031 int dragons[], int max_dragons); 1032 void make_domains(struct eye_data b_eye[BOARDMAX], 1033 struct eye_data w_eye[BOARDMAX], 1034 int owl_call); 1035 void partition_eyespaces(struct eye_data eye[BOARDMAX], int color); 1036 void find_half_and_false_eyes(int color, struct eye_data eye[BOARDMAX], 1037 struct half_eye_data heye[BOARDMAX], 1038 int find_mask[BOARDMAX]); 1039 1040 void set_eyevalue(struct eyevalue *e, int a, int b, int c, int d); 1041 int min_eye_threat(struct eyevalue *e); 1042 int min_eyes(struct eyevalue *e); 1043 int max_eyes(struct eyevalue *e); 1044 int max_eye_threat(struct eyevalue *e); 1045 void add_eyevalues(struct eyevalue *e1, struct eyevalue *e2, 1046 struct eyevalue *sum); 1047 int eye_move_urgency(struct eyevalue *e); 1048 char *eyevalue_to_string(struct eyevalue *e); 1049 1050 int is_halfeye(struct half_eye_data heye[BOARDMAX], int pos); 1051 int is_false_eye(struct half_eye_data heye[BOARDMAX], int pos); 1052 1053 #endif /* _LIBERTY_H_ */ 1054 1055 1056 /* 1057 * Local Variables: 1058 * tab-width: 8 1059 * c-basic-offset: 2 1060 * End: 1061 */ 1062