Subversion Repositories Games.Chess Giants

#include <math.h>

#include "chess.h"

#include "data.h"

/* last modified 02/23/14 */

/*

 *******************************************************************************

 *                                                                             *

 *   TimeAdjust() is called to adjust timing variables after each program move *

 *   is made.  It simply increments the number of moves made, decrements the   *

 *   amount of time used, and then makes any necessary adjustments based on    *

 *   the time controls.                                                        *

 *                                                                             *

 *******************************************************************************

 */

void TimeAdjust(int time_used, int side) {

/*

 ************************************************************

 *                                                          *

 *  Decrement the number of moves remaining to the next     *

 *  time control.  Then subtract the time the program took  *

 *  to choose its move from the time remaining.             *

 *                                                          *

 ************************************************************

 */

  tc_moves_remaining[side]--;

  tc_time_remaining[side] -=

      (tc_time_remaining[side] >

      time_used) ? time_used : tc_time_remaining[side];

  if (!tc_moves_remaining[side]) {

    if (tc_sudden_death == 2)

      tc_sudden_death = 1;

    tc_moves_remaining[side] += tc_secondary_moves;

    tc_time_remaining[side] += tc_secondary_time;

    Print(4095, "time control reached (%s)\n", (side) ? "white" : "black");

  }

  if (tc_increment)

    tc_time_remaining[side] += tc_increment;

}

/* last modified 02/23/14 */

/*

 *******************************************************************************

 *                                                                             *

 *   TimeCheck() is used to determine when the search should stop.  It uses    *

 *   several conditions to make this determination:  (1) The search time has   *

 *   exceeded the time per move limit;  (2) The value at the root of the tree  *

 *   has not dropped too low.                                                  *

 *                                                                             *

 *   We use one additional trick here to avoid stopping the search just before *

 *   we change to a better move.  We simply do our best to complete the        *

 *   iteration which means we have searched every move to this same depth.     *

 *                                                                             *

 *   This is implemented by having Search() call TimeCheck() passing it a      *

 *   value of one (1) for the parameter busy.  TimeCheck() will only end the   *

 *   search if we have exceeded the max time limit.  Otherwise, we continue.   *

 *   Iterate() calls TimeCheck() passing it a value of "0" for busy, which     *

 *   simply says "now, if we have used the target time limit (which can be     *

 *   modified by the "difficulty value), we will stop and not try another      *

 *   iteration."                                                               *

 *                                                                             *

 *   The "difficulty" value is used to implement the concept of an "easy move" *

 *   or a "hard move".  With an easy move, we want to spend less time since    *

 *   the easy move is obvious.  The opposite idea is a hard move, where we     *

 *   actually want to spend more time to be sure we don't make a mistake by`   *

 *   moving too quickly.                                                       *

 *                                                                             *

 *   The basic methodology revolves around how many times we change our mind   *

 *   on the best move at the root of the tree.                                 *

 *                                                                             *

 *   The "difficulty" variable is initially set to 100, which represents a     *

 *   percentage of the actual target time we should spend on this move.  If    *

 *   we end an iteration without having changed our mind at all, difficulty    *

 *   is reduced by multiplying by .9, with a lower bound of 60%.               *

 *                                                                             *

 *   If we change our mind during an iteration, there are two cases.  (1) If   *

 *   difficulty is < 100%, we set it back to 100% +20% for each time we        *

 *   changed the best move.  (2) if difficulty is already at 100% or higher,   *

 *   we multiply difficulty by .80, then add 20% for each root move change.    *

 *   For example, suppose we are at difficulty=60%, and we suddenly change our *

 *   mind twice this iteration (3 different best moves).                       *

 *                                                                             *

 *   difficulty = 100 + 3*20 = 160% of the actual target time will be used.    *

 *                                                                             *

 *   Suppose we change back and forth between two best moves multiple times,   *

 *   with difficulty currently at 100%.  The first time:                       *

 *                                                                             *

 *   difficulty = .80 * 100 + 2*20 = 120%                                      *

 *                                                                             *

 *   The next iteration:                                                       *

 *                                                                             *

 *   difficulty = .80 * 120 + 2 * 20 = 96% _ 40% = 136%                        *

 *                                                                             *

 *   The next iteration:                                                       *

 *                                                                             *

 *   difficulty = .80 * 136% + 40% = 149%                                      *

 *                                                                             *

 *   If we stop changing our mind, then difficulty starts on a downward trend. *

 *   The basic idea is that if we are locked in on a move, we can make it a    *

 *   bit quicker, but if we are changing back and forth, we are going to spend *

 *   more time to try to choose the best move.                                 *

 *                                                                             *

 *******************************************************************************

 */

