Initial commit of GNU Go v3.8.

[sgk-go] / engine / owl.c

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* 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).
*
*                             (|__|)
*                            (@)(@))
*                            |:v:: |
*                           (       )
*                            \|   |/
*                            =#===#=
*                            /___/
* 
*                The owl is noted for its keen vision 
*                       and (purported) wisdom.
*/

#include "gnugo.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "liberty.h"
#include "readconnect.h"
#include "patterns.h"
#include "cache.h"
#include "sgftree.h"
#include "gg_utils.h"

#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_LUNCHES 10
#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 */
                     /*    not called                                       */

struct local_owl_data {
 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];
 int color;

 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[MAX_LUNCHES];
 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;

/* Statistics. */
static int local_owl_node_counter;
/* Node limitation. */
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];


#define MAX_CUTS 5

enum same_dragon_value {
 SAME_DRAGON_NOT_CONNECTED,
 SAME_DRAGON_MAYBE_CONNECTED,
 SAME_DRAGON_CONNECTED,
 SAME_DRAGON_ALL_CONNECTED
};

struct matched_pattern_data;

struct owl_move_data {
 int pos;          /* move coordinate */
 int value;        /* value */
 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;
};

#define USE_BDIST 1

struct matched_pattern_data {
 int move;
 int value;
 int ll;
 int anchor;
#if USE_BDIST
 int bdist;
#endif
 struct pattern *pattern;

 /* To link combinable patterns in chains. */
 int next_pattern_index;
};
 
struct matched_patterns_list_data {
 int initialized;
 int counter;          /* Number of patterns in the list. */
 int used;             /* How many patterns have already been used?*/
 int list_size;        
 struct matched_pattern_data *pattern_list;
 int first_pattern_index[BOARDMAX];

 int heap_num_patterns;
 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,
                                        int ll, void *data);

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
                                              *list);

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,
                               int ll, void *data);
static void 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);
static void owl_determine_life(struct local_owl_data *owl,
                              struct local_owl_data *second_owl,
                              int does_attack,
                              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,
                            int does_attack,
                            struct eyevalue *probable_eyes,
                            int *eyemin, int *eyemax);
static int modify_stupid_eye_vital_point(struct local_owl_data *owl,
                                        int *vital_point,
                                        int is_attack_point);
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,
                           int semeai_call,
                           struct matched_pattern_data *pattern_data);
static void owl_test_cuts(signed char goal[BOARDMAX], int color,
                         int cuts[MAX_CUTS]);
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 owl_phase,
                                     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,
                            int at_bottom_of_stack);
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);

#if 0
static int catalog_goal(struct local_owl_data *owl,
                       int goal_worm[MAX_GOAL_WORMS]);
#endif

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];

static void
prepare_goal_list(int str, struct local_owl_data *owl,
                 int list[MAX_GOAL_WORMS], int *flag, int *kworm,
                 int do_list);
static void
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 s_worms = 0;
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. */
static int prefer_ko;

/* 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;



static void
clear_cut_list(int cuts[MAX_CUTS])
{
 int i;
 for (i = 0; i < MAX_CUTS; i++)
   cuts[i] = NO_MOVE;
}



/* 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.
*
*/

void
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.
*/
void
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,
                             int recompute_dragons)
{
 signed char ms[BOARDMAX];
 int w1, w2;
 int str;
 SGFTree *save_sgf_dumptree = sgf_dumptree;
 int save_verbose = verbose;
 int dummy_resulta;
 int dummy_resultb;
 int dummy_semeai_move;
 double start = 0.0;
 int reading_nodes_when_called = get_reading_node_counter();
 int nodes_used;
 int new_dragons[BOARDMAX];
 
 struct local_owl_data *owla;
 struct local_owl_data *owlb;
 Hash_data goal_hash;
 
 if (!resulta)
   resulta = &dummy_resulta;
 if (!resultb)
   resultb = &dummy_resultb;
 if (!semeai_move)
   semeai_move = &dummy_semeai_move;

 if (debug & DEBUG_OWL_PERFORMANCE)
   start = gg_cputime();

 if (recompute_dragons) {
   if (tryko(move, color, "Recompute dragons for semeai.")) {
     compute_new_dragons(new_dragons);
     popgo();
   }
   else
     recompute_dragons = 0;
 }
 
 
 /* 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.
  */
 s_worms = 0;
 memset(ms, 0, sizeof(ms));
 for (w1 = first_worm_in_dragon(apos);
      w1 != NO_MOVE;
      w1 = next_worm_in_dragon(w1)) {
   for (w2 = first_worm_in_dragon(bpos);
        w2 != NO_MOVE;
        w2 = next_worm_in_dragon(w2)) {
     if (adjacent_strings(w1, w2) || have_common_lib(w1, w2, NULL)) {
       mark_string(w1, ms, 1);
       mark_string(w2, ms, 1);
     }
   }
 }


 
 sgf_dumptree = NULL;
 if (verbose > 0)
   verbose--;
 for (str = BOARDMIN; str < BOARDMAX; str++) 
   if (ON_BOARD(str) && ms[str] && worm[str].origin == str) {
     int adj;
     int adjs[MAXCHAIN];
     int k;
     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
      * of the opponent.
      *
      * 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)
         adjacent_to_outside = 1;
     }
     
     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);
     }
   }
 verbose = save_verbose;
 sgf_dumptree = save_sgf_dumptree;

 ASSERT1(board[apos] == OTHER_COLOR(board[bpos]), apos);
 count_variations = 1;
 if (move == PASS_MOVE)
   DEBUG(DEBUG_SEMEAI, "owl_analyze_semeai: %1m vs. %1m\n", apos, bpos);
 else
   DEBUG(DEBUG_SEMEAI, "owl_analyze_semeai_after_move %C %1m: %1m vs. %1m\n",
         color, move, apos, bpos);
 
 if (owl) {
   if (recompute_dragons) {
     init_owl(&owla, apos, NO_MOVE, NO_MOVE, 1, new_dragons);
     init_owl(&owlb, bpos, NO_MOVE, NO_MOVE, 0, new_dragons);
   }
   else {
     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);
 }
 else {
   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);
 }

 result_certain = 1;

 {
   Hash_data temp = goal_to_hashvalue(owla->goal);
   goal_hash = goal_to_hashvalue(owlb->goal);
   hashdata_xor(goal_hash, temp);
 }
 if (owl
     && search_persistent_semeai_cache(ANALYZE_SEMEAI,
                                       apos, bpos, move, color, &goal_hash,
                                       resulta, resultb, semeai_move,
                                       semeai_result_certain)) {
   if (move == PASS_MOVE) {
     DEBUG(DEBUG_OWL_PERFORMANCE,
           "analyze_semeai %1m vs. %1m, result %d %d %1m (cached)\n",
           apos, bpos, *resulta, *resultb, *semeai_move);
   }
   else {
     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);
   }
   return;
 }

 /* 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)
   prefer_ko = board[apos];
 else if (dragon[bpos].size <= 5 && dragon[apos].size > 3 * dragon[bpos].size)
   prefer_ko = board[bpos];
 else
   prefer_ko = EMPTY;
 
 if (move == PASS_MOVE)
   do_owl_analyze_semeai(apos, bpos, owla, owlb,
                         resulta, resultb, semeai_move, 0, owl);
 else {
   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;
 if (move == PASS_MOVE) {
   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);
 }
 else {
   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,
         local_owl_node_counter,
         nodes_used, gg_cputime() - start);
 }
 
 if (semeai_result_certain)
   *semeai_result_certain = result_certain;

 if (owl)
   store_persistent_semeai_cache(ANALYZE_SEMEAI, apos, bpos, move, color,
                                 &goal_hash,
                                 *resulta, *resultb, *semeai_move,
                                 result_certain, nodes_used,
                                 owla->goal, owlb->goal);
}



/* 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.
*/

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)
{
 int color = board[apos];
 int other = OTHER_COLOR(color);
#if 0
 int wormsa, wormsb;
 int goal_wormsa[MAX_GOAL_WORMS], goal_wormsb[MAX_GOAL_WORMS];
#endif
 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];  
 int k;
 SGFTree *save_sgf_dumptree = sgf_dumptree;
 int save_count_variations = count_variations;
 int move_value;
 int best_resulta = 0;
 int best_resultb = 0;
 int best_move = 0;
 const char *best_move_name = NULL;
 int this_resulta = -1;
 int this_resultb = -1;
 int xpos;
 int value1;
 int value2;
 int this_variation_number = count_variations - 1;
 int you_look_alive = 0;
 int I_look_alive = 0;
 int dummy_move;
 int tested_moves;
 int critical_semeai_worms[MAX_SEMEAI_WORMS];
 int sworm;
 int we_might_be_inessential;
 struct eyevalue probable_eyes_a;
 struct eyevalue probable_eyes_b;
 struct eyevalue dummy_eyes;
 int I_have_more_eyes;
 
 SETUP_TRACE_INFO2("do_owl_analyze_semeai", apos, bpos);

 if (!move)
   move = &dummy_move;
 
 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
     && owl_phase
     && tt_get(&ttable, SEMEAI, apos, bpos, depth - stackp, NULL,
               &value1, &value2, &xpos) == 2) {
   TRACE_CACHED_RESULT2(value1, value2, xpos);
   *move = xpos;
     
   *resulta = value1;
   *resultb = value2;

   TRACE("%oVariation %d: %1m %1m %s %s %1m (cached) ",
         this_variation_number, apos, bpos,
         result_to_string(*resulta),
         result_to_string(*resultb),
         *move);
   SGFTRACE_SEMEAI(xpos, *resulta, *resultb, "cached");
   return;
 }

 global_owl_node_counter++;
 local_owl_node_counter++;

 shape_offensive_patterns.initialized = 0;
 shape_defensive_patterns.initialized = 0;
 
#if 0
 wormsa = catalog_goal(owla, goal_wormsa);
 wormsb = catalog_goal(owlb, goal_wormsb);
