[gnugo-devel] restricted_genmove

[Gunnar Farneback]

Consider the test case gunnar:2. The point of the test is that the
played move at D19 is horrible and that both E18 and E17 are clearly
locally better. It's far from clear, however, that either of the
latter moves would be the globally best one. Therefore the test is
written in the negative !D19 form.

As we all are well aware of by now, negative tests have some
problems. Currently gunnar:2 passes because E7 is valued to 13
points. This is of course ridiculous and is caused by a strange
non-amalgamation of C8/D7/C6. Moreover the D19 mistake is not at all
solved, it's still valued higher than E18 and E17, coming in at second
place. To conclude, this means that:

1. The patch causing E7 to be overvalued was awarded a PASS for this
   test case.
2. A patch solving the real problem with D19 will currently go unnoticed.
3. A patch solving the E7 problem will currently get a FAIL.

This is of course unacceptable and needs solving. One possibility is
to change the test into a positive one but that would have a couple of
drawbacks:

1. It's necessary to identify the globally best move or at least all
   reasonably good moves. This both requires much work and can only be
   reliably done by the strongest players.
2. It still doesn't address the real problem. We want E18 and E17 to
   be preferred over D19 regardless of the size of moves on the rest
   of the board.

A better solution would be to reconstruct the problem into one where
there are no moves on the board bigger than E18 and E17. This is, in
fact, a very good solution except for the fact that it requires a
substantial amount of work.

A third alternative, which is the one I'm going to propose, is to
introduce a new GTP command restricted_genmove. Then the test would be
written

# D19 is locally worse than both E17 and E18.
loadsgf games/nngs/gnugo-3.3.10-rcde05-200210280427.sgf 83
2 restricted_genmove white D19 E18 E17
#? [E17|E18]

This allows us to concentrate on the problem the test case was
intended for without any extra work in the construction of the test
case.

Not all negative tests are appropriate to convert into restricted
tests, but many are and doing this should significantly reduce the
problem we are seeing with accidental failures and passes.

The patch below implements the restricted_genmove command.

- new GTP command restricted_genmove
- new function genmove_restricted() in genmove.c
- new parameter allowed_moves[] to do_genmove(), review_move_reasons(),
  and find_best_move()

/Gunnar

Index: doc/gtp-commands.texi
===================================================================
RCS file: /cvsroot/gnugo/gnugo/doc/gtp-commands.texi,v
retrieving revision 1.6
diff -u -r1.6 gtp-commands.texi
--- doc/gtp-commands.texi       16 Nov 2002 00:50:05 -0000      1.6
+++ doc/gtp-commands.texi       29 Nov 2002 12:07:05 -0000
@@ -785,6 +785,19 @@
 
 @end example
 
address@hidden restricted_genmove
address@hidden restricted_genmove
+
address@hidden
+
+ Function:  Generate the supposedly best move for either color from a
+            choice of allowed vertices.
+ Arguments: color to move, allowed vertices
+ Fails:     invalid color, invalid vertex, no vertex listed
+ Returns:   a move coordinate (or "PASS")
+
address@hidden example
+
 @cindex level
 @item level
 
Index: engine/aftermath.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/aftermath.c,v
retrieving revision 1.36
diff -u -r1.36 aftermath.c
--- engine/aftermath.c  9 Oct 2002 18:36:23 -0000       1.36
+++ engine/aftermath.c  29 Nov 2002 12:07:08 -0000
@@ -849,7 +849,7 @@
   gg_assert(stackp == 0);
 
   /* Review the move reasons and estimate move values. */
-  if (review_move_reasons(move, &val, color, 0.0, lower_bound))
+  if (review_move_reasons(move, &val, color, 0.0, lower_bound, NULL))
     TRACE("Move generation likes %1m with value %f\n", *move, val);
   gg_assert(stackp == 0);
 
Index: engine/genmove.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/genmove.c,v
retrieving revision 1.56
diff -u -r1.56 genmove.c
--- engine/genmove.c    16 Nov 2002 00:30:25 -0000      1.56
+++ engine/genmove.c    29 Nov 2002 12:07:08 -0000
@@ -36,7 +36,8 @@
 #define NEEDS_UPDATE(x) (x != position_number ? (x = position_number, 1) : 0)
 
 static int get_level(int *level);
-static int do_genmove(int *move, int color, float pure_threat_value);
+static int do_genmove(int *move, int color, float pure_threat_value,
+                     int allowed_moves[BOARDMAX]);
 
 static double slowest_time = 0.0;
 static int    slowest_move = NO_MOVE;
@@ -292,7 +293,7 @@
   }
 #endif
 
-  retval = do_genmove(&move, color, 0.4);
+  retval = do_genmove(&move, color, 0.4, NULL);
   gg_assert(retval < 0 || ON_BOARD1(move));
 
   if (i) *i = I(move);
@@ -313,7 +314,22 @@
   int move;
   int retval;
 
