nando_3_16.1a (was RE: [gnugo-devel] A speedup)

[Portela Fernand]

Supercedes nando_3_16.1

Following is the best tuning I found. I implemented Arend's suggestion,
calling fast_defense() from all defendN functions, thus saving calls to
findlib(), another advantage being that the defensive move will now appear
in sgf traces (it wasn't the case in the former version of the patch).
Using accuratelib() appeared to be (a bit) more effective than fastlib(),
but Paul's other tip is certainly useful. I renamed the 'gained' variable
(misleading) and found another smallish optimization in defend_both().

Breakage is unchanged. Due to calling fast_defense from within the defendN
functions, the gain in reading nodes is down to 0.3%. On the other hand,
I haven't coded in my own regression scripts the retrieval of trymove
counts (I've got to try this pike script one day), but I guess there must be
a significant drop there. The rather imprecise timings I can get here still
show a global speedup of at least 5%.

Thank you all for your contributions :)

/nando

Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.98
diff -u -r1.98 reading.c
--- engine/reading.c    12 Jan 2003 20:51:45 -0000      1.98
+++ engine/reading.c    14 Jan 2003 01:20:42 -0000
@@ -503,6 +503,15 @@
   ASSERT1(IS_STONE(color) , astr);
   ASSERT1(color == board[bstr], bstr);
 
+  /* This probably helps here too...
+   * (see attack_either)
+   */
+  if (countlib(astr) > countlib(bstr)) {
+    int t = astr;
+    astr = bstr;
+    bstr = t;
+  }
+
   attack_and_defend(astr, &acode, NULL, &dcode, &a_savepos);
   if (acode != 0) {
     a_threatened = 1;
@@ -1064,6 +1072,35 @@
 }
 
 
+/* Called by the defendN functions.
+ * Don't think too much if there's an easy way to get enough liberties
+ */
+
+static int
+fast_defense(int str, int liberties, int *libs, int *move)
+{
+  int color = board[str];
+  int k;
+  int newlibs;
+
+  ASSERT1(libs != NULL, str);
+  ASSERT1(move != NULL, str);
+
+  for (k = 0; k < liberties; k++) {
+    /* accuratelib() to be seems more effective than fastlib() here.
+     * (probably because it catches more cases). And since 5 liberties
+     * is enough for our purpose, no need to ask for more.
+     */
+    newlibs = accuratelib(libs[k], color, 5, NULL);
+    if (newlibs > 4
+       || (newlibs == 4 && stackp > fourlib_depth)) {
+      *move = libs[k];
+      return 1;
+    }
+  }
+  return 0;
+}
+
 /* If str points to a string with exactly one liberty, defend1 
  * determines whether it can be saved by extending or capturing
  * a boundary chain having one liberty. The function returns WIN if the
string
@@ -1106,6 +1143,9 @@
   liberties = findlib(str, 1, &lib);
   ASSERT1(liberties == 1, str);
 
+  if (fast_defense(str, liberties, &lib, &xpos))
+    RETURN_RESULT(WIN, xpos, move, "fast defense");
+
   /* Collect moves to try in the first batch.
    * 1. First order liberty.
    * 2. Chain breaking moves.
@@ -1214,6 +1254,9 @@
   liberties = findlib(str, 2, libs);
   ASSERT1(liberties == 2, str);
 
+  if (fast_defense(str, liberties, libs, &xpos))
+    RETURN_RESULT(WIN, xpos, move, "fast defense");
+
   /* Collect moves to try in the first batch.
    * 1. First order liberties.
    * 2. Chain breaking moves.
@@ -1439,6 +1482,9 @@
   liberties = findlib(str, 3, libs);
   ASSERT1(liberties == 3, str);
 
+  if (fast_defense(str, liberties, libs, &xpos))
+    RETURN_RESULT(WIN, xpos, move, "fast defense");
+
   /* Collect moves to try in the first batch.
    * 1. First order liberties.
    * 2. Chain breaking moves.
@@ -1705,6 +1751,9 @@
 
   liberties = findlib(str, 4, libs);
   ASSERT1(liberties == 4, str);
+
+  if (fast_defense(str, liberties, libs, &xpos))
+    RETURN_RESULT(WIN, xpos, move, "fast defense");
 
   /* Collect moves to try in the first batch.
    * 1. First order liberties.