[gnugo-devel] followup analysis

[Paul Pogonyshev]

- new global register_good_attack_threat() and is_known_good_attack_threat()

currently our policy for determining valid attacks threats in
estimate_territorial_value() has the following rule:

        /* No followup value if string can be defended with threat
         * against our move. An exception to this is when our move
         * isn't safe anyway and we play this only for the followup
         * value, typically as a ko threat.

this is of course better than assigning followups to every threat,
but not good enough. consider the position from trevord:950:

  .X...|
  .....|
  XX*XX|
  OO.XO|
  O.OOO|

because of the mentioned policy move at '*' is not given a followup.
the patch is intended to provide machinery for dealing with such
positions using patterns.

basically, it adds a new pseudo-function `good_attack_threat' which
can be used in patterns to force skipping of the above rule. i have
only added one pattern corresponding to the position from trevord:950.
more patterns can be added when more related problems are discovered.

the patch gives no regression changes. however, it does solve the
targeted problem: R9 is now given a proper followup, but gnu go still
values H2 0.04 points more (R9 is better, but there are no ways gnu
go can understand that now and besides H2 has large enough followup
itself to be good enough).

Paul


Index: engine/move_reasons.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/move_reasons.c,v
retrieving revision 1.112
diff -u -p -r1.112 move_reasons.c
--- engine/move_reasons.c       27 Mar 2003 10:33:11 -0000      1.112
+++ engine/move_reasons.c       2 May 2003 20:12:44 -0000
@@ -63,6 +63,10 @@ int next_lunch;
 /* Point redistribution */
 int replacement_map[BOARDMAX];
 
+/* Attack threats that are known to be sente locally. */
+static int known_good_attack_threats[BOARDMAX][MAX_ATTACK_THREATS];
+
+
 /* Helper functions to check conditions in discard rules. */
 typedef int (*discard_condition_fn_ptr)(int pos, int what);
 
@@ -123,6 +127,11 @@ clear_move_reasons(void)
       replacement_map[pos] = NO_MOVE;
     }
   }
+
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    for (k = 0; k < MAX_ATTACK_THREATS; k++)
+      known_good_attack_threats[pos][k] = NO_MOVE;
+  }
 }
 
 
@@ -1934,6 +1943,62 @@ scale_randomness(int pos, float scaling)
 {
   if (scaling > move[pos].randomness_scaling)
     move[pos].randomness_scaling = scaling;
+}
+
+
+/* Register the given `move' as a good attack threat against `target'. By
+ * "good" we mean a threat which is effectively a sente for the player.
+ * E.g. in this position the threat is good, because it results in four
+ * sente moves locally (trevord:950):
+ *
+ *  ..OX..
+ *  .O.*..
+ *  .OXX..
+ *  .OOX..
+ *  ------
+ *
+ * We use this list of good threats for performance reasons so that
+ * estimate_territorial_value() in valuemoves.c doesn't have to read
+ * through all the moves. Such threats are found with patterns.
+ */
+void
+register_good_attack_threat(int move, int target)
+{
+  int k;
+  ASSERT_ON_BOARD1(move);
+  ASSERT_ON_BOARD1(target);
+  ASSERT1(IS_STONE(worm[target].color), move);
+
+  target = worm[target].origin;
+  for (k = 0; k < MAX_ATTACK_THREATS; k++) {
+    if (known_good_attack_threats[move][k] == target)
+      break;
+    if (known_good_attack_threats[move][k] == NO_MOVE) {
+      known_good_attack_threats[move][k] = target;
+      break;
+    }
+  }
+}
+
+
+/* Determine if an attack threat is registered as good (see above). */
+int
+is_known_good_attack_threat(int move, int target)
+{
+  int k;
+  ASSERT_ON_BOARD1(move);
+  ASSERT_ON_BOARD1(target);
+  ASSERT1(IS_STONE(worm[target].color), move);
+
+  target = worm[target].origin;
+  for (k = 0; k < MAX_ATTACK_THREATS; k++) {
+    if (known_good_attack_threats[move][k] == target)
+      return 1;
+    if (known_good_attack_threats[move][k] == NO_MOVE)
+      break;
+  }
+
+  return 0;
 }
 
 
