/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
 * 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 and 2004                   *
 * 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 2             *
 *                                                                   *
 * 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., 59 Temple Place - Suite 330,           *
 * Boston, MA 02111, USA.                                            *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#include "gnugo.h"

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdarg.h>
#include <math.h>

#include "liberty.h"
#include "sgftree.h"
#include "random.h"
#include "gg_utils.h"


/*
 * Change the status of all the stones in the dragon at (dr).
 */

void
change_dragon_status(int dr, int status)
{
  int pos;
  int origin = dragon[dr].origin;

  for (pos = BOARDMIN; pos < BOARDMAX; pos++)
    if (ON_BOARD(pos)) {
      if (dragon[pos].origin == origin)
	dragon[pos].status = status;
    }
}


/*
 * Check whether a move at (move) stops the enemy from playing at (apos).
 */

int
defend_against(int move, int color, int apos)
{
  if (trymove(move, color, "defend_against", NO_MOVE)) {
    if (safe_move(apos, OTHER_COLOR(color)) == 0) {
      popgo();
      return 1;
    }
    popgo();
  }
  return 0;
}


/* 
 * Returns true if color can cut at (pos), or if connection through (pos)
 * is inhibited. This information is collected by find_cuts(), using the B
 * patterns in the connections database.
 */

int
cut_possible(int pos, int color)
{
  return (cutting_points[pos] & OTHER_COLOR(color)) != 0;
}


/*
 * does_attack(move, str) returns true if the move at (move)
 * attacks (str). This means that it captures the string, and that
 * (str) is not already dead.
 */

int
does_attack(int move, int str)
{
  int color = board[str];
  int other = OTHER_COLOR(color);
  int result = 0;
  int acode = 0;
  int dcode = 0;
  int spos = NO_MOVE;
  
  if (stackp == 0) {
    if (worm[str].attack_codes[0] != 0 
	&& worm[str].defense_codes[0] == 0)
      return 0;
    spos = worm[str].defense_points[0];
  }
  else {
    attack_and_defend(str, &acode, NULL, &dcode, &spos);
    if (acode != 0 && dcode == 0)
      return 0;
  }
  
  if (trymove(move, other, "does_attack-A", str)) {
    if (!board[str] || !find_defense(str, NULL)) {
      result = WIN;
      increase_depth_values();
      if (spos != NO_MOVE && trymove(spos, color, "does_attack-B", str)) {
	if (board[str] && !attack(str, NULL))
	  result = 0;
	popgo();
      }
      decrease_depth_values();
    }
    popgo();
  }

  return result;
}


/*
 * does_defend(move, str) returns true if the move at (move)
 * defends (str). This means that it defends the string, and that
 * (str) can be captured if no defense is made.
 */

int
does_defend(int move, int str)
{
  int color = board[str];
  int other = OTHER_COLOR(color);
  int result = 0;
  int spos = NO_MOVE;

  if (stackp == 0) {
    if (worm[str].attack_codes[0] == 0)
      return 0;
    else
      spos = worm[str].attack_points[0];
  }
  else if (!attack(str, &spos))
    return 0;

  gg_assert(spos != NO_MOVE);
  
  if (trymove(move, color, "does_defend-A", str)) {
    if (!attack(str, NULL)) {
      result = 1;
      increase_depth_values();
      if (trymove(spos, other, "does_defend-B", str)) {
	if (!board[str] || !find_defense(str, NULL))
	  result = 0;
	popgo();
      }
      decrease_depth_values();
    }
    popgo();
  }

  return result;
}


/* 
 * Example: somewhere(WHITE, 2, apos, bpos, cpos).
 * 
 * Returns true if one of the vertices listed
 * satisfies board[pos]==color. Here num_moves is the
 * number of moves. If check_alive is true, the dragon is not allowed
 * to be dead. This check is only valid if stackp==0.
 */

int
somewhere(int color, int check_alive, int num_moves, ...)
{
  va_list ap;
  int pos;
  int k;

  gg_assert(stackp == 0 || !check_alive);
  
  va_start(ap, num_moves);
  for (k = 0; k < num_moves; k++) {
    pos = va_arg(ap, int);

    if (board[pos] == color
	&& (!check_alive || dragon[pos].status != DEAD))
      return 1;
  }

  return 0;
}

/* Search along the edge for the first visible stone. Start at apos
 * and move in the direction of bpos. Return 1 if the first visible
 * stone is of the given color. It is required that apos and bpos are
 * at the same distance from the edge.
 *
 * FIXME: The detection of the first visible stone is quite crude and
 * probably needs to be improved.
 */
int
visible_along_edge(int color, int apos, int bpos)
{
  int ai = I(apos);
  int aj = J(apos);
  int bi = I(bpos);
  int bj = J(bpos);
  int pos;
  int forward;
  int up;
  ASSERT1((ai == bi) ^ (aj == bj), apos);

  if (ai == bi) {
    if (aj > bj)
      forward = WEST(0);
    else
      forward = EAST(0);

    if (ai < board_size/2) {
      pos = POS(0, bj);
      up = SOUTH(0);
    }
    else {
      pos = POS(board_size - 1, bj);
      up = NORTH(0);
    }
  }
  else {
    if (ai > bi)
      forward = NORTH(0);
    else
      forward = SOUTH(0);

    if (aj < board_size/2) {
      pos = POS(bi, 0);
      up = EAST(0);
    }
    else {
      pos = POS(bi, board_size - 1);
      up = WEST(0);
    }
  }
  
  for (; ON_BOARD(pos); pos += forward) {
    int k;
    for (k = 4; k >= 0; k--) {
      ASSERT_ON_BOARD1(pos + k * up);
      if (board[pos + k * up] == color)
	return 1;
      else if (board[pos + k * up] == OTHER_COLOR(color))
	return 0;
    }
  }

  return 0;
}

/* Is the board symmetric (or rather antisymmetric) with respect to
 * mirroring in tengen after a specific move has been played? If the
 * move is PASS_MOVE, check the current board.
 *
 * If strict is set we require that each stone is matched by a stone
 * of the opposite color at the mirrored vertex. Otherwise we only
 * require that each stone is matched by a stone of either color.
 */
int
test_symmetry_after_move(int move, int color, int strict)
{
  int pos;
  int result = 1;

  if (move != PASS_MOVE) {
    if (board[move] != EMPTY)
      return 0;
    if (!trymove(move, color, "find_mirror_move", NO_MOVE))
      return 0;
  }
  
  for (pos = BOARDMIN; pos < MIRROR_MOVE(pos); pos++) {
    int sum;
    if (!ON_BOARD(pos))
      continue;
    
    sum = board[pos] + board[MIRROR_MOVE(pos)];
    if (sum != EMPTY + EMPTY && sum != BLACK + WHITE) {
      if (strict || sum == EMPTY + WHITE || sum == EMPTY + BLACK) {
      result = 0;
      break;
      }
    }
  }

  if (move != PASS_MOVE)
    popgo();
  
  return result;
}


/* The function play_break_through_n() plays a sequence of moves,
 * alternating between the players and starting with color. After
 * having played through the sequence, the three last coordinate pairs
 * gives a position to be analyzed by break_through(), to see whether
 * either color has managed to enclose some stones and/or connected
 * his own stones. If any of the three last positions is empty, it's
 * assumed that the enclosure has failed, as well as the attempt to
 * connect.
 *
 * If one or more of the moves to play turns out to be illegal for
 * some reason, the rest of the sequence is played anyway, and
 * break_through() is called as if nothing special happened.
 *
 * Like break_through(), this function returns 1 if the attempt to
 * break through was succesful and 2 if it only managed to cut
 * through.
 */
   
int
play_break_through_n(int color, int num_moves, ...)
{
  va_list ap;
  int mcolor = color;
  int success = 0;
  int i;
  int played_moves = 0;
  int apos;
  int xpos;
  int ypos;
  int zpos;
  
  va_start(ap, num_moves);

  /* Do all the moves with alternating colors. */
  for (i = 0; i < num_moves; i++) {
    apos = va_arg(ap, int);

    if (apos != NO_MOVE
	&& (trymove(apos, mcolor, "play_break_through_n", NO_MOVE)
	    || tryko(apos, mcolor, "play_break_through_n")))
      played_moves++;
    mcolor = OTHER_COLOR(mcolor);
  }

  /* Now do the real work. */
  xpos = va_arg(ap, int);
  ypos = va_arg(ap, int);
  zpos = va_arg(ap, int);
    
  /* Temporarily increase the depth values with the number of explicitly
   * placed stones.
   */
#if 0
  modify_depth_values(played_moves);
#endif
  
  if (board[xpos] == EMPTY
      || board[ypos] == EMPTY
      || board[zpos] == EMPTY)
    success = 1;
  else
    success = break_through(xpos, ypos, zpos);

#if 0
  modify_depth_values(-played_moves);
#endif
  
  /* Pop all the moves we could successfully play. */
  for (i = 0; i < played_moves; i++)
    popgo();

  va_end(ap);
  return success;
}


