Re: [gnugo-devel] dragon amalgamation revisited

[Gunnar Farnebäck]

Nando wrote:
> Gunnar wrote:
> > The real point of simplifying the amalgamation code is that then we
> > can easily run amalgamation independently of anything else, and in
> > particular at stackp>0. This is also implemented by the patch in form
> > of the new function compute_new_dragons() in dragon.c. It is not
> > actually used anywhere yet but that will change in a later patch.
> 
> Sounds awfully good. Can't wait to see that next patch. :)

Ok, here it is. First the breakage:

blunder:27      PASS T2 [!R3]
blunder:32      PASS H4 [E3|H4]
blunder:33      PASS O19 [!H6|J1]
blunder:34      PASS F16 [!A19|C19]
blunder:35      PASS J3 [!G1]

32 and 34 are virtually identical and easy to solve by adding an extra
condition in detect_tactical_blunder(). Basically it is okay if a
tactically dead string which lives in seki also becomes tactically
critical or alive when outer liberties are filled. See the comment
about blunder:32,34 in the patch.

27, 33, and 35 are more interesting. What they have in common is that
tactical trouble is detected (an opponent string suddenly becomes
tactically defendable after the move) but neither owl reading nor
semeai reading can verify that the opponent string becomes
strategically viable. The reason why the semeai reading fails is that
the tactical trouble causes a part of a dragon to no longer be
connected to the rest of the dragon but the semeai reading does not
know this and thinks it is easily alive and therefore the opponent
string remains dead. So the solution is to modify the semeai code to
optionally (determined by an argument in the call) start by
recomputing dragons after a move. For example, in blunder:27 the move
white R3 is a blunder because it allows black to play T2 and
tactically defend T3. Previously the semeai reading would have
considered the single T3 stone against the entire O9 dragon, believing
white had simple independent life while black couldn't make a single
eye. After the patch it will only involve white R2 and S3 in the
semeai against T3, correctly finding a seki.

- new argument recompute_dragons to owl_analyze_semeai_after_move()
- owl_mark_dragon() and init_owl() revised
- detect_tactical_blunder() revised
- value of tactical blunders doubled to twice the effective size of
  the string
- not a blunder if a string which already is alive in seki becomes
  tactically safe when outer liberties are filled

We might want to use the recompute_dragons option also in other places
where owl_analyze_semeai_after_move() is called, but I haven't looked
into the performance or regression effects of that. I'm not planning
to do that anytime soon so if somebody else wants to try, feel free.

/Gunnar

Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.218
diff -u -r1.218 liberty.h
--- engine/liberty.h    31 May 2004 13:57:51 -0000      1.218
+++ engine/liberty.h    1 Jun 2004 03:24:05 -0000
@@ -494,7 +494,8 @@
 void owl_analyze_semeai_after_move(int move, int color, int apos, int bpos,
                                   int *resulta, int *resultb,
                                   int *semeai_move, int owl,
-                                  int *semeai_result_certain);
+                                  int *semeai_result_certain,
+                                  int recompute_dragons);
 
 void set_search_diamond(int pos);
 void reset_search_mask(void);
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.214
diff -u -r1.214 owl.c
--- engine/owl.c        31 May 2004 13:53:25 -0000      1.214
+++ engine/owl.c        1 Jun 2004 03:24:07 -0000
@@ -201,7 +201,8 @@
                                         int *vital_point,
                                         int is_attack_point);
 static void owl_mark_dragon(int apos, int bpos,
-                           struct local_owl_data *owl);
+                           struct local_owl_data *owl,
+                           int new_dragons[BOARDMAX]);
 static void owl_mark_worm(int apos, int bpos,
                          struct local_owl_data *owl);
 static void owl_mark_boundary(struct local_owl_data *owl);
@@ -260,7 +261,7 @@
 static void reduced_init_owl(struct local_owl_data **owl,
                             int at_bottom_of_stack);
 static void init_owl(struct local_owl_data **owl, int target1, int target2,
-                    int move, int use_stack);
+                    int move, int use_stack, int new_dragons[BOARDMAX]);
 
 static struct local_owl_data *owl_stack[2 * MAXSTACK];
 static int owl_stack_size = 0;