#endif
 
 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].pos = 0;
   moves[k].value = -1;
   moves[k].name = NULL;
   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. */
 sgf_dumptree = NULL;
 count_variations = 0;
 
 /* 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.
  */

 {
   int upos;
   
   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);
       if (acode == WIN
           && semeai_trust_tactical_attack(semeai_worms[sworm])
           && important_semeai_worms[sworm]) {
         *resulta = WIN;
         *resultb = WIN;
         *move = upos;
         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,
                            move, upos, WIN, WIN);
       }
       else if (acode != 0
                && 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);
       }
       else if (acode == WIN
                && 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.
  */
 if (!owl_phase) {
   set_eyevalue(&probable_eyes_a, 0, 0, 0, 0);
   set_eyevalue(&probable_eyes_b, 0, 0, 0, 0);
   I_have_more_eyes = 0;
 }
 else {
   /* 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. 
    */
   int eyemin_a;
   int eyemin_b;
   int eyemax_a;
   int eyemax_b;
   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 
    * such lunches.
    */
   
   owl_find_lunches(owla);
   owl_find_lunches(owlb);
   for (k = 0; k < MAX_LUNCHES; k++) {
     if (owla->lunch[k] != NO_MOVE 
         && owlb->goal[owla->lunch[k]]) {
       owla->lunch[k] = NO_MOVE;
     }
   }
#if 1
   for (k = 0; k < MAX_LUNCHES; k++) {
     if (owlb->lunch[k] != NO_MOVE 
         && owla->goal[owlb->lunch[k]]) {
       owlb->lunch[k] = NO_MOVE;
     }
   }
#endif

   if (owl_estimate_life(owla, owlb, vital_defensive_moves,
                         &live_reasona, 0, &probable_eyes_a,
                         &eyemin_a, &eyemax_a))
     I_look_alive = 1;
   else if (stackp > 2 && owl_escape_route(owla) >= 5) {
     live_reasona = "escaped";
     I_look_alive = 1;
   }

   if (owl_estimate_life(owlb, owla, vital_offensive_moves,
                         &live_reasonb, 1, &probable_eyes_b,
                         &eyemin_b, &eyemax_b))
     you_look_alive = 1;
   else if (stackp > 2 && owl_escape_route(owlb) >= 5) {
     live_reasonb = "escaped";
     you_look_alive = 1;
   }
   
   if (verbose) {
     gprintf("probable_eyes_a: %s eyemin: %d eyemax: %d",
             eyevalue_to_string(&probable_eyes_a), eyemin_a, eyemax_a);
     if (I_look_alive)
       gprintf("%o I look alive (%s)", live_reasona);
     gprintf("%o\n");
     gprintf("probable_eyes_b: %s eyemin: %d eyemax: %d",
             eyevalue_to_string(&probable_eyes_b), eyemin_b, eyemax_b);
     if (you_look_alive)
       gprintf("%o you look alive(%s)", live_reasonb);
     gprintf("%o\n");
   }

   /* Stop here if both look certain to live. */
   if (I_look_alive && you_look_alive) {
     *resulta = WIN;
     *resultb = 0;
     *move = PASS_MOVE;
     sgf_dumptree = save_sgf_dumptree;
     count_variations = save_count_variations;
     TRACE("Both live\n");
     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. */
   if (!I_look_alive) {
     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))
         break;
   }
   else
     shape_defensive_moves[0].pos = NO_MOVE;

   if (!you_look_alive) {
     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))
         break;
   }
   else
     shape_offensive_moves[0].pos = NO_MOVE;

   /* Filter out moves, which fill our eye (and not split it). */
   if (eyemax_a > 0) {
     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. 
    */

   if (!I_look_alive) {
     semeai_review_owl_moves(vital_defensive_moves, owla, owlb, color,
                             &safe_outside_liberty_found,
                             &safe_common_liberty_found,
                             &riskless_move_found,
                             mw, moves, 0, 30,
                             critical_semeai_worms);
     
     semeai_review_owl_moves(shape_defensive_moves, owla, owlb, color,
                             &safe_outside_liberty_found,
                             &safe_common_liberty_found,
                             &riskless_move_found,
                             mw, moves, 0, 0,
                             critical_semeai_worms);
   }

   if (!you_look_alive) {
     semeai_review_owl_moves(vital_offensive_moves, owla, owlb, color,
                             &safe_outside_liberty_found,
                             &safe_common_liberty_found,
                             &riskless_move_found,
                             mw, moves, 1, 30,
                             critical_semeai_worms);
     
     semeai_review_owl_moves(shape_offensive_moves, owla, owlb, color,
                             &safe_outside_liberty_found,
                             &safe_common_liberty_found,
                             &riskless_move_found,
                             mw, moves, 1, 0,
                             critical_semeai_worms);
   }

   /* If no moves were found so far, also check the eyespaces when
    * opponent semeai worms are allowed to be included for vital
    * moves.
    */
   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,
                            &eyemin_b, &eyemax_b))
       semeai_review_owl_moves(vital_offensive_moves, owla, owlb, color,
                               &safe_outside_liberty_found,
                               &safe_common_liberty_found,
                               &riskless_move_found,
                               mw, moves, 1, 30,
                               critical_semeai_worms);
     include_semeai_worms_in_eyespace = 0;
   }

   if (eyemin_a == eyemax_a)
     /* We have stable number of eyes, so we can try to reduce
      * opponent eyes.
      */
     I_have_more_eyes = (eyemin_a > min_eyes(&probable_eyes_b));
   else {
     if (min_eyes(&probable_eyes_a) == max_eyes(&probable_eyes_a))
       /* If we can't increase our number of eyes, we try to reduce
        * opponent eyes.
        */
       I_have_more_eyes = (max_eyes(&probable_eyes_a) > min_eyes(&probable_eyes_b));
     else
       /* 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 (get_level() < 8) {
     /* If no owl moves were found on two consecutive moves,
      * turn off the owl phase.
      */
     if (moves[0].pos == NO_MOVE) {
       if (owl_phase == 1)
         owl_phase = 2;
       else if (owl_phase == 2)
         owl_phase = 0;
     }
     else
       owl_phase = 1;
   }
 }

 if (1 && verbose) {
   showboard(0);
   goaldump(owla->goal);
   goaldump(owlb->goal);
 }
 
 /* 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.
  */
 if (!you_look_alive
     && !safe_outside_liberty_found
     && (moves[0].value < 110 || I_have_more_eyes)) {
   int pos;
   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
     if (!ON_BOARD(pos))
       continue;
     
     if (board[pos] == EMPTY && !mw[pos]) {
       if (liberty_of_goal(pos, owlb)) {
         if (!liberty_of_goal(pos, owla)) {
           /* outside liberty */
           if (safe_move(pos, color) == WIN) {
             safe_outside_liberty_found = 1;
             outside_liberty.pos = pos;
             break;
           }
           else if (backfill_outside_liberty.pos == NO_MOVE)
             backfill_outside_liberty.pos = find_semeai_backfilling_move(bpos,
                                                                         pos);
         }
         else {
           /* common liberty */
           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,
                                                                        pos);
         }
       }
     }
   }
 }

 /* 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
  * move.
  */
 if (!you_look_alive) {
   if (safe_outside_liberty_found
       && outside_liberty.pos != NO_MOVE) {
     move_value = semeai_move_value(outside_liberty.pos,
                                    owla, owlb, 50,
                                    critical_semeai_worms);
     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);
     riskless_move_found = 1;
     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,
                                    owla, owlb, 50,
                                    critical_semeai_worms);
     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);
     riskless_move_found = 1;
     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,
                                    owla, owlb, 10,
                                    critical_semeai_worms);
     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))
       riskless_move_found = 1;
     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,
                                    owla, owlb, 10,
                                    critical_semeai_worms);
     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))
       riskless_move_found = 1;
     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);

     if (move) {
       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;
 tested_moves = 0;
 for (k = 0; k < MAX_SEMEAI_MOVES; k++) {
   int mpos = moves[k].pos;
   if (mpos == NO_MOVE)
     break;

   if (moves[k].value == 0)
     continue;

   /* Do not try too many moves. */
   if (tested_moves > 2
       || (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. */
     if (!allpats)
       break;
     else if (trymove(mpos, color, moves[k].name, apos)) {
       semeai_add_sgf_comment(moves[k].value, owl_phase);
       popgo();
     }
     continue;
   }
   
   if (count_variations >= semeai_node_limit
       || stackp >= MAX_SEMEAI_DEPTH)
     continue;

   /* 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,
                                  owl_phase, mpos, color,
                                  best_resulta == 0 || best_resultb == 0,
                                  moves[k].value, moves[k].name,
                                  moves[k].same_dragon, moves[k].pattern_data,
                                  moves[k].lunch, NULL,
                                  &this_resulta, &this_resultb)) {
     tested_moves++;
     if (this_resultb == WIN && this_resulta == WIN) {
       /* Ideal result, no need to try any more moves. */
       *resulta = WIN;
       *resultb = WIN;
       *move = mpos;
       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,
                          move, mpos, WIN, WIN);
     }
     /* 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)))
              || (prefer_ko == color
                  && (this_resultb > best_resultb
                      || (this_resultb == best_resultb
                          && this_resulta > best_resulta)))) {
       best_resulta = this_resulta;
       best_resultb = this_resultb;
       best_move = mpos;
       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
  * lost.
  */
 if (best_resulta == 0 && best_resultb == 0 && you_look_alive) {
   *resulta = 0;
   *resultb = 0;
   *move = PASS_MOVE;
   SGFTRACE_SEMEAI(PASS_MOVE, 0, 0, "You live, I die");
   READ_RETURN_SEMEAI(SEMEAI, apos, bpos, depth - stackp,
                      move, PASS_MOVE, 0, 0);
 }

 /* 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;
   int eyemin_a;
   int eyemax_a;
   for (sworm = 0; sworm < s_worms; sworm++) {
     if (board[semeai_worms[sworm]] == other) {
       if (important_semeai_worms[sworm])
         break;
     }
   }
   
   if (sworm == s_worms) {
     include_semeai_worms_in_eyespace = 1;
     if (!owl_estimate_life(owla, owlb, vital_defensive_moves,
                            &live_reasona, 0, &dummy_eyes,
                            &eyemin_a, &eyemax_a)
         && eyemax_a < 2) {
       include_semeai_worms_in_eyespace = 0;
       *resulta = 0;
       *resultb = 0;
       *move = PASS_MOVE;
       SGFTRACE_SEMEAI(PASS_MOVE, 0, 0, "You live, I die - 2");
       READ_RETURN_SEMEAI(SEMEAI, apos, bpos, depth - stackp,
                          move, PASS_MOVE, 0, 0);
     }
     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 (pass) {
     if (max_eyes(&probable_eyes_a) < min_eyes(&probable_eyes_b)) {
       *resulta = 0;
       *resultb = 0;
       *move = PASS_MOVE;
       TRACE("You have more eyes.\n");
       SGFTRACE_SEMEAI(PASS_MOVE, 0, 0, "You have more eyes");
       READ_RETURN_SEMEAI(SEMEAI, apos, bpos, depth - stackp,
                          move, PASS_MOVE, 0, 0);
     }
     else if (max_eyes(&probable_eyes_b) < min_eyes(&probable_eyes_a)) {
       *resulta = WIN;
       *resultb = WIN;
       *move = PASS_MOVE;
       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);
     }
     else {
       *resulta = WIN;
       *resultb = 0;
       *move = PASS_MOVE;
       TRACE("Seki\n");
       SGFTRACE_SEMEAI(PASS_MOVE, WIN, 0, "Seki");
       READ_RETURN_SEMEAI(SEMEAI, apos, bpos, depth - stackp,
                          move, PASS_MOVE, WIN, 0);
     }
   }
   else {
   /* 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");
     *move = PASS_MOVE;
     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.
  * OOXX.OO.XO
  * ----------
  *
  * In such cases too, we try to pass to see if it doesn't actually yield
  * a better result.
  *
  * FIXME: there might be more cases where passing would be valuable. 
  */
 if (!pass && k == 1) {
   if ((best_resulta == WIN && best_resultb == 0
        && best_move != NO_MOVE
        && 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_move = PASS_MOVE;
       best_resulta = REVERSE_RESULT(this_resulta);
       best_resultb = REVERSE_RESULT(this_resultb);
       best_move_name = "Pass";
     }
   }
 }

 *resulta = best_resulta;
 *resultb = best_resultb;
 if (best_resulta == 0)
   best_move = PASS_MOVE;
 *move = best_move;
 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
* move.
*/
static int
semeai_trymove_and_recurse(int apos, int bpos, struct local_owl_data *owla,
                          struct local_owl_data *owlb,
                          int owl_phase,
                          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)
{
 int ko_move = 0;
 
 gg_assert(this_resulta != NULL && this_resultb != NULL);
 *this_resulta = 0;
 *this_resultb = 0;

 if (!komaster_trymove(move, color, move_name, apos, &ko_move, ko_allowed)) {
   int kpos;
   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 libs[MAX_LIBERTIES];
     int n;
     int nlib;
     int sworm;
     int worm_color;
     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)
           return 0;

         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))
               return 0;

             /* Our dragon has double ko, but we have to check if
              * opponent dragon doesn't have outside liberties or
              * double ko.
              */
             *this_resulta = WIN;
             *this_resultb = WIN;
           }
       }
       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.
            */
           return 0;
       }
     }
     if (*this_resulta == WIN)
       return 1;
   }

   return 0;
 }
 
 semeai_add_sgf_comment(move_value, owl_phase);
 TRACE("Trying %C %1m. Current stack: ", color, move);
 if (verbose) {
   dump_stack();
   goaldump(owla->goal);
   gprintf("\n");
   goaldump(owlb->goal);
   gprintf("\n");
 }
 TRACE("%s, value %d, same_dragon %d\n", move_name, move_value, same_dragon);
   
 push_owl(&owla);
 push_owl(&owlb);

 if (owla->color == color) {
   owl_update_goal(move, same_dragon, lunch, owla, 1, pattern_data);
   owl_update_boundary_marks(move, owlb);
 }
 else {
   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;
 }
 else {
   do_owl_analyze_semeai(bpos, apos, owlb, owla,
                         this_resultb, this_resulta, semeai_move,
                         0, owl_phase);
   *this_resulta = REVERSE_RESULT(*this_resulta);
   *this_resultb = REVERSE_RESULT(*this_resultb);
 }
   
 pop_owl(&owlb);
 pop_owl(&owla);
   
 popgo();
   
 /* Does success require ko? */
 if (ko_move) {
   if (*this_resulta != 0)
     *this_resulta = KO_B;
   if (*this_resultb != 0)
     *this_resultb = KO_B;
 }
   
 if (count_variations >= semeai_node_limit) {
   TRACE("Out of nodes, claiming win.\n");
   result_certain = 0;
   *this_resulta = WIN;
   *this_resultb = WIN;
 }
 return 1;
}

/* Add details in sgf file about move value and whether owl_phase is active. */
static void
semeai_add_sgf_comment(int value, int owl_phase)
{
 char buf[100];

 if (!sgf_dumptree)
   return;
 
 if (owl_phase)
   gg_snprintf(buf, 100, "value %d, owl_phase", value);
 else
   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
* untrustworthy.
*
* This function decides whether an attack should be trusted. It does
* not check whether there actually is an attack, though.
*/
static int
semeai_trust_tactical_attack(int str)
{
 int liberties;
 int libs[3];
 int other = OTHER_COLOR(board[str]);
 
 liberties = findlib(str, 3, libs);
 if (liberties > 2)
   return 0;

 if (liberties < 2)
   return 1;

 if (!is_self_atari(libs[0], other)
     || !is_self_atari(libs[1], other))
   return 1;

 return 0;
}


/* 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
* dragon.
*/
static int
semeai_is_riskless_move(int move, struct local_owl_data *owla)
{
 int k;
 int liberties = accuratelib(move, owla->color, MAXLIBS, NULL);
 if (!liberty_of_goal(move, owla))
   return 1;
 for (k = 0; k < 4; k++) {
   int pos = move + delta[k];
   if (board[pos] == owla->color
       && owla->goal[pos]
       && countlib(pos) > liberties)
     return 0;
 }
 return 1;
}


/* 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
* in the semeai.
*/
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)
{
 int move;
 int move_value;
 enum same_dragon_value same_dragon;
 struct matched_pattern_data *pattern_data = NULL;
 int k;
 
 for (k = 0; k < MAX_MOVES-1; k++) {
   move = owl_moves[k].pos;
   if (move == NO_MOVE)
     break;

   if (owl_moves[k].value == 0)
     continue;

   /* 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;
     else
       *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 (guess_same_dragon) {
     if (liberty_of_goal(move, owla)
         || second_liberty_of_goal(move, owla))
       same_dragon = SAME_DRAGON_MAYBE_CONNECTED;
     else
       same_dragon = SAME_DRAGON_NOT_CONNECTED;
   }
   else {
     same_dragon = owl_moves[k].same_dragon;
     pattern_data = owl_moves[k].pattern_data;
   }

   mw[move] = 1;
   move_value = (semeai_move_value(move, owla, owlb, owl_moves[k].value,
                                   critical_semeai_worms)
                 + value_bonus);
   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 '.':
*
*       XXX
*      XXOX
*      XOOX
*      X.*X
*      ----
*/
static int
semeai_propose_eyespace_filling_move(struct local_owl_data *owla,
                                    struct local_owl_data *owlb)
{
 int color = OTHER_COLOR(owlb->color);
 int pos;
 int mw[BOARDMAX];
 int mz[BOARDMAX];

 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;

     if (mw[origin] > 1
         && min_eyes(&owlb->my_eye[origin].value) == 1) {
       int good_move = 0;

       if (trymove(pos, color, "eyespace_filling", NO_MOVE)) {
         struct eyevalue new_value;
         int dummy_attack;
         int dummy_defense;

         compute_eyes(origin, &new_value, &dummy_attack, &dummy_defense,
                      owlb->my_eye, owlb->half_eye, 0);
         if (max_eyes(&new_value) <= 1)
           good_move = 1;

         popgo();
       }

       if (good_move)
         return pos;
     }
   }
 }

 return NO_MOVE;
}


/* 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.
*/

static int
semeai_move_value(int move, struct local_owl_data *owla,
                 struct local_owl_data *owlb,
                 int raw_value, int *critical_semeai_worms)
{
 int pos;
 int net = 0;
 int color = owla->color;
 int save_verbose = verbose;
 int k;
 int bonus = 0;

 ASSERT1(board[move] == EMPTY, move);
 verbose = 0;
 if (safe_move(move, color)) {
   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
     if (IS_STONE(board[pos])
         && pos == find_origin(pos)) {
       int count_lib = -1;
       if (owla->goal[pos]) {
         count_lib = countlib(pos);
         net -= 75 * count_lib;
       }
       if (owlb->goal[pos]) {
         if (count_lib < 0)
           count_lib = countlib(pos);
         net += 100 * count_lib;
       }
     }
   }
   if (!trymove(move, color, NULL, 0)) {
     verbose = save_verbose;
     return 0;
   }
   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
     if (IS_STONE(board[pos])
         && pos == find_origin(pos)) {
       int count_lib = -1;
       if (owla->goal[pos]
           || (pos == move && liberty_of_goal(move, owla))) {
         count_lib = countlib(pos);
         net += 75 * count_lib;
       }
       if (owlb->goal[pos]) {
         if (count_lib < 0)
           count_lib = countlib(pos);
         net -= 100 * count_lib;
       }
     }
   }

   increase_depth_values();
   for (k = 0; k < s_worms; k++) {
     if (!critical_semeai_worms[k])
       continue;
     if (board[semeai_worms[k]] == color
         && !attack(semeai_worms[k], NULL))
       bonus += 50;
     else if (board[semeai_worms[k]] == OTHER_COLOR(color)
              && !find_defense(semeai_worms[k], NULL))
       bonus += 50;
   }
   decrease_depth_values();
   
   popgo();
 }

 verbose = save_verbose;

 if (net < 0)
   net = 0;

 net /= 25;
 net *= 3;
 
 return raw_value + net + bonus;
}


/* Remove all moves from the list that would fill our own eye. */
static void
remove_eye_filling_moves(struct local_owl_data *our_owl,
                        struct owl_move_data *moves)
{
 int k;
 int color = our_owl->color;

