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

/* ============================================================= *\
 *                        Time handling                          *
 *                          for GNU Go                           *
 *                         __       __                           *
 *                        <  >     <  >                          *
 *                      +--++-------++--+                        *
 *                      |  .'11 12 1'.  |                        *
 *                      |  :10 \    2:  |                        *
 *                      |  :9   @-> 3:  |                        *
 *                      |  :8       4;  |                        *
 *                      |  '..7 6 5..'  |                        *
 *                      |_______________|                        *
 *                                                               *
\* ============================================================= */

#include "gnugo.h"

#include "liberty.h"
#include "gg_utils.h"
#include "clock.h"

/* parameters */
#define CLOCK_MAX_MOVES           500   /* max number of moves for a game */
#define CLOCK_STEP                0.4   /* modification step for level */
#define CLOCK_HURRY               10    /* Last chance limit: */
#define CLOCK_HURRYR              0.02  /* (10 sec or or 2% of main_time) */
#define CLOCK_HURRY_LEVEL         1     /* Last chance level: */
#define CLOCK_SAFE                300   /* Keep Ahead limit: */
#define CLOCK_SAFER               0.20  /* (5min or 20% of time) */
#define CLOCK_DELTA               10    /* Maximal time difference: */
#define CLOCK_DELTAR              0.10  /* 10sec or 10% of left time */
#define CLOCK_TIME_CONTRACT       0.75  /* 75% of time to play */
#define CLOCK_MOVE_CONTRACT(b)    (((b)*(b))/2)
#define CLOCK_CONTRACT_MIN_LEVEL  5


/*************************/
/* Datas and other stuff */
/*************************/

extern int board_size;

typedef struct {

  /* clock parameters */
  int    clock_on;
  int    ready;
  double main_time;
  double byoyomi_time; /* zero if no byo-yomi */
  int    byoyomi_stones;

  /* clock status */
  double timer[3];
  double btimer[3];
  int    byoyomi[3];
  int    dead[3];

  /* dates of each move */
  int    moveno; /* invariant: COLOR(clk.moveno) = color of last move */
  double date[CLOCK_MAX_MOVES];

  /* adapative system parameters */
  int    autolevel_on;
  double level;  /* FIXME: Why is this a double and not an int? */
  double levels[CLOCK_MAX_MOVES];
  double expected[CLOCK_MAX_MOVES];
  double error; /* time/move estimation error */
} gnugo_clock;

static gnugo_clock clk;

/* Color macro:
 *   WHITE : odd moves
 *   BLACK : even moves. 
 */
#define COLOR(m)  ((m) % 2 ? WHITE : BLACK)


static const char *pname[3] = {"     ", "White", "Black"};


/* forward declarations */

static double estimate_time_by_move(int color, int move);




/* Echo a time value in STANDARD format */

static void
timeval_print(FILE *outfile, double tv)
{
  int min;
  double sec;

  min = (int) tv / 60;
  sec = tv - min*60;

  fprintf(outfile, "%3dmin %.2fsec ", min, sec);
}

/******************************/
/*  Initialization functions  */
/******************************/


/*
 * Initialize the structure.
 * -1 means "do not modify this value".
 * clock_init(-1, -1, -1) only resets the clock.
 */
void
clock_init(int time, int byo_time, int byo_stones)
{
  int color;

  if (time > 0) {
    clk.main_time = time;
    clk.ready = 1;
  }

  if (byo_time >= 0)
    clk.byoyomi_time = byo_time;

  if (byo_stones >= 0)
    clk.byoyomi_stones = byo_stones;

  clk.moveno = -1;
  for (color = WHITE; color <= BLACK; color++) {
    clk.timer[color] = 0;
    clk.btimer[color] = 0;
    clk.byoyomi[color] = 0;
    clk.dead[color] = 0;
  }
}


/*
 * Activate the clock.
 */
void 
clock_enable(void)
{
  gg_assert(clk.ready);
  clk.clock_on = 1;
}

/*
 * Activate Autolevel.
 */
