[gnugo-devel] semeai moves

[Arend Bayer]

In semeai_move_reasons(), if a move occupying a liberty wins a semeai,
we immediately test all comparable liberties whether they win the semeai,
too. This patch instead marks them as POTENTIAL_SEMEAI_ATTACK/DEFENSE,
and tests them later only if this move got a different move reason, too.
The rational is that if winning the semeai is the only move reason, there
is most likely no reason to prefer it to the original move.

It gives a small performance improvement overall, but a big one on a few
of the slowest moves in the regressions.

Arend

- new move reasons POTENTIAL_SEMEAI_ATTACK/DEFENSE to defer analysis of
  possible semeai winning moves until move valuation

Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.222
diff -u -p -r1.222 liberty.h
--- engine/liberty.h    21 Aug 2004 09:05:04 -0000      1.222
+++ engine/liberty.h    22 Aug 2004 20:50:14 -0000
@@ -369,6 +369,8 @@ void add_connection_move(int pos, int dr
 void add_cut_move(int pos, int dr1, int dr2);
 void add_antisuji_move(int pos);
 void add_semeai_move(int pos, int dr);
+void add_potential_semeai_attack(int pos, int dr1, int dr2);
+void add_potential_semeai_defense(int pos, int dr1, int dr2);
 void add_semeai_threat(int pos, int dr);
 
 void add_owl_attack_move(int pos, int dr, int kworm, int code);
Index: engine/move_reasons.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/move_reasons.c,v
retrieving revision 1.127
diff -u -p -r1.127 move_reasons.c
--- engine/move_reasons.c       25 May 2004 03:13:33 -0000      1.127
+++ engine/move_reasons.c       22 Aug 2004 20:50:15 -0000
@@ -44,6 +44,11 @@ int conn_worm1[MAX_CONNECTIONS];
 int conn_worm2[MAX_CONNECTIONS];
 int next_connection;
 
+/* Potential semeai moves. */
+int semeai_target1[MAX_POTENTIAL_SEMEAI];
+int semeai_target2[MAX_POTENTIAL_SEMEAI];
+static int next_semeai;
+
 /* Unordered sets (currently pairs) of move reasons / targets */
 Reason_set either_data[MAX_EITHER];
 int next_either;
@@ -89,6 +94,7 @@ clear_move_reasons(void)
   int k;
   next_reason = 0;
   next_connection = 0;
+  next_semeai = 0;
   next_either = 0;
   next_all = 0;
   next_eye = 0;
@@ -856,6 +862,46 @@ add_semeai_move(int pos, int dr)
 }
 
 /*
+ * Add to the reasons for the move at (pos) that it might
+ * kill/save the dragon at (dr1) in the semeai against (dr2).
+ */
+static void
+add_potential_semeai_move(int pos, int type, int dr1, int dr2)
+{
+  ASSERT1(ON_BOARD(dr1), pos);
+  ASSERT1(ON_BOARD(dr2), pos);
+  if (next_semeai >= MAX_POTENTIAL_SEMEAI)
+    DEBUG(DEBUG_MOVE_REASONS,
+         "Potential semeai move at %1m dropped as list was full\n", pos);
+  else {
+    semeai_target1[next_semeai] = dr1;
+    semeai_target2[next_semeai] = dr2;
+    add_move_reason(pos, type, next_semeai);
+    next_semeai++;
+  }
+}
+
+/*
+ * Add to the reasons for the move at (pos) that it might
+ * kill the dragon at (dr1) in the semeai against (dr2).
+ */
+void
+add_potential_semeai_attack(int pos, int dr1, int dr2)
+{
+  add_potential_semeai_move(pos, POTENTIAL_SEMEAI_ATTACK, dr1, dr2);
+}
+
+/*
+ * Add to the reasons for the move at (pos) that it might
+ * save the dragon at (dr1) in the semeai against (dr2).
+ */
+void
+add_potential_semeai_defense(int pos, int dr1, int dr2)
+{
+  add_potential_semeai_move(pos, POTENTIAL_SEMEAI_DEFENSE, dr1, dr2);
+}
+
+/*
  * Add to the reasons for the move at (pos) that given two
  * moves in a row a move here can win the dragon (friendly or
  * not) at (dr) in semeai. Such a move can be used as a 
Index: engine/move_reasons.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/move_reasons.h,v
retrieving revision 1.40
diff -u -p -r1.40 move_reasons.h
--- engine/move_reasons.h       10 Apr 2004 14:30:03 -0000      1.40
+++ engine/move_reasons.h       22 Aug 2004 20:50:15 -0000
@@ -39,7 +39,6 @@
 #define SEMEAI_MOVE             18
 #define SEMEAI_THREAT           (SEMEAI_MOVE | THREAT_BIT)
 
-/*      BLOCK_TERRITORY_MOVE    20   OBSOLETE */
 #define EXPAND_TERRITORY_MOVE   20
 #define EXPAND_MOYO_MOVE        22
 #define INVASION_MOVE           24
