[gnugo-devel] fuseki db

[Douglas Ridgway]

This is a redo of the new fuseki pattern set, as generated with the new
extract_fuseki I posted last week. I think it's ready to replace the
existing db, at least in testing. 

The major change from the last version is that popularity tuning is
now basen on unique players, not unique games. This should avoid
things like the idiosyncratic moves played by "naoki" in the previous
version.  Popularity parameters are 4 1.0 2, same as before, except
for 9x9 H2 and 13x13, for which I used 2 1.0 1 due to the sparseness
of games. 19x19 H7 and up are also sparse, but I think quality is more
important there. The reduced number of patterns due to requiring
unique players is generally modest: about 10% typically. The other
change is that I've tried to make sure that the manual edits of the
existing db have been carried over.

Here is a summary table:

  Size  Handi   MinStr  Games   Depth   MinFreq Patterns
  9     0       6       1999    11      2       913
  9     2       10      231     10      1       443
  13    0       8       497     11      1       864
  19    0       0       35411   25      2       18063
  19    2       0       3930    25      2       1960
  19    3       0       2622    25      2       1431
  19    4       1       2172    25      2       1057
  19    5       3       2062    25      2       992
  19    6       6       2026    25      2       873
  19    7       6       771     25      2       313
  19    8       6       250     25      2       118
  19    9       6       458     25      2       166

MinStr is the minimum strength of the weakest player included. Depth is
both the max depth of the pattern generated and the minimum length of
game. Games is the total number of acceptable games. MinFreq is the least
number of unique players who must play a pattern before acceptance.
Patterns is the number of automatically generated patterns.

The new db files are > 1MB compressed, so I left them out of the
email. They can be downloaded from http://dridgway.com/Go/fuseki.tgz.

I haven't extracted the patterns for 9x9 H>2 and 13x13 H>1, either
from the existing db or from what games I have. There aren't that many
of them either way. I propose they simply get dropped, and rely on the
rule-generated moves. They can be added later if desired.

I have adjusted the weights for the 9x9 first move in the same way as
the existing db, and deleted (or confirmed nonappearance) of patterns
commented out of the existing db. Details below. So, other than
the small board handicap patterns, there's no work I know of in the
existing db which is being lost by substituting the new db.

In addition to the new .db files, I have included patches here to
raise some limits, remove the fuseki.c popularity screen and reduce
the pattern size to use less memory.  Still, the compiled binary is
larger: 7.5M, as as compared to 4.4M for 3.6-pre4.  If there are
situations where binary size is critical, a trimmed version could be
generated.

All comments appreciated.

Thanks,

doug.
address@hidden


Comments on deleted patterns:

I made a list of patterns deleted from the existing db by looking for
commented out patterns, and generated hashes for them, so that I could
check for them in the new db. A complete list appears below.  No
fuseki9 or fuseki13 patterns which had been deleted from the existing
db appeared in new db. I haven't checked whether this is due to my not
having the games leading to these patterns, excluding them during game
selection, or the popularity pruning, but in any case this lends some
weight to the claim that this db tends to contain higher quality
moves. Many deleted fuseki19 patterns did not appear either. One
example is Fuseki585. This pattern did appear in my previous
proposal, having been played 22 times, winning 18. Since it's now
gone, it must have been played exclusively by a single player ("naoki"
again?).  Deleted patterns which still appeared in the new
version I commented out by hand, pasting in the original comment from
the old db.

Doing this, I found a few deleted patterns which might be worth
reconsidering. Here's a list, with reasons:

        488 (actually dominates most alternatives based on amateur results)
        616 (does fine, is by far most popular)
        649 (ditto)
        714 (followup to 616. This move is better than ave, but see below)
        1000 (seems ordinary)

Of these, 1000 appears in pro play (44/95 games on gobase.org), but
the rest do not, although only 488 has a position with many hits. The
position where 714 appears is interesting:

+-------------------+
|...................|
|...................|
|...O........dO.....|
|...........cOXaX...|
|...........bX......|
|...................|
|...................|
|...................|
|...................|
|...............X...|
|...................|
|...................|
|...................|
|...................|
|...................|
|...O...........X...|
|...................|
|...................|
|...................|
+-------------------+

Played moves are ''a''-''d'', in order of decreasing popularity. The
differences in outcome are highly significant, p < 0.001, one of only
two positions (out of 15,000 total in the db) to meet that
standard. ''a'', the most popular move, is played 57/91 times this
position appears. It did the worst: winning 17/57, 30%, as compared to
48% overall. Pattern 714 is ''b'', and won 8/12. ''c'' won 12/14, and
''d'' won 4/4. ''b''-''d'' are statistically indistinguishable, but
they are all better than ''a''.  If I had to delete one, I know which
one I'd pick, but I'd rather see how GNU Go handled these positions
first.

I also found one more pattern that looks a little odd (F-H3-106
0x3c4e9bfb 0x0a134851), but left it in. There are no doubt others as well.