void 
clock_enable_autolevel(void)
{
  gg_assert(clk.clock_on);
  clk.autolevel_on = 1;
}


/***********************/
/*  Access functions.  */
/***********************/


/* 
 * Maintain timers and all stuff up to date
 * (used by push_button).
 */
static void
clock_byoyomi_update(int color, double dt)
{
  gg_assert(clk.moveno > 0);

  /* update byoyomi timer */
  if (clk.byoyomi[color])
    clk.btimer[color] = clk.btimer[color] + dt;
 
  /* Check if player is just begining byoyomi. */
  if (clk.timer[color] < clk.main_time && !clk.byoyomi[color]) {
    clk.byoyomi[color] = clk.moveno;
    clk.btimer[color] = dt;
  }
  
  /* Check if player is time-out. */
  clk.dead[color] |= (clock_is_byoyomi(color)
		      && clk.byoyomi_time < clk.btimer[color]);

  /* Check byoyomi period reset. */
  if (clk.byoyomi[color]
      && clk.moveno - clk.byoyomi[color] == 2 * clk.byoyomi_stones - 1) {
    clk.byoyomi[color] = clk.moveno;
    clk.btimer[color] = 0;
  }
}


/*
 * Update the clock.
 */
void
clock_push_button(int color)
{
  double now, dt, tme;

  if (!clk.clock_on)
    return;

  now = gg_gettimeofday();
  gg_assert(clk.ready);

  /* time/move estimation */
  tme = estimate_time_by_move(color, clk.moveno);

  /* first move */
  if (clk.moveno == -1) {
    /* fprintf(stderr, "clock: first move by %s.\n", pname[color]); */
    clk.moveno++;
    clk.date[0] = now;

    if (color != BLACK) { /* do an empty move for BLACK */
      clk.date[1] = now;
      clk.moveno++;
    }
    return;
  }

  /* fprintf(stderr, "clock: %s push the button.\n", pname[color]);*/
  /* fprintf(stderr, "clock: %s's turn.\n", pname[COLOR(clk.moveno+1)]);*/

  /* Pushing twice on the button does nothing. */
  if (color != COLOR(clk.moveno+1)) {
    fprintf(stderr, "clock: double push.\n");
    return;
  }

  /* Other moves (clk. moveno > -1) */
  clk.moveno++;
  gg_assert(clk.moveno < CLOCK_MAX_MOVES);
  clk.date[clk.moveno] = now;

  /* Update main timer. */
  dt = clk.date[clk.moveno] - clk.date[clk.moveno - 1];
  clk.timer[color] += dt;

  /* Estimate prediction error for next move. */
  if (clk.moveno > 11)
    clk.error = (clk.error + 2 * gg_abs(dt-tme))/3;
  else
    clk.error = 3.0;

  clock_byoyomi_update(color, dt);
  clock_print(color);
}


/*
 * Unplay a move.
 */
void 
clock_unpush_button(int color)
{
  double dt;

  if (!clk.clock_on)
    return;
     
  gg_assert(clk.ready);
  gg_assert(color == COLOR(clk.moveno));

  if (clk.moveno < 1) {
    clock_init(-1, -1, -1);
    return;
  }

  /* Update main timer. */
  dt = clk.date[clk.moveno] - clk.date[clk.moveno - 1];
  clk.timer[color] -= dt;
  clk.moveno--;

  /* Check if back from byoyomi. */
  if (clk.timer[color] < clk.main_time) {
    clk.byoyomi[color] = 0;
    clk.btimer[color] = 0;
  }
     
  /* Update byoyomi timer. */
  if (clk.byoyomi[color])
    clk.btimer[color] -= dt;

  clock_print(color);
}


/*
 * return the (exact) main timer value.
 */
double
clock_get_timer(int color)
{
  double dt;

  gg_assert(clk.clock_on && clk.ready);

  dt = gg_gettimeofday() - clk.date[clk.moveno];

  if (COLOR(clk.moveno) != color)
    return clk.timer[color] + dt;
  else 
    return clk.timer[color];
}