@@ -64,6 +63,8 @@
 
 #define OWL_ATTACK_MOVE_GAIN    60
 #define OWL_DEFEND_MOVE_LOSS    62
+#define POTENTIAL_SEMEAI_ATTACK        64
+#define POTENTIAL_SEMEAI_DEFENSE 66
 
 #define ANTISUJI_MOVE           70
 
@@ -136,6 +137,7 @@ struct move_data {
 #define MAX_WORMS              2*MAX_BOARD*MAX_BOARD/3
 #define MAX_DRAGONS            MAX_WORMS
 #define MAX_CONNECTIONS        4*MAX_WORMS
+#define MAX_POTENTIAL_SEMEAI   50
 #define MAX_EYES               MAX_BOARD*MAX_BOARD/2
 #define MAX_LUNCHES            MAX_WORMS
 #define MAX_EITHER             100
@@ -152,6 +154,9 @@ extern int conn_worm1[MAX_CONNECTIONS];
 extern int conn_worm2[MAX_CONNECTIONS];
 extern int next_connection;
 
+extern int semeai_target1[MAX_POTENTIAL_SEMEAI];
+extern int semeai_target2[MAX_POTENTIAL_SEMEAI];
+
 /* Unordered sets (currently pairs) of move reasons / targets */
 typedef struct {
   int reason1;
Index: engine/semeai.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/semeai.c,v
retrieving revision 1.71
diff -u -p -r1.71 semeai.c
--- engine/semeai.c     2 Jun 2004 02:53:26 -0000       1.71
+++ engine/semeai.c     22 Aug 2004 20:50:15 -0000
@@ -380,7 +380,6 @@ semeai_move_reasons(int color)
   int liberties;
   int libs[MAXLIBS];
   int r;
-  int resulta, resultb, semeai_move, s_result_certain;
 
   for (d = 0; d < number_of_dragons; d++)
     if (dragon2[d].semeais && DRAGON(d).status == CRITICAL) {
@@ -400,9 +399,8 @@ semeai_move_reasons(int color)
            && !is_self_atari(dragon2[d].semeai_defense_point, color)) {
          
          /* If this is a move to fill the non-common liberties of the
-          * target, and is not a ko or snap-back, then we try all
-          * non-common liberties of the target and add all winning
-          * moves to the move list.
+          * target, and is not a ko or snap-back, then we mark all
+          * non-common liberties of the target as potential semeai moves.
           */
 
           liberties = findlib(dragon2[d].semeai_defense_target, MAXLIBS, libs);
@@ -410,19 +408,9 @@ semeai_move_reasons(int color)
           for (r = 0; r < liberties; r++) {
             if (!neighbor_of_dragon(libs[r], dragon2[d].origin)
                && !is_self_atari(libs[r], color)
-               && libs[r] != dragon2[d].semeai_defense_point) {
-              owl_analyze_semeai_after_move(libs[r], color,
-                                           dragon2[d].semeai_defense_target,
-                                           dragon2[d].origin,
-                                           &resulta, &resultb, &semeai_move,
-                                           1, &s_result_certain, 0);
-              if (resulta == 0 && resultb == 0) {
-               add_semeai_move(libs[r], dragon2[d].origin);
-               DEBUG(DEBUG_SEMEAI,
-                     "Adding semeai defense move for %1m at %1m\n",
-                     DRAGON(d).origin, libs[r]);
-             }
-            }
+               && libs[r] != dragon2[d].semeai_defense_point)
+             add_potential_semeai_defense(libs[r], dragon2[d].origin,
+                                          dragon2[d].semeai_defense_target);
          }
        }
       }