/* The function play_attack_defend_n() plays a sequence of moves,
 * alternating between the players and starting with color. After
 * having played through the sequence, the last coordinate pair gives
 * a target to attack or defend, depending on the value of do_attack.
 * If there is no stone present to attack or defend, it is assumed
 * that it has already been captured. If one or more of the moves to
 * play turns out to be illegal for some reason, the rest of the
 * sequence is played anyway, and attack/defense is tested as if
 * nothing special happened.
 *
 * A typical use for these functions is to set up a ladder in an
 * autohelper and see whether it works or not.
 */
   
int
play_attack_defend_n(int color, int do_attack, int num_moves, ...)
{
  va_list ap;
  int mcolor = color;
  int success = 0;
  int i;
  int played_moves = 0;
  int apos;
  int zpos;
  
  va_start(ap, num_moves);

  /* Do all the moves with alternating colors. */
  for (i = 0; i < num_moves; i++) {
    apos = va_arg(ap, int);

    if (apos != NO_MOVE
	&& (trymove(apos, mcolor, "play_attack_defend_n", NO_MOVE)
	    || tryko(apos, mcolor, "play_attack_defend_n")))
      played_moves++;
    mcolor = OTHER_COLOR(mcolor);
  }

  /* Now do the real work. */
  zpos = va_arg(ap, int);

  /* Temporarily increase the depth values with the number of explicitly
   * placed stones.
   *
   * This improves the reading of pattern constraints but
   * unfortunately tends to be too expensive. For the time being it is
   * disabled.
   */
#if 0
  modify_depth_values(played_moves);
#endif
  
  if (do_attack) {
    if (board[zpos] == EMPTY)
      success = WIN;
    else
      success = attack(zpos, NULL);
  }
  else {
    if (board[zpos] == EMPTY)
      success = 0;
    else {
      int dcode = find_defense(zpos, NULL);
      if (dcode == 0 && !attack(zpos, NULL))
	success = WIN;
      else
	success = dcode;
    }
  }

#if 0
  modify_depth_values(-played_moves);
#endif
  
  /* Pop all the moves we could successfully play. */
  for (i = 0; i < played_moves; i++)
    popgo();

  va_end(ap);
  return success;
}


/* The function play_attack_defend2_n() plays a sequence of moves,
 * alternating between the players and starting with color. After
 * having played through the sequence, the two last coordinate pairs
 * give two targets to simultaneously attack or defend, depending on
 * the value of do_attack. If there is no stone present to attack or
 * defend, it is assumed that it has already been captured. If one or
 * more of the moves to play turns out to be illegal for some reason,
 * the rest of the sequence is played anyway, and attack/defense is
 * tested as if nothing special happened.
 *
 * A typical use for these functions is to set up a crosscut in an
 * autohelper and see whether at least one cutting stone can be
 * captured.
 */
   
int
play_attack_defend2_n(int color, int do_attack, int num_moves, ...)
{
  va_list ap;
  int mcolor = color;
  int success = 0;
  int i;
  int played_moves = 0;
  int apos;
  int ypos;
  int zpos;
  
  va_start(ap, num_moves);

  /* Do all the moves with alternating colors. */
  for (i = 0; i < num_moves; i++) {
    apos = va_arg(ap, int);

    if (apos != NO_MOVE
	&& (trymove(apos, mcolor, "play_attack_defend_n", NO_MOVE)
	    || tryko(apos, mcolor, "play_attack_defend_n")))
      played_moves++;
    mcolor = OTHER_COLOR(mcolor);
  }

  /* Now do the real work. */
  ypos = va_arg(ap, int);
  zpos = va_arg(ap, int);

  /* Temporarily increase the depth values with the number of explicitly
   * placed stones.
   */
#if 0
  modify_depth_values(played_moves);
#endif
  

  /* FIXED: tm - returns ko results correctly (3.1.22) */
  if (do_attack) {
    if (board[ypos] == EMPTY || board[zpos] == EMPTY)
      success = WIN;
    else
      success = attack_either(ypos, zpos);
  }
  else {
    if (board[ypos] == EMPTY || board[zpos] == EMPTY)
      success = 0;
    else
      success = defend_both(ypos, zpos);
  }

#if 0
  modify_depth_values(-played_moves);
#endif
  
  /* Pop all the moves we could successfully play. */
  for (i = 0; i < played_moves; i++)
    popgo();

  va_end(ap);
  return success;
}


/* The function play_connect_n() plays a sequence of moves,
 * alternating between the players and starting with color. After
 * having played through the sequence, the two last coordinates
 * give two targets that should be connected or disconnected, depending on
 * the value of do_connect. If there is no stone present to connect or
 * disconnect, it is assumed that the connection has failed. If one or
 * more of the moves to play turns out to be illegal for some reason,
 * the rest of the sequence is played anyway, and connection/disconnection
 * is tested as if nothing special happened.
 */

int 
play_connect_n(int color, int do_connect, int num_moves, ...)
{
  va_list ap;
  int mcolor = color;
  int success = 0;
  int i;
  int played_moves = 0;
  int apos;
  int ypos;
  int zpos;

  va_start(ap, num_moves);

  /* Do all the moves with alternating colors. */
  for (i = 0; i < num_moves; i++) {
    apos = va_arg(ap, int);

    if (apos != NO_MOVE
	&& (trymove(apos, mcolor, "play_connect_n", NO_MOVE)
	    || tryko(apos, mcolor, "play_connect_n")))
      played_moves++;
    mcolor = OTHER_COLOR(mcolor);
  }

  /* Now do the real work. */
  ypos = va_arg(ap, int);
  zpos = va_arg(ap, int);

  /* Temporarily increase the depth values with the number of explicitly
   * placed stones.
   *
   * This improves the reading of pattern constraints but
   * unfortunately tends to be too expensive. For the time being it is
   * disabled.
   */
#if 0
  modify_depth_values(played_moves);
#endif
  
  /* See if ypos and zpos can be connected (or disconnected). */
  if (do_connect) {
    if (board[ypos] == EMPTY || board[zpos] == EMPTY)
      success = 0;
    else
      success = string_connect(ypos, zpos, NULL);
  }
  else {
    if (board[ypos] == EMPTY || board[zpos] == EMPTY)
      success = WIN;
    else
      success = disconnect(ypos, zpos, NULL);
  }

#if 0
  modify_depth_values(-played_moves);
#endif
  
  /* Pop all the moves we could successfully play. */
  for (i = 0; i < played_moves; i++)
    popgo();

  va_end(ap);
  return success;
}



/* 
 * It is assumed in reading a ladder if stackp >= depth that
 * as soon as a bounding stone is in atari, the string is safe.
 * It is used similarly at other places in reading.c to implement simplifying
 * assumptions when stackp is large. DEPTH is the default value of depth.
 *
 * Unfortunately any such scheme invites the ``horizon effect.'' Increasing
 * DEPTH will make the program stronger and slower.
 *
 */

/* Tactical reading using C functions */
#define DEPTH                16
#define BRANCH_DEPTH         13
#define BACKFILL_DEPTH       12
#define BACKFILL2_DEPTH       5
#define BREAK_CHAIN_DEPTH     7
#define SUPERSTRING_DEPTH     7
#define FOURLIB_DEPTH         7
#define KO_DEPTH              8

#if 0
#undef FOURLIB_DEPTH
#define FOURLIB_DEPTH         9
#endif


#define AA_DEPTH              6

/* Pattern based reading */
#define OWL_DISTRUST_DEPTH    6
#define OWL_BRANCH_DEPTH      8
#define OWL_READING_DEPTH    20
#define SEMEAI_BRANCH_DEPTH  12
#define SEMEAI_BRANCH_DEPTH2  6

/* Connecton reading */
#define CONNECT_NODE_LIMIT 2000
#define CONNECT_DEPTH        64
#define CONNECT_DEPTH2       20

#define BREAKIN_NODE_LIMIT  400
#define BREAKIN_DEPTH	     14

/* Set the various reading depth parameters. If mandated_depth_value
 * is not -1 that value is used; otherwise the depth values are
 * set as a function of level. The parameter mandated_depth_value
 * can be set at the command line to force a particular value of
 * depth; normally it is -1.
 */