/*
 * Give the time left or negative if in byoyomi.
 */
double  
clock_get_time_left(int color)
{
  return clk.main_time - clock_get_timer(color);
}


/*
 * Check if color is (officially) in byoyomi.
 */
int
clock_is_byoyomi(int color)
{
  return clock_get_time_left(color) < 0;
}


/*
 * Return the (exact) main timer value.
 */
double
clock_get_btimer(int color)
{
  double dt;
  
  /* sanity check */
  gg_assert(clk.clock_on && clk.ready);
  dt = gg_gettimeofday() - clk.date[clk.moveno];

  if (COLOR(clk.moveno) != color)
    return clk.btimer[color] + dt;
  else 
    return clk.btimer[color];
}


/*
 * Get The Byoyomi time left and the number of stones to play.
 */
double
clock_get_btime_left(int color, int *stones)
{
  if (stones != NULL)
    *stones = clk.byoyomi_stones - (clk.moveno - clk.byoyomi[color]) / 2;

  return clk.byoyomi_time - clock_get_btimer(color);
}


/*
 * Check if a player is time over.
 */
int
clock_is_time_over(int color)
{
  return clock_is_byoyomi(color) && clock_get_btime_left(color, NULL) <= 0;
}


void
clock_print(int color)
{
  double tleft;
  int stones;

  if (!clk.clock_on)
    return;

  gg_assert(clk.ready);

  fprintf(stderr, "clock: "); 
  fprintf(stderr, "%s ", pname[color]);

  if (clock_is_time_over(color))
    fprintf(stderr, "TIME OUT! ");
  else {
    if (clock_is_byoyomi(color))
      tleft = clock_get_btime_left(color, &stones);
    else
      tleft = clock_get_time_left(color);
      
    if (clock_is_byoyomi(color)) {
      fprintf(stderr, "byoyomi");
      timeval_print(stderr, tleft);
      fprintf(stderr, "for %d stones.\n", stones);
    }
    else
      timeval_print(stderr, tleft);

  }
  fprintf(stderr, "\n");
}



/**********************/
/*  Autolevel system  */
/**********************/



/* Write the time/move to outfile */
void 
clock_report_autolevel(FILE *outfile, int color)
{
  int i, first;
  double dt, est, exp;

  if (!clk.autolevel_on)
    return;

  if (outfile == NULL)
    outfile = fopen("autolevel.dat", "w");
  if (outfile == NULL)
    return;

  fprintf(outfile, "#\n#  level  prediction   expected  time/move\n");  
  fprintf(outfile, "#-----------------------------------------\n"); 

  if (color == WHITE)
    first = 8;
  else
    first = 9;

  for (i = first; i < clk.moveno; i += 2) {
    dt = clk.date[i+1] - clk.date[i];
    est = estimate_time_by_move(color, i);
    exp = clk.expected[i + 1];
    fprintf(outfile, "%5.2f  %5.2f  %5.2f  %5.2f\n",
	    clk.levels[i + 1], est, exp, dt);
  }
}


/* 
 * Give an estimation of the time/move 
 * based on the last played move.
 */

/* coeficients to estimate time/move */
static const double 
coef[5] = {
  1.0/15.0, 2.0/15.0, 3.0/15.0, 4.0/15.0, 5.0/15.0 
};

static double
estimate_time_by_move(int color, int move)
{
  double res;
  int i;

  if (move <= 10)
    return 0;

  gg_assert(COLOR(move) == OTHER_COLOR(color));

  res = 0;
  for (i = 0; i < 5; i++)
    res += coef[i] * (clk.date[move-9+i*2] - clk.date[move-10+i*2]);
  
  return res;
}


/* 
 * Try to respect a "time contract". 
 */