-  retval = do_genmove(&move, color, 0.0);
+  retval = do_genmove(&move, color, 0.0, NULL);
+
+  if (i) *i = I(move);
+  if (j) *j = J(move);
+
+  return retval;
+}
+
+
+int
+genmove_restricted(int *i, int *j, int color, int allowed_moves[BOARDMAX])
+{
+  int move;
+  int retval;
+
+  retval = do_genmove(&move, color, 0.0, allowed_moves);
 
   if (i) *i = I(move);
   if (j) *j = J(move);
@@ -323,11 +339,17 @@
 
 
 /* 
- * Perform the actual move generation. 
+ * Perform the actual move generation.
+ *
+ * The array allowed_moves restricts which moves may be considered. If
+ * NULL any move is allowed. Pass is always allowed and will be chosen
+ * if the move generation doesn't like any of the allowed moves (or
+ * overlooks them).
  */
   
 static int
-do_genmove(int *move, int color, float pure_threat_value)
+do_genmove(int *move, int color, float pure_threat_value,
+          int allowed_moves[BOARDMAX])
 {
   float val;
   int save_verbose;
@@ -460,7 +482,7 @@
 
   /* Review the move reasons and estimate move values. */
   if (review_move_reasons(move, &val, color, 
-                         pure_threat_value, lower_bound))
+                         pure_threat_value, lower_bound, allowed_moves))
     TRACE("Move generation likes %1m with value %f\n", *move, val);
   gg_assert(stackp == 0);
   time_report(1, "review move reasons", NO_MOVE, 1.0);
@@ -474,7 +496,8 @@
       shapes(color);
       if (!disable_endgame_patterns)
        endgame_shapes(color);