 for (k = 0; k < MAX_MOVES; k++) {
   if (moves[k].pos == NO_MOVE)
     break;
   else {
     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
      * proposed).
      */
     if (eye->color == color && eye->msize == 0 && eye->neighbors <= 1
         && eye->esize != 1
         && our_owl->half_eye[moves[k].pos].type != HALF_EYE
         && !has_neighbor(moves[k].pos, OTHER_COLOR(color)))
       moves[k].value = 0;
   }
 }
}

/* Is the vertex at pos adjacent to an element of the owl goal? */
static int
liberty_of_goal(int pos, struct local_owl_data *owl)
{
 int k;
 for (k = 0; k < 4; k++)
   if (IS_STONE(board[pos + delta[k]]) && owl->goal[pos + delta[k]])
     return 1;
 
 return 0;
}

/* Is the vertex at pos a second liberty of the owl goal? */
static int
second_liberty_of_goal(int pos, struct local_owl_data *owl)
{
 int k;
 for (k = 0; k < 4; k++)
   if (board[pos + delta[k]] == EMPTY && liberty_of_goal(pos + delta[k], owl))
     return 1;
 
 return 0;
}


/* '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:
*
*   ------+
*   O.OaXc|
*   OOOOOX|
*   XXXXXb|
*   ......|
*
* 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.
*/

static int
find_semeai_backfilling_move(int worm, int liberty)
{
 int color = board[worm];
 int other = OTHER_COLOR(color);
 int result = NO_MOVE;

 if (safe_move(liberty, other) == WIN)
   return liberty;
 if (is_self_atari(liberty, other)) {
   int fill;
   if (approxlib(liberty, other, 1, &fill) > 0
       && trymove(fill, other, "find_semeai_backfilling_move", worm)) {
     if (safe_move(liberty, other))
       result = fill;
     else if (board[worm] != EMPTY)
       result = find_semeai_backfilling_move(worm, liberty);
     popgo();
   }
 }
 if (ON_BOARD(result) && safe_move(result, other))
   return result;
 else
   return NO_MOVE;
}

/* Some helper function for do_owl_attack/defend. */

static int
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",
         this_variation_number);
   *live_reason = "max reading depth reached";
   return 1;
 }
 /* If the owl node limit has been reached, assume the dragon has
  * managed to escape.
  */
 if (local_owl_node_counter >= owl_node_limit) {
   result_certain = 0;
   TRACE("%oVariation %d: ALIVE (owl node limit reached)\n",
         this_variation_number);
   *live_reason = "owl node limit reached";
   return 1;
 }
 return 0;
}

static void
clear_owl_move_data(struct owl_move_data moves[MAX_MOVES])
{
 int k;
 for (k = 0; k < MAX_MOVES; k++) {
   moves[k].pos = NO_MOVE;
   moves[k].value = -1;
   moves[k].name = NULL;
   moves[k].same_dragon = SAME_DRAGON_CONNECTED;
   moves[k].escape = 0;
   moves[k].lunch = NO_MOVE;
   moves[k].pattern_data = NULL;
   clear_cut_list(moves[k].cuts);
 }
}

static void
set_single_owl_move(struct owl_move_data moves[MAX_MOVES],
                   int pos, const char *name)
{
 moves[0].pos          = pos;
 moves[0].value        = 25;
 moves[0].name         = name;
 moves[0].same_dragon  = SAME_DRAGON_MAYBE_CONNECTED;
 moves[0].escape       = 0;
 moves[0].lunch        = NO_MOVE;
 moves[0].pattern_data = NULL;
 clear_cut_list(moves[0].cuts);
 moves[1].value        = 0;
}


/* 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.
*
* */

int
owl_attack(int target, int *attack_point, int *certain, int *kworm)
{
 int result;
 struct local_owl_data *owl;
 int reading_nodes_when_called = get_reading_node_counter();
 double start = 0.0;
 int tactical_nodes;
 int move = NO_MOVE;
 int wpos = NO_MOVE;
 int wid = MAX_GOAL_WORMS;

 result_certain = 1;
 if (worm[target].unconditional_status == DEAD) {
   if (attack_point)
     *attack_point = NO_MOVE;
   if (kworm)
     *kworm = NO_MOVE;
   if (certain)
     *certain = 1;
   return 1;
 }

 if (search_persistent_owl_cache(OWL_ATTACK, target, 0, 0, &result,
                                 attack_point, kworm, certain))
   return result;

 if (debug & DEBUG_OWL_PERFORMANCE)
   start = gg_cputime();
 
 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,
                   kworm, 1);
 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, move, wpos,
                            result_certain, tactical_nodes,
                            owl->goal, board[target]);
 if (attack_point)
   *attack_point = move;
 if (kworm)
   *kworm = wpos;
 if (certain)
   *certain = result_certain;

 return result;
}


/* Static function containing the main recursive code for 
* owl_attack.
*/

static int
do_owl_attack(int str, int *move, int *wormid,
             struct local_owl_data *owl, int escape)
{
 int color = board[str];
 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 pass;
 int k;
 int savemove = 0;
 int saveworm = MAX_GOAL_WORMS;
 int savecode = 0;
 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. */
 const char *live_reason;
 int move_cutoff;
 int xpos;
 int value1;
 int value2;
 int this_variation_number = count_variations - 1;
 
 SETUP_TRACE_INFO("owl_attack", str);

 shape_patterns.initialized = 0;

 str = find_origin(str);

 if (tt_get(&ttable, OWL_ATTACK, str, NO_MOVE, depth - stackp, NULL, 
            &value1, &value2, &xpos) == 2) {

   TRACE_CACHED_RESULT(value1, xpos);
   if (move)
     *move = xpos;

   if (value1 == GAIN) {
     if (wormid) {
       if (goal_worms_computed)
         *wormid = value2;
       else
         *wormid = MAX_GOAL_WORMS;
     }
   }
   
   if (value1 == WIN)
     TRACE("%oVariation %d: DEAD (cached)\n", this_variation_number);
   else
     TRACE("%oVariation %d: ALIVE (cached)\n", this_variation_number);
   
   SGFTRACE(xpos, value1, "cached");
   
   return value1;
 }


 /* 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++;

 current_owl_data = owl;
 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.
    */
   int acode = 0;
   int mpos = NO_MOVE;
   if (experimental_owl_ext && goal_worms_computed) {
     int size = 0;
     saveworm = MAX_GOAL_WORMS;
     for (k = 0; k < MAX_GOAL_WORMS; k++) {
       if (owl_goal_worm[k] == NO_MOVE)
         break;
       if (board[owl_goal_worm[k]] == EMPTY
           || countlib(owl_goal_worm[k]) > 1)
         continue;
       if (worm[owl_goal_worm[k]].size > size) {
         saveworm = k;
         size = worm[owl_goal_worm[k]].size;
       }
     }
     if (saveworm != MAX_GOAL_WORMS && size >= 3) {
       acode = GAIN;
       findlib(worm[owl_goal_worm[saveworm]].origin, 1, &mpos);
       /* ASSERT1( ... */
     }
   }
   SGFTRACE(0, acode, live_reason);
   TRACE("%oVariation %d: ALIVE (%s)\n", this_variation_number, live_reason);
   if (acode == 0) {
     READ_RETURN(OWL_ATTACK, str, depth - stackp, move, 0, 0);
   }
   else {
     if (wormid)
       *wormid = saveworm;
     READ_RETURN2(OWL_ATTACK, str, depth - stackp,
                  move, mpos, acode, saveworm);
   }
 }

 /* We try moves in five passes.
  *                                stackp==0   stackp>0
  * 0. Vital moves in the interval  [70..]      [45..]
  * 1. Shape moves
  * 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++) {
   moves = NULL;
   move_cutoff = 1;
   
   current_owl_data = owl;
   /* Get the shape moves if we are in the right pass. */
   switch (pass) {
   case 1:
     if (stackp > owl_branch_depth && number_tried_moves > 0)
       continue;
     
     owl_shapes(&shape_patterns, shape_moves, other, owl, &owl_attackpat_db);
     moves = shape_moves;
     break;

   case 0:
   case 2:
     if (stackp > owl_branch_depth && number_tried_moves > 0)
       continue;
     
     moves = vital_moves;
     if (pass == 0 || stackp > owl_distrust_depth) {
       if (stackp == 0)
         move_cutoff = 70;
       else
         move_cutoff = 45;
     }
     if (eyemax < 2 && stackp > 2)
       move_cutoff = 99; /* Effectively disable vital moves. */
     break;

   case 3:
   case 5:
     {
       /* 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.
        */
       int apos;
       int result;
       SGFTree *save_sgf_dumptree = sgf_dumptree;
       int save_count_variations = count_variations;

       sgf_dumptree = NULL;
       count_variations = 0;
       result = attack(str, &apos);
       if (result == WIN
           || (result != 0 && (min_eyes(&probable_eyes) >= 2
                               || pass == 5))) {
         set_single_owl_move(shape_moves, apos, "tactical attack");
         moves = shape_moves;
       }
       sgf_dumptree = save_sgf_dumptree;
       count_variations = save_count_variations;
     }
     break;

   /* If we found no move in the first four passes we ask the defender
    * for a move suggestion.
    */
   case 4:
     if (number_tried_moves == 0) {
       int dpos;
       int dcode = do_owl_defend(str, &dpos, NULL, owl, escape);
       /* No defense, we won. */
       if (dcode == 0) {
         TRACE("%oVariation %d: DEAD (no defense)\n",
               this_variation_number);
         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
          * attack with this move.
          *
          * 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;

         sgf_dumptree = NULL;
         count_variations = 0;

         if (is_suicide(dpos, other) || send_two_return_one(dpos, other)) {
           int dpos2;
           for (k = 0; k < 4; k++) {
             if (board[dpos + delta[k]] == other
                 && find_defense(dpos + delta[k], &dpos2)) {
               dpos = dpos2;
               name = "defense move (backfill)";
               break;
             }
           }
         }

         sgf_dumptree = save_sgf_dumptree;
         count_variations = save_count_variations;
       
         if (dpos != NO_MOVE) {
           set_single_owl_move(shape_moves, dpos, name);
           moves = shape_moves;
         }
       }
     }
     break;
   } /* switch (pass) */
     

   /* FIXME: This block probably should reappear somewhere in this
    * function.
    */
#if 0
   /* 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
      * escaping.
      */
     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);
   }
#endif

   if (!moves)
     continue;
   
   /* 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
    * can then be defended.
    */
   for (k = 0; k < MAX_MOVES; k++) {
     int mpos;
     int ko_move = -1;
     int origin = NO_MOVE;
     int captured;
     int wid = MAX_GOAL_WORMS;
     int dcode;

     /* Consider only the highest scoring move if we're deeper than
      * owl_branch_depth.
      *
      * FIXME: To behave as intended, k should be replaced by
      *        number_tried_moves.
      */
     if (stackp > owl_branch_depth && k > 0)
       break;

     current_owl_data = owl;

     /* Shape moves are selected on demand. */
     if (pass == 1) {
       if (!get_next_move_from_list(&shape_patterns, other,
                                    shape_moves, move_cutoff, owl))
         break;
     }
     else
       if (moves[k].value < move_cutoff)
         break;

     mpos = moves[k].pos;
     ASSERT_ON_BOARD1(mpos);
   
     /* Have we already tested this move? */
     if (mw[mpos])
       continue;

     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))
       continue;

     captured = (color == WHITE ? white_captured : black_captured) - captured;

     TRACE("Trying %C %1m. Escape = %d. Current stack: ",
           other, mpos, escape);
     if (verbose)
       dump_stack();

     /* We have now made a move. Analyze the new position. */
     push_owl(&owl);
     mw[mpos] = 1;
     number_tried_moves++;
     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 = str;
     else
       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);
       if (!owl->goal[origin])
         origin = select_new_goal_origin(origin, owl);
     }
     mark_goal_in_sgf(owl->goal);

     if (origin == NO_MOVE)
       dcode = 0;
     else
       dcode = do_owl_defend(origin, NULL, &wid, owl, escape);

     if (!ko_move) {
       if (dcode == 0) {
         pop_owl(&owl);
         popgo();
         if (sgf_dumptree) {
           const char *wintxt;
           char winstr[192];
           if (origin == NO_MOVE)
             wintxt = "all original stones captured";
           else
             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)
           saveworm = wid;
       }
       /* 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
#if 0
                && stackp > 1
#endif
                && captured >= 3) {
         int w = MAX_GOAL_WORMS;
         int size = 0;
         int l;
         /* locate the biggest captured worm */
         for (l = 0; l < MAX_GOAL_WORMS; l++) {
           if (owl_goal_worm[l] == NO_MOVE)
             break;
           if (board[owl_goal_worm[l]] == EMPTY)
             if (size == 0 || worm[owl_goal_worm[l]].size > size) {
               w = l;
               size = worm[owl_goal_worm[l]].size;
             }
         }
         if (w != MAX_GOAL_WORMS) {
           if (GAIN > savecode) {
             /* if new result better, just update */
             dcode = LOSS;
             saveworm = w;
           }
           else if (GAIN == savecode) {
             /* bigger ? */
             int wpos = owl_goal_worm[saveworm];
             if (size > worm[wpos].size)
               saveworm = w;
           }
         }
       }
       UPDATE_SAVED_KO_RESULT(savecode, savemove, dcode, mpos);
     }
     else { /* ko_move */
       if (dcode != WIN) {
         if (mpos == 0) {
           SGFTRACE(mpos, KO_B, "all original stones captured with ko");
         }
         else {
           SGFTRACE(mpos, KO_B, "attack effective - ko");
         }
         /* We already know the savecode was previously 0. */
         savemove = mpos;
         savecode = KO_B;

         /* 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.
          */
         number_tried_moves--;
       }
     }
   
     pop_owl(&owl);
     popgo();
   }
 }

 close_pattern_list(other, &shape_patterns);
 
 if (savecode) {
   if (savecode == GAIN) {
     SGFTRACE(savemove, savecode, "attack effective (gain) - E");
     if (wormid)
       *wormid = saveworm;
     READ_RETURN2(OWL_ATTACK, str, depth - stackp,
                  move, savemove, savecode, saveworm);
   }
   else {
     SGFTRACE(savemove, savecode, "attack effective (ko) - E");
     READ_RETURN(OWL_ATTACK, str, depth - stackp, move, savemove, savecode);
   }
 }

 if (sgf_dumptree) {
   char winstr[128];
   sprintf(winstr, "attack failed)\n  (%d variations",
                   count_variations - this_variation_number);
   SGFTRACE(0, 0, winstr);
 }
 
 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).
*/