void
set_depth_values(int level, int report_levels)
{
  static int node_limits[] = {500, 500, 450, 400, 400, 325, 275,
			      200, 150, 100, 75, 50};
  int depth_level;

  /*
   * Other policies depending on level:
   * aftermath.c:   >=  8: call estimate_score().
   * dragon.c:      >=  8: compute owl threats (currently disabled)
   * genmove.c:     >=  8: call estimate_score().
   * owl.c:         >=  9: use vital attack pattern database
   *                >=  8: increase depth values in owl_substantial
   *                >=  8: don't turn off owl_phase in semeai reading
   * reading.c:     >=  8: Use superstrings and do more backfilling.
   * value_moves.c: >=  6: try to find more owl attacks/defenses
   * breakin.c:     >= 10: try to find break-ins. (*)
   *
   * The break-in code (*) is particularly expensive. 
   *
   * Speedups between levels 9 and 10 and between levels 7 and 8
   * are obtained by turning off services, and between these
   * levels no changes are made in the depths. The parameter
   * depth_level is the correction compared to the default settings at level
   * 10 for most reading depths.
   */
  if (level >= 10)
    depth_level = level - 10;
  else if (level == 9)
    depth_level = 0;
  else if (level == 8)
    depth_level = -1;
  else 
    depth_level = level - 8;

  depth                = gg_max(6, DEPTH 	    + depth_level);
  branch_depth         = gg_max(3, BRANCH_DEPTH	    + depth_level);
  backfill_depth       = gg_max(2, BACKFILL_DEPTH    + depth_level);
  backfill2_depth      = gg_max(1, BACKFILL2_DEPTH   + depth_level);
  break_chain_depth    = gg_max(2, BREAK_CHAIN_DEPTH + depth_level);
  if (level >= 8)
    owl_distrust_depth = gg_max(1, (2 * OWL_DISTRUST_DEPTH + depth_level) / 2);
  else
    owl_distrust_depth = gg_max(1, (2 * OWL_DISTRUST_DEPTH - 1
				    + depth_level) / 2);
  owl_branch_depth     = gg_max(2, (2 * OWL_BRANCH_DEPTH   + depth_level) / 2);
  owl_reading_depth    = gg_max(5, (2 * OWL_READING_DEPTH  + depth_level) / 2);

  /* Atari-atari depth levels are unchanged only between levels 7/8, 9/10: */
  if (level >= 10)
    aa_depth = gg_max(0, AA_DEPTH + (level - 10));
  else if (level == 9)
    aa_depth = gg_max(0, AA_DEPTH);
  else if (level >= 7)
    aa_depth = gg_max(0, AA_DEPTH - 1);
  else
    aa_depth = gg_max(0, AA_DEPTH - (8 - level));

  /* Exceptions:
   * fourlib_depth: This is constant from levels 7 to 10.
   * superstring_depth: set to 0 below level 8.
   */
  if (level >= 10)
    ko_depth            = gg_max(1, KO_DEPTH + (level - 10));
  else if (level == 9)
    ko_depth            = gg_max(1, KO_DEPTH);
  else if (level >= 7)
    ko_depth            = gg_max(1, KO_DEPTH - 1);
  else
    ko_depth            = gg_max(1, KO_DEPTH + (level - 8));

  if (level >= 10)
    fourlib_depth       = gg_max(1, FOURLIB_DEPTH + (level - 10));
  else if (level >= 7)
    fourlib_depth       = gg_max(1, FOURLIB_DEPTH);
  else
    fourlib_depth       = gg_max(1, FOURLIB_DEPTH + (level - 7));

  if (level >= 8)
    superstring_depth = gg_max(1, SUPERSTRING_DEPTH);
  else
    superstring_depth = 0;

  if (level >= 10)
    owl_node_limit      = OWL_NODE_LIMIT * pow(1.5, depth_level);
  else {
    owl_node_limit      = (OWL_NODE_LIMIT * node_limits[10 - level] /
			   node_limits[0]);
    owl_node_limit      = gg_max(20, owl_node_limit);
  }

  semeai_branch_depth  = gg_max(2, (2*SEMEAI_BRANCH_DEPTH  + depth_level) / 2);
  semeai_branch_depth2 = gg_max(2, (2*SEMEAI_BRANCH_DEPTH2 + depth_level) / 2);
  semeai_node_limit    = SEMEAI_NODE_LIMIT * pow(1.5, depth_level);

  connect_depth         = gg_max(2, CONNECT_DEPTH  + 2 * depth_level);
  connect_depth2        = gg_max(2, CONNECT_DEPTH2 + 2 * depth_level);
  connection_node_limit = CONNECT_NODE_LIMIT * pow(1.5, depth_level);
  breakin_depth 	= gg_max(2, BREAKIN_DEPTH + 2 * depth_level);
  breakin_node_limit 	= BREAKIN_NODE_LIMIT * pow(1.5, depth_level);

  if (mandated_depth != -1)
    depth = mandated_depth;
  if (mandated_backfill_depth != -1)
    backfill_depth = mandated_backfill_depth;
  if (mandated_backfill2_depth != -1)
    backfill2_depth = mandated_backfill2_depth;
  if (mandated_break_chain_depth != -1)
    break_chain_depth = mandated_break_chain_depth;
  if (mandated_superstring_depth != -1)
    superstring_depth = mandated_superstring_depth;
  if (mandated_branch_depth != -1)
    branch_depth = mandated_branch_depth;
  if (mandated_fourlib_depth != -1)
    fourlib_depth = mandated_fourlib_depth;
  if (mandated_ko_depth != -1)
    ko_depth = mandated_ko_depth;
  if (mandated_aa_depth != -1)
    aa_depth = mandated_aa_depth;
  if (mandated_owl_distrust_depth != -1)
    owl_distrust_depth = mandated_owl_distrust_depth;
  if (mandated_owl_branch_depth != -1)
    owl_branch_depth = mandated_owl_branch_depth;
  if (mandated_owl_reading_depth != -1)
    owl_reading_depth = mandated_owl_reading_depth;
  if (mandated_owl_node_limit != -1)
    owl_node_limit = mandated_owl_node_limit;

  depth_offset = 0;
  
  if (report_levels) {
    fprintf(stderr, "at level %d:\n\n\
depth: %d\n\
branch_depth: %d\n\
backfill_depth: %d\n\
backfill2_depth: %d\n\
break_chain_depth: %d\n\
owl_distrust_depth: %d\n\
owl_branch_depth: %d\n\
owl_reading_depth: %d\n\
aa_depth: %d\n\
ko_depth: %d\n\
fourlib_depth: %d\n\
superstring_depth: %d\n\
owl_node_limit: %d\n\
semeai_branch_depth: %d\n\
semeai_branch_depth2: %d\n\
semeai_node_limit: %d\n\
connect_depth: %d\n\
connect_depth2: %d\n\
connection_node_limit: %d\n\
breakin_depth: %d\n\
breakin_node_limit: %d\n\n",
	    level, depth, branch_depth, backfill_depth, backfill2_depth,
	    break_chain_depth, owl_distrust_depth, owl_branch_depth,
	    owl_reading_depth, aa_depth, ko_depth, fourlib_depth,
	    superstring_depth, owl_node_limit, semeai_branch_depth, 
	    semeai_branch_depth2, semeai_node_limit, connect_depth, 
            connect_depth2, connection_node_limit, breakin_depth, 
	    breakin_node_limit);
  }
}


/*
 * Modify the various tactical reading depth parameters. This is
 * typically used to avoid horizon effects. By temporarily increasing
 * the depth values when trying some move, one can avoid that an
 * irrelevant move seems effective just because the reading hits a
 * depth limit earlier than it did when reading only on relevant
 * moves.
 */

void
modify_depth_values(int n)
{
  depth              += n;
  backfill_depth     += n;
  backfill2_depth    += n;
  break_chain_depth  += n;
  superstring_depth  += n;
  branch_depth       += n;
  fourlib_depth      += n;
  ko_depth           += n;
  breakin_depth	     += n;
  depth_offset       += n;
}

void
increase_depth_values(void)
{
  modify_depth_values(1);
}

void
decrease_depth_values(void)
{
  modify_depth_values(-1);
}

/* These functions allow more drastic temporary modifications of the
 * depth values. Typical use is to turn certain depth values way down
 * for reading where speed is more important than accuracy, e.g. for
 * the influence function.
 */

static int save_depth;
static int save_backfill_depth;
static int save_backfill2_depth;
static int save_break_chain_depth;
static int save_superstring_depth;
static int save_branch_depth;
static int save_fourlib_depth;
static int save_ko_depth;

/* Currently this function is never called. */

void
set_temporary_depth_values(int d, int b, int b2, int bc,
			   int ss, int br, int f, int k)
{
  save_depth             = depth;
  save_backfill_depth    = backfill_depth;
  save_backfill2_depth   = backfill2_depth;
  save_break_chain_depth = break_chain_depth;
  save_superstring_depth = superstring_depth;
  save_branch_depth      = branch_depth;
  save_fourlib_depth     = fourlib_depth;
  save_ko_depth          = ko_depth;

  depth             = d;
  backfill_depth    = b;
  backfill2_depth   = b2;
  break_chain_depth = bc;
  superstring_depth = ss;
  branch_depth      = br;
  fourlib_depth     = f;
  ko_depth          = k;
}

void
restore_depth_values()
{
  depth             = save_depth;
  backfill_depth    = save_backfill_depth;
  backfill2_depth   = save_backfill2_depth;
  break_chain_depth = save_break_chain_depth;
  superstring_depth = save_superstring_depth;
  branch_depth      = save_branch_depth;
  fourlib_depth     = save_fourlib_depth;
  ko_depth          = save_ko_depth;
}

/*******************
 * Detect blunders *
 *******************/

static int detect_owl_blunder(int move, int color, int *defense_point,
			      char safe_stones[BOARDMAX], int liberties,
			      float *return_value, int save_verbose);

static void detect_tactical_blunder(int move, int color, int *defense_point,
				    char safe_stones[BOARDMAX],
				    int liberties, int *libs,
				    float *return_value, int save_verbose);

/* Check that the move at color doesn't involve any kind of blunder,
 * regardless of size.
 */
int
confirm_safety(int move, int color, int *defense_point,
	       char safe_stones[BOARDMAX])
{
  return (blunder_size(move, color, defense_point, safe_stones) == 0.0);
}

