Re: [gnugo-devel] Patch: Strategic effect for strategic attacks and defenses

[Gunnar Farneback]

Inge wrote:
> trevorb:390   FAILs for other reason
>                 The chosen move, F7, has a valuation of 6 points for
>                 "defends against combination attack on several worms",
>                 which a) does only capture in ko and b) the correct
>                 move also protects against.  
> 
>                 The problem here is that atari-atari only generates
>                 one defense point.

Wrong, atari_atari (or strictly speaking combinations()) generates up
to four defense points. In this particular case F7, G7, and G6 (the
correct move) are found.

But it's correct that atari_atari sometimes misses the best defense
when there are lots of candidates. This patch solves the problem by
forcing atari_atari to generate nearly all possible defense
moves.

This is done by marking all potential defense moves during the
atari_atari reading, i.e. moves in the attack sequence, liberties of
moves in the attack sequence, and moves defending some threatened
string in the sequence. To determine which of them are really
effective, we play the move and see whether the combination attack has
gone away.

The regression delta is good, 12 passes, no failures.

./regress.sh . trevorb.tst
380 unexpected PASS!
./regress.sh . trevor.tst
280 unexpected PASS!
410 unexpected PASS!
./regress.sh . nngs.tst
420 unexpected PASS!
1890 unexpected PASS!
./regress.sh . trevorc.tst
690 unexpected PASS!
950 unexpected PASS!
./regress.sh . trevord.tst
680 unexpected PASS!
./regress.sh . nngs2.tst
210 unexpected PASS!
./regress.sh . nngs3.tst
750 unexpected PASS!
./regress.sh . strategy5.tst
273 unexpected PASS!
274 unexpected PASS!

- combinations() revised
- atari_atari() generates lots of defense moves and validates them
- do_atari_atari() generates lots of potential defense moves
- decide_combination() revised
- YOUR_ATARI_ATARI_MOVE considered safe in examine_move_safety()
- atari_atari tuning

/Gunnar

Index: engine/combination.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/combination.c,v
retrieving revision 1.37
diff -u -r1.37 combination.c
--- engine/combination.c        30 Sep 2002 01:59:42 -0000      1.37
+++ engine/combination.c        19 Oct 2002 10:17:38 -0000
@@ -46,7 +46,7 @@
 {
   int save_verbose;
   int attack_point;
-  int defense_point;
+  char defense_points[BOARDMAX];
   int other = OTHER_COLOR(color);
   int aa_val;
 
@@ -68,25 +68,19 @@
     add_my_atari_atari_move(attack_point, aa_val);
   }
   
-  aa_val = atari_atari(other, &attack_point, &defense_point, save_verbose);
+  aa_val = atari_atari(other, &attack_point, defense_points, save_verbose);
   if (aa_val > 0) {
-    int libs[2];
+    int pos;
     if (save_verbose)
-      gprintf("Combination attack for %C with size %d found at %1m, defense at 
%1m\n",
-             other, aa_val, attack_point, defense_point);
-    if (defense_point != NO_MOVE && safe_move(defense_point, color))
-      add_your_atari_atari_move(defense_point, aa_val);
-    /* Playing at the attack point is probably also a defense. */
-    if (safe_move(attack_point, color))
-      add_your_atari_atari_move(attack_point, aa_val);
-    /* If the attacking move gets two liberties, playing first on one
-     * of them is probably a defense.
-     */
-    if (approxlib(attack_point, other, 2, libs) == 2) {
-      if (safe_move(libs[0], color))
-       add_your_atari_atari_move(libs[0], aa_val);
-      if (safe_move(libs[1], color))
-       add_your_atari_atari_move(libs[1], aa_val);
+      gprintf("Combination attack for %C with size %d found at %1m\n",
+             other, aa_val, attack_point);
+    
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+      if (ON_BOARD(pos) && defense_points[pos]) {
+       add_your_atari_atari_move(pos, aa_val);
+       if (save_verbose)
+         gprintf("- defense at %1m\n", pos);
+      }
     }
   }
   verbose = save_verbose;
@@ -215,9 +209,9 @@
 static void compute_aa_status(int color, const char safe_stones[BOARDMAX]);
 static void compute_aa_values(int color);
 static int get_aa_status(int pos);