int
owl_threaten_attack(int target, int *attack1, int *attack2)
{
 struct owl_move_data moves[MAX_MOVES];
 int k;
 int other = OTHER_COLOR(board[target]);
 struct local_owl_data *owl;
 int result = 0;
 int reading_nodes_when_called = get_reading_node_counter();
 signed char saved_boundary[BOARDMAX];
 double start = 0.0;
 int tactical_nodes;
 int move = 0;
 int move2 = 0;
 struct matched_patterns_list_data shape_patterns;

 shape_patterns.initialized = 0;
 result_certain = 1;
 if (search_persistent_owl_cache(OWL_THREATEN_ATTACK, target, 0, 0,
                                 &result, attack1, attack2, NULL))
   return result;

 if (debug & DEBUG_OWL_PERFORMANCE)
   start = gg_cputime();
 
 gg_assert(stackp == 0);
 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++) {
   current_owl_data = owl;
   if (!get_next_move_from_list(&shape_patterns, other, moves, 1, owl))
     break;
   else {
     int mpos = moves[k].pos;

     if (mpos != NO_MOVE && moves[k].value > 0)
       if (trymove(mpos, other, moves[k].name, target)) {
         int pos;
         int origin = NO_MOVE;
         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);
               break;
             }
           }
           
           if (origin == NO_MOVE
               || do_owl_attack(origin, NULL, NULL, owl, 0)) {
             /* probably this can't happen */
             popgo();
             gg_assert(stackp == 0);
             result = 1;
             break;
           }
         }
         else if (do_owl_attack(target, &move2, NULL, owl, 0) == WIN) {
           move = moves[k].pos;
           popgo();
           gg_assert(stackp == 0);
           result = 1;
           break;
         }
         popgo();
         memcpy(owl->boundary, saved_boundary, sizeof(saved_boundary));
       }
   }
 }
 tactical_nodes = get_reading_node_counter() - reading_nodes_when_called;
 gg_assert(stackp == 0);

 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,
                            result, move, move2, 0,
                            tactical_nodes, owl->goal, board[target]);

 if (attack1)
   *attack1 = move;
 if (attack2)
   *attack2 = move2;

 close_pattern_list(other, &shape_patterns);
 return result;
}


/* 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.  
*/

int
owl_defend(int target, int *defense_point, int *certain, int *kworm)
{
 int result;
 static struct local_owl_data *owl;
 int reading_nodes_when_called = get_reading_node_counter();
 double start = 0.0;
 int tactical_nodes;
 int move = NO_MOVE;
 int wpos = NO_MOVE;
 int wid = MAX_GOAL_WORMS;

 result_certain = 1;
 if (worm[target].unconditional_status == DEAD)
   return 0;

 if (search_persistent_owl_cache(OWL_DEFEND, target, 0, 0, &result, 
                                 defense_point, kworm, certain))
   return result;

 if (debug & DEBUG_OWL_PERFORMANCE)
   start = gg_cputime();

 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,
                   kworm, 1);
 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,
                            board[target]);

 if (defense_point)
   *defense_point = move;
 if (kworm)
   *kworm = wpos;
 if (certain)
   *certain = result_certain;
 
 return result;
}


/* Static function containing the main recursive code for owl_defend.
*/

static int
do_owl_defend(int str, int *move, int *wormid, struct local_owl_data *owl,
             int escape)
{
 int color = board[str];
 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 pass;
 int k;
 int savemove = 0;
 int saveworm = MAX_GOAL_WORMS;
 int savecode = 0;
 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 escape_route;
 const char *live_reason;
 int move_cutoff;
 int xpos;
 int value1;
 int value2;
 int this_variation_number = count_variations - 1;

 SETUP_TRACE_INFO("owl_defend", str);

 shape_patterns.initialized = 0;
 
 str = find_origin(str);

 if (tt_get(&ttable, OWL_DEFEND, str, NO_MOVE, depth - stackp, NULL, 
            &value1, &value2, &xpos) == 2) {
   
   TRACE_CACHED_RESULT(value1, xpos);
   if (move)
     *move = xpos;

   if (value1 == LOSS) {
     if (wormid) {
       if (goal_worms_computed)
         *wormid = value2;
       else
         *wormid = MAX_GOAL_WORMS;
     }
   }

   if (value1 == WIN || value1 == LOSS)
     TRACE("%oVariation %d: ALIVE (cached)\n", this_variation_number);
   else
     TRACE("%oVariation %d: DEAD (cached)\n", this_variation_number);

   SGFTRACE(xpos, value1, "cached");

   return value1;
 }

 /* 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
  *        this hardwired value.
  */
 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
    * escaping.
    */
   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++;

 current_owl_data = owl;
 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);
   }
 }
 else {
   /* 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
    * state of eyes.
    */
   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].pos = 0;
   vital_moves[0].value = -1;
   set_eyevalue(&probable_eyes, 0, 0, 0, 0);
 }

 /* We try moves in four passes.
  *                                stackp==0   stackp>0
  * 0. Vital moves in the interval  [70..]      [45..]
  * 1. Shape moves
  * 2. Vital moves in the interval  [..69]      [..44]
  * 3. Tactical defense moves
  */
 for (pass = 0; pass < 4; pass++) {
   moves = NULL;
   move_cutoff = 1;
   
   current_owl_data = owl;
   switch (pass) {
   /* Get the shape moves if we are in the right pass. */
   case 1:
     
     if (stackp > owl_branch_depth && number_tried_moves > 0)
       continue;
     
     owl_shapes(&shape_patterns, shape_moves, color, owl, &owl_defendpat_db);
     moves = shape_moves;
     break;

   case 0:
   case 2:
     if (stackp > owl_branch_depth && number_tried_moves > 0)
       continue;
     
     moves = vital_moves;
     if (pass == 0 || stackp > owl_distrust_depth) {
       if (stackp == 0)
         move_cutoff = 70;
       else if (eyemin + min_eyes(&probable_eyes) > 3)
         move_cutoff = 25;
       else if (eyemin + min_eyes(&probable_eyes) >= 3)
         move_cutoff = 35;
       else
         move_cutoff = 45;
     }
     if (eyemax < 2 && stackp > 2)
       move_cutoff = 99; /* Effectively disable vital moves. */
     break;

   case 3:
     {
       int goalcount = 0;

       /* If the goal is small, try a tactical defense. */

       for (k = BOARDMIN; k < BOARDMAX; k++)
         if (ON_BOARD(k))
           goalcount += owl->goal[k];

       if (goalcount < 5) {

         /* 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.
          */
         int dpos;
         SGFTree *save_sgf_dumptree = sgf_dumptree;
         int save_count_variations = count_variations;

         sgf_dumptree = NULL;
         count_variations = 0;
         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");
           moves = shape_moves;
         }
         sgf_dumptree = save_sgf_dumptree;
         count_variations = save_count_variations;
       }
       if (!moves)
         continue;
     }
   } /* switch (pass) */

   /* 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
    * can then be attacked.
    */
   for (k = 0; k < MAX_MOVES; k++) {
     int mpos;
     int ko_move = -1;
     int new_escape;
     int wid = MAX_GOAL_WORMS;
     
     /* Consider only the highest scoring move if we're deeper than
      * owl_branch_depth.
      *
      * FIXME: To behave as intended, k should be replaced by
      *        number_tried_moves.
      */
     if (stackp > owl_branch_depth && k > 0)
       break;
     
     current_owl_data = owl;
     
     if (pass == 1) {
       if (!get_next_move_from_list(&shape_patterns, color, shape_moves,
                                    move_cutoff, owl))
         break;
     }
     else
       if (moves[k].value < move_cutoff)
         break;
     
     mpos = moves[k].pos;
     modify_eyefilling_move(&mpos, color);
     ASSERT_ON_BOARD1(mpos);
     
     /* Have we already tested this move? */
     if (mw[mpos])
       continue;
     
     /* Try to make the move. */
     if (!komaster_trymove(mpos, color, moves[k].name, str,
                           &ko_move, savecode == 0))
       continue;

     new_escape = escape;
     if (moves[k].escape)
       new_escape++;

     TRACE("Trying %C %1m. Escape = %d. Current stack: ",
           color, mpos, escape);
     if (verbose)
       dump_stack();

     /* We have now made a move. Analyze the new position. */
     push_owl(&owl);
     mw[mpos] = 1;
     number_tried_moves++;

     /* 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,
                     moves[k].pattern_data);
     mark_goal_in_sgf(owl->goal);

     if (!ko_move) {
       int acode = do_owl_attack(str, NULL, &wid, owl, new_escape);
       if (!acode) {
         pop_owl(&owl);
         popgo();
         if (sgf_dumptree) {
           char winstr[192];
           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);
       }
       if (acode == GAIN)
         saveworm = wid;
       UPDATE_SAVED_KO_RESULT(savecode, savemove, acode, mpos);
     }
     else {
       if (do_owl_attack(str, NULL, NULL, owl, new_escape) != WIN) {
         savemove = mpos;
         savecode = KO_B;
       }
     }
     
     /* Undo the tested move. */
     pop_owl(&owl);
     popgo();
   }
 }

 close_pattern_list(color, &shape_patterns);
 
 if (savecode) {
   if (savecode == LOSS) {
     SGFTRACE(savemove, savecode, "defense effective (loss) - B");
     if (wormid)
       *wormid = saveworm;
     READ_RETURN2(OWL_DEFEND, str, depth - stackp,
                  move, savemove, savecode, saveworm);
   }
   else {
     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);
 }
 

 if (sgf_dumptree) {
   char winstr[196];
   int print_genus = eyemin == 1 ? 1 : 0;
   sprintf(winstr, "defense failed - genus %d)\n  (%d variations",
                   print_genus, count_variations - this_variation_number);
   SGFTRACE(0, 0, winstr);
 }

 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).
*/

int
owl_threaten_defense(int target, int *defend1, int *defend2)
{
 struct owl_move_data moves[MAX_MOVES];
 int k;
 int color = board[target];
 int result = 0;
 struct local_owl_data *owl;
 int reading_nodes_when_called = get_reading_node_counter();
 signed char saved_goal[BOARDMAX];
 double start = 0.0;
 int tactical_nodes;
 int move = 0;
 int move2 = 0;
 struct matched_patterns_list_data shape_patterns;

 shape_patterns.initialized = 0;

 result_certain = 1;
 if (worm[target].unconditional_status == DEAD)
   return 0;

 if (search_persistent_owl_cache(OWL_THREATEN_DEFENSE, target, 0, 0,
                                 &result, defend1, defend2, NULL))
   return result;

 if (debug & DEBUG_OWL_PERFORMANCE)
   start = gg_cputime();

 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++) {
   current_owl_data = owl;
   if (!get_next_move_from_list(&shape_patterns, color, moves, 1, owl))
     break;
   else {
     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) {
           move = moves[k].pos;
           popgo();
           /* Don't return the second move if occupied before trymove */
           if (move2 != NO_MOVE && IS_STONE(board[move2]))
             move2 = NO_MOVE;
           result = WIN;
           break;
         }
         else
           popgo();
         memcpy(owl->goal, saved_goal, sizeof(saved_goal));
       }
   }
 }
 tactical_nodes = get_reading_node_counter() - reading_nodes_when_called;
 gg_assert(stackp == 0);

 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,
                            result, move, move2, 0,
                            tactical_nodes, owl->goal, board[target]);

 if (defend1)
   *defend1 = move;
 if (defend2)
   *defend2 = move2;

 close_pattern_list(color, &shape_patterns);
 return result;
}



/*
* 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
* be considered alive.
*/
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, 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);

 sgf_dumptree = NULL;
 count_variations = 0;

 owl_determine_life(owl, second_owl, does_attack, vital_moves,
                    probable_eyes, eyemin, eyemax);

 matches_found = 0;
 memset(found_matches, 0, sizeof(found_matches));

 if (get_level() >= 8) {
   memset(owl->safe_move_cache, 0, sizeof(owl->safe_move_cache));
   if (!does_attack) {
     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;
 else
   *eyemin = 0;

 sgf_dumptree = save_sgf_dumptree;
 count_variations = save_count_variations;

 if (*eyemin >= 2
     || (*eyemin == 1 && min_eyes(probable_eyes) >= 4)
     || (stackp > owl_distrust_depth
         && min_eyes(probable_eyes) >= 2
         && !matches_found)) {
   if (*eyemin >= 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
            && !matches_found)
     *live_reason = "getting deep, looks lively";
   else
     gg_assert(0);
   return 1;
 }

 if (!does_attack
     && (*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);
 }

 return 0;
}


/* 
* 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.
*/

static void
owl_determine_life(struct local_owl_data *owl,
                  struct local_owl_data *second_owl,
                  int does_attack,
                  struct owl_move_data *moves,
                  struct eyevalue *probable_eyes, int *eyemin, int *eyemax)
{
 int color = owl->color;
 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];
 int dummy_eyemin = 0;
 int dummy_eyemax = 0;
 struct eyevalue eyevalue;
 struct eyevalue eyevalue_list[BOARDMAX/2];
 int eyes_attack_points[BOARDMAX/2];
 int pessimistic_min;
 int attack_point;
 int defense_point;
 int pos;
 int k;
 int lunch;
 int num_eyes = 0;
 int num_lunches = 0;
 int save_debug = debug;
 memset(vital_values, 0, sizeof(vital_values));

 if (!eyemin)
   eyemin = &dummy_eyemin;
 if (!eyemax)
   eyemax = &dummy_eyemax;

 *eyemin = 0;
 *eyemax = 0;
 
 /* Turn off eye debugging if we're not also debugging owl. */
 if (!(debug & DEBUG_OWL))
   debug &= ~DEBUG_EYES;
 
 clear_owl_move_data(moves);
 
 if (!owl->lunches_are_current)
   owl_find_lunches(owl);
 
 if (0) {
   for (k = 0; k < MAX_LUNCHES; k++)
     if (owl->lunch[k] != NO_MOVE)
       gprintf("owl lunch %1m, attack %1m, defend %1m\n",
               owl->lunch[k],
               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++) {
   if (ON_BOARD(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) {
     int value = 0;
     const char *reason = "";
     compute_eyes_pessimistic(pos, &eyevalue, &pessimistic_min,
                              &attack_point, &defense_point,
                              eye, owl->half_eye);

     /* 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
      * of compute_eyes().
      *
      * (Obviously this is a quite fuzzy heuristic. With more accurate
      * connection analysis in the owl code we could do this more robustly.)
      */
     if (mw[pos] < mz[pos]
         || (mw[pos] < 3 * mz[pos] && mz[pos] > 5))
       pessimistic_min = 0;

     /* It appears that this policy is needed no longer. */
#if 0
     /* 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++) {
         if (ON_BOARD(pos2)
             && eye[pos2].origin == pos
             && owl->inessential[pos2]) {
           pessimistic_min = 0;
           break;
         }
       }
     }
#endif

     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
      * sufficient.
      * 2. This part of the code is in no way time critical.
      */
#if 0
     /* Found two certain eyes---look no further. */
     if (*eyemin >= 2) {
       debug = save_debug;
       return 2;
     }
#endif

     if (eye_move_urgency(&eyevalue)) {
       value = 50;
       if (max_eyes(&eyevalue) - min_eyes(&eyevalue) == 2)
         value = 70;
       else if (max_eyes(&eyevalue) - pessimistic_min == 2)
         value = 60;
       reason = "vital move";
     }
     else if (max_eyes(&eyevalue) != pessimistic_min) {
       if (max_eyes(&eyevalue) - pessimistic_min == 2)
         value = 40;
       else
         value = 30;
       reason = "marginal eye space";
     }

     if (value > 0) {
       if (does_attack && attack_point != NO_MOVE) {
         if (vital_values[attack_point] > 0) {
           value += vital_values[attack_point];
           if (value > 98)
             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",
                 attack_point);

         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
        *
        * |XXX.
        * |OOX.
        * |.OX.
        * |XOXX
        * |XOOX
        * |O*OX
        * +----
        *
        * but it's okay in this position
        * 
        * |XXXXX
        * |....X
        * |OOOOX
        * |.XXOX
        * |.*XOX
        * +-----
        *
        * 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.
        */
       else if (!does_attack
                && 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];
           if (value > 98)
             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",
                 defense_point);

         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;
         }
       }
     }
     num_eyes++;
   }
 }

 /* 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
  * space.
  */
 {
   for (lunch = 0; (lunch < MAX_LUNCHES); lunch++)
     if (owl->lunch[lunch] != NO_MOVE
         && owl->lunch_defense_point[lunch] != NO_MOVE) {
       int value = 0;
       int lunch_min;
       int lunch_probable;
       int lunch_max;
       struct eyevalue e;
       sniff_lunch(owl->lunch[lunch], 
                   &lunch_min, &lunch_probable, &lunch_max, owl);

       set_eyevalue(&e, 0, 0, lunch_probable, lunch_probable);
       *eyemax += lunch_max;

       if (lunch_probable == 0) {
         if (countstones(owl->lunch[lunch]) == 1)
           continue;
         value = 20;
       }
       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]);
       else
         value = 75 + countstones(owl->lunch[lunch]);

       if (owl->lunch_attack_code[lunch] != WIN)
         value -= 10;

       if (does_attack) {
         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.
            */
           int ne;
           for (ne = 0; ne < num_eyes - num_lunches; ne++)
             if (eyes_attack_points[ne] == defense_point)
               break;
           gg_assert(ne < num_eyes - num_lunches);
           /* merge eye values */
           add_eyevalues(&eyevalue_list[ne], &e, &eyevalue_list[ne]);
           /* and adjust */
           eyevalue_list[ne].a = 0;
           eyevalue_list[ne].b = 0;
         } 
         else {
           num_lunches++;
           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);
       }
       else {
         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);
         else
           owl_add_move(moves, attack_point, value, "eat lunch",
                        SAME_DRAGON_MAYBE_CONNECTED, NO_MOVE, 0, NO_MOVE,
                        MAX_MOVES, NULL);
         num_lunches++;
         eyevalue_list[num_eyes++] = e;
       }
     }
 }

 /* now, totalize the eye potential */
 {
   int ne;
   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
    * eye).
    */
   if (num_eyes - num_lunches > 1 && max_eye_threat(probable_eyes) > 1)
     *eyemax += 1;

   for (; ne < num_eyes; ne++)
     add_eyevalues(probable_eyes, &eyevalue_list[ne], probable_eyes);
 }

 debug = save_debug;
}


