Re: [gnugo-devel] Owl mistake and thrashing dragons.

[Gunnar Farneback]

I wrote:
> It would probably be better to have a boardsized array marking all
> thrashing stones rather than a single dragon pointer. If the last move
> played is part of a dead dragon which neighbors another dead dragon of
> the same color, it seems natural to mark both dragons as thrashing.

This patch implements that policy. It solves the test cases thrash:1
and thrash:2, but I believe it does so somewhat accidentally.
Primarily it's a preparation for further revisions.

- new static functions mark_dragon() and identify_thrashing_dragons()
  in dragon.c
- dead friendly neighbors of a thrashing dragon also considered thrashing
- new global array thrashing_stone[] to mark all thrashing dragons

/Gunnar

Index: engine/dragon.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v
retrieving revision 1.102
diff -u -r1.102 dragon.c
--- engine/dragon.c     13 Jan 2003 20:31:45 -0000      1.102
+++ engine/dragon.c     27 Jan 2003 21:20:14 -0000
@@ -56,6 +56,8 @@
 static void add_adjacent_dragon(int a, int b);
 static int dragon_invincible(int pos);
 static int dragon_looks_inessential(int origin);
+static void mark_dragon(int pos, char mx[BOARDMAX], char mark);
+static void identify_thrashing_dragons(void);
 static void analyze_false_eye_territory(void);
 static int connected_to_eye(int pos, int str, int color, int eye_color,
                            struct eye_data *eye);
@@ -97,12 +99,11 @@
  */
 
 void 
-make_dragons(int color, int stop_before_owl, int save_verbose)
+make_dragons(int color, int stop_before_owl)
 {
   int str;
   int dr;
   int d;
-  int last_move;
 
   start_timer(2);
   dragon2_initialized = 0;
@@ -469,22 +470,7 @@
       dragon[str] = dragon[dd->origin];
     }
 
-  /* If the opponent's last move is a dead dragon, this is
-   * called a *thrashing dragon*. We must be careful because
-   * the opponent may be trying to trick us, so even though
-   * GNU Go thinks the stone is dead, we should consider
-   * attacking it, particularly if we are ahead.
-   */
-
-  last_move = get_last_move();
-  if (last_move != NO_MOVE
-      && dragon[last_move].status == DEAD) {
-    thrashing_dragon = dragon[last_move].origin;
-    if (save_verbose)
-      gprintf("thrashing dragon found at %1m\n", thrashing_dragon);
-  }
-  else
-    thrashing_dragon = 0;
+  identify_thrashing_dragons();
 
   /* Owl threats. */
   for (str = BOARDMIN; str < BOARDMAX; str++)
