Re[2]: [gnugo-devel] speed optimization continues

[Paul Pogonyshev]

Gunnar wrote:
> This patch is broken, as commented below. When trying to fix it in the
> obvious way two optics test cases fail.

> ./regress.sh . optics.tst
> 322 unexpected FAIL: Correct '0 2 G17 G17', got '0 1 G17 G17'
> 1807 unexpected FAIL: Correct '1 2 F11 (F11|H8|F8)', got '1 1'

strange, i thought i send a valid one. i fixed it and it now passes
optics, life, ld_owl and owl.

by the way, there are 4 PASSes and 1 FAIL in life.tst. i remember them
be before this patch. i attached a small patch at the end of the mail
which updates expected results for that file. life.tst looks much like
a copy of optics.tst. should we not delete it?

Paul


Index: gnugo/engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.54
diff -u -r1.54 optics.c
--- gnugo/engine/optics.c       30 Sep 2002 20:09:57 -0000      1.54
+++ gnugo/engine/optics.c       4 Oct 2002 21:32:41 -0000
@@ -307,12 +307,8 @@
  *
  */
 
-#define lively_stone(pos, color) (board[pos] == color && lively[pos])
-#define has_inf(color, pos) (domain[pos] || lively_stone(pos, color))
 #define sufficient_influence(pos, apos, bpos) \