-      if (review_move_reasons(move, &val, color, pure_threat_value, score)) {
+      if (review_move_reasons(move, &val, color, pure_threat_value, score,
+                             allowed_moves)) {
        TRACE("Upon reconsideration move generation likes %1m with value %f\n",
              *move, val); 
       }
@@ -486,7 +509,8 @@
   if (val <= 6.0 && !disable_endgame_patterns && !limit_search) {
     endgame_shapes(color);
     gg_assert(stackp == 0);
-    if (review_move_reasons(move, &val, color, pure_threat_value, score))
+    if (review_move_reasons(move, &val, color, pure_threat_value, score,
+                           allowed_moves))
       TRACE("Move generation likes %1m with value %f\n", *move, val);
     gg_assert(stackp == 0);
     time_report(1, "endgame", NO_MOVE, 1.0);
@@ -501,7 +525,8 @@
        || revise_semeai(color)) {
       shapes(color);
       endgame_shapes(color);
-      if (review_move_reasons(move, &val, color, pure_threat_value, score)) {
+      if (review_move_reasons(move, &val, color, pure_threat_value, score,
+                             allowed_moves)) {
        TRACE("Upon reconsideration move generation likes %1m with value %f\n",
              *move, val); 
       }
@@ -513,7 +538,8 @@
    * all missing dame points.
    */
   if (val < 0.0 
-      && fill_liberty(move, color)) {
+      && fill_liberty(move, color)
+      && (!allowed_moves || allowed_moves[*move])) {
     val = 1.0;
     TRACE("Filling a liberty at %1m\n", *move);
     record_top_move(*move, val);
@@ -533,7 +559,8 @@
          || (thrashing_dragon
              && ((color == BLACK && score < -15.0)
                  || (color == WHITE && score > 15.0))))
-      && aftermath_genmove(move, color, NULL, 0) > 0) {
+      && aftermath_genmove(move, color, NULL, 0) > 0
+      && (!allowed_moves || allowed_moves[*move])) {
     ASSERT1(is_legal(*move, color), *move);
     val = 1.0;
     TRACE("Aftermath move at %1m\n", *move);
@@ -548,7 +575,8 @@
   if (val < 0.0
       && !doing_scoring
       && capture_all_dead 
-      && aftermath_genmove(move, color, NULL, 1) > 0) {
+      && aftermath_genmove(move, color, NULL, 1) > 0
+      && (!allowed_moves || allowed_moves[*move])) {
     ASSERT1(is_legal(*move, color), *move);
     val = 1.0;
     TRACE("Aftermath move at %1m\n", *move);
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.136
diff -u -r1.136 liberty.h
--- engine/liberty.h    21 Nov 2002 00:25:10 -0000      1.136
+++ engine/liberty.h    29 Nov 2002 12:07:09 -0000
@@ -497,7 +497,8 @@
                             const char safe_stones[BOARDMAX]);
 
 int review_move_reasons(int *move, float *val, int color,
-                       float pure_threat_value, float lower_bound);
+                       float pure_threat_value, float lower_bound,
+                       int allowed_moves[BOARDMAX]);
 int fill_liberty(int *move, int color);
 int aftermath_genmove(int *aftermath_move, int color,
                      int under_control[BOARDMAX],
@@ -527,6 +528,8 @@
 int within_search_area(int pos);
 int metamachine_genmove(int *i, int *j, int color);
 void draw_search_area(void);
+
+int genmove_restricted(int *i, int *j, int color, int allowed_moves[BOARDMAX]);
 
 void change_attack(int str, int move, int acode);
 void change_defense(int str, int move, int dcode);
Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.67
diff -u -r1.67 value_moves.c
--- engine/value_moves.c        19 Nov 2002 16:32:35 -0000      1.67
+++ engine/value_moves.c        29 Nov 2002 12:07:13 -0000
@@ -2878,7 +2878,8 @@
  * for the best move.
  */
 static int
-find_best_move(int *the_move, float *val, int color)
+find_best_move(int *the_move, float *val, int color,
+              int allowed_moves[BOARDMAX])
 {
   int good_move_found = 0;
   int ko_values_have_been_added = 0;
@@ -2896,8 +2897,10 @@
     /* Search through all board positions for the highest valued move. */
     for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
       float tval = move[pos].final_value;
+      if (allowed_moves && !allowed_moves[pos])
+       continue;
       if (!ON_BOARD(pos) || move[pos].final_value == 0.0)
-         continue;
+       continue;
        
       if (tval > bestval) {
        if (is_legal(pos, color) || is_illegal_ko_capture(pos, color)) {
@@ -2975,10 +2978,14 @@
  * which only threatens to capture or kill something. The reason for
  * playing these is that the move may be effective because we have
  * misevaluated the dangers or because the opponent misplays.
+ *
+ * The array allowed_moves restricts which moves may be considered. If
+ * NULL any move is allowed.
  */
 int
 review_move_reasons(int *the_move, float *val, int color,
-                   float pure_threat_value, float score)
+                   float pure_threat_value, float score,
+                   int allowed_moves[BOARDMAX])
 {
   int save_verbose;
   
@@ -3023,7 +3030,7 @@
   print_top_moves();
 
   /* Select the highest valued move and return it. */
-  return find_best_move(the_move, val, color);
+  return find_best_move(the_move, val, color, allowed_moves);
 }
 
 
Index: interface/play_gtp.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_gtp.c,v
retrieving revision 1.103
diff -u -r1.103 play_gtp.c
--- interface/play_gtp.c        16 Nov 2002 00:30:25 -0000      1.103
+++ interface/play_gtp.c        29 Nov 2002 12:07:16 -0000
@@ -130,6 +130,7 @@
 DECLARE(gtp_query_boardsize);
 DECLARE(gtp_query_orientation);
 DECLARE(gtp_quit);
+DECLARE(gtp_restricted_genmove);
 DECLARE(gtp_reg_genmove);
 DECLARE(gtp_report_uncertainty);
 DECLARE(gtp_reset_connection_node_counter);
@@ -252,6 +253,7 @@
   {"query_boardsize",         gtp_query_boardsize},
   {"query_orientation",       gtp_query_orientation},
   {"quit",                           gtp_quit},
+  {"restricted_genmove",      gtp_restricted_genmove},
   {"reg_genmove",             gtp_reg_genmove},
   {"report_uncertainty",      gtp_report_uncertainty},
   {"reset_connection_node_counter", gtp_reset_connection_node_counter},
@@ -2161,6 +2163,61 @@
   gtp_print_vertex(i, j);
   return gtp_finish_response();
 }
+
+
+/* Function:  Generate the supposedly best move for either color from a
+ *            choice of allowed vertices.
+ * Arguments: color to move, allowed vertices
+ * Fails:     invalid color, invalid vertex, no vertex listed
+ * Returns:   a move coordinate (or "PASS")
+ */
+static int
+gtp_restricted_genmove(char *s)
+{
+  int i, j;
+  int color;
+  int n;
+  int allowed_moves[BOARDMAX];
+  int number_allowed_moves = 0;
+  memset(allowed_moves, 0, sizeof(allowed_moves));
+
+  n = gtp_decode_color(s, &color);
+  if (!n)
+    return gtp_failure("invalid color");
+
+  s += n;
+  while (1) {
+    n = gtp_decode_coord(s, &i, &j);
+    if (n > 0) {
+      allowed_moves[POS(i, j)] = 1;
+      number_allowed_moves++;
+      s += n;
+    }
+    else if (sscanf(s, "%*s") != EOF)
+      return gtp_failure("invalid coordinate");
+    else
+      break;
+  }
+
+  if (number_allowed_moves == 0)
+    return gtp_failure("no allowed vertex");
+
+  if (stackp > 0)
+    return gtp_failure("genmove cannot be called when stackp > 0");
+
+  /* This is intended for regression purposes and should therefore be
+   * deterministic. The best way to ensure this is to reset the random
+   * number generator before calling genmove(). It is always seeded by
+   * 0.
+   */
+  random_seed = 0;
+  
+  genmove_restricted(&i, &j, color, allowed_moves);
+  gtp_start_response(GTP_SUCCESS);
+  gtp_print_vertex(i, j);
+  return gtp_finish_response();
+}
+
 
 /* Function : Generate a list of the best moves in the previous genmove
  *            command (either of genmove_black, genmove_white, gg_genmove).