@@ -328,7 +329,7 @@
                   int *semeai_move, int owl, int *semeai_result_certain)
 {
   owl_analyze_semeai_after_move(PASS_MOVE, EMPTY, apos, bpos, resulta, resultb,
-                               semeai_move, owl, semeai_result_certain);
+                               semeai_move, owl, semeai_result_certain, 0);
 }
 
 /* Same as the function above with the addition that an arbitrary move
@@ -337,7 +338,8 @@
 void
 owl_analyze_semeai_after_move(int move, int color, int apos, int bpos,
                              int *resulta, int *resultb, int *semeai_move, 
-                             int owl, int *semeai_result_certain)
+                             int owl, int *semeai_result_certain,
+                             int recompute_dragons)
 {
   char ms[BOARDMAX];
   int w1, w2;
@@ -349,6 +351,7 @@
   int dummy_semeai_move;
   double start = 0.0;
   int reading_nodes_when_called = get_reading_node_counter();
+  int new_dragons[BOARDMAX];
   
   struct local_owl_data *owla;
   struct local_owl_data *owlb;
@@ -362,6 +365,16 @@
   
   if (debug & DEBUG_OWL_PERFORMANCE)
     start = gg_cputime();
+
+  if (recompute_dragons) {
+    if (tryko(move, color, "Recompute dragons for semeai.")) {
+      compute_new_dragons(new_dragons);
+      popgo();
+    }
+    else
+      recompute_dragons = 0;
+  }
+  
   
   /* Look for owl substantial worms of either dragon adjoining
    * the other dragon. Capturing such a worm wins the semeai.
@@ -441,8 +454,14 @@
          color, move, apos, bpos);
   
   if (owl) {
-    init_owl(&owla, apos, NO_MOVE, NO_MOVE, 1);
-    init_owl(&owlb, bpos, NO_MOVE, NO_MOVE, 0);
+    if (recompute_dragons) {
+      init_owl(&owla, apos, NO_MOVE, NO_MOVE, 1, new_dragons);
+      init_owl(&owlb, bpos, NO_MOVE, NO_MOVE, 0, new_dragons);
+    }
+    else {
+      init_owl(&owla, apos, NO_MOVE, NO_MOVE, 1, NULL);
+      init_owl(&owlb, bpos, NO_MOVE, NO_MOVE, 0, NULL);
+    }
     owl_make_domains(owla, owlb);
   }
   else {
@@ -1642,7 +1661,7 @@
     start = gg_cputime();
   
   TRACE("owl_attack %1m\n", target);
-  init_owl(&owl, target, NO_MOVE, NO_MOVE, 1);
+  init_owl(&owl, target, NO_MOVE, NO_MOVE, 1, NULL);
   owl_make_domains(owl, NULL);
   prepare_goal_list(target, owl, owl_goal_worm, &goal_worms_computed,
                    kworm, 1);
@@ -2159,7 +2178,7 @@
   
   gg_assert(stackp == 0);
   TRACE("owl_threaten_attack %1m\n", target);
-  init_owl(&owl, target, NO_MOVE, NO_MOVE, 1);
+  init_owl(&owl, target, NO_MOVE, NO_MOVE, 1, NULL);
   memcpy(saved_boundary, owl->boundary, sizeof(saved_boundary));
   owl_make_domains(owl, NULL);
   owl_shapes(&shape_patterns, moves, other, owl, &owl_attackpat_db);
@@ -2285,7 +2304,7 @@
     start = gg_cputime();
 
   TRACE("owl_defend %1m\n", target);
-  init_owl(&owl, target, NO_MOVE, NO_MOVE, 1);
+  init_owl(&owl, target, NO_MOVE, NO_MOVE, 1, NULL);
   owl_make_domains(owl, NULL);
   prepare_goal_list(target, owl, owl_goal_worm, &goal_worms_computed,
                    kworm, 1);
@@ -2680,7 +2699,7 @@
     start = gg_cputime();
 
   TRACE("owl_threaten_defense %1m\n", target);
-  init_owl(&owl, target, NO_MOVE, NO_MOVE, 1);
+  init_owl(&owl, target, NO_MOVE, NO_MOVE, 1, NULL);
   memcpy(saved_goal, owl->goal, sizeof(saved_goal));
   owl_make_domains(owl, NULL);
   owl_shapes(&shape_patterns, moves, color, owl, &owl_defendpat_db);
@@ -4237,33 +4256,47 @@
 }  
 
 
-/* Marks the dragons at (apos) and (bpos). If only one dragon
- * needs marking, (bpos) should be passed as (0). 
+/* Marks the dragons at apos and bpos. If only one dragon
+ * needs marking, bpos should be passed as NO_MOVE. 
  */
 
 static void
-owl_mark_dragon(int apos, int bpos, struct local_owl_data *owl)
+owl_mark_dragon(int apos, int bpos, struct local_owl_data *owl,
+               int new_dragons[BOARDMAX])
 {
   int pos;
   int color = board[apos];
   
   ASSERT1(bpos == NO_MOVE || board[bpos] == color, bpos);
 
-  for (pos = BOARDMIN; pos < BOARDMAX; pos++)
-    if (ON_BOARD(pos)) {
-      if (is_same_dragon(pos, apos) || is_same_dragon(pos, bpos))
-       owl->goal[pos] = 1;
-      else
-       owl->goal[pos] = 0;
-    }
+  if (new_dragons == NULL) {
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+      if (ON_BOARD(pos)) {
+       if (is_same_dragon(pos, apos) || is_same_dragon(pos, bpos))
+         owl->goal[pos] = 1;
+       else
+         owl->goal[pos] = 0;
+      }
+  }
+  else {
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+      if (ON_BOARD(pos)) {
+       if (IS_STONE(board[pos])
+           && (new_dragons[pos] == new_dragons[apos]
+               || new_dragons[pos] == new_dragons[bpos]))
+         owl->goal[pos] = 1;
+       else
+         owl->goal[pos] = 0;
+      }
+  }
 
   owl->color = color;
   owl_mark_boundary(owl);
 }
 
 
