[gnugo-devel] connection distances

[Arend Bayer]

- connection tuning
- new function spread_connection_distances() broken out of
  compute_connection_distances()

This is part of arend_3_20.5.
It splits up compute_connection_distances() into a function that
initializes the connection data, and the function
spread_connection_distances(), which does the actual computing of connection
distances. This is to allow this function to get used in different
circumstances:

- connect (string, opp. territory) as discussed in the tesuji threat recently
- my experimental owl escape patch uses it to compute which vertices are
"nearby" to the goal dragon

Of course, reusing this code for different purposes will make it harder
to change it. But my impression is that it works so well that we shouldn't
expect major changes there any time soon. Gunnar?


Additionally, it does some minor tuning to the computation of connection
distances. The intention is:

.......
....X..
.OaObO.
.......
Here white should obviously try to play at "b" first, not "a".
These two points can be distinguished by approxlib(pos, X).

It gives a 1% speedup, and 1 PASS/1 FAIL. Both changes are caused by
a now correct (and formerly wrong) readconnect result (will add test case).

Arend


Index: engine/readconnect.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/readconnect.c,v
retrieving revision 1.46
diff -u -p -r1.46 readconnect.c
--- engine/readconnect.c        30 Apr 2003 16:20:27 -0000      1.46
+++ engine/readconnect.c        16 May 2003 12:51:51 -0000
@@ -2524,7 +2553,7 @@ find_connection_moves(int str1, int str2
       } \
       else { \
         int r; \
-        num_stones = findstones(pos, MAX_BOARD * MAX_BOARD, stones); \
+        int num_stones = findstones(pos, MAX_BOARD * MAX_BOARD, stones); \
         for (r = 0; r < num_stones; r++) { \
           if (conn->distances[stones[r]] == HUGE_CONNECTION_DISTANCE) \
             conn->queue[conn->queue_end++] = stones[r]; \
@@ -2538,12 +2567,11 @@ find_connection_moves(int str1, int str2
        } \
       } \
     } \
-  } while (0);
+  } while (0)

-/* Compute connection distances from the string str to nearby
- * vertices. This is a rough approximation of the number of moves
- * required to secure a connection from str to another vertex of the
- * board. We also compute delta values which are intended to tell how
+/* Do the real work of computing connection distances.
+ * This is a rough approximation of the number of moves required to secure
+ * a connection. We also compute delta values which are intended to tell how
  * big difference a particular move locally has on the connection
  * distance. However, remember that this is only a heuristic with the
  * sole purpose of helping to find relevant moves for connection
@@ -2598,38 +2626,26 @@ find_connection_moves(int str1, int str2
  * That is because there is a pattern directly recognizing the safe
  * link between the two lower stones, without taking the longer road
  * over the two diagonal links.
+ *
+ * (color) is the color for which we are computing connection distances,
+ * (target) the position we want to reach (can be set to NO_MOVE),
+ * (*conn) has to have the queue initialized with the positions
+ * from which we want to know the distances,
+ * (cutoff_distance) is the highest distance before we give up,
+ * (speculative) controls some special cases in the propagation rules
+ * below.
  */

