Re: [gnugo-devel] attack_either patches analysis

[Evan Berggren Daniel]

On Fri, 8 Nov 2002, Evan Berggren Daniel wrote:

> > 1. just return asuccess when the other string is safe, i.e.
> >     if countlib(bstr) >= 5 or maybe 4
> > 2. similar if stackp > branch_depth
> > 3. really not worry about ko results when you've already called
> >     defend_both() (you simply cannot do that when you don't use a
> >     komaster scheme).
> > 4. try to return as soon as possible (i.e. insert
> >     if (defend0 != 0)
> >       return defended0;
> >     between the two alibs trymove's
> > 5. maybe worry about not playing the same move twice (in case they
> >     have common liberties).
> >
> > Evan, do you want to give (some of) it a try?
>
> Yes, I plan to do that.
>
> I'm going to move both functions to the candidate move macros, and maybe
> add some depth checks.

I did that, and the results look good.  Reading nodes in owl.tst go from
25347652 (cvs) to 25278457 (with new patch), or about a 0.2% increase.
I'm not entirely sure how this translates to total time, or how comparable
it is to all of first_batch.

I have not run regressions, but I did check that nothing changed in
owl.tst or 13x13.tst as compared to the old version of the patch.

Oh, as for your 3rd point about komaster schemes, there is a case where it
makes sense to return ko results:

Attack_either calls defend_both calls attack_either, which gets as the
best result a ko from attack(astr) or attack(bstr).  The ko result should
probably be propogated back up.

Of course, a real komaster scheme is probably worth trying, and I'll do
that when I'm done with my current patch attempt.

The patch below includes both of my original patches, and is against
current cvs.

Thanks again

Evan Daniel

Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.83
diff -u -r1.83 reading.c
--- engine/reading.c    20 Oct 2002 10:05:39 -0000      1.83
+++ engine/reading.c    8 Nov 2002 17:11:32 -0000
@@ -423,8 +423,8 @@
  * stones.
  *
  * FIXME: The current implementation only looks for uncoordinated
- *        attacks. This is insufficient to find double ataris or
- *        moves such as 'a' in positions like
+ *        attacks. This is insufficient to find moves such as 'a'
+ *        in positions like
  *
  *        XOOOOOOOX
  *        XOXXOXXOX
@@ -433,6 +433,11 @@
  *
  *        where neither of the threatened X stones can be captured right
  *        out. Still either can be captured by a move down to a.
+ *
+ *        This is not actually a big deal.  We (currently, as of 3.3.9)
+ *        don't use this function in cases like that.  Fixing this
+ *        generates 0 PASSes.  Perhaps we should use it like that,
+ *        but it's probably too expensive.
  */

 int
@@ -441,8 +446,11 @@
   int asuccess = 0;
   int bsuccess = 0;
   int color = board[astr];
+  int best = 0;
+  struct reading_moves moves;
   ASSERT1(IS_STONE(color) , astr);
   ASSERT1(color == board[bstr], bstr);
+  moves.num = 0;

   /* Start by attacking the string with the fewest liberties. On
    * average this seems to be slightly more efficient.
@@ -458,35 +466,58 @@
     return asuccess;

   bsuccess = attack(bstr, NULL);
-  if (asuccess || bsuccess) {
-    return (asuccess > bsuccess) ? asuccess : bsuccess;
-  }
+  if (bsuccess == WIN)
+    return bsuccess;
+
+  best = gg_max(asuccess, bsuccess);
+
+  /* We could attempt to upgrade ko results, but it doesn't
+   * seem to help any.
+   */
+  if (best != 0) return best;
+
+  /* this is to prevent a crash in case of
+   * alib == 1, blib == 2, and a snapback around a.
+   */
+  if (countlib(astr) == 1)
+    return best;

   /* Try (a little) harder */
   {
-    int libs[2];
-    int alibs = findlib(astr, 2, libs);
+    int alibs[2];
+    int blibs[2];
+    int alibcount = findlib(astr, 2, alibs);
+    int blibcount = findlib(bstr, 2, blibs);
+#if 0
     int defended0 = WIN;
     int defended1 = WIN;
+#endif
     int other = OTHER_COLOR(color);
+    int k;
     /* Let's just try the case where the group with the fewest liberties
      * has only 2, and try each atari in turn.
      */
-    if (alibs == 2) {
-      if (trymove(libs[0], other, "attack_either-A", astr, EMPTY, NO_MOVE)) {
-       defended0 = defend_both(astr, bstr);
-       popgo();
-      }
-      if (defended0
-         && trymove(libs[1], other, "attack_either-B", astr,
-                    EMPTY, NO_MOVE)) {
-       defended1 = defend_both(astr, bstr);
+    if (alibcount == 2) {
+           ADD_CANDIDATE_MOVE(alibs[0], 0, moves);
+           ADD_CANDIDATE_MOVE(alibs[1], 0, moves);
+    }
+
+    if (blibcount == 2) {
+           ADD_CANDIDATE_MOVE(blibs[0], 0, moves);
+           ADD_CANDIDATE_MOVE(blibs[1], 0, moves);
+    }
+
+    for (k = 0; k < moves.num; k++) {
+      if (trymove(moves.pos[k], other, "attack_either", astr, EMPTY, NO_MOVE)) 
{
+        best = gg_max(best, REVERSE_RESULT(defend_both(astr, bstr)));
        popgo();
+       if (best == WIN)
+         return best;
       }
     }
-    return REVERSE_RESULT(gg_min(defended0, defended1));
-  }

+    return best;
+  }
 }


@@ -510,8 +541,12 @@
   int b_savepos;
   int acode = 0;
   int dcode = 0;
-
+  int best = 0;
   int color = board[astr];
+  struct reading_moves moves;
+  int k;
+  moves.num = 0;
+
   ASSERT1(IS_STONE(color) , astr);
   ASSERT1(color == board[bstr], bstr);

@@ -552,21 +587,8 @@
    * somewhat pessimistic estimation.
    */

-  if (trymove(a_savepos, color, "defend_both-A", astr, EMPTY, NO_MOVE)) {
-    if (board[bstr] && !attack(bstr, NULL)) {
-      popgo();
-      return WIN;
-    }
-    popgo();
-  }
-
-  if (trymove(b_savepos, color, "defend_both-B", bstr, EMPTY, NO_MOVE)) {
-    if (board[astr] && !attack(astr, NULL)) {
-      popgo();
-      return WIN;
-    }
-    popgo();
-  }
+  ADD_CANDIDATE_MOVE(a_savepos, 0, moves);
+  ADD_CANDIDATE_MOVE(b_savepos, 0, moves);

   /* The next improvement is to try to attack a common adjacent string. */
   {
@@ -596,22 +618,25 @@
          continue;   /* No, it wasn't. */

        if (attack(epos, &fpos)) {
-         if (trymove(fpos, color, "defend_both-C", astr, EMPTY, NO_MOVE)) {
-           if (board[astr] && board[bstr]
-               && !attack(astr, NULL)
-               && !attack(bstr, NULL)) {
-             popgo();
-             return WIN;
-           }
-           popgo();
-         }
+         ADD_CANDIDATE_MOVE(fpos, 0, moves);
        }
       }
     }
   }
+
+  for (k = 0; k < moves.num; k++) {
+    if (trymove(moves.pos[k], color, "defend_both", astr, EMPTY, NO_MOVE)) {
+      best = gg_max(best, REVERSE_RESULT(attack_either(astr, bstr)));
+      popgo();
+      if (best == WIN)
+       return best;
+    }
+  }

-  /* Both strings can be attacked but we have only time to defend one. */
-  return 0;
+  /* We haven't found a way to guarantee defense, but we might have found
+   * a way to defend in ko.
+   */
+  return best;
 }