Re: [gnugo-devel] attack_either patches analysis

[Arend Bayer]

Evan wrote:

> I finally got around to analyzing the delta on the attack_either patches.

I just found some time, too.

> 13x13:42     Properly solved
> 13x13:40     Accidental
> trevora:220  unsure, maybe accidental
> nngs3:670    Properly solved
>
>
>
> 13x13:42
>
> The following gtp should make it clear what's going on (fails without the
> patch, passes with)
>
> loadsgf games/mertin13x13/katsunari-gnugo2.W+4.sgf 126
> black L4
> defend_both N7 K4
> #? [0]

As I said in a previous e-mail, this is not correct. However, this is
not the fault of your patch, but a reading mistake further down in the
tree:

loadsgf games/mertin13x13/katsunari-gnugo2.W+4.sgf 126
trymove black L4
trymove white N3
trymove black N2
defend K4
#? [1 N1]
popgo
popgo
popgo


> nngs3:670
>
> here, the reason appears to be that an owl_attack and owl_defend pair is
> found for the dragon at D13 that wasn't before.  (D12 is both the attack
> and defense point).

> loadsgf games/nngs/Lazarus-gnugo-3.1.34-200204280120.sgf 32
> owl_attack D13
> #? [1 D12]
>
> is the relevant GTP.  I have not investigated in detail how the attack is
> found.

This is a very good change due to your patch. After black D12, white
C13, the (here very good) pattern A1005 matches only with it. The
constraint translates into the following gtp sequence:

loadsgf games/nngs/Lazarus-gnugo-3.1.34-200204280120.sgf 32
trymove black D12
trymove white C13
trymove white C12
trymove white C11
attack_either C11 D12
#? [1 D12]
popgo
popgo
popgo
popgo

What remains to do is a measurement whether your patches have a negative
performance impact.

Arend


(Below is an update of your two patches against currenct CVS.)




Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.83
diff -u -p -r1.83 reading.c
--- engine/reading.c    20 Oct 2002 10:05:39 -0000      1.83
+++ engine/reading.c    7 Nov 2002 10:59:18 -0000
@@ -423,8 +423,8 @@ attack_and_defend(int str,
  * 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 @@ attack_and_defend(int str,
  *
  *        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,6 +446,7 @@ attack_either(int astr, int bstr)
   int asuccess = 0;
   int bsuccess = 0;
   int color = board[astr];
+  int best = 0;
   ASSERT1(IS_STONE(color) , astr);
   ASSERT1(color == board[bstr], bstr);

@@ -458,35 +464,66 @@ attack_either(int astr, int bstr)
     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);
     int defended0 = WIN;
     int defended1 = WIN;
     int other = OTHER_COLOR(color);
     /* 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)) {
+    if (alibcount == 2) {
+      if (trymove(alibs[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,
+         && trymove(alibs[1], other, "attack_either-B", astr,
                     EMPTY, NO_MOVE)) {
        defended1 = defend_both(astr, bstr);
        popgo();
       }
+      best =  gg_max(best, REVERSE_RESULT(gg_min(defended0, defended1)));
+      if (best == WIN) return best;
+    }
+
+
+    if (blibcount == 2) {
+      if (trymove(blibs[0], other, "attack_either-A", astr, EMPTY, NO_MOVE)) {
+       defended0 = defend_both(astr, bstr);
+       popgo();
+      }
+      if (defended0
+         && trymove(blibs[1], other, "attack_either-B", astr,
+                    EMPTY, NO_MOVE)) {
+       defended1 = defend_both(astr, bstr);
+       popgo();
+      }
+      best = gg_max(best, REVERSE_RESULT(gg_min(defended0, defended1)));
     }
-    return REVERSE_RESULT(gg_min(defended0, defended1));
-  }

+    return best;
+  }
 }


@@ -510,6 +547,7 @@ defend_both(int astr, int bstr)
   int b_savepos;
   int acode = 0;
   int dcode = 0;
+  int best = 0;

   int color = board[astr];
   ASSERT1(IS_STONE(color) , astr);
@@ -553,19 +591,19 @@ defend_both(int astr, int bstr)
    */

   if (trymove(a_savepos, color, "defend_both-A", astr, EMPTY, NO_MOVE)) {
-    if (board[bstr] && !attack(bstr, NULL)) {
-      popgo();
-      return WIN;
+    if (board[bstr]) {
+      best = gg_max(best, REVERSE_RESULT(attack_either(astr, bstr)));
     }
     popgo();
+    if (best == WIN) return best;
   }

   if (trymove(b_savepos, color, "defend_both-B", bstr, EMPTY, NO_MOVE)) {
-    if (board[astr] && !attack(astr, NULL)) {
-      popgo();
-      return WIN;
+    if (board[bstr]) {
+      best = gg_max(best, REVERSE_RESULT(attack_either(astr, bstr)));
     }
     popgo();
+    if (best == WIN) return best;
   }

   /* The next improvement is to try to attack a common adjacent string. */
@@ -597,21 +635,21 @@ defend_both(int astr, int bstr)

        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;
+           if (board[astr] && board[bstr]) {
+             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;
 }