-static void
-compute_connection_distances(int str, int target, struct connection_data *conn)
+void
+spread_connection_distances(int color, int target,
+                           struct connection_data *conn,
+                           float cutoff_distance, int speculative)
 {
-  int color = board[str];
   int other = OTHER_COLOR(color);
+  float distance;
   int pos;
   int k;
-  float distance;
   int stones[MAX_BOARD * MAX_BOARD];
-  int num_stones = findstones(str, MAX_BOARD * MAX_BOARD, stones);
-  float cutoff_distance = 3.0001;
-
-  conn->queue_start = 0;
-  conn->queue_end = 0;
-
-  /* Initialize distance and delta values so that the former are
-   * everywhere huge and the latter everywhere zero.
-   */
-  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
-    conn->distances[pos] = HUGE_CONNECTION_DISTANCE;
-    conn->deltas[pos] = 0.0;
-    conn->coming_from[pos] = NO_MOVE;
-    conn->vulnerable1[pos] = NO_MOVE;
-    conn->vulnerable2[pos] = NO_MOVE;
-  }
-
-  /* Add all stones in the initial string to the queue. */
-  for (k = 0; k < num_stones; k++) {
-    ENQUEUE(conn, NO_MOVE, stones[k], 0.0, 0.0, NO_MOVE, NO_MOVE);
-  }

   /* Loop until we reach the end of the queue. */
   for (; conn->queue_start < conn->queue_end; conn->queue_start++) {
@@ -2828,16 +2844,26 @@ compute_connection_distances(int str, in
         * a ladder.
         */
        if (board[apos] == EMPTY
-           && conn->distances[apos] > distance + 0.7
+           && conn->distances[apos] > distance + 0.6
            && ladder_capturable(apos, other)) {
-         ENQUEUE(conn, pos, apos, distance + 0.7, 0.7, apos, NO_MOVE);
+         ENQUEUE(conn, pos, apos, distance + 0.6, 0.6, apos, NO_MOVE);
        }

-       /* Case 7. "a" is empty or occupied by opponent.
-        */
-       if ((board[apos] == EMPTY || board[apos] == other)
+       /* Case 7a. "a" is empty. */
+       if (board[apos] == EMPTY) {
+         float this_delta
+           = 0.85 + 0.05 * gg_min(approxlib(apos, other, 5, NULL), 5);
+         ENQUEUE(conn, pos, apos, distance + this_delta, this_delta,
+                 NO_MOVE, NO_MOVE);
+       }
+
+       /* Case 7b. "a" is occupied by opponent. */
+       if (board[apos] == other
            && conn->distances[apos] > distance + 1.0) {
-         ENQUEUE(conn, pos, apos, distance + 1.0, 1.0, NO_MOVE, NO_MOVE);
+         if (speculative)
+           ENQUEUE(conn, pos, apos, distance + 1.0, 1.0, NO_MOVE, NO_MOVE);
+         else
+           ENQUEUE(conn, pos, apos, distance + 1.1, 1.1, NO_MOVE, NO_MOVE);
        }

        /* Case 8. Diagonal connection to empty vertex "b" through
@@ -3064,9 +3095,14 @@ compute_connection_distances(int str, in
          ENQUEUE(conn, pos, apos, distance, 0.0,
                  conn->vulnerable1[pos], conn->vulnerable2[pos]);
        }
-       else if (ON_BOARD(apos)) {
-         ENQUEUE(conn, pos, apos, distance + 1.0, 1.0, NO_MOVE, NO_MOVE);
+       else if (board[apos] == EMPTY) {
+         float this_delta
+           = 0.8 + 0.05 * gg_min(approxlib(apos, other, 6, NULL), 6);
+         ENQUEUE(conn, pos, apos, distance + this_delta, this_delta,
+                 NO_MOVE, NO_MOVE);
        }
+       else if (board[apos] == OTHER_COLOR(color))
+         ENQUEUE(conn, pos, apos, distance + 1.0, 1.0, NO_MOVE, NO_MOVE);

        /* Case 1. Diagonal connection to empty vertex "b" through
         * empty vertices "a" and "g".
@@ -3093,8 +3129,56 @@ compute_connection_distances(int str, in
 }


-/* Print the connection distances in a struct connection_data. */
+/* Compute the connection distances from string (str) to nearby
+ * vertices, until we reach target or the distance gets too high.
+ */
 static void
+compute_connection_distances(int str, int target, struct connection_data *conn)
+{
+  int color = board[str];
+
+  clear_connection_data(conn);
+
+  /* Add all stones in the initial string to the queue. */
+  {
+    int stones[MAX_BOARD * MAX_BOARD];
+    int num_stones = findstones(str, MAX_BOARD * MAX_BOARD, stones);
+    int k;
+    for (k = 0; k < num_stones; k++) {
+      conn->queue[conn->queue_end++] = stones[k];
+      conn->distances[stones[k]] = 0.0;
+      conn->deltas[stones[k]] = 0.0;
+      conn->coming_from[stones[k]] = NO_MOVE;
+      conn->vulnerable1[stones[k]] = NO_MOVE;
+      conn->vulnerable2[stones[k]] = NO_MOVE;
+    }
+  }
+  spread_connection_distances(color, target, conn, 3.0501, 1);
+}
+
+
+/* Initialize distance and delta values so that the former are
+ * everywhere huge and the latter everywhere zero.
+ */
+void
+clear_connection_data(struct connection_data *conn)
+{
+  int pos;
+
+  conn->queue_start = 0;
+  conn->queue_end = 0;
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    conn->distances[pos] = HUGE_CONNECTION_DISTANCE;
+    conn->deltas[pos] = 0.0;
+    conn->coming_from[pos] = NO_MOVE;
+    conn->vulnerable1[pos] = NO_MOVE;
+    conn->vulnerable2[pos] = NO_MOVE;
+  }
+}
+
+
+/* Print the connection distances in a struct connection_data. */
+void
 print_connection_distances(struct connection_data *conn)
 {
   int i, j;