gnugo-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[gnugo-devel] Time handling in play_gtp.c


From: Gunnar Farneback
Subject: [gnugo-devel] Time handling in play_gtp.c
Date: Mon, 07 Jul 2003 01:23:45 +0200
User-agent: EMH/1.14.1 SEMI/1.14.3 (Ushinoya) FLIM/1.14.2 (Yagi-Nishiguchi) APEL/10.3 Emacs/20.7 (sparc-sun-solaris2.7) (with unibyte mode)

This patch adds time handling under GTP. Previously the commands
time_settings and time_left were recognized but they had no actual
effect on the engine. Now the level is adapted when performing
genmove, with respect to the available time.

We already have similar functionality in clock.c but I just didn't
manage to understand that code, so this is a completely separate
implementation. I've modified the relevant TODO item with a comment
about this.

The algorithm is essentially the same as in gnugoclient. It's kind of
crude but reasonably robust, I believe. Basically it decreases the
level if, at the speed of the previous move, it doesn't have time to
play the number of remaining moves plus three. If the shortage of time
is more severe, the level may be decreased multiple steps at once.
Conversely the level is increased if it has time to play the required
number of moves plus six.

More sophisticated time handling algorithms can certainly be
implemented, preferrably with a solid basis in system identification
theory and/or control theory. This is also commented in the new TODO
entry.

The patch also adds two new options --min-level and --max-level,
determining the range of levels available to the level adjustment
schemes. These are also effective for the --autolevel mechanism in
clock.c, which previously was hardwired to work between level 2 and
level 10.

- TODO revised.
- clock_init_autolevel() retired
- new global variables min_level and max_level
- new options --min-level and --max-level
- time handling implemented in play_gtp.c

In order to test this feature you can use twogtp.pike, which I have
recently added to CVS. It has been written mostly by Paul with a few
modifications by me. It has all the features of the other twogtp
programs, plus time control options.

Btw, don't use --autolevel together with timing information through
GTP. Having two level adjustment schemes active with no cooperation
cannot be expected to give a good result.

/Gunnar

Index: TODO
===================================================================
RCS file: /cvsroot/gnugo/gnugo/TODO,v
retrieving revision 1.12
diff -u -r1.12 TODO
--- TODO        27 May 2003 07:45:54 -0000      1.12
+++ TODO        6 Jul 2003 22:03:39 -0000
@@ -81,11 +81,10 @@
 
  * Support for ko in eyes.db and optics.c.
 
- * Implement handling of timing information through the GTP commands
-   time_settings and time_left for real. Currently the information is
-   received but then ignored. This may involve integration with the
-   current autolevel code in engine/clock.c or writing new level
-   adjustment code.
+ * Integrate the time handling code in play_gtp.c with the autolevel
+   code in clock.c. Alternatively, replace them both with something
+   better. Basing it on some solid system identification theory and/or
+   control theory wouldn't hurt.
 
  * Create a paradigm for handling other types of ko (approach move ko,
    multi-step ko, etc) and then write code that handles them. 
Index: doc/gtp-commands.texi
===================================================================
RCS file: /cvsroot/gnugo/gnugo/doc/gtp-commands.texi,v
retrieving revision 1.12
diff -u -r1.12 gtp-commands.texi
--- doc/gtp-commands.texi       4 Jun 2003 19:16:46 -0000       1.12
+++ doc/gtp-commands.texi       6 Jul 2003 22:03:39 -0000
@@ -900,8 +900,6 @@
 
  Status:    GTP version 2 standard command.
 
- FIXME: This command stores the time settings but no one ever takes notice.
-
 @end example
 
 
@@ -916,8 +914,6 @@
  Returns:   nothing
 
  Status:    GTP version 2 standard command.
-
- FIXME: This command does not take any action.
 
 @end example
 
Index: engine/clock.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/clock.c,v
retrieving revision 1.15
diff -u -r1.15 clock.c
--- engine/clock.c      2 Jan 2003 00:23:28 -0000       1.15
+++ engine/clock.c      6 Jul 2003 22:03:40 -0000
@@ -83,11 +83,9 @@
 
   /* adapative system parameters */
   int    autolevel_on;
-  double min_level;
-  double level;
+  double level;  /* FIXME: Why is this a double and not an int? */
   double levels[CLOCK_MAX_MOVES];
   double expected[CLOCK_MAX_MOVES];
-  double max_level;
   double error; /* time/move estimation error */
 } gnugo_clock;
 