-static int do_atari_atari(int color, int *attack_point,
-                         int *defense_point, int last_friendly,
-                         int save_verbose, int minsize,
+static int do_atari_atari(int color, int *attack_point, int *defense_point,
+                         char all_potential_defenses[BOARDMAX],
+                         int last_friendly, int save_verbose, int minsize,
                          char goal[BOARDMAX]);
 static int atari_atari_succeeded(int color, int *attack_point,
                                 int *defense_point, int last_friendly,
@@ -246,11 +240,14 @@
 /* Set to 1 if you want verbose traces from this function. */
 
 int
-atari_atari(int color, int *attack_move, int *defense_move, int save_verbose)
+atari_atari(int color, int *attack_move, char defense_moves[BOARDMAX],
+           int save_verbose)
 {
+  int other = OTHER_COLOR(color);
   int apos;
   int dpos;
   int aa_val;
+  char saved_defense_moves[BOARDMAX];
 
   /* Collect worm statuses of opponent's worms. We need to
    * know this because we only want to report unexpected
@@ -266,7 +263,9 @@
   compute_aa_status(color, NULL);
   compute_aa_values(color);
   
-  aa_val = do_atari_atari(color, &apos, &dpos, NO_MOVE,
+  if (defense_moves)
+    memset(defense_moves, 0, BOARDMAX);
+  aa_val = do_atari_atari(color, &apos, &dpos, defense_moves, NO_MOVE,
                          save_verbose, 0, NULL);
 
   if (aa_val == 0)
@@ -280,11 +279,13 @@
     
     if (attack_move)
       *attack_move = apos;
-    if (defense_move)
-      *defense_move = dpos;
     
     forbidden[apos] = 1;
-    new_aa_val = do_atari_atari(color, &apos, &dpos, NO_MOVE,
+    if (defense_moves) {
+      memcpy(saved_defense_moves, defense_moves, BOARDMAX);
+      memset(defense_moves, 0, BOARDMAX);
+    }
+    new_aa_val = do_atari_atari(color, &apos, &dpos, defense_moves, NO_MOVE,
                                save_verbose, aa_val, NULL);
 
     /* The last do_atari_atari call fails. When do_atari_atari fails,
@@ -292,15 +293,48 @@
      * to a move that works and is necessary.
      */
     if (new_aa_val == 0)
-      return aa_val;
+      break;
     else
       aa_val = new_aa_val;
   }
 
-  /* We'll never get here, but the compiler may be more happy if it
-   * looks like we're returning something.
-   */
-  return 0;
+  if (defense_moves) {
+    int pos;
+    memcpy(defense_moves, saved_defense_moves, BOARDMAX);
+    /* defense_moves[] contains potential defense moves. Now we
+     * examine which of them really work.
+     */
+    forbidden[apos] = 0;
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+      if (!ON_BOARD(pos) || !defense_moves[pos])
+       continue;
+
+      if (!trymove(pos, other, "atari_atari", NO_MOVE, EMPTY, NO_MOVE)) {
+       defense_moves[pos] = 0;
+       if (save_verbose)
+         gprintf("%1m deleted defense point, illegal\n", pos);
+       continue;
+      }
+
+      if (attack(pos, NULL)) {
+       defense_moves[pos] = 0;
+       popgo();
+       if (save_verbose)
+         gprintf("%1m deleted defense point, unsafe\n", pos);
+       continue;
+      }
+      
+      if (do_atari_atari(color, &apos, &dpos, NULL, NO_MOVE,
+                        save_verbose, aa_val, NULL) > 0) {
+       if (save_verbose)
+         gprintf("%1m deleted defense point, didn't work\n", pos);
+       defense_moves[pos] = 0;
+      }
+      
+      popgo();
+    }
+  }
+  return aa_val;
 }
 
 
@@ -356,7 +390,8 @@
     abortgo(__FILE__, __LINE__, "trymove", I(move), J(move));
   increase_depth_values();
 
-  aa_val = do_atari_atari(other, &apos, &defense_point, NO_MOVE, 0, 0, NULL);
+  aa_val = do_atari_atari(other, &apos, &defense_point, NULL,
+                         NO_MOVE, 0, 0, NULL);
   after_aa_val = aa_val;
 
   if (aa_val == 0 || defense_point == NO_MOVE) {
@@ -381,8 +416,8 @@
      */
     after_defense_point = defense_point;
     forbidden[apos] = 1;
-    aa_val = do_atari_atari(other, &apos, &defense_point, NO_MOVE, 0, aa_val,
-                           NULL);
+    aa_val = do_atari_atari(other, &apos, &defense_point, NULL,
+                           NO_MOVE, 0, aa_val, NULL);
   }
 
   popgo();
@@ -393,7 +428,7 @@
    */
   compute_aa_status(other, NULL);
   compute_aa_values(other);
