[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] compact internal fuseki db representation
|
From: |
Arend Bayer |
|
Subject: |
[gnugo-devel] compact internal fuseki db representation |
|
Date: |
Mon, 12 Sep 2005 02:35:56 +0200 (CEST) |
This patch compactifies the internal representation of the fuseki database
by storing a hash value for the full pattern, instead of storing all
elements. It reduces the size by about a factor of 4.
The point of this is of course to that it will reduce the size impact of
Doug's new (and a lot bigger) fuseki databases.
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.
Arend
Index: engine/board.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.h,v
retrieving revision 1.24
diff -u -p -r1.24 board.h
--- engine/board.h 12 Jun 2005 09:34:13 -0000 1.24
+++ engine/board.h 12 Sep 2005 00:09:22 -0000
@@ -64,6 +64,7 @@
#define MAXSTACK MAX_BOARD * MAX_BOARD
#define MAXCHAIN 160
+#define HASH_RANDOM_SEED 12345
/* ================================================================ *
* One-dimensional board *
Index: engine/fuseki.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/fuseki.c,v
retrieving revision 1.26
diff -u -p -r1.26 fuseki.c
--- engine/fuseki.c 12 Jun 2005 09:34:14 -0000 1.26
+++ engine/fuseki.c 12 Sep 2005 00:09:22 -0000
@@ -267,7 +267,7 @@ static void
fuseki_callback(int move, struct fullboard_pattern *pattern, int ll)
{
TRACE("Fuseki database move at %1m with relative weight %d, pattern %s+%d\n",
- move, (int) pattern->value, pattern->name, ll);
+ move, pattern->value, pattern->name, ll);
/* Store coordinates and relative weight for the found move. */
fuseki_moves[num_fuseki_moves] = move;
Index: engine/hash.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/hash.c,v
retrieving revision 1.34
diff -u -p -r1.34 hash.c
--- engine/hash.c 12 Jun 2005 09:34:14 -0000 1.34
+++ engine/hash.c 12 Sep 2005 00:09:22 -0000
@@ -108,10 +108,8 @@ void
hashdata_recalc(Hash_data *target, Intersection *p, int ko_pos)
{
int pos;
- int i;
- for (i = 0; i < NUM_HASHVALUES; i++)
- target->hashval[i] = 0;
+ hashdata_clear(target);
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (p[pos] == WHITE)
@@ -124,6 +122,14 @@ hashdata_recalc(Hash_data *target, Inter
hashdata_xor(*target, ko_hash[ko_pos]);
}
+/* Clear hashdata. */
+void
+hashdata_clear(Hash_data *hd)
+{
+ int i;
+ for (i = 0; i < NUM_HASHVALUES; i++)
+ hd->hashval[i] = 0;
+}
/* Set or remove ko in the hash value and hash position. */
void
@@ -162,16 +168,14 @@ hashdata_invert_kom_pos(Hash_data *hd, i
Hash_data
goal_to_hashvalue(const char *goal)
{
- int i, pos;
+ int pos;
Hash_data return_value;
- for (i = 0; i < NUM_HASHVALUES; i++)
- return_value.hashval[i] = 0;
+ hashdata_clear(&return_value);
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(pos) && goal[pos])
- for (i = 0; i < NUM_HASHVALUES; i++)
- return_value.hashval[i] ^= goal_hash[pos].hashval[i];
+ hashdata_xor(return_value, goal_hash[pos]);
return return_value;
}
Index: engine/hash.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/hash.h,v
retrieving revision 1.34
diff -u -p -r1.34 hash.h
--- engine/hash.h 12 Jun 2005 09:34:14 -0000 1.34
+++ engine/hash.h 12 Sep 2005 00:09:22 -0000
@@ -87,6 +87,7 @@ void hash_init(void);
#define INIT_ZOBRIST_ARRAY(a) \
hash_init_zobrist_array(a, (int) (sizeof(a) / sizeof(a[0])))
+void hashdata_clear(Hash_data *hd);
void hashdata_recalc(Hash_data *hd, Intersection *board, int ko_pos);
void hashdata_invert_ko(Hash_data *hd, int pos);
void hashdata_invert_stone(Hash_data *hd, int pos, int color);
Index: engine/interface.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/interface.c,v
retrieving revision 1.53
diff -u -p -r1.53 interface.c
--- engine/interface.c 12 Jun 2005 09:34:14 -0000 1.53
+++ engine/interface.c 12 Sep 2005 00:09:23 -0000
@@ -43,7 +43,7 @@ init_gnugo(float memory, unsigned int se
* reproducable results.
* FIXME: Test the quality of the seed.
*/
- set_random_seed(12345);
+ set_random_seed(HASH_RANDOM_SEED);
reading_cache_init(memory * 1024 * 1024);
set_random_seed(seed);
persistent_cache_init();
Index: engine/matchpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/matchpat.c,v
retrieving revision 1.68
diff -u -p -r1.68 matchpat.c
--- engine/matchpat.c 12 Jun 2005 09:34:14 -0000 1.68
+++ engine/matchpat.c 12 Sep 2005 00:09:25 -0000
@@ -1155,6 +1155,17 @@ matchpat_goal_anchor(matchpat_callback_f
}
+static int
+fullboard_transform(int pos, int trans)
+{
+ int dx = I(pos) - (board_size-1)/2;
+ int dy = J(pos) - (board_size-1)/2;
+ int x, y;
+ gg_assert(POS((board_size-1)/2, (board_size-1)/2) + DELTA(dx, dy) == pos);
+ TRANSFORM2(dx, dy, &x, &y, trans);
+ return POS(x + (board_size-1)/2, y + (board_size-1)/2);
+}
+
/* A dedicated matcher which can only do fullboard matching on
* odd-sized boards, optimized for fuseki patterns.
*/
@@ -1162,50 +1173,56 @@ void
fullboard_matchpat(fullboard_matchpat_callback_fn_ptr callback, int color,
struct fullboard_pattern *pattern)
{
- int other = OTHER_COLOR(color);
int ll; /* Iterate over transformations (rotations or reflections) */
- int k; /* Iterate over elements of pattern */
/* We transform around the center point. */
- int mid = POS((board_size-1)/2, (board_size-1)/2);
int number_of_stones_on_board = stones_on_board(BLACK | WHITE);
+ static int color_map[gg_max(WHITE, BLACK)];
+ /* One hash value for each rotation/reflection: */
+ Hash_data current_board_hash[8];
/* Basic sanity check. */
gg_assert(color != EMPTY);
gg_assert(board_size % 2 == 1);
- /* Try each pattern - NULL pattern marks end of list. */
- for (; pattern->patn; pattern++) {
- /* The number of stones on the board must be right. This is not
- * only an optimization because we never even look at the
- * intersections which are empty in the pattern.
- */
- if (pattern->patlen != number_of_stones_on_board)
- continue;
-
- /* try each orientation transformation */
- for (ll = 0; ll < 8; ll++) {
- /* Now iterate over the elements of the pattern. */
- for (k = 0; k < pattern->patlen; k++) { /* match each point */
- int pos; /* board co-ords of transformed pattern element */
- int att = pattern->patn[k].att; /* what we are looking for */
+ color_map[EMPTY] = EMPTY;
+ if (color == WHITE) {
+ color_map[WHITE] = WHITE;
+ color_map[BLACK] = BLACK;
+ }
+ else {
+ color_map[WHITE] = BLACK;
+ color_map[BLACK] = WHITE;
+ }
- /* Work out the position on the board of this pattern element. */
- pos = AFFINE_TRANSFORM(pattern->patn[k].offset, ll, mid);
+ /* Get hash data of all rotations/reflections of current board position. */
+ for (ll = 0; ll < 8; ll++) {
+ Intersection p[BOARDSIZE];
+ int pos;
+ for (pos = 0; pos < BOARDSIZE; pos++)
+ if (ON_BOARD(pos))
+ p[pos] = color_map[board[fullboard_transform(pos, ll)]];
+ else
+ p[pos] = GRAY;
- ASSERT_ON_BOARD1(pos);
+ if (ON_BOARD(board_ko_pos))
+ hashdata_recalc(¤t_board_hash[ll], p,
+ fullboard_transform(board_ko_pos, ll));
+ else
+ hashdata_recalc(¤t_board_hash[ll], p, NO_MOVE);
+ }
- if ((att == ATT_O && board[pos] != color)
- || (att == ATT_X && board[pos] != other))
- break;
-
- } /* loop over elements */
-
- if (k == pattern->patlen) {
+ /* Try each pattern - NULL pattern name marks end of list. */
+ for (; pattern->name; pattern++) {
+ if (pattern->number_of_stones != number_of_stones_on_board)
+ continue;
+ /* Try each orientation transformation. */
+ for (ll = 0; ll < 8; ll++)
+ if (hashdata_is_equal(current_board_hash[ll], pattern->fullboard_hash)) {
/* A match! - Call back to the invoker to let it know. */
- int pos = AFFINE_TRANSFORM(pattern->move_offset, ll, mid);
+ int pos = AFFINE_TRANSFORM(pattern->move_offset, ll,
+ POS((board_size-1)/2, (board_size-1)/2));
callback(pos, pattern, ll);
}
- }
}
}
Index: patterns/Makefile.am
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/Makefile.am,v
retrieving revision 1.33
diff -u -p -r1.33 Makefile.am
--- patterns/Makefile.am 9 Sep 2005 22:59:05 -0000 1.33
+++ patterns/Makefile.am 12 Sep 2005 00:09:25 -0000
@@ -40,7 +40,7 @@ EXTRA_DIST = $(DSP)\
mkpat_SOURCES = mkpat.c transform.c dfa.c
-mkpat_LDADD = ../utils/libutils.a
+mkpat_LDADD = ../utils/libutils.a ../engine/libboard.a ../sgf/libsgf.a
if DFA_ENABLED
DFAFLAGS = -D -m
Index: patterns/Makefile.in
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/Makefile.in,v
retrieving revision 1.52
diff -u -p -r1.52 Makefile.in
--- patterns/Makefile.in 9 Sep 2005 22:59:05 -0000 1.52
+++ patterns/Makefile.in 12 Sep 2005 00:09:25 -0000
@@ -119,7 +119,7 @@ EXTRA_DIST = $(DSP)\
mkpat_SOURCES = mkpat.c transform.c dfa.c
-mkpat_LDADD = ../utils/libutils.a
+mkpat_LDADD = ../utils/libutils.a ../engine/libboard.a ../sgf/libsgf.a
@address@hidden = -D -m
@address@hidden =
@@ -222,7 +222,8 @@ mkeyes_DEPENDENCIES = ../utils/libutils.
mkeyes_LDFLAGS =
am_mkpat_OBJECTS = mkpat.$(OBJEXT) transform.$(OBJEXT) dfa.$(OBJEXT)
mkpat_OBJECTS = $(am_mkpat_OBJECTS)
-mkpat_DEPENDENCIES = ../utils/libutils.a
+mkpat_DEPENDENCIES = ../utils/libutils.a ../engine/libboard.a \
+ ../sgf/libsgf.a
mkpat_LDFLAGS =
am_transpat_OBJECTS = transpat.$(OBJEXT) patlib.$(OBJEXT) \
transform.$(OBJEXT)
Index: patterns/mkpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkpat.c,v
retrieving revision 1.147
diff -u -p -r1.147 mkpat.c
--- patterns/mkpat.c 12 Jun 2005 09:34:15 -0000 1.147
+++ patterns/mkpat.c 12 Sep 2005 00:09:25 -0000
@@ -88,6 +88,7 @@ If output file is not specified, writes
#include "gg_utils.h"
#include "dfa-mkpat.h"
+#include "hash.h"
#define DB_GENERAL ((int) 'p')
@@ -173,6 +174,7 @@ static char constraint_diagram[MAX_BOARD
static char *prefix;
static struct pattern pattern[MAXPATNO]; /* accumulate the patterns into here
*/
static char pattern_names[MAXPATNO][MAXNAME]; /* with optional names here, */
+static Hash_data pattern_hash[MAXPATNO];
static int num_attributes;
static struct pattern_attribute attributes[MAXPATNO * NUM_ATTRIBUTES];
static char helper_fn_names[MAXPATNO][MAXNAME]; /* helper fn names here */
@@ -917,11 +919,9 @@ read_pattern_line(char *p)
}
/* Special limitations for fullboard patterns. */
- if (database_type == DB_FULLBOARD) {
+ if (database_type == DB_FULLBOARD)
if (off == ATT_dot)
continue;
- assert(off == ATT_X || off == ATT_O);
- }
/* Range checking. */
assert(el < (int) (sizeof(elements) / sizeof(elements[0])));
@@ -2711,6 +2711,89 @@ corner_write_variations(struct corner_va
}
+/* ================================================================ */
+/* Fullboard database specific functions */
+/* ================================================================ */
+
+static void
+fullboard_init(void)
+{
+ set_random_seed(HASH_RANDOM_SEED);
+ hash_init();
+}
+
+/* Compute a hash of the current fullboard pattern, where we assume
+ * black stones at X and white stones at O elements.
+ */
+static void
+compute_fullboard_hash(void)
+{
+ int node;
+ int used_nodes = 0;
+ int pos;
+ Intersection pattern_board[BOARDSIZE];
+ unsigned int bs = maxi + 1;
+
+ assert(ci == maxi/2 && cj == maxj/2);
+ assert(maxi == maxj && mini == minj && mini == 0);
+
+ /* Clear private board. */
+ for (pos = 0; pos < BOARDSIZE; pos++)
+ if ((unsigned) I(pos) < bs && (unsigned) J(pos) < bs) {
+ pattern_board[pos] = EMPTY;
+ }
+ else
+ pattern_board[pos] = GRAY;
+
+ /* Populate private board. */
+ for (node = 0; node < el; node++) {
+ int x = elements[node].x;
+ int y = elements[node].y;
+ int att = elements[node].att;
+ int pos = POS(x, y);
+ assert((unsigned) I(pos) < bs && (unsigned) J(pos) < bs);
+
+ if (att == ATT_O)
+ pattern_board[pos] = WHITE;
+ else
+ pattern_board[pos] = BLACK;
+
+ used_nodes++;
+ }
+
+ /* Compute hash. */
+ hashdata_recalc(&pattern_hash[patno], pattern_board, NO_MOVE);
+
+ pattern[patno].patlen = used_nodes;
+}
+
+
+static void
+write_fullboard_patterns(FILE *outfile)
+{
+ int j, k;
+
+ fprintf(outfile, "struct fullboard_pattern %s[] = {\n", prefix);
+
+ for (j = 0; j < patno; ++j) {
+ struct pattern *p = pattern + j;
+ fprintf(outfile, " {{{");
+ for (k = 0; k < NUM_HASHVALUES; k++) {
+ fprintf(outfile, "0x%lx", pattern_hash[j].hashval[k]);
+ if (k < NUM_HASHVALUES - 1)
+ fprintf(outfile, ",");
+ }
+ fprintf(outfile, "}},%d,\"%s\",%d,%d},\n",
+ p->patlen, pattern_names[j], p->move_offset, (int) p->value);
+ }
+
+ fprintf(outfile, " {{{");
+ for (k = 0; k < NUM_HASHVALUES - 1; k++)
+ fprintf(outfile, "0,");
+ fprintf(outfile, "0}}, -1,NULL,0,0}\n};\n");
+}
+
+
static void
write_attributes(FILE *outfile)
{
@@ -2763,9 +2846,7 @@ write_patterns(FILE *outfile)
#endif
/* Write out the patterns. */
- if (database_type == DB_FULLBOARD)
- fprintf(outfile, "struct fullboard_pattern %s[] = {\n", prefix);
- else if (database_type == DB_CORNER)
+ if (database_type == DB_CORNER)
fprintf(outfile, "static struct corner_pattern %s[] = {\n", prefix);
else
fprintf(outfile, "static struct pattern %s[] = {\n", prefix);
@@ -2773,12 +2854,6 @@ write_patterns(FILE *outfile)
for (j = 0; j < patno; ++j) {
struct pattern *p = pattern + j;
- if (database_type == DB_FULLBOARD) {
- fprintf(outfile, " {%s%d,%d,\"%s\",%d,%f},\n", prefix, j, p->patlen,
- pattern_names[j], p->move_offset, p->value);
- continue;
- }
-
if (database_type == DB_CORNER) {
fprintf(outfile, " {%d,%d,0x%x,\"%s\",",
second_corner_offset[j], (p->trfno == 4),
@@ -2867,11 +2942,6 @@ write_patterns(FILE *outfile)
if (database_type == DB_CORNER)
return;
- if (database_type == DB_FULLBOARD) {
- fprintf(outfile, " {NULL,0,NULL,0,0.0}\n};\n");
- return;
- }
-
/* Add a final empty entry. */
fprintf(outfile, " {NULL, 0,0,NULL,0,0,0,0,0,0,0,0");
#if GRID_OPT
@@ -2888,10 +2958,6 @@ write_patterns(FILE *outfile)
static void
write_pattern_db(FILE *outfile)
{
- /* Don't want this for fullboard patterns. */
- if (database_type == DB_FULLBOARD)
- return;
-
if (database_type == DB_CORNER) {
fprintf(outfile, "struct corner_db %s_db = {\n", prefix);
fprintf(outfile, " %d,\n", corner_max_width + 1);
@@ -3068,9 +3134,10 @@ main(int argc, char *argv[])
dfa_init();
new_dfa(&dfa, "mkpat's dfa");
}
-
- if (database_type == DB_CORNER)
+ else if (database_type == DB_CORNER)
corner_init();
+ else if (database_type == DB_FULLBOARD)
+ fullboard_init();
if (database_type == OPTIMIZE_DFA) {
if (transformations_file_name == NULL) {
@@ -3371,8 +3438,9 @@ main(int argc, char *argv[])
write_to_dfa(patno);
if (database_type == DB_CORNER)
corner_add_pattern();
-
- if (database_type != DB_CORNER && database_type != OPTIMIZE_DFA)
+ else if (database_type == DB_FULLBOARD)
+ compute_fullboard_hash();
+ else if (database_type != OPTIMIZE_DFA)
write_elements(output_FILE);
}
@@ -3465,14 +3533,14 @@ main(int argc, char *argv[])
fprintf(stderr, "%d / %d patterns have edge-constraints\n",
pats_with_constraints, patno);
- if (database_type != OPTIMIZE_DFA) {
+ if (database_type == DB_FULLBOARD)
+ write_fullboard_patterns(output_FILE);
+ else if (database_type != OPTIMIZE_DFA) {
/* Forward declaration, which autohelpers might need. */
- if (database_type != DB_FULLBOARD) {
- if (database_type != DB_CORNER)
- fprintf(output_FILE, "static struct pattern %s[%d];\n\n", prefix, patno
+ 1);
- else
- fprintf(output_FILE, "static struct corner_pattern %s[%d];\n\n",
prefix, patno + 1);
- }
+ if (database_type != DB_CORNER)
+ fprintf(output_FILE, "static struct pattern %s[%d];\n\n", prefix, patno
+ 1);
+ else
+ fprintf(output_FILE, "static struct corner_pattern %s[%d];\n\n", prefix,
patno + 1);
/* Write the autohelper code. */
fprintf(output_FILE, "%s", autohelper_code);
Index: patterns/patterns.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/patterns.h,v
retrieving revision 1.68
diff -u -p -r1.68 patterns.h
--- patterns/patterns.h 12 Jun 2005 09:34:15 -0000 1.68
+++ patterns/patterns.h 12 Sep 2005 00:09:25 -0000
@@ -291,11 +291,11 @@ struct pattern_db {
struct fullboard_pattern {
- struct patval *patn; /* array of elements */
- int patlen; /* number of elements */
- const char *name; /* short description of pattern (optional) */
- int move_offset; /* offset of the suggested move (to intersection
(0,0)) */
- float value; /* value for pattern, if matched */
+ Hash_data fullboard_hash; /* Hash of the full board position. */
+ int number_of_stones; /* Number of stones on board. */
+ const char *name; /* Pattern identifier. */
+ int move_offset; /* position of the move relative to tengen */
+ int value; /* value for pattern, if matched */
};
- [gnugo-devel] compact internal fuseki db representation,
Arend Bayer <=