@@ -447,18 +435,9 @@ semeai_move_reasons(int color)
           for (r = 0; r < liberties; r++) {
             if (!neighbor_of_dragon(libs[r], dragon2[d].semeai_attack_target)
                && !is_self_atari(libs[r], color)
-               && libs[r] != dragon2[d].semeai_attack_point) {
-              owl_analyze_semeai_after_move(libs[r], color, dragon2[d].origin,
-                                           dragon2[d].semeai_attack_target,
-                                           &resulta, &resultb, &semeai_move,
-                                           1, &s_result_certain, 0);
-              if (resulta == 0 && resultb == 0) {
-               add_semeai_move(libs[r], dragon2[d].origin);
-               DEBUG(DEBUG_SEMEAI,
-                     "Adding semeai attack move for %1m at %1m\n",
-                     DRAGON(d).origin, libs[r]);
-             }
-            }
+               && libs[r] != dragon2[d].semeai_attack_point)
+             add_potential_semeai_attack(libs[r], dragon2[d].origin,
+                                         dragon2[d].semeai_attack_target);
          }
        }
       }
Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.129
diff -u -p -r1.129 value_moves.c
--- engine/value_moves.c        3 Jun 2004 18:49:43 -0000       1.129
+++ engine/value_moves.c        22 Aug 2004 20:50:16 -0000
@@ -706,6 +706,89 @@ find_more_owl_attack_and_defense_moves(i
   verbose = save_verbose;
 }
 
+/* Tests whether the potential semeai move at (pos) with details given via
+ * (*reason) works, and adds a semeai move if applicable.
+ */
+static void
+try_potential_semeai_move(int pos, int color, struct move_reason *reason)
+{
+  int dr1 = semeai_target1[reason->what];
+  int dr2 = semeai_target2[reason->what];
+  int resulta, resultb, certain, old_certain;
+  ASSERT1(IS_STONE(board[dr1]), pos);
+  switch (reason->type) {
+    case POTENTIAL_SEMEAI_ATTACK:
+      owl_analyze_semeai_after_move(pos, color, dr1, dr2,
+                                   &resulta, &resultb, NULL,
+                                   1, &certain, 0);
+      old_certain = DRAGON2(dr1).semeai_attack_certain;
+      break;
+    case POTENTIAL_SEMEAI_DEFENSE:
+      old_certain = DRAGON2(dr1).semeai_defense_certain;
+      /* In this case other dragon gets to move first after forced move. */
+      owl_analyze_semeai_after_move(pos, color, dr2, dr1,
+                                   &resulta, &resultb, NULL,
+                                   1, &certain, 0);
+      break;
+    default:
+      ASSERT1(0, pos);
+  }
+  if (resulta == 0 && resultb == 0
+      && (certain || !old_certain)) {
+    add_semeai_move(pos, dr1);
+    DEBUG(DEBUG_SEMEAI,
+         "Potential semeai move at %1m for dragon at %1m is real\n",
+         pos, dr1);
+  }
+  else
+    DEBUG(DEBUG_MOVE_REASONS, "Potential semeai move at %1m for %1m 
discarded\n",
+         pos, dr1);
+}
+
+/* This functions tests all potential semeai attack moves whether they work,
+ * provided that there is at least one other move reasons stored for the
+ * relevant position.
+ */
+static void
+find_more_semeai_moves(int color)
+{
+  int pos;
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    int k, r;
+    int potential_semeai_move_found = 0;
+    int other_move_reason_found = 0;
+    if (!ON_BOARD1(pos))
+      continue;
+    for (k = 0; k < MAX_REASONS; k++) {
+      r = move[pos].reason[k];
+      if (r < 0)
+       break;
+      switch (move_reasons[r].type) {
+       case POTENTIAL_SEMEAI_ATTACK:
+       case POTENTIAL_SEMEAI_DEFENSE:
+          potential_semeai_move_found = 1;
+         break;
+       default:
+         other_move_reason_found = 1;
+      }
+    }
+    if ((r < 0 || k == MAX_REASONS)
+       && !other_move_reason_found)
+      continue;
+    if (!potential_semeai_move_found)
+      continue;
+
+    for (k = 0; k < MAX_REASONS; k++) {
+      int r = move[pos].reason[k];
+      if (r < 0)
+       break;
+      if (move_reasons[r].type == POTENTIAL_SEMEAI_ATTACK
+         || move_reasons[r].type == POTENTIAL_SEMEAI_DEFENSE)
+       try_potential_semeai_move(pos, color, &(move_reasons[r]));
+    }
+  }
+}
+
 
 /*
  * Any move that captures or defends a worm also potentially connects
@@ -3560,6 +3643,9 @@ review_move_reasons(int *the_move, float
     time_report(2, "  find_more_owl_attack_and_defense_moves", NO_MOVE, 1.0);
   }
 
+  find_more_semeai_moves(color);
+  time_report(2, "  find_more_semeai_moves", NO_MOVE, 1.0);
+
   save_verbose = verbose;
   if (verbose > 0)
     verbose--;