Deleted patterns:

  fuseki9.db:     pre        post  
              7   0x00000000 0x00b2a091
              111 0x2f467a26 0x32300763
              225 0x44212106 0x09af5f12
              412 0x2052f710 0x42141d60
              413 0x2052f710 0x3a474f76
              549 0x06d8e7df 0x09f42680
              555 0x1de86bc1 0x29d11713
              561 0x0e01f6a9 0x0b0ce87c
              565 0x230e4f6c 0x23bceffd
              571 0x1f699724 0x025d17b5
              583 0x3612b99b 0x36cc64e4
              702 0x3472a568 0x15cdf052
              711 0x11c856fd 0x117af66c
              713 0x12db2235 0x19a669bd
              736 0x1a2c3e19 0x1540dd85
              798 0x0030c1c8 0x4967d22a
              833 0x1b68fa69 0x2bce437e
              837 0x00144f75 0x02b57e37
              842 0x3a2718a1 0x3f6cc3ff

  fuseki13.db: 
               216 0x152c4b64 0x07b19de1

  fuseki19.db: 
               222 0x0f9914bf 0x26b8f34b
               386 0x18ed665d 0x1a6acca3
               488 0x220d654c 0x235d1a72
               585 0x1f8d9980 0x19d9b0e4
               616 0x03a214d2 0x3153ab5c
               649 0x1f7e329c 0x05b73660 
               671 0x27573111 0x17b40344
               679 0x009aba80 0x12bd7dd6
               714 0x1a329e6b 0x01ae4faa
               843 0x2bb585cc 0x0b225dd4
               1000 0x0ed9073c 0x319ca3dd
               1008 0x8479d061 0x3286c6f4
               1009 0x8479d061 0x01e0348b
               1016 0x46f43692 0x1a1a68c7
               1018 0x46f43692 0x27cfe268
               1036 0x6b6cdf56 0x005c23ec
               1066 0x91f2e768 0x15ac033e
               1095 0x07a3c5d9 0x16badbe8
               1223 0x148c37e6 0x02798636
               1224 0x148c37e6 0x0c63568c
               1289 0x1598e085 0x38a42bbb
               1368 0x09161d1a 0x03c87449
               1377 0x3c4e9bfb 0x12d88cc1
               1379 0x3c4e9bfb 0x074e9810
               1413 0x0061a17f 0x0d516aa5
               1422 0x0061a17f 0x2eb2f35c
               1489 0x085e1576 0x103e09ae



Index: patterns/mkpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkpat.c,v
retrieving revision 1.142
diff -u -r1.142 mkpat.c
--- patterns/mkpat.c    13 Nov 2004 04:46:45 -0000      1.142
+++ patterns/mkpat.c    17 Nov 2004 22:33:01 -0000
@@ -108,7 +108,7 @@
 #define MAXLINE                        500
 #define MAXCONSTRAINT          10000
 #define MAXACTION              10000
-#define MAXPATNO               5000
+#define MAXPATNO               100000
 #define MAXLABELS              20
 #define MAXPARAMS              20
 #define MAX_INPUT_FILE_NAMES   10
@@ -3214,6 +3214,7 @@
          if (!discard_pattern) {
            convert_attribute_labels_to_offsets();
            patno++;
+           assert(patno<MAXPATNO);
          }
          else
            code_pos = save_code_pos;
@@ -3451,6 +3452,7 @@
     case 4:
       check_constraint_diagram();
       patno++;
+      assert(patno<MAXPATNO);
       reset_pattern();
     }
   }

Index: engine/fuseki.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/fuseki.c,v
retrieving revision 1.24
diff -u -r1.24 fuseki.c
--- engine/fuseki.c     8 Nov 2004 04:10:02 -0000       1.24
+++ engine/fuseki.c     17 Nov 2004 22:31:50 -0000
@@ -39,7 +39,7 @@
  * number of stones actually residing on the board. This does in
  * particular include handicap stones.
  */
-#define MAX_FUSEKI_DATABASE_STONES 19
+#define MAX_FUSEKI_DATABASE_STONES 30


 #define UPPER_LEFT  0
@@ -300,15 +300,10 @@
     return 0;

   /* Choose randomly with respect to relative weights for matched moves.
-   * Do not choose moves with less value than 20% of the best move
-   * if there are more than two moves on board.
    */
   best_fuseki_value = fuseki_value[0];
   q = gg_rand() % fuseki_total_value;
   for (k = 0; k < num_fuseki_moves; k++) {
-    if (stones_on_board(BLACK | WHITE) > 2
-       && fuseki_value[k] < (best_fuseki_value / 5))
-      break;
     q -= fuseki_value[k];
     if (q < 0)
       break;

Index: patterns/patterns.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/patterns.h,v
retrieving revision 1.67
diff -u -r1.67 patterns.h
--- patterns/patterns.h 13 Nov 2004 04:46:45 -0000      1.67
+++ patterns/patterns.h 17 Nov 2004 22:30:09 -0000
@@ -170,8 +170,8 @@


 typedef struct patval {
-  int offset;
-  int att;
+  short offset;
+  char att;
 } Patval;

 /* Build-time version of patval structure. */