[gnugo-devel] patterns maintenance patch

[Paul Pogonyshev]

- make `mkpat' detect duplicate pattern names
- reduce DFA_MAX_MATCHED 20 times and calculate actual maximum
  with new function dfa_calculate_max_matched_patterns()

I noticed that the DFA optimizer gives inconsistent results sometimes.
It can reduce DFA to (say) 10000 states, but when restarted it begins
with some 10100 states instead.  I managed to track the bug down---
this is all because of duplicate pattern names.  The transformation
hint files (.dtr) specify suggested transformations reffering to
patterns by names, so obviously weird things happen when the names
conflict.

This patch adds a checkpoint to `mkpat' which prints warnings when
two or more patterns in the same file have identical names.  It also
renames a few patterns in `owl_defendpats.db' and `patterns.db' to
resolve existing name conflicts.  File `patterns.db' doesn't really
matter since it doesn't use transformation hints, but I think it's
generally a good idea to keep pattern names unique.

The second change is a possible speed optimization.  Currently,
do_dfa_matchpat() allocates 16 KB stack chunk for storing matched
pattern indices.  This is way more than enough and might reduce memory
caching efficiency.  I added a new function which calculates the
actual maximum for each DFA and reduced DFA_MAX_MATCHED from (8 * 500)
to (8 * 24).  Actually (8 * 15) is enough with current databases.  I
haven't verified if this really improves anything, but the change is
simple anyway.

Finally, this patch includes some changes to `patterns/Makefile.am'.
Firstly, I renamed hoshi joseki patterns from "JH???" to "JHK???" and
"JHO???" for the corresponding files.  Otherwise we have name conflicts
between `hoshi_keima.db' and `hoshi_other.db'.  Secondly, I replaced
all redirections (`<', `>' and `cat') with `mkpat's `-i' and `-o'
options.  This way we get more informative warnings, like

  patterns.db(10981) : Warning : duplicate pattern name `ED96'

instead of

  <stdin>(10981) : Warning : duplicate pattern name `ED96'


Paul



Index: patterns/Makefile.am
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/Makefile.am,v
retrieving revision 1.24
diff -u -p -r1.24 Makefile.am
--- patterns/Makefile.am        4 Nov 2003 21:59:44 -0000       1.24
+++ patterns/Makefile.am        28 May 2004 12:28:15 -0000
@@ -73,6 +73,9 @@ GGBUILTSOURCES = conn.c patterns.c apatt
 DBBUILT = hoshi_keima.db hoshi_other.db komoku.db sansan.db \
          mokuhazushi.db takamoku.db
 
+DBBUILT_INPUT = -i hoshi_keima.db -i hoshi_other.db -i komoku.db \
+               -i sansan.db -i mokuhazushi.db -i takamoku.db
+
 DB_TO_TAG = aa_attackpats.db attack.db barriers.db conn.db defense.db\
            endgame.db eyes.db fuseki.db fuseki9.db fuseki13.db fuseki19.db\
            handicap.db influence.db oracle.db owl_attackpats.db\
@@ -93,10 +96,10 @@ noinst_LIBRARIES = libpatterns.a
 libpatterns_a_SOURCES = connections.c helpers.c transform.c $(GGBUILTSOURCES)
 
 hoshi_keima.db : $(srcdir)/hoshi_keima.sgf joseki$(EXEEXT)
-       ./joseki JH $(srcdir)/hoshi_keima.sgf >hoshi_keima.db
+       ./joseki JHK $(srcdir)/hoshi_keima.sgf >hoshi_keima.db
 
 hoshi_other.db : $(srcdir)/hoshi_other.sgf joseki$(EXEEXT)
-       ./joseki JH $(srcdir)/hoshi_other.sgf >hoshi_other.db
+       ./joseki JHO $(srcdir)/hoshi_other.sgf >hoshi_other.db
 
 komoku.db : $(srcdir)/komoku.sgf joseki$(EXEEXT)
        ./joseki JK $(srcdir)/komoku.sgf >komoku.db
@@ -111,72 +114,72 @@ takamoku.db : $(srcdir)/takamoku.sgf jos
        ./joseki JT $(srcdir)/takamoku.sgf >takamoku.db
 
 patterns.c : $(srcdir)/patterns.db $(srcdir)/patterns2.db mkpat$(EXEEXT)