@@ -170,16 +168,6 @@
   clk.clock_on = 1;
 }
 
-/* 
- * set the autolevel parameters.
- */
-void 
-clock_init_autolevel(int min_level, int max_level)
-{
-  clk.min_level = min_level;  
-  clk.max_level = max_level;
-}
-
 /*
  * Activate Autolevel.
  */
@@ -632,10 +620,10 @@
     keep_ahead(color);
 
   /* Update the level. */
-  if (clk.level > clk.max_level)
-    clk.level = clk.max_level;
-  if (clk.level < clk.min_level)
-    clk.level = clk.min_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;
Index: engine/clock.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/clock.h,v
retrieving revision 1.7
diff -u -r1.7 clock.h
--- engine/clock.h      2 Jan 2003 00:23:28 -0000       1.7
+++ engine/clock.h      6 Jul 2003 22:03:40 -0000
@@ -64,7 +64,6 @@
 void clock_init(int time, int byo_time, int byo_stones);
 void clock_enable(void);
  
-void clock_init_autolevel(int min_level, int max_level);
 void clock_enable_autolevel(void);
 
 /* main access */
Index: engine/globals.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/globals.c,v
retrieving revision 1.52
diff -u -r1.52 globals.c
--- engine/globals.c    19 Jun 2003 18:57:45 -0000      1.52
+++ engine/globals.c    6 Jul 2003 22:03:40 -0000
@@ -123,6 +123,8 @@
 float lower_bound     = 0.0;
 float upper_bound     = 0.0;
 int level             = DEFAULT_LEVEL; /* strength; up to 10 supported */
+int min_level         = 0;
+int max_level         = gg_max(DEFAULT_LEVEL, 10);
 int debug             = 0;  /* controls debug output */
 int verbose           = 0;  /* trace level */
 char outfilename[128] = ""; /* output file (-o option) */
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.184
diff -u -r1.184 liberty.h
--- engine/liberty.h    26 Jun 2003 20:24:03 -0000      1.184
+++ engine/liberty.h    6 Jul 2003 22:03:41 -0000
@@ -818,6 +818,8 @@
 extern int breakin_depth;
 extern int breakin_node_limit;
 extern int level;               /* controls the strength of play */
+extern int min_level;           /* minimum level for adjustment schemes */
+extern int max_level;           /* minimum level for adjustment schemes */
 extern int semeai_variations;   /* max variations considered reading semeai */
 extern float best_move_values[10];
 extern int best_moves[10];
Index: interface/main.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/main.c,v
retrieving revision 1.74
diff -u -r1.74 main.c
--- interface/main.c    19 Jun 2003 18:57:45 -0000      1.74
+++ interface/main.c    6 Jul 2003 22:03:42 -0000
@@ -115,6 +115,8 @@
       OPT_NOFUSEKI,
       OPT_NOJOSEKIDB,
       OPT_LEVEL,
+      OPT_MIN_LEVEL,
+      OPT_MAX_LEVEL,
       OPT_LIMIT_SEARCH,
       OPT_SHOWTIME,
       OPT_SHOWSCORE,
@@ -214,6 +216,8 @@
   {"owl-reading",    required_argument, 0, OPT_OWL_READING},
   {"owl-node-limit", required_argument, 0, OPT_OWL_NODE_LIMIT},
   {"level",          required_argument, 0, OPT_LEVEL},
+  {"min-level",      required_argument, 0, OPT_MIN_LEVEL},
+  {"max-level",      required_argument, 0, OPT_MAX_LEVEL},
   {"limit-search",   required_argument, 0, OPT_LIMIT_SEARCH},
   {"clock",          required_argument, 0, OPT_CLOCK_TIME},
   {"byo-time",       required_argument, 0, OPT_CLOCK_BYO_TIME},
@@ -316,7 +320,9 @@
   komi = 0.0;
   
   level = DEFAULT_LEVEL;
-
+  min_level = 0;
+  max_level = 10;
+  
   mandated_depth               = -1;
   mandated_backfill_depth      = -1;
   mandated_backfill2_depth     = -1;
@@ -355,7 +361,6 @@
 
   /* Default parameters for clock and auto level systems. */
   clock_init(3600, 0, 0);      /* One hour sudden death. */
-  clock_init_autolevel(2, 10); /* 2 < level < 10 */
 
   sgftree_clear(&sgftree);
   gameinfo_clear(&gameinfo, board_size, komi);
@@ -766,6 +771,14 @@
        level = atoi(gg_optarg);
        break;
 
