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 @[EMAIL PROTECTED] = -D -m @[EMAIL PROTECTED] = @@ -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 mailing list [email protected] http://lists.gnu.org/mailman/listinfo/gnugo-devel
