Re: Symmetry corrections (was: RE: [gnugo-devel] code maintenance pat ch)

[Gunnar Farneback]

Arend wrote:
> This explanation isn't 100% accurate. The matching order doesn't change
> (the DFA doesn't know about symmetries of patterns) in this case.

Huh? Somehow the matcher has to come up with a match for the pattern
at only one rotation instead of two. Why couldn't this affect the
matching order?

> I am pointing this out because I think I should change that. (I just
> looked at the function again and realized _how bad_ the algorithm is
> in this respect.) It is annoying when adding a new pattern to have to
> filter out the real change in owl results from this random noise. Changing
> this function a little could at least reduce the noise.

Something like this (untested) patch?

/Gunnar

Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.107
diff -u -r1.107 owl.c
--- engine/owl.c        26 Sep 2002 20:04:36 -0000      1.107
+++ engine/owl.c        3 Oct 2002 19:32:57 -0000
@@ -2870,6 +2870,11 @@
  * pattern; then it is checked whether this move has not been tried before,
  * and if the pattern constraint is valid. This is repeated until enough
  * moves are found or the end of the list is reached.
+ *
+ * When two patterns have the same value, the address of the pattern
+ * is used for a secondary comparison. This is entirely arbitrary but
+ * improves the stability of the sorting, giving more predictable
+ * results.
  */
 
 static int
@@ -2878,6 +2883,7 @@
 {
   int top, bottom;
   float top_val;
+  struct pattern *top_pattern;
   int k;
   int i;
   int move;
@@ -2897,14 +2903,18 @@
      * by a value cutoff.
      */
     top_val = list->pattern_list[top].pattern->value;
+    top_pattern = list->pattern_list[top].pattern;
     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) {
+       if (list->pattern_list[bottom].pattern->value > top_val
+           || (list->pattern_list[bottom].pattern->value == top_val
+               && list->pattern_list[bottom].pattern > top_pattern)) {
          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;
        }
       list->ordered_up_to++;
     }