Re: [gnugo-devel] compact internal fuseki db representation

[Gunnar Farnebäck]

Arend wrote:
> Gunnar has made some suggestions and prelimary implementation for a
> compressed source representation (avoiding the need to put the huge
> .db-files into CVS), see http://83.250.33.151/gnugo/trac.cgi/ticket/7.
> So maybe we can finally merge it.

First the drawback of the compression; it discards all information in
the comments. While those are not needed for building GNU Go they are
interesting when analyzing fuseki database moves. Still it does not
seem worth the space to include them in CVS and in the distribution.

After removing the comments, the rest is compressed into this format,

F-H0-1 3977 pd
F-H0-2 1136 pc
F-H0-3 201 od
[...]
F-H0-34 1207 dpppddpd
F-H0-35 1113 dcppdppd
F-H0-36 193 eqppddpd
[...]
F-H3-20 88 lpopqpdpttpdttdd
F-H3-21 73 mqopqpdpttpdttdd
F-H3-22 43 oqopqpdpttpdttdd

with pattern name, value, and a sequence of sgf encoded board points.
The first point is the move, followed by a sequence of X and O stones
(X first, then alternating). In case of unbalanced stones, passes (tt)
are used. 

Some data points:

Size of current fuseki19 database: 760 kB
gzipped: 31 kB

Size of new fuseki19 database: 19.4 MB
gzipped: 1.4 MB

Size of compressed new fuseki19 database: 820 kB
gzipped: 230 kB
Size of uncompressed compressed new fuseki19 database: 12.4 MB

The new files compress_fuseki.c and uncompress_fuseki.c can be found
in the appended patch. They have already been committed to CVS.

/Gunnar

