[gnugo-devel] set_depth_values() patch

[Arend Bayer]

I am not sure whether I succeeded in simplifying this function, but at
least this helped me understand what it is doing...

This patch doesn't change its behaviour (yet). The tuning seems to be
based (as I've added in the comments) on the assumptions that we have
two level policies outside of this function that have a strong
performance impact:
1. Levels 8 and higher we use owl threats
2. Levels 10 and higher we use superstring technology

No. 1 isn't true anymore, and no. 2 isn't expensive. Below are some
figures for strategy5.tst that show that there is almost no change in
used nodes between levels 7 and 8, and between levels 9 and 10.

On the other thand the jump from level 8 to 9 is extremely big; my guess is
that this is due to using the owl vital attack database only for levels
9 and higher. This makes it _a lot_ harder for a dragon to be declared
alive by owl, and hence the big jump in owl nodes in my opinion. It might
be worth to try and make this depth-dependant instead.
(So at least I learned _something_ useful from this :-) )

I will leave the actual changes to another patch another time (which
will then actually make that functions simpler...).

Arend


strateg5.tst:
10001: reading nodes
10001: owl nodes
10002: connection nodes

Oh btw, level 2 performed best with three PASSes and no FAILs...

Level 0
10000 1835974
10001 8578
10002 6561
Level 1
10000 2059799
10001 9106
10002 6177
Level 2
10000 2645960
10001 11768
10002 7461
Level 3
10000 3184442
10001 12811
10002 7508
Level 4
10000 4584235
10001 19186
10002 12978
Level 5
10000 5550046
10001 19650
10002 10754
Level 6
10000 7531857
10001 23678
10002 11985
Level 7
10000 10552458
10001 25301
10002 11841
Level 8
10000 10611472
10001 25621
10002 11841
Level 9
10000 18517555
10001 58962
10002 24297
Level 10
10000 19827612
10001 58905
10002 24230
Level 11
10000 27294153
10001 62742
10002 23267


Index: engine/dragon.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v
retrieving revision 1.76
diff -u -r1.76 dragon.c
--- engine/dragon.c     16 Sep 2002 08:30:28 -0000      1.76
+++ engine/dragon.c     18 Sep 2002 20:56:15 -0000
@@ -608,7 +608,7 @@
   time_report(2, "  compute dragon safety", NO_MOVE, 1.0);

   /* Resolve semeais. This may revise the safety and status fields. */
-  if (experimental_semeai && level > 7)
+  if (experimental_semeai && level >= 8)
     new_semeai(color);
   else
     semeai(color);
Index: engine/filllib.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/filllib.c,v
retrieving revision 1.24
diff -u -r1.24 filllib.c
--- engine/filllib.c    10 Sep 2002 20:17:27 -0000      1.24
+++ engine/filllib.c    18 Sep 2002 20:56:17 -0000
@@ -311,6 +311,8 @@
              *move = libs[0];
            else if (is_legal(libs[1], color))
              *move = libs[1];
+           else
+             continue;
            DEBUG(DEBUG_FILLLIB, "Filllib: Found at %1m.\n", *move);
            return 1;
          }
Index: engine/genmove.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/genmove.c,v
retrieving revision 1.49
diff -u -r1.49 genmove.c
--- engine/genmove.c    16 Sep 2002 08:26:41 -0000      1.49
+++ engine/genmove.c    18 Sep 2002 20:56:19 -0000
@@ -80,6 +80,7 @@
   /* Initialize things for hashing of positions. */
   reading_cache_clear();
   hashdata_recalc(&hashdata, board, board_ko_pos);
+
   worms_examined = -1;
   initial_influence_examined = -1;
   dragons_examined_without_owl = -1;
@@ -90,10 +91,7 @@
   /* Prepare our table of move reasons. */
   clear_move_reasons();