- (ON_BOARD(bpos) \
-  && (domain[apos] + domain[bpos]) \
-      > (inhibit[pos] > 1) + (inhibit[apos] > 0) + (inhibit[bpos] > 0))
+  (ON_BOARD(bpos) && influence[bpos] > threshold[pos] - influence[apos])
 
 static void
 compute_primary_domains(int color, int domain[BOARDMAX],
@@ -321,89 +317,113 @@
                        int first_time)
 {
   int other = OTHER_COLOR(color);
-  int found_one;
-  int i, j;
-  int pos;
-  int inhibit[BOARDMAX];
-  memset(inhibit, 0, sizeof(inhibit));
+  int i, j, k;
+  int pos, pos2;
+  int own, enemy;
+  char threshold[BOARDMAX];
+  signed char influence[BOARDMAX];
+  int list[BOARDMAX];
+  int size = 0, lastchange = 0;
 
+  memset(threshold, 0, sizeof(threshold));
+  memset(influence, 0, sizeof(influence));
+  
   /* In the first pass we
    * 1. Give influence to lively own stones and their neighbors.
    *    (Cases (1) and (2) above.)
-   * 2. Set inhibit for lively opponent stones and their neighbors.
+   * 2. Fill influence[] and threshold[] arrays with initial values.
    */
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++) {
-      pos = POS(i, j);
-      if (lively_stone(pos, color))
-       domain[pos] = 1; /* Case (1) above. */
-      else if (lively_stone(pos, other))
-       inhibit[pos] = 1;
-      else {
-       if (lively_stone(SOUTH(pos), color)
-           || lively_stone(WEST(pos), color)
-           || lively_stone(NORTH(pos), color)
-           || lively_stone(EAST(pos), color)) {
-         /* Case (2) above.
-          *
-          * To explain the asymmetry between the first time around
-          * this loop and subsequent ones, a false margin is adjacent
-          * to both B and W lively stones, so it's found on the first
-          * pass through the loop.
-          */
-         if (first_time) {
-           if (board[pos] == EMPTY && false_margin(pos, color, lively))
-             false_margins[pos] = 1;
-           else if (board[pos] == EMPTY
-                    && false_margin(pos, other, lively))
-             false_margins[pos] = 1;
-           else
-             domain[pos] = 1;
-         }
-         else {
-           if (IS_STONE(board[pos]) || false_margins[pos] != 1)
-             domain[pos] = 1;
-         }
-       }
-       
-       if (lively_stone(SOUTH(pos), other)
-           || lively_stone(WEST(pos), other)
-           || lively_stone(NORTH(pos), other)
-           || lively_stone(EAST(pos), other))
-         inhibit[pos] = 2;
-       else if (is_edge_vertex(pos))
-         inhibit[pos] = 1;
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (!ON_BOARD(pos))
+      continue;
+   
+    if (lively[pos]) {
+      if (board[pos] == color) {
+        domain[pos] = 1; /* Case (1) above. */
+        influence[pos] = 1;
+      }
+      else
+        influence[pos] = -1;
+      continue;
+    }
+
+    own = enemy = 0;
+    for (k = 0; k < 4; k++) {
+      pos2 = pos + delta[k];
+      if (ON_BOARD(pos2) && lively[pos2]) {
+        if (board[pos2] == color)
+          own = 1;
+        else
+          enemy = 1;
       }
     }
 
+    if (own) {
+      /* To explain the asymmetry between the first time around
+       * this loop and subsequent ones, a false margin is adjacent
+       * to both B and W lively stones, so it's found on the first
+       * pass through the loop.
+       */
+      if (first_time) {
+        if (board[pos] == EMPTY && (false_margin(pos, color, lively)
+            || false_margin(pos, other, lively)))
+          false_margins[pos] = 1;
+        else {
+          domain[pos] = 1;
+          influence[pos] = 1;
+        }
+      }
+      else if (board[pos] != EMPTY || !false_margins[pos]) {
+        domain[pos] = 1;
+        influence[pos] = 1;
+      }
+    }
+    else
+      list[size++] = pos;
+   
+    if (enemy) {
+      threshold[pos] = 1;
+      influence[pos]--;
+    }
+    else if (is_edge_vertex(pos))
+      influence[pos]--;
+  }
+
   /* Now we loop over the board until no more vertices can be added to
    * the domain through case (3) above.
    */
-  do {
-    found_one = 0;
-    for (i = 0; i < board_size; i++)
-      for (j = 0; j < board_size; j++) {
-       pos = POS(i, j);
-       
-       /* First we handle the trivial cases. */
-       if (domain[pos] || lively_stone(pos, other) || false_margins[pos])
-         continue;
-
-       /* Case (3) above. */
-       if (sufficient_influence(pos, SOUTH(pos), SE(pos))
-           || sufficient_influence(pos, SOUTH(pos), SW(pos))
-           || sufficient_influence(pos, WEST(pos), SW(pos))
-           || sufficient_influence(pos, WEST(pos), NW(pos))
-           || sufficient_influence(pos, NORTH(pos), NW(pos))
-           || sufficient_influence(pos, NORTH(pos), NE(pos))
-           || sufficient_influence(pos, EAST(pos), NE(pos))
-           || sufficient_influence(pos, EAST(pos), SE(pos))) {
-         domain[pos] = 1;
-         found_one = 1;
-       }
+  if (size) {
+    k = size;
+    while (1) {
+      if (!k)
+        k = size;
+      pos = list[--k];
+   
+      /* Case (3) above. */
+      if (sufficient_influence(pos, SOUTH(pos), SE(pos))
+          || sufficient_influence(pos, SOUTH(pos), SW(pos))
+          || sufficient_influence(pos, EAST(pos), SE(pos))
+          || sufficient_influence(pos, EAST(pos), NE(pos))
+          || sufficient_influence(pos, WEST(pos), SW(pos))
+          || sufficient_influence(pos, WEST(pos), NW(pos))
+          || sufficient_influence(pos, NORTH(pos), NW(pos))
+          || sufficient_influence(pos, NORTH(pos), NE(pos))) {
+        domain[pos] = 1;
+        influence[pos]++;
+
+        if (!--size)
+          break;
+        if (k < size)
+          list[k] = list[size];
+        else
+          k--;
+        lastchange = k;
       }
-  } while (found_one);
-  
+      else if (k == lastchange)
+        break; /* Looped the whole list and found nothing new */
+    }
+  }
+
   if (0 && (debug & DEBUG_EYES)) {
     start_draw_board();
     for (i = 0; i < board_size; i++)
@@ -415,7 +435,6 @@
 }
 
 
-
 static void
 count_neighbours(struct eye_data eyedata[BOARDMAX])
 {
@@ -446,16 +465,15 @@
 static int
 is_lively(int owl_call, int pos)
 {
-  int result;
+  if (board[pos] == EMPTY)
+    return 0;
 
   if (owl_call)
-    result = owl_lively(pos);
+    return owl_lively(pos);
   else
-    result = (!worm[pos].inessential
-             && (worm[pos].attack_codes[0] == 0
-                 || worm[pos].defense_codes[0] != 0));
-
-  return result;
+    return (!worm[pos].inessential
+      && (worm[pos].attack_codes[0] == 0
+      ||  worm[pos].defense_codes[0] != 0));
 }

Index: gnugo/regression/life.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/life.tst,v
retrieving revision 1.6
diff -u -r1.6 life.tst
--- gnugo/regression/life.tst   19 Sep 2002 12:57:29 -0000      1.6
+++ gnugo/regression/life.tst   4 Oct 2002 21:40:50 -0000
@@ -137,7 +137,7 @@
 1006 eval_eye P6
 #? [1 1]
 1007 eval_eye Q9
-#? [1 1]*
+#? [1 1]
 1008 eval_eye D11
 #? [2 2]
 1009 eval_eye E6
@@ -149,7 +149,7 @@
 1012 eval_eye C1
 #? [1 1]*
 1013 eval_eye O16
-#? [1 2 G16 L16]
+#? [1 2 G16 L16]*
 
 # incident 73
 # This is a problem with make_domains(). The position is a seki.
@@ -160,7 +160,7 @@
 
 loadsgf games/incident73.sgf 212
 1201 eval_eye T10
-#? [1 2 T8 T8]*
+#? [1 2 T8 T8]
 
 # incident 97
 loadsgf games/incident97.sgf 175
@@ -193,7 +193,7 @@
 1704 eval_eye Q19
 #? [1 1]
 1705 eval_eye A19
-#? [1 2 A18 A18]*
+#? [1 2 A18 A18]
 
 # Report number of nodes visited by the tactical reading
 10000 get_reading_node_counter