@@ -509,8 +495,7 @@
        if (level >= 8
            && !disable_threat_computation
            && (owl_threats 
-               || (thrashing_dragon
-                   && is_same_dragon(str, thrashing_dragon)))) {
+               || thrashing_stone[str])) {
          if (acode && !dcode && dragon[str].owl_attack_point != NO_MOVE) {
            if (owl_threaten_defense(str, &defense_point,
                                     &second_defense_point)) {
@@ -1116,18 +1101,85 @@
 get_alive_stones(int color, char safe_stones[BOARDMAX])
 {
   int d;
-  int ii;
   get_lively_stones(color, safe_stones);
   for (d = 0; d < number_of_dragons; d++) {
     if (dragon2[d].safety == DEAD
        || (dragon2[d].safety == CRITICAL
            && board[dragon2[d].origin] == OTHER_COLOR(color))) {
-      for (ii = first_worm_in_dragon(dragon2[d].origin); ii != NO_MOVE;
-          ii = next_worm_in_dragon(ii))
-       mark_string(ii, safe_stones, 0);
+      mark_dragon(dragon2[d].origin, safe_stones, 0);
     }
   }
 }
+
+
+/* Mark the stones of a dragon. */
+static void
+mark_dragon(int pos, char mx[BOARDMAX], char mark)
+{
+  int w;
+  for (w = first_worm_in_dragon(dragon[pos].origin); w != NO_MOVE;
+       w = next_worm_in_dragon(w))
+    mark_string(w, mx, mark);
+}
+
+
+/* If the opponent's last move is a dead dragon, this is called a
+ * *thrashing dragon*. We must be careful because the opponent may be
+ * trying to trick us, so even though GNU Go thinks the stone is dead,
+ * we should consider attacking it, particularly if we are ahead.
+ *
+ * This function determines whether the last played move is part of a
+ * dead dragon. It also looks for dead friendly neighbors of the
+ * thrashing dragon, which are also considered as thrashing. The
+ * stones of the primary thrashing dragon are marked by 1 in the
+ * thrashing_stone[] array and its neighbors are marked by 2.
+ * Neighbors of neighbors are marked 3, and so on, up to at most
+ * distance 5.
+ */
+static void
+identify_thrashing_dragons()
+{
+  int k;
+  int dist;
+  int last_move;
+  int color;
+
+  thrashing_dragon = 0;
+  memset(thrashing_stone, 0, sizeof(thrashing_stone));
+
+  last_move = get_last_move();
+  if (last_move == NO_MOVE
+      || dragon[last_move].status != DEAD)
+    return;
+
+  thrashing_dragon = dragon[last_move].origin;
+  DEBUG(DEBUG_DRAGONS, "thrashing dragon found at %1m\n", thrashing_dragon);
+  mark_dragon(thrashing_dragon, thrashing_stone, 1);
+  color = board[thrashing_dragon];
+  
+  for (dist = 1; dist < 5; dist++) {
+    int pos;
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+      if (board[pos] != color
+         || dragon[pos].origin != pos
+         || thrashing_stone[pos] != dist)
+       continue;
+      
+      for (k = 0; k < DRAGON2(pos).neighbors; k++) {
+       int d = DRAGON2(pos).adjacent[k];
+       if (DRAGON(d).color == color
+           && DRAGON(d).status == DEAD
+           && thrashing_stone[dragon2[d].origin] == 0) {
+         DEBUG(DEBUG_DRAGONS,
+               "neighbor at distance %d of thrashing dragon found at %1m\n",
+               dist + 1, DRAGON(d).origin);
+         mark_dragon(DRAGON(d).origin, thrashing_stone, dist + 1);
+       }
+      }
+    }
+  }
+}
+
 
 static void
 set_dragon_strengths(const char safe_stones[BOARDMAX],
Index: engine/genmove.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/genmove.c,v
retrieving revision 1.64
diff -u -r1.64 genmove.c
--- engine/genmove.c    26 Jan 2003 10:30:08 -0000      1.64
+++ engine/genmove.c    27 Jan 2003 21:20:16 -0000
@@ -143,14 +143,14 @@
 
     if (how_much == EXAMINE_DRAGONS_WITHOUT_OWL) {
       if (NEEDS_UPDATE(dragons_examined_without_owl))
-       make_dragons(color, 1, save_verbose);
+       make_dragons(color, 1);
       verbose = save_verbose;
       gg_assert(test_gray_border() < 0);
       return;
     }
     
     if (NEEDS_UPDATE(dragons_examined)) {
-      make_dragons(color, 0, save_verbose);
+      make_dragons(color, 0);
       /* We have automatically done a partial dragon analysis as well. */
       dragons_examined_without_owl = position_number;
     }
@@ -672,22 +672,16 @@
       || (color == WHITE && score < advantage))
     return 0;
 
-  /* If an owl threat has been found, a move reason has
-   * probably been generated, so we skip this step. */
-  if (dragon[thrashing_dragon].owl_threat_status == CAN_THREATEN_DEFENSE)
-    return 0;
-
   if (disable_threat_computation
       || !thrashing_dragon 
       || dragon[thrashing_dragon].status != DEAD)
     return 0;
   
   for (pos = BOARDMIN; pos < BOARDMAX; pos++)
-    if (ON_BOARD(pos)
-       && is_same_dragon(pos, thrashing_dragon))
+    if (ON_BOARD(pos) && thrashing_stone[pos]) {
       dragon[pos].status = UNKNOWN;
-
-  DRAGON2(thrashing_dragon).safety = ALIVE;
+      DRAGON2(pos).safety = ALIVE;
+    }
 
   set_strength_data(OTHER_COLOR(color), safe_stones, strength);
   compute_influence(OTHER_COLOR(color), safe_stones, strength,
Index: engine/globals.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/globals.c,v
retrieving revision 1.40
diff -u -r1.40 globals.c
--- engine/globals.c    3 Jan 2003 18:23:42 -0000       1.40
+++ engine/globals.c    27 Jan 2003 21:20:16 -0000
@@ -48,7 +48,8 @@
 int          move_history_pos[MAX_MOVE_HISTORY];
 int          move_history_pointer;
 
-int thrashing_dragon = 0; /* Dead opponent's dragon trying to live */
+int thrashing_dragon = NO_MOVE; /* Dead opponent's dragon trying to live. */
+char thrashing_stone[BOARDMAX]; /* All thrashing stones. */
 
 float        komi;
 int          movenum;
Index: engine/gnugo.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/gnugo.h,v
retrieving revision 1.88
diff -u -r1.88 gnugo.h
--- engine/gnugo.h      4 Jan 2003 15:30:58 -0000       1.88
+++ engine/gnugo.h      27 Jan 2003 21:20:17 -0000
@@ -462,7 +462,7 @@
 void compute_worm_influence(void);
 
 /* dragon.c */
-void make_dragons(int color, int stop_before_owl, int save_verbose);
+void make_dragons(int color, int stop_before_owl);
 void initialize_dragon_data(void);
 void show_dragons(void);
 int crude_status(int pos);
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.154
diff -u -r1.154 liberty.h
--- engine/liberty.h    26 Jan 2003 10:30:08 -0000      1.154
+++ engine/liberty.h    27 Jan 2003 21:20:20 -0000
@@ -775,6 +775,7 @@
 extern int experimental_influence;   /* use experimental influence module */
 
 extern int thrashing_dragon; /* Dead opponent's dragon trying to live */
+extern char thrashing_stone[BOARDMAX]; /* All thrashing stones. */
 
 /* Experimental reading */
 extern char *rgoal;