-  /* Set up depth values. Level 10 should be more or less the same as level 9
-   * except that the superstring technology is used in the reading code. This
-   * makes us about 10% slower.
-   */
+  /* Set up depth values (see comments there for details). */
   set_depth_values(level);
 }

Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.70
diff -u -r1.70 reading.c
--- engine/reading.c    11 Sep 2002 15:33:17 -0000      1.70
+++ engine/reading.c    18 Sep 2002 20:56:42 -0000
@@ -1352,7 +1352,7 @@
     }
   }

-  if (level >= 10 && stackp <= superstring_depth) {
+  if (stackp <= superstring_depth) {
     int dcode = superstring_breakchain(str, &xpos, komaster, kom_pos, 4);
     CHECK_RESULT_UNREVERSED(savecode, savemove, dcode, xpos, move,
                            "superstring_breakchain");
@@ -1363,7 +1363,7 @@
    * super_string.
    */
   saved_num_moves = moves.num;
-  if (level >= 10 && stackp <= superstring_depth) {
+  if (stackp <= superstring_depth) {
     int ss_liberties;
     int ss_libs[MAX_LIBERTIES + 4];

Index: engine/utils.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/utils.c,v
retrieving revision 1.51
diff -u -r1.51 utils.c
--- engine/utils.c      2 Sep 2002 14:19:22 -0000       1.51
+++ engine/utils.c      18 Sep 2002 20:56:48 -0000
@@ -562,91 +562,85 @@
 void
 set_depth_values(int level)
 {
-  static int node_limits[10] = {500, 450, 400, 325, 275,
-                               200, 150, 100, 75, 50};
-  if (level >= 10) {
-    depth               = gg_max(6, DEPTH - 10 + level);
-    ko_depth            = gg_max(1, KO_DEPTH - 10 + level);
-    backfill_depth      = gg_max(2, BACKFILL_DEPTH - 10 + level);
-    backfill2_depth     = gg_max(1, BACKFILL2_DEPTH - 10 + level);
-    superstring_depth   = gg_max(1, SUPERSTRING_DEPTH - 10 + level);
-    branch_depth        = gg_max(3, BRANCH_DEPTH - 10 + level);
-    fourlib_depth       = gg_max(1, FOURLIB_DEPTH - 10 + level);
-    aa_depth            = gg_max(0, AA_DEPTH - 10 + level);
-    aa_threat_depth     = gg_max(0, AA_THREAT_DEPTH - 10 + level);
-    owl_distrust_depth  = gg_max(1, OWL_DISTRUST_DEPTH - 5 + level/2);
-    owl_branch_depth    = gg_max(2, OWL_BRANCH_DEPTH - 5 + level/2);
-    owl_reading_depth   = gg_max(5, OWL_READING_DEPTH - 5 + level/2);
-    if (level == 10)
-      owl_node_limit    = OWL_NODE_LIMIT;
-    else
-      owl_node_limit    = OWL_NODE_LIMIT * pow(1.5, -10 + level);
-    urgent              = 0;
+  static int node_limits[] = {500, 500, 450, 400, 400, 325, 275,
+                             200, 150, 100, 75, 50};
+  int depth_level;
+
+  /*
+   * Other policies depending on level:
+   * aftermath.c:   >=  8: call estimate_score().
+   * dragon.c:      >=  8: compute owl threats (currently disabled) (*)
+   *                >=  8: call owl analysis of semeai (currently disabled)
+   * genmove.c:     >=  8: call estimate_score().
+   * owl.c:         >=  9: use vital attack pattern database
+   *                >= 10: increase depth values in owl_substantial
+   * reading.c:     >= 10: Use superstrings and do more backfilling. (*)
+   * value_moves.c: >=  6: try to find more owl attacks/defenses
+   *
+   * Those two marked (*) are particular expensive. Hence we don't change
+   * most depth values between levels 7 and 8 resp. 9 and 10.
+   * FIXME: This isn't correct for owl threats anymore.
+   *
+   * depth_level indicates the correction compared to the default settings
+   * at level 10 for most reading depths.
+   */
+  if (level >= 10)
+    depth_level = level - 10;
+  else if (level >= 8)
+    depth_level = level - 9;
+  else
+    depth_level = level - 8;
+
+  depth               = gg_max(6, DEPTH           + depth_level);
+  backfill_depth      = gg_max(2, BACKFILL_DEPTH  + depth_level);
+  backfill2_depth     = gg_max(1, BACKFILL2_DEPTH + depth_level);
+  branch_depth        = gg_max(3, BRANCH_DEPTH    + depth_level);
+  if (level >= 8)
+    owl_distrust_depth  = gg_max(1, (2 * OWL_DISTRUST_DEPTH + depth_level) / 
2);
+  else
+    owl_distrust_depth  = gg_max(1, (2*OWL_DISTRUST_DEPTH-1 + depth_level) / 
2);
+  owl_branch_depth    = gg_max(2, (2 * OWL_BRANCH_DEPTH   + depth_level) / 2);
+  owl_reading_depth   = gg_max(5, (2 * OWL_READING_DEPTH  + depth_level) / 2);
+  urgent              = 0;
+
+  /* Atari-atari depth levels are unchanged only between levels 7/8: */
+  if (level >= 8) {
+    aa_depth            = gg_max(0, AA_DEPTH        + (level - 10));
+    aa_threat_depth     = gg_max(0, AA_THREAT_DEPTH + (level - 10));
   }
-  else if (level > 7) {
-    depth               = gg_max(6, DEPTH - 9 + level);
-    ko_depth            = gg_max(1, KO_DEPTH - 9 + level);
-    backfill_depth      = gg_max(2, BACKFILL_DEPTH - 9 + level);
-    backfill2_depth     = gg_max(1, BACKFILL2_DEPTH - 9 + level);
-    superstring_depth   = 0 ;
-    branch_depth        = gg_max(3, BRANCH_DEPTH - 9 + level);
-    if (level < 9)
-      fourlib_depth     = gg_max(1, FOURLIB_DEPTH - 8 + level);
-    else
-      fourlib_depth     = gg_max(1, FOURLIB_DEPTH - 9 + level);
-    aa_depth            = gg_max(0, AA_DEPTH - 10 + level);
-    aa_threat_depth     = gg_max(0, AA_THREAT_DEPTH - 10 + level);
-    owl_distrust_depth  = gg_max(1, OWL_DISTRUST_DEPTH - 5
-                             + (level+1)/2);
-    owl_branch_depth    = gg_max(2, OWL_BRANCH_DEPTH - 5 + (level+1)/2);
-    owl_reading_depth   = gg_max(5, OWL_READING_DEPTH - 5 + (level+1)/2);
-    owl_node_limit      = (OWL_NODE_LIMIT * node_limits[9 - level] /
-                          node_limits[0]);
-    owl_node_limit      = gg_max(20, owl_node_limit);
-    urgent              = 0;
+  else {
+    aa_depth            = gg_max(0, AA_DEPTH        + (level - 9));
+    aa_threat_depth     = gg_max(0, AA_THREAT_DEPTH + (level - 9));
   }
-  else if (level == 7) {
-    depth               = gg_max(6, DEPTH - 1);
-    ko_depth            = gg_max(1, KO_DEPTH - 1);
-    backfill_depth      = gg_max(2, BACKFILL_DEPTH - 1);
-    backfill2_depth     = gg_max(1, BACKFILL2_DEPTH - 1);
-    superstring_depth   = 0 ;
-    branch_depth        = gg_max(3, BRANCH_DEPTH - 1);
-    if (level < 9)
-      fourlib_depth     = gg_max(1, FOURLIB_DEPTH);
-    else
-      fourlib_depth     = gg_max(1, FOURLIB_DEPTH - 1);
-    aa_depth            = gg_max(0, AA_DEPTH - 2);
-    aa_threat_depth     = gg_max(0, AA_THREAT_DEPTH - 2);
-    owl_distrust_depth  = gg_max(1, OWL_DISTRUST_DEPTH - 1);
-    owl_branch_depth    = gg_max(2, OWL_BRANCH_DEPTH - 5 + (level+1)/2);
-    owl_reading_depth   = gg_max(5, OWL_READING_DEPTH - 5 + (level+1)/2);
-    owl_node_limit      = (OWL_NODE_LIMIT * node_limits[9 - level] /
-                          node_limits[0]);
-    owl_node_limit      = gg_max(20, owl_node_limit);
-    urgent              = 0;
+
+  /* Exceptions:
+   * fourlib_depth: This is constant from levels 7 to 10.
+   * FIXME: ko_depth: jumps strangely at level 7.
+   * superstring_depth: set to 0 below level 10.
+   */
+  if (level >= 10)
+    ko_depth            = gg_max(1, KO_DEPTH + (level - 10));
+  else if (level != 7)
+    ko_depth            = gg_max(1, KO_DEPTH + (level - 9));
+  else /* level == 7 -- FIXME */
+    ko_depth            = gg_max(1, KO_DEPTH + (level - 8));
+
+  if (level >= 10)
+    fourlib_depth       = gg_max(1, FOURLIB_DEPTH + (level - 10));
+  else if (level >= 7)
+    fourlib_depth       = gg_max(1, FOURLIB_DEPTH);
+  else
+    fourlib_depth       = gg_max(1, FOURLIB_DEPTH + (level - 7));
+
+  if (level >= 10) {
+    superstring_depth   = gg_max(1, SUPERSTRING_DEPTH + (level - 10));
+    owl_node_limit      = OWL_NODE_LIMIT * pow(1.5, depth_level);
   }
-  else if (level < 7) {
-    depth               = gg_max(6, DEPTH - 8 + level);
-    ko_depth            = gg_max(1, KO_DEPTH - 9 + level);
-    backfill_depth      = gg_max(2, BACKFILL_DEPTH - 8 + level);
-    backfill2_depth     = gg_max(1, BACKFILL2_DEPTH - 8 + level);
-    superstring_depth   = 0 ;
-    branch_depth        = gg_max(3, BRANCH_DEPTH - 8 + level);
-    if (level < 9)
-      fourlib_depth     = gg_max(1, FOURLIB_DEPTH - 7 + level);
-    else
-      fourlib_depth     = gg_max(1, FOURLIB_DEPTH - 8 + level);
-    aa_depth            = gg_max(0, AA_DEPTH - 9 + level);
-    aa_threat_depth     = gg_max(0, AA_THREAT_DEPTH - 9 + level);
-    owl_distrust_depth  = gg_max(1, OWL_DISTRUST_DEPTH - 5
-                             + (level+1)/2);
-    owl_branch_depth    = gg_max(2, OWL_BRANCH_DEPTH - 4 + level/2);
-    owl_reading_depth   = gg_max(5, OWL_READING_DEPTH - 4 + level/2);
-    owl_node_limit      = (OWL_NODE_LIMIT * node_limits[8 - level] /
+  else {
+    superstring_depth   = 0;
+    owl_node_limit      = (OWL_NODE_LIMIT * node_limits[10 - level] /
                           node_limits[0]);
     owl_node_limit      = gg_max(20, owl_node_limit);
-    urgent              = 0;
   }


Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.53
diff -u -r1.53 value_moves.c
--- engine/value_moves.c        16 Sep 2002 07:27:49 -0000      1.53
+++ engine/value_moves.c        18 Sep 2002 20:57:00 -0000
@@ -1741,7 +1741,7 @@
    */
   this_value = 0.0;

-  if (move[pos].move_safety == 1 && safe_move(pos, color) == WIN)
+  if (move[pos].move_safety == 1 && safe_move(pos, color))
     saved_stones[pos] = INFLUENCE_SAVED_STONE;
   else
     saved_stones[pos] = INFLUENCE_CAPTURED_STONE;
@@ -2909,7 +2909,7 @@
   save_verbose = verbose;
   if (verbose > 0)
     verbose--;
-  if (level > 5) {
+  if (level >= 6) {
     find_more_owl_attack_and_defense_moves(color);
     time_report(2, "  find_more_owl_attack_and_defense_moves", NO_MOVE, 1.0);
   }