-       cat  $(srcdir)/patterns.db $(srcdir)/patterns2.db \
-               | ./mkpat -b pat >patterns.c
+       ./mkpat -b pat -i $(srcdir)/patterns.db -i$(srcdir)/patterns2.db \
+               -o patterns.c
 
 josekidb.c : $(DBBUILT) mkpat$(EXEEXT)
-       cat  $(DBBUILT) | ./mkpat -C joseki >josekidb.c
+       ./mkpat -C joseki $(DBBUILT_INPUT) -o josekidb.c
 
 apatterns.c : $(srcdir)/attack.db mkpat$(EXEEXT)
-       cat $(srcdir)/attack.db | ./mkpat -X attpat >apatterns.c
+       ./mkpat -X attpat -i $(srcdir)/attack.db -o apatterns.c
 
 dpatterns.c : $(srcdir)/defense.db mkpat$(EXEEXT)
-       cat $(srcdir)/defense.db | ./mkpat defpat >dpatterns.c
+       ./mkpat defpat -i $(srcdir)/defense.db -o dpatterns.c
 
 conn.c : $(srcdir)/conn.db mkpat$(EXEEXT)
-       ./mkpat -c conn < $(srcdir)/conn.db >conn.c
+       ./mkpat -c conn -i $(srcdir)/conn.db -o conn.c
 
 endgame.c : $(srcdir)/endgame.db mkpat$(EXEEXT)
-       cat $(srcdir)/endgame.db | ./mkpat -b endpat >endgame.c
+       ./mkpat -b endpat -i $(srcdir)/endgame.db -o endgame.c
 
 eyes.c: $(srcdir)/eyes.db mkeyes$(EXEEXT)
        ./mkeyes < $(srcdir)/eyes.db >eyes.c
 
 influence.c : $(srcdir)/influence.db mkpat$(EXEEXT)
-       ./mkpat -c influencepat < $(srcdir)/influence.db >influence.c
+       ./mkpat -c influencepat -i $(srcdir)/influence.db -o influence.c
 
 barriers.c : $(srcdir)/barriers.db mkpat$(EXEEXT)
-       ./mkpat -c -b barrierspat < $(srcdir)/barriers.db >barriers.c
+       ./mkpat -c -b barrierspat -i $(srcdir)/barriers.db -o barriers.c
 
 aa_attackpat.c : $(srcdir)/aa_attackpats.db $(srcdir)/aa_attackpats.dtr 
mkpat$(EXEEXT)
        ./mkpat $(DFAFLAGS) -b -t $(srcdir)/aa_attackpats.dtr aa_attackpat \
-               < $(srcdir)/aa_attackpats.db >aa_attackpat.c
+               -i $(srcdir)/aa_attackpats.db -o aa_attackpat.c
 
 owl_attackpat.c : $(srcdir)/owl_attackpats.db $(srcdir)/owl_attackpats.dtr 
mkpat$(EXEEXT)
        ./mkpat $(DFAFLAGS) -b -t $(srcdir)/owl_attackpats.dtr owl_attackpat \
-               < $(srcdir)/owl_attackpats.db >owl_attackpat.c
+               -i $(srcdir)/owl_attackpats.db -o owl_attackpat.c
 
 oraclepat.c : $(srcdir)/oracle.db mkpat$(EXEEXT)
-       ./mkpat -b oracle < $(srcdir)/oracle.db >oraclepat.c
+       ./mkpat -b oracle -i $(srcdir)/oracle.db -o oraclepat.c
 
 owl_vital_apat.c : $(srcdir)/owl_vital_apats.db $(srcdir)/owl_vital_apats.dtr 
mkpat$(EXEEXT)
        ./mkpat $(DFAFLAGS) -b -t $(srcdir)/owl_vital_apats.dtr owl_vital_apat \
-               < $(srcdir)/owl_vital_apats.db >owl_vital_apat.c
+               -i $(srcdir)/owl_vital_apats.db -o owl_vital_apat.c
 
 owl_defendpat.c : $(srcdir)/owl_defendpats.db $(srcdir)/owl_defendpats.dtr 
mkpat$(EXEEXT)
        ./mkpat $(DFAFLAGS) -b -t $(srcdir)/owl_defendpats.dtr owl_defendpat \
-               < $(srcdir)/owl_defendpats.db >owl_defendpat.c
+               -i $(srcdir)/owl_defendpats.db -o owl_defendpat.c
 
 fusekipat.c : $(srcdir)/fuseki.db mkpat$(EXEEXT)