/* 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
* origins.
*
* 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.
*/

static void
owl_find_relevant_eyespaces(struct local_owl_data *owl,
                           int mw[BOARDMAX], int mz[BOARDMAX])
{
 int pos;
 int eye_color;
 int k;
 struct eye_data *eye = owl->my_eye;
 
 if (owl->color == WHITE)
   eye_color = WHITE;
 else
   eye_color = BLACK;

 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];
       if (ON_BOARD(pos2)
           && eye[pos2].color == eye_color
           && !eye[pos2].marginal) {
         if (owl->goal[pos])
           mw[eye[pos2].origin]++;
         else
           mz[eye[pos2].origin]++;
       }
     }
   }
 }
}

/* Case 1.
*
* The optics code occasionally comes up with stupid vital moves, like
* a in this position:
*
* ----+
* O...|
* OX..|
* OX..|
* O.X.|
* .O.a|
* ....|
*
* This function moves such moves to the second line.
*
* Case 2.
*
* 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.
*
* ----+
* XO.O|
* XOOX|
* XXO.|
* .XOO|
* .XXX|
*
* Case 3.
*
* Playing into a snapback is usually not an effective way to destroy
* an eye.
*
* XOOO|
* XOXX|
* XXO.|
* .XXO|
* ....|
*
* This function changes the attack point to NO_MOVE (i.e. removes it).
*/
static int
modify_stupid_eye_vital_point(struct local_owl_data *owl, int *vital_point,
                             int is_attack_point)
{
 int up;
 int right;
 int k;
 int libs[2];

 /* Case 1. */
 for (k = 0; k < 4; k++) {
   up = delta[k];
   if (ON_BOARD(*vital_point - up))
     continue;

   if (board[*vital_point + up] != EMPTY)
     continue;

   right = delta[(k+1) % 4];

   if (board[*vital_point + right] != EMPTY
       || board[*vital_point - right] != EMPTY)
     continue;

   if (board[*vital_point + 2 * up] != EMPTY
       || board[*vital_point + up + right] != EMPTY
       || board[*vital_point + up - right] != EMPTY) {
     *vital_point += up;
     return 1;
   }
 }

 /* Case 2. */
 if (!is_attack_point) {
   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)
           && countlib(pos) == 1) {
         findlib(pos, 1, vital_point);
         return 1;
       }
     }
   }
 }

 /* Case 3. */
 if (is_attack_point
     && does_capture_something(*vital_point, OTHER_COLOR(owl->color))
     && accuratelib(*vital_point, OTHER_COLOR(owl->color), 2, libs) == 1
     && !attack(libs[0], NULL)) {
   *vital_point = NO_MOVE;
   return 1;
 }

 return 0;
}


/* The purpose of this function is to avoid moves which needlessly
* fill in an eye. A typical example, from ld_owl:188, is
*
* -----+
* .O.OX|
* XOOXX|
* XXOOX|
* .XXO.|
* ..XOO|
* ..XXX|
*
* 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.
*/
static int
modify_eyefilling_move(int *move, int color)
{
 int k;
 int r;
 int other = OTHER_COLOR(color);
 /* Only do this for a small eye. */
 for (k = 0; k < 4; k++)
   if (ON_BOARD(*move + delta[k]) && board[*move + delta[k]] != color)
     return 0;

 for (r = 4; r < 8; r++)
   if (board[*move + delta[r]] == other
       && countlib(*move + delta[r]) == 1) {
     for (k = 0; k < 4; k++)
       if (board[*move + delta[k]] == color
           && countlib(*move + delta[k]) == 1
           && !adjacent_strings(*move + delta[r], *move + delta[k]))
         break;

     if (k == 4) {
       int new_move;
       findlib(*move + delta[r], 1, &new_move);
       TRACE("Changing eyefilling move at %1m to capture at %1m.\n",
             *move, new_move);
       *move = new_move;
       return 1;
     }
   }
 
 return 0;    
}


/* 
* 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
* being -1.
*
* 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.
*/

static void
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;
 sgf_dumptree = NULL;
 count_variations = 0;

 current_owl_data = owl;
 
 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. */
static int
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)
       return 0;
     else
       safe_move_checked = 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))
     return 0;
   constraint_checked = 1;
 }

 /* 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)) {
     if (0)
       TRACE("  move at %1m wasn't safe, discarded\n", move);
     return 0;
   }
   if (!is_legal(move, color)) {
     if (0)
       TRACE("  move at %1m wasn't legal, discarded\n", move);
     return 0;
   }
 }
 
 /* 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) {
     if (0)
       TRACE("  opponent can't play safely at %1m, move discarded\n", move);
     return 0;
   }
 }

 /* 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))
     return 0;
 return 1;
}


/* 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.
*/
static void
init_pattern_list(struct matched_patterns_list_data *list)
{
 gg_assert(!list->initialized);

 list->counter = 0;
 list->used = 0;

 list->pattern_list = malloc(200 * sizeof(list->pattern_list[0]));
 list->list_size = 200;
 gg_assert(list->pattern_list != NULL);
 list->pattern_heap = NULL;

 if (0)
   gprintf("List at %x has new array at %x\n", list, list->pattern_list);

 list->initialized = 1;
}


/* This function has to get called before the memory of *list is freed
* in the calling function.
*/
static void
close_pattern_list(int color, struct matched_patterns_list_data *list)
{
 if (list->initialized) {
   if (0)
     gprintf("%d patterns matched, %d patterns checked\n", list->counter,
             list->used);
   if (0)
     gprintf("Pattern list at %x freed for list at %x\n",
             list->pattern_list, list);
   if (allpats && verbose) {
     int i;
     int found_one = 0;
     SGFTree *save_sgf_dumptree = sgf_dumptree;
     int save_count_variations = count_variations;
     sgf_dumptree = NULL;
     count_variations = 0;

     if (!current_owl_data->lunches_are_current)
       owl_find_lunches(current_owl_data);

     if (!list->pattern_heap)
       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)) {
         if (!found_one) {
           TRACE("Remaining valid (but unused) patterns at stack: ");
           dump_stack();
           found_one = 1;
         }
         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);
 }
 list->counter = -1;
}


/* Can be called from gdb for debugging:
* (gdb) set dump_pattern_list(&shape_patterns)
*/
void
dump_pattern_list(struct matched_patterns_list_data *list)
{
 int i;
 struct matched_pattern_data *matched_pattern;
 if (!list->initialized)
   return;
 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("%o * ");
 }
 gprintf("%o\n");

 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);
 }
 gprintf("\n");
}


/* This function stores a found pattern in the list for later evaluation.
* The only processing done is computing the position of the move, and
* forgetting the color.
*/
static void
collect_owl_shapes_callbacks(int anchor, int color, struct pattern *pattern,
                            int ll, void *data)
{
 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->ll      = ll;
 next_pattern->anchor  = anchor;
 next_pattern->pattern = pattern;
 next_pattern->next_pattern_index = -1;

 matched_patterns->counter++;
}


#define MAX_STORED_REASONS      4

static int
valuate_combinable_pattern_chain(struct matched_patterns_list_data *list,
                                int pos)
{
 /* 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 num_eye_threats = 0;
 int eye_threats[MAX_STORED_REASONS];
 int num_reverse_sente = 0;
 int reverse_sente_against[MAX_STORED_REASONS];
 int num_move_reasons;
 float full_value = 0.0;

 ASSERT1(pattern_index != -1, pos);

 do {
   struct matched_pattern_data *pattern_data = (list->pattern_list
                                                + pattern_index);
   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;
          attribute++) {
       int k;
       int target = AFFINE_TRANSFORM(attribute->offset, pattern_data->ll,
                                     pattern_data->move);

       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)
               break;
           }

           if (k == num_capture_threats) {
             capture_threats[num_capture_threats++] = target;
             full_value += pattern_data->pattern->value;
           }
         }

         break;

       case THREATENS_EYE:
         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)
               break;
           }

           if (k == num_eye_threats) {
             eye_threats[num_eye_threats++] = target;
             full_value += pattern_data->pattern->value;
           }
         }

         break;

       case REVERSE_SENTE:
         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)
               break;
           }

           if (k == num_reverse_sente) {
             reverse_sente_against[num_reverse_sente++] = target;
             full_value += pattern_data->pattern->value;
           }
         }

         break;

       default:
         gg_assert(0);
       }
     }
   }

   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? */
   return 0;
 }

 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);
}


#if USE_BDIST

/* Compute the squared of the distance of a point on the board to the
* center of the board.
*/
static int
bdist(int move)
{
 /* 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 */


static void
pattern_list_prepare(struct matched_patterns_list_data *list)
{
 int k;
 int pos;

 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
  * heap elements first.
  */
 if (list->counter > 0) { /* avoid malloc(0) */
   list->pattern_heap = malloc(list->counter * sizeof(*(list->pattern_heap)));
   gg_assert(list->pattern_heap != NULL);
 }
 else {
   /* 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;

#if USE_BDIST
   list->pattern_list[k].bdist = bdist(move);
#endif

   /* Allocate heap elements for normal patterns.  Link combinable
    * patterns in chains.
    */
   if (!(list->pattern_list[k].pattern->class & CLASS_c))
     list->pattern_heap[list->heap_num_patterns++] = &list->pattern_list[k];
   else {
     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. */
static void
pattern_list_build_heap(struct matched_patterns_list_data *list)
{
 int k;
 int limit = list->heap_num_patterns / 2;

 for (k = limit; --k >= 0;) {
   int parent;
   int child;
   struct matched_pattern_data *pattern_data = list->pattern_heap[k];

   for (parent = k; parent < limit; parent = child) {
     child = 2 * parent + 1;
     if (child + 1 < list->heap_num_patterns
         && BETTER_PATTERN(list->pattern_heap[child + 1],
                           list->pattern_heap[child]))
       child++;

     if (BETTER_PATTERN(pattern_data, list->pattern_heap[child]))
       break;

     list->pattern_heap[parent] = list->pattern_heap[child];
   }

   list->pattern_heap[parent] = pattern_data;
 }
}


/* Pops patterns list's heap once. */
static void
pattern_list_pop_heap_once(struct matched_patterns_list_data *list)
{
 int parent;
 int child;

 list->heap_num_patterns--;
 for (parent = 0; 2 * parent + 1 < list->heap_num_patterns; parent = child) {
   child = 2 * parent + 1;
   if (BETTER_PATTERN(list->pattern_heap[child + 1],
                      list->pattern_heap[child]))
     child++;

   if (BETTER_PATTERN(list->pattern_heap[list->heap_num_patterns],
                      list->pattern_heap[child]))
     break;

   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.
*/
static void
pattern_list_sink_heap_top_element(struct matched_patterns_list_data *list)
{
 int parent;
 int child;
 struct matched_pattern_data *heap_top_element = list->pattern_heap[0];

 for (parent = 0; 2 * parent + 1 < list->heap_num_patterns; parent = child) {
   child = 2 * parent + 1;
   if (child + 1 < list->heap_num_patterns
       && BETTER_PATTERN(list->pattern_heap[child + 1],
                         list->pattern_heap[child]))
     child++;

   if (BETTER_PATTERN(heap_top_element,
                      list->pattern_heap[child]))
     break;

   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
* is more than one.
*/
static void
generate_cut_list(struct pattern *pattern, int ll, int anchor,
                 int cuts[MAX_CUTS], struct local_owl_data *owl)
{
 int k;
 int num = 0;
 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]))
     continue;
   pos = find_origin(pos);
   if (!mark[pos] && board[pos] == owl->color && owl->goal[pos]) {
     cuts[num++] = pos;
     mark[pos] = 1;
     if (num == MAX_CUTS)
       return;
   }
 }
 if (num == 1)
   cuts[0] = NO_MOVE;
 else if ((debug & DEBUG_SPLIT_OWL) && num > 1)
   gprintf("Move provokes %d cuts, among them %1m and %1m.\n", num,
           cuts[0], cuts[1]);
}

/* 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
* list.
*
* 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
* list is reached.
*/

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)
{
 int move_found = 0;
 SGFTree *save_sgf_dumptree = sgf_dumptree;
 int save_count_variations = count_variations;

 sgf_dumptree = NULL;
 count_variations = 0;

 /* Prepare pattern list if needed. */
 if (!list->pattern_heap)
   pattern_list_prepare(list);

 while (list->heap_num_patterns > 0) {
   int k;
   struct matched_pattern_data *pattern_data;
   struct pattern *pattern;
   int move;
   int value;
   int ll;
   int anchor;
   int next_pattern_index;

   /* Peek top element of heap associated with pattern list. */
   if (list->pattern_heap[0]->value < cutoff)
     break;

   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;

   list->used++;

   ASSERT_ON_BOARD1(move);
   for (k = 0; k < MAX_MOVES; k++) {
     if (moves[k].pos == move || moves[k].value <= 0)
       break;
   }

   if (moves[k].pos == move) {
     /* No point in testing this pattern/chain.  Throw it out. */
     pattern_list_pop_heap_once(list);
     continue;
   }

   /* 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().
    */
   if (pattern == NULL
       || 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);
     }
     else {
       /* 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;
       continue;
     }

     moves[k].pos = move;
     moves[k].value = value;
     clear_cut_list(moves[k].cuts);
     move_found = 1;

     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.
          */
         DEBUG(DEBUG_SPLIT_OWL,
               "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;
       else {
         int i;
         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,
                                    pattern_data->ll)) {
               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;
               }
               else
                 same_dragon = SAME_DRAGON_CONNECTED;

               break;
             }
           }
         }

         moves[k].same_dragon = same_dragon;
       }
     }
     else {
       moves[k].name = "Pattern combination";
       if (verbose) {
         /* 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];
       }
       else
         moves[k].same_dragon = SAME_DRAGON_CONNECTED;
     }

     if (pattern && pattern->class & CLASS_E)
       moves[k].escape = 1;
     else
       moves[k].escape = 0;

     break;
   }
   else {                      /* !check_pattern_hard(...) */
     if (!(pattern->class & CLASS_c)) {
       /* Just forget about it. */
       pattern_list_pop_heap_once(list);
     }
     else {
       /* Set this pattern to not matched and advance to next one in
        * the chain, if any.
        */
       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,
                                                                       move);
       pattern_list_sink_heap_top_element(list);
     }
   }
 }

 sgf_dumptree = save_sgf_dumptree;
 count_variations = save_count_variations;

 return move_found;
}


