[gnugo-devel] Improved stabilisation in get_next_move_from_list

[Teun Burgers]

Arend wrote:

> Possible suggestions:
> 1. Make your patch dependent on some #define's.
> 2. Add the move > top_move test back as a fourth condition

The attached patch superceeds the previous ones and implements 1) and
2).
Also I introduced local vars bot_move, bot_value, bot_pattern and
bot_dist
to hopefully improve readability and reduce the number of calls to
bdist.

Teun

Index: owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.115
diff -u -r1.115 owl.c
--- owl.c       23 Oct 2002 18:32:35 -0000      1.115
+++ owl.c       25 Oct 2002 20:44:21 -0000
@@ -3004,6 +3004,24 @@
   matched_patterns->counter++;
 }
 
+#define USE_BDIST 0
+#if USE_BDIST
+
+/* compute the squared of the distance of a point on the board
+ * to the center of the board
+ */
+
+static int bdist(int move)
+{
+  /* i = 0:              idist = - (board_size - 1)
+     i = board_size -1 : idist =    board_size - 1
+     */
+  int idist = 2*I(move) - board_size + 1;
+  int jdist = 2*J(move) - board_size + 1;
+  return idist*idist + jdist*jdist;
+}
+#endif
+
 /* This function searches in the previously stored list of matched patterns
  * for the highest valued unused patterns that have a valid constraint.
  * It returns the moves at the next empty positions in the array (moves[]).
@@ -3047,26 +3065,61 @@
     float top_val = list->pattern_list[top].pattern->value;
     struct pattern *top_pattern = list->pattern_list[top].pattern;
     int top_move = list->pattern_list[top].move;
+#if USE_BDIST
+    int top_dist = bdist(list->pattern_list[top].move);
+#endif
 
     /* Maybe we already know the top entry (if previous call was ended
      * by a value cutoff.
      */
     if (top >= list->ordered_up_to) {
       /* One bubble sort iteration. */
-      for (bottom = list->counter-1; bottom > top; bottom--)
-       if (list->pattern_list[bottom].pattern->value > top_val
-           || (list->pattern_list[bottom].pattern->value == top_val
-               && list->pattern_list[bottom].pattern < top_pattern)
-           || (list->pattern_list[bottom].pattern->value == top_val
-               && list->pattern_list[bottom].pattern == top_pattern
-               && list->pattern_list[bottom].move < top_move)) {
+      for (bottom = list->counter-1; bottom > top; bottom--) {
+       float bot_val = list->pattern_list[bottom].pattern->value;
+       struct pattern *bot_pattern = NULL;
+       int bot_move = NO_MOVE;
+#if USE_BDIST
+       int bot_dist = 0;
+#endif
+       if (bot_val >= top_val) {
+         bot_pattern = list->pattern_list[bottom].pattern;
+         bot_move = list->pattern_list[bottom].move;
+#if USE_BDIST
+         bot_dist = bdist(list->pattern_list[bottom].move);
+#endif
+       }
+#if USE_BDIST
+        if (bot_val > top_val
+           || (bot_val == top_val
+               && bot_pattern < top_pattern)
+           || (bot_val == top_val
+               && bot_pattern == top_pattern
+               && bot_dist < top_dist)
+           || (bot_val == top_val
+               && bot_pattern == top_pattern
+               && bot_dist == top_dist
+              && bot_move < top_move)) {
+#else
+        if (bot_val > top_val
+           || (bot_val == top_val
+               && bot_pattern < top_pattern)
+           || (bot_val == top_val
+               && bot_pattern == top_pattern
+               && bot_move < top_move)) {
+#endif
+
          matched_pattern = list->pattern_list[bottom];
          list->pattern_list[bottom] = list->pattern_list[top];
          list->pattern_list[top] = matched_pattern;
-         top_val = list->pattern_list[top].pattern->value;
-         top_pattern = list->pattern_list[top].pattern;
-         top_move = list->pattern_list[top].move;
+
+         top_val = bot_val;
+          top_pattern = bot_pattern;
+          top_move = bot_move;
+#if USE_BDIST
+          top_dist = bot_dist;
+#endif
        }
+      }
       list->ordered_up_to++;
     }
     matched_pattern = list->pattern_list[top];