[gnugo-devel] readconnect/breakin patch

[Arend Bayer]

- fix "no moves found" logic in various readconnect.c functions
- new debug flag DEBUG_BREAKIN
- "smaller goal" in breakin.c revised
- be more careful when erasing territory after successful break-in
- break-in move generation bug fix

The break-in code did overuse DEBUG_TERRITORY, which made this pretty
unusable. Now only the "Erasing territory at..."-messages are printed by
DEBUG_TERRITORY, which one probably wants to know in this case.

This includes the patch I had sent earlier fixing the problems Gunnar had
reported. The move generation bug fix addresses the position Evan had
sent (nngs4:630). Now the move at B6 does get recognized as break-in, but
only gets valued to 5 points -- which might even be correct.

Arend

trevora:150     PASS F6 [F6]
trevora:370     PASS F6 [F6]
nicklas5:1212   PASS dead [dead]
nngs:1280       PASS D13 [D13]
strategy3:120   PASS C7 [C7]
global:1        PASS B3 [B3]
century2002:240 FAIL C7 [F18]           Accidental
ninestones:240  PASS K1 [!M19]
ninestones:540  FAIL L19 [B15]          Bad, but extremely tricky
        Problem is computation of connection distances does not know
        about komaster state (when using ladder_capturable etc.)
gunnar:36       PASS B18 [B18]
arend2:70       FAIL N16 [N7|O9]        Mostly accidental

Index: engine/breakin.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/breakin.c,v
retrieving revision 1.4
diff -u -p -r1.4 breakin.c
--- engine/breakin.c    9 Jun 2003 16:19:16 -0000       1.4
+++ engine/breakin.c    18 Jun 2003 10:57:55 -0000
@@ -126,15 +126,21 @@ compute_smaller_goal(int owner, int colo
     /* We don't want vertices that are at the border of the territory, and
      * from which a break-in is unlikely; these often lead to false
      * positives.
-     * So we throw out every vertex that has only one neighbor in the goal.
+     * So we throw out every vertex that has only one neighbor in the goal,
+     * or that is on an edge and has only two goal neighbors.
      */
     for (j = 0; j < 4; j++)
       if (ON_BOARD(pos + delta[j])
          && goal[pos + delta[j]]
          && (board[pos] == EMPTY || goal[pos] == OTHER_COLOR(owner)))
        goal_neighbors++;
-    if (goal_neighbors > 1)
+#if 0
+    if (goal_neighbors > 2
+       || goal_neighbors == 2 && !is_edge_vertex(pos))
+#else
+    if (goal_neighbors >= 2)
       smaller_goal[pos] = 1;
+#endif
   }

   /* Finally, in the case of blocking off, we only want one connected
@@ -202,14 +208,21 @@ break_in_goal_from_str(int str, char goa
                      int color_to_move)
 {
   int move = NO_MOVE;
+  int saved_move = NO_MOVE;
   char smaller_goal[BOARDMAX];
   struct connection_data conn;

-  compute_connection_distances(str, NO_MOVE, 3.01, &conn);
+  /* When blocking off, we use a somewhat smaller goal area. */
+  if (color_to_move == board[str])
+    compute_connection_distances(str, NO_MOVE, 3.01, &conn);
+  else
+    compute_connection_distances(str, NO_MOVE, 2.81, &conn);
   compute_smaller_goal(OTHER_COLOR(board[str]), color_to_move,
                       &conn, goal, smaller_goal);