/* This function will detect some blunders. If the move reduces the
 * number of liberties of an adjacent friendly string, there is a
 * danger that the move could backfire, so the function checks that no
 * friendly worm which was formerly not attackable becomes attackable,
 * and it checks that no opposing worm which was not defendable
 * becomes defendable.
 *
 * It returns the estimated size of the blunder, or 0.0 if nothing
 * bad has happened.
 *
 * The array safe_stones[] contains the stones that are supposedly
 * safe after (move). It may be NULL.
 *
 * For use when called from fill_liberty, this function may optionally
 * return a point of defense, which, if taken, will presumably make
 * the move at (move) safe on a subsequent turn.
 */

float
blunder_size(int move, int color, int *defense_point,
	     char safe_stones[BOARDMAX])
{
  int libs[5];
  int liberties = accuratelib(move, color, 5, libs);
  int trouble = 0;
  int save_verbose = verbose;
  float return_value = 0.0;
  int atari;
  char defense_moves[BOARDMAX];
  
  if (defense_point)
    *defense_point = NO_MOVE;

  TRACE("Checking safety of a %s move at %1m\n", color_to_string(color), move);

  if (verbose > 0)
    verbose--;

  /* We start by checking whether we have accidentally killed an own
   * dragon.
   */
  trouble = detect_owl_blunder(move, color, defense_point,
			       safe_stones, liberties,
			       &return_value, save_verbose);
  

  /* Next we see whether the move has caused tactical complications.
   * The trouble variable is set if a string next to the move with few
   * liberties has not gained liberties by the move.
   */
  if (trouble)
    detect_tactical_blunder(move, color, defense_point, safe_stones,
			    liberties, libs, &return_value, save_verbose);

  /* FIXME: We would also need a detect_semeai_blunder() to check
   * against moves which make the outcome of a semeai worse, e.g. by
   * letting the opponent live in seki.
   */

  
  /* Finally we call the atari-atari code to see whether the move has
   * set up some combination attack that didn't exist before. We do
   * this last to avoid duplicate blunder reports.
   */
  atari = atari_atari_blunder_size(color, move, defense_moves, safe_stones);
  if (atari) {
    if (defense_point) {
      /* FIXME: Choose defense point more systematically. */
      int pos;
      *defense_point = NO_MOVE;
      for (pos = BOARDMIN; pos < BOARDMAX; pos++)
	if (ON_BOARD(pos) && defense_moves[pos]) {
	  *defense_point = pos;
	  break;
	}
    }
    verbose = save_verbose;
    TRACE("Combination attack appears.\n");
    return_value += (float) atari;
  }

  verbose = save_verbose;
  return return_value;
}

/* Check whether we have accidentally killed an own dragon adjacent to
 * move. If this happens, we mark its stones as no longer safe, and
 * remember the dragon's size.
 */

static int
detect_owl_blunder(int move, int color, int *defense_point,
		   char safe_stones[BOARDMAX], int liberties,
		   float *return_value, int save_verbose)
{
  int k;
  int ii;
  int trouble = 0;
  int dragon_analyzed[4] = {0, 0, 0, 0};
  int current_verbose = verbose;
  
  for (k = 0; k < 4; k++) {
    int bpos = move + delta[k];
    int j;
    /* We get worried if there is a liberty problem (and in this case
     * there might also be tactical trouble), or if we play inside
     * our eye space and the dragon is only just alive.
     */
    if (board[bpos] != color)
      continue;
    if (liberties <= worm[bpos].liberties
	&& liberties <= 4)
      trouble = 1;
    else
      if (min_eyes(&(DRAGON2(bpos).genus)) > 2
	  || !is_proper_eye_space(move))
	continue;

    /* Don't test the same dragon twice. */
    for (j = 0; j < k; j++)
      if (dragon_analyzed[j] == dragon[bpos].origin)
	break;
    if (j < k)
      continue;
    dragon_analyzed[k] = dragon[bpos].origin;

    /* Don't reanalyze if (move) is an owl defense for (bpos). */
    if (safe_stones && safe_stones[bpos] == OWL_SAVED_STONE)
      continue;

    if ((dragon[bpos].status == ALIVE
	 || (safe_stones 
	     && safe_stones[bpos]))
	&& DRAGON2(bpos).safety != INVINCIBLE
	&& DRAGON2(bpos).safety != STRONGLY_ALIVE) {
      int kworm = NO_MOVE;
      int acode = owl_confirm_safety(move, bpos, defense_point, &kworm);

      /* If owl couldn't confirm safety, maybe semeai can. */
      if (acode != WIN) {
	int r;
	for (r = 0; r < DRAGON2(bpos).neighbors; r++) {
	  int neighbor = dragon2[DRAGON2(bpos).adjacent[r]].origin;
	  int resultb;
	  if (board[neighbor] == color)
	    continue;
	  owl_analyze_semeai_after_move(move, color, neighbor, bpos,
					NULL, &resultb, NULL, 1, NULL, 0);
	  if (resultb == 0)
	    acode = WIN;
	}
      }
      
      if (acode == 0) {
	verbose = save_verbose;
	TRACE("Dragon at %1m becomes attackable.\n", bpos);
	verbose = current_verbose;
	*return_value += 2.0 * dragon[bpos].effective_size;
	if (safe_stones)
	  mark_dragon(bpos, safe_stones, 0);
      }
      else if (acode == LOSS) {
	verbose = save_verbose;
	TRACE("Dragon at %1m becomes attackable.\n", bpos);
	verbose = current_verbose;
	if (kworm == move) {
	  int l;
	  /* the worm origin was messed by our own move */
	  for (l = 0; l < 4; l++) {
	    int kworm = move + delta[l];
	    if (board[kworm] == color) {
	      *return_value += 2.0 * worm[kworm].effective_size;
	      if (safe_stones)
		for (ii = BOARDMIN; ii < BOARDMAX; ii++)
		  if (ON_BOARD(ii) && worm[ii].origin == worm[kworm].origin)
		    safe_stones[ii] = 0;
	    }
	  }
	}
	else {
	  *return_value += 2.0 * worm[kworm].effective_size;
	  if (safe_stones)
	    for (ii = BOARDMIN; ii < BOARDMAX; ii++)
	      if (ON_BOARD(ii) && worm[ii].origin == worm[kworm].origin)
		safe_stones[ii] = 0;
	}
      }
    }
  }

  return trouble;
}

/* Check whether a move causes any unexpected and unwelcome changes in
 * the tactical status of worms all over the board.
 */
static void
detect_tactical_blunder(int move, int color, int *defense_point,
			char safe_stones[BOARDMAX],
			int liberties, int *libs,
			float *return_value, int save_verbose)
{
  int other = OTHER_COLOR(color);
  int pos;
  int ii;
  int current_verbose = verbose;

  if (!trymove(move, color, NULL, NO_MOVE))
    return;
  
  /* Need to increase the depth values during this reading to avoid
   * horizon effects.
   */
  increase_depth_values();
  
  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
    if (!IS_STONE(board[pos])
	|| worm[pos].origin != pos
	|| pos == move)
      continue;
    
    /* First, we look for a new tactical attack. */
    if (board[pos] == color
	&& ((safe_stones && safe_stones[pos])
	    || (!safe_stones && worm[pos].attack_codes[0] == 0))
	&& attack(pos, NULL)) {
      /* A safe worm of ours has become attackable. */
      if (defense_point)
	find_defense(pos, defense_point);
      verbose = save_verbose;
      TRACE("After %1m Worm at %1m becomes attackable.\n", move, pos);
      verbose = current_verbose;
      *return_value += worm[pos].effective_size;
      if (safe_stones) /* Can't use mark_string. */
	for (ii = BOARDMIN; ii < BOARDMAX; ii++)
	  if (worm[ii].origin == worm[pos].origin)
	    safe_stones[ii] = 0;
    }
    else if (board[pos] == other
	     && worm[pos].origin == pos
	     && worm[pos].attack_codes[0] != 0
	     && worm[pos].defense_codes[0] == 0
	     && find_defense(pos, NULL)) {
      /* A dead opponent's worm has become defendable.
       * Also ask the owl code whether the string can live
       * strategically. To do this we need to temporarily undo
       * the trymove().
       */
      int owl_attacks;
      int defense_effective = 0;
      
      popgo();
      decrease_depth_values();
      owl_attacks = owl_does_attack(move, pos, NULL);
      if (owl_attacks != WIN) {
	*return_value += 2 * worm[pos].effective_size;
	defense_effective = 1;
	verbose = save_verbose;
	TRACE("After %1m worm at %1m becomes defendable - A.\n", move, pos);
	verbose = current_verbose;
      }
      else if (dragon[pos].status != ALIVE) {
	/* Before redoing the trymove we also check whether the worm now
	 * has a semeai defense. See blunder:26 for an example.
	 *
	 * If the worm already was alive in seki, it is generally okay
	 * that it also becomes tactically safe when the outer
	 * liberties are filled, see e.g. blunder:32,34. Thus the
	 * check above.
	 */
	int k;
	int adj[MAXCHAIN];
	int num_adj;
	num_adj = extended_chainlinks(pos, adj, 0);
	for (k = 0; k < num_adj; k++) {
	  int neighbor = adj[k];
	  int resulta;
	  owl_analyze_semeai_after_move(move, color, pos, neighbor,
					&resulta, NULL, NULL, 1, NULL, 1);
	  if (resulta != 0) {
	    *return_value += 2 * worm[pos].effective_size;
	    defense_effective = 1;
	    verbose = save_verbose;
	    TRACE("After %1m worm at %1m becomes defendable - B.\n",
		  move, pos);
	    verbose = current_verbose;
	    break;
	  }
	}
      }
      
      trymove(move, color, NULL, NO_MOVE);
      increase_depth_values();
      
      if (defense_effective && defense_point) {
	int dpos;
	if (attack(pos, &dpos)) {
	  *defense_point = dpos;
	  /* Check that this move is legal and effective also on the
           * original board, otherwise find a tactical attack there
           * instead.
	   */
	  popgo();
	  
	  if (!is_legal(dpos, color)
	      || play_attack_defend_n(color, 0, 1, dpos, pos))
	    attack(pos, defense_point);

	  /* Redo the move, we know that it won't fail. */
	  trymove(move, color, NULL, NO_MOVE);
	}
	else {
	  verbose = save_verbose;
	  TRACE("No attack found (unexpectedly) on %1m after move at %1m.\n",
		pos, move);
	  verbose = current_verbose;
	}
      }
    }
  }

  /* Look for double atari style complications of the move.
   *
   * FIXME: Since we have an atari_atari check in blunder_size(), do
   * we still need to do this step?
   */
  if (liberties == 2) {
    float d_a_blunder_size;
    if (double_atari(libs[0], other, &d_a_blunder_size, safe_stones)) {
      if (defense_point && safe_move(libs[0], color) == WIN)
	*defense_point = libs[0];
      *return_value += d_a_blunder_size;
      verbose = save_verbose;
      TRACE("Double threat appears at %1m.\n", libs[0]);
      verbose = current_verbose;
    }
    else if (double_atari(libs[1], other, &d_a_blunder_size, safe_stones)) {
      if (defense_point && safe_move(libs[1], color) == WIN)
	*defense_point = libs[1];
      *return_value += d_a_blunder_size;
      verbose = save_verbose;
      TRACE("Double threat appears at %1m.\n", libs[1]);
      verbose = current_verbose;
    }
  }
  
  /* Reset the depth values. */
  decrease_depth_values();

  popgo();
}


