/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* This is GNU Go, a Go program. Contact gnugo@gnu.org, or see *
* http://www.gnu.org/software/gnugo/ for more information. *
* Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, *
* 2008 and 2009 by the Free Software Foundation. *
* This program is free software; you can redistribute it and/or *
* modify it under the terms of the GNU General Public License as *
* published by the Free Software Foundation - version 3 or *
* (at your option) any later version. *
* This program is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU General Public License in file COPYING for more details. *
* You should have received a copy of the GNU General Public *
* License along with this program; if not, write to the Free *
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor, *
* Boston, MA 02111, USA. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
* The code in this file implements "Optics With Limit-negotiation (OWL)."
* The life and death code in optics.c, works reasonably well as long as the
* position is in a *terminal position*, which we define to be one where there
* are no moves left which can expand the eye space, or limit it. In
* situations where the dragon is surrounded, yet has room to thrash around a
* bit making eyes, a simple application of the graph-based analysis will not
* work. Instead, a bit of reading is needed to reach a terminal position.
* The defender tries to expand his eyespace, the attacker to limit it, and
* when neither finds an effective move, the position is evaluated. We call
* this type of life and death reading *Optics With Limit-negotiation* (OWL).
* The owl is noted for its keen vision
* and (purported) wisdom.
#define MAX_MOVES 3 /* maximum number of branches at each node */
#define MAX_SEMEAI_MOVES 6 /* semeai branch factor */
#define MAX_SEMEAI_DEPTH 100 /* Don't read below this depth */
#define MAX_GOAL_WORMS 15 /* maximum number of worms in a dragon to be */
/* cataloged. NOTE: Must fit in value2 in hashnode! */
#define MAX_ESCAPE 3 /* After this many escape moves, owl_determine_life is */
signed char goal
[BOARDMAX
];
signed char boundary
[BOARDMAX
];
/* Same as goal, except never anything is removed from it. */
signed char cumulative_goal
[BOARDMAX
];
/* FIXME: neighbors[] and escape_values[] are never recomputed.
* Consider moving these arrays from stack to a static or
* dynamic variable so it is not copied around in
* do_push_owl(). Be aware of semeai code though.
signed char neighbors
[BOARDMAX
];
signed char escape_values
[BOARDMAX
];
struct eye_data my_eye
[BOARDMAX
];
/* array of half-eye data for use during owl reading */
struct half_eye_data half_eye
[BOARDMAX
];
int lunch_attack_code
[MAX_LUNCHES
];
int lunch_attack_point
[MAX_LUNCHES
];
int lunch_defend_code
[MAX_LUNCHES
];
int lunch_defense_point
[MAX_LUNCHES
];
signed char inessential
[BOARDMAX
];
int lunches_are_current
; /* If true, owl lunch data is current */
signed char safe_move_cache
[BOARDMAX
];
/* This is used to organize the owl stack. */
struct local_owl_data
*restore_from
;
static int result_certain
;
static int local_owl_node_counter
;
static int global_owl_node_counter
= 0;
static struct local_owl_data
*current_owl_data
;
static struct local_owl_data
*other_owl_data
;
static int goal_worms_computed
= 0;
static int owl_goal_worm
[MAX_GOAL_WORMS
];
SAME_DRAGON_NOT_CONNECTED
,
SAME_DRAGON_MAYBE_CONNECTED
,
SAME_DRAGON_ALL_CONNECTED
struct matched_pattern_data
;
int pos
; /* move coordinate */
const char *name
; /* name of the pattern suggesting the move */
/* whether the move extends the dragon or not */
enum same_dragon_value same_dragon
;
int lunch
; /* Position of a lunch, if applicable.*/
int escape
; /* true if an escape pattern is matched */
int defense_pos
; /* defense coordinate for vital owl attack patterns. */
int cuts
[MAX_CUTS
]; /* strings of the goal that might get cut off */
/* pointer to pattern data, used for SAME_DRAGON_ALL_CONNECTED */
struct matched_pattern_data
*pattern_data
;
struct matched_pattern_data
{
/* To link combinable patterns in chains. */
struct matched_patterns_list_data
{
int counter
; /* Number of patterns in the list. */
int used
; /* How many patterns have already been used?*/
struct matched_pattern_data
*pattern_list
;
int first_pattern_index
[BOARDMAX
];
struct matched_pattern_data
**pattern_heap
;
void dump_pattern_list(struct matched_patterns_list_data
*list
);
static int do_owl_attack(int str
, int *move
, int *wormid
,
struct local_owl_data
*owl
, int escape
);
static int do_owl_defend(int str
, int *move
, int *wormid
,
struct local_owl_data
*owl
, int escape
);
static void owl_shapes(struct matched_patterns_list_data
*list
,
struct owl_move_data moves
[MAX_MOVES
], int color
,
struct local_owl_data
*owl
, struct pattern_db
*type
);
static void collect_owl_shapes_callbacks(int anchor
, int color
,
struct pattern
*pattern_db
,
static void pattern_list_prepare(struct matched_patterns_list_data
*list
);
static void pattern_list_build_heap(struct matched_patterns_list_data
*list
);
static void pattern_list_pop_heap_once(struct matched_patterns_list_data
*list
);
static void pattern_list_sink_heap_top_element(struct matched_patterns_list_data
static int get_next_move_from_list(struct matched_patterns_list_data
*list
,
int color
, struct owl_move_data
*moves
,
int cutoff
, struct local_owl_data
*owl
);
static void init_pattern_list(struct matched_patterns_list_data
*list
);
static void close_pattern_list(int color
,
struct matched_patterns_list_data
*list
);
static void owl_shapes_callback(int anchor
, int color
,
struct pattern
*pattern_db
,
static void owl_add_move(struct owl_move_data
*moves
, int move
, int value
,
enum same_dragon_value same_dragon
, int lunch
,
int escape
, int defense_pos
, int max_moves
,
struct matched_pattern_data
*pattern_data
);
static void owl_determine_life(struct local_owl_data
*owl
,
struct local_owl_data
*second_owl
,
struct owl_move_data
*moves
,
struct eyevalue
*probable_eyes
,
int *eyemin
, int *eyemax
);
static void owl_find_relevant_eyespaces(struct local_owl_data
*owl
,
int mw
[BOARDMAX
], int mz
[BOARDMAX
]);
static int owl_estimate_life(struct local_owl_data
*owl
,
struct local_owl_data
*second_owl
,
struct owl_move_data vital_moves
[MAX_MOVES
],
const char **live_reason
,
struct eyevalue
*probable_eyes
,
int *eyemin
, int *eyemax
);
static int modify_stupid_eye_vital_point(struct local_owl_data
*owl
,
static int modify_eyefilling_move(int *move
, int color
);
static int estimate_lunch_half_eye_bonus(int lunch
,
struct half_eye_data half_eye
[BOARDMAX
]);
static void owl_mark_dragon(int apos
, int bpos
,
struct local_owl_data
*owl
,
int new_dragons
[BOARDMAX
]);
static void owl_mark_worm(int apos
, int bpos
,
struct local_owl_data
*owl
);
static void owl_mark_boundary(struct local_owl_data
*owl
);
static void owl_update_goal(int pos
, enum same_dragon_value same_dragon
,
int lunch
, struct local_owl_data
*owl
,
struct matched_pattern_data
*pattern_data
);
static void owl_test_cuts(signed char goal
[BOARDMAX
], int color
,
static void componentdump(const signed char component
[BOARDMAX
]);
static void owl_update_boundary_marks(int pos
, struct local_owl_data
*owl
);
static void owl_find_lunches(struct local_owl_data
*owl
);
static int improve_lunch_attack(int lunch
, int attack_point
);
static int improve_lunch_defense(int lunch
, int defense_point
);
static void owl_make_domains(struct local_owl_data
*owla
,
struct local_owl_data
*owlb
);
static int owl_safe_move(int move
, int color
);
static void sniff_lunch(int lunch
, int *min
, int *probable
, int *max
,
struct local_owl_data
*owl
);
static void eat_lunch_escape_bonus(int lunch
, int *min
, int *probable
,
int *max
, struct local_owl_data
*owl
);
static int select_new_goal_origin(int origin
, struct local_owl_data
*owl
);
static void compute_owl_escape_values(struct local_owl_data
*owl
);
static int owl_escape_route(struct local_owl_data
*owl
);
static void do_owl_analyze_semeai(int apos
, int bpos
,
struct local_owl_data
*owla
,
struct local_owl_data
*owlb
,
int *resulta
, int *resultb
,
int *move
, int pass
, int owl_phase
);
static int semeai_trymove_and_recurse(int apos
, int bpos
,
struct local_owl_data
*owla
,
struct local_owl_data
*owlb
,
int move
, int color
, int ko_allowed
,
int move_value
, const char *move_name
,
enum same_dragon_value same_dragon
,
struct matched_pattern_data
*pattern_data
,
int lunch
, int *semeai_move
,
int *this_resulta
, int *this_resultb
);
static void semeai_add_sgf_comment(int value
, int owl_phase
);
static int semeai_trust_tactical_attack(int str
);
static int semeai_propose_eyespace_filling_move(struct local_owl_data
*owla
,
struct local_owl_data
*owlb
);
static void semeai_review_owl_moves(struct owl_move_data owl_moves
[MAX_MOVES
],
struct local_owl_data
*owla
,
struct local_owl_data
*owlb
, int color
,
int *safe_outside_liberty_found
,
int *safe_common_liberty_found
,
int *riskless_move_found
,
signed char mw
[BOARDMAX
],
struct owl_move_data semeai_moves
[MAX_SEMEAI_MOVES
],
int guess_same_dragon
, int value_bonus
,
int *critical_semeai_worms
);
static int semeai_move_value(int move
, struct local_owl_data
*owla
,
struct local_owl_data
*owlb
, int raw_value
,
int *critical_semeai_worms
);
static int semeai_is_riskless_move(int move
, struct local_owl_data
*owla
);
static void remove_eye_filling_moves(struct local_owl_data
*our_owl
,
struct owl_move_data
*moves
);
static int find_semeai_backfilling_move(int worm
, int liberty
);
static int liberty_of_goal(int pos
, struct local_owl_data
*owl
);
static int second_liberty_of_goal(int pos
, struct local_owl_data
*owl
);
static int matches_found
;
static signed char found_matches
[BOARDMAX
];
static void reduced_init_owl(struct local_owl_data
**owl
,
static void init_owl(struct local_owl_data
**owl
, int target1
, int target2
,
int move
, int use_stack
, int new_dragons
[BOARDMAX
]);
static struct local_owl_data
*owl_stack
[2 * MAXSTACK
];
static int owl_stack_size
= 0;
static int owl_stack_pointer
= 0;
static void check_owl_stack_size(void);
static void push_owl(struct local_owl_data
**owl
);
static void do_push_owl(struct local_owl_data
**owl
);
static void pop_owl(struct local_owl_data
**owl
);
static int catalog_goal(struct local_owl_data
*owl
,
int goal_worm
[MAX_GOAL_WORMS
]);
static int list_goal_worms(struct local_owl_data
*owl
,
int goal_worm
[MAX_GOAL_WORMS
]);
/* FIXME: taken from move_reasons.h */
#define MAX_DRAGONS 2 * MAX_BOARD * MAX_BOARD / 3
static int dragon_goal_worms
[MAX_DRAGONS
][MAX_GOAL_WORMS
];
prepare_goal_list(int str
, struct local_owl_data
*owl
,
int list
[MAX_GOAL_WORMS
], int *flag
, int *kworm
,
finish_goal_list(int *flag
, int *wpos
, int list
[MAX_GOAL_WORMS
], int index
);
/* Semeai worms are worms whose capture wins the semeai. */
#define MAX_SEMEAI_WORMS 20
static int semeai_worms
[MAX_SEMEAI_WORMS
];
static int important_semeai_worms
[MAX_SEMEAI_WORMS
];
/* Whether one color prefers to get a ko over a seki. */
/* Usually it's a bad idea to include the opponent worms involved in
* the semeai in the eyespace. For some purposes (determining a
* definite lack of eyespace, finding certain vital moves), however,
* we want to do that anyway. Then set this variable to 1 before
* calling owl_estimate_life() and reset it afterwards.
* FIXME: We should implement a nicer mechanism to propagate this
* information to owl_lively(), where it's used.
static int include_semeai_worms_in_eyespace
= 0;
clear_cut_list(int cuts
[MAX_CUTS
])
for (i
= 0; i
< MAX_CUTS
; i
++)
/* Called when (apos) and (bpos) point to adjacent dragons
* of the opposite color, both with matcher_status DEAD or
* CRITICAL, analyzes the semeai, assuming that the player
* of the (apos) dragon moves first. The results returned
* by *resulta and *resultb are the results of the defense
* of the apos dragon and the attack of the bpos dragon,
* respectively. Thus if these results are 1 and 0,
* respectively, the usual meaning is that a move by the
* apos player produces seki.
* owl determines whether owl moves are being generated
* or simple liberty filling is taking place.
owl_analyze_semeai(int apos
, int bpos
, int *resulta
, int *resultb
,
int *semeai_move
, int owl
, int *semeai_result_certain
)
owl_analyze_semeai_after_move(PASS_MOVE
, EMPTY
, apos
, bpos
, resulta
, resultb
,
semeai_move
, owl
, semeai_result_certain
, 0);
/* Same as the function above with the addition that an arbitrary move
* may be made before the analysis is performed.
owl_analyze_semeai_after_move(int move
, int color
, int apos
, int bpos
,
int *resulta
, int *resultb
, int *semeai_move
,
int owl
, int *semeai_result_certain
,
signed char ms
[BOARDMAX
];
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_verbose
= verbose
;
int reading_nodes_when_called
= get_reading_node_counter();
int new_dragons
[BOARDMAX
];
struct local_owl_data
*owla
;
struct local_owl_data
*owlb
;
resulta
= &dummy_resulta
;
resultb
= &dummy_resultb
;
semeai_move
= &dummy_semeai_move
;
if (debug
& DEBUG_OWL_PERFORMANCE
)
if (tryko(move
, color
, "Recompute dragons for semeai.")) {
compute_new_dragons(new_dragons
);
/* Look for owl substantial worms of either dragon adjoining
* the other dragon. Capturing such a worm wins the semeai.
* These are the semeai_worms. This code must come before
* the owl_init() calls because the owl_substantial
* FIXME: The sentence above is unfinished.
memset(ms
, 0, sizeof(ms
));
for (w1
= first_worm_in_dragon(apos
);
w1
= next_worm_in_dragon(w1
)) {
for (w2
= first_worm_in_dragon(bpos
);
w2
= next_worm_in_dragon(w2
)) {
if (adjacent_strings(w1
, w2
) || have_common_lib(w1
, w2
, NULL
)) {
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
if (ON_BOARD(str
) && ms
[str
] && worm
[str
].origin
== str
) {
int adjacent_to_outside
= 0;
/* Is the string adjacent to a living dragon outside the semeai?
* In that case it's important to attack/defend it for the life
* FIXME: Checking crude_status here isn't quite appropriate but
* owl_status is not always computed and status itself is unsafe
* since it might change before later calls to this code, e.g.
* when checking for blunders.
* Not checking for aliveness at all gives problems in e.g.
* ld_owl:302 where S19 is a separate dragon and R19 should not
* be considered critically important. What we really would like
* to determine is whether it's outside the semeai, however.
adj
= chainlinks(str
, adjs
);
for (k
= 0; k
< adj
; k
++) {
if (!is_same_dragon(adjs
[k
], apos
)
&& !is_same_dragon(adjs
[k
], bpos
)
&& dragon
[adjs
[k
]].crude_status
== ALIVE
)
if ((adjacent_to_outside
|| countstones(str
) > 6)
&& s_worms
< MAX_SEMEAI_WORMS
) {
important_semeai_worms
[s_worms
] = 1;
semeai_worms
[s_worms
++] = str
;
DEBUG(DEBUG_SEMEAI
, "important semeai worm: %1m\n", str
);
else if (owl_substantial(str
) && s_worms
< MAX_SEMEAI_WORMS
) {
important_semeai_worms
[s_worms
] = 0;
semeai_worms
[s_worms
++] = str
;
DEBUG(DEBUG_SEMEAI
, "semeai worm: %1m\n", str
);
sgf_dumptree
= save_sgf_dumptree
;
ASSERT1(board
[apos
] == OTHER_COLOR(board
[bpos
]), apos
);
DEBUG(DEBUG_SEMEAI
, "owl_analyze_semeai: %1m vs. %1m\n", apos
, bpos
);
DEBUG(DEBUG_SEMEAI
, "owl_analyze_semeai_after_move %C %1m: %1m vs. %1m\n",
color
, move
, apos
, bpos
);
init_owl(&owla
, apos
, NO_MOVE
, NO_MOVE
, 1, new_dragons
);
init_owl(&owlb
, bpos
, NO_MOVE
, NO_MOVE
, 0, new_dragons
);
init_owl(&owla
, apos
, NO_MOVE
, NO_MOVE
, 1, NULL
);
init_owl(&owlb
, bpos
, NO_MOVE
, NO_MOVE
, 0, NULL
);
owl_make_domains(owla
, owlb
);
reduced_init_owl(&owla
, 1);
reduced_init_owl(&owlb
, 0);
local_owl_node_counter
= 0;
owl_mark_worm(apos
, NO_MOVE
, owla
);
owl_mark_worm(bpos
, NO_MOVE
, owlb
);
Hash_data temp
= goal_to_hashvalue(owla
->goal
);
goal_hash
= goal_to_hashvalue(owlb
->goal
);
hashdata_xor(goal_hash
, temp
);
&& search_persistent_semeai_cache(ANALYZE_SEMEAI
,
apos
, bpos
, move
, color
, &goal_hash
,
resulta
, resultb
, semeai_move
,
semeai_result_certain
)) {
DEBUG(DEBUG_OWL_PERFORMANCE
,
"analyze_semeai %1m vs. %1m, result %d %d %1m (cached)\n",
apos
, bpos
, *resulta
, *resultb
, *semeai_move
);
DEBUG(DEBUG_OWL_PERFORMANCE
,
"analyze_semeai_after_move %C %1m: %1m vs. %1m, result %d %d %1m (cached)\n",
color
, move
, apos
, bpos
, *resulta
, *resultb
, *semeai_move
);
/* In some semeai situations one or both players have the option to
* choose between seki and ko for the life and death of both. In
* general this choice depends on the ko threat situation, the
* overall score, and the strategical effects on surrounding
* dragons, but we don't try to correctly estimate this. Instead we
* make the reasonable assumption that if one dragon is
* substantially smaller than the other dragon, ko is to be
* preferred for the smaller dragon and seki for the larger dragon.
* prefer_ko can be either WHITE, BLACK, or EMPTY and tells which
* color, if any, prefers to get ko.
if (dragon
[apos
].size
<= 5 && dragon
[bpos
].size
> 3 * dragon
[apos
].size
)
else if (dragon
[bpos
].size
<= 5 && dragon
[apos
].size
> 3 * dragon
[bpos
].size
)
do_owl_analyze_semeai(apos
, bpos
, owla
, owlb
,
resulta
, resultb
, semeai_move
, 0, owl
);
semeai_trymove_and_recurse(bpos
, apos
, owlb
, owla
, owl
,
move
, color
, 1, 0, "mandatory move",
SAME_DRAGON_MAYBE_CONNECTED
, NULL
, NO_MOVE
,
semeai_move
, resultb
, resulta
);
*resulta
= REVERSE_RESULT(*resulta
);
*resultb
= REVERSE_RESULT(*resultb
);
nodes_used
= get_reading_node_counter() - reading_nodes_when_called
;
DEBUG(DEBUG_OWL_PERFORMANCE
,
"analyze_semeai %1m vs. %1m, result %d %d %1m (%d, %d nodes, %f seconds)\n",
apos
, bpos
, *resulta
, *resultb
, *semeai_move
, local_owl_node_counter
,
nodes_used
, gg_cputime() - start
);
DEBUG(DEBUG_OWL_PERFORMANCE
,
"analyze_semeai_after_move %C %1m: %1m vs. %1m, result %d %d %1m (%d, %d nodes, %f seconds)\n",
color
, move
, apos
, bpos
, *resulta
, *resultb
, *semeai_move
,
nodes_used
, gg_cputime() - start
);
if (semeai_result_certain
)
*semeai_result_certain
= result_certain
;
store_persistent_semeai_cache(ANALYZE_SEMEAI
, apos
, bpos
, move
, color
,
*resulta
, *resultb
, *semeai_move
,
result_certain
, nodes_used
,
/* It is assumed that the 'a' player moves first, and
* determines the best result for both players. The
* parameter "pass" is 1 if the opponent's last move is
* pass. In this case, if no move is found but the genus
* is less than 2, then the position is declared seki.
* If a move is needed to get this result, then (*move) is
* the location, otherwise this field returns PASS.
do_owl_analyze_semeai(int apos
, int bpos
,
struct local_owl_data
*owla
,
struct local_owl_data
*owlb
,
int *resulta
, int *resultb
,
int *move
, int pass
, int owl_phase
)
int other
= OTHER_COLOR(color
);
int goal_wormsa
[MAX_GOAL_WORMS
], goal_wormsb
[MAX_GOAL_WORMS
];
struct owl_move_data vital_defensive_moves
[MAX_MOVES
];
struct owl_move_data vital_offensive_moves
[MAX_MOVES
];
struct owl_move_data shape_defensive_moves
[MAX_MOVES
];
struct owl_move_data shape_offensive_moves
[MAX_MOVES
];
struct matched_patterns_list_data shape_offensive_patterns
;
struct matched_patterns_list_data shape_defensive_patterns
;
struct owl_move_data moves
[MAX_SEMEAI_MOVES
];
struct owl_move_data outside_liberty
;
struct owl_move_data common_liberty
;
struct owl_move_data backfill_outside_liberty
;
struct owl_move_data backfill_common_liberty
;
int safe_outside_liberty_found
= 0;
int safe_common_liberty_found
= 0;
int riskless_move_found
= 0;
signed char mw
[BOARDMAX
];
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
const char *best_move_name
= NULL
;
int this_variation_number
= count_variations
- 1;
int critical_semeai_worms
[MAX_SEMEAI_WORMS
];
int we_might_be_inessential
;
struct eyevalue probable_eyes_a
;
struct eyevalue probable_eyes_b
;
struct eyevalue dummy_eyes
;
SETUP_TRACE_INFO2("do_owl_analyze_semeai", apos
, bpos
);
ASSERT1(board
[apos
] == owla
->color
, apos
);
ASSERT1(board
[bpos
] == owlb
->color
, bpos
);
apos
= find_origin(apos
);
bpos
= find_origin(bpos
);
if (stackp
<= semeai_branch_depth
&& tt_get(&ttable
, SEMEAI
, apos
, bpos
, depth
- stackp
, NULL
,
&value1
, &value2
, &xpos
) == 2) {
TRACE_CACHED_RESULT2(value1
, value2
, xpos
);
TRACE("%oVariation %d: %1m %1m %s %s %1m (cached) ",
this_variation_number
, apos
, bpos
,
result_to_string(*resulta
),
result_to_string(*resultb
),
SGFTRACE_SEMEAI(xpos
, *resulta
, *resultb
, "cached");
global_owl_node_counter
++;
local_owl_node_counter
++;
shape_offensive_patterns
.initialized
= 0;
shape_defensive_patterns
.initialized
= 0;
wormsa
= catalog_goal(owla
, goal_wormsa
);
wormsb
= catalog_goal(owlb
, goal_wormsb
);
outside_liberty
.pos
= NO_MOVE
;
common_liberty
.pos
= NO_MOVE
;
backfill_outside_liberty
.pos
= NO_MOVE
;
backfill_common_liberty
.pos
= NO_MOVE
;
for (k
= 0; k
< MAX_SEMEAI_MOVES
; k
++) {
moves
[k
].same_dragon
= SAME_DRAGON_CONNECTED
;
moves
[k
].lunch
= NO_MOVE
;
clear_cut_list(moves
[k
].cuts
);
ASSERT1(other
== board
[bpos
], bpos
);
memset(mw
, 0, sizeof(mw
));
/* Turn off the sgf file and variation counting. */
/* Look for a tactical attack. We seek a semeai worm of owlb which
* can be attacked. If such exists and is considered critical, we
* declare victory. If it's not considered critical we add the
* attacking move as a high priority move to try.
for (sworm
= 0; sworm
< s_worms
; sworm
++) {
critical_semeai_worms
[sworm
] = 0;
if (board
[semeai_worms
[sworm
]] == other
) {
int acode
= attack(semeai_worms
[sworm
], &upos
);
&& semeai_trust_tactical_attack(semeai_worms
[sworm
])
&& important_semeai_worms
[sworm
]) {
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
SGFTRACE_SEMEAI(upos
, WIN
, WIN
, "tactical win found");
READ_RETURN_SEMEAI(SEMEAI
, apos
, bpos
, depth
- stackp
,
&& find_defense(semeai_worms
[sworm
], NULL
)) {
critical_semeai_worms
[sworm
] = 1;
owl_add_move(moves
, upos
, 105, "attack semeai worm",
SAME_DRAGON_MAYBE_CONNECTED
,
NO_MOVE
, 0, NO_MOVE
, MAX_SEMEAI_MOVES
, NULL
);
TRACE("Added %1m %d (-1)\n", upos
, 105);
&& important_semeai_worms
[sworm
]) {
owl_add_move(moves
, upos
, 100, "attack semeai worm",
SAME_DRAGON_MAYBE_CONNECTED
,
NO_MOVE
, 0, NO_MOVE
, MAX_SEMEAI_MOVES
, NULL
);
TRACE("Added %1m %d (-1)\n", upos
, 100);
/* Look for a tactical rescue. If a semeai worm of owla is tactically
* threatened, try to save it.
we_might_be_inessential
= 1;
for (sworm
= 0; sworm
< s_worms
; sworm
++)
if (board
[semeai_worms
[sworm
]] == color
) {
if (important_semeai_worms
[sworm
])
we_might_be_inessential
= 0;
if (attack(semeai_worms
[sworm
], NULL
)
&& find_defense(semeai_worms
[sworm
], &upos
)) {
critical_semeai_worms
[sworm
] = 1;
owl_add_move(moves
, upos
, 85, "defend semeai worm",
SAME_DRAGON_MAYBE_CONNECTED
, NO_MOVE
,
0, NO_MOVE
, MAX_SEMEAI_MOVES
, NULL
);
TRACE("Added %1m %d (0)\n", upos
, 85);
/* We generate the candidate moves. During the early stages of
* the semeai, there may be moves to expand or shrink the
* eyespaces of the two dragons. During the later stages, the
* picture is simplified and reading the semeai is a matter
* of filling liberties until one of the dragons may be removed,
* or a seki results. The first stage we call the owl phase.
set_eyevalue(&probable_eyes_a
, 0, 0, 0, 0);
set_eyevalue(&probable_eyes_b
, 0, 0, 0, 0);
/* First the vital moves. These include moves to attack or
* defend the eyespace (e.g. nakade, or hane to reduce the
* number of eyes) or moves to capture a lunch.
const char *live_reasona
;
const char *live_reasonb
;
/* We do not wish for any string of the 'b' dragon to be
* counted as a lunch of the 'a' dragon since owl_determine_life
* can give a wrong result in the case of a semeai. So we eliminate
for (k
= 0; k
< MAX_LUNCHES
; k
++) {
if (owla
->lunch
[k
] != NO_MOVE
&& owlb
->goal
[owla
->lunch
[k
]]) {
owla
->lunch
[k
] = NO_MOVE
;
for (k
= 0; k
< MAX_LUNCHES
; k
++) {
if (owlb
->lunch
[k
] != NO_MOVE
&& owla
->goal
[owlb
->lunch
[k
]]) {
owlb
->lunch
[k
] = NO_MOVE
;
if (owl_estimate_life(owla
, owlb
, vital_defensive_moves
,
&live_reasona
, 0, &probable_eyes_a
,
else if (stackp
> 2 && owl_escape_route(owla
) >= 5) {
live_reasona
= "escaped";
if (owl_estimate_life(owlb
, owla
, vital_offensive_moves
,
&live_reasonb
, 1, &probable_eyes_b
,
else if (stackp
> 2 && owl_escape_route(owlb
) >= 5) {
live_reasonb
= "escaped";
gprintf("probable_eyes_a: %s eyemin: %d eyemax: %d",
eyevalue_to_string(&probable_eyes_a
), eyemin_a
, eyemax_a
);
gprintf("%o I look alive (%s)", live_reasona
);
gprintf("probable_eyes_b: %s eyemin: %d eyemax: %d",
eyevalue_to_string(&probable_eyes_b
), eyemin_b
, eyemax_b
);
gprintf("%o you look alive(%s)", live_reasonb
);
/* Stop here if both look certain to live. */
if (I_look_alive
&& you_look_alive
) {
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
SGFTRACE_SEMEAI(PASS_MOVE
, WIN
, 0, "Both live");
READ_RETURN_SEMEAI(SEMEAI
, apos
, bpos
, depth
- stackp
,
move
, PASS_MOVE
, WIN
, 0);
/* Next the shape moves. */
owl_shapes(&shape_defensive_patterns
, shape_defensive_moves
, color
,
owla
, &owl_defendpat_db
);
for (k
= 0; k
< MAX_MOVES
-1; k
++)
if (!get_next_move_from_list(&shape_defensive_patterns
, color
,
shape_defensive_moves
, 1, owla
))
shape_defensive_moves
[0].pos
= NO_MOVE
;
owl_shapes(&shape_offensive_patterns
, shape_offensive_moves
, color
,
owlb
, &owl_attackpat_db
);
for (k
= 0; k
< MAX_MOVES
-1; k
++)
if (!get_next_move_from_list(&shape_offensive_patterns
, color
,
shape_offensive_moves
, 1, owlb
))
shape_offensive_moves
[0].pos
= NO_MOVE
;
/* Filter out moves, which fill our eye (and not split it). */
remove_eye_filling_moves(owla
, vital_defensive_moves
);
remove_eye_filling_moves(owla
, vital_offensive_moves
);
remove_eye_filling_moves(owla
, shape_defensive_moves
);
remove_eye_filling_moves(owla
, shape_offensive_moves
);
/* Now we review the moves already considered, while collecting
* them into a single list.
semeai_review_owl_moves(vital_defensive_moves
, owla
, owlb
, color
,
&safe_outside_liberty_found
,
&safe_common_liberty_found
,
semeai_review_owl_moves(shape_defensive_moves
, owla
, owlb
, color
,
&safe_outside_liberty_found
,
&safe_common_liberty_found
,
semeai_review_owl_moves(vital_offensive_moves
, owla
, owlb
, color
,
&safe_outside_liberty_found
,
&safe_common_liberty_found
,
semeai_review_owl_moves(shape_offensive_moves
, owla
, owlb
, color
,
&safe_outside_liberty_found
,
&safe_common_liberty_found
,
/* If no moves were found so far, also check the eyespaces when
* opponent semeai worms are allowed to be included for vital
if (moves
[0].pos
== NO_MOVE
|| we_might_be_inessential
) {
include_semeai_worms_in_eyespace
= 1;
if (!owl_estimate_life(owlb
, owla
, vital_offensive_moves
,
&live_reasonb
, 1, &dummy_eyes
,
semeai_review_owl_moves(vital_offensive_moves
, owla
, owlb
, color
,
&safe_outside_liberty_found
,
&safe_common_liberty_found
,
include_semeai_worms_in_eyespace
= 0;
if (eyemin_a
== eyemax_a
)
/* We have stable number of eyes, so we can try to reduce
I_have_more_eyes
= (eyemin_a
> min_eyes(&probable_eyes_b
));
if (min_eyes(&probable_eyes_a
) == max_eyes(&probable_eyes_a
))
/* If we can't increase our number of eyes, we try to reduce
I_have_more_eyes
= (max_eyes(&probable_eyes_a
) > min_eyes(&probable_eyes_b
));
/* If we can increase our number of eyes, we do it and let
* opponent to increase his.
I_have_more_eyes
= (max_eyes(&probable_eyes_a
) > max_eyes(&probable_eyes_b
));
/* If no owl moves were found on two consecutive moves,
* turn off the owl phase.
if (moves
[0].pos
== NO_MOVE
) {
/* Now we look for a move to fill a liberty. This is only
* interesting if the opponent doesn't already have two eyes.
* If we have more eyes, always check for a backfilling move.
&& !safe_outside_liberty_found
&& (moves
[0].value
< 110 || I_have_more_eyes
)) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] == EMPTY
&& !mw
[pos
]) {
if (liberty_of_goal(pos
, owlb
)) {
if (!liberty_of_goal(pos
, owla
)) {
if (safe_move(pos
, color
) == WIN
) {
safe_outside_liberty_found
= 1;
outside_liberty
.pos
= pos
;
else if (backfill_outside_liberty
.pos
== NO_MOVE
)
backfill_outside_liberty
.pos
= find_semeai_backfilling_move(bpos
,
if (safe_move(pos
, color
) == WIN
) {
safe_common_liberty_found
= 1;
common_liberty
.pos
= pos
;
else if (backfill_common_liberty
.pos
== NO_MOVE
)
backfill_common_liberty
.pos
= find_semeai_backfilling_move(bpos
,
/* Add the best liberty filling move available. We first want to
* play outer liberties, second backfilling moves required before
* filling an outer liberty. If no such moves are available we try
* to fill a mutual liberty or play a corresponding backfilling
if (safe_outside_liberty_found
&& outside_liberty
.pos
!= NO_MOVE
) {
move_value
= semeai_move_value(outside_liberty
.pos
,
owl_add_move(moves
, outside_liberty
.pos
, move_value
,
"safe outside liberty", SAME_DRAGON_NOT_CONNECTED
,
NO_MOVE
, 0, NO_MOVE
, MAX_SEMEAI_MOVES
, NULL
);
TRACE("Added %1m %d (5)\n", outside_liberty
.pos
, move_value
);
else if (backfill_outside_liberty
.pos
!= NO_MOVE
) {
move_value
= semeai_move_value(backfill_outside_liberty
.pos
,
owl_add_move(moves
, backfill_outside_liberty
.pos
, move_value
,
"backfilling move", SAME_DRAGON_NOT_CONNECTED
, NO_MOVE
, 0,
NO_MOVE
, MAX_SEMEAI_MOVES
, NULL
);
TRACE("Added %1m %d (6)\n", backfill_outside_liberty
.pos
, move_value
);
else if (safe_common_liberty_found
&& common_liberty
.pos
!= NO_MOVE
) {
move_value
= semeai_move_value(common_liberty
.pos
,
owl_add_move(moves
, common_liberty
.pos
, move_value
,
"safe common liberty", SAME_DRAGON_MAYBE_CONNECTED
,
NO_MOVE
, 0, NO_MOVE
, MAX_SEMEAI_MOVES
, NULL
);
if (semeai_is_riskless_move(common_liberty
.pos
, owla
))
TRACE("Added %1m %d (7)\n", common_liberty
.pos
, move_value
);
else if (backfill_common_liberty
.pos
!= NO_MOVE
) {
move_value
= semeai_move_value(backfill_common_liberty
.pos
,
owl_add_move(moves
, backfill_common_liberty
.pos
, move_value
,
"backfilling move", SAME_DRAGON_NOT_CONNECTED
, NO_MOVE
, 0,
NO_MOVE
, MAX_SEMEAI_MOVES
, NULL
);
if (semeai_is_riskless_move(backfill_common_liberty
.pos
, owla
))
TRACE("Added %1m %d (6)\n", backfill_common_liberty
.pos
, move_value
);
if (moves
[0].pos
== NO_MOVE
) {
/* If no move has been found yet, see if we can fill opponent's
* eye (i.e. put more stones in "bulky five" shape).
if (min_eyes(&probable_eyes_b
) == 1) {
int move
= semeai_propose_eyespace_filling_move(owla
, owlb
);
owl_add_move(moves
, move
, 70, "eyespace filling",
SAME_DRAGON_NOT_CONNECTED
, NO_MOVE
,
0, NO_MOVE
, MAX_SEMEAI_MOVES
, NULL
);
if (moves
[0].pos
== NO_MOVE
)
TRACE("No move found\n");
/* Now we are ready to try moves. Turn on the sgf output ... */
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
for (k
= 0; k
< MAX_SEMEAI_MOVES
; k
++) {
/* Do not try too many moves. */
|| (stackp
> semeai_branch_depth2
&& tested_moves
> 1)
|| (stackp
> semeai_branch_depth
&& tested_moves
> 0)) {
/* If allpats, try and pop to get the move in the sgf record. */
else if (trymove(mpos
, color
, moves
[k
].name
, apos
)) {
semeai_add_sgf_comment(moves
[k
].value
, owl_phase
);
if (count_variations
>= semeai_node_limit
|| stackp
>= MAX_SEMEAI_DEPTH
)
/* Try playing the move at mpos and call ourselves recursively to
* determine the result obtained by this move.
if (semeai_trymove_and_recurse(apos
, bpos
, owla
, owlb
,
best_resulta
== 0 || best_resultb
== 0,
moves
[k
].value
, moves
[k
].name
,
moves
[k
].same_dragon
, moves
[k
].pattern_data
,
&this_resulta
, &this_resultb
)) {
if (this_resultb
== WIN
&& this_resulta
== WIN
) {
/* Ideal result, no need to try any more moves. */
TRACE("After %1m I (%C) am alive, you are dead\n", mpos
, color
);
SGFTRACE_SEMEAI(mpos
, WIN
, WIN
, moves
[k
].name
);
close_pattern_list(color
, &shape_defensive_patterns
);
close_pattern_list(color
, &shape_offensive_patterns
);
READ_RETURN_SEMEAI(SEMEAI
, apos
, bpos
, depth
- stackp
,
/* When there is a choice between ko and seki, the prefer_ko
* variable decides policy. Thus if prefer_ko == color we
* consider attacking the opponent more important than defending
* our dragon, and vise versa otherwise.
else if ((prefer_ko
!= color
&& (this_resulta
> best_resulta
|| (this_resulta
== best_resulta
&& this_resultb
> best_resultb
)))
&& (this_resultb
> best_resultb
|| (this_resultb
== best_resultb
&& this_resulta
> best_resulta
)))) {
best_resulta
= this_resulta
;
best_resultb
= this_resultb
;
best_move_name
= moves
[k
].name
;
close_pattern_list(color
, &shape_defensive_patterns
);
close_pattern_list(color
, &shape_offensive_patterns
);
/* If we can't find a move and the opponent looks alive, we have
if (best_resulta
== 0 && best_resultb
== 0 && you_look_alive
) {
SGFTRACE_SEMEAI(PASS_MOVE
, 0, 0, "You live, I die");
READ_RETURN_SEMEAI(SEMEAI
, apos
, bpos
, depth
- stackp
,
/* If we didn't find a working move and we look dead even if including the
* opponent stones in our eyespace, we have lost.
if (best_resulta
== 0 && best_resultb
== 0
&& !riskless_move_found
) {
const char *live_reasona
;
for (sworm
= 0; sworm
< s_worms
; sworm
++) {
if (board
[semeai_worms
[sworm
]] == other
) {
if (important_semeai_worms
[sworm
])
include_semeai_worms_in_eyespace
= 1;
if (!owl_estimate_life(owla
, owlb
, vital_defensive_moves
,
&live_reasona
, 0, &dummy_eyes
,
include_semeai_worms_in_eyespace
= 0;
SGFTRACE_SEMEAI(PASS_MOVE
, 0, 0, "You live, I die - 2");
READ_RETURN_SEMEAI(SEMEAI
, apos
, bpos
, depth
- stackp
,
include_semeai_worms_in_eyespace
= 0;
/* If we can't find a useful move and opponent passed, it's seki, unless
* one dragon has more eyes than the other.
if (best_resulta
== 0 && best_resultb
== 0
&& !riskless_move_found
) {
if (max_eyes(&probable_eyes_a
) < min_eyes(&probable_eyes_b
)) {
TRACE("You have more eyes.\n");
SGFTRACE_SEMEAI(PASS_MOVE
, 0, 0, "You have more eyes");
READ_RETURN_SEMEAI(SEMEAI
, apos
, bpos
, depth
- stackp
,
else if (max_eyes(&probable_eyes_b
) < min_eyes(&probable_eyes_a
)) {
TRACE("I have more eyes\n");
SGFTRACE_SEMEAI(PASS_MOVE
, WIN
, WIN
, "I have more eyes");
READ_RETURN_SEMEAI(SEMEAI
, apos
, bpos
, depth
- stackp
,
move
, PASS_MOVE
, WIN
, WIN
);
SGFTRACE_SEMEAI(PASS_MOVE
, WIN
, 0, "Seki");
READ_RETURN_SEMEAI(SEMEAI
, apos
, bpos
, depth
- stackp
,
move
, PASS_MOVE
, WIN
, 0);
/* No working move was found, but opponent hasn't passed. Then we pass. */
do_owl_analyze_semeai(bpos
, apos
, owlb
, owla
,
resultb
, resulta
, NULL
, 1, owl_phase
);
*resulta
= REVERSE_RESULT(*resulta
);
*resultb
= REVERSE_RESULT(*resultb
);
TRACE("No move found\n");
SGFTRACE_SEMEAI(PASS_MOVE
, *resulta
, *resultb
, "No move found");
READ_RETURN_SEMEAI(SEMEAI
, apos
, bpos
, depth
- stackp
,
move
, PASS_MOVE
, *resulta
, *resultb
);
/* There are a few selected cases where we should try to see if it
* would be better to pass rather than playing any move in the semeai.
* A first simple example is the case of positions where there is nothing
* left to play but common liberties. In case the above analysis concluded
* the result is seki and if the best (and only) move happens to be a
* common liberty, we attempt to pass, so that the engine considers tenuki
* as a viable option in case it actually is.
* Another example is related to "disturbing" kos.
* .OOOOOOOO. In this position (similar to semeai:130), X has just taken
* OOXXXXXXOO the ko on the left. The semeai code finds the ko recapture
* OX.XXOOXXO as the only attacking move and concludes the result is KO_B.
* In such cases too, we try to pass to see if it doesn't actually yield
* FIXME: there might be more cases where passing would be valuable.
if ((best_resulta
== WIN
&& best_resultb
== 0
&& best_move
== common_liberty
.pos
)
|| (best_resulta
== KO_B
&& best_resultb
== KO_B
&& is_ko(best_move
, owla
->color
, NULL
))) {
do_owl_analyze_semeai(bpos
, apos
, owlb
, owla
, &this_resultb
,
&this_resulta
, NULL
, 1, owl_phase
);
if (REVERSE_RESULT(this_resulta
) >= best_resulta
&& REVERSE_RESULT(this_resultb
) >= best_resultb
) {
best_resulta
= REVERSE_RESULT(this_resulta
);
best_resultb
= REVERSE_RESULT(this_resultb
);
SGFTRACE_SEMEAI(best_move
, best_resulta
, best_resultb
, best_move_name
);
READ_RETURN_SEMEAI(SEMEAI
, apos
, bpos
, depth
- stackp
,
move
, best_move
, best_resulta
, best_resultb
);
/* Play a move, update goal and boundaries appropriately, and call
* do_owl_analyze_semeai() recursively to determine the result of this
semeai_trymove_and_recurse(int apos
, int bpos
, struct local_owl_data
*owla
,
struct local_owl_data
*owlb
,
int move
, int color
, int ko_allowed
,
int move_value
, const char *move_name
,
enum same_dragon_value same_dragon
,
struct matched_pattern_data
*pattern_data
,
int lunch
, int *semeai_move
,
int *this_resulta
, int *this_resultb
)
gg_assert(this_resulta
!= NULL
&& this_resultb
!= NULL
);
if (!komaster_trymove(move
, color
, move_name
, apos
, &ko_move
, ko_allowed
)) {
if (is_ko(move
, color
, &kpos
)) {
/* Move was not allowed because of komaster. We want to check
* if this situation is double ko and when it is, we won semeai.
int other
= OTHER_COLOR(color
);
for (sworm
= 0; sworm
< s_worms
; sworm
++) {
worm_color
= board
[semeai_worms
[sworm
]];
if (worm_color
== color
) {
/* We only check up to MAX_LIBERTIES, due to performance
* reasons. When we have more liberties we have some outside
* liberties to fill and these moves will be tried later
* (and double ko situation will be found).
nlib
= findlib(semeai_worms
[sworm
], MAX_LIBERTIES
, libs
);
if (nlib
> MAX_LIBERTIES
)
for (n
= 0; n
< nlib
; n
++)
if (is_ko(libs
[n
], other
, NULL
)) {
/* Check if situation is not a nested ko capture. */
if (DIAGONAL_NEIGHBORS(libs
[n
], kpos
))
/* Our dragon has double ko, but we have to check if
* opponent dragon doesn't have outside liberties or
else if (worm_color
== other
) {
if (countlib(semeai_worms
[sworm
]) > 2)
/* In double ko situation the opponent can have only a
* single eye and a ko outside liberty to be sure that we
* will always win double ko.
if (*this_resulta
== WIN
)
semeai_add_sgf_comment(move_value
, owl_phase
);
TRACE("Trying %C %1m. Current stack: ", color
, move
);
TRACE("%s, value %d, same_dragon %d\n", move_name
, move_value
, same_dragon
);
if (owla
->color
== color
) {
owl_update_goal(move
, same_dragon
, lunch
, owla
, 1, pattern_data
);
owl_update_boundary_marks(move
, owlb
);
owl_update_goal(move
, same_dragon
, lunch
, owlb
, 1, pattern_data
);
owl_update_boundary_marks(move
, owla
);
mark_goal_in_sgf(owla
->goal
);
mark_goal_in_sgf(owlb
->goal
);
/* Do a recursive call to read the semeai after the move we just
* tried. If dragon b was captured by the move, call
* do_owl_attack() to see whether it sufficed for us to live.
if (board
[bpos
] == EMPTY
) {
/* FIXME: Are all owl_data fields and relevant static
* variables properly set up for a call to do_owl_attack()?
*this_resulta
= REVERSE_RESULT(do_owl_attack(apos
, semeai_move
, NULL
, owla
, 0));
*this_resultb
= *this_resulta
;
do_owl_analyze_semeai(bpos
, apos
, owlb
, owla
,
this_resultb
, this_resulta
, semeai_move
,
*this_resulta
= REVERSE_RESULT(*this_resulta
);
*this_resultb
= REVERSE_RESULT(*this_resultb
);
/* Does success require ko? */
if (count_variations
>= semeai_node_limit
) {
TRACE("Out of nodes, claiming win.\n");
/* Add details in sgf file about move value and whether owl_phase is active. */
semeai_add_sgf_comment(int value
, int owl_phase
)
gg_snprintf(buf
, 100, "value %d, owl_phase", value
);
gg_snprintf(buf
, 100, "value %d", value
);
sgftreeAddComment(sgf_dumptree
, buf
);
/* In semeai situations tactical attacks often cannot be trusted. This
* in particular holds for strings with three or more liberties. Two
* liberties can usually be trusted, but if neither liberty can be
* played immediately, the need for backfilling moves gives an
* effective liberty count of more than two, again making the attack
* This function decides whether an attack should be trusted. It does
* not check whether there actually is an attack, though.
semeai_trust_tactical_attack(int str
)
int other
= OTHER_COLOR(board
[str
]);
liberties
= findlib(str
, 3, libs
);
if (!is_self_atari(libs
[0], other
)
|| !is_self_atari(libs
[1], other
))
/* A move is deemed riskless (i.e., doesn't kill ourself in a seki situation)
* if it doesn't decrease the liberty count of any goal string of our
semeai_is_riskless_move(int move
, struct local_owl_data
*owla
)
int liberties
= accuratelib(move
, owla
->color
, MAXLIBS
, NULL
);
if (!liberty_of_goal(move
, owla
))
for (k
= 0; k
< 4; k
++) {
int pos
= move
+ delta
[k
];
if (board
[pos
] == owla
->color
&& countlib(pos
) > liberties
)
/* Review the moves in owl_moves[] and add them into semeai_moves[].
* This is used to merge multiple sets of owl moves into one move
* list, while revising the values for use in semeai reading.
* We also record whether the moves include an outer or common liberty
semeai_review_owl_moves(struct owl_move_data owl_moves
[MAX_MOVES
],
struct local_owl_data
*owla
,
struct local_owl_data
*owlb
, int color
,
int *safe_outside_liberty_found
,
int *safe_common_liberty_found
,
int *riskless_move_found
,
signed char mw
[BOARDMAX
],
struct owl_move_data semeai_moves
[MAX_SEMEAI_MOVES
],
int guess_same_dragon
, int value_bonus
,
int *critical_semeai_worms
)
enum same_dragon_value same_dragon
;
struct matched_pattern_data
*pattern_data
= NULL
;
for (k
= 0; k
< MAX_MOVES
-1; k
++) {
if (owl_moves
[k
].value
== 0)
/* Does the move fill a liberty in the semeai? */
if (liberty_of_goal(move
, owlb
)
&& safe_move(move
, color
)) {
if (!liberty_of_goal(move
, owla
))
*safe_outside_liberty_found
= 1;
*safe_common_liberty_found
= 1;
if (is_legal(move
, color
) && !is_ko(move
, color
, NULL
)
&& semeai_is_riskless_move(move
, owla
))
*riskless_move_found
= 1;
/* For some types of owl moves we don't have same_dragon
* information recorded and need to guess.
if (liberty_of_goal(move
, owla
)
|| second_liberty_of_goal(move
, owla
))
same_dragon
= SAME_DRAGON_MAYBE_CONNECTED
;
same_dragon
= SAME_DRAGON_NOT_CONNECTED
;
same_dragon
= owl_moves
[k
].same_dragon
;
pattern_data
= owl_moves
[k
].pattern_data
;
move_value
= (semeai_move_value(move
, owla
, owlb
, owl_moves
[k
].value
,
owl_add_move(semeai_moves
, move
, move_value
, owl_moves
[k
].name
,
same_dragon
, NO_MOVE
, owl_moves
[k
].escape
,
NO_MOVE
, MAX_SEMEAI_MOVES
, pattern_data
);
TRACE("Added %1m %d\n", move
, move_value
);
/* Propose an eyespace filling move. Such a move can, for instance,
* add a stone to opponent's "bulky five" shape. We of course choose
* a move that doesn't allow opponent to turn his dead eyeshape into a
* two eyes eyeshape. E.g. in this position, the function will
* propose the move at '*', not at the '.':
semeai_propose_eyespace_filling_move(struct local_owl_data
*owla
,
struct local_owl_data
*owlb
)
int color
= OTHER_COLOR(owlb
->color
);
owl_find_relevant_eyespaces(owlb
, mw
, mz
);
/* Never try to fill opponent's eyes which contain our dragon. This
* is nothing else than suicide.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (ON_BOARD(pos
) && owla
->goal
[pos
])
mw
[owlb
->my_eye
[pos
].origin
] = 0;
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] == EMPTY
) {
int origin
= owlb
->my_eye
[pos
].origin
;
&& min_eyes(&owlb
->my_eye
[origin
].value
) == 1) {
if (trymove(pos
, color
, "eyespace_filling", NO_MOVE
)) {
struct eyevalue new_value
;
compute_eyes(origin
, &new_value
, &dummy_attack
, &dummy_defense
,
owlb
->my_eye
, owlb
->half_eye
, 0);
if (max_eyes(&new_value
) <= 1)
/* Try to estimate the value of a semeai move. This has two
* components. The first is the change in the total number of
* liberties for strings involved in the semeai. The second is a bonus
* for attacks and defenses of critical semeai worms.
semeai_move_value(int move
, struct local_owl_data
*owla
,
struct local_owl_data
*owlb
,
int raw_value
, int *critical_semeai_worms
)
int save_verbose
= verbose
;
ASSERT1(board
[move
] == EMPTY
, move
);
if (safe_move(move
, color
)) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
&& pos
== find_origin(pos
)) {
count_lib
= countlib(pos
);
count_lib
= countlib(pos
);
if (!trymove(move
, color
, NULL
, 0)) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
&& pos
== find_origin(pos
)) {
|| (pos
== move
&& liberty_of_goal(move
, owla
))) {
count_lib
= countlib(pos
);
count_lib
= countlib(pos
);
for (k
= 0; k
< s_worms
; k
++) {
if (!critical_semeai_worms
[k
])
if (board
[semeai_worms
[k
]] == color
&& !attack(semeai_worms
[k
], NULL
))
else if (board
[semeai_worms
[k
]] == OTHER_COLOR(color
)
&& !find_defense(semeai_worms
[k
], NULL
))
return raw_value
+ net
+ bonus
;
/* Remove all moves from the list that would fill our own eye. */
remove_eye_filling_moves(struct local_owl_data
*our_owl
,
struct owl_move_data
*moves
)
int color
= our_owl
->color
;
for (k
= 0; k
< MAX_MOVES
; k
++) {
if (moves
[k
].pos
== NO_MOVE
)
struct eye_data
*eye
= &our_owl
->my_eye
[moves
[k
].pos
];
/* If esize==1 this eye must not be a real eye (at least one
* worm is capturable, otherwise this move would not be
if (eye
->color
== color
&& eye
->msize
== 0 && eye
->neighbors
<= 1
&& our_owl
->half_eye
[moves
[k
].pos
].type
!= HALF_EYE
&& !has_neighbor(moves
[k
].pos
, OTHER_COLOR(color
)))
/* Is the vertex at pos adjacent to an element of the owl goal? */
liberty_of_goal(int pos
, struct local_owl_data
*owl
)
if (IS_STONE(board
[pos
+ delta
[k
]]) && owl
->goal
[pos
+ delta
[k
]])
/* Is the vertex at pos a second liberty of the owl goal? */
second_liberty_of_goal(int pos
, struct local_owl_data
*owl
)
if (board
[pos
+ delta
[k
]] == EMPTY
&& liberty_of_goal(pos
+ delta
[k
], owl
))
/* 'liberty' is a liberty of 'worm' which we would like to fill.
* However it is not safe to play there, so we look for a
* backfilling move. For example in this situation:
* If 'worm' is the O string and 'liberty' is 'a', the
* function returns 'b'. To fill at 'a', X must first
* fill 'b' and 'c' and it is better to fill at 'b' first
* since that will sometimes leave fewer or smaller ko threats.
* Returns NO_MOVE if no move is found.
find_semeai_backfilling_move(int worm
, int liberty
)
int other
= OTHER_COLOR(color
);
if (safe_move(liberty
, other
) == WIN
)
if (is_self_atari(liberty
, other
)) {
if (approxlib(liberty
, other
, 1, &fill
) > 0
&& trymove(fill
, other
, "find_semeai_backfilling_move", worm
)) {
if (safe_move(liberty
, other
))
else if (board
[worm
] != EMPTY
)
result
= find_semeai_backfilling_move(worm
, liberty
);
if (ON_BOARD(result
) && safe_move(result
, other
))
/* Some helper function for do_owl_attack/defend. */
reading_limit_reached(const char **live_reason
, int this_variation_number
)
/* If (stackp > owl_reading_depth), interpret deep reading
* conservatively as escape.
if (stackp
> owl_reading_depth
) {
TRACE("%oVariation %d: ALIVE (maximum reading depth reached)\n",
*live_reason
= "max reading depth reached";
/* If the owl node limit has been reached, assume the dragon has
if (local_owl_node_counter
>= owl_node_limit
) {
TRACE("%oVariation %d: ALIVE (owl node limit reached)\n",
*live_reason
= "owl node limit reached";
clear_owl_move_data(struct owl_move_data moves
[MAX_MOVES
])
for (k
= 0; k
< MAX_MOVES
; k
++) {
moves
[k
].same_dragon
= SAME_DRAGON_CONNECTED
;
moves
[k
].lunch
= NO_MOVE
;
moves
[k
].pattern_data
= NULL
;
clear_cut_list(moves
[k
].cuts
);
set_single_owl_move(struct owl_move_data moves
[MAX_MOVES
],
int pos
, const char *name
)
moves
[0].same_dragon
= SAME_DRAGON_MAYBE_CONNECTED
;
moves
[0].lunch
= NO_MOVE
;
moves
[0].pattern_data
= NULL
;
clear_cut_list(moves
[0].cuts
);
/* Returns true if a move can be found to attack the dragon
* at (target), in which case (*attack_point) is the recommended move.
* (attack_point) can be a null pointer if only the result is needed.
* The array goal marks the extent of the dragon. This must
* be maintained during reading. Call this function only when
* stackp==0; otherwise you can call do_owl_attack but you must
* set up the goal and boundary arrays by hand first.
* Returns KO_A or KO_B if the position is ko:
* - Returns KO_A if the attack prevails provided attacker is willing to
* ignore any ko threat (the attacker makes the first ko capture).
* - Returns KO_B if attack succeeds provided attacker has a ko threat
* which must be answered (the defender makes the first ko capture).
* If GNU Go is compiled with `configure --enable-experimental-owl-ext'
* then a return codes of GAIN is also possible.
* - Returns GAIN if the attack fails but another worm of the
* opponent's is captured in during the failed attack. The location
* of the killed worm is returned through the *kworm field.
owl_attack(int target
, int *attack_point
, int *certain
, int *kworm
)
struct local_owl_data
*owl
;
int reading_nodes_when_called
= get_reading_node_counter();
int wid
= MAX_GOAL_WORMS
;
if (worm
[target
].unconditional_status
== DEAD
) {
if (search_persistent_owl_cache(OWL_ATTACK
, target
, 0, 0, &result
,
attack_point
, kworm
, certain
))
if (debug
& DEBUG_OWL_PERFORMANCE
)
TRACE("owl_attack %1m\n", target
);
init_owl(&owl
, target
, NO_MOVE
, NO_MOVE
, 1, NULL
);
owl_make_domains(owl
, NULL
);
prepare_goal_list(target
, owl
, owl_goal_worm
, &goal_worms_computed
,
result
= do_owl_attack(target
, &move
, &wid
, owl
, 0);
finish_goal_list(&goal_worms_computed
, &wpos
, owl_goal_worm
, wid
);
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
DEBUG(DEBUG_OWL_PERFORMANCE
,
"owl_attack %1m, result %d %1m (%d, %d nodes, %f seconds)\n",
target
, result
, move
, local_owl_node_counter
,
tactical_nodes
, gg_cputime() - start
);
store_persistent_owl_cache(OWL_ATTACK
, target
, 0, 0,
result_certain
, tactical_nodes
,
owl
->goal
, board
[target
]);
*certain
= result_certain
;
/* Static function containing the main recursive code for
do_owl_attack(int str
, int *move
, int *wormid
,
struct local_owl_data
*owl
, int escape
)
int other
= OTHER_COLOR(color
);
struct owl_move_data vital_moves
[MAX_MOVES
];
struct owl_move_data shape_moves
[MAX_MOVES
];
struct owl_move_data
*moves
;
struct matched_patterns_list_data shape_patterns
;
signed char mw
[BOARDMAX
];
int number_tried_moves
= 0;
int saveworm
= MAX_GOAL_WORMS
;
int eyemin
= -1; /* Lower bound on the number of eyes. */
int eyemax
= -1; /* Upper bound on the number of eyes. */
struct eyevalue probable_eyes
; /* Best guess of eyevalue. */
int this_variation_number
= count_variations
- 1;
SETUP_TRACE_INFO("owl_attack", str
);
shape_patterns
.initialized
= 0;
if (tt_get(&ttable
, OWL_ATTACK
, str
, NO_MOVE
, depth
- stackp
, NULL
,
&value1
, &value2
, &xpos
) == 2) {
TRACE_CACHED_RESULT(value1
, xpos
);
*wormid
= MAX_GOAL_WORMS
;
TRACE("%oVariation %d: DEAD (cached)\n", this_variation_number
);
TRACE("%oVariation %d: ALIVE (cached)\n", this_variation_number
);
SGFTRACE(xpos
, value1
, "cached");
/* If reading goes to deep or we run out of nodes, we assume life. */
if (reading_limit_reached(&live_reason
, this_variation_number
)) {
SGFTRACE(0, 0, live_reason
);
READ_RETURN(OWL_ATTACK
, str
, depth
- stackp
, move
, 0, 0);
memset(mw
, 0, sizeof(mw
));
global_owl_node_counter
++;
local_owl_node_counter
++;
memset(owl
->safe_move_cache
, 0, sizeof(owl
->safe_move_cache
));
/* First see whether there is any chance to kill. */
if (owl_estimate_life(owl
, NULL
, vital_moves
, &live_reason
, 1,
&probable_eyes
, &eyemin
, &eyemax
)) {
* We need to check here if there's a worm under atari. If yes,
* locate it and report a (gote) GAIN.
if (experimental_owl_ext
&& goal_worms_computed
) {
saveworm
= MAX_GOAL_WORMS
;
for (k
= 0; k
< MAX_GOAL_WORMS
; k
++) {
if (owl_goal_worm
[k
] == NO_MOVE
)
if (board
[owl_goal_worm
[k
]] == EMPTY
|| countlib(owl_goal_worm
[k
]) > 1)
if (worm
[owl_goal_worm
[k
]].size
> size
) {
size
= worm
[owl_goal_worm
[k
]].size
;
if (saveworm
!= MAX_GOAL_WORMS
&& size
>= 3) {
findlib(worm
[owl_goal_worm
[saveworm
]].origin
, 1, &mpos
);
SGFTRACE(0, acode
, live_reason
);
TRACE("%oVariation %d: ALIVE (%s)\n", this_variation_number
, live_reason
);
READ_RETURN(OWL_ATTACK
, str
, depth
- stackp
, move
, 0, 0);
READ_RETURN2(OWL_ATTACK
, str
, depth
- stackp
,
move
, mpos
, acode
, saveworm
);
/* We try moves in five passes.
* 0. Vital moves in the interval [70..] [45..]
* 2. Vital moves in the interval [..69] [..44]
* 3. Tactical attack moves (except certain kos)
* 4. Moves found by the defender
* 5. Tactical ko attack moves which were not tried in pass 3
for (pass
= 0; pass
< 6; pass
++) {
/* Get the shape moves if we are in the right pass. */
if (stackp
> owl_branch_depth
&& number_tried_moves
> 0)
owl_shapes(&shape_patterns
, shape_moves
, other
, owl
, &owl_attackpat_db
);
if (stackp
> owl_branch_depth
&& number_tried_moves
> 0)
if (pass
== 0 || stackp
> owl_distrust_depth
) {
if (eyemax
< 2 && stackp
> 2)
move_cutoff
= 99; /* Effectively disable vital moves. */
/* Look for a tactical attack. This is primarily intended for
* the case where the whole dragon is a single string, therefore
* we only look at the string at the "origin".
* We must be wary with attacks giving ko. Unless the dragon
* otherwise looks alive, this may turn a dead dragon into one
* which can live by ko. Such moves will be tried anyway in
* pass 5. Notice though that we can only reach there if an owl
* defense was found in pass 4.
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
result
= attack(str
, &apos
);
|| (result
!= 0 && (min_eyes(&probable_eyes
) >= 2
set_single_owl_move(shape_moves
, apos
, "tactical attack");
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* If we found no move in the first four passes we ask the defender
if (number_tried_moves
== 0) {
int dcode
= do_owl_defend(str
, &dpos
, NULL
, owl
, escape
);
/* No defense, we won. */
TRACE("%oVariation %d: DEAD (no defense)\n",
SGFTRACE(0, WIN
, "no defense");
close_pattern_list(other
, &shape_patterns
);
READ_RETURN(OWL_ATTACK
, str
, depth
- stackp
, move
, 0, WIN
);
else if (dpos
!= NO_MOVE
) {
/* The dragon could be defended by one more move. Try to
* If the move is suicide for us, try to find a backfilling
* move to play instead. Do this also if the move is a
* send-two-return-one sacrifice.
const char *name
= "defense move";
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
if (is_suicide(dpos
, other
) || send_two_return_one(dpos
, other
)) {
for (k
= 0; k
< 4; k
++) {
if (board
[dpos
+ delta
[k
]] == other
&& find_defense(dpos
+ delta
[k
], &dpos2
)) {
name
= "defense move (backfill)";
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
set_single_owl_move(shape_moves
, dpos
, name
);
/* FIXME: This block probably should reappear somewhere in this
/* First test whether the dragon has escaped. */
if (owl_escape_route(owl
) >= 5) {
/* FIXME: We probably should make distinction in the returned
* result whether the dragon lives by making two eyes or by
TRACE("%oVariation %d: ALIVE (escaped)\n", this_variation_number
);
SGFTRACE(0, 0, "escaped");
close_pattern_list(other
, &shape_patterns
);
READ_RETURN0(OWL_ATTACK
, str
, depth
- stackp
);
/* For the up to MAX_MOVES best moves with value equal to
* move_cutoff or higher, try to attack the dragon and see if it
for (k
= 0; k
< MAX_MOVES
; k
++) {
int wid
= MAX_GOAL_WORMS
;
/* Consider only the highest scoring move if we're deeper than
* FIXME: To behave as intended, k should be replaced by
if (stackp
> owl_branch_depth
&& k
> 0)
/* Shape moves are selected on demand. */
if (!get_next_move_from_list(&shape_patterns
, other
,
shape_moves
, move_cutoff
, owl
))
if (moves
[k
].value
< move_cutoff
)
/* Have we already tested this move? */
captured
= (color
== WHITE
? white_captured
: black_captured
);
/* Try to make the move. */
if (!komaster_trymove(mpos
, other
, moves
[k
].name
, str
,
&ko_move
, savecode
== 0))
captured
= (color
== WHITE
? white_captured
: black_captured
) - captured
;
TRACE("Trying %C %1m. Escape = %d. Current stack: ",
/* We have now made a move. Analyze the new position. */
owl_update_boundary_marks(mpos
, owl
);
/* If the origin of the dragon has been captured, we look
* for another string which was part of the original dragon,
* marked when stackp==0, which has not been captured. If no
* such string is found, owl_attack declares victory.
if (IS_STONE(board
[str
]))
origin
= select_new_goal_origin(NO_MOVE
, owl
);
/* Test whether the move cut the goal dragon apart. */
if (moves
[k
].cuts
[0] != NO_MOVE
&& origin
!= NO_MOVE
) {
owl_test_cuts(owl
->goal
, owl
->color
, moves
[k
].cuts
);
origin
= select_new_goal_origin(origin
, owl
);
mark_goal_in_sgf(owl
->goal
);
dcode
= do_owl_defend(origin
, NULL
, &wid
, owl
, escape
);
wintxt
= "all original stones captured";
wintxt
= "attack effective";
sprintf(winstr
, "%s)\n (%d variations", wintxt
,
count_variations
- this_variation_number
);
SGFTRACE(mpos
, WIN
, winstr
);
close_pattern_list(other
, &shape_patterns
);
READ_RETURN(OWL_ATTACK
, str
, depth
- stackp
, move
, mpos
, WIN
);
else if (experimental_owl_ext
&& dcode
== LOSS
) {
if (saveworm
== MAX_GOAL_WORMS
|| worm
[owl_goal_worm
[wid
]].size
> worm
[owl_goal_worm
[saveworm
]].size
)
/* The conditions here are set so that this code doesn't get
* triggered when the capture is immediate (the tactical
* reading code should take care of these).
else if (experimental_owl_ext
&& goal_worms_computed
/* locate the biggest captured worm */
for (l
= 0; l
< MAX_GOAL_WORMS
; l
++) {
if (owl_goal_worm
[l
] == NO_MOVE
)
if (board
[owl_goal_worm
[l
]] == EMPTY
)
if (size
== 0 || worm
[owl_goal_worm
[l
]].size
> size
) {
size
= worm
[owl_goal_worm
[l
]].size
;
if (w
!= MAX_GOAL_WORMS
) {
/* if new result better, just update */
else if (GAIN
== savecode
) {
int wpos
= owl_goal_worm
[saveworm
];
if (size
> worm
[wpos
].size
)
UPDATE_SAVED_KO_RESULT(savecode
, savemove
, dcode
, mpos
);
SGFTRACE(mpos
, KO_B
, "all original stones captured with ko");
SGFTRACE(mpos
, KO_B
, "attack effective - ko");
/* We already know the savecode was previously 0. */
/* It's possible that the defender has no defense even if we
* give up the ko. In order to force a test of this,
* assuming this was our only move, we decrease the number
* of tried moves counter, disregarding this move.
close_pattern_list(other
, &shape_patterns
);
SGFTRACE(savemove
, savecode
, "attack effective (gain) - E");
READ_RETURN2(OWL_ATTACK
, str
, depth
- stackp
,
move
, savemove
, savecode
, saveworm
);
SGFTRACE(savemove
, savecode
, "attack effective (ko) - E");
READ_RETURN(OWL_ATTACK
, str
, depth
- stackp
, move
, savemove
, savecode
);
sprintf(winstr
, "attack failed)\n (%d variations",
count_variations
- this_variation_number
);
READ_RETURN0(OWL_ATTACK
, str
, depth
- stackp
);
/* Returns true if the dragon at (target) can be captured given
* two moves in a row. The first two moves to capture the
* dragon are given as (*attack1) and (*attack2).
owl_threaten_attack(int target
, int *attack1
, int *attack2
)
struct owl_move_data moves
[MAX_MOVES
];
int other
= OTHER_COLOR(board
[target
]);
struct local_owl_data
*owl
;
int reading_nodes_when_called
= get_reading_node_counter();
signed char saved_boundary
[BOARDMAX
];
struct matched_patterns_list_data shape_patterns
;
shape_patterns
.initialized
= 0;
if (search_persistent_owl_cache(OWL_THREATEN_ATTACK
, target
, 0, 0,
&result
, attack1
, attack2
, NULL
))
if (debug
& DEBUG_OWL_PERFORMANCE
)
TRACE("owl_threaten_attack %1m\n", target
);
init_owl(&owl
, target
, NO_MOVE
, NO_MOVE
, 1, NULL
);
memcpy(saved_boundary
, owl
->boundary
, sizeof(saved_boundary
));
owl_make_domains(owl
, NULL
);
owl_shapes(&shape_patterns
, moves
, other
, owl
, &owl_attackpat_db
);
for (k
= 0; k
< MAX_MOVES
; k
++) {
if (!get_next_move_from_list(&shape_patterns
, other
, moves
, 1, owl
))
if (mpos
!= NO_MOVE
&& moves
[k
].value
> 0)
if (trymove(mpos
, other
, moves
[k
].name
, target
)) {
owl
->lunches_are_current
= 0;
owl_update_boundary_marks(mpos
, owl
);
/* If the origin of the dragon has been captured, we look
* for another string which was part of the original dragon,
* marked when stackp==0, which has not been captured. If no
* such string is found, owl_attack declares victory.
if (board
[target
] == EMPTY
) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (IS_STONE(board
[pos
]) && owl
->goal
[pos
] == 1) {
origin
= find_origin(pos
);
|| do_owl_attack(origin
, NULL
, NULL
, owl
, 0)) {
/* probably this can't happen */
else if (do_owl_attack(target
, &move2
, NULL
, owl
, 0) == WIN
) {
memcpy(owl
->boundary
, saved_boundary
, sizeof(saved_boundary
));
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
DEBUG(DEBUG_OWL_PERFORMANCE
,
"owl_threaten_attack %1m %1m %1m, result %d (%d, %d nodes, %f seconds)\n",
target
, move
, move2
, result
, local_owl_node_counter
,
tactical_nodes
, gg_cputime() - start
);
store_persistent_owl_cache(OWL_THREATEN_ATTACK
, target
, 0, 0,
tactical_nodes
, owl
->goal
, board
[target
]);
close_pattern_list(other
, &shape_patterns
);
/* Returns true if a move can be found to defend the dragon
* at (target), in which case (*defense_point) is the recommended move.
* (defense_point) can be a null pointer if the result is not needed.
* The array goal marks the extent of the dragon. This must
* be maintained during reading. Call this function only when
* stackp==0; otherwise you can call do_owl_attack but you must
* set up the goal and boundary arrays by hand first.
* Returns KO_A or KO_B if the position is ko:
* - Returns KO_A if the defendse succeeds provided the defender is willing to
* ignore any ko threat (the defender makes the first ko capture).
* - Returns KO_B if the defense succeeds provided the defender has a ko threat
* which must be answered (the attacker makes the first ko capture).
* If GNU Go is compiled with `configure --enable-experimental-owl-ext'
* then a return codes of GAIN is also possible.
* - Returns LOSS if the defense succeeds but another worm of the
* defender's is captured in during the defense. The location
* of the killed worm is returned through the *kworm field.
* The array goal marks the extent of the dragon. This must
* be maintained during reading.
owl_defend(int target
, int *defense_point
, int *certain
, int *kworm
)
static struct local_owl_data
*owl
;
int reading_nodes_when_called
= get_reading_node_counter();
int wid
= MAX_GOAL_WORMS
;
if (worm
[target
].unconditional_status
== DEAD
)
if (search_persistent_owl_cache(OWL_DEFEND
, target
, 0, 0, &result
,
defense_point
, kworm
, certain
))
if (debug
& DEBUG_OWL_PERFORMANCE
)
TRACE("owl_defend %1m\n", target
);
init_owl(&owl
, target
, NO_MOVE
, NO_MOVE
, 1, NULL
);
owl_make_domains(owl
, NULL
);
prepare_goal_list(target
, owl
, owl_goal_worm
, &goal_worms_computed
,
result
= do_owl_defend(target
, &move
, &wid
, owl
, 0);
finish_goal_list(&goal_worms_computed
, &wpos
, owl_goal_worm
, wid
);
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
DEBUG(DEBUG_OWL_PERFORMANCE
,
"owl_defend %1m, result %d %1m (%d, %d nodes, %f seconds)\n",
target
, result
, move
, local_owl_node_counter
,
tactical_nodes
, gg_cputime() - start
);
store_persistent_owl_cache(OWL_DEFEND
, target
, 0, 0, result
, move
, wpos
,
result_certain
, tactical_nodes
, owl
->goal
,
*certain
= result_certain
;
/* Static function containing the main recursive code for owl_defend.
do_owl_defend(int str
, int *move
, int *wormid
, struct local_owl_data
*owl
,
struct owl_move_data shape_moves
[MAX_MOVES
];
struct owl_move_data vital_moves
[MAX_MOVES
];
struct owl_move_data
*moves
;
struct matched_patterns_list_data shape_patterns
;
signed char mw
[BOARDMAX
];
int number_tried_moves
= 0;
int saveworm
= MAX_GOAL_WORMS
;
int eyemin
= -1; /* Lower bound on the number of eyes. */
int eyemax
= -1; /* Upper bound on the number of eyes. */
struct eyevalue probable_eyes
; /* Best guess of eyevalue. */
int this_variation_number
= count_variations
- 1;
SETUP_TRACE_INFO("owl_defend", str
);
shape_patterns
.initialized
= 0;
if (tt_get(&ttable
, OWL_DEFEND
, str
, NO_MOVE
, depth
- stackp
, NULL
,
&value1
, &value2
, &xpos
) == 2) {
TRACE_CACHED_RESULT(value1
, xpos
);
*wormid
= MAX_GOAL_WORMS
;
if (value1
== WIN
|| value1
== LOSS
)
TRACE("%oVariation %d: ALIVE (cached)\n", this_variation_number
);
TRACE("%oVariation %d: DEAD (cached)\n", this_variation_number
);
SGFTRACE(xpos
, value1
, "cached");
/* In order to get a defense move even if we seem to already have
* escaped and to reduce the impact of overestimated escape
* possibilities, we don't declare escape victory on the first move.
* FIXME: Should introduce a new owl depth value rather than having
escape_route
= owl_escape_route(owl
);
if (stackp
> 2 && escape_route
>= 5) {
/* FIXME: We probably should make distinction in the returned
* result whether the dragon lives by making two eyes or by
TRACE("%oVariation %d: ALIVE (escaped)\n", this_variation_number
);
SGFTRACE(0, WIN
, "escaped");
READ_RETURN(OWL_DEFEND
, str
, depth
- stackp
, move
, 0, WIN
);
/* If reading goes to deep or we run out of nodes, we assume life. */
if (reading_limit_reached(&live_reason
, this_variation_number
)) {
SGFTRACE(0, WIN
, live_reason
);
READ_RETURN(OWL_DEFEND
, str
, depth
- stackp
, move
, 0, WIN
);
memset(mw
, 0, sizeof(mw
));
local_owl_node_counter
++;
global_owl_node_counter
++;
memset(owl
->safe_move_cache
, 0, sizeof(owl
->safe_move_cache
));
/* First see whether we might already be alive. */
if (escape
< MAX_ESCAPE
) {
if (owl_estimate_life(owl
, NULL
, vital_moves
, &live_reason
, 0,
&probable_eyes
, &eyemin
, &eyemax
)) {
SGFTRACE(0, WIN
, live_reason
);
TRACE("%oVariation %d: ALIVE (%s)\n",
this_variation_number
, live_reason
);
READ_RETURN(OWL_DEFEND
, str
, depth
- stackp
, move
, 0, WIN
);
/* In this case we don't recompute eyes. However, to avoid accessing
* partially-random data left on stack, we copy eye data from the
* previous depth level. It should be reasonably close to the actual
memcpy(owl
->my_eye
, owl
->restore_from
->my_eye
, sizeof(owl
->my_eye
));
memcpy(owl
->half_eye
, owl
->restore_from
->half_eye
, sizeof(owl
->half_eye
));
vital_moves
[0].value
= -1;
set_eyevalue(&probable_eyes
, 0, 0, 0, 0);
/* We try moves in four passes.
* 0. Vital moves in the interval [70..] [45..]
* 2. Vital moves in the interval [..69] [..44]
* 3. Tactical defense moves
for (pass
= 0; pass
< 4; pass
++) {
/* Get the shape moves if we are in the right pass. */
if (stackp
> owl_branch_depth
&& number_tried_moves
> 0)
owl_shapes(&shape_patterns
, shape_moves
, color
, owl
, &owl_defendpat_db
);
if (stackp
> owl_branch_depth
&& number_tried_moves
> 0)
if (pass
== 0 || stackp
> owl_distrust_depth
) {
else if (eyemin
+ min_eyes(&probable_eyes
) > 3)
else if (eyemin
+ min_eyes(&probable_eyes
) >= 3)
if (eyemax
< 2 && stackp
> 2)
move_cutoff
= 99; /* Effectively disable vital moves. */
/* If the goal is small, try a tactical defense. */
for (k
= BOARDMIN
; k
< BOARDMAX
; k
++)
goalcount
+= owl
->goal
[k
];
/* Look for a tactical defense. This is primarily intended for
* the case where the whole dragon is a single string, therefore
* we only look at the string at the "origin".
* We only accept clearly effective tactical defenses here,
* using a liberty heuristic. The reason for this is problems
* with ineffective self ataris which do defend tactically but
* have no strategical effect other than wasting owl nodes or
* confusing the eye analysis.
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
if (attack_and_defend(str
, NULL
, NULL
, NULL
, &dpos
)
&& (approxlib(dpos
, color
, 2, NULL
) > 1
|| does_capture_something(dpos
, color
))) {
TRACE("Found tactical defense for %1m at %1m.\n", str
, dpos
);
set_single_owl_move(shape_moves
, dpos
, "tactical_defense");
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* For the up to MAX_MOVES best moves with value equal to
* move_cutoff or higher, try to defend the dragon and see if it
for (k
= 0; k
< MAX_MOVES
; k
++) {
int wid
= MAX_GOAL_WORMS
;
/* Consider only the highest scoring move if we're deeper than
* FIXME: To behave as intended, k should be replaced by
if (stackp
> owl_branch_depth
&& k
> 0)
if (!get_next_move_from_list(&shape_patterns
, color
, shape_moves
,
if (moves
[k
].value
< move_cutoff
)
modify_eyefilling_move(&mpos
, color
);
/* Have we already tested this move? */
/* Try to make the move. */
if (!komaster_trymove(mpos
, color
, moves
[k
].name
, str
,
&ko_move
, savecode
== 0))
TRACE("Trying %C %1m. Escape = %d. Current stack: ",
/* We have now made a move. Analyze the new position. */
/* Add the stone just played to the goal dragon, unless the
* pattern explicitly asked for not doing this.
owl_update_goal(mpos
, moves
[k
].same_dragon
, moves
[k
].lunch
, owl
, 0,
mark_goal_in_sgf(owl
->goal
);
int acode
= do_owl_attack(str
, NULL
, &wid
, owl
, new_escape
);
sprintf(winstr
, "defense effective)\n (%d variations",
count_variations
- this_variation_number
);
SGFTRACE(mpos
, WIN
, winstr
);
close_pattern_list(color
, &shape_patterns
);
READ_RETURN(OWL_DEFEND
, str
, depth
- stackp
, move
, mpos
, WIN
);
UPDATE_SAVED_KO_RESULT(savecode
, savemove
, acode
, mpos
);
if (do_owl_attack(str
, NULL
, NULL
, owl
, new_escape
) != WIN
) {
/* Undo the tested move. */
close_pattern_list(color
, &shape_patterns
);
SGFTRACE(savemove
, savecode
, "defense effective (loss) - B");
READ_RETURN2(OWL_DEFEND
, str
, depth
- stackp
,
move
, savemove
, savecode
, saveworm
);
SGFTRACE(savemove
, savecode
, "defense effective (ko) - B");
READ_RETURN(OWL_DEFEND
, str
, depth
- stackp
, move
, savemove
, savecode
);
if (number_tried_moves
== 0 && min_eyes(&probable_eyes
) >= 2) {
SGFTRACE(0, WIN
, "genus probably >= 2");
READ_RETURN(OWL_DEFEND
, str
, depth
- stackp
, move
, 0, WIN
);
int print_genus
= eyemin
== 1 ? 1 : 0;
sprintf(winstr
, "defense failed - genus %d)\n (%d variations",
print_genus
, count_variations
- this_variation_number
);
READ_RETURN0(OWL_DEFEND
, str
, depth
- stackp
);
/* Returns true if the dragon at (target) can be defended given
* two moves in a row. The first two moves to defend the
* dragon are given as (*defend1) and (*defend2).
owl_threaten_defense(int target
, int *defend1
, int *defend2
)
struct owl_move_data moves
[MAX_MOVES
];
int color
= board
[target
];
struct local_owl_data
*owl
;
int reading_nodes_when_called
= get_reading_node_counter();
signed char saved_goal
[BOARDMAX
];
struct matched_patterns_list_data shape_patterns
;
shape_patterns
.initialized
= 0;
if (worm
[target
].unconditional_status
== DEAD
)
if (search_persistent_owl_cache(OWL_THREATEN_DEFENSE
, target
, 0, 0,
&result
, defend1
, defend2
, NULL
))
if (debug
& DEBUG_OWL_PERFORMANCE
)
TRACE("owl_threaten_defense %1m\n", target
);
init_owl(&owl
, target
, NO_MOVE
, NO_MOVE
, 1, NULL
);
memcpy(saved_goal
, owl
->goal
, sizeof(saved_goal
));
owl_make_domains(owl
, NULL
);
owl_shapes(&shape_patterns
, moves
, color
, owl
, &owl_defendpat_db
);
for (k
= 0; k
< MAX_MOVES
; k
++) {
if (!get_next_move_from_list(&shape_patterns
, color
, moves
, 1, owl
))
if (moves
[k
].pos
!= NO_MOVE
&& moves
[k
].value
> 0)
if (trymove(moves
[k
].pos
, color
, moves
[k
].name
, target
)) {
owl
->lunches_are_current
= 0;
owl_update_goal(moves
[k
].pos
, moves
[k
].same_dragon
,
moves
[k
].lunch
, owl
, 0, moves
[k
].pattern_data
);
if (do_owl_defend(target
, &move2
, NULL
, owl
, 0) == WIN
) {
/* Don't return the second move if occupied before trymove */
if (move2
!= NO_MOVE
&& IS_STONE(board
[move2
]))
memcpy(owl
->goal
, saved_goal
, sizeof(saved_goal
));
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
DEBUG(DEBUG_OWL_PERFORMANCE
,
"owl_threaten_defense %1m %1m %1m, result %d (%d, %d nodes, %f seconds)\n",
target
, move
, move2
, result
, local_owl_node_counter
,
tactical_nodes
, gg_cputime() - start
);
store_persistent_owl_cache(OWL_THREATEN_DEFENSE
, target
, 0, 0,
tactical_nodes
, owl
->goal
, board
[target
]);
close_pattern_list(color
, &shape_patterns
);
* This function calls owl_determine_life() to get an eye estimate,
* and matchpat() for vital attack moves, and decides according to
* various policies (depth-dependant) whether the dragon should thus
owl_estimate_life(struct local_owl_data
*owl
,
struct local_owl_data
*second_owl
,
struct owl_move_data vital_moves
[MAX_MOVES
],
const char **live_reason
, int does_attack
,
struct eyevalue
*probable_eyes
, int *eyemin
, int *eyemax
)
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
struct owl_move_data dummy_moves
[MAX_MOVES
];
int other
= OTHER_COLOR(owl
->color
);
owl_determine_life(owl
, second_owl
, does_attack
, vital_moves
,
probable_eyes
, eyemin
, eyemax
);
memset(found_matches
, 0, sizeof(found_matches
));
memset(owl
->safe_move_cache
, 0, sizeof(owl
->safe_move_cache
));
clear_owl_move_data(dummy_moves
);
matchpat(owl_shapes_callback
, other
,
&owl_vital_apat_db
, dummy_moves
, owl
->goal
);
else if (max_eyes(probable_eyes
) >= 2)
matchpat(owl_shapes_callback
, other
,
&owl_vital_apat_db
, vital_moves
, owl
->goal
);
if ((debug
& DEBUG_EYES
) && (debug
& DEBUG_OWL
))
gprintf("owl: eyemin=%d matches_found=%d\n", *eyemin
, matches_found
);
if (*eyemin
>= matches_found
)
*eyemin
-= matches_found
;
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
|| (*eyemin
== 1 && min_eyes(probable_eyes
) >= 4)
|| (stackp
> owl_distrust_depth
&& min_eyes(probable_eyes
) >= 2
*live_reason
= "2 or more secure eyes";
else if (*eyemin
== 1 && min_eyes(probable_eyes
) >= 4)
*live_reason
= "1 secure eye, likely >= 4";
else if (stackp
> owl_distrust_depth
&& min_eyes(probable_eyes
) >= 2
*live_reason
= "getting deep, looks lively";
&& (*eyemin
+ matches_found
>= 2
|| (*eyemin
+ matches_found
== 1 && min_eyes(probable_eyes
) >= 4)
|| (stackp
> owl_distrust_depth
&& min_eyes(probable_eyes
) >= 2))) {
/* We are not yet alive only due to owl vital attack patterns matching.
* Let's try to defend against it.
owl_add_move(vital_moves
, dummy_moves
[0].defense_pos
,
dummy_moves
[0].value
, dummy_moves
[0].name
,
SAME_DRAGON_CONNECTED
, NO_MOVE
, 0, NO_MOVE
, MAX_MOVES
, NULL
);
* This function is invoked from do_owl_attack() and do_owl_defend()
* for each node to determine whether the the dragon has sufficient
* eye potential to live. It also generates vital moves to attack or
* defend the eyes. There are two distinct sources for eyes. The first
* is the eyespaces found by make_domains() and evaluated by
* compute_eyes_pessimistic(). The second is the lunches found by
* owl_find_lunches() and evaluated by sniff_lunch().
* The best guess of the eye potential is stored as an eyevalue in
* *probable_eyes. This is not entirely reliable though since the
* graph matching techniques in optics.c fail to understand subtleties
* like atari inside the eyespace, cutting points in the wall, and
* shortage of outside liberties. (The patterns in owl_vital_apats.db
* are used to compensate for this. See do_owl_attack() and
* do_owl_defend() for how these are used.) Also the estimates from
* sniff_lunch() are fairly unreliable.
* A lower and upper bound on the number of eyes are returned in
* *eyemin and *eyemax. The value of *eyemin must be offset by the
* matches of owl_vital_apats.db. If that number is 2 or larger, we
* should be certain of life.
* Vital moves to attack or defend eyes are returned in the moves[]
* array. Also moves to reduce the uncertainty of the eye estimates
* are added to this array, but with smaller move values. The
* parameter does_attack determines whether to generate vital attack
* moves or vital defense moves.
* The dragon is specified by the information in the owl struct. The
* color of the dragon is passed in the color parameter.
* For use in the semeai code, a second dragon can be provided. Set
* this to NULL when only one dragon is involved.
owl_determine_life(struct local_owl_data
*owl
,
struct local_owl_data
*second_owl
,
struct owl_move_data
*moves
,
struct eyevalue
*probable_eyes
, int *eyemin
, int *eyemax
)
struct eye_data
*eye
= owl
->my_eye
;
int mw
[BOARDMAX
]; /* mark relevant eye origins */
int mz
[BOARDMAX
]; /* mark potentially irrelevant eye origins */
int vital_values
[BOARDMAX
];
struct eyevalue eyevalue
;
struct eyevalue eyevalue_list
[BOARDMAX
/2];
int eyes_attack_points
[BOARDMAX
/2];
memset(vital_values
, 0, sizeof(vital_values
));
/* Turn off eye debugging if we're not also debugging owl. */
if (!(debug
& DEBUG_OWL
))
clear_owl_move_data(moves
);
if (!owl
->lunches_are_current
)
for (k
= 0; k
< MAX_LUNCHES
; k
++)
if (owl
->lunch
[k
] != NO_MOVE
)
gprintf("owl lunch %1m, attack %1m, defend %1m\n",
owl
->lunch_attack_point
[k
],
owl
->lunch_defense_point
[k
]);
owl_make_domains(owl
, second_owl
);
owl_find_relevant_eyespaces(owl
, mw
, mz
);
/* Reset halfeye data. Set topological eye value to something big. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
owl
->half_eye
[pos
].type
= 0;
owl
->half_eye
[pos
].value
= 10.0;
/* Find topological half eyes and false eyes. */
find_half_and_false_eyes(color
, eye
, owl
->half_eye
, mw
);
/* The eyespaces may have been split or changed in other ways by the
* topological analysis, so we need to regenerate them and once more
* determine which ones are relevant.
partition_eyespaces(owl
->my_eye
, owl
->color
);
owl_find_relevant_eyespaces(owl
, mw
, mz
);
set_eyevalue(probable_eyes
, 0, 0, 0, 0);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (ON_BOARD(pos
) && mw
[pos
] > 1) {
compute_eyes_pessimistic(pos
, &eyevalue
, &pessimistic_min
,
&attack_point
, &defense_point
,
/* If the eyespace is more in contact with own stones not in the goal,
* than with ones in the goal, there is a risk that we can be cut off
* from a major part of the eyespace. Thus we can't trust the opinion
* (Obviously this is a quite fuzzy heuristic. With more accurate
* connection analysis in the owl code we could do this more robustly.)
|| (mw
[pos
] < 3 * mz
[pos
] && mz
[pos
] > 5))
/* It appears that this policy is needed no longer. */
/* If this eyespace includes an owl inessential string, we must assume
* that the pessimistic min is 0.
if (pessimistic_min
> 0) {
for (pos2
= BOARDMIN
; pos2
< BOARDMAX
; pos2
++) {
&& eye
[pos2
].origin
== pos
&& owl
->inessential
[pos2
]) {
eyes_attack_points
[num_eyes
] = NO_MOVE
;
eyevalue_list
[num_eyes
] = eyevalue
;
*eyemin
+= pessimistic_min
;
/* Fill in the value field for use by the owl_eyespace() function. */
eye
[pos
].value
= eyevalue
;
/* This shortcut has been disabled for two reasons:
* 1. Due to the vital attack moves being able to later reduce
* the *eyemin, we can't say that a certain *eyemin is
* 2. This part of the code is in no way time critical.
/* Found two certain eyes---look no further. */
if (eye_move_urgency(&eyevalue
)) {
if (max_eyes(&eyevalue
) - min_eyes(&eyevalue
) == 2)
else if (max_eyes(&eyevalue
) - pessimistic_min
== 2)
else if (max_eyes(&eyevalue
) != pessimistic_min
) {
if (max_eyes(&eyevalue
) - pessimistic_min
== 2)
reason
= "marginal eye space";
if (does_attack
&& attack_point
!= NO_MOVE
) {
if (vital_values
[attack_point
] > 0) {
value
+= vital_values
[attack_point
];
value
= 98; /* Higher values may get special interpretation. */
TRACE("%s at %1m, score %d (eye at %1m, value %s, pessimistic_min %d)\n",
reason
, attack_point
, value
,
pos
, eyevalue_to_string(&eyevalue
), pessimistic_min
);
if (eye
[attack_point
].marginal
&& modify_stupid_eye_vital_point(owl
, &attack_point
, 1))
TRACE("vital point looked stupid, moved it to %1m\n",
if (attack_point
!= NO_MOVE
) {
owl_add_move(moves
, attack_point
, value
, reason
,
SAME_DRAGON_MAYBE_CONNECTED
, NO_MOVE
,
0, NO_MOVE
, MAX_MOVES
, NULL
);
vital_values
[attack_point
] = value
;
eyes_attack_points
[num_eyes
] = attack_point
;
/* The reason for the last set of tests is that we don't
* want to play a self atari in e.g. this position
* but it's okay in this position
* In both cases * is the vital point according to the graph
* matching. The significant difference is that in the first
* case the vital point is adjacent to stones in the goal.
&& defense_point
!= NO_MOVE
&& board
[defense_point
] == EMPTY
&& (!liberty_of_goal(defense_point
, owl
)
|| !is_self_atari(defense_point
, color
)
|| is_ko(defense_point
, color
, NULL
)
|| safe_move(defense_point
, color
) != 0)) {
if (vital_values
[defense_point
] > 0) {
value
+= vital_values
[defense_point
];
value
= 98; /* Higher values may get special interpretation. */
TRACE("%s at %1m, score %d (eye at %1m, value %s, pessimistic_min %d)\n",
reason
, defense_point
, value
, pos
,
eyevalue_to_string(&eyevalue
), pessimistic_min
);
if ((eye
[defense_point
].marginal
|| eye
[defense_point
].origin
!= pos
)
&& modify_stupid_eye_vital_point(owl
, &defense_point
, 0))
TRACE("vital point looked stupid, moved it to %1m\n",
if (defense_point
!= NO_MOVE
) {
owl_add_move(moves
, defense_point
, value
, reason
,
SAME_DRAGON_MAYBE_CONNECTED
, NO_MOVE
,
0, NO_MOVE
, MAX_MOVES
, NULL
);
vital_values
[defense_point
] = value
;
/* Sniff each lunch for nutritional value. The assumption is that
* capturing the lunch is gote, therefore the number of half eyes
* equals the MINIMUM number of eyes yielded by the resulting eye
for (lunch
= 0; (lunch
< MAX_LUNCHES
); lunch
++)
if (owl
->lunch
[lunch
] != NO_MOVE
&& owl
->lunch_defense_point
[lunch
] != NO_MOVE
) {
sniff_lunch(owl
->lunch
[lunch
],
&lunch_min
, &lunch_probable
, &lunch_max
, owl
);
set_eyevalue(&e
, 0, 0, lunch_probable
, lunch_probable
);
if (lunch_probable
== 0) {
if (countstones(owl
->lunch
[lunch
]) == 1)
else if (lunch_probable
== 1 && lunch_max
== 1)
value
= 60 + countstones(owl
->lunch
[lunch
]);
else if (lunch_probable
== 1 && lunch_max
== 2)
value
= 70 + countstones(owl
->lunch
[lunch
]);
value
= 75 + countstones(owl
->lunch
[lunch
]);
if (owl
->lunch_attack_code
[lunch
] != WIN
)
defense_point
= improve_lunch_defense(owl
->lunch
[lunch
],
owl
->lunch_defense_point
[lunch
]);
if (vital_values
[defense_point
]) {
/* The point here is that the move which saves the lunch also
* attacks an eye. So this attack move reduces the global eye
* potential. The eyes arithmetic for probable_eyes has then
* to be adapted accordingly.
for (ne
= 0; ne
< num_eyes
- num_lunches
; ne
++)
if (eyes_attack_points
[ne
] == defense_point
)
gg_assert(ne
< num_eyes
- num_lunches
);
add_eyevalues(&eyevalue_list
[ne
], &e
, &eyevalue_list
[ne
]);
eyevalue_list
[num_eyes
++] = e
;
TRACE("save lunch at %1m with %1m, score %d, probable eye %d, max eye %d\n",
owl
->lunch
[lunch
], defense_point
, value
,
lunch_probable
, lunch_max
);
owl_add_move(moves
, defense_point
, value
,
"save lunch", SAME_DRAGON_MAYBE_CONNECTED
,
NO_MOVE
, 0, NO_MOVE
, MAX_MOVES
, NULL
);
attack_point
= improve_lunch_attack(owl
->lunch
[lunch
],
owl
->lunch_attack_point
[lunch
]);
TRACE("eat lunch at %1m with %1m, score %d, probable eye %d, max eye %d\n",
owl
->lunch
[lunch
], attack_point
, value
,
lunch_probable
, lunch_max
);
/* We only remember the lunch for owl_update_goal() if the lunch
* cannot be defended with ko after the move.
* If we capture the lunch by an illegal ko capture, we become
* ko master with this move, and hence the above is true.
if (owl
->lunch_attack_code
[lunch
] == WIN
|| is_illegal_ko_capture(attack_point
, owl
->color
))
owl_add_move(moves
, attack_point
, value
, "eat lunch",
SAME_DRAGON_MAYBE_CONNECTED
, owl
->lunch
[lunch
],
0, NO_MOVE
, MAX_MOVES
, NULL
);
owl_add_move(moves
, attack_point
, value
, "eat lunch",
SAME_DRAGON_MAYBE_CONNECTED
, NO_MOVE
, 0, NO_MOVE
,
eyevalue_list
[num_eyes
++] = e
;
/* now, totalize the eye potential */
for (ne
= 0; ne
< num_eyes
- num_lunches
; ne
++)
add_eyevalues(probable_eyes
, &eyevalue_list
[ne
], probable_eyes
);
*eyemax
+= max_eyes(probable_eyes
);
/* If we have at least two different eyespaces and can create one eye
* in sente, we assume there's a chance to create another one. This is
* needed because optics code don't know about eyespaces influencing
* each other and combination moves (i.e. double threats to create an
if (num_eyes
- num_lunches
> 1 && max_eye_threat(probable_eyes
) > 1)
for (; ne
< num_eyes
; ne
++)
add_eyevalues(probable_eyes
, &eyevalue_list
[ne
], probable_eyes
);
/* The eyespaces we want to evaluate are the ones which
* are adjacent to the dragon (whose stones comprise the
* support of goal) which are not GRAY bordered. These
* are the eyespaces of the dragon. Now we find their
* It is required that there are at least two distinct connections,
* adjacent or diagonal, between non-marginal eyespace vertices and
* stones of the goal dragon. Otherwise there is a risk that we
* include irrelevant eye spaces.
owl_find_relevant_eyespaces(struct local_owl_data
*owl
,
int mw
[BOARDMAX
], int mz
[BOARDMAX
])
struct eye_data
*eye
= owl
->my_eye
;
memset(mw
, 0, BOARDMAX
* sizeof(mw
[0]));
memset(mz
, 0, BOARDMAX
* sizeof(mz
[0]));
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] == owl
->color
) {
for (k
= 0; k
< 8; k
++) {
int pos2
= pos
+ delta
[k
];
&& eye
[pos2
].color
== eye_color
&& !eye
[pos2
].marginal
) {
* The optics code occasionally comes up with stupid vital moves, like
* This function moves such moves to the second line.
* In this position the optics code can suggest the empty 1-2 point as
* vital move for the eyespace on the right edge. That is okay for attack
* but obviously not for defense.
* Playing into a snapback is usually not an effective way to destroy
* This function changes the attack point to NO_MOVE (i.e. removes it).
modify_stupid_eye_vital_point(struct local_owl_data
*owl
, int *vital_point
,
for (k
= 0; k
< 4; k
++) {
if (ON_BOARD(*vital_point
- up
))
if (board
[*vital_point
+ up
] != EMPTY
)
right
= delta
[(k
+1) % 4];
if (board
[*vital_point
+ right
] != EMPTY
|| board
[*vital_point
- right
] != EMPTY
)
if (board
[*vital_point
+ 2 * up
] != EMPTY
|| board
[*vital_point
+ up
+ right
] != EMPTY
|| board
[*vital_point
+ up
- right
] != EMPTY
) {
if (approxlib(*vital_point
, OTHER_COLOR(owl
->color
), 1, NULL
) == 0) {
for (k
= 4; k
< 8; k
++) {
int pos
= *vital_point
+ delta
[k
];
if (board
[pos
] == OTHER_COLOR(owl
->color
)
findlib(pos
, 1, vital_point
);
&& does_capture_something(*vital_point
, OTHER_COLOR(owl
->color
))
&& accuratelib(*vital_point
, OTHER_COLOR(owl
->color
), 2, libs
) == 1
&& !attack(libs
[0], NULL
)) {
/* The purpose of this function is to avoid moves which needlessly
* fill in an eye. A typical example, from ld_owl:188, is
* where various patterns manage to propose the eye-filling move on
* the top edge instead of capturing the opponent stones and get two
* solid eyes. This function modifies the move accordingly.
modify_eyefilling_move(int *move
, int color
)
int other
= OTHER_COLOR(color
);
/* Only do this for a small eye. */
if (ON_BOARD(*move
+ delta
[k
]) && board
[*move
+ delta
[k
]] != color
)
if (board
[*move
+ delta
[r
]] == other
&& countlib(*move
+ delta
[r
]) == 1) {
if (board
[*move
+ delta
[k
]] == color
&& countlib(*move
+ delta
[k
]) == 1
&& !adjacent_strings(*move
+ delta
[r
], *move
+ delta
[k
]))
findlib(*move
+ delta
[r
], 1, &new_move
);
TRACE("Changing eyefilling move at %1m to capture at %1m.\n",
* Generates up to max_moves moves, attempting to attack or defend the goal
* dragon. The found moves are put in moves, an array of owl_move_data
* structs, starting in the position 'initial'. The entries in the array are
* sorted by value with moves[initial] having highest priority. When no more
* moves are available this is indicated by value and coordinates in the array
* This function automatically initializes the owl_safe_move cache the
* pattern list. WATCH OUT: This has to be matched with a call to
* close_pattern_list(pattern_list)!!!
* Returns 1 if at least one move is found, or 0 if no move is found.
owl_shapes(struct matched_patterns_list_data
*pattern_list
,
struct owl_move_data moves
[MAX_MOVES
],
int color
, struct local_owl_data
*owl
, struct pattern_db
*type
)
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
clear_owl_move_data(moves
);
/* We must reset the owl safe_move_cache before starting the
* pattern matching. The cache is used by owl_shapes_callback().
memset(owl
->safe_move_cache
, 0, sizeof(owl
->safe_move_cache
));
init_pattern_list(pattern_list
);
matchpat(collect_owl_shapes_callbacks
, color
, type
, pattern_list
, owl
->goal
);
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* This function contains all the expensive checks for a matched pattern. */
check_pattern_hard(int move
, int color
, struct pattern
*pattern
, int ll
)
int constraint_checked
= 0;
int safe_move_checked
= 0;
/* The very first check is whether we can disregard the pattern due
* due to an owl safe_move_cache lookup.
if (!(pattern
->class & CLASS_s
))
if (current_owl_data
->safe_move_cache
[move
]) {
if (current_owl_data
->safe_move_cache
[move
] == 1)
/* If the constraint is cheap to check, we do this first. */
if ((pattern
->autohelper_flag
& HAVE_CONSTRAINT
)
&& pattern
->constraint_cost
< 0.45) {
if (!pattern
->autohelper(ll
, move
, color
, 0))
/* For sacrifice patterns, the survival of the stone to be played is
* not checked. Otherwise we discard moves which can be captured.
* Illegal ko captures are accepted for ko analysis.
if (!(pattern
->class & CLASS_s
) && !safe_move_checked
) {
if (!owl_safe_move(move
, color
)) {
TRACE(" move at %1m wasn't safe, discarded\n", move
);
if (!is_legal(move
, color
)) {
TRACE(" move at %1m wasn't legal, discarded\n", move
);
/* For class n patterns, the pattern is contingent on an opponent
* move at * not being captured.
* We can't use owl_safe_move() here because we would try the wrong color.
if (pattern
->class & CLASS_n
) {
if (safe_move(move
, OTHER_COLOR(color
)) == 0) {
TRACE(" opponent can't play safely at %1m, move discarded\n", move
);
/* If the pattern has a constraint, call the autohelper to see
* if the pattern must be rejected.
if ((pattern
->autohelper_flag
& HAVE_CONSTRAINT
) && !constraint_checked
)
if (!pattern
->autohelper(ll
, move
, color
, 0))
/* This initializes a pattern list, allocating memory for 200 patterns.
* If more patterns need to be stored, collect_owl_shapes_callbacks will
* dynamically reallocate additional memory.
* The space for list->pattern_list is allocated here.
* This function is automatically called from owl_shapes. Every call here
* has to be matched by a call to close_pattern_list below.
init_pattern_list(struct matched_patterns_list_data
*list
)
gg_assert(!list
->initialized
);
list
->pattern_list
= malloc(200 * sizeof(list
->pattern_list
[0]));
gg_assert(list
->pattern_list
!= NULL
);
list
->pattern_heap
= NULL
;
gprintf("List at %x has new array at %x\n", list
, list
->pattern_list
);
/* This function has to get called before the memory of *list is freed
* in the calling function.
close_pattern_list(int color
, struct matched_patterns_list_data
*list
)
gprintf("%d patterns matched, %d patterns checked\n", list
->counter
,
gprintf("Pattern list at %x freed for list at %x\n",
list
->pattern_list
, list
);
if (allpats
&& verbose
) {
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
if (!current_owl_data
->lunches_are_current
)
owl_find_lunches(current_owl_data
);
pattern_list_build_heap(list
);
for (i
= 0; i
< list
->heap_num_patterns
; i
++)
if (check_pattern_hard(list
->pattern_heap
[i
]->move
, color
,
list
->pattern_heap
[i
]->pattern
,
list
->pattern_heap
[i
]->ll
)) {
TRACE("Remaining valid (but unused) patterns at stack: ");
TRACE("Pattern %s found at %1m with value %d\n",
list
->pattern_heap
[i
]->pattern
->name
,
list
->pattern_heap
[i
]->move
,
(int) list
->pattern_heap
[i
]->pattern
->value
);
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
free(list
->pattern_list
);
free(list
->pattern_heap
);
/* Can be called from gdb for debugging:
* (gdb) set dump_pattern_list(&shape_patterns)
dump_pattern_list(struct matched_patterns_list_data
*list
)
struct matched_pattern_data
*matched_pattern
;
gprintf("%oList size %d. %d Patterns in list, %d have been used.",
list
->list_size
, list
->counter
, list
->used
);
for (i
= 0; i
< list
->counter
; i
++) {
matched_pattern
= &list
->pattern_list
[i
];
gprintf("%o\n Pattern %s (orient. %d) at %1m, value %f.",
matched_pattern
->pattern
->name
, matched_pattern
->ll
,
matched_pattern
->move
, matched_pattern
->pattern
->value
);
if (matched_pattern
->next_pattern_index
!= -1)
gprintf("%oCurrent heap ordering: \n");
for (i
= 0; i
< list
->heap_num_patterns
; i
++) {
matched_pattern
= list
->pattern_heap
[i
];
gprintf("%o %s (%1m), %f; ", matched_pattern
->pattern
->name
,
matched_pattern
->move
, matched_pattern
->pattern
->value
);
/* This function stores a found pattern in the list for later evaluation.
* The only processing done is computing the position of the move, and
collect_owl_shapes_callbacks(int anchor
, int color
, struct pattern
*pattern
,
struct matched_patterns_list_data
*matched_patterns
= data
;
struct matched_pattern_data
*next_pattern
;
UNUSED(color
); /* The calling function has to remember that. */
if (matched_patterns
->counter
>= matched_patterns
->list_size
) {
matched_patterns
->list_size
+= 100;
matched_patterns
->pattern_list
= realloc(matched_patterns
->pattern_list
,
matched_patterns
->list_size
* sizeof(matched_patterns
->pattern_list
[0]));
next_pattern
= &matched_patterns
->pattern_list
[matched_patterns
->counter
];
next_pattern
->move
= AFFINE_TRANSFORM(pattern
->move_offset
, ll
, anchor
);
next_pattern
->value
= pattern
->value
;
next_pattern
->anchor
= anchor
;
next_pattern
->pattern
= pattern
;
next_pattern
->next_pattern_index
= -1;
matched_patterns
->counter
++;
#define MAX_STORED_REASONS 4
valuate_combinable_pattern_chain(struct matched_patterns_list_data
*list
,
/* FIXME: This is just a first attempt at pattern combination.
* Improve it. The first idea is to differentiate between
* move reason types. For instance, when there is a secure
* eye already, a threat to create another is more severe.
* This will certainly involve splitting the function into
* attack and defense versions.
int pattern_index
= list
->first_pattern_index
[pos
];
int num_capture_threats
= 0;
int capture_threats
[MAX_STORED_REASONS
];
int eye_threats
[MAX_STORED_REASONS
];
int num_reverse_sente
= 0;
int reverse_sente_against
[MAX_STORED_REASONS
];
ASSERT1(pattern_index
!= -1, pos
);
struct matched_pattern_data
*pattern_data
= (list
->pattern_list
struct pattern_attribute
*attribute
;
/* Skip patterns that haven't passed constraint validation. */
if (pattern_data
->pattern
) {
for (attribute
= pattern_data
->pattern
->attributes
;
attribute
->type
!= LAST_ATTRIBUTE
;
int target
= AFFINE_TRANSFORM(attribute
->offset
, pattern_data
->ll
,
switch (attribute
->type
) {
case THREATENS_TO_CAPTURE
:
if (num_capture_threats
< MAX_STORED_REASONS
) {
ASSERT1(IS_STONE(board
[target
]), target
);
target
= find_origin(target
);
for (k
= 0; k
< num_capture_threats
; k
++) {
if (capture_threats
[k
] == target
)
if (k
== num_capture_threats
) {
capture_threats
[num_capture_threats
++] = target
;
full_value
+= pattern_data
->pattern
->value
;
if (num_eye_threats
< MAX_STORED_REASONS
) {
target
= current_owl_data
->my_eye
[target
].origin
;
for (k
= 0; k
< num_eye_threats
; k
++) {
if (eye_threats
[k
] == target
)
if (k
== num_eye_threats
) {
eye_threats
[num_eye_threats
++] = target
;
full_value
+= pattern_data
->pattern
->value
;
if (num_reverse_sente
< MAX_STORED_REASONS
) {
ASSERT1(board
[target
] == EMPTY
, target
);
for (k
= 0; k
< num_reverse_sente
; k
++) {
if (reverse_sente_against
[k
] == target
)
if (k
== num_reverse_sente
) {
reverse_sente_against
[num_reverse_sente
++] = target
;
full_value
+= pattern_data
->pattern
->value
;
pattern_index
= pattern_data
->next_pattern_index
;
} while (pattern_index
>= 0);
num_move_reasons
= num_capture_threats
+ num_eye_threats
+ num_reverse_sente
;
if (num_move_reasons
<= 1) {
/* Not much to combine, eh? */
if (num_move_reasons
== 2)
return gg_min(gg_normalize_float2int(full_value
, 1.0), 75);
if (num_move_reasons
== 3)
return gg_min(gg_normalize_float2int(full_value
* 0.85, 1.0), 90);
return gg_min(gg_normalize_float2int(full_value
* 0.75, 1.0), 99);
/* Compute the squared of the distance of a point on the board to the
/* i = 0: idist = - (board_size - 1)
* i = board_size -1 : idist = board_size - 1
int idist
= 2*I(move
) - board_size
+ 1;
int jdist
= 2*J(move
) - board_size
+ 1;
return idist
*idist
+ jdist
*jdist
;
/* NOTICE : In order to stabilize the regression test results,
* arbitrary parameters like pattern memory address and move position
* have been included in the sorting algorithm.
#define BETTER_PATTERN(a, b) \
((a)->value > (b)->value \
|| ((a)->value == (b)->value \
&& ((a)->pattern < (b)->pattern \
|| ((a)->pattern == (b)->pattern \
&& ((a)->bdist < (b)->bdist \
|| ((a)->bdist == (b)->bdist \
&& (a)->move < (b)->move))))))
#else /* not USE_BDIST */
#define BETTER_PATTERN(a, b) \
((a)->value > (b)->value \
|| ((a)->value == (b)->value \
&& ((a)->pattern < (b)->pattern \
|| ((a)->pattern == (b)->pattern \
&& (a)->move < (b)->move))))
#endif /* not USE_BDIST */
pattern_list_prepare(struct matched_patterns_list_data
*list
)
list
->heap_num_patterns
= 0;
/* This is more than needed in case of (combinable) pattern chains,
* but it is easier to allocate more than to count real number of
if (list
->counter
> 0) { /* avoid malloc(0) */
list
->pattern_heap
= malloc(list
->counter
* sizeof(*(list
->pattern_heap
)));
gg_assert(list
->pattern_heap
!= NULL
);
/* free() has defined behaviour for NULL pointer */
list
->pattern_heap
= NULL
;
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
list
->first_pattern_index
[pos
] = -1;
for (k
= 0; k
< list
->counter
; k
++) {
int move
= list
->pattern_list
[k
].move
;
list
->pattern_list
[k
].bdist
= bdist(move
);
/* Allocate heap elements for normal patterns. Link combinable
if (!(list
->pattern_list
[k
].pattern
->class & CLASS_c
))
list
->pattern_heap
[list
->heap_num_patterns
++] = &list
->pattern_list
[k
];
list
->pattern_list
[k
].next_pattern_index
= list
->first_pattern_index
[move
];
list
->first_pattern_index
[move
] = k
;
/* Allocate one heap element for each chain of combinable patterns
* and calculate initial chain values (as if all patterns passed
* constraint validation).
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (list
->first_pattern_index
[pos
] != -1) {
struct matched_pattern_data
*pattern_data
= &list
->pattern_list
[list
->first_pattern_index
[pos
]];
pattern_data
->value
= valuate_combinable_pattern_chain(list
, pos
);
list
->pattern_heap
[list
->heap_num_patterns
++] = pattern_data
;
if (list
->heap_num_patterns
> 0)
pattern_list_build_heap(list
);
/* Fast heap building. Takes O(n) only. */
pattern_list_build_heap(struct matched_patterns_list_data
*list
)
int limit
= list
->heap_num_patterns
/ 2;
for (k
= limit
; --k
>= 0;) {
struct matched_pattern_data
*pattern_data
= list
->pattern_heap
[k
];
for (parent
= k
; parent
< limit
; parent
= child
) {
if (child
+ 1 < list
->heap_num_patterns
&& BETTER_PATTERN(list
->pattern_heap
[child
+ 1],
list
->pattern_heap
[child
]))
if (BETTER_PATTERN(pattern_data
, list
->pattern_heap
[child
]))
list
->pattern_heap
[parent
] = list
->pattern_heap
[child
];
list
->pattern_heap
[parent
] = pattern_data
;
/* Pops patterns list's heap once. */
pattern_list_pop_heap_once(struct matched_patterns_list_data
*list
)
list
->heap_num_patterns
--;
for (parent
= 0; 2 * parent
+ 1 < list
->heap_num_patterns
; parent
= child
) {
if (BETTER_PATTERN(list
->pattern_heap
[child
+ 1],
list
->pattern_heap
[child
]))
if (BETTER_PATTERN(list
->pattern_heap
[list
->heap_num_patterns
],
list
->pattern_heap
[child
]))
list
->pattern_heap
[parent
] = list
->pattern_heap
[child
];
list
->pattern_heap
[parent
] = list
->pattern_heap
[list
->heap_num_patterns
];
/* Sink top element of heap because it got devalued. This happens
* when a combinable pattern doesn't pass check_pattern_hard() -- it
* is no longer counted and its whole chain's value is reduced.
pattern_list_sink_heap_top_element(struct matched_patterns_list_data
*list
)
struct matched_pattern_data
*heap_top_element
= list
->pattern_heap
[0];
for (parent
= 0; 2 * parent
+ 1 < list
->heap_num_patterns
; parent
= child
) {
if (child
+ 1 < list
->heap_num_patterns
&& BETTER_PATTERN(list
->pattern_heap
[child
+ 1],
list
->pattern_heap
[child
]))
if (BETTER_PATTERN(heap_top_element
,
list
->pattern_heap
[child
]))
list
->pattern_heap
[parent
] = list
->pattern_heap
[child
];
list
->pattern_heap
[parent
] = heap_top_element
;
/* Adds all goal strings in the pattern area to the cuts[] list, if there
generate_cut_list(struct pattern
*pattern
, int ll
, int anchor
,
int cuts
[MAX_CUTS
], struct local_owl_data
*owl
)
signed char mark
[BOARDMAX
];
memset(mark
, 0, BOARDMAX
);
for (k
= 0; k
< pattern
->patlen
; k
++) {
int pos
= AFFINE_TRANSFORM(pattern
->patn
[k
].offset
, ll
, anchor
);
if (!IS_STONE(board
[pos
]))
if (!mark
[pos
] && board
[pos
] == owl
->color
&& owl
->goal
[pos
]) {
else if ((debug
& DEBUG_SPLIT_OWL
) && num
> 1)
gprintf("Move provokes %d cuts, among them %1m and %1m.\n", num
,
/* This function searches in the previously stored list of matched
* patterns for the highest valued unused patterns that have a valid
* constraint. It returns the moves at the next empty positions in
* the array moves[]. Empty positions in the moves array are marked
* by having value <= 0. There must be enough empty positions in the
* If the highest valued pattern found has a value less than cutoff,
* no move is returned. Returns 1 if a move is found, 0 otherwise.
* This function also dispatches constraint validation of combinable
* pattern chains. Whenever a pattern from a chain fails constraints,
* the chain is reevaluated and most likely drops in value enough to
* let other patterns (or chains) climb to the top of pattern heap.
* This function loops until enough moves are found or the end of the
get_next_move_from_list(struct matched_patterns_list_data
*list
, int color
,
struct owl_move_data
*moves
, int cutoff
,
struct local_owl_data
*owl
)
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
/* Prepare pattern list if needed. */
pattern_list_prepare(list
);
while (list
->heap_num_patterns
> 0) {
struct matched_pattern_data
*pattern_data
;
/* Peek top element of heap associated with pattern list. */
if (list
->pattern_heap
[0]->value
< cutoff
)
pattern_data
= list
->pattern_heap
[0];
pattern
= list
->pattern_heap
[0]->pattern
;
move
= list
->pattern_heap
[0]->move
;
value
= list
->pattern_heap
[0]->value
;
ll
= list
->pattern_heap
[0]->ll
;
anchor
= list
->pattern_heap
[0]->anchor
;
next_pattern_index
= list
->pattern_heap
[0]->next_pattern_index
;
for (k
= 0; k
< MAX_MOVES
; k
++) {
if (moves
[k
].pos
== move
|| moves
[k
].value
<= 0)
if (moves
[k
].pos
== move
) {
/* No point in testing this pattern/chain. Throw it out. */
pattern_list_pop_heap_once(list
);
/* There has to be an empty space. */
gg_assert(k
< MAX_MOVES
);
/* If a pattern chain was devalued because its last pattern didn't
* pass constraint validation, `pattern' is set NULL (i.e. nothing
* more to test). Note that devalued chains might still be
* useful, i.e. if 2 of 3 patterns passed check_pattern_hard().
|| check_pattern_hard(move
, color
, pattern
, ll
)) {
if (next_pattern_index
== -1) {
/* Normal pattern or last one in a chain. */
pattern_list_pop_heap_once(list
);
/* We just validated a non-last pattern in a chain. Since the
* chain remains at the same value, we keep the heap structure
* untouched. However, we need to set heap's top to point to
* next pattern of the chain.
list
->pattern_heap
[0] = list
->pattern_list
+ next_pattern_index
;
list
->pattern_heap
[0]->value
= value
;
clear_cut_list(moves
[k
].cuts
);
if (pattern
&& !(pattern
->class & CLASS_c
)) {
moves
[k
].name
= pattern
->name
;
TRACE("Pattern %s found at %1m with value %d\n",
pattern
->name
, move
, moves
[k
].value
);
if (pattern
->class & CLASS_C
) {
/* Cut possible. (Only used in attack patterns). Try to find
* goal strings in the pattern area and store them in the cut list
* if there is more than one.
"Generating cut list for move at %1m.\n", move
);
generate_cut_list(pattern
, ll
, anchor
, moves
[k
].cuts
, owl
);
if (pattern
->class & CLASS_B
)
moves
[k
].same_dragon
= SAME_DRAGON_NOT_CONNECTED
;
else if (pattern
->class & CLASS_a
) {
moves
[k
].same_dragon
= SAME_DRAGON_ALL_CONNECTED
;
moves
[k
].pattern_data
= pattern_data
;
else if (!(pattern
->class & CLASS_b
))
moves
[k
].same_dragon
= SAME_DRAGON_CONNECTED
;
enum same_dragon_value same_dragon
= SAME_DRAGON_MAYBE_CONNECTED
;
/* If we do not yet know whether the move belongs to the
* same dragon, we see whether another pattern can clarify.
for (i
= 0; i
< list
->heap_num_patterns
; i
++) {
pattern_data
= list
->pattern_heap
[i
];
if (pattern_data
->pattern
&& pattern_data
->move
== move
&& ((pattern_data
->pattern
->class & CLASS_B
)
|| !(pattern_data
->pattern
->class & CLASS_b
))) {
if (check_pattern_hard(move
, color
, pattern_data
->pattern
,
TRACE("Additionally pattern %s found at %1m\n",
pattern_data
->pattern
->name
, move
);
if (pattern_data
->pattern
->class & CLASS_B
)
same_dragon
= SAME_DRAGON_NOT_CONNECTED
;
else if (pattern_data
->pattern
->class & CLASS_a
) {
same_dragon
= SAME_DRAGON_ALL_CONNECTED
;
moves
[k
].pattern_data
= pattern_data
;
same_dragon
= SAME_DRAGON_CONNECTED
;
moves
[k
].same_dragon
= same_dragon
;
moves
[k
].name
= "Pattern combination";
/* FIXME: write names of all patterns in chain. */
/* FIXME: Add handling of CLASS_b.
* FIXME: It is silently assumed that all patterns in the
* chain have the same class. When the last pattern in
* chain didn't match, this will not work at all.
if (pattern
&& pattern
->class & CLASS_B
)
moves
[k
].same_dragon
= SAME_DRAGON_NOT_CONNECTED
;
else if (pattern
&& pattern
->class & CLASS_a
) {
moves
[k
].same_dragon
= SAME_DRAGON_ALL_CONNECTED
;
moves
[k
].pattern_data
= list
->pattern_heap
[0];
moves
[k
].same_dragon
= SAME_DRAGON_CONNECTED
;
if (pattern
&& pattern
->class & CLASS_E
)
else { /* !check_pattern_hard(...) */
if (!(pattern
->class & CLASS_c
)) {
/* Just forget about it. */
pattern_list_pop_heap_once(list
);
/* Set this pattern to not matched and advance to next one in
list
->pattern_heap
[0]->pattern
= NULL
;
if (next_pattern_index
!= -1)
list
->pattern_heap
[0] = list
->pattern_list
+ next_pattern_index
;
/* Reevaluate chain and adjust heap structure accordingly. */
list
->pattern_heap
[0]->value
= valuate_combinable_pattern_chain(list
,
pattern_list_sink_heap_top_element(list
);
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* This function takes an array of already found moves (passed as
* 'data') and looks for moves to replace these. Only moves near
* the goal dragon are considered.
owl_shapes_callback(int anchor
, int color
, struct pattern
*pattern
,
int tval
; /* trial move and its value */
struct owl_move_data
*moves
= data
; /* considered moves passed as data */
enum same_dragon_value same_dragon
= SAME_DRAGON_MAYBE_CONNECTED
;
/* Pick up the location of the move */
move
= AFFINE_TRANSFORM(pattern
->move_offset
, ll
, anchor
);
/* Before we do any expensive reading, check whether this move
* already is known with a higher value or if there are too many
* other moves with higher value.
for (k
= 0; k
< MAX_MOVES
; k
++) {
if (moves
[k
].value
== -1)
if (moves
[k
].pos
== move
) {
if (moves
[k
].value
>= pattern
->value
)
if (k
== MAX_MOVES
&& moves
[MAX_MOVES
- 1].value
>= pattern
->value
)
if (!check_pattern_hard(move
, color
, pattern
, ll
))
/* and work out the value of this move */
/* ask helper function to consider the move */
DEBUG(DEBUG_HELPER
, " asking helper to consider '%s'+%d at %1m\n",
pattern
->name
, ll
, move
);
tval
= pattern
->helper(pattern
, ll
, move
, color
);
DEBUG(DEBUG_HELPER
, "helper likes pattern '%s' value %d at %1m\n",
pattern
->name
, tval
, move
);
DEBUG(DEBUG_HELPER
, " helper does not like pattern '%s' at %1m\n",
return; /* pattern matcher does not like it */
tval
= (int) pattern
->value
;
/* having made it here, we have made it through all the extra checks */
TRACE("Pattern %s found at %1m with value %d\n", pattern
->name
, move
, tval
);
if (pattern
->class & CLASS_B
)
same_dragon
= SAME_DRAGON_NOT_CONNECTED
;
else if (pattern
->class & CLASS_b
)
same_dragon
= SAME_DRAGON_MAYBE_CONNECTED
;
else if (pattern
->class & CLASS_a
) {
same_dragon
= SAME_DRAGON_ALL_CONNECTED
;
/* FIXME: Currently this code is only used with vital attack
* moves, so there is no use for the "a" classification. If it
* would be needed in the future it's necessary to set up a struct
* matched_pattern_data here to be passed to owl_add_move(). This
* is not all that simple with respect to memory management
* however. Notice that a local variable in this function would go
* out of scope too early.
same_dragon
= SAME_DRAGON_CONNECTED
;
if (pattern
->class & CLASS_E
)
/* Finally, check for position of defense move. */
for (k
= 0; k
< pattern
->patlen
; k
++)
if (pattern
->patn
[k
].att
== ATT_not
)
defense_pos
= AFFINE_TRANSFORM(pattern
->patn
[k
].offset
, ll
, anchor
);
owl_add_move(moves
, move
, tval
, pattern
->name
, same_dragon
, NO_MOVE
,
escape
, defense_pos
, MAX_MOVES
, NULL
);
/* Add a move to the list of candidate moves */
owl_add_move(struct owl_move_data
*moves
, int move
, int value
,
const char *reason
, enum same_dragon_value same_dragon
, int lunch
,
int escape
, int defense_pos
, int max_moves
,
struct matched_pattern_data
*pattern_data
)
if (!found_matches
[move
]) {
/* Add the new move to the list of already found moves, if the value
* is sufficently large. We keep the list sorted.
* First we must see if this move already is in the list.
for (k
= 0; k
< max_moves
; k
++) {
if (moves
[k
].value
== -1)
if (moves
[k
].pos
== move
) {
if (same_dragon
> moves
[k
].same_dragon
) {
moves
[k
].same_dragon
= same_dragon
;
moves
[k
].pattern_data
= pattern_data
;
/* Did we already have this move in the list with a higher value? */
if (k
< max_moves
&& moves
[k
].value
>= value
)
/* Insert the move at the right place in the list and adjust other
if (k
== 0 || value
<= moves
[k
-1].value
) {
/* Can't get higher. Insert the move below this point and quit
/* If B or b class pattern, this move shouldn't be added to the
* dragon under consideration.
moves
[k
].same_dragon
= same_dragon
;
moves
[k
].pattern_data
= pattern_data
;
moves
[k
].escape
= escape
;
moves
[k
].defense_pos
= defense_pos
;
/* Shuffle the passed move one step downwards. */
moves
[k
] = moves
[k
-1]; /* struct copy */
/* Assert that the list contains unique moves. */
for (k
= 0; k
< max_moves
; k
++)
for (l
= k
+1; l
< max_moves
; l
++)
gg_assert(moves
[k
].pos
== 0
|| moves
[k
].pos
!= moves
[l
].pos
);
/* Marks the dragons at apos and bpos. If only one dragon
* needs marking, bpos should be passed as NO_MOVE.
owl_mark_dragon(int apos
, int bpos
, struct local_owl_data
*owl
,
int new_dragons
[BOARDMAX
])
ASSERT1(bpos
== NO_MOVE
|| board
[bpos
] == color
, bpos
);
if (new_dragons
== NULL
) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (is_same_dragon(pos
, apos
) || is_same_dragon(pos
, bpos
))
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
&& (new_dragons
[pos
] == new_dragons
[apos
]
|| new_dragons
[pos
] == new_dragons
[bpos
]))
memcpy(owl
->cumulative_goal
, owl
->goal
, sizeof(owl
->goal
));
/* Marks the worms at apos and bpos. If only one worm
* needs marking, bpos should be passed as NO_MOVE.
owl_mark_worm(int apos
, int bpos
, struct local_owl_data
*owl
)
ASSERT1(bpos
== NO_MOVE
|| board
[bpos
] == color
, bpos
);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (is_same_worm(pos
, apos
) || is_same_worm(pos
, bpos
))
/* Mark the boundary strings of the dragon. A boundary string is marked 2
* if it adjoins a friendly live dragon, 1 otherwise.
owl_mark_boundary(struct local_owl_data
*owl
)
int other
= OTHER_COLOR(color
);
memset(owl
->boundary
, 0, sizeof(owl
->boundary
));
memset(owl
->neighbors
, 0, sizeof(owl
->neighbors
));
/* Find all friendly neighbors of the dragon in goal. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] == color
&& owl
->goal
[pos
]) {
for (k
= 0; k
< 4; k
++) {
if (board
[pos
+ delta
[k
]] == EMPTY
&& board
[pos
+ 2 * delta
[k
]] == color
&& !owl
->neighbors
[pos
+ 2 * delta
[k
]])
mark_string(pos
+ 2 * delta
[k
], owl
->neighbors
, 1);
int pos2
= pos
+ delta
[k
];
&& (board
[SOUTH(gg_min(pos
, pos2
))] == EMPTY
|| board
[NORTH(gg_max(pos
, pos2
))] == EMPTY
))
mark_string(pos2
, owl
->neighbors
, 1);
/* First find all boundary strings (including those adjacent not to
* the goal dragon, but one of its neighbors).
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (board
[pos
] == other
&& !owl
->boundary
[pos
]) {
if (ON_BOARD(pos
+ delta
[k
])
&& (owl
->goal
[pos
+ delta
[k
]] || owl
->neighbors
[pos
+ delta
[k
]])) {
mark_string(pos
, owl
->boundary
, 1);
/* Upgrade the mark of a boundary string if it adjoins a safe
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (owl
->boundary
[pos
] == 1) {
for (k
= 0; k
< 8; k
++) {
int pos2
= pos
+ delta
[k
];
&& ((dragon
[pos2
].crude_status
!= DEAD
&& countstones(pos2
) > 2)
|| dragon
[pos2
].crude_status
== ALIVE
)) {
mark_string(pos
, owl
->boundary
, 2);
/* During the owl reading, stones farther away may become parts of
* the boundary. We mark those strings neighboring some other
* friendly dragon with boundary value 2 right away, since we have
* no mechanism for detecting this later.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (board
[pos
] == other
&& owl
->boundary
[pos
] == 0) {
/* If a lunch has been amalgamated into a larger dragon, we
* Notice that we assume that no stone of the attacking color
* has been placed on the board with trymove() when this
* function is called. Thus we can (mostly) trust the worm data for
if (worm
[pos
].attack_codes
[0] != 0
&& worm
[pos
].size
!= dragon
[pos
].size
)
/* This can happen if called when stackp > 0 */
if (dragon
[pos
].id
== -1)
for (k
= 0; k
< DRAGON2(pos
).neighbors
; k
++) {
int d
= DRAGON2(pos
).adjacent
[k
];
int apos
= dragon2
[d
].origin
;
if (board
[apos
] == color
&& !owl
->goal
[apos
]) {
/* Add the stone just played to the goal dragon if same_dragon is
* SAME_DRAGON_CONNECTED. We also add all stones belonging to the same
* generalized string to the goal. If same_dragon is
* SAME_DRAGON_MAYBE_CONNECTED, we only add the stones if at least one
* stone of the generalized string already was part of the goal. If
* same_dragon is SAME_DRAGON_NOT_CONNECTED, we don't add any stones
* The SAME_DRAGON_ALL_CONNECTED case is like SAME_DRAGON_CONNECTED
* but additionally all other own stones in the pattern suggesting the
* move are also added to the goal.
owl_update_goal(int pos
, enum same_dragon_value same_dragon
, int lunch
,
struct local_owl_data
*owl
, int semeai_call
,
struct matched_pattern_data
*pattern_data
)
int stones
[MAX_BOARD
* MAX_BOARD
];
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
/* Turn off sgf output during find_superstring(). */
if (same_dragon
== SAME_DRAGON_NOT_CONNECTED
)
num_stones
= findstones(pos
, MAX_BOARD
* MAX_BOARD
, stones
);
find_superstring_conservative(pos
, &num_stones
, stones
);
find_superstring(pos
, &num_stones
, stones
);
/* Turn sgf output back on. */
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* If same_dragon field is 1, only add if the played stone
* clearly is in contact with the goal dragon.
if (same_dragon
<= SAME_DRAGON_MAYBE_CONNECTED
) {
for (k
= 0; k
< num_stones
; k
++)
if (owl
->goal
[stones
[k
]] != 0) {
for (k
= 0; k
< num_stones
; k
++) {
if (owl
->goal
[stones
[k
]] == 0) {
TRACE("Added %1m to goal.\n", stones
[k
]);
owl
->goal
[stones
[k
]] = 2;
owl
->cumulative_goal
[stones
[k
]] = 1;
/* If this move captures a lunch, we add all it's direct neighbours to the
if (!semeai_call
&& lunch
!= NO_MOVE
&& board
[lunch
] != EMPTY
) {
adj
= chainlinks(lunch
, adjs
);
for (k
= 0; k
< adj
; k
++)
if (!owl
->goal
[adjs
[k
]]) {
mark_string(adjs
[k
], owl
->goal
, 2);
mark_string(adjs
[k
], owl
->cumulative_goal
, 2);
/* Now we handle the SAME_DRAGON_ALL_CONNECTED case. The move has
* already been added to the goal above, so it remains to find all
* other friendly stones in the pattern and add them too. We do that
* by a recursive call to this function in SAME_DRAGON_CONNECTED mode.
* This is maybe not the most elegant technique, however.
if (same_dragon
== SAME_DRAGON_ALL_CONNECTED
) {
gg_assert(pattern_data
!= NULL
);
for (k
= 0; k
< pattern_data
->pattern
->patlen
; k
++) {
/* all the following stuff (currently) applies only at occupied cells */
if (pattern_data
->pattern
->patn
[k
].att
!= ATT_O
)
/* transform pattern real coordinate */
pos2
= AFFINE_TRANSFORM(pattern_data
->pattern
->patn
[k
].offset
,
pattern_data
->ll
, pattern_data
->anchor
);
owl_update_goal(pos2
, SAME_DRAGON_CONNECTED
, NO_MOVE
, owl
, semeai_call
,
/* Computes the connected components of a the graph that is given by
* having graph[i][j] = 1 if i and j are connected, and that has size
* This function is generic, but without having the fixed MAX_CUTS
* array size it is ugly to write in ANSI C89 (no variably sized arrays),
* so we leave it here for now.
connected_components(signed char graph
[MAX_CUTS
][MAX_CUTS
], int graph_size
,
signed char component
[MAX_CUTS
])
memset(component
, -1, MAX_CUTS
);
/* Find unidentified string. */
for (k
= 0; k
< graph_size
; k
++)
break; /* All are identified. */
component
[k
] = num_components
; /* Start new component. */
do { /* Spread new component. */
for (j
= k
+1; j
< graph_size
; j
++)
if (graph
[k
][j
] && component
[j
] == -1) {
component
[j
] = num_components
;
gg_assert(num_components
> 0);
/* This functions gets called after a move has been made that threatens
* to cut the owl goal dragon. It cuts the goal if necessary, and sets it
* to the biggest remaining component.
owl_test_cuts(signed char goal
[BOARDMAX
], int color
, int cuts
[MAX_CUTS
])
signed char connected
[MAX_CUTS
][MAX_CUTS
];
/* int connect_move[MAX_CUTS][MAX_CUTS]; */
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
memset(connected
, 1, MAX_CUTS
*MAX_CUTS
);
if (debug
& DEBUG_SPLIT_OWL
) {
gprintf("Called for this goal: ");
gprintf("At this position:\n");
/* Delete captured strings from list. */
for (k
= 0; k
< MAX_CUTS
; k
++) {
if (board
[cuts
[k
]] == EMPTY
) {
for (j
= k
+ 1; j
< MAX_CUTS
; j
++) {
/* Test for each pair of strings in cuts[] whether it can now be
for (k
= 0; k
< num_cuts
; k
++) {
ASSERT1(board
[cuts
[k
]] == color
, cuts
[k
]);
for (j
= k
+ 1; j
< num_cuts
; j
++)
if (fast_disconnect(cuts
[k
], cuts
[j
], NULL
) == WIN
) {
signed char component
[MAX_CUTS
];
signed char component2
[BOARDMAX
];
int component_size
[MAX_CUTS
];
int biggest_component
= -1;
struct connection_data
*conn_data
;
/* Start by computing the connected components among the strings
num_components
= connected_components(connected
, num_cuts
, component
);
if (num_components
<= 1) {
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* Now break up the goal by associating each goal stone to one of
* the connected components.
* First we compute the connection distances from each of the
* partial goals we have found.
memset(component2
, -1, BOARDMAX
);
memset(component_size
, 0, sizeof(int) * num_components
);
conn_data
= malloc(sizeof(struct connection_data
) * num_components
);
for (c_id
= 0; c_id
< num_components
; c_id
++) {
signed char this_goal
[BOARDMAX
];
memset(this_goal
, 0, BOARDMAX
);
for (k
= 0; k
< num_cuts
; k
++)
if (component
[k
] == c_id
) {
mark_string(cuts
[k
], this_goal
, 1);
mark_string(cuts
[k
], component2
, (signed char) c_id
);
init_connection_data(color
, this_goal
, NO_MOVE
, FP(3.01),
spread_connection_distances(color
, conn_data
+ c_id
);
/* Now put each goal string to the component to which it has the
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
int closest_dist
= HUGE_CONNECTION_DISTANCE
;
int closest_component
= -1;
if (board
[pos
] != color
|| !goal
[pos
])
if (pos
!= find_origin(pos
))
for (c_id
= 0; c_id
< num_components
; c_id
++) {
if (conn_data
[c_id
].distances
[pos
] < closest_dist
) {
closest_dist
= conn_data
[c_id
].distances
[pos
];
closest_component
= c_id
;
/* FIXME: What to do if no close component found? */
if (closest_component
!= -1) {
mark_string(pos
, component2
, (signed char) closest_component
);
component_size
[closest_component
] += countstones(pos
);
/* Now find the biggest_component. */
for (c_id
= 0; c_id
< num_components
; c_id
++)
if (component_size
[c_id
] > biggest_size
) {
biggest_size
= component_size
[c_id
];
biggest_component
= c_id
;
gg_assert(biggest_component
!= -1);
/* Now delete everything except the biggest component from the goal. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (component2
[pos
] != biggest_component
)
if (debug
& DEBUG_SPLIT_OWL
) {
gprintf("Split dragon. Biggest component is %d (of %d).\n",
biggest_component
, num_components
);
componentdump(component2
);
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* We update the boundary marks. The boundary mark must be
* constant on each string. It is nonzero if the string
* adjoins the goal dragon, or if the string includes a
* stone played in the course of analysis. If the string
* adjoins a live friendly dragon, the boundary mark is 2.
owl_update_boundary_marks(int pos
, struct local_owl_data
*owl
)
signed char boundary_mark
= 0;
for (k
= 0; k
< 4; k
++) {
int pos2
= pos
+ delta
[k
];
if (ON_BOARD(pos2
) && owl
->boundary
[pos2
] > boundary_mark
)
boundary_mark
= owl
->boundary
[pos2
];
if (board
[pos2
] == owl
->color
&& dragon
[pos2
].color
== owl
->color
&& dragon
[pos2
].status
== ALIVE
&& !owl
->neighbors
[pos2
])
mark_string(pos
, owl
->boundary
, boundary_mark
);
/* Lists the goal array. For use in GDB:
* (gdb) set goaldump(goal).
goaldump(const signed char goal
[BOARDMAX
])
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (ON_BOARD(pos
) && goal
[pos
])
gprintf("%o%1m (%d) ", pos
, (int) goal
[pos
]);
componentdump(const signed char component
[BOARDMAX
])
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (ON_BOARD(pos
) && component
[pos
] != -1)
gprintf("%o%1m (%d) ", pos
, (int) component
[pos
]);
* Owl attack moves are ineffective when the dragon can still live in a
* semeai. This function tests whether an owl attack move has this problem.
* If not, an owl attack move reason is added, otherwise we treat the
* move as a strategic attack.
test_owl_attack_move(int pos
, int dr
, int kworm
, int acode
)
int color
= OTHER_COLOR(board
[dr
]);
if (DRAGON2(dr
).semeais
== 0
|| DRAGON2(dr
).semeai_defense_point
== NO_MOVE
|| (DRAGON2(dr
).semeais
== 1 && semeai_move_reason_known(pos
, dr
))
add_owl_attack_move(pos
, dr
, kworm
, acode
);
DEBUG(DEBUG_OWL
, "owl: %1m attacks %1m (%s) at move %d\n",
pos
, dr
, result_to_string(DRAGON2(dr
).owl_attack_code
),
int dr2
= DRAGON2(dr
).semeai_defense_target
;
int semeai_result
, certain
;
int save_verbose
= verbose
;
owl_analyze_semeai_after_move(pos
, color
, dr
, dr2
, &semeai_result
,
NULL
, NULL
, 1, &certain
, 0);
if (certain
>= DRAGON2(dr
).semeai_defense_certain
&& (semeai_result
>= REVERSE_RESULT(acode
))) {
/* Demote the move reasons. */
DEBUG(DEBUG_OWL
, "owl: %1m ineffective owl attack on %1m (can live in semeai with %1m)\n", pos
, dr
, dr2
);
add_strategical_attack_move(pos
, dr
);
add_owl_attack_move(pos
, dr
, kworm
, acode
);
DEBUG(DEBUG_OWL
, "owl: %1m attacks %1m (%s) at move %d\n",
pos
, dr
, result_to_string(DRAGON2(dr
).owl_attack_code
),
/* Add owl move reasons. This function should be called once during
* genmove. It has to be called after semeai_move_reasons().
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!IS_STONE(board
[pos
])
|| dragon
[pos
].origin
!= pos
)
if (dragon
[pos
].status
== CRITICAL
&& DRAGON2(pos
).owl_attack_point
!= NO_MOVE
) {
if (board
[pos
] == color
) {
if (DRAGON2(pos
).owl_defense_point
!= NO_MOVE
) {
if (DRAGON2(pos
).owl_defense_code
== LOSS
) {
add_loss_move(DRAGON2(pos
).owl_defense_point
, pos
,
DRAGON2(pos
).owl_defense_kworm
);
DEBUG(DEBUG_OWL
, "owl: %1m defends %1m with loss at move %d\n",
DRAGON2(pos
).owl_defense_point
, pos
, movenum
+1);
add_owl_defense_move(DRAGON2(pos
).owl_defense_point
, pos
,
DRAGON2(pos
).owl_defense_code
);
DEBUG(DEBUG_OWL
, "owl: %1m defends %1m at move %d\n",
DRAGON2(pos
).owl_defense_point
, pos
, movenum
+1);
else { /* opponent's dragon */
/* We don't want to add this move reason if the attacker
* dies because the victim only formed a nakade shape.
* FIXME: This code overlaps heavily with some code in
* examine_move_safety() in move_reasons.c. The caching
* scheme should minimize the performance hit, but of course
* it's unfortunate to have the code duplication.
int move
= DRAGON2(pos
).owl_attack_point
;
/* No worries if we catch something big. */
if (dragon
[pos
].effective_size
< 8) {
/* Look through the neighbors of the victim for dragons of
* our color. If we find at least one being thought alive
* everything is ok. Otherwise we keep track of the
* largest one for further examination.
for (k
= 0; k
< DRAGON2(pos
).neighbors
; k
++) {
int d
= DRAGON2(pos
).adjacent
[k
];
if (DRAGON(d
).color
== color
) {
if (DRAGON(d
).status
== ALIVE
) {
if (DRAGON(d
).size
> largest
) {
bpos
= dragon2
[d
].origin
;
largest
= DRAGON(d
).size
;
/* It may occasionally happen that no neighbor of our
* color was found. Assume safe in that case.
/* If not yet thought safe, ask the owl code whether the
* owl attack defends the (largest) attacker.
if (!safe
&& owl_does_defend(move
, bpos
, &kworm
) != WIN
) {
"owl: %1m attacks %1m at move %d, but the attacker dies.\n",
DRAGON2(pos
).safety
= INESSENTIAL
;
/* If we've reached this far, it only remains to check the move
* against semeai complications. */
test_owl_attack_move(move
, pos
, DRAGON2(pos
).owl_attack_kworm
,
DRAGON2(pos
).owl_attack_code
);
else if (DRAGON2(pos
).owl_status
== DEAD
&& DRAGON2(pos
).owl_threat_status
== CAN_THREATEN_DEFENSE
) {
&& DRAGON2(pos
).owl_defense_point
!= NO_MOVE
) {
add_owl_defense_threat_move(DRAGON2(pos
).owl_defense_point
, pos
, WIN
);
DEBUG(DEBUG_OWL
, "owl: %1m threatens to defend %1m at move %d\n",
DRAGON2(pos
).owl_defense_point
, pos
, movenum
+1);
&& DRAGON2(pos
).owl_second_defense_point
!= NO_MOVE
&& is_legal(DRAGON2(pos
).owl_second_defense_point
, color
)) {
add_owl_defense_threat_move(DRAGON2(pos
).owl_second_defense_point
,
DEBUG(DEBUG_OWL
, "owl: %1m threatens to defend %1m at move %d\n",
DRAGON2(pos
).owl_second_defense_point
, pos
, movenum
+1);
/* If the opponent can threaten to live, an attacking
* move gets a small value to make sure it's really dead.
if (board
[pos
] == OTHER_COLOR(color
)
&& DRAGON2(pos
).owl_threat_status
== CAN_THREATEN_DEFENSE
&& DRAGON2(pos
).owl_attack_point
!= NO_MOVE
) {
add_owl_prevent_threat_move(DRAGON2(pos
).owl_attack_point
, pos
);
DEBUG(DEBUG_OWL
, "owl: %1m prevents a threat against %1m at move %d\n",
DRAGON2(pos
).owl_attack_point
, pos
, movenum
+1);
else if (DRAGON2(pos
).owl_status
== ALIVE
) {
if (board
[pos
] == OTHER_COLOR(color
)
&& DRAGON2(pos
).owl_threat_status
== CAN_THREATEN_ATTACK
) {
if (DRAGON2(pos
).owl_attack_point
!= NO_MOVE
) {
add_owl_attack_threat_move(DRAGON2(pos
).owl_attack_point
, pos
, WIN
);
DEBUG(DEBUG_OWL
, "owl: %1m threatens %1m at move %d\n",
DRAGON2(pos
).owl_attack_point
, pos
, movenum
+1);
if (DRAGON2(pos
).owl_second_attack_point
!= NO_MOVE
&& is_legal(DRAGON2(pos
).owl_second_attack_point
, color
)) {
add_owl_attack_threat_move(DRAGON2(pos
).owl_second_attack_point
, pos
,
DEBUG(DEBUG_OWL
, "owl: %1m threatens %1m at move %d\n",
DRAGON2(pos
).owl_second_attack_point
, pos
, movenum
+1);
else if (board
[pos
] == OTHER_COLOR(color
)
&& DRAGON2(pos
).owl_attack_point
!= NO_MOVE
&& DRAGON2(pos
).owl_attack_code
== GAIN
) {
add_owl_attack_move(DRAGON2(pos
).owl_attack_point
, pos
,
DRAGON2(pos
).owl_attack_kworm
, GAIN
);
DEBUG(DEBUG_OWL
, "owl: %1m attacks %1m with gain at move %d\n",
DRAGON2(pos
).owl_attack_point
, pos
, movenum
+1);
else if (board
[pos
] == color
&& DRAGON2(pos
).owl_defense_point
!= NO_MOVE
&& DRAGON2(pos
).owl_defense_code
== LOSS
) {
add_loss_move(DRAGON2(pos
).owl_defense_point
, pos
,
DRAGON2(pos
).owl_defense_kworm
);
DEBUG(DEBUG_OWL
, "owl: %1m defends %1m with loss at move %d\n",
DRAGON2(pos
).owl_defense_point
, pos
, movenum
+1);
else if (board
[pos
] == color
&& DRAGON2(pos
).owl_attack_point
!= NO_MOVE
&& DRAGON2(pos
).owl_attack_code
== GAIN
&& DRAGON2(pos
).owl_defense_code
== WIN
&& DRAGON2(pos
).owl_defense_point
!= NO_MOVE
) {
add_owl_defense_move(DRAGON2(pos
).owl_defense_point
, pos
,
DRAGON2(pos
).owl_defense_code
);
DEBUG(DEBUG_OWL
, "owl: %1m defends %1m against possible loss at move %d\n",
DRAGON2(pos
).owl_defense_point
, pos
, movenum
+1);
/* The owl code found the friendly dragon alive, but was uncertain,
* and an extra point of defense was found, so this might
* be a good place to play.
else if (board
[pos
] == color
&& !DRAGON2(pos
).owl_attack_certain
&& DRAGON2(pos
).owl_defense_certain
&& ON_BOARD(DRAGON2(pos
).owl_defense_point
)) {
add_owl_uncertain_defense_move(DRAGON2(pos
).owl_defense_point
, pos
);
"owl: %1m defends the uncertain dragon at %1m at move %d\n",
DRAGON2(pos
).owl_defense_point
, pos
, movenum
+1);
/* The owl code found the dragon dead, but was uncertain,
* and an extra point of attack was found, so this might
* be a good place to play.
else if (DRAGON2(pos
).owl_status
== DEAD
&& board
[pos
] == OTHER_COLOR(color
)
&& !DRAGON2(pos
).owl_attack_certain
&& ON_BOARD(DRAGON2(pos
).owl_attack_point
)) {
add_owl_uncertain_defense_move(DRAGON2(pos
).owl_attack_point
, pos
);
"owl: %1m might defend the uncertain dragon at %1m at move %d\n",
DRAGON2(pos
).owl_attack_point
, pos
, movenum
+1);
/* Use the owl code to determine whether the move at (move) makes
* the dragon at (target) owl safe. This is used to test whether
* tactical defenses are strategically viable and whether a vital eye
* point does kill an owl critical dragon.
* Should be called only when stackp==0.
owl_does_defend(int move
, int target
, int *kworm
)
int color
= board
[target
];
struct local_owl_data
*owl
;
int reading_nodes_when_called
= get_reading_node_counter();
int wid
= MAX_GOAL_WORMS
;
if (debug
& DEBUG_OWL_PERFORMANCE
)
if (worm
[target
].unconditional_status
== DEAD
)
origin
= dragon
[target
].origin
;
TRACE("owl_does_defend %1m %1m(%1m)\n", move
, target
, origin
);
if (search_persistent_owl_cache(OWL_DOES_DEFEND
, move
, target
, 0,
&result
, kworm
, NULL
, NULL
))
if (trymove(move
, color
, "owl_does_defend", target
)) {
/* Check if a compatible owl_attack() is cached. */
if (search_persistent_owl_cache(OWL_ATTACK
, origin
, 0, 0,
&result
, NULL
, kworm
, NULL
)) {
return REVERSE_RESULT(result
);
* FIXME: (move) will be added to the goal dragon although we
* do not know whether it is really connected.
init_owl(&owl
, target
, NO_MOVE
, move
, 1, NULL
);
prepare_goal_list(target
, owl
, owl_goal_worm
, &goal_worms_computed
,
acode
= do_owl_attack(target
, NULL
, &wid
, owl
, 0);
finish_goal_list(&goal_worms_computed
, &wpos
, owl_goal_worm
, wid
);
result
= REVERSE_RESULT(acode
);
return 0; /* Don't cache anything in this case. */
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
DEBUG(DEBUG_OWL_PERFORMANCE
,
"owl_does_defend %1m %1m(%1m), result %d (%d, %d nodes, %f seconds)\n",
move
, target
, origin
, result
, local_owl_node_counter
,
tactical_nodes
, gg_cputime() - start
);
store_persistent_owl_cache(OWL_DOES_DEFEND
, move
, target
, 0,
tactical_nodes
, owl
->goal
, board
[target
]);
/* Use the owl code to determine whether the dragon at (target) is owl
* safe after an own move at (move). This is used to detect
* blunders. In case the dragon is not safe, it also tries to find a
* defense point making (target) safe in a later move.
* Should be called only when stackp==0.
owl_confirm_safety(int move
, int target
, int *defense_point
, int *kworm
)
int color
= board
[target
];
struct local_owl_data
*owl
;
int reading_nodes_when_called
= get_reading_node_counter();
int wid
= MAX_GOAL_WORMS
;
if (debug
& DEBUG_OWL_PERFORMANCE
)
if (worm
[target
].unconditional_status
== DEAD
)
origin
= dragon
[target
].origin
;
TRACE("owl_confirm_safety %1m %1m(%1m)\n", move
, target
, origin
);
if (search_persistent_owl_cache(OWL_CONFIRM_SAFETY
, move
, target
, 0,
&result
, defense_point
, kworm
, NULL
))
if (trymove(move
, color
, "owl_confirm_safety", target
)) {
/* Check if a compatible owl_attack() is cached. */
if (search_persistent_owl_cache(OWL_ATTACK
, origin
, 0, 0,
&result
, defense_point
, kworm
, NULL
)) {
init_owl(&owl
, target
, NO_MOVE
, move
, 1, NULL
);
prepare_goal_list(target
, owl
, owl_goal_worm
, &goal_worms_computed
,
acode
= do_owl_attack(target
, &defense
, &wid
, owl
, 0);
finish_goal_list(&goal_worms_computed
, &wpos
, owl_goal_worm
, wid
);
return 0; /* Don't cache anything in this case. */
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
DEBUG(DEBUG_OWL_PERFORMANCE
,
"owl_confirm_safety %1m %1m(%1m), result %d %1m (%d, %d nodes, %f seconds)\n",
move
, target
, origin
, result
, defense
,
local_owl_node_counter
, tactical_nodes
,
store_persistent_owl_cache(OWL_CONFIRM_SAFETY
, move
, target
, 0,
result
, defense
, wpos
, 0,
tactical_nodes
, owl
->goal
, board
[target
]);
*defense_point
= defense
;
/* Use the owl code to determine whether the attack move at (move) of
* the dragon (target) is effective, i.e. whether it kills the stones.
* Should be called only when stackp==0.
owl_does_attack(int move
, int target
, int *kworm
)
int color
= board
[target
];
int other
= OTHER_COLOR(color
);
struct local_owl_data
*owl
;
int reading_nodes_when_called
= get_reading_node_counter();
int wid
= MAX_GOAL_WORMS
;
if (debug
& DEBUG_OWL_PERFORMANCE
)
if (worm
[target
].unconditional_status
== ALIVE
)
origin
= dragon
[target
].origin
;
TRACE("owl_does_attack %1m %1m(%1m)\n", move
, target
, origin
);
if (search_persistent_owl_cache(OWL_DOES_ATTACK
, move
, target
, 0,
&result
, kworm
, NULL
, NULL
))
/* FIXME: We want to do this after the trymove(), but currently
* owl_mark_dragon() may crash if the trymove() happens to remove
* some stones of the goal dragon from the board.
init_owl(&owl
, target
, NO_MOVE
, NO_MOVE
, 1, NULL
);
if (trymove(move
, other
, "owl_does_attack", target
)) {
/* Check if a compatible owl_defend() is cached. */
if (search_persistent_owl_cache(OWL_DEFEND
, origin
, 0, 0,
&result
, NULL
, kworm
, NULL
)) {
return REVERSE_RESULT(result
);
local_owl_node_counter
= 0;
owl
->lunches_are_current
= 0;
owl_mark_dragon(target
, NO_MOVE
, owl
);
owl_update_boundary_marks(move
, owl
);
compute_owl_escape_values(owl
);
/* FIXME: Should also check if part of the dragon was captured,
* like do_owl_attack() does.
if (board
[target
] == EMPTY
)
prepare_goal_list(target
, owl
, owl_goal_worm
, &goal_worms_computed
,
dcode
= do_owl_defend(target
, NULL
, &wid
, owl
, 0);
finish_goal_list(&goal_worms_computed
, &wpos
, owl_goal_worm
, wid
);
result
= REVERSE_RESULT(dcode
);
owl
->lunches_are_current
= 0;
return 0; /* Don't cache anything in this case. */
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
DEBUG(DEBUG_OWL_PERFORMANCE
,
"owl_does_attack %1m %1m(%1m), result %d (%d, %d nodes, %f seconds)\n",
move
, target
, origin
, result
, local_owl_node_counter
,
tactical_nodes
, gg_cputime() - start
);
store_persistent_owl_cache(OWL_DOES_ATTACK
, move
, target
, 0,
tactical_nodes
, owl
->goal
, board
[target
]);
/* Use the owl code to determine whether connecting the two dragons
* (target1) and (target2) by playing at (move) results in a living
* dragon. Should be called only when stackp==0.
owl_connection_defends(int move
, int target1
, int target2
)
int color
= board
[target1
];
int reading_nodes_when_called
= get_reading_node_counter();
struct local_owl_data
*owl
;
if (debug
& DEBUG_OWL_PERFORMANCE
)
ASSERT1(board
[target2
] == color
, target2
);
TRACE("owl_connection_defends %1m %1m %1m\n", move
, target1
, target2
);
if (worm
[target1
].unconditional_status
== DEAD
)
if (worm
[target2
].unconditional_status
== DEAD
)
if (search_persistent_owl_cache(OWL_CONNECTION_DEFENDS
, move
, target1
,
target2
, &result
, NULL
, NULL
, NULL
))
init_owl(&owl
, target1
, target2
, NO_MOVE
, 1, NULL
);
if (trymove(move
, color
, "owl_connection_defends", target1
)) {
owl_update_goal(move
, SAME_DRAGON_MAYBE_CONNECTED
, NO_MOVE
, owl
, 0, NULL
);
if (!do_owl_attack(move
, NULL
, NULL
, owl
, 0))
owl
->lunches_are_current
= 0;
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
DEBUG(DEBUG_OWL_PERFORMANCE
,
"owl_conn_defends %1m %1m %1m, result %d (%d, %d nodes, %f seconds)\n",
move
, target1
, target2
, result
, local_owl_node_counter
,
tactical_nodes
, gg_cputime() - start
);
store_persistent_owl_cache(OWL_CONNECTION_DEFENDS
, move
, target1
, target2
,
result
, 0, 0, 0, tactical_nodes
,
/* This function attempts to make a list of dead strings
* which may be relevant to the life of the goal dragon.
* Such strings are called owl lunches. They are ignored
* (treated as invisible) during the running of make_domains.
* In certain cases we also need to identify tactically safe strings
* which should be included in the eyespace, e.g. in this position:
* The three O stones cannot be captured, but they can't live
* independently without capturing the surrounding stones. We call
* such stones INESSENTIAL and identify them by the condition that for
* each liberty of the corresponding superstring, the following must
* 1. At least one neighbor of the liberty is the goal dragon.
* 2. No neighbor of the liberty is the same color as the tested string,
* unless part of the same superstring.
* 3. No neighbor of the liberty of the same color as the goal dragon
* does not belong to the goal dragon.
* 4. No neighbor of the liberty belonging to the goal dragon can be
* There is a weakness with this characterization though, which can be
* The two O stones intruding in X's eyespace cannot be tactically
* captured and their liberties satisfy the requirements above. Still
* it doesn't make any sense to count those stones as
* inessential. Therefore we add another requirement on the stones
* 5. No neighbor of the stones does not belong to the goal or can be
* A second weakness can be noticed in this position:
* The white stones in the corner should qualify as inessential but
* the corner liberty doesn't satisfy requirement 1. Therefore we add
* an alternative requirement:
* 1b. The liberty is a topologically false eye with respect to the
* This is not quite good enough though, as shown in this position:
* The four O stones are regarded as inessential after inclusion of
* rule 1b, which is clearly inappropriate. To solve this problem we
* 1b'. The liberty is a topologically false eye with respect to the
* goal dragon and is adjacent to no empty vertex.
owl_find_lunches(struct local_owl_data
*owl
)
int other
= OTHER_COLOR(color
);
signed char already_checked
[BOARDMAX
];
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
for (prevlunch
= 0; prevlunch
< MAX_LUNCHES
; prevlunch
++)
owl
->lunch
[prevlunch
] = NO_MOVE
;
memset(owl
->inessential
, 0, sizeof(owl
->inessential
));
memset(already_checked
, 0, sizeof(already_checked
));
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] == color
&& owl
->goal
[pos
]) {
/* Loop over the eight neighbors. */
for (k
= 0; k
< 8; k
++) {
int pos2
= pos
+ delta
[k
];
/* If the immediate neighbor is empty, we look two steps away. */
if (k
< 4 && board
[pos2
] == EMPTY
)
if (board
[pos2
] != other
)
lunch
= find_origin(pos2
);
if (already_checked
[lunch
])
already_checked
[lunch
] = 1;
attack_and_defend(lunch
, &acode
, &apos
, &dcode
, &dpos
);
owl
->lunch
[lunches
] = lunch
;
owl
->lunch_attack_code
[lunches
] = acode
;
owl
->lunch_attack_point
[lunches
] = apos
;
owl
->lunch_defend_code
[lunches
] = dcode
;
ASSERT1(board
[apos
] == EMPTY
, lunch
);
owl
->lunch_defense_point
[lunches
] = dpos
;
ASSERT1(board
[dpos
] == EMPTY
, lunch
);
owl
->lunch_defense_point
[lunches
] = NO_MOVE
;
if (lunches
== MAX_LUNCHES
) {
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
owl
->lunches_are_current
= 1;
else if (!owl
->inessential
[lunch
]) {
/* Test for inessentiality. */
int stones
[MAX_BOARD
* MAX_BOARD
];
int superstring
[BOARDMAX
];
/* First check the neighbors of the string. */
adj
= chainlinks(lunch
, adjs
);
for (r
= 0; r
< adj
; r
++) {
if (!owl
->goal
[adjs
[r
]] || attack(adjs
[r
], NULL
) != 0) {
find_superstring_stones_and_liberties(lunch
, &num_stones
, stones
,
memset(superstring
, 0, sizeof(superstring
));
for (r
= 0; r
< num_stones
; r
++)
superstring
[stones
[r
]] = 1;
for (r
= 0; r
< liberties
; r
++) {
for (s
= 0; s
< 4; s
++) {
int cpos
= bpos
+ delta
[s
];
if (board
[cpos
] == color
) {
if (attack(cpos
, NULL
) != 0) {
else if (owl
->goal
[cpos
])
else if (board
[cpos
] == other
/* Requirement 1 not satisfied. Test requirement 1b.
* N.B. This is a simplified topological eye test.
* The simplification may be good, bad, or neutral.
for (s
= 4; s
< 8; s
++) {
if (!ON_BOARD(bpos
+ delta
[s
]))
else if (owl
->goal
[bpos
+ delta
[s
]])
if (diagonal_goal
+ (off_board
>= 2) < 2)
/* Check that the liberty is adjacent to no empty
* vertex, as required by 1b'.
for (s
= 0; s
< 4; s
++) {
if (board
[bpos
+ delta
[s
]] == EMPTY
) {
TRACE("Inessential string found at %1m.\n", lunch
);
for (r
= 0; r
< num_stones
; r
++)
owl
->inessential
[stones
[r
]] = 1;
owl
->lunches_are_current
= 1;
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
/* Try to improve the move to attack a lunch. Essentially we try to avoid
* unsafe moves when there are less risky ways to attack.
* This function also improves lunch attack point in a special case when
* we capture a one- or two-stone lunch on the first line. If we eat it
* with a first line move, there is a huge risk we'll end up with a false
* eye. Therefore, we move the attack to the second line when it works.
* In all these position the attack point is moved from ',' to '*'.
improve_lunch_attack(int lunch
, int attack_point
)
int color
= OTHER_COLOR(board
[lunch
]);
if (safe_move(attack_point
, color
)) {
if (is_edge_vertex(lunch
)
&& is_edge_vertex(attack_point
)
&& neighbor_of_string(attack_point
, lunch
)) {
int stones
= countstones(lunch
);
&& findlib(lunch
, 2, libs
) == 2
&& is_edge_vertex(libs
[0])
&& is_edge_vertex(libs
[1]))) {
for (k
= 0; k
< 4; k
++) {
int apos
= attack_point
+ delta
[k
];
if (!ON_BOARD(attack_point
- delta
[k
]) && board
[apos
] == EMPTY
) {
if (does_attack(apos
, lunch
) && safe_move(apos
, color
))
for (k
= 0; k
< 4; k
++) {
int pos
= attack_point
+ delta
[k
];
&& find_defense(pos
, &defense_point
)
&& defense_point
!= NO_MOVE
&& does_attack(defense_point
, lunch
)) {
TRACE("Moved attack of lunch %1m from %1m to %1m.\n",
lunch
, attack_point
, defense_point
);
/* Try to improve the move to defend a lunch.
* An example where this is useful is the position below, where the
* defense of A is moved from b to c. This is a possible variation in
improve_lunch_defense(int lunch
, int defense_point
)
int color
= board
[lunch
];
for (k
= 0; k
< 4; k
++) {
int pos
= defense_point
+ delta
[k
];
if (board
[pos
] == OTHER_COLOR(color
)
if (libs
[0] == defense_point
)
if (accuratelib(pos2
, color
, MAXLIBS
, NULL
)
> accuratelib(defense_point
, color
, MAXLIBS
, NULL
)
&& does_defend(pos2
, lunch
)) {
TRACE("Moved defense of lunch %1m from %1m to %1m.\n",
lunch
, defense_point
, pos2
);
/* Wrapper for make domains. The second set of owl data is optional.
* Use a null pointer if it is not needed. Otherwise, make_domains
* is run separately for the two owl data, but information about
* tactically dead lunches is used from *both* sources through
* the owl_lively() calls.
owl_make_domains(struct local_owl_data
*owla
, struct local_owl_data
*owlb
)
/* We need to set this so that owl_lively() can be used. */
struct eye_data
*black_eye
= NULL
;
struct eye_data
*white_eye
= NULL
;
if (!owla
->lunches_are_current
)
if (owla
->color
== BLACK
)
black_eye
= owla
->my_eye
;
white_eye
= owla
->my_eye
;
gg_assert(owla
->color
== OTHER_COLOR(owlb
->color
));
if (!owlb
->lunches_are_current
)
if (owlb
->color
== BLACK
)
black_eye
= owlb
->my_eye
;
white_eye
= owlb
->my_eye
;
make_domains(black_eye
, white_eye
, 1);
/* True unless (pos) is EMPTY or occupied by a lunch for the goal dragon.
* Used during make_domains (see optics.c: lively macro). A ``lively''
* worm is one that might be alive, hence cannot be ignored in
* determining eye spaces.
origin
= find_origin(pos
);
/* When reading a semeai there is a second set of owl data to consider.
* Strings of the second owl are considered lively no matter what,
* since declaring such a string dead prematurely can prevent the
* semeai code from finishing its job.
* On the other hand a friendly string which is a lunch of the
* other dragon and can't be saved is not lively.
if (include_semeai_worms_in_eyespace
&& other_owl_data
->goal
[pos
])
if (other_owl_data
->goal
[pos
] && !semeai_trust_tactical_attack(pos
))
/* FIXME: Shouldn't we check other_owl_data->inessential[origin] here? */
for (lunch
= 0; lunch
< MAX_LUNCHES
; lunch
++)
if (other_owl_data
->lunch
[lunch
] == origin
&& other_owl_data
->lunch_defense_point
[lunch
] == NO_MOVE
)
/* Inessential stones are not lively. */
if (current_owl_data
->inessential
[origin
])
/* Lunches that can't be saved are dead, so don't report them as lively. */
for (lunch
= 0; lunch
< MAX_LUNCHES
; lunch
++)
if (current_owl_data
->lunch
[lunch
] == origin
&& current_owl_data
->lunch_defense_point
[lunch
] == NO_MOVE
)
/* Caching version of safe_move for the callback. This function has
* its own cache, separate from the global safe move cache. Note that
* since the cache is reset by owl_shapes before starting pattern
* matching, and since (unlike safe_move) this function is always
* called from the same place in owl_shapes_callback, the color will
* be the same each time it is called. So there is no need to have
* separate caches for B and W.
owl_safe_move(int move
, int color
)
if (trymove(move
, color
, "owl_safe_move", 0)) {
acode
= attack(move
, NULL
);
current_owl_data
->safe_move_cache
[move
] = safe
+1;
/* This function, called when stackp==0, returns true if capturing
* the string at (str) results in a live group.
#define MAX_SUBSTANTIAL_LIBS 10
int libs
[MAX_SUBSTANTIAL_LIBS
+ 1];
int liberties
= findlib(str
, MAX_SUBSTANTIAL_LIBS
+1, libs
);
int reading_nodes_when_called
= get_reading_node_counter();
struct local_owl_data
*owl
;
if (debug
& DEBUG_OWL_PERFORMANCE
)
/* FIXME: We want to use the full init_owl here too (cf. similar
reduced_init_owl(&owl
, 1);
owl
->color
= OTHER_COLOR(board
[str
]);
local_owl_node_counter
= 0;
/* Big strings are always substantial since the biggest nakade is
* six stones. (There are probably rare exceptions to this
* rule, but they are unlikely to come up in a game.)
if (countstones(str
) > 6)
if (liberties
> MAX_SUBSTANTIAL_LIBS
)
memset(owl
->goal
, 0, sizeof(owl
->goal
));
/* Mark the neighbors of the string. If one is found which is alive, return
adj
= chainlinks(str
, adjs
);
for (k
= 0; k
< adj
; k
++) {
if (dragon
[adjs
[k
]].status
== ALIVE
)
mark_dragon(adjs
[k
], owl
->goal
, 1);
/* We must check the cache while stackp == 0, but we wait until the
* trivial tests have been done.
if (search_persistent_owl_cache(OWL_SUBSTANTIAL
, str
, 0, 0,
&result
, NULL
, NULL
, NULL
))
/* fill all the liberties */
for (k
= 0; k
< liberties
; k
++) {
if (trymove(libs
[k
], owl
->color
, NULL
, 0)) {
/* if we can't fill, try swapping with the next liberty */
&& trymove(libs
[k
+1], owl
->color
, NULL
, 0)) {
owl
->goal
[libs
[k
+1]] = 1;
/* Can't fill the liberties. Give up! */
while (num_moves
-- > 0) {
/* FIXME: We would want to use init_owl() here too, but it doesn't
* fit very well with the construction of the goal array above.
memcpy(owl
->cumulative_goal
, owl
->goal
, BOARDMAX
);
compute_owl_escape_values(owl
);
owl
->lunches_are_current
= 0;
if (do_owl_attack(libs
[0], NULL
, NULL
, owl
, 0))
while (num_moves
-- > 0) {
tactical_nodes
= get_reading_node_counter() - reading_nodes_when_called
;
DEBUG(DEBUG_OWL_PERFORMANCE
,
"owl_substantial %1m, result %d (%d, %d nodes, %f seconds)\n",
str
, result
, local_owl_node_counter
,
tactical_nodes
, gg_cputime() - start
);
store_persistent_owl_cache(OWL_SUBSTANTIAL
, str
, 0, 0, result
, 0, 0, 0,
tactical_nodes
, owl
->goal
, owl
->color
);
/* Returns true if and only if (i, j) is a 1-2 vertex, i.e. next to a
if ((i
== 0 || i
== board_size
-1 || j
== 0 || j
== board_size
-1)
&& (i
== 1 || i
== board_size
-2 || j
== 1 || j
== board_size
-2))
/* Reports the number of eyes gotten by capturing a boundary string.
* This implementation tends to give an optimistic view of the
* chances, so if it tells that the lunch is worthless, it truly
* should be. The converse is not true.
sniff_lunch(int lunch
, int *min
, int *probable
, int *max
,
struct local_owl_data
*owl
)
int other
= OTHER_COLOR(board
[lunch
]);
ASSERT1(IS_STONE(board
[lunch
]), lunch
);
if (owl
->boundary
[lunch
] == 2) {
/* Do we believe this capture would help escaping? */
liberties
= findlib(lunch
, MAXLIBS
, libs
);
for (r
= 0; r
< liberties
; r
++) {
if (owl
->escape_values
[libs
[r
]] > 0
&& !is_self_atari(libs
[r
], other
)) {
if (ON_BOARD(libs
[r
] + delta
[k
]) && owl
->goal
[libs
[r
] + delta
[k
]])
estimate_lunch_eye_value(lunch
, min
, probable
, max
, 1);
int bonus
= estimate_lunch_half_eye_bonus(lunch
, owl
->half_eye
);
eat_lunch_escape_bonus(lunch
, min
, probable
, max
, owl
);
/* Capturing a lunch can give eyes by turning a false eye into a proper one,
* etc. This function returns the likely increase in half eyes
* by capturing the string at (lunch).
estimate_lunch_half_eye_bonus(int lunch
,
struct half_eye_data half_eye
[BOARDMAX
])
int size
= findstones(lunch
, 10, stones
);
ASSERT1(size
< 10, lunch
);
for (k
= 0; k
< size
; k
++) {
for (d
= 4; d
< 8; d
++) {
int pos
= stone
+ delta
[d
];
&& (is_halfeye(half_eye
, pos
) || is_false_eye(half_eye
, pos
)))
estimate_lunch_eye_value(int lunch
, int *min
, int *probable
, int *max
,
int appreciate_one_two_lunches
)
int other
= OTHER_COLOR(board
[lunch
]);
int size
= countstones(lunch
);
findstones(lunch
, 2, stones
);
/* A lunch on a 1-2 point tends always to be worth contesting. */
if ((obvious_false_eye(stones
[0], other
)
|| obvious_false_eye(stones
[1], other
))
&& (!appreciate_one_two_lunches
|| !(one_two_point(stones
[0]) || one_two_point(stones
[1])))) {
if (!obvious_false_eye(lunch
, other
)) {
/* Gives a bonus for a lunch capture which joins a (or some) friendly
* string(s) to the goal dragon and improves the escape potential at
* the same time. This is indicated in some situations where the owl
* code would stop the analysis because of various cutoffs. See
* The following implementation tries to get a precise idea of the
* escape potential improvement by calling dragon_escape() twice.
eat_lunch_escape_bonus(int lunch
, int *min
, int *probable
, int *max
,
struct local_owl_data
*owl
)
/* Be very careful before touching this value.
* See owl_estimate_life() for details.
/* Don't mess up with kos */
neighbors
= chainlinks(lunch
, adjacent
);
for (n
= 0; n
< neighbors
; n
++)
adjoins
|= !owl
->goal
[adjacent
[n
]];
before
= dragon_escape(owl
->goal
, owl
->color
, owl
->escape_values
);
/* if the escape route is already large enough to be considered
* a WIN by the owl code, then no need for more */
signed char new_goal
[BOARDMAX
];
memcpy(new_goal
, owl
->goal
, sizeof(new_goal
));
for (n
= 0; n
< neighbors
; n
++)
if (!owl
->goal
[adjacent
[n
]])
mark_string(adjacent
[n
], new_goal
, 2);
after
= dragon_escape(new_goal
, owl
->color
, owl
->escape_values
);
/* Following is completely ad hoc. Another set of tests might
* very well get better results. */
if (after
- before
>= 3) {
if (after
>= 8 || (before
== 0 && after
>= 5)) {
/* Find a new origin when it has been captured or cut out of the
* goal. Used in do_owl_attack()
select_new_goal_origin(int origin
, struct local_owl_data
*owl
)
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (board
[pos
] == owl
->color
&& owl
->goal
[pos
] == 1)
/* Retrieve topological eye values stored in the half_eye[] array of
* FIXME: Sooner or later we'll want this to return a non-rounded
* value. When we change this, we have to review all patterns using
* the autohelper owl_topological_eye().
owl_topological_eye(int pos
, int color
)
value
= current_owl_data
->half_eye
[pos
].value
;
if (value
> 2.0 && value
< 4.0)
return (int) (value
+ 0.99); /* Round up. */
return (int) value
; /* Round down. */
/* This function returns true if it is judged that the capture of the
* string at (pos) is sufficient to create one eye.
* Update: Now it instead returns the max number of eyes.
sniff_lunch(pos
, &min
, &probable
, &max
, current_owl_data
);
compute_owl_escape_values(struct local_owl_data
*owl
)
signed char safe_stones
[BOARDMAX
];
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
signed char mx
[BOARDMAX
];
memset(mx
, 0, sizeof(mx
));
get_lively_stones(OTHER_COLOR(owl
->color
), safe_stones
);
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
compute_escape_influence(owl
->color
, safe_stones
, NULL
, NULL
,
DEBUG(DEBUG_ESCAPE
, "Owl escape values:\n");
for (m
= 0; m
< board_size
; m
++) {
for (n
= 0; n
< board_size
; n
++) {
if (dragon
[pos
].color
== owl
->color
&& !owl
->goal
[pos
]) {
if (dragon
[pos
].crude_status
== ALIVE
)
owl
->escape_values
[pos
] = 6;
else if (dragon
[pos
].crude_status
== UNKNOWN
) {
if (DRAGON2(pos
).moyo_size
> 5)
owl
->escape_values
[pos
] = 4;
else if (DRAGON2(pos
).escape_route
> 5) {
if (mx
[dragon
[pos
].origin
])
owl
->escape_values
[pos
] = owl
->escape_values
[dragon
[pos
].origin
];
signed char escape_values
[BOARDMAX
];
signed char dragon_stones
[BOARDMAX
];
compute_escape_influence(owl
->color
, safe_stones
, owl
->goal
,
/* mark_dragon() can't be used here in case a string of
* the dragon was captured by the initial move in
* owl_does_attack(). Actually it isn't really proper to
* use is_same_dragon() at stackp>0 either but it's more
for (pos2
= BOARDMIN
; pos2
< BOARDMAX
; pos2
++) {
dragon_stones
[pos2
] = is_same_dragon(pos2
, pos
);
if (dragon_escape(dragon_stones
, owl
->color
, escape_values
) > 5)
owl
->escape_values
[dragon
[pos
].origin
] = 4;
mx
[dragon
[pos
].origin
] = 1;
DEBUG(DEBUG_ESCAPE
, "%o%d", owl
->escape_values
[pos
]);
DEBUG(DEBUG_ESCAPE
, "%o\n");
/* Used by autohelpers. */
owl_escape_value(int pos
)
/* FIXME: Should have a more robust mechanism to avoid
* escaping inwards. Returning a negative value is just a kludge.
if (current_owl_data
->goal
[pos
])
if (ON_BOARD(pos
+ delta
[k
]) && current_owl_data
->goal
[pos
+ delta
[k
]])
return current_owl_data
->escape_values
[pos
];
/* Used by autohelpers. */
return current_owl_data
->goal
[pos
] != 0;
* Returns 1 if (pos) is an eyespace for the color of the dragon currently
* under owl investigation.
origin
= current_owl_data
->my_eye
[pos
].origin
;
&& (current_owl_data
->my_eye
[origin
].color
== current_owl_data
->color
)
&& max_eyes(¤t_owl_data
->my_eye
[origin
].value
) > 0);
* Returns 1 if (pos) is an eyespace for the color of the dragon currently
* under owl investigation, which is possibly worth (at least) 2 eyes.
owl_big_eyespace(int pos
)
origin
= current_owl_data
->my_eye
[pos
].origin
;
&& (current_owl_data
->my_eye
[origin
].color
== current_owl_data
->color
)
&& max_eyes(¤t_owl_data
->my_eye
[origin
].value
) >= 2);
* Returns 1 if (pos) is an eyespace for the color of the dragon currently
* under owl investigation.
origin
= current_owl_data
->my_eye
[pos
].origin
;
|| (current_owl_data
->my_eye
[origin
].color
!= current_owl_data
->color
))
return min_eyes(¤t_owl_data
->my_eye
[origin
].value
);
* Returns 1 if (pos) is an eyespace for the color of the dragon currently
* under owl investigation.
origin
= current_owl_data
->my_eye
[pos
].origin
;
|| (current_owl_data
->my_eye
[origin
].color
!= current_owl_data
->color
))
return max_eyes(¤t_owl_data
->my_eye
[origin
].value
);
* Returns 1 if (pos) is a non-marginal eyespace for the color of the
* dragon currently under owl investigation.
return ((current_owl_data
->my_eye
[pos
].color
== current_owl_data
->color
)
&& !current_owl_data
->my_eye
[pos
].marginal
);
* Returns the effective size of the eyespace at pos.
origin
= current_owl_data
->my_eye
[pos
].origin
;
return current_owl_data
->my_eye
[origin
].esize
- current_owl_data
->my_eye
[origin
].msize
;
* Returns whether str is a lunch.
ASSERT1(current_owl_data
->lunches_are_current
, str
);
origin
= find_origin(str
);
for (k
= 0; k
< MAX_LUNCHES
; k
++) {
if (current_owl_data
->lunch
[k
] == NO_MOVE
)
if (current_owl_data
->lunch
[k
] == origin
)
* Returns 1 if (pos) is considered to be a strong dragon. This is
* intended to be used to decide whether connecting to some external
* stones is an easy way to live. The current implementation is fairly
* conservative, requiring that (pos) was part of a dragon with two
* eyes according to the static analysis. This requirement may be
* relaxed considerably in the future.
* (pos) must not be part of the goal dragon.
owl_strong_dragon(int pos
)
ASSERT1(IS_STONE(board
[pos
]), pos
);
return (!current_owl_data
->goal
[pos
]
&& dragon
[pos
].color
== board
[pos
]
&& dragon
[pos
].crude_status
== ALIVE
);
owl_escape_route(struct local_owl_data
*owl
)
signed char modified_escape
[BOARDMAX
];
memcpy(modified_escape
, owl
->escape_values
, sizeof(modified_escape
));
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (ON_BOARD(pos
) && owl
->cumulative_goal
[pos
])
modified_escape
[pos
] = 0;
return dragon_escape(owl
->goal
, owl
->color
, modified_escape
);
/****************************
* Initialization of owl data
****************************/
/* This is a temporary solution. We want to be able to use the full
* init_owl() also in owl_substantial.
reduced_init_owl(struct local_owl_data
**owl
, int at_bottom_of_stack
)
*owl
= owl_stack
[owl_stack_pointer
];
VALGRIND_MAKE_WRITABLE(*owl
, sizeof(struct local_owl_data
));
/* Initialize owl data. Set at_bottom_of_stack to 1 the first time you
* call init_owl() and to 0 any following time (only relevant if you
* need more than one set of owl data).
init_owl(struct local_owl_data
**owl
, int target1
, int target2
, int move
,
int at_bottom_of_stack
, int new_dragons
[BOARDMAX
])
reduced_init_owl(owl
, at_bottom_of_stack
);
local_owl_node_counter
= 0;
(*owl
)->lunches_are_current
= 0;
owl_mark_dragon(target1
, target2
, *owl
, new_dragons
);
owl_update_goal(move
, SAME_DRAGON_MAYBE_CONNECTED
, NO_MOVE
, *owl
, 0, NULL
);
compute_owl_escape_values(*owl
);
/* Check the size of the owl stack and extend it if too small. */
check_owl_stack_size(void)
while (owl_stack_size
<= owl_stack_pointer
) {
owl_stack
[owl_stack_size
] = malloc(sizeof(*owl_stack
[0]));
gg_assert(owl_stack
[owl_stack_size
] != NULL
);
/* Push owl data one step upwards in the stack. Gets called from
do_push_owl(struct local_owl_data
**owl
)
struct local_owl_data
*new_owl
= owl_stack
[owl_stack_pointer
];
/* Mark all the data in *new_owl as uninitialized. */
VALGRIND_MAKE_WRITABLE(new_owl
, sizeof(struct local_owl_data
));
memcpy(new_owl
->goal
, (*owl
)->goal
, sizeof(new_owl
->goal
));
memcpy(new_owl
->cumulative_goal
, (*owl
)->cumulative_goal
,
sizeof(new_owl
->cumulative_goal
));
memcpy(new_owl
->boundary
, (*owl
)->boundary
, sizeof(new_owl
->boundary
));
memcpy(new_owl
->neighbors
, (*owl
)->neighbors
, sizeof(new_owl
->neighbors
));
memcpy(new_owl
->escape_values
, (*owl
)->escape_values
,
sizeof(new_owl
->escape_values
));
new_owl
->color
= (*owl
)->color
;
new_owl
->lunches_are_current
= 0;
/* Needed for stack organization. Since there may be one or two sets
* of owl data active at we don't know whether to restore from the
* previos stack entry or two steps back.
new_owl
->restore_from
= *owl
;
/* Finally move the *owl pointer. */
/* Push owl data one step upwards in the stack. The stack is extended
* with dynamically allocated memory if it is too small.
* This function no longer may move existing owl data around, so
* existing pointers do not risk becoming invalid.
push_owl(struct local_owl_data
**owl
)
/* Retrieve owl data from the stack. */
pop_owl(struct local_owl_data
**owl
)
*owl
= (*owl
)->restore_from
;
* List worms in order to track captures during owl reading
list_goal_worms(struct local_owl_data
*owl
, int goal_worm
[MAX_GOAL_WORMS
])
for (k
= 0; k
< MAX_GOAL_WORMS
; k
++)
for (pos
= BOARDMIN
; pos
< BOARDMAX
&& w
< MAX_GOAL_WORMS
; pos
++) {
&& owl
->goal
[pos
] == 1) {
int origin
= find_origin(pos
);
if (goal_worm
[k
] == origin
)
/* experimental: let's try to fill up the array with other neighboring
if (1 && (w
> 0) && (w
< MAX_GOAL_WORMS
)) {
for (k
= 0; k
< DRAGON2(pos
).neighbors
&& w
< MAX_GOAL_WORMS
; k
++) {
int d
= DRAGON2(pos
).adjacent
[k
];
if (DRAGON(d
).color
!= owl
->color
)
for (ii
= BOARDMIN
; ii
< BOARDMAX
&& w
< MAX_GOAL_WORMS
; ii
++)
if (ON_BOARD(ii
) && board
[ii
] && worm
[ii
].origin
== ii
&& worm
[ii
].size
>= 3 && dragon
[ii
].id
== d
)
prepare_goal_list(int str
, struct local_owl_data
*owl
,
int list
[MAX_GOAL_WORMS
], int *flag
,
list_goal_worms(owl
, list
);
/* N.B. We cannot use sizeof(list) below because a formal array
* parameter implicitly is converted to a pointer and sizeof(list)
* thus equals sizeof(int *), which is not what we want.
memcpy(dragon_goal_worms
[dragon
[str
].id
], list
,
sizeof(dragon_goal_worms
[dragon
[str
].id
]));
finish_goal_list(int *flag
, int *wpos
, int list
[MAX_GOAL_WORMS
], int index
)
if (index
== MAX_GOAL_WORMS
)
/* Returns the number of worms in the goal dragon, and a pointer to each */
catalog_goal(struct local_owl_data
*owl
, int goal_worm
[MAX_GOAL_WORMS
])
for (k
= 0; k
< MAX_WORMS
; k
++)
for (pos
= BOARDMIN
; pos
< BOARDMAX
&& worms
< MAX_WORMS
; pos
++)
int origin
= find_origin(pos
);
DEBUG(DEBUG_SEMEAI
, "goal worm: %1m\n", pos
);
goal_worm
[worms
++] = pos
;
/***********************/
global_owl_node_counter
= 0;
/* Retrieve statistics. */
return global_owl_node_counter
;