+      case OPT_MIN_LEVEL:
+       min_level = atoi(gg_optarg);
+       break;
+
+      case OPT_MAX_LEVEL:
+       max_level = atoi(gg_optarg);
+       break;
+
       case OPT_LIMIT_SEARCH:
        {
          int m, n;
@@ -1366,6 +1379,8 @@
    --owl-reading <depth>        owl reading depth (default %d)\n\
    --owl-node-limit <limit>     max nodes for owl reading (default %d)\n\
    --level <amount>             strength (default %d, up to 10 supported)\n\
+   --min-level <amount>         minimum level for adjustment schemes\n\
+   --max-level <amount>         maximum level for adjustment schemes\n\
    --autolevel                  adapt gnugo level during game to respect\n\
                                 the time specified by --clock <sec>.\n\
 "
Index: interface/play_gtp.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_gtp.c,v
retrieving revision 1.121
diff -u -r1.121 play_gtp.c
--- interface/play_gtp.c        9 Jun 2003 16:19:17 -0000       1.121
+++ interface/play_gtp.c        6 Jul 2003 22:03:43 -0000
@@ -35,12 +35,27 @@
 /* Internal state that's not part of the engine. */
 static int handicap = 0;
 static int main_time = 0;
-static int byo_yomi_time = 0;
+static int byo_yomi_time = 1;
 static int byo_yomi_stones = 0;
 
 static int report_uncertainty = 0;
 static int gtp_orientation = 0;
 
+/* Time handling. Index 0 is the most recent report, index 1 the
+ * second most recent report.
+ */
+static int black_time_left[2];
+static int black_stones_left[2];
+static int white_time_left[2];
+static int white_stones_left[2];
+static int level_offset;
+
+
+static void gtp_init_time_handling(void);
+static void analyze_time_data(int time_left_data[2], int stones_left_data[2],
+                             int *time_for_last_move,
+                             int *time_left, int *stones_left);
+static void adjust_level_offset(int color);
 static void print_influence(float white_influence[BOARDMAX],
                            float black_influence[BOARDMAX],
                            int influence_regions[BOARDMAX]);
@@ -313,6 +328,9 @@
   gtp_internal_set_boardsize(board_size);
   gtp_orientation = gtp_initial_orientation;
   gtp_set_vertex_transform_hooks(rotate_on_input, rotate_on_output);
+
+  /* Initialize time handling. */
+  gtp_init_time_handling();
   
   /* Prepare pattern matcher and reading code. */
   reset_engine();
@@ -466,6 +484,8 @@
     update_random_seed();
 
   clear_board();
+  gtp_init_time_handling();
+  
   return gtp_success("");
 }
 
@@ -819,6 +839,7 @@
   handicap = gameinfo.handicap;
   gtp_internal_set_boardsize(board_size);
   reset_engine();
+  gtp_init_time_handling();
 
   sgfFreeNode(sgftree.root);
 
@@ -2282,7 +2303,10 @@
   if (stackp > 0)
     return gtp_failure("genmove cannot be called when stackp > 0");
 
+  adjust_level_offset(color);
+  level += level_offset;
   val = genmove(&i, &j, color);
+  level -= level_offset;
 
   if (resign_allowed && val < 0.0 && ON_BOARD(POS(i, j))) {
     return gtp_success("resign");
@@ -2512,6 +2536,7 @@
     return gtp_failure("level not an integer");
   
   level = new_level;
+  level_offset = 0;
   return gtp_success("");
 }
 
@@ -2566,14 +2591,134 @@
  * time handling *
  *****************/
 
