From 6c6a8b2a27b195660b203790eb53ffe8b128b6fb Mon Sep 17 00:00:00 2001 From: Petr Baudis Date: Wed, 1 Dec 2010 03:20:03 +0100 Subject: [PATCH] Introduce Fuego-compatible forcing opening book (fbook) --- HACKING | 9 +++-- Makefile | 2 +- board.c | 14 +++++++- board.h | 6 +++- fbook.c | 110 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ fbook.h | 24 +++++++++++++ gtp.c | 16 ++++++++- joseki/joseki.c | 4 +-- t-unit/test.c | 2 +- uct/uct.c | 5 ++- zzgo.c | 12 ++++--- 11 files changed, 189 insertions(+), 15 deletions(-) create mode 100644 fbook.c create mode 100644 fbook.h diff --git a/HACKING b/HACKING index 241d64c..4bfa9a9 100644 --- a/HACKING +++ b/HACKING @@ -260,10 +260,13 @@ the Kogo dictionary. Opening Book ============ -So far, there is no explicit support for opening book. - -However, the UCT engine can "pre-read" the starting board position and +The UCT engine can "pre-read" the starting board position and dump the core of the built tree to a file, loading it later. This is called a 'tbook' (as in "tree book") and can be generated using the ./gentbook.sh script. The newly generated file is automatically used by the UCT engine when found. + +Alternatively, there is a support for directly used opening book +(so-called fbook, a.k.a. "forced book" or "fuseki book"). The book +is stored in a text file in Fuego-compatible format and can be loaded +using the ./zzgo -f parameter. diff --git a/Makefile b/Makefile index 1326083..924da9d 100644 --- a/Makefile +++ b/Makefile @@ -38,7 +38,7 @@ unexport INCLUDES INCLUDES=-I. -OBJS=board.o gtp.o move.o ownermap.o pattern3.o pattern.o patternsp.o playout.o probdist.o random.o stone.o timeinfo.o network.o +OBJS=board.o gtp.o move.o ownermap.o pattern3.o pattern.o patternsp.o playout.o probdist.o random.o stone.o timeinfo.o network.o fbook.o SUBDIRS=random replay patternscan joseki montecarlo uct uct/policy playout tactics t-unit distributed all: all-recursive zzgo diff --git a/board.c b/board.c index 370183c..d94e10c 100644 --- a/board.c +++ b/board.c @@ -8,6 +8,7 @@ //#define DEBUG #include "board.h" #include "debug.h" +#include "fbook.h" #include "mq.h" #include "random.h" @@ -39,18 +40,24 @@ static void board_trait_recompute(struct board *board, coord_t coord); static void board_setup(struct board *b) { + char *fbookfile = b->fbookfile; + memset(b, 0, sizeof(*b)); + b->fbookfile = fbookfile; + struct move m = { pass, S_NONE }; b->last_move = b->last_move2 = b->last_ko = b->ko = m; } struct board * -board_init(void) +board_init(char *fbookfile) { struct board *b = malloc2(sizeof(struct board)); board_setup(b); + b->fbookfile = fbookfile; + // Default setup b->size = 9 + 2; board_clear(b); @@ -152,6 +159,7 @@ void board_done_noalloc(struct board *board) { if (board->b) free(board->b); + if (board->fbook) fbook_done(board->fbook); } void @@ -295,6 +303,10 @@ board_clear(struct board *board) probdist_set(&board->prob[1], c, double_to_fixp((board_at(board, c) == S_NONE) * 1.0f)); } foreach_point_end; #endif + + if (board->fbookfile) { + board->fbook = fbook_init(board->fbookfile, board); + } } static char * diff --git a/board.h b/board.h index 7d621f5..11dc23f 100644 --- a/board.h +++ b/board.h @@ -14,6 +14,7 @@ #include "move.h" struct features_gamma; +struct fbook; /* Maximum supported board size. (Without the S_OFFBOARD edges.) */ @@ -137,6 +138,9 @@ struct board { RULES_JAPANESE, } rules; + char *fbookfile; + struct fbook *fbook; + /* Iterator offsets for foreach_neighbor*() */ int nei8[8], dnei[4]; @@ -306,7 +310,7 @@ struct board { #define hash_at(b_, coord, color) ((b_)->h[((color) == S_BLACK ? board_size2(b_) : 0) + coord]) -struct board *board_init(void); +struct board *board_init(char *fbookfile); struct board *board_copy(struct board *board2, struct board *board1); void board_done_noalloc(struct board *board); void board_done(struct board *board); diff --git a/fbook.c b/fbook.c new file mode 100644 index 0000000..dbe10ed --- /dev/null +++ b/fbook.c @@ -0,0 +1,110 @@ +#include +#include +#include +#include + +#include "board.h" +#include "debug.h" +#include "fbook.h" + +struct fbook * +fbook_init(char *filename, struct board *b) +{ + FILE *f = fopen(filename, "r"); + if (!f) { + perror(filename); + return NULL; + } + + struct fbook *fbook = calloc(1, sizeof(*fbook)); + fbook->bsize = board_size(b); + fbook->handicap = b->handicap; + for (int i = 0; i < 1<moves[i] = pass; + + if (DEBUGL(1)) + fprintf(stderr, "Loading opening fbook %s...\n", filename); + + /* Scratch board where we lay out the sequence; + * one for each transposition. */ + struct board *bs[8]; + for (int i = 0; i < 8; i++) { + bs[i] = board_init(NULL); + board_resize(bs[i], fbook->bsize - 2); + } + + char linebuf[1024]; + while (fgets(linebuf, sizeof(linebuf), f)) { + char *line = linebuf; + linebuf[strlen(linebuf) - 1] = 0; // chop + + /* Format of line is: + * BSIZE COORD COORD COORD... | COORD + * We descend up to |, then add the new node + * with value minimax(1000), forcing UCT to + * always pick that node immediately. */ + int bsize = strtol(line, &line, 10); + if (bsize != fbook->bsize - 2) + continue; + while (isspace(*line)) line++; + + for (int i = 0; i < 8; i++) { + board_clear(bs[i]); + bs[i]->last_move.color = S_WHITE; + } + + while (*line != '|') { + coord_t *c = str2coord(line, fbook->bsize); + + for (int i = 0; i < 8; i++) { +#define HASH_VMIRROR 1 +#define HASH_HMIRROR 2 +#define HASH_XYFLIP 4 + coord_t coord = *c; + if (i & HASH_VMIRROR) { + coord = coord_xy(b, coord_x(coord, b), board_size(b) - 1 - coord_y(coord, b)); + } + if (i & HASH_HMIRROR) { + coord = coord_xy(b, board_size(b) - 1 - coord_x(coord, b), coord_y(coord, b)); + } + if (i & HASH_XYFLIP) { + coord = coord_xy(b, coord_y(coord, b), coord_x(coord, b)); + } + struct move m = { .coord = coord, .color = stone_other(bs[i]->last_move.color) }; + int ret = board_play(bs[i], &m); + assert(ret >= 0); + } + + coord_done(c); + while (!isspace(*line)) line++; + while (isspace(*line)) line++; + } + + line++; + while (isspace(*line)) line++; + + coord_t *c = str2coord(line, fbook->bsize); + for (int i = 0; i < 8; i++) { +#if 0 + fprintf(stderr, "%c %"PRIhash" (<%d> %s)\n", + is_pass(fbook->moves[bs[i]->hash & fbook_hash_mask]) ? '+' : 'C', + bs[i]->hash & fbook_hash_mask, i, linebuf); +#endif + fbook->moves[bs[i]->hash & fbook_hash_mask] = *c; + } + coord_done(c); + } + + for (int i = 0; i < 8; i++) { + board_done(bs[i]); + } + + fclose(f); + + return fbook; +} + +void fbook_done(struct fbook *fbook) +{ + free(fbook); +} diff --git a/fbook.h b/fbook.h new file mode 100644 index 0000000..e344be5 --- /dev/null +++ b/fbook.h @@ -0,0 +1,24 @@ +#ifndef ZZGO_FBOOK_H +#define ZZGO_FBOOK_H + +#include "move.h" + +struct board; + +/* Opening book (fbook as in "forcing book" since the move is just + * played unconditionally if found, or possibly "fuseki book"). */ + +struct fbook { + int bsize; + int handicap; + +#define fbook_hash_bits 19 // 4M w/ 32-bit coord_t +#define fbook_hash_mask ((1 << fbook_hash_bits) - 1) + /* pass == no move in this position */ + coord_t moves[1<fbook) { + /* We have an fbook, check if we cannot make + * a move along it right away. */ + coord_t cf = board->fbook->moves[board->hash & fbook_hash_mask]; + if (!is_pass(cf)) { + if (DEBUGL(1)) + fprintf(stderr, "fbook match\n"); + c = coord_copy(cf); + } + } + + if (!c) c = engine->genmove(engine, board, &ti[color], color, !strcasecmp(cmd, "kgs-genmove_cleanup")); - coord_t *c = engine->genmove(engine, board, &ti[color], color, !strcasecmp(cmd, "kgs-genmove_cleanup")); struct move m = { *c, color }; if (board_play(board, &m) < 0) { fprintf(stderr, "Attempted to generate an illegal move: [%s, %s]\n", coord2sstr(m.coord, board), stone2str(m.color)); diff --git a/joseki/joseki.c b/joseki/joseki.c index 930c2e4..84cc560 100644 --- a/joseki/joseki.c +++ b/joseki/joseki.c @@ -131,7 +131,7 @@ void engine_joseki_done(struct engine *e) { struct joseki_engine *j = e->data; - struct board *b = board_init(); + struct board *b = board_init(NULL); board_resize(b, j->size - 2); board_clear(b); @@ -163,7 +163,7 @@ joseki_state_init(char *arg) struct joseki_engine *j = calloc2(1, sizeof(struct joseki_engine)); for (int i = 0; i < 16; i++) - j->b[i] = board_init(); + j->b[i] = board_init(NULL); j->debug_level = 1; diff --git a/t-unit/test.c b/t-unit/test.c index 4736676..e4473a9 100644 --- a/t-unit/test.c +++ b/t-unit/test.c @@ -90,7 +90,7 @@ unittest(char *filename) exit(EXIT_FAILURE); } - struct board *b = board_init(); + struct board *b = board_init(NULL); char line[256]; while (fgets(line, sizeof(line), f)) { line[strlen(line) - 1] = 0; // chomp diff --git a/uct/uct.c b/uct/uct.c index 4631ebd..09d5764 100644 --- a/uct/uct.c +++ b/uct/uct.c @@ -121,7 +121,10 @@ static char * uct_printhook_ownermap(struct board *board, coord_t c, char *s, char *end) { struct uct *u = board->es; - assert(u); + if (!u) { + strcat(s, ". "); + return s + 2; + } const char chr[] = ":XO,"; // dame, black, white, unclear const char chm[] = ":xo,"; char ch = chr[board_ownermap_judge_point(&u->ownermap, c, GJ_THRES)]; diff --git a/zzgo.c b/zzgo.c index b8ce54f..b87489d 100644 --- a/zzgo.c +++ b/zzgo.c @@ -70,8 +70,8 @@ static void usage(char *name) { fprintf(stderr, "Pachi version %s\n", PACHI_VERSION); fprintf(stderr, "Usage: %s [-e random|replay|patternscan|montecarlo|uct|distributed]\n" - " [-d DEBUG_LEVEL] [-s RANDOM_SEED] [-t TIME_SETTINGS] [-u TEST_FILENAME]" - " [-g [HOST:]GTP_PORT] [-l [HOST:]LOG_PORT] [ENGINE_ARGS]\n", name); + " [-d DEBUG_LEVEL] [-s RANDOM_SEED] [-t TIME_SETTINGS] [-u TEST_FILENAME]\n" + " [-g [HOST:]GTP_PORT] [-l [HOST:]LOG_PORT] [-f FBOOKFILE] [ENGINE_ARGS]\n", name); } int main(int argc, char *argv[]) @@ -82,11 +82,12 @@ int main(int argc, char *argv[]) char *gtp_port = NULL; char *log_port = NULL; int gtp_sock = -1; + char *fbookfile = NULL; seed = time(NULL) ^ getpid(); int opt; - while ((opt = getopt(argc, argv, "e:d:g:l:s:t:u:")) != -1) { + while ((opt = getopt(argc, argv, "e:d:f:g:l:s:t:u:")) != -1) { switch (opt) { case 'e': if (!strcasecmp(optarg, "random")) { @@ -111,6 +112,9 @@ int main(int argc, char *argv[]) case 'd': debug_level = atoi(optarg); break; + case 'f': + fbookfile = strdup(optarg); + break; case 'g': gtp_port = strdup(optarg); break; @@ -152,7 +156,7 @@ int main(int argc, char *argv[]) if (DEBUGL(0)) fprintf(stderr, "Random seed: %d\n", seed); - struct board *b = board_init(); + struct board *b = board_init(fbookfile); struct time_info ti[S_MAX]; ti[S_BLACK] = ti_default; ti[S_WHITE] = ti_default; -- 2.11.4.GIT