-  aa_val = do_atari_atari(other, NULL, NULL, NO_MOVE, 0, 0, NULL);
+  aa_val = do_atari_atari(other, NULL, NULL, NULL, NO_MOVE, 0, 0, NULL);
   if (after_aa_val - aa_val > 0) {
     if (defense)
       *defense = after_defense_point;
@@ -554,8 +589,8 @@
 
 static int
 do_atari_atari(int color, int *attack_point, int *defense_point,
-              int last_friendly, int save_verbose, int minsize,
-              char goal[BOARDMAX])
+              char all_potential_defenses[BOARDMAX], int last_friendly,
+              int save_verbose, int minsize, char goal[BOARDMAX])
 {
   int other = OTHER_COLOR(color);
   int k;
@@ -625,7 +660,18 @@
     
     if (!trymove(apos, color, "do_atari_atari-A", str, EMPTY, NO_MOVE))
       continue;
-       
+    
+    if (all_potential_defenses) {
+      all_potential_defenses[apos] = 1;
+      if (countlib(apos) <= 2) {
+       int libs[2];
+       int num_libs = findlib(apos, 2, libs);
+       all_potential_defenses[libs[0]] = 1;
+       if (num_libs == 2)
+         all_potential_defenses[libs[1]] = 1;
+      }
+    }
+
     if (!IS_STONE(board[str])) {
       /* Error situation. This could be caused by a wrong matcher status. */
       if (save_verbose || (debug & DEBUG_ATARI_ATARI))
@@ -650,6 +696,9 @@
     for (r = 0; r < num_defense_moves; r++) {
       bpos = defense_moves[r];
 
+      if (all_potential_defenses)
+       all_potential_defenses[bpos] = 1;
+
       if (trymove(bpos, other, "do_atari_atari-B", str, EMPTY, NO_MOVE)) {
        int new_aa_val;
        char new_goal[BOARDMAX];
@@ -660,8 +709,8 @@
        modify_depth_values(2);
        update_aa_goal(goal, new_goal, apos, color);
        new_aa_val = do_atari_atari(color, NULL, defense_point,
-                                   apos, save_verbose, minsize,
-                                   new_goal);
+                                   all_potential_defenses,
+                                   apos, save_verbose, minsize, new_goal);
        modify_depth_values(-2);
        if (new_aa_val < aa_val)
          aa_val = new_aa_val;
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.126
diff -u -r1.126 liberty.h
--- engine/liberty.h    14 Oct 2002 15:41:07 -0000      1.126
+++ engine/liberty.h    19 Oct 2002 10:17:41 -0000
@@ -483,7 +483,7 @@
 void endgame_shapes(int color);
 
 void combinations(int color);
-int atari_atari(int color, int *attack_move, int *defense_move,
+int atari_atari(int color, int *attack_move, char defense_moves[BOARDMAX],
                int save_verbose);
 int atari_atari_confirm_safety(int color, int tpos, int *move, int minsize,
                               const char saved_dragons[BOARDMAX],
Index: engine/sgfdecide.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/sgfdecide.c,v
retrieving revision 1.41
diff -u -r1.41 sgfdecide.c
--- engine/sgfdecide.c  14 Oct 2002 15:41:07 -0000      1.41
+++ engine/sgfdecide.c  19 Oct 2002 10:17:53 -0000
@@ -572,8 +572,10 @@
 decide_combination(int color)
 {
   int attack_move;
-  int defense_move;
+  char defense_moves[BOARDMAX];
   SGFTree tree;
+  int first = 1;
+  int pos;
 
   /* Prepare pattern matcher and reading code. */
   reset_engine();
@@ -584,9 +586,20 @@
     sgffile_begindump(&tree);
   count_variations = 1;
 
-  if (atari_atari(color, &attack_move, &defense_move, verbose))
-    gprintf("Combination attack for %C at %1m, defense at %1m\n", color,
-           attack_move, defense_move);
+  if (atari_atari(color, &attack_move, defense_moves, verbose)) {
+    gprintf("Combination attack for %C at %1m, defense at ", color,
+           attack_move);
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+      if (ON_BOARD(pos) && defense_moves[pos]) {
+       if (first)
+         first = 0;
+       else
+         gprintf(", ");
+       gprintf("%1m", pos);
+      }
+    }
+    gprintf("\n");
+  }
   else
     gprintf("No Combination attack for %C\n", color);
   
Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.63
diff -u -r1.63 value_moves.c
--- engine/value_moves.c        14 Oct 2002 17:43:27 -0000      1.63
+++ engine/value_moves.c        19 Oct 2002 10:18:03 -0000
@@ -610,6 +610,7 @@
         * defending move is not connected to the dragon defended.
         */
       case MY_ATARI_ATARI_MOVE:
+      case YOUR_ATARI_ATARI_MOVE:
       case EITHER_MOVE:         /* FIXME: More advanced handling? */
       case ALL_MOVE:            /* FIXME: More advanced handling? */
        tactical_safety = 1;
Index: patterns/aa_attackpats.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/aa_attackpats.db,v
retrieving revision 1.5
diff -u -r1.5 aa_attackpats.db
--- patterns/aa_attackpats.db   4 Mar 2002 06:49:08 -0000       1.5
+++ patterns/aa_attackpats.db   19 Oct 2002 10:18:04 -0000
@@ -59,10 +59,6 @@
 #       pattern that threatens some other string.
 # 
 #########################################################
-#                                                       #
-#          Limiting moves on the fourth line            #
-#                                                       #
-#########################################################
 
 
 Pattern A1
@@ -220,6 +216,22 @@
 --
 
 ;lib(A)==3 && olib(*)>=3
+
+
+Pattern A14
+
+.X.
+X*X
+?O?
+
+:|,-
+
+.X.
+A*B
+?O?
+
+;safe_omove(*) && oplay_attack_either(*,A,B)
+;&& !oplay_connect(*,A,B)
 
 
 # END OF FILE