/* Returns true if a move by (color) fits the following shape:
 * 
 *
 *    X*        (O=color)
 *    OX
 * 
 * capturing one of the two X strings. The name is a slight
 * misnomer since this includes attacks which are not necessarily
 * double ataris, though the common double atari is the most
 * important special case.
 * 
 * If safe_stones != NULL, then only attacks on stones marked as safe are
 * tried.
 *
 * The value of the double atari attack is returned in *value (unless
 * value is NULL), and the attacked stones are marked unsafe.
 */

int
double_atari(int move, int color, float *value, char safe_stones[BOARDMAX])
{
  int other = OTHER_COLOR(color);
  int k;
  int m = I(move);
  int n = J(move);

  if (!ON_BOARD(move))
    return 0;

  /* Loop over the diagonal directions. */
  for (k = 4; k < 8; k++) {
    int dm = deltai[k];
    int dn = deltaj[k];
    
    /* because (m, n) and (m+dm, n+dn) are opposite
     * corners of a square, ON_BOARD2(m, n) && ON_BOARD2(m+dm, n+dn)
     * implies ON_BOARD2(m+dm, n) and ON_BOARD2(n, n+dn)
     *
     * Only try to attack supposedly safe stones.
     */
    if (BOARD(m+dm, n+dn) == color
	&& BOARD(m, n+dn) == other
	&& BOARD(m+dm, n) == other
	&& (!safe_stones
	    || (safe_stones[POS(m, n+dn)] && safe_stones[POS(m+dm, n)]))
	&& trymove(move, color, "double_atari", NO_MOVE)) {
      if (countlib(move) > 1
	  && (BOARD(m, n+dn) == EMPTY || BOARD(m+dm, n) == EMPTY 
	      || !defend_both(POS(m, n+dn), POS(m+dm, n)))) {
	popgo();
	if (value) {
	  if (worm[POS(m, n+dn)].effective_size
	      > worm[POS(m+dm, n)].effective_size) {
	    *value = 2.0 * worm[POS(m, n+dn)].effective_size;
	    if (safe_stones)
	      mark_string(POS(m, n+dn), safe_stones, 0);
	  }
	  else {
	    *value = 2.0 * worm[POS(m+dm, n)].effective_size;
	    if (safe_stones)
	      mark_string(POS(m+dm, n), safe_stones, 0);
	  }
	}
	return 1;
      }
      popgo();
    }
  }
  
  return 0;
}
    

static int
capture_non_invincible_strings(int color, int exceptions[BOARDMAX])
{
  int other = OTHER_COLOR(color);
  int something_captured = 1; /* To get into the first turn of the loop. */
  int moves_played = 0;
  int save_moves;
  int libs[MAXLIBS];
  int liberties;
  int pos;
  int k;
  
  while (something_captured) {
    /* Nothing captured so far in this turn of the loop. */
    something_captured = 0;

    /* Visit all friendly strings on the board. */
    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
      if (board[pos] != color || find_origin(pos) != pos)
	continue;

      if (exceptions && exceptions[pos])
	continue;
      
      /* Try to capture the string at pos. */
      liberties = findlib(pos, MAXLIBS, libs);
      save_moves = moves_played;
      for (k = 0; k < liberties; k++) {
	if (trymove(libs[k], other, "unconditional_life", pos))
	  moves_played++;
      }
      
      /* Successful if already captured or a single liberty remains.
       * Otherwise we must rewind and take back the last batch of moves.
       */
      if (board[pos] == EMPTY)
	something_captured = 1;
      else if (findlib(pos, 2, libs) == 1) {
	/* Need to use tryko as a defense against the extreme case
	 * when the only opponent liberty that is not suicide is an
	 * illegal ko capture, like in this 5x5 position:
	 * +-----+
	 * |.XO.O|
	 * |XXOO.|
	 * |X.XOO|
	 * |XXOO.|
	 * |.XO.O|
	 * +-----+
	 */
	int success = tryko(libs[0], other, "unconditional_life");
	gg_assert(success);
	moves_played++;
	something_captured = 1;
      }
      else
	while (moves_played > save_moves) {
	  popgo();
	  moves_played--;
	}
    }
  }
  return moves_played;
}

