[gnugo-devel] boundary patch

[Paul Pogonyshev]

This patch is intended to improve owl boundaries.

The most notable change in this patch comes from analyzing nando:26

     A B C D E F G H J K L M N O P Q R S T
  19 . . . . X O X . . . . . O X X . . . . 19
  18 . . . . X . . . O . . O . O X . X . . 18
  17 . . . X . . X X . O . . . O X . X O . 17
  16 . . . + . . . O . + . . O X . X X O O 16
  15 . . X . . O . . . O . . . O X X X O . 15
  14 . . . X X O . O . . . . . O O O X X O 14
  13 . . O . . . . . . O . O . X . X O O . 13
  12 . . . . . X . . . . . . X . X O O . . 12
  11 . . X . . . . X . X X . . X . X O . . 11
  10 X . X + . . . . . + O X X . . + O . . 10
   9 O X . X X . X . . O X X O O O . . . . 9
   8 O X X O . . . . . O O . . . X O . . . 8
   7 O O O . O . . . X . . O O . X O . . . 7
   6 . X . O . . . O . X . . O X . O . . . 6
   5 . O . . . O . . . . . X X . . . . . . 5
   4 O . O O . . . X . X . . . X . O . . . 4
   3 . O . O X X . . . . . . . . X X O . . 3
   2 . O O X . . . . . . . . X X . . O . . 2
   1 . . . . X . . . . . . . . O X . . . . 1
     A B C D E F G H J K L M N O P Q R S T

The problem is that N16 is considered to be a "vital boundary",
because it adjoins a non-dead friendly dragon of size less than 2,
namely the O16 dragon.  The patch puts an additional requirement that
the friendly dragon is not a "neighbor" of the dragon under
consideration or lies "on another side of the boundary" in some sense.
In this position O16 is clearly a neighbor of P19.

Neighbors are defined as dragons that are either diagonally adjacent
with at least one empty vertex on sides of connection, or as dragons
at one point jump distance (a jump over an empty vertex).

In addition, i allowed vital boundary strings to be not only
horizontally/vertically, but also diagonally adjacent to
safe/small-non-dead friendly dragons.  This seemed to be logical, but
didn't give any noticeable results.


Regression breakage:

nngs:1140       FAIL 1 B10 [1 (A11|B11)]

        This one is a problem with the test, not with the patch.  B10
        is a valid defense too.  The patch revises this test.

nngs3:230       FAIL L12 [!L12]

        A fail, but not bad.  First of all, both patched and original
        versions like L12 move.  The reason 3.5.2-pre-1 version of GNU
        Go passes this test is that it considers E13 to be
        owl-defendable and "kills" it with E12 (69.05 vs 67.07 for
        L12).

        The patch actually gives an improvement.  In this position:

             A B C D E F G H J K L M N O P Q R S T
          19 . . . . . . . . . . . . . . . . . . . 19
          18 . . . . . . . . . . . . . . X X O . . 18
          17 . . . . . . X . . X O . O O O X X . . 17
          16 . . . X . . . . . X O . X X X X O X . 16
          15 . . . . . . . . . X O . . . . . O X . 15
          14 . . . X . . . . . . O . X . O . O X . 14
          13 . X . . O . . . X . O X . X O . O . . 13
          12 . O X X O . X . . . . O . . X O . . . 12
          11 . X O O O . . . . . . . . . . . . . . 11
          10 . . O X X X . X . X . . . O . X . . . 10
           9 . O O O X . . . . . . . . . . . . . . 9
           8 X O O X O O O O . . . . . . . . . . . 8
           7 . O X X . O X . . . . O . . . O . . . 7
           6 . X . X . O X . . . O . O . . . . . . 6
           5 . . . . . O X . . . . O X X . . . X . 5
           4 . . . X . O . . O X O . O X . X X . X 4
           3 . . . . X O . X . O X . O X . . O X . 3
           2 . . . . X X . . . . . . X . . . . O . 2
           1 . . . . . . . . . . . . . . . . . . . 1
             A B C D E F G H J K L M N O P Q R S T

        3.5.2-pre-1 tries D13 for white and then attacker surrenders,
        because the dragon is "getting deep, looks lively".  The
        patched version doesn't even try this move (not sure why,
        though).

nando:26        PASS 0 [0]

        The targeted test.  Solved properly.