/* 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.
*/
static void
owl_shapes_callback(int anchor, int color, struct pattern *pattern,
                   int ll, void *data)
{
 int tval;  /* trial move and its value */
 int move;
 struct owl_move_data *moves = data; /* considered moves passed as data */
 enum same_dragon_value same_dragon = SAME_DRAGON_MAYBE_CONNECTED;
 int escape = 0;
 int defense_pos;

 /* 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.
  */
 if (!allpats) {
   int k;
   for (k = 0; k < MAX_MOVES; k++) {
     if (moves[k].value == -1)
       break;
     if (moves[k].pos == move) {
       if (moves[k].value >= pattern->value)
         return;
       else
         break;
     }
   }
   if (k == MAX_MOVES && moves[MAX_MOVES - 1].value >= pattern->value)
     return;
 }
 
 if (!check_pattern_hard(move, color, pattern, ll))
   return;

 /* and work out the value of this move */
 if (pattern->helper) {
   /* ask helper function to consider the move */
   gg_assert(0);
   DEBUG(DEBUG_HELPER, "  asking helper to consider '%s'+%d at %1m\n",
         pattern->name, ll, move);
   tval = pattern->helper(pattern, ll, move, color);
   
   if (tval > 0) {
     DEBUG(DEBUG_HELPER, "helper likes pattern '%s' value %d at %1m\n",
           pattern->name, tval, move);
   }
   else {
     DEBUG(DEBUG_HELPER, "  helper does not like pattern '%s' at %1m\n",
           pattern->name, move);
     return;  /* pattern matcher does not like it */
   }
 }
 else { /* no helper */
   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.
    */
   gg_assert(0);
 }
 else
   same_dragon = SAME_DRAGON_CONNECTED;

 if (pattern->class & CLASS_E)
   escape = 1;
 else 
   escape = 0;

 /* Finally, check for position of defense move. */
 {
   int k;
   defense_pos = 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 */

static void
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)
{
 int k;

 if (!found_matches[move]) {
   found_matches[move] = 1;
   matches_found++;
 }
 
 /* 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)
     break;
   if (moves[k].pos == move) {
     if (same_dragon > moves[k].same_dragon) {
       moves[k].same_dragon = same_dragon;
       moves[k].pattern_data = pattern_data;
     }
     if (!moves[k].escape)
       escape = 0;
     break;
   }
 }

 /* Did we already have this move in the list with a higher value? */
 if (k < max_moves && moves[k].value >= value)
   return;

 /* Insert the move at the right place in the list and adjust other
  * entries as needed.
  */
 for (; k >= 0; k--) {
   if (k == 0 || value <= moves[k-1].value) {
     /* Can't get higher. Insert the move below this point and quit
      * looping.
      */
     if (k < max_moves) {
       moves[k].pos = move;
       moves[k].value = value;
       moves[k].name = reason;
       /* 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].lunch = lunch;
       moves[k].escape = escape;
       moves[k].defense_pos = defense_pos;
     }
     break;
   }
   /* Shuffle the passed move one step downwards. */
   if (k < max_moves)
     moves[k] = moves[k-1]; /* struct copy */
 }

 /* Assert that the list contains unique moves. */
 if (0) {
   int l;
   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. 
*/

static void
owl_mark_dragon(int apos, int bpos, struct local_owl_data *owl,
               int new_dragons[BOARDMAX])
{
 int pos;
 int color = board[apos];
 
 ASSERT1(bpos == NO_MOVE || board[bpos] == color, bpos);

 if (new_dragons == NULL) {
   for (pos = BOARDMIN; pos < BOARDMAX; pos++)
     if (ON_BOARD(pos)) {
       if (is_same_dragon(pos, apos) || is_same_dragon(pos, bpos))
         owl->goal[pos] = 1;
       else
         owl->goal[pos] = 0;
     }
 }
 else {
   for (pos = BOARDMIN; pos < BOARDMAX; pos++)
     if (ON_BOARD(pos)) {
       if (IS_STONE(board[pos])
           && (new_dragons[pos] == new_dragons[apos]
               || new_dragons[pos] == new_dragons[bpos]))
         owl->goal[pos] = 1;
       else
         owl->goal[pos] = 0;
     }
 }

 memcpy(owl->cumulative_goal, owl->goal, sizeof(owl->goal));
 owl->color = color;
 owl_mark_boundary(owl);
}


/* Marks the worms at apos and bpos. If only one worm
* needs marking, bpos should be passed as NO_MOVE. 
*/

static void
owl_mark_worm(int apos, int bpos, struct local_owl_data *owl)
{
 int pos;
 int color = board[apos];
 
 ASSERT1(bpos == NO_MOVE || board[bpos] == color, bpos);

 for (pos = BOARDMIN; pos < BOARDMAX; pos++)
   if (ON_BOARD(pos)) {
     if (is_same_worm(pos, apos) || is_same_worm(pos, bpos))
       owl->goal[pos] = 1;
     else
       owl->goal[pos] = 0;
   }

 owl->color = color;
}


/* Mark the boundary strings of the dragon. A boundary string is marked 2
* if it adjoins a friendly live dragon, 1 otherwise.
*/

static void
owl_mark_boundary(struct local_owl_data *owl)
{
 int k;
 int pos;
 int color = owl->color;
 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);
     }

     for (; k < 8; k++) {
       int pos2 = pos + delta[k];

       if (board[pos2] == color
           && !owl->neighbors[pos2]
           && (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]) {
     for (k = 0; k < 8; k++)
       if (ON_BOARD(pos + delta[k])
           && (owl->goal[pos + delta[k]] || owl->neighbors[pos + delta[k]])) {
         mark_string(pos, owl->boundary, 1);
         break;
       }
   }

 /* Upgrade the mark of a boundary string if it adjoins a safe
  * friendly dragon.
  */
 for (pos = BOARDMIN; pos < BOARDMAX; pos++)
   if (owl->boundary[pos] == 1) {
     for (k = 0; k < 8; k++) {
       int pos2 = pos + delta[k];
       if (board[pos2] == color
           && !owl->goal[pos2]
           && !owl->neighbors[pos2]
           && ((dragon[pos2].crude_status != DEAD && countstones(pos2) > 2)
               || dragon[pos2].crude_status == ALIVE)) {
         mark_string(pos, owl->boundary, 2);
         break;
       }
     }
   }
 
 /* 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
      * have to back out now.
      *
      * 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
      * stones of this color.
      */
     if (worm[pos].attack_codes[0] != 0
         && worm[pos].size != dragon[pos].size)
       continue;
     
     /* This can happen if called when stackp > 0 */
     if (dragon[pos].id == -1)
       continue;
     
     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]) {
         owl->boundary[pos] = 2;
         break;
       }
     }
   }
}

/* 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
* at all.
*
* 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.
*/
static void
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];
 int num_stones;
 int k;
 int do_add = 1;
 SGFTree *save_sgf_dumptree = sgf_dumptree;
 int save_count_variations = count_variations;
 

 /* Turn off sgf output during find_superstring(). */
 sgf_dumptree = NULL;
 count_variations = 0;
 
 if (same_dragon == SAME_DRAGON_NOT_CONNECTED)
   num_stones = findstones(pos, MAX_BOARD * MAX_BOARD, stones);
 else if (semeai_call)
   find_superstring_conservative(pos, &num_stones, stones);
 else
   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) {
   do_add = 0;
   for (k = 0; k < num_stones; k++)
     if (owl->goal[stones[k]] != 0) {
       do_add = 1;
       break;
     }
 }
 
 if (do_add)
   for (k = 0; k < num_stones; k++) {
     if (owl->goal[stones[k]] == 0) {
       if (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
  * goal.
  */
 if (!semeai_call && lunch != NO_MOVE && board[lunch] != EMPTY) {
   int adj, adjs[MAXCHAIN];
   int k;
   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++) {
     int pos2;
     
     /* all the following stuff (currently) applies only at occupied cells */
     if (pattern_data->pattern->patn[k].att != ATT_O)
       continue;
     
     /* transform pattern real coordinate */
     pos2 = AFFINE_TRANSFORM(pattern_data->pattern->patn[k].offset,
                             pattern_data->ll, pattern_data->anchor);

     if (!owl->goal[pos2])
       owl_update_goal(pos2, SAME_DRAGON_CONNECTED, NO_MOVE, owl, semeai_call,
                       pattern_data);
   }
 }

 if (1 && verbose)
   goaldump(owl->goal);
}


/* 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
* graph_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.
*/
static int
connected_components(signed char graph[MAX_CUTS][MAX_CUTS], int graph_size,
                    signed char component[MAX_CUTS])
{
 int num_components = 0;
 int k, j;

 if (graph_size <= 0)
   return 0;

 memset(component, -1, MAX_CUTS);
 for (;;) {
   int found_one;
   /* Find unidentified string. */
   for (k = 0; k < graph_size; k++)
     if (component[k] == -1)
       break;
   if (k == graph_size)
     break; /* All are identified. */
   component[k] = num_components; /* Start new component. */
   do { /* Spread new component. */
     found_one = 0;
     for (j = k+1; j < graph_size; j++)
       if (graph[k][j] && component[j] == -1) {
         component[j] = num_components;
         found_one = 1;
       }
   } while (found_one);
   num_components++;
 }
 gg_assert(num_components > 0);
 return num_components;
}

/* 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.
*/
static void
owl_test_cuts(signed char goal[BOARDMAX], int color, int cuts[MAX_CUTS])
{
 int k, j;
 signed char connected[MAX_CUTS][MAX_CUTS];
 /* int connect_move[MAX_CUTS][MAX_CUTS]; */
 int num_cuts;
 int found_cut = 0;
 SGFTree *save_sgf_dumptree = sgf_dumptree;
 int save_count_variations = count_variations;
   
 sgf_dumptree = NULL;
 count_variations = 0;

 memset(connected, 1, MAX_CUTS*MAX_CUTS);
 if (debug & DEBUG_SPLIT_OWL) {
   gprintf("Called for this goal: ");
   goaldump(goal);
   gprintf("At this position:\n");
   showboard(0);
 }

 /* Delete captured strings from list. */
 for (k = 0; k < MAX_CUTS; k++) {
   if (cuts[k] == NO_MOVE)
     break;
   if (board[cuts[k]] == EMPTY) {
     for (j = k + 1; j < MAX_CUTS; j++) {
       if (cuts[j] == NO_MOVE)
         break;
       cuts[j-1] = cuts[j];
     }
     cuts[k] = NO_MOVE;
     k--;
   }
 }
 num_cuts = k;

 /* Test for each pair of strings in cuts[] whether it can now be
  * disconnected.
  */
 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) {
       found_cut = 1;
       connected[k][j] = 0;
       connected[j][k] = 0;
     }
 }

 if (found_cut) {
   signed char component[MAX_CUTS];
   signed char component2[BOARDMAX];
   int component_size[MAX_CUTS];
   int num_components;
   int biggest_component = -1;
   struct connection_data *conn_data;
   int c_id;
   int pos;

   /* Start by computing the connected components among the strings
    * listed in cuts[].
    */
   num_components = connected_components(connected, num_cuts, component);
   if (num_components <= 1) {
     sgf_dumptree = save_sgf_dumptree;
     count_variations = save_count_variations;
     return;
   }

   /* 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),
                          conn_data + c_id, 1);
     spread_connection_distances(color, conn_data + c_id);
   }

   /* Now put each goal string to the component to which it has the
    * smallest distance.
    */
   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
     int closest_dist = HUGE_CONNECTION_DISTANCE;
     int closest_component = -1;
     if (board[pos] != color || !goal[pos])
       continue;
     if (pos != find_origin(pos))
       continue;
     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. */
   {
     int biggest_size = 0;
     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)
       goal[pos] = 0;
   if (debug & DEBUG_SPLIT_OWL) {
     gprintf("Split dragon. Biggest component is %d (of %d).\n",
             biggest_component, num_components);
     showboard(0);
     componentdump(component2);
   }
   free(conn_data);
 }
 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.
*/
static void
owl_update_boundary_marks(int pos, struct local_owl_data *owl)
{
 signed char boundary_mark = 0;
 int k;

 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->goal[pos2]
       && !owl->neighbors[pos2])
     boundary_mark = 2;
 }

 mark_string(pos, owl->boundary, boundary_mark);
}

/* Lists the goal array. For use in GDB:
* (gdb) set goaldump(goal).
*/

void
goaldump(const signed char goal[BOARDMAX])
{
 int pos;
 for (pos = BOARDMIN; pos < BOARDMAX; pos++)
   if (ON_BOARD(pos) && goal[pos])
     gprintf("%o%1m (%d)  ", pos, (int) goal[pos]);
 gprintf("\n");
}

void
componentdump(const signed char component[BOARDMAX])
{
 int pos;
 for (pos = BOARDMIN; pos < BOARDMAX; pos++)
   if (ON_BOARD(pos) && component[pos] != -1)
     gprintf("%o%1m (%d)  ", pos, (int) component[pos]);
 gprintf("\n");
}