/* Find those worms of the given color that can never be captured,
 * even if the opponent is allowed an arbitrary number of consecutive
 * moves. The coordinates of the origins of these worms are written to
 * the worm arrays and the number of non-capturable worms is
 * returned.
 *
 * The algorithm is to cycle through the worms until none remains or
 * no more can be captured. A worm is removed when it is found to be
 * capturable, by letting the opponent try to play on all its
 * liberties. If the attack fails, the moves are undone. When no more
 * worm can be removed in this way, the remaining ones are
 * unconditionally alive.
 *
 * After this, unconditionally dead opponent worms and unconditional
 * territory are identified. This is almost, but only almost,
 * straightforward. We first present a simple but only almost correct
 * solution, then show how to patch up its deficiencies.
 *
 * - - - - - - -
 *
 * Algorithm 1, simple but slightly incorrect.
 *
 * To find unconditionally dead opponent worms and unconditional
 * territory, we continue from the position obtained at the end of the
 * previous operation (only unconditionally alive strings remain for
 * color) with the following steps:
 *
 * 1. Play opponent stones on all liberties of the unconditionally
 *    alive strings except where illegal. (That the move order may
 *    determine exactly which liberties can be played legally is not
 *    important. Just pick an arbitrary order).
 * 2. Recursively extend opponent strings in atari, except where this
 *    would be suicide.
 * 3. Play an opponent stone anywhere it can get two empty
 *    neighbors. (I.e. split big eyes into small ones).
 * 4. Play an opponent stone anywhere it can get one empty
 *    neighbor. (I.e. reduce two space eyes to one space eyes.)
 *
 * Remaining opponent strings in atari and remaining liberties of the
 * unconditionally alive strings constitute the unconditional
 * territory.
 *
 * Opponent strings from the initial position placed on
 * unconditional territory are unconditionally dead.
 *
 * - - - - - - -
 *
 * The deficiency with this algorithm is that a certain class of sekis
 * are considered as dead, e.g. this position:
 *
 * .OOOOO.
 * OOXXXOO
 * OXX.XXO
 * OX.O.XO
 * OX.O.XO
 * OXX.XXO
 * OOXXXOO
 * .OOOOO.
 *
 * The problem is that while removing the two O stones, X is reduced
 * to a single small eye. Still O cannot capture these stones under
 * alternating play since the eyespace is too big.
 *
 * Before discussing this seki further we make a preliminary
 * modification of the algorithm.
 *
 * - - - - - - -
 *
 * Algorithm 2. More complex but still slightly incorrect algorithm:
 *
 * 1. Run algorithm 1.
 * 2. Return to the original position.
 * 3. Capture all capturable O strings which according to algorithm 1
 *    do not belong to unconditional territory.
 * 4. Play opponent stones on all liberties of the unconditionally
 *    alive strings except where illegal. (That the move order may
 *    determine exactly which liberties can be played legally is not
 *    important. Just pick an arbitrary order).
 * 5. Recursively extend opponent strings in atari, except where this
 *    would be suicide.
 * 6. Capture all remaining capturable O strings.
 * 7. Repeat 4 and 5 once.
 * 8. Play an opponent stone anywhere it can get two empty
 *    neighbors. (I.e. split big eyes into small ones).
 * 9. Play an opponent stone anywhere it can get one empty
 *    neighbor. (I.e. reduce two space eyes to one space eyes.)
 *
 * Remaining opponent strings in atari and remaining liberties of the
 * unconditionally alive strings constitute the unconditional
 * territory.
 *
 * Opponent strings from the initial position placed on
 * unconditional territory are unconditionally dead.
 *
 * - - - - - - -
 *
 * We can observe that, after step 5, an X group with at least two
 * distinct eyespaces would not risk being reduced to a single small
 * eye. Similarly an X group with a capturable O string of size at
 * least three would allow the formation of two distinct small eyes
 * after being captured. Thus it is easy to see that the only X groups
 * which would live in seki but could not be transformed into
 * unconditionally alive groups would have a single eyespace with a
 * capturable O string of size at most 2. Furthermore the eyespace
 * would not be possible to subdivide. Then if the capturable string
 * would be of size 1 it would in all cases form a nakade and we would
 * not have a seki. The plausible seki positions would all be
 * reducable to the following eyeshape:
 *
 * .OOOOO.
 * OOXXXO.
 * OXX.XOO
 * OX.OXXO
 * OXXO.XO
 * OOX.XXO
 * .OXXXOO
 * .OOOOO.
 *
 * The remaining question is what effects cutting points in the X
 * group would have. For example these X groups are dead:
 *
 * .OOOOO.   .OOOOO.   .OOOOO.   .OOOOO.   ..OOOO.   ..OOOO.
 * .OXXXO.   .OXXXO.   .OXXXO.	 .OXXXO.   OOOXXO.   OOOXXO.
 * OOX.XO.   OOX.XOO   OOX.XOO	 OOX.XOO   OXX.XO.   OXX.XOO
 * OX.OXOO   OX.OXXO   OX.OXXO	 OX.OXXO   OX.OXOO   OX.OXXO
 * OXXO.XO   OXXO.XO   OXXO.XO	 OXXO.XO   OXXO.XO   OXXO.XO
 * OOX.XXO   OOX.XOO   OOX.XXO	 OOX.XXO   OOX.XXO   OOX.XXO
 * .OXXXOO   .OXXXO.   .OXXOOO	 .OOXXOO   .OXXXOO   .OXXOOO
 * .OOOOO.   .OOOOO.   .OOOO..	 ..OOOO.   .OOOOO.   .OOOO..
 *
 * while these are alive in seki
 *
 * ..OOOO.   .OOOO..   .OOOO..   ..OOOO.   ..OOOO.
 * OOOXXO.   .OXXOO.   OOXXOO.	 .OOXXO.   OOOXXO.
 * OXX.XOO   OOX.XOO   OXX.XOO	 OOX.XOO   OXX.XOO
 * OX.OXXO   OX.OXXO   OX.OXXO	 OX.OXXO   OX.OXXO
 * OXXO.XO   OXXO.XO   OOXO.XO	 OXXO.XO   OOXO.XO
 * OOX.XXO   OOX.XXO   .OX.XXO	 OOX.XXO   .OX.XXO
 * .OXXXOO   .OXXXOO   .OXXOOO	 .OXXXOO   .OXXXOO
 * .OOOOO.   .OOOOO.   .OOOO..	 ..OOOO.   .OOOOO.
 *
 * The critical distinction between the dead ones and the seki ones is
 * that the stones marked a and b below,
 *
 * .OOOOO.
 * OOXXXO.
 * OXX.XOO
 * OX.ObXO
 * OXaO.XO
 * OOX.XXO
 * .OXXXOO
 * .OOOOO.
 *
 * belong to different strings for the dead groups and to the same
 * string for the seki groups.
 *
 * The trick to avoid misclassifying areas where the opponent can form
 * a seki group but not an invincible group as unconditional territory
 * is thus to detect the formation above and add a third stone to the
 * O group before the capturing in step 6 above.
 *
 * This leads to the final algorithm.
 *
 * - - - - - - -
 *
 * Algorithm 3. Final and correct algorithm:
 *
 * 1. Run algorithm 1.
 * 2. Return to the original position.
 * 3. Capture all capturable O strings which according to algorithm 1
 *    do not belong to unconditional territory.
 * 4. Play opponent stones on all liberties of the unconditionally
 *    alive strings except where illegal. (That the move order may
 *    determine exactly which liberties can be played legally is not
 *    important. Just pick an arbitrary order).
 * 5. Recursively extend opponent strings in atari, except where this
 *    would be suicide.
 * 6. Identify eyespaces of the kind described above and extend any
 *    matching two-stone string with a third stone.
 * 7. Capture all remaining capturable O strings.
 * 8. Repeat 4 and 5 once.
 * 9. Play an opponent stone anywhere it can get two empty
 *    neighbors. (I.e. split big eyes into small ones).
 * 10. Play an opponent stone anywhere it can get one empty
 *    neighbor. (I.e. reduce two space eyes to one space eyes.)
 *
 * Remaining opponent strings in atari and remaining liberties of the
 * unconditionally alive strings constitute the unconditional
 * territory.
 *
 * Opponent strings from the initial position placed on
 * unconditional territory are unconditionally dead.
 *
 * - - - - - - -
 *
 * On return, unconditional_territory[][] is 1 where color has
 * unconditionally alive stones, 2 where it has unconditional
 * territory, and 0 otherwise.
 */

void
unconditional_life(int unconditional_territory[BOARDMAX], int color)
{
  int found_one;
  int other = OTHER_COLOR(color);
  int libs[MAXLIBS];
  int liberties;
  int pos;
  int k, r;
  int moves_played;
  int potential_sekis[BOARDMAX];

  /* Find isolated two-stone strings which might be involved in the
   * kind of seki described in the comments.
   */
  memset(potential_sekis, 0, sizeof(potential_sekis));
  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
    int isolated = 1;
    int stones[2];
    int pos2;
    
    if (board[pos] != color
	|| find_origin(pos) != pos
	|| countstones(pos) != 2)
      continue;
    
    findstones(pos, 2, stones);
    for (k = 0; k < 2 && isolated; k++) {
      for (r = 0; r < 8 && isolated; r++) {
	pos2 = stones[k] + delta[r];
	if (!ON_BOARD(pos2)
	    || (board[pos2] == color
		&& !same_string(pos, pos2)))
	  isolated = 0;
      }
    }

    if (isolated) {
      potential_sekis[stones[0]] = 1;
      potential_sekis[stones[1]] = 1;
    }
  }
  
  moves_played = capture_non_invincible_strings(color, potential_sekis);
  /* The strings still remaining except those marked in
   * potential_sekis[] are uncapturable. Now see which opponent
   * strings can survive.
   *
   * 1. Play opponent stones on all liberties of the unconditionally
   *    alive strings except where illegal.
   */
  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
    if (board[pos] != color || potential_sekis[pos] || find_origin(pos) != pos)
      continue;
      
    /* Play as many liberties as we can. */
    liberties = findlib(pos, MAXLIBS, libs);
    for (k = 0; k < liberties; k++) {
      if (trymove(libs[k], other, "unconditional_life", pos))
	moves_played++;
    }
  }

  /* 2. Recursively extend opponent strings in atari, except where this
   *    would be suicide.
   */
  found_one = 1;
  while (found_one) {
    /* Nothing found so far in this turn of the loop. */
    found_one = 0;

    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
      if (board[pos] != other || countlib(pos) > 1)
	continue;
	
      /* Try to extend the string at (m, n). */
      findlib(pos, 1, libs);
      if (trymove(libs[0], other, "unconditional_life", pos)) {
	moves_played++;
	found_one = 1;
      }
    }
  }

  /* Now see whether there are any significant sekis on the board. */
  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
    if (!potential_sekis[pos]
	|| board[pos] == EMPTY
	|| find_origin(pos) != pos)
      continue;
    for (r = 0; r < 4; r++) {
      int up = delta[r];
      int right = delta[(r + 1) % 4];
      int locally_played_moves = 0;
      if (board[pos + up] != color
	  || board[pos + up + up] != EMPTY
	  || board[pos - up] != EMPTY)
	continue;
      for (k = 0; k < 2; k++) {
	if (k == 1)
	  right = -right;
	if (board[pos + right] != EMPTY || board[pos + up - right] != EMPTY)
	  continue;
	if (board[pos - right] == EMPTY
	    && trymove(pos - right, other, "unconditional_life", pos))
	  locally_played_moves++;
	if (board[pos + up + right] == EMPTY
	    && trymove(pos + up + right, other, "unconditional_life", pos))
	  locally_played_moves++;
	if (board[pos - right] == other && board[pos + up + right] == other
	    && same_string(pos - right, pos + up + right)) {
	  /* This is a critical seki. Extend the string with one stone
           * in an arbitrary direction to break the seki.
	   */
	  while (locally_played_moves > 0) {
	    popgo();
	    locally_played_moves--;
	  }
	  trymove(pos - up, color, "unconditional_life", pos);
	  moves_played++;
	  break;
	}
	else {
	  while (locally_played_moves > 0) {
	    popgo();
	    locally_played_moves--;
	  }
	}
      }
      if (countstones(pos) > 2)
	break;
    }
  }

  /* Capture the strings involved in potential sekis. */
  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
    if (!potential_sekis[pos] || board[pos] == EMPTY)
      continue;
    /* Play as many liberties as we can. */
    liberties = findlib(pos, MAXLIBS, libs);
    for (k = 0; k < liberties; k++) {
      if (trymove(libs[k], other, "unconditional_life", pos))
	moves_played++;
    }
  }
    

  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
    int apos;
    int bpos;
    int aopen, bopen;
    int alib, blib;
    if (board[pos] != other || countlib(pos) != 2)
      continue;
    findlib(pos, 2, libs);
    apos = libs[0];
    bpos = libs[1];
    if (abs(I(apos) - I(bpos)) + abs(J(apos) - J(bpos)) != 1)
      continue;
    
    /* Only two liberties and these are adjacent. Play one. We want
     * to maximize the number of open liberties. In this particular
     * situation we can count this with approxlib for the opposite
     * color. If the number of open liberties is the same, we
     * maximize the total number of obtained liberties.
     * Two relevant positions:
     *
     * |XXX. 
     * |OOXX    |XXXXXXX
     * |O.OX    |OOXOOOX
     * |..OX    |..OO.OX
     * +----    +-------
     */
    aopen = approxlib(apos, color, 4, NULL);
    bopen = approxlib(bpos, color, 4, NULL);
    alib  = approxlib(apos, other, 4, NULL);
    blib  = approxlib(bpos, other, 4, NULL);
    
    if (aopen > bopen || (aopen == bopen && alib >= blib)) {
      trymove(apos, other, "unconditional_life", pos);
      moves_played++;
    }
    else {
      trymove(bpos, other, "unconditional_life", pos);
      moves_played++;
    }
  }
  
  /* Identify unconditionally alive stones and unconditional territory. */
  memset(unconditional_territory, 0, sizeof(int) * BOARDMAX);
  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
    if (board[pos] == color && !potential_sekis[pos]) {
      unconditional_territory[pos] = 1;
      if (find_origin(pos) == pos) {
	liberties = findlib(pos, MAXLIBS, libs);
	for (k = 0; k < liberties; k++)
	  unconditional_territory[libs[k]] = 2;
      }
    }
    else if (board[pos] == other && countlib(pos) == 1) {
      unconditional_territory[pos] = 2;
      findlib(pos, 1, libs);
      unconditional_territory[libs[0]] = 2;
    }
  }
  
  /* Take back all moves. */
  while (moves_played > 0) {
    popgo();
    moves_played--;
  }
}