-       ./mkpat -b fusekipat < $(srcdir)/fuseki.db >fusekipat.c
+       ./mkpat -b fusekipat -i $(srcdir)/fuseki.db -o fusekipat.c
 
 fuseki9.c : $(srcdir)/fuseki9.db mkpat$(EXEEXT)
-       ./mkpat -b -f fuseki9 < $(srcdir)/fuseki9.db >fuseki9.c
+       ./mkpat -b -f fuseki9 -i $(srcdir)/fuseki9.db -o fuseki9.c
 
 fuseki13.c : $(srcdir)/fuseki13.db mkpat$(EXEEXT)
-       ./mkpat -b -f fuseki13 < $(srcdir)/fuseki13.db >fuseki13.c
+       ./mkpat -b -f fuseki13 -i $(srcdir)/fuseki13.db -o fuseki13.c
 
 fuseki19.c : $(srcdir)/fuseki19.db mkpat$(EXEEXT)
-       ./mkpat -b -f fuseki19 < $(srcdir)/fuseki19.db >fuseki19.c
+       ./mkpat -b -f fuseki19 -i $(srcdir)/fuseki19.db -o fuseki19.c
 
 handipat.c : $(srcdir)/handicap.db mkpat$(EXEEXT)
-       ./mkpat -b handipat < $(srcdir)/handicap.db >handipat.c
+       ./mkpat -b handipat -i $(srcdir)/handicap.db -o handipat.c
 
 read_attack.c : $(srcdir)/read_attack.db mkpat$(EXEEXT)
-       ./mkpat -b read_attack < $(srcdir)/read_attack.db >read_attack.c
+       ./mkpat -b read_attack -i $(srcdir)/read_attack.db -o read_attack.c
 
 read_defend.c : $(srcdir)/read_defend.db mkpat$(EXEEXT)
-       ./mkpat -b read_defend < $(srcdir)/read_defend.db >read_defend.c
+       ./mkpat -b read_defend -i $(srcdir)/read_defend.db -o read_defend.c
 
 
 ETAGS_ARGS = --language none --regex '/^Pattern[ \t]+[a-zA-Z0-9]+/' 
$(DB_TO_TAG)\
Index: patterns/dfa-mkpat.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa-mkpat.h,v
retrieving revision 1.2
diff -u -p -r1.2 dfa-mkpat.h
--- patterns/dfa-mkpat.h        24 Jan 2004 04:04:56 -0000      1.2
+++ patterns/dfa-mkpat.h        28 May 2004 12:28:15 -0000
@@ -95,6 +95,7 @@ void save_dfa(const char *f_name, dfa_t 
 dfa_t *load_dfa(const char *f_path, const char *f_name, dfa_t **ppdfa);
 void dfa_finalize(dfa_t *pdfa);
 void dfa_shuffle(dfa_t *pdfa);
+int dfa_calculate_max_matched_patterns(dfa_t *pdfa);
 int dfa_minmax_delta(dfa_t *pdfa, int next_index, int isMin);
 void dump_dfa(FILE *f, dfa_t *pdfa);
 
Index: patterns/dfa.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa.c,v
retrieving revision 1.35
diff -u -p -r1.35 dfa.c
--- patterns/dfa.c      24 Jan 2004 04:04:56 -0000      1.35
+++ patterns/dfa.c      28 May 2004 12:28:32 -0000
@@ -884,6 +884,46 @@ dfa_shuffle(dfa_t *pdfa)
 }
 
 
+/* Calculate the maximal number of patterns matched at one point for
+ * one transformation.  Multiplying this number by 8 gives an upper
+ * bound for the total number of matched patterns for all
+ * transformation.  The DFA must be shuffled before calling this
+ * function (to ensure that all jumps go forward).
+ */
+int
+dfa_calculate_max_matched_patterns(dfa_t *pdfa)
+{
+  int total_max = 0;
+  int *state_max = calloc(pdfa->last_state + 1, sizeof(int));
+  int k;
+
+  for (k = 1; k <= pdfa->last_state; k++) {
+    int i;
+
+    /* Increment maximal number of matched patterns for each pattern
+     * matched at state `k'.
+     */
+    for (i = pdfa->states[k].att; i; i = pdfa->indexes[i].next)
+      state_max[k]++;
+
+    if (total_max < state_max[k])
+      total_max = state_max[k];
+
+    for (i = 0; i < 4; i++) {
+      int next = pdfa->states[k].next[i];
+      if (next != 0) {
+       assert(next > k);
+
+       if (state_max[next] < state_max[k])
+         state_max[next] = state_max[k];
+      }
+    }
+  }
+
+  return total_max;
+}
+
+
 /*
  * Merges cached dfas into the master DFA
  */