+/* Initialize time data variables and set the level offset to 0. */
+static void
+gtp_init_time_handling(void)
+{
+  int k;
+  for (k = 0; k < 1; k++) {
+    black_time_left[k] = -1;
+    black_stones_left[k] = -1;
+    white_time_left[k] = -1;
+    white_stones_left[k] = -1;
+  }
+  level_offset = 0;
+}
+
+/* Analyze the two most recent time reports and determine the time
+ * spent on the last moves, the (effective) number of stones left and
+ * the (effective) remaining time.
+ */
+static void
+analyze_time_data(int time_left_data[2], int stones_left_data[2],
+                 int *time_for_last_move, int *time_left, int *stones_left)
+{
+  *time_for_last_move = -1;
+  *time_left = -1;
+  *stones_left = -1;
+
+  /* Do we have any time limits. */
+  if (byo_yomi_stones == 0 && byo_yomi_time > 0)
+    return;
+  
+  /* If we don't have time information for the two last moves, just return. */
+  if (time_left_data[1] < 0)
+    return;
+
+  if (stones_left_data[0] == 0) {
+    /* Main time running. */
+    *time_for_last_move = time_left_data[1] - time_left_data[0];
+    *time_left = time_left_data[0] + byo_yomi_time;
+    if (byo_yomi_time > 0)
+      *stones_left = byo_yomi_stones;
+    else {
+      /* Absolute time. Here we aim to be able to play at least X more
+       * moves or a total of Y moves. We choose Y as a third of the
+       * number of vertices and X as 40% of Y. For 19x19 this means
+       * that we aim to play at least a total of 120 moves
+       * (corresponding to a 240 move game) or another 24 moves.
+       */
+      int nominal_moves = board_size * board_size / 3;
+      *stones_left = gg_max(nominal_moves - movenum / 2,
+                           2 * nominal_moves / 5);
+    }
+  }
+  else {
+    if (stones_left_data[1] == 0)
+      *time_for_last_move = time_left_data[1] + (byo_yomi_time
+                                                - time_left_data[0]);
+    else if (stones_left_data[1] == stones_left_data[0] + 1)
+      *time_for_last_move = time_left_data[1] - time_left_data[0];
+    else
+      return;
+
+    *time_left = time_left_data[0];
+    *stones_left = stones_left_data[0];
+  }
+}
+
+/* Adjust the level offset given information of current playing speed
+ * and remaining time and stones.
+ *
+ * FIXME: Integrate this code with the one in clock.c. Or maybe rather
+ *        replace them both with something better.
+ */
+static void
+adjust_level_offset(int color)
+{
+  int time_for_last_move;
+  int time_left;
+  int stones_left;
+
+  if (color == BLACK)
+    analyze_time_data(black_time_left, black_stones_left, &time_for_last_move,
+                     &time_left, &stones_left);
+  else
+    analyze_time_data(white_time_left, white_stones_left, &time_for_last_move,
+                     &time_left, &stones_left);
+
+  if (time_for_last_move < 0)
+    return;
+
+  /* These rules are both crude and ad hoc.
+   *
+   * FIXME: Use rules with at least some theoretical basis.
+   */
+  if (time_left < time_for_last_move * (stones_left + 3))
+    level_offset--;
+  if (time_left < time_for_last_move * stones_left)
+    level_offset--;
+  if (3 * time_left < 2 * time_for_last_move * stones_left)
+    level_offset--;
+  if (2 * time_left < time_for_last_move * stones_left)
+    level_offset--;
+  if (3 * time_left < time_for_last_move * stones_left)
+    level_offset--;
+
+  if (time_for_last_move == 0)
+    time_for_last_move = 1;
+  if (time_left > time_for_last_move * (stones_left + 6))
+    level_offset++;
+  if (time_left > 2 * time_for_last_move * (stones_left + 6))
+    level_offset++;
+
+  if (level + level_offset < min_level)
+    level_offset = min_level - level;
+
+  if (level + level_offset > max_level)
+    level_offset = max_level - level;
+
+  if (0)
+    gprintf("New level %d (%d %C %d %d %d)\n", level + level_offset,
+           movenum / 2, color, time_for_last_move, time_left, stones_left);
+}
+
 /* Function:  Set time allowance
  * Arguments: int main_time, int byo_yomi_time, int byo_yomi_stones
  * Fails:     syntax error
  * Returns:   nothing
  *
  * Status:    GTP version 2 standard command.
- *
- * FIXME: This command stores the time settings but no one ever takes notice.
  */
 
 static int
@@ -2598,8 +2743,6 @@
  * Returns:   nothing
  *
  * Status:    GTP version 2 standard command.
- *
- * FIXME: This command does not take any action.
  */
 
 static int
@@ -2617,6 +2760,19 @@
   if (sscanf(s+n, "%d %d", &time, &stones) < 2)
     return gtp_failure("time and stones not two integers");
 
+  if (color == BLACK) {
+    black_time_left[1] = black_time_left[0];
+    black_stones_left[1] = black_stones_left[0];
+    black_time_left[0] = time;
+    black_stones_left[0] = stones;
+  }
+  else {
+    white_time_left[1] = white_time_left[0];
+    white_stones_left[1] = white_stones_left[0];
+    white_time_left[0] = time;
+    white_stones_left[0] = stones;
+  }
+  
   return gtp_success("");
 }
 




reply via email to

[Prev in Thread] Current Thread [Next in Thread]