Index: patterns/compress_fuseki.c
===================================================================
RCS file: patterns/compress_fuseki.c
diff -N patterns/compress_fuseki.c
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ patterns/compress_fuseki.c  14 Sep 2005 20:18:04 -0000
@@ -0,0 +1,147 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
+ * This is GNU Go, a Go program. Contact address@hidden, or see       *
+ * http://www.gnu.org/software/gnugo/ for more information.          *
+ *                                                                   *
+ * Copyright 1999, 2000, 2001, 2002, 2003, 2004 and 2005             *
+ * by the Free Software Foundation.                                  *
+ *                                                                   *
+ * This program is free software; you can redistribute it and/or     *
+ * modify it under the terms of the GNU General Public License as    *
+ * published by the Free Software Foundation - version 2             *
+ *                                                                   *
+ * This program is distributed in the hope that it will be useful,   *
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of    *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the     *
+ * GNU General Public License in file COPYING for more details.      *
+ *                                                                   *
+ * You should have received a copy of the GNU General Public         *
+ * License along with this program; if not, write to the Free        *
+ * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,       *
+ * Boston, MA 02111, USA.                                            *
+\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#define BUFSIZE 160
+#define MAX_STONES 40
+#define MAX_BOARDSIZE 19
+
+#define USAGE "\
+Usage : uncompress_fuseki boardsize filename\n\
+"
+
+/* Write a board point in sgf format. Also do a sanity check. */
+static void
+write_stone(int i, int j)
+{
+  assert(i > 0 && i <= MAX_BOARDSIZE);
+  assert(j > 0 && j <= MAX_BOARDSIZE);
+  printf("%c%c", j + 'a' - 1, i + 'a' - 1);
+}
+
+int
+main(int argc, char *argv[])
+{
+  const char *filename;
+  FILE *input_FILE;
+  char line[BUFSIZE];
+  char name[BUFSIZE];
+  int value;
+  int k;
+  int row = 0;
+  int movei = -1;
+  int movej = -1;
+  int xi[MAX_STONES];
+  int xj[MAX_STONES];
+  int oi[MAX_STONES];
+  int oj[MAX_STONES];
+  int num_x = 0;
+  int num_o = 0;
+  
+  /* Check number of arguments. */
+  if (argc != 2) {
+    fprintf(stderr, USAGE);
+    return EXIT_FAILURE;
+  }
+
+  filename = argv[1];
+
+  input_FILE = fopen(filename, "r");
+  if (!input_FILE) {
+    fprintf(stderr, "compress_fuseki: Cannot open file %s\n", filename);
+    return EXIT_FAILURE;
+  }
+  
+  while (fgets(line, BUFSIZE, input_FILE)) {
+    if (sscanf(line, "Pattern %s", name) == 1) {
+      /* A new name has been picked up.
+       * Reset the row counter and the lists of stones.
+       */
+      row = 0;
+      num_x = 0;
+      num_o = 0;
+    }
+    else if (line[0] == ':') {
+      /* The colon line ends the pattern. First get the move value. */
+      if (sscanf(line, ":8,-,value(%d)", &value) != 1) {
+       fprintf(stderr, "compress_fuseki: Misformed colon line \"%s\"\n",
+               line);
+       return EXIT_FAILURE;
+      }
+
+      /* Write the compressed description of this pattern.
+       * Pad the stone list with passes (tt) if unbalanced colors.
+       */
+      printf("%s %d ", name, value);
+      write_stone(movei, movej);
+      while (num_x > 0 || num_o > 0) {
+       if (num_x > 0) {
+         num_x--;
+         write_stone(xi[num_x], xj[num_x]);
+       }
+       else if (num_o > 0)
+         printf("tt");
+       if (num_o > 0) {
+         num_o--;
+         write_stone(oi[num_o], oj[num_o]);
+       }
+       else if (num_x > 0)
+         printf("tt");
+      }
+      printf("\n");
+    }
+    else if (line[0] == '|') {
+      /* Found a diagram line. */
+      row++;
+      for (k = 1; line[k] && line[k] != '|'; k++) {
+       if (line[k] == '*') {
+         movei = row;
+         movej = k;
+       }
+       else if (line[k] == 'X') {
+         xi[num_x] = row;
+         xj[num_x] = k;
+         num_x++;
+         assert(num_x < MAX_STONES);
+       }
+       else if (line[k] == 'O') {
+         oi[num_o] = row;
+         oj[num_o] = k;
+         num_o++;
+         assert(num_o < MAX_STONES);
+       }
+      }
+    }
+  }
+
+  return EXIT_SUCCESS;
+}
+
+/*
+ * Local Variables:
+ * tab-width: 8
+ * c-basic-offset: 2
+ * End:
+ */
Index: patterns/uncompress_fuseki.c
===================================================================
RCS file: patterns/uncompress_fuseki.c
diff -N patterns/uncompress_fuseki.c
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ patterns/uncompress_fuseki.c        14 Sep 2005 20:18:54 -0000
@@ -0,0 +1,173 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
+ * This is GNU Go, a Go program. Contact address@hidden, or see       *
+ * http://www.gnu.org/software/gnugo/ for more information.          *
+ *                                                                   *
+ * Copyright 1999, 2000, 2001, 2002, 2003, 2004 and 2005             *
+ * by the Free Software Foundation.                                  *
+ *                                                                   *
+ * This program is free software; you can redistribute it and/or     *
+ * modify it under the terms of the GNU General Public License as    *
+ * published by the Free Software Foundation - version 2             *
+ *                                                                   *
+ * This program is distributed in the hope that it will be useful,   *
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of    *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the     *
+ * GNU General Public License in file COPYING for more details.      *
+ *                                                                   *
+ * You should have received a copy of the GNU General Public         *
+ * License along with this program; if not, write to the Free        *
+ * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,       *
+ * Boston, MA 02111, USA.                                            *
+\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#define MAX_BOARDSIZE 19
+#define BUFSIZE 160
+
+#define USAGE "\
+Usage : uncompress_fuseki boardsize filename\n\
+"
+
+#define PREAMBLE "\
+# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #\n\
+# This is GNU Go, a Go program. Contact address@hidden, or see       #\n\
+# http://www.gnu.org/software/gnugo/ for more information.          #\n\
+#                                                                   #\n\
+# Copyright 1999, 2000, 2001, 2002, 2003, 2004 and 2005             #\n\
+# by the Free Software Foundation.                                  #\n\
+#                                                                   #\n\
+# This program is free software; you can redistribute it and/or     #\n\
+# modify it under the terms of the GNU General Public License as    #\n\
+# published by the Free Software Foundation - version 2             #\n\
+#                                                                   #\n\
+# This program is distributed in the hope that it will be useful,   #\n\
+# but WITHOUT ANY WARRANTY; without even the implied warranty of    #\n\
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the     #\n\
+# GNU General Public License in file COPYING for more details.      #\n\
+#                                                                   #\n\
+# You should have received a copy of the GNU General Public         #\n\
+# License along with this program; if not, write to the Free        #\n\
+# Software Foundation, Inc., 51 Franklin Street, Fifth Floor,       #\n\
+# Boston, MA 02111, USA.                                            #\n\
+# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #\n\
+# This file is automatically generated by uncompress_fuseki. Do     #\n\
+# not edit it directly. Instead, edit the corresponding .dbz file.  #\n\
+# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #\n\
+\n\n\
+"
+
+/* Place a stone (or move mark) on the internal board. The board point
+ * is sgf encoded.
+ */
+static void
+set_board(char board[MAX_BOARDSIZE + 2][MAX_BOARDSIZE + 2],
+         char *stones, char color, int boardsize)
+{
+  int i = stones[1] - 'a' + 1;
+  int j = stones[0] - 'a' + 1;
+  if (stones[0] != 't') {
+    assert(i > 0 && i < boardsize + 2);
+    board[i][j] = color;
+  }
+}
+
+int
+main(int argc, char *argv[])
+{
+  const char *filename;
+  FILE *input_FILE;
+  char line[BUFSIZE];
+  char name[BUFSIZE];
+  char stones[BUFSIZE];
+  int value;
+  char board[MAX_BOARDSIZE + 2][MAX_BOARDSIZE + 2];
+  int boardsize;
+  int i, j, k;
+  char color;
+
+  /* Check number of arguments. */
+  if (argc != 3) {
+    fprintf(stderr, USAGE);
+    return EXIT_FAILURE;
+  }
+
+  boardsize = atoi(argv[1]);
+  filename = argv[2];
+
+  assert(boardsize > 0 && boardsize <= MAX_BOARDSIZE);
+  
+  input_FILE = fopen(filename, "r");
+  if (!input_FILE) {
+    fprintf(stderr, "uncompress_fuseki: Cannot open file %s\n", filename);
+    return EXIT_FAILURE;
+  }
+  
+  /* Initialize the corners of the internal board description. */
+  board[0][0] = '+';
+  board[0][boardsize + 1] = '+';
+  board[boardsize + 1][0] = '+';
+  board[boardsize + 1][boardsize + 1] = '+';
+
+  /* Initialize the sides of the internal board description. */
+  for (k = 1; k <= boardsize; k++) {
+    board[0][k] = '-';
+    board[boardsize + 1][k] = '-';
+    board[k][0] = '|';
+    board[k][boardsize + 1] = '|';
+  }
+
+  printf(PREAMBLE);
+  printf("attribute_map value_only\n\n");
+
+  /* Loop over the lines of the compressed database.
+   * Each line is one pattern.
+   */
+  while (fgets(line, BUFSIZE, input_FILE)) {
+    /* Clear the internal board. */
+    for (i = 1; i <= boardsize; i++)
+      for (j = 1; j <= boardsize; j++)
+       board[i][j] = '.';
+
+    /* Assume a line from copyright notice if misformed and
+     * silently ignore it.
+     */
+    if (sscanf(line, "%s %d %s", name, &value, stones) != 3)
+      continue;
+
+    /* The first point in the stones list is the move to be played. */
+    set_board(board, stones, '*', boardsize);
+
+    /* Then follows alternating X and O stones. */
+    color = 'X';
+    for (k = 2; k < (int) strlen(stones); k += 2) {
+      set_board(board, stones + k, color, boardsize);
+      if (color == 'X')
+       color = 'O';
+      else
+       color = 'X';
+    }
+
+    /* Output the uncompressed pattern. */
+    printf("Pattern %s\n\n", name);
+    for (i = 0; i <= boardsize + 1; i++) {
+      for (j = 0; j <= boardsize + 1; j++)
+       printf("%c", board[i][j]);
+      printf("\n");
+    }
+    printf("\n:8,-,value(%d)\n\n\n", value);
+  }
+
+  return EXIT_SUCCESS;
+}
+
+
+/*
+ * Local Variables:
+ * tab-width: 8
+ * c-basic-offset: 2
+ * End:
+ */