int TimeCheck(TREE * RESTRICT tree, int busy) {

  int time_used;

  int i, ndone;

/*

 ************************************************************

 *                                                          *

 *  Check to see if we need to "burp" the time to let the   *

 *  operator know the search is progressing and how much    *

 *  time has been used so far.                              *

 *                                                          *

 ************************************************************

 */

  time_used = (ReadClock() - start_time);

  if (tree->nodes_searched > noise_level && display_options & 32 &&

      time_used > burp) {

    Lock(lock_io);

    if (pondering)

      printf("         %2i   %s%7s?  ", iteration_depth,

          Display2Times(time_used), tree->remaining_moves_text);

    else

      printf("         %2i   %s%7s*  ", iteration_depth,

          Display2Times(time_used), tree->remaining_moves_text);

    if (display_options & 32 && display_options & 64)

      printf("%d. ", move_number);

    if ((display_options & 32) && (display_options & 64) && Flip(root_wtm))

      printf("... ");

    printf("%s(%snps)             \r", tree->root_move_text,

        DisplayKMB(nodes_per_second));

    burp = (time_used / 1500) * 1500 + 1500;

    fflush(stdout);

    Unlock(lock_io);

  }

/*

 ************************************************************

 *                                                          *

 *  First, check to see if there is only one root move.  If *

 *  so, and we are not pondering, searching a book move or  *

 *  or annotating a game, we can return and make this move  *

 *  instantly.  We do need to finish iteration 1 so that we *

 *  actually back up a move to play.                        *

 *                                                          *

 ************************************************************

 */

  if (n_root_moves == 1 && !booking && !annotate_mode && !pondering &&

      iteration_depth > 1)

    return 1;

  if (iteration_depth <= 2)

    return 0;

/*

 ************************************************************

 *                                                          *

 *  If we are pondering or in analyze mode, we do not       *

 *  terminate on time since there is no time limit placed   *

 *  on these searches.  If we have reached the absolute     *

 *  time limit, we stop the search instantly.               *

 *                                                          *

 ************************************************************

 */

  if (pondering || analyze_mode)

    return 0;

  if (time_used > absolute_time_limit)

    return 1;

/*

 ************************************************************

 *                                                          *

 *  If the operator has specified a specific time limit, we *

 *  stop when we hit that regardless of any other tests     *

 *  used during normal timeing.                             *

 *                                                          *

 ************************************************************

 */

  if (search_time_limit) {

    if (time_used < time_limit)

      return 0;

    else

      return 1;

  }

/*

 ************************************************************

 *                                                          *

 *  If we are under the time limit already set, we do not   *

 *  terminate the search.  Once we reach that limit, we     *

 *  abort the search if we are fixing to start another      *

 *  iteration, otherwise we keep searching to try to        *

 *  complete the current iteration.                         *

 *                                                          *

 ************************************************************

 */

  if (time_used < (difficulty * time_limit) / 100)

    return 0;

  if (!busy)

    return 1;

/*

 ************************************************************

 *                                                          *

 *  We have reached the target time limit.  If we are in    *

 *  the middle of an iteration, we keep going unless we are *

 *  stuck on the first move, where there is no benefit to   *

 *  continuing and this will just burn clock time away.     *

 *                                                          *

 *  This is a bit tricky, because if we are on the first    *

 *  move AND we have failed low, we want to continue the    *

 *  search to find something better, if we have not failed  *

 *  low, we will abort the search in the test that follows  *

 *  this one.                                               *

 *                                                          *

 ************************************************************

 */

  ndone = 0;

  for (i = 0; i < n_root_moves; i++)

    if (root_moves[i].status & 8)

      ndone++;

  if (ndone == 1 && !(root_moves[0].status & 1))

    return 1;

/*

 ************************************************************

 *                                                          *

 *  We are in the middle of an iteration, we have used the  *

 *  allocated time limit, but we have more moves left to    *

 *  search.  We forge on until we complete the iteration    *

 *  which will terminate the search, or until we reach the  *

 *  "absolute_time_limit" where we terminate the search no  *

 *  matter what is going on.                                *

 *                                                          *

 ************************************************************

 */

  if (time_used + 300 > tc_time_remaining[root_wtm])

    return 1;

  return 0;

}