-/* Marks the worms at (apos) and (bpos). If only one worm
- * needs marking, (bpos) should be passed as (0). 
+/* Marks the worms at apos and bpos. If only one worm
+ * needs marking, bpos should be passed as NO_MOVE. 
  */
 
 static void
@@ -4528,7 +4561,7 @@
     if (verbose > 0)
       verbose--;
     owl_analyze_semeai_after_move(pos, color, dr, dr2, &semeai_result,
-                                 NULL, NULL, 1, &certain);
+                                 NULL, NULL, 1, &certain, 0);
     verbose = save_verbose;
     if (certain >= DRAGON2(dr).semeai_defense_certain
        && (semeai_result >= REVERSE_RESULT(acode))) {
@@ -4787,7 +4820,7 @@
      * FIXME: (move) will be added to the goal dragon although we
      * do not know whether it is really connected.
      */
-    init_owl(&owl, target, NO_MOVE, move, 1);
+    init_owl(&owl, target, NO_MOVE, move, 1, NULL);
     prepare_goal_list(target, owl, owl_goal_worm, &goal_worms_computed,
                      kworm, 0);
     acode = do_owl_attack(target, NULL, &wid, owl, 0);
@@ -4864,7 +4897,7 @@
        return 0;
     }
     
-    init_owl(&owl, target, NO_MOVE, move, 1);
+    init_owl(&owl, target, NO_MOVE, move, 1, NULL);
     prepare_goal_list(target, owl, owl_goal_worm, &goal_worms_computed,
                      kworm, 0);
     acode = do_owl_attack(target, &defense, &wid, owl, 0);
@@ -4938,7 +4971,7 @@
    * some stones of the goal dragon from the board.
    */
 #if 1
-  init_owl(&owl, target, NO_MOVE, NO_MOVE, 1);
+  init_owl(&owl, target, NO_MOVE, NO_MOVE, 1, NULL);
 #endif
 
   if (trymove(move, other, "owl_does_attack", target)) {
@@ -5023,7 +5056,7 @@
                                  target2, &result, NULL, NULL, NULL))
     return result;
 