/*
* 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.
*/
static void
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))
     || acode == GAIN) {
   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),
         movenum+1);
 }
 else {
   int dr2 = DRAGON2(dr).semeai_defense_target;
   int semeai_result, certain;
   int save_verbose = verbose;
   if (verbose > 0)
     verbose--;
   owl_analyze_semeai_after_move(pos, color, dr, dr2, &semeai_result,
                                 NULL, NULL, 1, &certain, 0);
   verbose = save_verbose;
   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);
   }
   else {
     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),
           movenum+1);
   }
 }
}

/* Add owl move reasons. This function should be called once during
* genmove. It has to be called after semeai_move_reasons().
*/

void
owl_reasons(int color)
{
 int pos;

 for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
   if (!IS_STONE(board[pos])
       || dragon[pos].origin != pos)
     continue;
   
   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);
         }
         else {
           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.
          */
         int largest = 0;
         int k;
         int bpos = NO_MOVE;
         int kworm = NO_MOVE;
         int safe = 0;
         for (k = 0; k < DRAGON2(pos).neighbors; k++) {
           int d = DRAGON2(pos).adjacent[k];
           if (DRAGON(d).color == color) {
             if (DRAGON(d).status == ALIVE) {
               safe = 1;
               break;
             }
             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 (bpos == NO_MOVE)
           safe = 1;
         
         /* 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) {
           DEBUG(DEBUG_OWL,
                 "owl: %1m attacks %1m at move %d, but the attacker dies.\n",
                 move, pos, movenum+1);
           DRAGON2(pos).safety = INESSENTIAL;
           continue;
         }
       }

       /* 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) {
     if (board[pos] == color 
         && 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);
     }
     if (board[pos] == color
           && 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,
                                   pos, WIN);
       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,
                                    WIN);
         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);
       DEBUG(DEBUG_OWL, 
             "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);
     DEBUG(DEBUG_OWL,
           "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.
*/

int
owl_does_defend(int move, int target, int *kworm)
{
 int color = board[target];
 int result = 0;
 struct local_owl_data *owl;
 int reading_nodes_when_called = get_reading_node_counter();
 int tactical_nodes;
 int origin;
 int acode;
 int wpos = NO_MOVE;
 int wid = MAX_GOAL_WORMS;
 double start = 0.0;

 if (debug & DEBUG_OWL_PERFORMANCE)
   start = gg_cputime();

 if (worm[target].unconditional_status == DEAD)
   return 0;

 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))
   return result;

 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)) {
     popgo();
     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,
                     kworm, 0);
   acode = do_owl_attack(target, NULL, &wid, owl, 0);
   finish_goal_list(&goal_worms_computed, &wpos, owl_goal_worm, wid);
   result = REVERSE_RESULT(acode);
   popgo();
 }
 else
   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,
                            result, wpos, 0, 0,
                            tactical_nodes, owl->goal, board[target]);

 if (kworm)
   *kworm = wpos;
 return result;
}


/* 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.
*/

int
owl_confirm_safety(int move, int target, int *defense_point, int *kworm)
{
 int color = board[target];
 int result = 0;
 struct local_owl_data *owl;
 int reading_nodes_when_called = get_reading_node_counter();
 int tactical_nodes;
 int origin;
 int defense = 0;
 double start = 0.0;
 int acode;
 int wpos = NO_MOVE;
 int wid = MAX_GOAL_WORMS;

 if (debug & DEBUG_OWL_PERFORMANCE)
   start = gg_cputime();

 if (worm[target].unconditional_status == DEAD)
   return 0;

 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))
   return result;

 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)) {
     popgo();
     if (result == 0)
       return WIN;
     else if (result == GAIN)
       return LOSS;
     else
       return 0;
   }
   
   init_owl(&owl, target, NO_MOVE, move, 1, NULL);
   prepare_goal_list(target, owl, owl_goal_worm, &goal_worms_computed,
                     kworm, 0);
   acode = do_owl_attack(target, &defense, &wid, owl, 0);
   finish_goal_list(&goal_worms_computed, &wpos, owl_goal_worm, wid);
   if (acode == 0)
     result = WIN;
   else if (acode == GAIN)
     result = LOSS;
   popgo();
 }
 else
   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,
       gg_cputime() - start);

 store_persistent_owl_cache(OWL_CONFIRM_SAFETY, move, target, 0,
                            result, defense, wpos, 0,
                            tactical_nodes, owl->goal, board[target]);

 if (defense_point)
   *defense_point = defense;
 if (kworm)
   *kworm = wpos;

 return result;
}


/* 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.
*/

int
owl_does_attack(int move, int target, int *kworm)
{
 int color = board[target];
 int other = OTHER_COLOR(color);
 int result = 0;
 struct local_owl_data *owl;
 int reading_nodes_when_called = get_reading_node_counter();
 int tactical_nodes;
 int origin;
 int dcode;
 int wpos = NO_MOVE;
 int wid = MAX_GOAL_WORMS;
 double start = 0.0;

 if (debug & DEBUG_OWL_PERFORMANCE)
   start = gg_cputime();

 if (worm[target].unconditional_status == ALIVE)
   return 0;

 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))
   return result;

 /* 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.
  */
#if 1
 init_owl(&owl, target, NO_MOVE, NO_MOVE, 1, NULL);
#endif

 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)) {
     popgo();
     return REVERSE_RESULT(result);
   }

#if 0
   local_owl_node_counter = 0;
   owl->lunches_are_current = 0;
   owl_mark_dragon(target, NO_MOVE, owl);
#endif
   owl_update_boundary_marks(move, owl);
#if 0
   compute_owl_escape_values(owl);
#endif
   /* FIXME: Should also check if part of the dragon was captured,
    *        like do_owl_attack() does.
    */
   if (board[target] == EMPTY)
     dcode = 0;
   else {
     prepare_goal_list(target, owl, owl_goal_worm, &goal_worms_computed,
                        kworm, 0);
     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;
   popgo();
 }
 else
   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,
                            result, wpos, 0, 0,
                            tactical_nodes, owl->goal, board[target]);

 if (kworm)
   *kworm = wpos;
 return result;
}


/* 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.
*/

int
owl_connection_defends(int move, int target1, int target2)
{
 int color = board[target1];
 int result = 0;
 int reading_nodes_when_called = get_reading_node_counter();
 int tactical_nodes;
 double start = 0.0;
 struct local_owl_data *owl;

 if (debug & DEBUG_OWL_PERFORMANCE)
   start = gg_cputime();

 ASSERT1(board[target2] == color, target2);
 TRACE("owl_connection_defends %1m %1m %1m\n", move, target1, target2);

 if (worm[target1].unconditional_status == DEAD)
   return 0;
 if (worm[target2].unconditional_status == DEAD)
   return 0;

 if (search_persistent_owl_cache(OWL_CONNECTION_DEFENDS, move, target1,
                                 target2, &result, NULL, NULL, NULL))
   return result;

 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))
     result = WIN;
   owl->lunches_are_current = 0;
   popgo();
 }
 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,
                            owl->goal, color);

 return result;
}


/* 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:
*
* -------
* OXXOOXO
* OX.O.XO
* OXX.XXO
* OOXXXOO
* .OOOOO.
*
* 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
* hold:
*
* 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
*    tactically captured.
*
* There is a weakness with this characterization though, which can be
* seen in this position:
*
* --------
* OX..OOX.
* OX.X.XOO
* OX.XX.O.
* O.XXOOO.
* .OOOO...
*
* 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
* themself:
*
* 5. No neighbor of the stones does not belong to the goal or can be
*    tactically captured.
*
* A second weakness can be noticed in this position:
*
* |OOOO.
* |XXXO.
* |O.XOO
* |OXXXO
* |.O.XO
* +-----
*
* 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
*     goal dragon.
*
* This is not quite good enough though, as shown in this position:
*
* ----------
* OX.X.OO...
* OXX.OOX.O.
* O.XXXXX.O.
* OOOOOOOOO.
*
* The four O stones are regarded as inessential after inclusion of
* rule 1b, which is clearly inappropriate. To solve this problem we
* modify the rule:
*
* 1b'. The liberty is a topologically false eye with respect to the
*      goal dragon and is adjacent to no empty vertex.
*/

static void
owl_find_lunches(struct local_owl_data *owl)
{
 int k;
 int pos;
 int lunches = 0;
 int prevlunch;
 int lunch;
 int acode;
 int apos;
 int dcode;
 int dpos;
 int color = owl->color;
 int other = OTHER_COLOR(color);
 signed char already_checked[BOARDMAX];

 SGFTree *save_sgf_dumptree = sgf_dumptree;
 int save_count_variations = count_variations;
   
 sgf_dumptree = NULL;
 count_variations = 0;
 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)
         pos2 += delta[k];

       if (board[pos2] != other)
         continue;

       lunch = find_origin(pos2);
       if (already_checked[lunch])
         continue;
       already_checked[lunch] = 1;

       attack_and_defend(lunch, &acode, &apos, &dcode, &dpos);
       if (acode != 0) {
         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);
         if (dcode != 0) {
           owl->lunch_defense_point[lunches] = dpos;
           ASSERT1(board[dpos] == EMPTY, lunch);
         }
         else
           owl->lunch_defense_point[lunches] = NO_MOVE;
         lunches++;
         if (lunches == MAX_LUNCHES) {
           sgf_dumptree = save_sgf_dumptree;
           count_variations = save_count_variations;
           owl->lunches_are_current = 1;
           return;
         }
       }
       else if (!owl->inessential[lunch]) {
         /* Test for inessentiality. */
         int adj;
         int adjs[MAXCHAIN];
         int num_stones;
         int stones[MAX_BOARD * MAX_BOARD];
         int liberties;
         int libs[MAXLIBS];
         int r;
         int essential = 0;
         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) {
             essential = 1;
             break;
           }
         }

         if (essential)
           continue;

         find_superstring_stones_and_liberties(lunch, &num_stones, stones,
                                               &liberties, libs, 0);

         memset(superstring, 0, sizeof(superstring));
         for (r = 0; r < num_stones; r++)
           superstring[stones[r]] = 1;

         for (r = 0; r < liberties; r++) {
           int bpos = libs[r];
           int goal_found = 0;
           int s;

           for (s = 0; s < 4; s++) {
             int cpos = bpos + delta[s];

             if (!ON_BOARD(cpos))
               continue;
             if (board[cpos] == color) {
               if (attack(cpos, NULL) != 0) {
                 essential = 1;
                 break;
               }
               else if (owl->goal[cpos])
                 goal_found = 1;
               else {
                 essential = 1;
                 break;
               }
             }
             else if (board[cpos] == other
                      && !superstring[cpos]) {
               essential = 1;
               break;
             }
           }
           if (!goal_found) {
             /* Requirement 1 not satisfied. Test requirement 1b.
              * N.B. This is a simplified topological eye test.
              * The simplification may be good, bad, or neutral.
              */
             int off_board = 0;
             int diagonal_goal = 0;
             for (s = 4; s < 8; s++) {
               if (!ON_BOARD(bpos + delta[s]))
                 off_board++;
               else if (owl->goal[bpos + delta[s]])
                 diagonal_goal++;
             }
             if (diagonal_goal + (off_board >= 2) < 2)
               essential = 1;
             else {
               /* 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) {
                   essential = 1;
                   break;
                 }
               }
             }
           }

           if (essential)
             break;
         }

         if (!essential) {
           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.
*
*   .*OO       .*OOO       .*OOOO
*   .,XO       .,X.O       .,XX.O
*   ----       -----       ------
*
* In all these position the attack point is moved from ',' to '*'.
*/
static int
improve_lunch_attack(int lunch, int attack_point)
{
 int color = OTHER_COLOR(board[lunch]);
 int defense_point;
 int k;

 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);
     int libs[2];

     if (stones == 1
         || (stones == 2
             && 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))
             return apos;
           break;
         }
       }
     }
   }

   return attack_point;
 }

 for (k = 0; k < 4; k++) {
   int pos = attack_point + delta[k];
   if (board[pos] == color
       && attack(pos, NULL)
       && 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);
     return defense_point;
   }
 }
 
 return attack_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
* ld_owl:182.
*
* ...X..|      ...X..|
* ...X..|      ...Xc.|
* ..XXO.|      ..XXOb|
* XXXOOX|      XXXOOA|
* XOOOX.|      XOOOX.|
* .XOX.X|      .XOX.X|
* ------+      ------+
*/
static int
improve_lunch_defense(int lunch, int defense_point)
{
 int color = board[lunch];
 int k;
 
 for (k = 0; k < 4; k++) {
   int pos = defense_point + delta[k];
   if (board[pos] == OTHER_COLOR(color)
       && countlib(pos) == 2) {
     int libs[2];
     int pos2;
     
     findlib(pos, 2, libs);
     if (libs[0] == defense_point)
       pos2 = libs[1];
     else
       pos2 = libs[0];

     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);
       return pos2;
     }
   }
 }
 
 return defense_point;
}


/* 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.
*/