-  DEBUG(DEBUG_TERRITORY, "Trying to break in from %1m to:\n", str);
-  if (debug & DEBUG_TERRITORY)
+  if (0 && (debug & DEBUG_BREAKIN))
+    print_connection_distances(&conn);
+  DEBUG(DEBUG_BREAKIN, "Trying to break in from %1m to:\n", str);
+  if (debug & DEBUG_BREAKIN)
     goaldump(smaller_goal);
   while ((color_to_move == board[str]
           && break_in(str, smaller_goal, &move))
@@ -223,6 +236,7 @@ break_in_goal_from_str(int str, char goa
      */
     int k;
     int save_num = *num_non_territory;
+    int affected_size = 0;
     float cut_off_distance = 3.5;
     if (ON_BOARD(move) && goal[move]) {
       non_territory[(*num_non_territory)++] = move;
@@ -249,13 +263,33 @@ break_in_goal_from_str(int str, char goa
     if (*num_non_territory == save_num)
       break;

-    for (k = save_num; k < *num_non_territory; k++)
-      goal[non_territory[k]] = 0;
+    for (k = save_num; k < *num_non_territory; k++) {
+      int j;
+      int pos =  non_territory[k];
+      if (goal[pos]) {
+       affected_size++;
+       goal[pos] = 0;
+      }
+      for (j = 0; j < 4; j++)
+       if (goal[pos + delta[j]])
+         affected_size++;
+      /* Don't kill too much territory at a time. */
+      if (affected_size >= 5) {
+       *num_non_territory = k;
+       break;
+      }
+    }

     compute_smaller_goal(OTHER_COLOR(board[str]), color_to_move,
                         &conn, goal, smaller_goal);
+    DEBUG(DEBUG_BREAKIN, "Now trying to break to smaller goal:\n", str);
+    if (debug & DEBUG_BREAKIN)
+      goaldump(smaller_goal);
+
+    if (saved_move == NO_MOVE)
+      saved_move = move;
   }
-  return move;
+  return saved_move;
 }

 #define MAX_TRIES 10
@@ -274,15 +308,15 @@ break_in_goal(int color_to_move, int own
   int candidates = 0;
   float min_distance = 5.0;

-  DEBUG(DEBUG_TERRITORY,
+  DEBUG(DEBUG_BREAKIN,
         "Trying to break (%C to move) %C's territory ", color_to_move, owner);
-  if (debug & DEBUG_TERRITORY)
+  if (debug & DEBUG_BREAKIN)
     goaldump(goal);
   /* Compute nearby fields of goal. */
   init_connection_data(intruder, goal, &conn);
   k = conn.queue_end;
   spread_connection_distances(intruder, NO_MOVE, &conn, 3.01, 1);
-  if (0 && (debug & DEBUG_TERRITORY))
+  if (0 && (debug & DEBUG_BREAKIN))
     print_connection_distances(&conn);

   /* Look for nearby stones. */
@@ -330,7 +364,7 @@ break_in_goal(int color_to_move, int own

   for (k = 0; k < num_non_territory; k++)
     influence_erase_territory(q, non_territory[k], owner);
-  if (0 && num_non_territory > 0 && (debug & DEBUG_TERRITORY))
+  if (0 && num_non_territory > 0 && (debug & DEBUG_BREAKIN))
     showboard(0);
 }

Index: engine/genmove.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/genmove.c,v
retrieving revision 1.75
diff -u -p -r1.75 genmove.c
--- engine/genmove.c    9 Jun 2003 16:19:16 -0000       1.75
+++ engine/genmove.c    18 Jun 2003 10:57:55 -0000
@@ -579,6 +579,8 @@ do_genmove(int *move, int color, float p
       slowest_movenum = movenum + 1;
     }
   }
+  if (0 && (debug & DEBUG_BREAKIN))
+    print_persistent_breakin_cache();

   /* Some consistency checks to verify that things are properly
    * restored and/or have not been corrupted.
Index: engine/gnugo.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/gnugo.h,v
retrieving revision 1.96
diff -u -p -r1.96 gnugo.h
--- engine/gnugo.h      4 Jun 2003 12:48:50 -0000       1.96
+++ engine/gnugo.h      18 Jun 2003 10:57:56 -0000
@@ -228,7 +228,7 @@ extern int output_flags;       /* amount
 #define DEBUG_WORMS                 0x0400
 #define DEBUG_MOVE_REASONS          0x0800
 #define DEBUG_OWL_PERFORMANCE       0x1000
-#define DEBUG_LIFE                  0x2000
+#define DEBUG_BREAKIN              0x2000
 #define DEBUG_FILLLIB               0x4000
 #define DEBUG_READING_PERFORMANCE   0x8000
 #define DEBUG_SCORING               0x010000
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.180
diff -u -p -r1.180 liberty.h
--- engine/liberty.h    9 Jun 2003 16:19:16 -0000       1.180
+++ engine/liberty.h    18 Jun 2003 10:57:57 -0000
@@ -347,6 +347,7 @@ void store_persistent_breakin_cache(int
                                    char breakin_shadow[BOARDMAX]);
 void purge_persistent_breakin_cache(void);
 void clear_persistent_breakin_cache(void);
+void print_persistent_breakin_cache(void);
 void purge_persistent_owl_cache(void);
 void clear_persistent_owl_cache(void);
 int search_persistent_owl_cache(int routine, int apos, int bpos, int cpos,
Index: engine/persistent.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/persistent.c,v
retrieving revision 1.12
diff -u -p -r1.12 persistent.c
--- engine/persistent.c 9 Jun 2003 16:19:16 -0000       1.12
+++ engine/persistent.c 18 Jun 2003 10:57:58 -0000
@@ -1330,6 +1330,14 @@ store_persistent_breakin_cache(int routi
   persistent_breakin_cache_size++;
 }

+void
+print_persistent_breakin_cache()
+{
+  int k;
+  for (k = 0; k < persistent_breakin_cache_size; k++)
+    print_persistent_breakin_cache_entry(k);
+}
+

 /* For debugging purposes. */
 static void
Index: engine/readconnect.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/readconnect.c,v
retrieving revision 1.53
diff -u -p -r1.53 readconnect.c
--- engine/readconnect.c        9 Jun 2003 16:19:16 -0000       1.53
+++ engine/readconnect.c        18 Jun 2003 10:58:01 -0000
@@ -1922,6 +1922,7 @@ recursive_connect2(int str1, int str2, i
   int savemove = NO_MOVE;
   int savecode = 0;
   int found_read_result;
+  int tried_moves = 0;
   Read_result *read_result = NULL;

   SETUP_TRACE_INFO2("recursive_connect2", str1, str2);
@@ -1987,6 +1988,7 @@ recursive_connect2(int str1, int str2, i
     if (komaster_trymove(xpos, color, "recursive_connect2", str1,
                         komaster, kom_pos, &new_komaster, &new_kom_pos,
                         &ko_move, stackp <= ko_depth && savecode == 0)) {
+      tried_moves++;
       if (!ko_move) {
        int acode = recursive_disconnect2(str1, str2, NULL,
                                          new_komaster, new_kom_pos,
@@ -2013,7 +2015,7 @@ recursive_connect2(int str1, int str2, i
     }
   }

-  if (num_moves == 0 && distance < 1.0) {
+  if (tried_moves == 0 && distance < 1.0) {
     SGFTRACE2(NO_MOVE, WIN, "no move, probably connected");
     READ_RETURN_CONN(read_result, move, NO_MOVE, WIN);
   }
@@ -2059,6 +2061,7 @@ recursive_disconnect2(int str1, int str2
   int savemove = NO_MOVE;
   int savecode = 0;
   int found_read_result;
+  int tried_moves = 0;
   Read_result *read_result = NULL;

   SETUP_TRACE_INFO2("recursive_disconnect2", str1, str2);
@@ -2127,6 +2130,7 @@ recursive_disconnect2(int str1, int str2
     if (komaster_trymove(xpos, other, "recursive_disconnect2", str1,
                         komaster, kom_pos, &new_komaster, &new_kom_pos,
                         &ko_move, stackp <= ko_depth && savecode == 0)) {
+      tried_moves++;
       if (!ko_move) {
        int dcode = recursive_connect2(str1, str2, NULL,
                                       new_komaster, new_kom_pos, has_passed);
@@ -2152,7 +2156,7 @@ recursive_disconnect2(int str1, int str2
     }
   }

-  if (num_moves == 0
+  if (tried_moves == 0
       && distance >= 1.0
       && (has_passed
          || !recursive_connect2(str1, str2, NULL, komaster, kom_pos, 1))) {
@@ -2194,7 +2198,8 @@ find_connection_moves(int str1, int str2
                      struct connection_data *conn1,
                      struct connection_data *conn2,
                      float max_dist1, float max_dist2,
-                     int moves[MAX_MOVES], float total_distance)
+                     int moves[MAX_MOVES], float total_distance,
+                     float cutoff)
 {
   int color = board[str1];
   int other = OTHER_COLOR(color);
@@ -2385,6 +2390,12 @@ find_connection_moves(int str1, int str2
        gprintf("%o%1M -0.1, disconnect move on edge\n", move);
     }

+    if (ladder_capturable(move, color_to_move)) {
+      distances[r] += 0.3;
+      if (verbose > 0)
+       gprintf("%o%1M +0.3, can be captured in a ladder\n", move);
+    }
+
     /* Bonus for moves adjacent to endpoint strings with 3 liberties.
      * Neighbor strings with less than 3 liberties have already
      * generated a bonus above.
@@ -2465,10 +2476,11 @@ find_connection_moves(int str1, int str2


   /* Filter out moves with distance at least 1.5 more than the best
-   * move.
+   * move, or with distance higher than the cutoff specified.
    */
   for (r = 0; r < num_moves; r++)
-    if (distances[r] > distances[0] + 1.5)
+    if (distances[r] > distances[0] + 1.5
+       || distances[r] > cutoff)
       break;
   num_moves = r;

@@ -2527,7 +2539,8 @@ find_string_connection_moves(int str1, i

   num_moves = find_connection_moves(str1, str2, color_to_move,
                                    &conn1, &conn2, max_dist1, max_dist2,
-                                   moves, *total_distance);
+                                   moves, *total_distance,
+                                   HUGE_CONNECTION_DISTANCE);
   return num_moves;
 }

@@ -2632,9 +2645,14 @@ find_break_moves(int str, const char goa
     print_connection_distances(&conn2);
   }

-  num_moves = find_connection_moves(str, str2, color_to_move,
-                                   &conn1, &conn2, max_dist1, max_dist2,
-                                   moves, *total_distance);
+  {
+    float cutoff = HUGE_CONNECTION_DISTANCE;
+    if (breakin_depth - stackp <= 5)
+      cutoff = 1.1 + (breakin_depth - stackp) * 0.15;
+    num_moves = find_connection_moves(str, str2, color_to_move,
+                                     &conn1, &conn2, max_dist1, max_dist2,
+                                     moves, *total_distance, cutoff);
+  }

   {
     int move;
@@ -2666,6 +2684,7 @@ recursive_break(int str, const char goal
   int savemove = NO_MOVE;
   int savecode = 0;
   int found_read_result;
+  int tried_moves = 0;
   Read_result *read_result = NULL;

   SETUP_TRACE_INFO("recursive_break", str);
@@ -2728,6 +2747,7 @@ recursive_break(int str, const char goal
     if (komaster_trymove(xpos, color, "recursive_break", str,
                         komaster, kom_pos, &new_komaster, &new_kom_pos,
                         &ko_move, stackp <= ko_depth && savecode == 0)) {
+      tried_moves++;
       if (!ko_move) {
        int acode = recursive_block(str, goal, NULL,
                                    new_komaster, new_kom_pos,
@@ -2753,7 +2773,7 @@ recursive_break(int str, const char goal
     }
   }

-  if (num_moves == 0 && distance < 1.0) {
+  if (tried_moves == 0 && distance < 1.0) {
     SGFTRACE(NO_MOVE, WIN, "no move, probably connected");
     READ_RETURN(read_result, move, NO_MOVE, WIN);
   }
@@ -2784,6 +2804,7 @@ recursive_block(int str, const char goal
   int savemove = NO_MOVE;
   int savecode = 0;
   int found_read_result;
+  int tried_moves = 0;
   Read_result *read_result = NULL;
   SETUP_TRACE_INFO("recursive_block", str);

@@ -2848,6 +2869,7 @@ recursive_block(int str, const char goal
     if (komaster_trymove(xpos, other, "recursive_block", str,
                         komaster, kom_pos, &new_komaster, &new_kom_pos,
                         &ko_move, stackp <= ko_depth && savecode == 0)) {
+      tried_moves++;
       if (!ko_move) {
        int dcode = recursive_break(str, goal, NULL,
                                    new_komaster, new_kom_pos, has_passed,
@@ -2873,7 +2895,7 @@ recursive_block(int str, const char goal
     }
   }

-  if (num_moves == 0
+  if (tried_moves == 0
       && distance >= 1.0
       && (has_passed
          || !recursive_break(str, goal, NULL, komaster, kom_pos, 1,
@@ -2893,7 +2915,7 @@ recursive_block(int str, const char goal



-/* Externably callable frontend to recursive_break_in.
+/* Externably callable frontend to recursive_break.
  * Returns WIN if (str) can connect to the area goal[] (which may or may
  * not contain stones), if he gets the first move.
  */
@@ -2920,7 +2942,7 @@ break_in(int str, const char goal[BOARDM

   if (search_persistent_breakin_cache(BREAK_IN, str, goal_hash,
                                         &result, move)) {
-    if (debug & DEBUG_TERRITORY) {
+    if (debug & DEBUG_BREAKIN) {
       gprintf("Break-in from %1m to:\n", str);
       goaldump(goal);
       gprintf("Result cached: %r %1m\n", result, *move);
@@ -2936,7 +2958,7 @@ break_in(int str, const char goal[BOARDM
   result = recursive_break(str, goal, move, EMPTY, NO_MOVE, 0, &goal_hash);
   verbose = save_verbose;
   tactical_nodes = get_reading_node_counter() - reading_nodes_when_called;
-  if (0) {
+  if (debug & DEBUG_BREAKIN) {
     gprintf("%obreak_in    %1M, result %d %1M (%d, %d nodes, %f seconds)\n",
            str, result, *move,
            nodes_connect, tactical_nodes, gg_cputime() - start);
@@ -2979,7 +3001,7 @@ block_off(int str, const char goal[BOARD
   str = find_origin(str);
   if (search_persistent_breakin_cache(BLOCK_OFF, str, goal_hash,
                                         &result, move)) {
-    if (debug & DEBUG_TERRITORY) {
+    if (debug & DEBUG_BREAKIN) {
       gprintf("Blocking off %1m from:\n", str);
       goaldump(goal);
       gprintf("Result cached: %r %1m\n", result, *move);
@@ -2997,7 +3019,7 @@ block_off(int str, const char goal[BOARD
   verbose = save_verbose;
   tactical_nodes = get_reading_node_counter() - reading_nodes_when_called;

-  if (0) {
+  if (debug & DEBUG_BREAKIN) {
     gprintf("%oblock_off %1m, result %d %1m (%d, %d nodes, %f seconds)\n",
            str, result, *move,
            nodes_connect, tactical_nodes, gg_cputime() - start);
Index: regression/trevorc.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/trevorc.tst,v
retrieving revision 1.54
diff -u -p -r1.54 trevorc.tst
--- regression/trevorc.tst      2 Jun 2003 21:30:57 -0000       1.54
+++ regression/trevorc.tst      18 Jun 2003 10:58:02 -0000
@@ -930,7 +930,7 @@ loadsgf games/trevor/auto/c84.sgf 94
 # games/trevor/auto/c86.sgf problems:

 loadsgf games/trevor/auto/c86.sgf 44
-1570 gg_genmove white
+1570 restricted_genmove white E1 E2 F2 F3
 #? [E2|F2|F3]