static void 
respect_time_contract(int color)
{
  double time_left, expected_tm, predicted_tm;
  double moves_left;

  fprintf(stderr, "\n*** time contract:\n");

  predicted_tm = estimate_time_by_move(color, clk.moveno);

  /* Compute the expected mean time/move 
   * to respect the contract.
   */
  moves_left = (CLOCK_MOVE_CONTRACT(board_size) - clk.moveno) / 2.0;
  time_left = (clock_get_time_left(color)
	       - (1.0 - CLOCK_TIME_CONTRACT) * clk.main_time);
  expected_tm = time_left / moves_left;

  clk.expected[clk.moveno + 1] = expected_tm;

  fprintf(stderr, "%4.0f moves ", moves_left);
  fprintf(stderr, "must be played in %.2fsec\n", time_left);
  fprintf(stderr, "time/move: prediction=%.2f", predicted_tm);
  fprintf(stderr, "+/-%.2fsec --> ", clk.error);
  fprintf(stderr, "expected=%.2f\n", expected_tm);

  /* Compare this result with the prediction
   * (up to prediction error estimation)
   * and update the level.
   */ 
  if (clk.level > CLOCK_CONTRACT_MIN_LEVEL)
    if ((predicted_tm - clk.error) > expected_tm)
      clk.level -= CLOCK_STEP;
  if ((predicted_tm + clk.error) < expected_tm)
    clk.level += CLOCK_STEP;
}


/* 
 * Try to keep gnugo ahead on the clock. 
 */
static void
keep_ahead(int color)
{
  double dt, st, delta_max;

  fprintf(stderr, "*** safe limit reached: trying to keep ahead\n");

  dt = clock_get_time_left(color) - clock_get_time_left(OTHER_COLOR(color));
  st = clock_get_time_left(color) + clock_get_time_left(OTHER_COLOR(color));
  delta_max = gg_max(CLOCK_DELTA, CLOCK_DELTAR * st);

  fprintf(stderr, "deltamax: %gsec, delta=%gsec => ", delta_max, dt);
      
  if (dt < -delta_max) {
    fprintf(stderr, "behind\n");
    clk.level -= CLOCK_STEP;
  }
  else {
    if (dt > delta_max) {
      fprintf(stderr, "ahead\n");
      clk.level += CLOCK_STEP;
    }
    else
      fprintf(stderr, "equal\n");
  }
}


/* 
 * Modify the level during a game to avoid losing by time.
 */
void
clock_adapt_level(int *p_level, int color)
{
  int old_level;
  double hurry_limit, safe_limit;

  /* 
   * Do not touch the level during the first 10 moves
   * to estimate time/move on a reasonable sample.
   */
  if (clk.moveno < 10 || !clk.autolevel_on) {
    clk.level = *p_level;
    clk.levels[clk.moveno + 1] = clk.level;
    return;
  }

  old_level = *p_level;
  
  /* 
   * Hurry strategy:
   * Behind this limit the only priority is finish at all costs.
   */
  hurry_limit = gg_max(CLOCK_HURRY, CLOCK_HURRYR * clk.main_time);
  if (clock_get_time_left(color) < hurry_limit) {
    fprintf(stderr, "*** hurry limit reached:\n");
    clk.level = CLOCK_HURRY_LEVEL;
    *p_level = clk.level;
    return;
  }

  /* 
   * Time contract strategy:
   * try to respect the time of a standard game. 
   */
  if (clk.moveno < CLOCK_MOVE_CONTRACT(board_size))
    respect_time_contract(color);

  /* 
   * Keep ahead strategy:
   * When the safe_limit is reached gnugo tries to keep ahead in time.
   */
  safe_limit = gg_max(CLOCK_SAFE, CLOCK_SAFER * clk.main_time);
  if (clock_get_time_left(color) < safe_limit) 
    keep_ahead(color);

  /* Update the level. */
  if (clk.level > (double) max_level)
    clk.level = (double) max_level;
  if (clk.level < (double) min_level)
    clk.level = (double) min_level;

  clk.levels[clk.moveno + 1] = clk.level;
  *p_level = clk.level;
  
  fprintf(stderr, "level %4.1f at move %d\n", clk.level, movenum);
}



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