/* Score the game and determine the winner */

void
who_wins(int color, FILE *outfile)
{
  float result;

  silent_examine_position(EXAMINE_DRAGONS);

#if 0
  float white_score;
  float black_score;
  int winner;
#endif

  if (color != BLACK && color != WHITE)
    color = BLACK;

#if 0
  /* Use the aftermath code to compute the final score. (Slower but
   * more reliable.) 
   */
  result = aftermath_compute_score(color, komi);
  if (result > 0.0)
    winner = WHITE;
  else {
    winner = BLACK;
    result = -result;
  }
#endif

  result = estimate_score(NULL, NULL);
  if (result == 0.0)
    fprintf(outfile, "Result: jigo   ");
  else
    fprintf(outfile, "Result: %c+%.1f   ",
	    (result > 0.0) ? 'W' : 'B', gg_abs(result));
}

/* Find the stones of an extended string, where the extensions are
 * through the following kinds of connections:
 *
 * 1. Solid connections (just like ordinary string).
 *
 *    OO
 *
 * 2. Diagonal connection or one space jump through an intersection
 *    where an opponent move would be suicide or self-atari.
 *
 *    ...
 *    O.O
 *    XOX
 *    X.X
 *
 * 3. Bamboo joint.
 *
 *    OO
 *    ..
 *    OO
 *
 * 4. Diagonal connection where both adjacent intersections are empty.
 *
 *    .O
 *    O.
 *
 * 5. Connection through adjacent or diagonal tactically captured stones.
 *    Connections of this type are omitted when the superstring code is
 *    called from reading.c, but included when the superstring code is
 *    called from owl.c
 */

static void
do_find_superstring(int str, int *num_stones, int *stones,
		    int *num_lib, int *libs, int maxlibs,
		    int *num_adj, int *adjs, int liberty_cap,
		    int proper, int type);

static void
superstring_add_string(int str,
		       int *num_my_stones, int *my_stones,
		       int *num_stones, int *stones,
		       int *num_libs, int *libs, int maxlibs,
		       int *num_adj, int *adjs, int liberty_cap,
		       char mx[BOARDMAX],
		       char ml[BOARDMAX],
		       char ma[BOARDMAX],
		       int do_add);

void
find_superstring(int str, int *num_stones, int *stones)
{
  do_find_superstring(str, num_stones, stones,
		      NULL, NULL, 0,
		      NULL, NULL, 0,
		      0, 1);
}

/* This is the same as find_superstring, except that connections of
 * type 5 are omitted. This is used in semeai analysis.
 */
void
find_superstring_conservative(int str, int *num_stones, int *stones)
{
  do_find_superstring(str, num_stones, stones,
		      NULL, NULL, 0,
		      NULL, NULL, 0,
		      0, 0);
}


/* This function computes the superstring at (str) as described above,
 * but omitting connections of type 5. Then it constructs a list of
 * liberties of the superstring which are not already liberties of
 * (str).
 *
 * If liberty_cap is nonzero, only liberties of substrings of the
 * superstring which have fewer than liberty_cap liberties are
 * generated.
 */

void
find_superstring_liberties(int str,
			   int *num_libs, int *libs, int liberty_cap)
{
  do_find_superstring(str, NULL, NULL,
		      num_libs, libs, MAX_LIBERTIES,
		      NULL, NULL, liberty_cap,
		      0, 0);
}

/* This function is the same as find_superstring_liberties, but it
 * omits those liberties of the string (str), presumably since
 * those have already been treated elsewhere.
 *
 * If liberty_cap is nonzero, only liberties of substrings of the
 * superstring which have at most liberty_cap liberties are
 * generated.
 */

void
find_proper_superstring_liberties(int str, 
				  int *num_libs, int *libs, 
				  int liberty_cap)
{
  do_find_superstring(str, NULL, NULL,
		      num_libs, libs, MAX_LIBERTIES,
		      NULL, NULL, liberty_cap,
		      1, 0);
}

/* This function computes the superstring at (str) as described above,
 * but omitting connections of type 5. Then it constructs a list of
 * liberties of the superstring which are not already liberties of
 * (str).
 *
 * If liberty_cap is nonzero, only liberties of substrings of the
 * superstring which have fewer than liberty_cap liberties are
 * generated.
 */

void
find_superstring_stones_and_liberties(int str,
				      int *num_stones, int *stones,
				      int *num_libs, int *libs,
				      int liberty_cap)
{
  do_find_superstring(str, num_stones, stones,
		      num_libs, libs, MAX_LIBERTIES,
		      NULL, NULL, liberty_cap,
		      0, 0);
}

/* analogous to chainlinks, this function finds boundary chains of the
 * superstring at (str), including those which are boundary chains of
 * (str) itself. If liberty_cap != 0, only those boundary chains with
 * <= liberty_cap liberties are reported.
 */

void
superstring_chainlinks(int str, 
		       int *num_adj, int adjs[MAXCHAIN],
		       int liberty_cap)
{
  do_find_superstring(str, NULL, NULL,
		      NULL, NULL, 0,
		      num_adj, adjs, liberty_cap,
		      0, 2);
}


/* analogous to chainlinks, this function finds boundary chains of the
 * superstring at (str), omitting those which are boundary chains of
 * (str) itself. If liberty_cap != 0, only those boundary chains with
 * <= liberty_cap liberties are reported.
 */

void
proper_superstring_chainlinks(int str,
			      int *num_adj, int adjs[MAXCHAIN],
			      int liberty_cap)
{
  do_find_superstring(str, NULL, NULL,
		      NULL, NULL, 0,
		      num_adj, adjs, liberty_cap,
		      1, 2);
}

/* Do the real work finding the superstring and recording stones,
 * liberties, and/or adjacent strings.
 */
