[gnugo-devel] comments & shortest transformations

[Paul Pogonyshev]

this patch does some followup cleaning after my recent patches.

- comments added to declarations of corner_* structures in patterns.h
- dfa optimizer now chooses the shortest transformation if it doesn't
  have a hint from a previous optimization

Arend's idea about choosing the shortest transformation strings first
proved useful. in fact the optimizer itself seems to do better with
such initial data. maybe local minimums which are close to the
"shortest strings point" are usually "deeper" than most other local
minimums. when we update .dtr files next time we should probably do
that from scratch. it allows to squeeze another 1000 states out from
owl_attackpats.db for instance (down to a bit more than 7000 states).

btw, while i was writing dfa optimizer, i noticed that my
scan_for_patterns() speedup patch broke matching with pre-rotated dfas.
however, i seriously doubt we'll ever use that option. recently Evan
built (in something like half an hour) a pre-rotated dfa for
owl_attackpats.db. it contained about 3.8 million states. even non-
optimized dfa contains less than 25 thousand states, and optimized -
about 8 thousand only. do we really need to keep the ability to
build pre-rotated dfas?

Paul


Index: patterns.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/patterns.h,v
retrieving revision 1.50
diff -u -p -r1.50 patterns.h
--- patterns.h  3 Feb 2003 23:33:05 -0000       1.50
+++ patterns.h  8 Feb 2003 17:30:19 -0000
@@ -380,35 +380,37 @@ struct corner_variation;
 struct corner_pattern;
 
 struct corner_db {
-  int max_width;
-  int max_height;
+  int max_width;       /* Largest possible width and... */
+  int max_height;      /* ... largest possible height of database patterns. */
 
-  char num_top_variations;
+  char num_top_variations; /* Number of top level variations. */
   struct corner_variation *top_variations;
 };
 
 struct corner_variation {
-  int move_offset;
-  char xor_att;
-  char num_stones;
+  int move_offset;     /* Offset of the move in this variation. */
+  char xor_att;        /* 0 - the same color as the first matched stone,
+                        * 3 - the opposite color.
+                        */
+  char num_stones;      /* Number of stones in the `move_offset' rectangle. */
 
-  char num_variations;
-  struct corner_variation *variations;
+  char num_variations;  /* Number of subvariations. */
+  struct corner_variation *variations; /* Pointer to subvariation array. */
 
-  struct corner_pattern *pattern;
+  struct corner_pattern *pattern; /* Address of matched pattern (if any). */
 };
 
 struct corner_pattern {
-  int second_corner_offset;
-  int symmetric;
+  int second_corner_offset; /* Offset of pattern's second corner. */
+  int symmetric;       /* If the pattern is symmetric ('/' symmetry). */
 
-  unsigned int class;
-  const char *name;
+  unsigned int class;  /* Pattern class. */
+  const char *name;    /* Pattern name (optional). */
 
-  float shape;
+  float shape;         /* Pattern shape value. */
 
-  int autohelper_flag;
-  autohelper_fn_ptr autohelper;
+  int autohelper_flag; /* Whether autohelper has constraint and/or action. */
+  autohelper_fn_ptr autohelper; /* Automatically generated helper (or NULL). */
 };
 
 /* Build time version of corner_variation structure. */
Index: dfa.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa.c,v
retrieving revision 1.28
diff -u -p -r1.28 dfa.c
--- dfa.c       8 Feb 2003 15:20:28 -0000       1.28
+++ dfa.c       8 Feb 2003 20:48:01 -0000
@@ -1822,6 +1822,30 @@ dfa_patterns_set_last_pattern_variation(
 }
 
 
+/* Make the shortest variation of the last pattern its current variation. It
+ * is used as a starting point in dfa optimization process.
+ */
+void
+dfa_patterns_select_shortest_variation(dfa_patterns *patterns)
+{
+  int k;
+  int min_length;
+  dfa_pattern *pattern = patterns->last_pattern;
+  assert(pattern);
+
+  pattern->current_variation = 0;
+  min_length = strlen(pattern->variation[0]);
+  for (k = 1; k < pattern->num_variations; k++) {
+    int length = strlen(pattern->variation[k]);
+
+    if (length < min_length) {
+      pattern->current_variation = k;
+      min_length = length;
+    }
+  }
+}
+
+
 /* Build a dfa graph for a list of patterns. */
 void
 dfa_patterns_build_graph(dfa_patterns *patterns)
Index: dfa.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa.h,v
retrieving revision 1.22
diff -u -p -r1.22 dfa.h
--- dfa.h       8 Feb 2003 15:20:28 -0000       1.22
+++ dfa.h       8 Feb 2003 20:48:36 -0000
@@ -282,6 +282,7 @@ void                dfa_patterns_add_pattern(dfa_patte
                                         const char *string, int index);
 void           dfa_patterns_set_last_pattern_variation(dfa_patterns *patterns,
                                                        int variation);
+void           dfa_patterns_select_shortest_variation(dfa_patterns *patterns);
 void           dfa_patterns_build_graph(dfa_patterns *patterns);
 int *          dfa_patterns_optimize_variations(dfa_patterns *patterns,
                                                 int iterations);
Index: mkpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkpat.c,v
retrieving revision 1.113
diff -u -p -r1.113 mkpat.c
--- mkpat.c     8 Feb 2003 15:20:28 -0000       1.113
+++ mkpat.c     8 Feb 2003 20:51:31 -0000
@@ -612,7 +612,9 @@ write_to_dfa(int index)
   }
 
   if (database_type == OPTIMIZE_DFA) {
-    if (pattern[index].trfno != 5)
+    if (transformation_hint == -1)
+      dfa_patterns_select_shortest_variation(&dfa_pats);
+    else if (pattern[index].trfno != 5)
       dfa_patterns_set_last_pattern_variation(&dfa_pats, transformation_hint);
     else
       dfa_patterns_set_last_pattern_variation(&dfa_pats, transformation_hint - 
2);
@@ -2998,6 +3000,10 @@ main(int argc, char *argv[])
            command_data[79] = 0;
          }
          strcpy(pattern_names[patno], command_data);
+
+         /* Special case. Choose shortest transformation later. */
+         if (database_type == OPTIMIZE_DFA)
+           transformation_hint = -1;
 
          if (transformations_FILE) {
            if (!have_pending_name && !feof(transformations_FILE)) {