/* last modified 02/23/14 */

/*

 *******************************************************************************

 *                                                                             *

 *   TimeSet() is called to set the two variables "time_limit" and             *

 *   "absolute_time_limit" which controls the amount of time taken by the      *

 *   iterated search.  It simply takes the timing controls as set by the user  *

 *   and uses these values to calculate how much time should be spent on the   *

 *   next search.                                                              *

 *                                                                             *

 *******************************************************************************

 */

void TimeSet(int search_type) {

  int mult = 0, extra = 0;

  int surplus, average;

  int simple_average;

  surplus = 0;

  average = 0;

/*

 ************************************************************

 *                                                          *

 *  Check to see if we are in a sudden-death type of time   *

 *  control.  If so, we have a fixed amount of time         *

 *  remaining.  Set the search time accordingly and exit.   *

 *                                                          *

 *  If we have less than 5 seconds on the clock prior to    *

 *  the increment, then limit our search to the increment.  *

 *                                                          *

 *  If we have less than 2.5 seconds on the clock prior to  *

 *  the increment, then limit our search to half the        *

 *  increment in an attempt to add some time to our buffer. *

 *                                                          *

 *  Set our MAX search time to half the remaining time.     *

 *                                                          *

 *  If our search time will drop the clock below 1 second,  *

 *  then limit our MAX search time to the normal search     *

 *  time.  This is done to stop any extensions from         *

 *  dropping us too low.                                    *

 *                                                          *

 ************************************************************

 */

  if (tc_sudden_death == 1) {

    if (tc_increment) {

      time_limit =

          (tc_time_remaining[root_wtm] -

          tc_operator_time * tc_moves_remaining[root_wtm]) /

          (ponder ? 20 : 26) + tc_increment;

      if (tc_time_remaining[root_wtm] < 500 + tc_increment) {

        time_limit = tc_increment;

        if (tc_time_remaining[root_wtm] < 250 + tc_increment)

          time_limit /= 2;

      }

      absolute_time_limit = tc_time_remaining[root_wtm] / 2 + tc_increment;

      if (absolute_time_limit < time_limit ||

          tc_time_remaining[root_wtm] - time_limit < 100)

        absolute_time_limit = time_limit;

      if (tc_time_remaining[root_wtm] - time_limit < 50) {

        time_limit = tc_time_remaining[root_wtm] - 50;

        if (time_limit < 5)

          time_limit = 5;

      }

      if (tc_time_remaining[root_wtm] - absolute_time_limit < 25) {

        absolute_time_limit = tc_time_remaining[root_wtm] - 25;

        if (absolute_time_limit < 5)

          absolute_time_limit = 5;

      }

    } else {

      time_limit = tc_time_remaining[root_wtm] / (ponder ? 20 : 26);

      absolute_time_limit =

          Min(time_limit * 5, tc_time_remaining[root_wtm] / 2);

    }

  }

/*

 ************************************************************

 *                                                          *

 *  We are not in a sudden_death situation.  We now have    *

 *  two choices:  If the program has saved enough time to   *

 *  meet the surplus requirement, then we simply divide     *

 *  the time left evenly among the moves left.  If we       *

 *  haven't yet saved up a cushion so that "fail-lows"      *

 *  have extra time to find a solution, we simply take the  *

 *  number of moves divided into the total time less the    *

 *  necessary operator time as the target.                  *

 *                                                          *

 ************************************************************

 */

  else {

    if (move_number <= tc_moves)

      simple_average =

          (tc_time -

          (tc_operator_time * tc_moves_remaining[root_wtm])) / tc_moves;

    else

      simple_average =

          (tc_secondary_time -

          (tc_operator_time * tc_moves_remaining[root_wtm])) /

          tc_secondary_moves;

    surplus =

        Max(tc_time_remaining[root_wtm] -

        (tc_operator_time * tc_moves_remaining[root_wtm]) -

        simple_average * tc_moves_remaining[root_wtm], 0);

    average =

        (tc_time_remaining[root_wtm] -

        (tc_operator_time * tc_moves_remaining[root_wtm]) +

        tc_moves_remaining[root_wtm] * tc_increment)

        / tc_moves_remaining[root_wtm];

    if (surplus < tc_safety_margin)

      time_limit = (average < simple_average) ? average : simple_average;

    else

      time_limit =

          (average < 2/*.0*/ * simple_average) ? average : 2/*.0*/ * simple_average; // Pierre-Marie Baty -- this is integer math

  }

  if (surplus < 0)

    surplus = 0;

  if (tc_increment > 200 && moves_out_of_book < 2)

    /*time_limit *= 1.2;*/ time_limit = (time_limit * 12) / 10; // Pierre-Marie Baty -- this is integer math

  if (time_limit <= 0)

    time_limit = 5;

  absolute_time_limit =

      time_limit + surplus / 2 + ((tc_time_remaining[root_wtm] -

          tc_operator_time * tc_moves_remaining[root_wtm]) / 4);

  if (absolute_time_limit > 6 * time_limit)

    absolute_time_limit = 6 * time_limit;

  if (absolute_time_limit > tc_time_remaining[root_wtm] / 2)

    absolute_time_limit = tc_time_remaining[root_wtm] / 2;

/*

 ************************************************************

 *                                                          *

 *  The "usage" option can be used to force the time limit  *

 *  higher or lower than normal.  The new "timebook"        *

 *  command can also modify the target time making the      *

 *  program use more time early in the game as it exits the *

 *  book, knowing it will save time later on by ponder hits *

 *  and instant moves.                                      *

 *                                                          *

 ************************************************************

 */

  if (usage_level)

    /*time_limit *= 1.0 + usage_level / 100.0;*/ time_limit += time_limit * usage_level / 100; // Pierre-Marie Baty -- this is integer math

  if (first_nonbook_factor && moves_out_of_book < first_nonbook_span) {

    mult =

        (first_nonbook_span - moves_out_of_book + 1) * first_nonbook_factor;

    extra = time_limit * mult / first_nonbook_span / 100;

    time_limit += extra;

  }

/*

 ************************************************************

 *                                                          *

 *  If the operator has set an absolute search time limit   *

 *  already, then we simply copy this value and return.     *

 *                                                          *

 ************************************************************

 */

  if (search_time_limit) {

    time_limit = search_time_limit;

    absolute_time_limit = time_limit;

  }

  if (search_type == puzzle || search_type == booking) {

    time_limit /= 10;

    absolute_time_limit = time_limit * 3;

  }

  if (!tc_sudden_death && !search_time_limit &&

      time_limit > 3 * tc_time / tc_moves)

    time_limit = 3 * tc_time / tc_moves;

  time_limit = Min(time_limit, absolute_time_limit);

  if (search_type != puzzle) {

    if (!tc_sudden_death)

      Print(128, "        time surplus %s  ", DisplayTime(surplus));

    else

      Print(128, "         ");

    Print(128, "time limit %s", DisplayTimeKibitz(time_limit));

    Print(128, " (+%s)", DisplayTimeKibitz(extra));

    Print(128, " (%s)", DisplayTimeKibitz(absolute_time_limit));

    if (fabs(usage_level) > 0.0001) {

      Print(128, "/");

      Print(128, "(%d)", usage_level);

    }

    Print(128, "\n");

  }

  if (time_limit <= 1) {

    time_limit = 1;

    usage_level = 0;

  }

}