static void
do_find_superstring(int str, int *num_stones, int *stones,
		    int *num_libs, int *libs, int maxlibs,
		    int *num_adj, int *adjs, int liberty_cap,
		    int proper, int type)
{
  int num_my_stones;
  int my_stones[MAX_BOARD * MAX_BOARD];
  
  char mx[BOARDMAX]; /* stones */
  char ml[BOARDMAX]; /* liberties */
  char ma[BOARDMAX]; /* adjacent strings */

  int k, l, r;
  int color = board[str];
  int other = OTHER_COLOR(color);

  memset(mx, 0, sizeof(mx));
  memset(ml, 0, sizeof(ml));
  memset(ma, 0, sizeof(ma));

  if (num_stones)
    *num_stones = 0;
  if (num_libs)
    *num_libs = 0;
  if (num_adj)
    *num_adj = 0;

  /* Include the string itself in the superstring. Only record stones,
   * liberties, and/or adjacent strings if proper==0.
   */
  num_my_stones = 0;
  superstring_add_string(str, &num_my_stones, my_stones,
			 num_stones, stones,
			 num_libs, libs, maxlibs,
			 num_adj, adjs, liberty_cap,
			 mx, ml, ma,
			 !proper);

  /* Loop over all found stones, looking for more strings to include
   * in the superstring. The loop is automatically extended over later
   * found stones as well.
   */
  for (r = 0; r < num_my_stones; r++) {
    int pos = my_stones[r];

    for (k = 0; k < 4; k++) {
      /* List of relative coordinates. (pos) is marked by *.
       *
       *  ef.
       *  gb.
       *  *ac
       *  .d.
       *
       */
      int right = delta[k];
      int up = delta[(k+1)%4];
      
      int apos = pos + right;
      int bpos = pos + right + up;
      int cpos = pos + 2*right;
      int dpos = pos + right - up;
      int epos = pos + 2*up;
      int fpos = pos + right + 2*up;
      int gpos = pos + up;
      int unsafe_move;
      
      if (!ON_BOARD(apos))
	continue;
      
      /* Case 1. Nothing to do since stones are added string by string. */
            
      /* Case 2. */
      if (board[apos] == EMPTY) {
	if (type == 2)
	  unsafe_move = (approxlib(apos, other, 2, NULL) < 2);
	else
	  unsafe_move = is_self_atari(apos, other);
	
	if (unsafe_move && type == 1 && is_ko(apos, other, NULL))
	  unsafe_move = 0;
	
	if (unsafe_move) {
	  if (board[bpos] == color && !mx[bpos])
	    superstring_add_string(bpos, &num_my_stones, my_stones,
				   num_stones, stones,
				   num_libs, libs, maxlibs,
				   num_adj, adjs, liberty_cap,
				   mx, ml, ma, 1);
	  if (board[cpos] == color && !mx[cpos])
	    superstring_add_string(cpos, &num_my_stones, my_stones,
				   num_stones, stones,
				   num_libs, libs, maxlibs,
				   num_adj, adjs, liberty_cap,
				   mx, ml, ma, 1);
	  if (board[dpos] == color && !mx[dpos])
	    superstring_add_string(dpos, &num_my_stones, my_stones,
				   num_stones, stones,
				   num_libs, libs, maxlibs,
				   num_adj, adjs, liberty_cap,
				   mx, ml, ma, 1);
	}
      }
      
      /* Case 3. */
      /* Notice that the order of these tests is significant. We must
       * check bpos before fpos and epos to avoid accessing memory
       * outside the board array. (Notice that fpos is two steps away
       * from pos, which we know is on the board.)
       */
      if (board[apos] == color && board[bpos] == EMPTY
	  && board[fpos] == color && board[epos] == color && !mx[epos]
	  && board[gpos] == EMPTY)
	superstring_add_string(epos, &num_my_stones, my_stones,
			       num_stones, stones,
			       num_libs, libs, maxlibs,
			       num_adj, adjs, liberty_cap,
			       mx, ml, ma, 1);
      /* Don't bother with f, it is part of the string just added. */
      
      /* Case 4. */
      if (board[bpos] == color && !mx[bpos]
	  && board[apos] == EMPTY && board[gpos] == EMPTY)
	superstring_add_string(bpos, &num_my_stones, my_stones,
			       num_stones, stones,
			       num_libs, libs, maxlibs,
			       num_adj, adjs, liberty_cap,
			       mx, ml, ma, 1);
      
      /* Case 5. */
      if (type == 1)
	for (l = 0; l < 2; l++) {
	  int upos;
	  
	  if (l == 0) {
	    /* adjacent lunch */
	    upos = apos;
	  }
	  else {
	    /* diagonal lunch */
	    upos = bpos;
	  }
	  
	  if (board[upos] != other)
	    continue;
	  
	  upos = find_origin(upos);
	  
	  /* Only do the reading once. */
	  if (mx[upos] == 1)
	    continue;
	  
	  mx[upos] = 1;
	  
	  if (attack(upos, NULL)
	      && !find_defense(upos, NULL)) {
	    int lunch_stones[MAX_BOARD*MAX_BOARD];
	    int num_lunch_stones = findstones(upos, MAX_BOARD*MAX_BOARD,
					      lunch_stones);
	    int m, n;
	    for (m = 0; m < num_lunch_stones; m++)
	      for (n = 0; n < 8; n++) {
		int vpos = lunch_stones[m] + delta[n];
		if (board[vpos] == color && !mx[vpos])
		  superstring_add_string(vpos,
					 &num_my_stones, my_stones,
					 num_stones, stones,
					 num_libs, libs, maxlibs,
					 num_adj, adjs, liberty_cap,
					 mx, ml, ma, 1);
	      }
	  }
	}
      if (num_libs && maxlibs > 0 && *num_libs >= maxlibs)
	return;
    }
  }
}

/* Add a new string to a superstring. Record stones, liberties, and
 * adjacent strings as asked for.
 */
static void
superstring_add_string(int str,
		       int *num_my_stones, int *my_stones,
		       int *num_stones, int *stones,
		       int *num_libs, int *libs, int maxlibs,
		       int *num_adj, int *adjs, int liberty_cap,
		       char mx[BOARDMAX],
		       char ml[BOARDMAX],
		       char ma[BOARDMAX],
		       int do_add)
{
  int num_my_libs;
  int my_libs[MAXLIBS];
  int num_my_adj;
  int my_adjs[MAXCHAIN];
  int new_stones;
  int k;
  
  ASSERT1(mx[str] == 0, str);

  /* Pick up the stones of the new string. */
  new_stones = findstones(str, board_size * board_size,
			  &(my_stones[*num_my_stones]));
  
  mark_string(str, mx, 1);
  if (stones) {
    gg_assert(num_stones);
    for (k = 0; k < new_stones; k++) {
      if (do_add) {
	stones[*num_stones] = my_stones[*num_my_stones + k];
	(*num_stones)++;
      }
    }
  }
  (*num_my_stones) += new_stones;

  /* Pick up the liberties of the new string. */
  if (libs) {
    gg_assert(num_libs);
    /* Get the liberties of the string. */
    num_my_libs = findlib(str, MAXLIBS, my_libs);

    /* Remove this string from the superstring if it has too many
     * liberties.
     */
    if (liberty_cap > 0 && num_my_libs > liberty_cap)
      (*num_my_stones) -= new_stones;

    for (k = 0; k < num_my_libs; k++) {
      if (ml[my_libs[k]])
	continue;
      ml[my_libs[k]] = 1;
      if (do_add && (liberty_cap == 0 || num_my_libs <= liberty_cap)) {
	libs[*num_libs] = my_libs[k];
	(*num_libs)++;
	if (*num_libs == maxlibs)
	  break;
      }
    }
  }

  /* Pick up adjacent strings to the new string. */
  if (adjs) {
    gg_assert(num_adj);
    num_my_adj = chainlinks(str, my_adjs);
    for (k = 0; k < num_my_adj; k++) {
      if (liberty_cap > 0 && countlib(my_adjs[k]) > liberty_cap)
	continue;
      if (ma[my_adjs[k]])
	continue;
      ma[my_adjs[k]] = 1;
      if (do_add) {
	adjs[*num_adj] = my_adjs[k];
	(*num_adj)++;
      }
    }
  }
}

/* Internal timers for assessing time spent on various tasks. */
#define NUMBER_OF_TIMERS 4
static double timers[NUMBER_OF_TIMERS];

/* Start a timer. */
void
start_timer(int n)
{
  gg_assert(n >= 0 && n < NUMBER_OF_TIMERS);
  if (!showtime)
    return;

  timers[n] = gg_cputime();
}

/* Report time spent and restart the timer. Make no report if elapsed
 * time is less than mintime.
 */
double
time_report(int n, const char *occupation, int move, double mintime)
{
  double t;
  double dt;
  gg_assert(n >= 0 && n < NUMBER_OF_TIMERS);

  if (!showtime)
    return 0.0;

  t = gg_cputime();
  dt = t - timers[n];
  if (dt > mintime) {
    gprintf("%s", occupation);
    if (move != NO_MOVE)
      gprintf("%1m", move);
    fprintf(stderr, ": %.2f sec\n", dt);
  }
  timers[n] = t;
  return dt;
}

void
clearstats()
{
  stats.nodes                    = 0;
  stats.read_result_entered      = 0;
  stats.read_result_hits         = 0;
  stats.trusted_read_result_hits = 0;
}
  
void
showstats()
{
  gprintf("Nodes:                    %d\n", stats.nodes);
  gprintf("Read results entered:     %d\n", stats.read_result_entered);
  gprintf("Read result hits:         %d\n", stats.read_result_hits);
  gprintf("Trusted read result hits: %d\n", stats.trusted_read_result_hits);
}


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