trevorb:120 and nngs4:420

        Two accidential fails caused by certain patterns no longer
        being matched after the patch (because boundary strings were
        correctly downgraded to non-vital by the patch).  These are
        resolved by two additional patterns.

The patch causes a small decrease (about 0.2%) in owl node counter
(before is 3.5.2-pre-1 with escape values patch):

before:  1512155669 2467554 8795393
after:   1510276776 2462124 8803775

Paul



--- engine/owl.c.~1.179.~       2003-10-22 02:55:54.000000000 +0000
+++ engine/owl.c        2003-11-06 14:19:47.000000000 +0000
@@ -67,10 +67,13 @@ struct local_owl_data {
   char goal[BOARDMAX];
   char boundary[BOARDMAX];
 
-  /* FIXME: escape_values[] are never recomputed. Consider moving this array
-   *       from stack to a static or dynamic variable so it is not copied
-   *       around in do_push_owl(). Be aware of semeai code though.
+  /* FIXME: neighbors[] and escape_values[] are never recomputed.
+   *       Consider moving these arrays from stack to a static or
+   *       dynamic variable so it is not copied around in
+   *       do_push_owl().  Be aware of semeai code though.
    */
+  char neighbors[BOARDMAX];
+
   char escape_values[BOARDMAX];
   int color;
 
@@ -3739,30 +3742,59 @@ owl_mark_worm(int apos, int bpos, struct
 static void
 owl_mark_boundary(struct local_owl_data *owl)
 {
-  int pos;
-  int other = OTHER_COLOR(owl->color);
   int k;
+  int pos;
+  int color = owl->color;
+  int other = OTHER_COLOR(color);
   
   memset(owl->boundary, 0, sizeof(owl->boundary));
-  /* first find all boundary strings. */
+  memset(owl->neighbors, 0, sizeof(owl->neighbors));
+
+  /* Find all friendly neighbors of the dragon in goal. */
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (board[pos] == color && owl->goal[pos]) {
+      for (k = 0; k < 4; k++) {
+       if (board[pos + delta[k]] == EMPTY
+           && board[pos + 2 * delta[k]] == color
+           && !owl->neighbors[pos + 2 * delta[k]])
+         mark_string(pos + 2 * delta[k], owl->neighbors, 1);
+      }
+
+      for (; k < 8; k++) {
+       int pos2 = pos + delta[k];
+
+       if (board[pos2] == color
+           && !owl->neighbors[pos2]
+           && (board[SOUTH(gg_min(pos, pos2))] == EMPTY
+               || board[NORTH(gg_max(pos, pos2))] == EMPTY))
+         mark_string(pos2, owl->neighbors, 1);
+      }
+    }
+  }
+
+  /* First find all boundary strings (including those adjacent not to
+   * the goal dragon, but one of its neighbors).
+   */
   for (pos = BOARDMIN; pos < BOARDMAX; pos++)
     if (board[pos] == other && !owl->boundary[pos]) {
       for (k = 0; k < 8; k++)
-       if (ON_BOARD(pos + delta[k]) && owl->goal[pos + delta[k]]) {
+       if (ON_BOARD(pos + delta[k])
+           && (owl->goal[pos + delta[k]] || owl->neighbors[pos + delta[k]])) {
          mark_string(pos, owl->boundary, 1);
          break;
        }
     }
-  
+
   /* Upgrade the mark of a boundary string if it adjoins a safe
    * friendly dragon.
    */
   for (pos = BOARDMIN; pos < BOARDMAX; pos++)
-    if (board[pos] == other && owl->boundary[pos] == 1) {
-      for (k = 0; k < 4; k++) {
+    if (owl->boundary[pos] == 1) {
+      for (k = 0; k < 8; k++) {
        int pos2 = pos + delta[k];
-       if (board[pos2] == owl->color
+       if (board[pos2] == color
            && !owl->goal[pos2]
+           && !owl->neighbors[pos2]
            && ((dragon[pos2].crude_status != DEAD && countstones(pos2) > 2)
                || dragon[pos2].crude_status == ALIVE)) {
          mark_string(pos, owl->boundary, 2);
@@ -3798,7 +3830,7 @@ owl_mark_boundary(struct local_owl_data 
        int d = DRAGON2(pos).adjacent[k];
        int apos = dragon2[d].origin;
        
-       if (board[apos] == owl->color && !owl->goal[apos]) {
+       if (board[apos] == color && !owl->goal[apos]) {
          owl->boundary[pos] = 2;
          break;
        }
@@ -3878,22 +3910,19 @@ owl_update_boundary_marks(int pos, struc
 
   for (k = 0; k < 4; k++) {
     int pos2 = pos + delta[k];
+
     if (ON_BOARD(pos2) && owl->boundary[pos2] > boundary_mark)
       boundary_mark = owl->boundary[pos2];
+
     if (board[pos2] == owl->color
        && dragon[pos2].color == owl->color
        && dragon[pos2].status == ALIVE
-       && !owl->goal[pos2])
+       && !owl->goal[pos2]
+       && !owl->neighbors[pos2])
       boundary_mark = 2;
   }
-  owl->boundary[pos] = boundary_mark;
 
-  for (k = 0; k < 4; k++) {
-    int pos2 = pos + delta[k];
-    if (board[pos2] == board[pos]
-       && owl->boundary[pos2] < boundary_mark)
-      mark_string(pos2, owl->boundary, boundary_mark);
-  }
+  mark_string(pos, owl->boundary, boundary_mark);
 }
 
 /* Lists the goal array. For use in GDB:
@@ -5490,6 +5540,7 @@ do_push_owl(struct local_owl_data **owl)
   /* Copy the owl data. */
   memcpy(new_owl->goal, (*owl)->goal, sizeof(new_owl->goal));
   memcpy(new_owl->boundary, (*owl)->boundary, sizeof(new_owl->boundary));
+  memcpy(new_owl->neighbors, (*owl)->neighbors, sizeof(new_owl->neighbors));
   memcpy(new_owl->escape_values, (*owl)->escape_values,
         sizeof(new_owl->escape_values));
   new_owl->color = (*owl)->color;
--- patterns/owl_attackpats.db.~1.94.~  2003-11-03 23:30:43.000000000 +0000
+++ patterns/owl_attackpats.db  2003-11-06 14:12:42.000000000 +0000
@@ -4470,6 +4470,23 @@ cd??
 ;owl_escape_value(c) + owl_escape_value(d) > 0
 
 
+Pattern VA54
+# pp New pattern (3.5.3).  See trevorb:120.
+# FIXME: is it better to do this algorithmically with owl boundaries?
+
+XOX        prevent escaping by capturing
+.*O
+---
+
+:8,-,value(75)
+
+BOX
+.*A
+---
+
+; lib(A) == 1 && owl_escape_value(B) > 0
+
+
 #########################################################
 #                                                       #
 #       Kill or threaten a worm of the dragon           #
--- patterns/owl_defendpats.db.~1.104.~ 2003-11-03 23:30:51.000000000 +0000
+++ patterns/owl_defendpats.db  2003-11-06 14:28:20.000000000 +0000
@@ -4810,6 +4810,24 @@ a*.
 ; lib(a) == 2 || oplay_attack(*,a)
 
 
+Pattern D1142
+# pp New pattern (3.5.3).  See nngs4:420.
+
+?X?        split boundary in hope that it will help;
+*OX        low value because it's not guaranteed it will
+?XO
+
+:-,b,value(30)
+
+?C?
+*AX
+?DB
+
+; does_defend(*,A) && !oplay_attack(*,B)
+; && !same_string(B,C) && vital_chain(B) && vital_chain(C)
+; && (oplay_attack(*,B) || oplay_attack(*,C)) && !oplay_connect(*,B,C)
+
+
 ########################################################
 #                                                       #
 #                       Kikashi                         #
--- regression/nngs.tst.~1.64.~ 2003-09-06 00:23:44.000000000 +0000
+++ regression/nngs.tst 2003-11-06 19:20:01.000000000 +0000
@@ -533,7 +533,7 @@ loadsgf games/nngs/gnugo-3.1.18-goku-200
 
 loadsgf games/nngs/gnugo-3.1.18-gopriest-200201072104.sgf 42
 1140 owl_defend B13
-#? [1 (A11|B11)]
+#? [1 (A11|B11|B10)]
 
 
 loadsgf games/nngs/gnugo-3.1.18-gopriest-200201072104.sgf 54