Index: engine/move_reasons.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/move_reasons.h,v
retrieving revision 1.32
diff -u -p -r1.32 move_reasons.h
--- engine/move_reasons.h       28 Jan 2003 12:12:19 -0000      1.32
+++ engine/move_reasons.h       2 May 2003 20:12:45 -0000
@@ -132,14 +132,15 @@ struct move_data {
  * FIXME: Many of these could be optimized more for size (e.g. MAX_EYES)
  */
 
-#define MAX_MOVE_REASONS  1000
-#define MAX_WORMS         2*MAX_BOARD*MAX_BOARD/3
-#define MAX_DRAGONS       MAX_WORMS
-#define MAX_CONNECTIONS   4*MAX_WORMS
-#define MAX_EYES          MAX_BOARD*MAX_BOARD/2
-#define MAX_LUNCHES       MAX_WORMS
-#define MAX_EITHER        100
-#define MAX_ALL           100
+#define MAX_MOVE_REASONS       1000
+#define MAX_WORMS              2*MAX_BOARD*MAX_BOARD/3
+#define MAX_DRAGONS            MAX_WORMS
+#define MAX_CONNECTIONS        4*MAX_WORMS
+#define MAX_EYES               MAX_BOARD*MAX_BOARD/2
+#define MAX_LUNCHES            MAX_WORMS
+#define MAX_EITHER             100
+#define MAX_ALL                100
+#define MAX_ATTACK_THREATS     6
 
 
 extern struct move_data move[BOARDMAX];
@@ -198,6 +199,9 @@ void mark_changed_dragon(int pos, int co
                         float strength[BOARDMAX], float *effective_size);
 void mark_changed_string(int affected, char changed_stones[BOARDMAX],
                         float strength[BOARDMAX], char new_status);
+
+void register_good_attack_threat(int move, int target);
+int is_known_good_attack_threat(int move, int target);
 
 /*
  * Local Variables:
Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.89
diff -u -p -r1.89 value_moves.c
--- engine/value_moves.c        28 Apr 2003 17:45:04 -0000      1.89
+++ engine/value_moves.c        2 May 2003 20:12:53 -0000
@@ -1553,10 +1553,14 @@ estimate_territorial_value(int pos, int 
          * isn't safe anyway and we play this only for the followup
          * value, typically as a ko threat.
         *
+        * This rule may be overwritten with patterns. See pattern
+        * Sente22 and related test trevord:950 for an example.
+        *
         * FIXME: This is somewhat halfhearted since only one defense
         * move is tested.
         */
-       if (board[aa] != EMPTY
+       if (!is_known_good_attack_threat(pos, aa)
+           && board[aa] != EMPTY
            && (move[pos].move_safety == 1
                || adjacent_to_nondead_stone(pos, color))
            && find_defense(aa, &defense_move) == WIN
Index: patterns/mkpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkpat.c,v
retrieving revision 1.118
diff -u -p -r1.118 mkpat.c
--- patterns/mkpat.c    27 Mar 2003 10:33:13 -0000      1.118
+++ patterns/mkpat.c    2 May 2003 20:13:03 -0000
@@ -364,7 +364,8 @@ static struct autohelper_func autohelper
   {"oracle_threatens",         2, 0, 0.01, "oracle_threatens(%s, %s)"},
   {"value",                    0, 2, 0.0,  "(%s->value)"},
   {"adjacent_to_defendable_stone_in_atari", 1, 0, 1.0,
-                "adjacent_to_defendable_stone_in_atari(%s)"}
+                "adjacent_to_defendable_stone_in_atari(%s)"},
+  {"good_attack_threat",       2, 0, 0.01, "register_good_attack_threat(%s, 
%s)"}
 };
 
 
Index: patterns/patterns2.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/patterns2.db,v
retrieving revision 1.57
diff -u -p -r1.57 patterns2.db
--- patterns/patterns2.db       16 Apr 2003 22:03:43 -0000      1.57
+++ patterns/patterns2.db       2 May 2003 20:13:07 -0000
@@ -3151,6 +3151,24 @@ ba*
 ;oterri(b) && oterri(c) && oterri(d) && safe_xmove(*) && !xplay_attack(*,a,*)
 
 
+Pattern Sente22
+# pp New pattern, see trevord:950 (3.3.20)
+
+?OX?
+O.*.
+?XX?
+
+:8,OX
+
+?OX?
+Oa*b
+?AA?
+
+; oplay_attack(*,A) && oplay_attack(*,a,A) && oplay_attack(*,b,a,A)
+
+> good_attack_threat(*,A)
+
+
 ########################################################
 #
 # Double threat moves and defense against double threats