static void
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;
 
 current_owl_data = owla;
 other_owl_data = owlb;

 if (!owla->lunches_are_current)
   owl_find_lunches(owla);
 if (owla->color == BLACK)
   black_eye = owla->my_eye;
 else
   white_eye = owla->my_eye;
 
 if (owlb) {
   gg_assert(owla->color == OTHER_COLOR(owlb->color));
   if (!owlb->lunches_are_current)
     owl_find_lunches(owlb);
   if (owlb->color == BLACK)
     black_eye = owlb->my_eye;
   else
     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.
*/

int 
owl_lively(int pos)
{
 int origin;
 int lunch;
 ASSERT_ON_BOARD1(pos);

 if (board[pos] == EMPTY)
   return 0;
 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 (other_owl_data) {

   if (include_semeai_worms_in_eyespace && other_owl_data->goal[pos])
     return 0;
   
   if (other_owl_data->goal[pos] && !semeai_trust_tactical_attack(pos))
     return 1;
   /* 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)
       return 0;
 }

 /* Inessential stones are not lively. */
 if (current_owl_data->inessential[origin])
   return 0;

 /* 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)
     return 0;

 return 1;
}


/* 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.
*/

static int
owl_safe_move(int move, int color)
{
 int acode, safe = 0;

 if (trymove(move, color, "owl_safe_move", 0)) {
   acode = attack(move, NULL);
   if (acode != WIN)
     safe = 1;
   else
     safe = 0;
   popgo();
 }
 current_owl_data->safe_move_cache[move] = safe+1;
 return safe;
}
 

/* 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
owl_substantial(int str)
{
 int k;
 int libs[MAX_SUBSTANTIAL_LIBS + 1];
 int liberties = findlib(str, MAX_SUBSTANTIAL_LIBS+1, libs);
 int reading_nodes_when_called = get_reading_node_counter();
 int tactical_nodes;
 int result;
 double start = 0.0;
 struct local_owl_data *owl;
 int num_moves = 0;

 if (debug & DEBUG_OWL_PERFORMANCE)
   start = gg_cputime();

 /* FIXME: We want to use the full init_owl here too (cf. similar
  * remark below).
  */
 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)
   return 1;
 
 if (liberties > MAX_SUBSTANTIAL_LIBS)
   return 0;

 memset(owl->goal, 0, sizeof(owl->goal));
 /* Mark the neighbors of the string. If one is found which is alive, return
  * true. */
 {
   int adjs[MAXCHAIN];
   int adj;

   adj = chainlinks(str, adjs);
   for (k = 0; k < adj; k++) {
     if (dragon[adjs[k]].status == ALIVE)
       return 1;
     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))
   return result;

 /* fill all the liberties */
 for (k = 0; k < liberties; k++) {
   if (trymove(libs[k], owl->color, NULL, 0)) {
     if (get_level() >= 8)
       increase_depth_values();
     owl->goal[libs[k]] = 1;
     num_moves++;
   }
   else {
     /* if we can't fill, try swapping with the next liberty */
     if (k < liberties-1
         && trymove(libs[k+1], owl->color, NULL, 0)) {
       if (get_level() >= 8)
         increase_depth_values();
       owl->goal[libs[k+1]] = 1;
       libs[k+1] = libs[k];
       num_moves++;
     }
     else {
       /* Can't fill the liberties. Give up! */
       while (num_moves-- > 0) {
         if (get_level() >= 8)
           decrease_depth_values();
         popgo();
       }
       return 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_mark_boundary(owl);
 owl->lunches_are_current = 0;

 if (do_owl_attack(libs[0], NULL, NULL, owl, 0))
   result = 0;
 else
   result = 1;
 while (num_moves-- > 0) {
   if (get_level() >= 8)
     decrease_depth_values();
   popgo();
 }

 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);

 return result;
}



/* Returns true if and only if (i, j) is a 1-2 vertex, i.e. next to a
* corner.
*/
static int
one_two_point(int pos)
{
 int i = I(pos);
 int j = J(pos);
 
 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))
   return 1;

 return 0;
}



/* 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.
*/

static void
sniff_lunch(int lunch, int *min, int *probable, int *max,
           struct local_owl_data *owl)
{
 int other = OTHER_COLOR(board[lunch]);
 int libs[MAXLIBS];
 int liberties;
 int r;

 ASSERT1(IS_STONE(board[lunch]), lunch);

 if (owl->boundary[lunch] == 2) {
   *min = 2;
   *probable = 2;
   *max = 2;
   return;
 }

 /* 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)) {
     int k;
     for (k = 0; k < 8; k++)
       if (ON_BOARD(libs[r] + delta[k]) && owl->goal[libs[r] + delta[k]])
         break;
     if (k == 8) {
       *min = 2;
       *probable = 2;
       *max = 2;
       return;
     }
   }
 }

 estimate_lunch_eye_value(lunch, min, probable, max, 1);

 if (*min < 2) {
   int bonus = estimate_lunch_half_eye_bonus(lunch, owl->half_eye);
   *min += bonus/2;
   *probable += bonus;
   *max += (bonus + 1)/2;
 }

 if (*probable < 2)
   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).
*/
static int
estimate_lunch_half_eye_bonus(int lunch,
                             struct half_eye_data half_eye[BOARDMAX])
{
 int stones[10];
 int k;
 int size = findstones(lunch, 10, stones);
 int half_eyes = 0;

 ASSERT1(size < 10, lunch);

 for (k = 0; k < size; k++) {
   int stone = stones[k];
   int d;
   for (d = 4; d < 8; d++) {
     int pos = stone + delta[d];
     if (ON_BOARD(pos)
         && (is_halfeye(half_eye, pos) || is_false_eye(half_eye, pos)))
       half_eyes++;
   }
 }
 return half_eyes;
}


void
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);

 if (size > 6) {
   *min = 2;
   *probable = 2;
   *max = 2;
 }
 else if (size > 4) {
   *min = 1;
   *probable = 2;
   *max = 2;
 }
 else if (size > 2) {
   *min = 0;
   *probable = 1;
   *max = 2;
 }
 else if (size == 2) {
   int stones[2];
   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])))) {
     *min = 0;
     *probable = 0;
     *max = 0;
   }
   else {
     *min = 0;
     *probable = 1;
     *max = 1;
   }
 }
 else if (size == 1) {
   if (!obvious_false_eye(lunch, other)) {
     *min = 0;
     *probable = 1;
     *max = 1;
   }
   else {
     *min = 0;
     *probable = 0;
     *max = 0;
   }
 }
}

/* 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
* do_owl_defend()
* 
* The following implementation tries to get a precise idea of the
* escape potential improvement by calling dragon_escape() twice.
*/
static void
eat_lunch_escape_bonus(int lunch, int *min, int *probable, int *max,
                      struct local_owl_data *owl)
{
 int adjacent[MAXCHAIN];
 int neighbors;
 int adjoins = 0;
 int n;
 /* Be very careful before touching this value.
  * See owl_estimate_life() for details.
  */
 UNUSED(min);
 
 /* Don't mess up with kos */
 if (is_ko_point(lunch))
   return;
 
 neighbors = chainlinks(lunch, adjacent);
 for (n = 0; n < neighbors; n++)
   adjoins |= !owl->goal[adjacent[n]];
 
 if (adjoins) {
   int before, after;
   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 */
   if (before < 5) {
     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)) {
         *probable = 2;
         *max = 2;
       }
       else if (*max < 2)
         (*max)++;
     }
   }
 }
}


/* Find a new origin when it has been captured or cut out of the
* goal. Used in do_owl_attack()
*/
static int
select_new_goal_origin(int origin, struct local_owl_data *owl)
{
 int pos;
 for (pos = BOARDMIN; pos < BOARDMAX; pos++)
   if (board[pos] == owl->color && owl->goal[pos] == 1)
     return find_origin(pos);

 return origin;
}


/* Retrieve topological eye values stored in the half_eye[] array of
* the current owl data.
*
* 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().
*/
int
owl_topological_eye(int pos, int color)
{
 float value;
 UNUSED(color);
 value = current_owl_data->half_eye[pos].value;
 if (value > 2.0 && value < 4.0)
   return 3;
 else if (value <= 2.0)
   return (int) (value + 0.99); /* Round up. */
 else
   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.
*/

int
vital_chain(int pos)
{
 int min;
 int probable;
 int max;
 sniff_lunch(pos, &min, &probable, &max, current_owl_data);

 return max;
}


static void
compute_owl_escape_values(struct local_owl_data *owl)
{
 int pos;
 int m, n;
 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));
   
 sgf_dumptree = NULL;
 count_variations = 0;
 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,
                          owl->escape_values);

 DEBUG(DEBUG_ESCAPE, "Owl escape values:\n");
 for (m = 0; m < board_size; m++) {
   for (n = 0; n < board_size; n++) {
     pos = POS(m, 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];
           else {
             int pos2;
             signed char escape_values[BOARDMAX];
             signed char dragon_stones[BOARDMAX];

             compute_escape_influence(owl->color, safe_stones, owl->goal,
                                      NULL, escape_values);

             /* 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
              * robust at least.
              */
             for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) {
               if (ON_BOARD(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. */
int
owl_escape_value(int pos)
{
 /* FIXME: Should have a more robust mechanism to avoid 
  * escaping inwards. Returning a negative value is just a kludge.
  */
 int k;
 ASSERT_ON_BOARD1(pos);
 if (current_owl_data->goal[pos])
   return -10;

 if (board[pos] == EMPTY)
   for (k = 0; k < 8; k++)
     if (ON_BOARD(pos + delta[k]) && current_owl_data->goal[pos + delta[k]])
       return -10;
 
 return current_owl_data->escape_values[pos];
}


/* Used by autohelpers. */
int
owl_goal_dragon(int pos)
{
 return current_owl_data->goal[pos] != 0;
}

/* Used by autohelpers.
* Returns 1 if (pos) is an eyespace for the color of the dragon currently
* under owl investigation.
*/
int
owl_eyespace(int pos)
{
 int origin;
 ASSERT_ON_BOARD1(pos);
 
 origin = current_owl_data->my_eye[pos].origin;
 return (ON_BOARD(origin)
         && (current_owl_data->my_eye[origin].color
             == current_owl_data->color)
         && max_eyes(&current_owl_data->my_eye[origin].value) > 0);
}


/* Used by autohelpers.
* 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.
*/
int
owl_big_eyespace(int pos)
{
 int origin;
 ASSERT_ON_BOARD1(pos);

 origin = current_owl_data->my_eye[pos].origin;
 return (ON_BOARD(origin) 
         && (current_owl_data->my_eye[origin].color
             == current_owl_data->color)
         && max_eyes(&current_owl_data->my_eye[origin].value) >= 2);
}


/* Used by autohelpers.
* Returns 1 if (pos) is an eyespace for the color of the dragon currently
* under owl investigation.
*/
int
owl_mineye(int pos)
{
 int origin;
 ASSERT_ON_BOARD1(pos);
 
 origin = current_owl_data->my_eye[pos].origin;
 if (!ON_BOARD(origin)
     || (current_owl_data->my_eye[origin].color
         != current_owl_data->color))
   return 0;
     
 return min_eyes(&current_owl_data->my_eye[origin].value);
}


/* Used by autohelpers.
* Returns 1 if (pos) is an eyespace for the color of the dragon currently
* under owl investigation.
*/
int
owl_maxeye(int pos)
{
 int origin;
 ASSERT_ON_BOARD1(pos);
 
 origin = current_owl_data->my_eye[pos].origin;
 if (!ON_BOARD(origin)
     || (current_owl_data->my_eye[origin].color
         != current_owl_data->color))
   return 0;
     
 return max_eyes(&current_owl_data->my_eye[origin].value);
}


/* Used by autohelpers.
* Returns 1 if (pos) is a non-marginal eyespace for the color of the
* dragon currently under owl investigation.
*/
int
owl_proper_eye(int pos)
{
 ASSERT_ON_BOARD1(pos);

 return ((current_owl_data->my_eye[pos].color
          == current_owl_data->color)
         && !current_owl_data->my_eye[pos].marginal);
}
 

/* Used by autohelpers.
* Returns the effective size of the eyespace at pos.
*/
int
owl_eye_size(int pos)
{
 int origin;
 ASSERT_ON_BOARD1(pos);

 origin = current_owl_data->my_eye[pos].origin;
 return current_owl_data->my_eye[origin].esize
        - current_owl_data->my_eye[origin].msize;
}
 

/* Used by autohelpers.
* Returns whether str is a lunch.
*/
int
owl_lunch(int str)
{
 int k;
 int origin;
 ASSERT_ON_BOARD1(str);
 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)
     break;
   if (current_owl_data->lunch[k] == origin)
     return 1;
 }

 return 0;
}
 

/* Used by autohelpers.

* 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.
*/
int
owl_strong_dragon(int pos)
{
 ASSERT_ON_BOARD1(pos);
 ASSERT1(IS_STONE(board[pos]), pos);
 
 return (!current_owl_data->goal[pos]
         && dragon[pos].color == board[pos]
         && dragon[pos].crude_status == ALIVE);
}
 

static int
owl_escape_route(struct local_owl_data *owl)
{
 signed char modified_escape[BOARDMAX];
 int pos;
 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.
*/
static void
reduced_init_owl(struct local_owl_data **owl, int at_bottom_of_stack)
{
 if (at_bottom_of_stack)
   owl_stack_pointer = 0;
 else
   owl_stack_pointer++;

 check_owl_stack_size();
 *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).
*/
static void
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);
 if (move != NO_MOVE)
   owl_update_goal(move, SAME_DRAGON_MAYBE_CONNECTED, NO_MOVE, *owl, 0, NULL);
 compute_owl_escape_values(*owl);
}


/***********************
* Storage of owl data
***********************/

/* Check the size of the owl stack and extend it if too small. */
static void
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);
   owl_stack_size++;
 }
}

/* Push owl data one step upwards in the stack. Gets called from
* push_owl.
*/
static void
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));
 /* Copy the 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. */
 *owl = new_owl;
}


/* 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.
*/
static void
push_owl(struct local_owl_data **owl)
{
 owl_stack_pointer++;
 check_owl_stack_size();
 do_push_owl(owl);
}


/* Retrieve owl data from the stack. */
static void
pop_owl(struct local_owl_data **owl)
{
 *owl = (*owl)->restore_from;
 owl_stack_pointer--;
}


/*
* List worms in order to track captures during owl reading
* (GAIN/LOSS codes)
*/
static int
list_goal_worms(struct local_owl_data *owl, int goal_worm[MAX_GOAL_WORMS])
{
 int pos, k;
 int w = 0;

 for (k = 0; k < MAX_GOAL_WORMS; k++)
   goal_worm[k] = NO_MOVE;

 for (pos = BOARDMIN; pos < BOARDMAX && w < MAX_GOAL_WORMS; pos++) {
   if (ON_BOARD(pos)
       && board[pos]
       && owl->goal[pos] == 1) {
     int origin = find_origin(pos);
     for (k = 0; k < w; k++)
       if (goal_worm[k] == origin) 
         break;
     if (k == w)
       goal_worm[w++] = pos;
   }
 }

 /* experimental: let's try to fill up the array with other neighboring
  * opponent worms
  */
 if (1 && (w > 0) && (w < MAX_GOAL_WORMS)) {
   pos = goal_worm[0];
   for (k = 0; k < DRAGON2(pos).neighbors && w < MAX_GOAL_WORMS; k++) {
     int ii;
     int d = DRAGON2(pos).adjacent[k];
     if (DRAGON(d).color != owl->color)
       continue;

     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)
         goal_worm[w++] = ii;
   }
 }

 return w;
}

static void
prepare_goal_list(int str, struct local_owl_data *owl,
                 int list[MAX_GOAL_WORMS], int *flag,
                 int *kworm, int do_list)
{
 gg_assert(flag != NULL);

 if (kworm) {
   if (do_list)
     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]));
   *flag = 1;
 }
 else
   *flag = 0;
}

static void
finish_goal_list(int *flag, int *wpos, int list[MAX_GOAL_WORMS], int index)
{
 gg_assert(flag != NULL);
 gg_assert(wpos != NULL);

 *flag = 0;
 if (index == MAX_GOAL_WORMS)
   *wpos = NO_MOVE;
 else
   *wpos = list[index];
}


/* Returns the number of worms in the goal dragon, and a pointer to each */

#if 0
static int
catalog_goal(struct local_owl_data *owl, int goal_worm[MAX_GOAL_WORMS])
{
 int pos;
 int worms = 0;
 int k;

 for (k = 0; k < MAX_WORMS; k++)
   goal_worm[k] = NO_MOVE;

 for (pos = BOARDMIN; pos < BOARDMAX && worms < MAX_WORMS; pos++)
   if (ON_BOARD(pos)
       && board[pos]
       && (owl->goal)[pos]) {
     int origin = find_origin(pos);
     if (pos == origin) {
       if (0) {
         DEBUG(DEBUG_SEMEAI, "goal worm: %1m\n", pos);
       }
       goal_worm[worms++] = pos;
     }
   }
 return worms;
}
#endif

/***********************/

/* Clear statistics. */
void
reset_owl_node_counter()
{
 global_owl_node_counter = 0;
}


/* Retrieve statistics. */
int
get_owl_node_counter()
{
 return global_owl_node_counter;
}


/*
* Local Variables:
* tab-width: 8
* c-basic-offset: 2
* End:
*/