Index: patterns/dfa.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa.h,v
retrieving revision 1.27
diff -u -p -r1.27 dfa.h
--- patterns/dfa.h      24 Jan 2004 04:04:56 -0000      1.27
+++ patterns/dfa.h      28 May 2004 12:28:32 -0000
@@ -39,8 +39,8 @@
 #define OUT_BOARD 3            /* # */
 
 
-/* Maximum pattern matched at one positions. */
-#define DFA_MAX_MATCHED                (8 * 500)
+/* Maximal number of patterns matched at one positions. */
+#define DFA_MAX_MATCHED                (8 * 24)
 
 /* Conversion macro. */
 #define EXPECTED_COLOR(player_c, position_c)   (convert[player_c][position_c])
Index: patterns/mkpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkpat.c,v
retrieving revision 1.133
diff -u -p -r1.133 mkpat.c
--- patterns/mkpat.c    4 Mar 2004 00:06:26 -0000       1.133
+++ patterns/mkpat.c    28 May 2004 12:28:52 -0000
@@ -3205,6 +3205,8 @@ main(int argc, char *argv[])
        }
 
        if (command == 1) { /* Pattern `name' */
+         int k;
+
          if (!discard_pattern) {
            convert_attribute_labels_to_offsets();
            patno++;
@@ -3218,6 +3220,18 @@ main(int argc, char *argv[])
                    current_file, current_line_number);
            command_data[MAXNAME - 1] = 0;
          }
+
+         /* Somewhat inefficient, but doesn't take any real time
+          * given current database sizes.
+          */
+         for (k = 0; k < patno; k++) {
+           if (strcmp(pattern_names[k], command_data) == 0) {
+             fprintf(stderr, "%s(%d) : Warning : duplicate pattern name 
`%s'\n",
+                     current_file, current_line_number, command_data);
+             break;
+           }
+         }
+
          strcpy(pattern_names[patno], command_data);
 
          transformation_hint = find_transformation_hint(pattern_names[patno]);
@@ -3484,7 +3498,7 @@ main(int argc, char *argv[])
       print_c_dfa(output_FILE, prefix, &dfa);
       fprintf(stderr, "---------------------------\n");
 
-      if (DFA_MAX_MATCHED/8 < patno)
+      if (DFA_MAX_MATCHED/8 < dfa_calculate_max_matched_patterns(&dfa))
         fprintf(stderr, "Warning: Increase DFA_MAX_MATCHED in 'dfa.h'.\n");
 
       kill_dfa(&dfa);
Index: patterns/owl_defendpats.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/owl_defendpats.db,v
retrieving revision 1.117
diff -u -p -r1.117 owl_defendpats.db
--- patterns/owl_defendpats.db  8 Apr 2004 19:07:35 -0000       1.117
+++ patterns/owl_defendpats.db  28 May 2004 12:29:05 -0000
@@ -3791,7 +3791,7 @@ Pattern D841
 :8,-,value(45)
 
 
-Pattern D841
+Pattern D842
 # gf New pattern. (3.5.5)
 
 ???X.|
@@ -3804,7 +3804,7 @@ XOO..|
 :8,-,value(76)
 
 
-Pattern D842
+Pattern D843
 # pp New pattern (3.5.5)
 
 |OOOOO     workaround lunch problem (the eye is not considered a unit)
Index: patterns/patterns.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/patterns.db,v
retrieving revision 1.125
diff -u -p -r1.125 patterns.db
--- patterns/patterns.db        3 Mar 2004 22:14:12 -0000       1.125
+++ patterns/patterns.db        28 May 2004 12:29:16 -0000
@@ -10978,7 +10978,7 @@ hgeXd
 > replace(a,*)
 
 
-Pattern ED96
+Pattern ED97
 # gf New pattern. (3.5.3)
 # See gifu03:401
 
@@ -11001,7 +11001,7 @@ d.......
 ;weak(a) && weak(B) && x_somewhere(c,d)
 
 
-Pattern ED97
+Pattern ED98
 # evand new Pattern (3.5.4)
 
 .....