-  init_owl(&owl, target1, target2, NO_MOVE, 1);
+  init_owl(&owl, target1, target2, NO_MOVE, 1, NULL);
 
   if (trymove(move, color, "owl_connection_defends", target1)) {
     owl_update_goal(move, 1, NO_MOVE, owl, 0);
@@ -6126,13 +6159,13 @@
  */
 static void
 init_owl(struct local_owl_data **owl, int target1, int target2, int move,
-         int at_bottom_of_stack)
+         int at_bottom_of_stack, int new_dragons[BOARDMAX])
 {
   reduced_init_owl(owl, at_bottom_of_stack);
 
   local_owl_node_counter = 0;
   (*owl)->lunches_are_current = 0;
-  owl_mark_dragon(target1, target2, *owl);
+  owl_mark_dragon(target1, target2, *owl, new_dragons);
   if (move != NO_MOVE)
     owl_update_goal(move, 1, NO_MOVE, *owl, 0);
   compute_owl_escape_values(*owl);
Index: engine/semeai.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/semeai.c,v
retrieving revision 1.70
diff -u -r1.70 semeai.c
--- engine/semeai.c     25 May 2004 03:13:46 -0000      1.70
+++ engine/semeai.c     1 Jun 2004 03:24:07 -0000
@@ -270,7 +270,7 @@
        continue;
 
       owl_analyze_semeai_after_move(defend_move, color, opponent, str,
-                                   &resulta, &resultb, NULL, 1, &certain);
+                                   &resulta, &resultb, NULL, 1, &certain, 0);
 
       /* Do not trust uncertain results. In fact it should only take a
        * few nodes to determine the semeai result, if it is a proper
@@ -292,7 +292,7 @@
         */
        owl_analyze_semeai_after_move(defend_move, OTHER_COLOR(color),
                                      str, opponent, &resulta, NULL,
-                                     NULL, 1, NULL);
+                                     NULL, 1, NULL, 0);
        if (resulta != WIN)
          dragon2[d].semeai_attack_point = defend_move;
        else {
@@ -303,7 +303,7 @@
          for (k = 0; k < liberties; k++) {
            owl_analyze_semeai_after_move(libs[k], OTHER_COLOR(color),
                                          str, opponent, &resulta, NULL,
-                                         NULL, 1, NULL);
+                                         NULL, 1, NULL, 0);
            if (resulta != WIN) {
              dragon2[d].semeai_attack_point = libs[k];
              break;
@@ -415,7 +415,7 @@
                                            dragon2[d].semeai_defense_target,
                                            dragon2[d].origin,
                                            &resulta, &resultb, &semeai_move,
-                                           1, &s_result_certain);
+                                           1, &s_result_certain, 0);
               if (resulta == 0 && resultb == 0) {
                add_semeai_move(libs[r], dragon2[d].origin);
                DEBUG(DEBUG_SEMEAI,
@@ -451,7 +451,7 @@
               owl_analyze_semeai_after_move(libs[r], color, dragon2[d].origin,
                                            dragon2[d].semeai_attack_target,
                                            &resulta, &resultb, &semeai_move,
-                                           1, &s_result_certain);
+                                           1, &s_result_certain, 0);
               if (resulta == 0 && resultb == 0) {
                add_semeai_move(libs[r], dragon2[d].origin);
                DEBUG(DEBUG_SEMEAI,
Index: engine/utils.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/utils.c,v
retrieving revision 1.94
diff -u -r1.94 utils.c
--- engine/utils.c      31 May 2004 13:57:51 -0000      1.94
+++ engine/utils.c      1 Jun 2004 03:24:08 -0000
@@ -1049,7 +1049,7 @@
          if (board[neighbor] == color)
            continue;
          owl_analyze_semeai_after_move(move, color, neighbor, bpos,
-                                       NULL, &resultb, NULL, 1, NULL);
+                                       NULL, &resultb, NULL, 1, NULL, 0);
          if (resultb == 0)
            acode = WIN;
        }
@@ -1107,7 +1107,7 @@
   int other = OTHER_COLOR(color);
   int pos;
   int ii;
-  int current_verbose = save_verbose;
+  int current_verbose = verbose;
 
   if (!trymove(move, color, NULL, NO_MOVE))
     return;
@@ -1157,30 +1157,38 @@
       decrease_depth_values();
       owl_attacks = owl_does_attack(move, pos, NULL);
       if (owl_attacks != WIN) {
-       *return_value += worm[pos].effective_size;
+       *return_value += 2 * worm[pos].effective_size;
        defense_effective = 1;
        verbose = save_verbose;
-       TRACE("After %1m worm at %1m becomes defendable.\n", move, pos);
+       TRACE("After %1m worm at %1m becomes defendable - A.\n", move, pos);
        verbose = current_verbose;
       }
-      else {
+      else if (dragon[pos].status != ALIVE) {
        /* Before redoing the trymove we also check whether the worm now
         * has a semeai defense. See blunder:26 for an example.
+        *
+        * If the worm already was alive in seki, it is generally okay
+        * that it also becomes tactically safe when the outer
+        * liberties are filled, see e.g. blunder:32,34. Thus the
+        * check above.
         */
        int k;
-       for (k = 0; k < DRAGON2(pos).neighbors; k++) {
-         int neighbor = dragon2[DRAGON2(pos).adjacent[k]].origin;
+       int adj[MAXCHAIN];
+       int num_adj;
+       num_adj = extended_chainlinks(pos, adj, 0);
+       for (k = 0; k < num_adj; k++) {
+         int neighbor = adj[k];
          int resulta;
-         if (board[neighbor] != color)
-           continue;
          owl_analyze_semeai_after_move(move, color, pos, neighbor,
-                                       &resulta, NULL, NULL, 1, NULL);
+                                       &resulta, NULL, NULL, 1, NULL, 1);
          if (resulta != 0) {
-           *return_value += worm[pos].effective_size;
+           *return_value += 2 * worm[pos].effective_size;
            defense_effective = 1;
            verbose = save_verbose;
-           TRACE("After %1m worm at %1m becomes defendable.\n", move, pos);
+           TRACE("After %1m worm at %1m becomes defendable - B.\n",
+                 move, pos);
            verbose = current_verbose;
+           break;
          }
        }
       }
Index: interface/play_gtp.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_gtp.c,v
retrieving revision 1.151
diff -u -r1.151 play_gtp.c
--- interface/play_gtp.c        31 May 2004 13:57:52 -0000      1.151
+++ interface/play_gtp.c        1 Jun 2004 03:24:10 -0000
@@ -1807,7 +1807,7 @@
 
   owl_analyze_semeai_after_move(move, color, dragona, dragonb,
                                &resulta, &resultb, &semeai_move, 1,
-                               &result_certain);
+                               &result_certain, 0);
   gtp_start_response(GTP_SUCCESS);
   gtp_print_code(resulta);
   gtp_printf(" ");