From 93df17a5d6274c50373905d7761c37687ae6a0ee Mon Sep 17 00:00:00 2001 From: Petr Baudis Date: Sun, 10 Mar 2013 01:47:04 +0100 Subject: [PATCH] Split libmap_hash to libmap_group array, create libmap_group slots only to pre-simulation groups --- board.c | 18 +++++++++++- board.h | 2 ++ playout.c | 6 ++-- playout/moggy.c | 4 +-- tactics/2lib.c | 3 +- tactics/goals.c | 62 ++++++++++++++++++++++++++++++---------- tactics/goals.h | 87 +++++++++++++++++++++++++++++++++++++-------------------- tactics/nlib.c | 1 + 8 files changed, 132 insertions(+), 51 deletions(-) diff --git a/board.c b/board.c index 357a993..94069ae 100644 --- a/board.c +++ b/board.c @@ -163,6 +163,11 @@ board_done(struct board *board) void board_resize(struct board *board, int size) { + if (board->libmap) { + libmap_put(board->libmap); + board->libmap = NULL; + } + #ifdef BOARD_SIZE assert(board_size(board) == size + 2); #endif @@ -294,6 +299,8 @@ board_init_data(struct board *board) #endif } foreach_point_end; #endif + + board->libmap_init_groups = true; } void @@ -1229,9 +1236,14 @@ board_play_outside(struct board *board, struct move *m, int f) }); board_at(board, coord) = color; - if (unlikely(!group)) + if (unlikely(!group)) { group = new_group(board, coord); + /* Make sure the new group has a libmap entry. */ + if (board->libmap && board->libmap_init_groups) + libmap_group_init(board->libmap, board, coord, color); + } + board->last_move2 = board->last_move; board->last_move = *m; board->moves++; @@ -1331,6 +1343,10 @@ board_play_in_eye(struct board *board, struct move *m, int f) board_at(board, coord) = color; group_t group = new_group(board, coord); + /* Make sure the new group has a libmap entry. */ + if (board->libmap && board->libmap_init_groups) + libmap_group_init(board->libmap, board, coord, color); + board->last_move2 = board->last_move; board->last_move = *m; board->moves++; diff --git a/board.h b/board.h index 75e9b0c..5dd5ebe 100644 --- a/board.h +++ b/board.h @@ -160,6 +160,8 @@ struct board { char *fbookfile; struct fbook *fbook; struct libmap_hash *libmap; + /* Whether to add new groups to the libmap as they pop up. */ + bool libmap_init_groups; /* Queue of moves to store in libmap_hash with their goal value * at the game end. */ struct libmap_mq *lmqueue; diff --git a/playout.c b/playout.c index c17473b..12c2d40 100644 --- a/playout.c +++ b/playout.c @@ -82,8 +82,10 @@ play_random_game(struct playout_setup *setup, gamelen = 10; struct libmap_mq lmqueue = {{0}}; - if (b->libmap) + if (b->libmap) { b->lmqueue = &lmqueue; + b->libmap_init_groups = false; + } if (policy->setboard) policy->setboard(policy, b); @@ -161,7 +163,7 @@ play_random_game(struct playout_setup *setup, if (ownermap) board_ownermap_fill(ownermap, b); if (b->libmap) { - libmap_queue_process(b->libmap, b->lmqueue, b, score > 0 ? S_WHITE : S_BLACK); + libmap_queue_process(b, score > 0 ? S_WHITE : S_BLACK); b->lmqueue = NULL; } diff --git a/playout/moggy.c b/playout/moggy.c index 48b0732..e2dbb4b 100644 --- a/playout/moggy.c +++ b/playout/moggy.c @@ -507,7 +507,7 @@ playout_moggy_seqchoose(struct playout_policy *p, struct playout_setup *s, struc if (pp->atarirate > fast_random(100)) { struct libmap_mq q; q.mq.moves = 0; local_2lib_check(p, b, &b->last_move, &q); - coord_t c = libmap_queue_mqpick(b->libmap, b->lmqueue, &q); + coord_t c = libmap_queue_mqpick(b, &q); if (!is_pass(c)) return c; } @@ -516,7 +516,7 @@ playout_moggy_seqchoose(struct playout_policy *p, struct playout_setup *s, struc if (pp->nlibrate > fast_random(100)) { struct libmap_mq q; q.mq.moves = 0; local_nlib_check(p, b, &b->last_move, &q); - coord_t c = libmap_queue_mqpick(b->libmap, b->lmqueue, &q); + coord_t c = libmap_queue_mqpick(b, &q); if (!is_pass(c)) return c; } diff --git a/tactics/2lib.c b/tactics/2lib.c index f053941..f8acb17 100644 --- a/tactics/2lib.c +++ b/tactics/2lib.c @@ -243,7 +243,7 @@ group_2lib_check(struct board *b, group_t group, enum stone to_play, struct libm return; hash_t libhash = group_to_libmap(b, group); - struct libmap_move_groupinfo lmgi = { .group = group, .hash = libhash, .goal = to_play }; + struct libmap_move_groupinfo lmgi = { .group = group, .color = color, .hash = libhash, .goal = to_play }; can_atari_group(b, group, color, to_play, q, tag, lmgi, 0, use_def_no_hopeless); /* Can we counter-atari another group, if we are the defender? */ @@ -257,7 +257,6 @@ group_2lib_check(struct board *b, group_t group, enum stone to_play, struct libm if (board_group_info(b, g2).libs == 1) { /* We can capture a neighbor. */ struct move m; m.coord = board_group_info(b, g2).lib[0]; m.color = to_play; - struct libmap_move_groupinfo lmgi; lmgi.group = group; lmgi.hash = libhash; lmgi.goal = to_play; libmap_mq_add(q, m, tag, lmgi); libmap_mq_nodup(q); continue; diff --git a/tactics/goals.c b/tactics/goals.c index 1e2e6c4..5c57d92 100644 --- a/tactics/goals.c +++ b/tactics/goals.c @@ -111,6 +111,13 @@ libmap_init(struct board *b) lm->b = b; b->libmap = lm; lm->refcount = 1; + + lm->groups[0] = calloc2(board_size2(b), sizeof(*lm->groups[0])); + lm->groups[1] = calloc2(board_size2(b), sizeof(*lm->groups[1])); + for (group_t g = 1; g < board_size2(b); g++) // foreach_group + if (group_at(b, g) == g) + libmap_group_init(lm, b, g, board_at(b, g)); + return lm; } @@ -119,16 +126,41 @@ libmap_put(struct libmap_hash *lm) { if (__sync_sub_and_fetch(&lm->refcount, 1) > 0) return; + for (group_t g = 0; g < board_size2(lm->b); g++) { + if (lm->groups[0][g]) + free(lm->groups[0][g]); + if (lm->groups[1][g]) + free(lm->groups[1][g]); + } + free(lm->groups[0]); + free(lm->groups[1]); free(lm); } void -libmap_queue_process(struct libmap_hash *lm, struct libmap_mq *lmqueue, struct board *b, enum stone winner) +libmap_group_init(struct libmap_hash *lm, struct board *b, group_t g, enum stone color) +{ + assert(color == S_BLACK || color == S_WHITE); + if (lm->groups[color - 1][g]) + return; + + struct libmap_group *lmg = calloc2(1, sizeof(*lmg)); + lmg->group = g; + lmg->color = color; + lm->groups[color - 1][g] = lmg; +} + + +void +libmap_queue_process(struct board *b, enum stone winner) { + struct libmap_mq *lmqueue = b->lmqueue; assert(lmqueue->mq.moves <= MQL); for (unsigned int i = 0; i < lmqueue->mq.moves; i++) { struct libmap_move_groupinfo *gi = &lmqueue->gi[i]; struct move m = { .coord = lmqueue->mq.move[i], .color = lmqueue->color[i] }; + struct libmap_group *lg = b->libmap->groups[gi->color - 1][gi->group]; + if (!lg) continue; floating_t val; if (libmap_config.eval == LME_LOCAL || libmap_config.eval == LME_LVALUE) { val = board_local_value(libmap_config.eval == LME_LVALUE, b, gi->group, gi->goal); @@ -136,13 +168,13 @@ libmap_queue_process(struct libmap_hash *lm, struct libmap_mq *lmqueue, struct b } else { assert(libmap_config.eval == LME_GLOBAL); val = winner == gi->goal ? 1.0 : 0.0; } - libmap_add_result(lm, gi->hash, m, val, 1); + libmap_add_result(b->libmap, lg, gi->hash, m, val, 1); } lmqueue->mq.moves = 0; } void -libmap_add_result(struct libmap_hash *lm, hash_t hash, struct move move, +libmap_add_result(struct libmap_hash *lm, struct libmap_group *lg, hash_t hash, struct move move, floating_t result, int playouts) { /* If hash line is full, replacement strategy is naive - pick the @@ -150,32 +182,32 @@ libmap_add_result(struct libmap_hash *lm, hash_t hash, struct move move, * randomly. */ unsigned int min_playouts = INT_MAX; hash_t min_hash = hash; hash_t ih; - for (ih = hash; lm->hash[ih & libmap_hash_mask].hash != hash; ih++) { - // fprintf(stderr, "%"PRIhash": check %"PRIhash" (%d)\n", hash & libmap_hash_mask, ih & libmap_hash_mask, lm->hash[ih & libmap_hash_mask].moves); - if (lm->hash[ih & libmap_hash_mask].moves == 0) { - lm->hash[ih & libmap_hash_mask].hash = hash; + for (ih = hash; lg->hash[ih & libmap_hash_mask].hash != hash; ih++) { + // fprintf(stderr, "%"PRIhash": check %"PRIhash" (%d)\n", hash & libmap_hash_mask, ih & libmap_hash_mask, lg->hash[ih & libmap_hash_mask].moves); + if (lg->hash[ih & libmap_hash_mask].moves == 0) { + lg->hash[ih & libmap_hash_mask].hash = hash; break; } if (ih >= hash + libmap_hash_maxline) { /* Snatch the least used bucket. */ ih = min_hash; // fprintf(stderr, "clear %"PRIhash"\n", ih & libmap_hash_mask); - memset(&lm->hash[ih & libmap_hash_mask], 0, sizeof(lm->hash[0])); - lm->hash[ih & libmap_hash_mask].hash = hash; + memset(&lg->hash[ih & libmap_hash_mask], 0, sizeof(lg->hash[0])); + lg->hash[ih & libmap_hash_mask].hash = hash; break; } /* Keep track of least used bucket. */ - assert(lm->hash[ih & libmap_hash_mask].moves > 0); - unsigned int hp = lm->hash[ih & libmap_hash_mask].move[0].stats.playouts; + assert(lg->hash[ih & libmap_hash_mask].moves > 0); + unsigned int hp = lg->hash[ih & libmap_hash_mask].move[0].stats.playouts; if (hp < min_playouts || (hp == min_playouts && fast_random(2))) { min_playouts = hp; min_hash = ih; } } - // fprintf(stderr, "%"PRIhash": use %"PRIhash" (%d)\n", hash & libmap_hash_mask, ih & libmap_hash_mask, lm->hash[ih & libmap_hash_mask].moves); - struct libmap_context *lc = &lm->hash[ih & libmap_hash_mask]; + // fprintf(stderr, "%"PRIhash": use %"PRIhash" (%d)\n", hash & libmap_hash_mask, ih & libmap_hash_mask, lg->hash[ih & libmap_hash_mask].moves); + struct libmap_context *lc = &lg->hash[ih & libmap_hash_mask]; lc->visits++; for (int i = 0; i < lc->moves; i++) { @@ -208,8 +240,10 @@ libmap_board_move_stats(struct libmap_hash *lm, struct board *b, struct move mov neighboring_groups_list(b, board_at(b, c) == S_BLACK || board_at(b, c) == S_WHITE, move.coord, groups, groups_n, groupsbycolor_xxunused); for (int i = 0; i < groups_n; i++) { + struct libmap_group *lg = lm->groups[board_at(b, groups[i]) - 1][groups[i]]; + if (!lg) continue; hash_t hash = group_to_libmap(b, groups[i]); - struct move_stats *lp = libmap_move_stats(b->libmap, hash, move); + struct move_stats *lp = libmap_move_stats(b->libmap, lg, hash, move); if (!lp) continue; stats_merge(&tot, lp); } diff --git a/tactics/goals.h b/tactics/goals.h index 59f6f93..71201cf 100644 --- a/tactics/goals.h +++ b/tactics/goals.h @@ -60,6 +60,7 @@ void libmap_setup(char *arg); struct libmap_move_groupinfo { /* Group-relative tactical description of a move. */ + enum stone color; group_t group; hash_t hash; enum stone goal; @@ -80,6 +81,8 @@ static void libmap_mq_print(struct libmap_mq *q, struct board *b, char *label); /** Global storage of all the libmap contexts encountered. */ +struct libmap_group; + struct libmap_hash { struct board *b; /* Multiple board instances may share the same libmap hash; @@ -88,33 +91,52 @@ struct libmap_hash { * track of all the libmap uses in multi-thread environment. */ int refcount; - /* Stored statistics. */ + /* All groups existing on a "base position" (in case of the UCT + * engine, in some tree branch) will have their struct libmap_group + * pre-allocated. When recording moves for libmap groups based on + * playout data, no new libmap_group records are used and data on + * groups existing only in simulations is not kept. */ + struct libmap_group **groups[2]; // [color-1][board_size2(b)] +}; + +/* Get a new libmap. */ +struct libmap_hash *libmap_init(struct board *b); +/* Release libmap. Based on refcount, this will free it. */ +void libmap_put(struct libmap_hash *lm); + +struct libmap_group { + group_t group; + enum stone color; + + /* Stored per-group libmap contexts with statistics of moves + * performance regarding achieving a tactical goal related + * to this group (move by us == survival, move by opponent + * == kill). */ /* We store statistics in a hash table without separated chains; * if bucket is occupied, we look into the following ones, * allowing up to libmap_hash_maxline subsequent checks. */ /* XXX: We mishandle hashes >= UINT64_MAX - libmap_hash_maxline. */ -#define libmap_hash_bits 19 +#define libmap_hash_bits 11 #define libmap_hash_size (1 << libmap_hash_bits) #define libmap_hash_mask (libmap_hash_size - 1) #define libmap_hash_maxline 32 struct libmap_context hash[libmap_hash_size]; }; -/* Get a new libmap. */ -struct libmap_hash *libmap_init(struct board *b); -/* Release libmap. Based on refcount, this will free it. */ -void libmap_put(struct libmap_hash *lm); +/* Allocate a libmap group record for the given group. */ +void libmap_group_init(struct libmap_hash *lm, struct board *b, group_t g, enum stone color); /* Pick a move from @q, enqueue it in lmqueue and return its coordinate. */ -static coord_t libmap_queue_mqpick(struct libmap_hash *lm, struct libmap_mq *lmqueue, struct libmap_mq *q); +static coord_t libmap_queue_mqpick(struct board *b, struct libmap_mq *q); /* Record queued moves in the hashtable based on final position of b and winner's color. */ -void libmap_queue_process(struct libmap_hash *lm, struct libmap_mq *lmqueue, struct board *b, enum stone winner); +void libmap_queue_process(struct board *b, enum stone winner); + /* Add a result to the hashed statistics. */ -void libmap_add_result(struct libmap_hash *lm, hash_t hash, struct move move, floating_t result, int playouts); +void libmap_add_result(struct libmap_hash *lm, struct libmap_group *lg, hash_t hash, struct move move, floating_t result, int playouts); /* Get libmap context of a given group. */ -static struct libmap_context *libmap_group_context(struct libmap_hash *lm, hash_t hash); +static struct libmap_context *libmap_group_context(struct libmap_hash *lm, struct libmap_group *lg, hash_t hash); /* Get statistics of particular move in given libmap structure. */ -static struct move_stats *libmap_move_stats(struct libmap_hash *lm, hash_t hash, struct move move); +static struct move_stats *libmap_move_stats(struct libmap_hash *lm, struct libmap_group *lg, hash_t hash, struct move move); /* Get statistics of particular move on given board. */ /* (Note that this is inherently imperfect as it does not take into account * counter-atari moves.) */ @@ -163,7 +185,8 @@ libmap_mq_print(struct libmap_mq *q, struct board *b, char *label) coord2sstr(q->gi[i].group, b), q->gi[i].hash & libmap_hash_mask); struct move m = { .coord = q->mq.move[i], .color = q->color[i] }; - struct move_stats *ms = libmap_move_stats(b->libmap, q->gi[i].hash, m); + struct libmap_group *lg = b->libmap->groups[q->gi[i].color - 1][q->gi[i].group]; + struct move_stats *ms = libmap_move_stats(b->libmap, lg, q->gi[i].hash, m); if (ms) { fprintf(stderr, "(%.3f/%d)", ms->value, ms->playouts); } @@ -174,7 +197,7 @@ libmap_mq_print(struct libmap_mq *q, struct board *b, char *label) static inline int -libmap_queue_mqpick_threshold(struct libmap_hash *lm, struct libmap_mq *q) +libmap_queue_mqpick_threshold(struct libmap_hash *lm, struct board *b, struct libmap_mq *q) { /* Pick random move, up to a simple check - if a move has tactical * rating lower than threshold, prefer another. */ @@ -187,7 +210,8 @@ libmap_queue_mqpick_threshold(struct libmap_hash *lm, struct libmap_mq *q) do { int pm = p % q->mq.moves; struct move m = { .coord = q->mq.move[pm], .color = q->color[pm] }; - struct move_stats *ms = libmap_move_stats(lm, q->gi[pm].hash, m); + struct libmap_group *lg = lm->groups[q->gi[pm].color - 1][q->gi[pm].group]; + struct move_stats *ms = libmap_move_stats(lm, lg, q->gi[pm].hash, m); if (!ms || ms->value >= libmap_config.pick_threshold) { found = true; break; @@ -200,21 +224,23 @@ libmap_queue_mqpick_threshold(struct libmap_hash *lm, struct libmap_mq *q) } static inline int -libmap_queue_mqpick_ucb(struct libmap_hash *lm, struct libmap_mq *q) +libmap_queue_mqpick_ucb(struct libmap_hash *lm, struct board *b, struct libmap_mq *q) { int best_pa[BOARD_MAX_MOVES + 1], best_pn = 1; floating_t best_urgency = -9999; LM_DEBUG fprintf(stderr, "\tBandit: "); for (unsigned int p = 0; p < q->mq.moves; p++) { - struct libmap_context *lc = libmap_group_context(lm, q->gi[p].hash); - /* TODO: Consider all moves of this group, * not just mq contents. */ struct move m = { .coord = q->mq.move[p], .color = q->color[p] }; + //fprintf(stderr, "%d: %d, %d\n", p, q->gi[p].color - 1, q->gi[p].group); + struct libmap_group *lg = lm->groups[q->gi[p].color - 1][q->gi[p].group]; + struct libmap_context *lc = libmap_group_context(lm, lg, q->gi[p].hash); + struct move_stats s = !is_pass(m.coord) ? libmap_config.prior : libmap_config.tenuki_prior; int group_visits = (lc ? lc->visits : 0) + s.playouts; - struct move_stats *ms = libmap_move_stats(lm, q->gi[p].hash, m); + struct move_stats *ms = libmap_move_stats(lm, lg, q->gi[p].hash, m); if (ms) stats_merge(&s, ms); floating_t urgency = s.value + libmap_config.explore_p * sqrt(log(group_visits) / s.playouts); @@ -236,7 +262,7 @@ libmap_queue_mqpick_ucb(struct libmap_hash *lm, struct libmap_mq *q) } static inline coord_t -libmap_queue_mqpick(struct libmap_hash *lm, struct libmap_mq *lmqueue, struct libmap_mq *q) +libmap_queue_mqpick(struct board *b, struct libmap_mq *q) { if (!q->mq.moves) return pass; // nothing to do @@ -264,13 +290,13 @@ g_next_move:; unsigned int p = 0; if (q->mq.moves > 1) { - if (lm) { + if (b->libmap) { switch (libmap_config.pick_mode) { case LMP_THRESHOLD: - p = libmap_queue_mqpick_threshold(lm, q); + p = libmap_queue_mqpick_threshold(b->libmap, b, q); break; case LMP_UCB: - p = libmap_queue_mqpick_ucb(lm, q); + p = libmap_queue_mqpick_ucb(b->libmap, b, q); break; } } else { @@ -280,31 +306,32 @@ g_next_move:; if (p < 0) return pass; - if (lm) { + if (b->libmap) { struct move m = { .coord = q->mq.move[p], .color = q->color[p] }; - libmap_mq_add(lmqueue, m, q->mq.tag[p], q->gi[p]); + libmap_mq_add(b->lmqueue, m, q->mq.tag[p], q->gi[p]); } return q->mq.move[p]; } static inline struct libmap_context * -libmap_group_context(struct libmap_hash *lm, hash_t hash) +libmap_group_context(struct libmap_hash *lm, struct libmap_group *lg, hash_t hash) { + if (!lg) return NULL; hash_t ih; - for (ih = hash; lm->hash[ih & libmap_hash_mask].hash != hash; ih++) { - if (lm->hash[ih & libmap_hash_mask].moves == 0) + for (ih = hash; lg->hash[ih & libmap_hash_mask].hash != hash; ih++) { + if (lg->hash[ih & libmap_hash_mask].moves == 0) return NULL; if (ih >= hash + libmap_hash_maxline) return NULL; } - return &lm->hash[ih & libmap_hash_mask]; + return &lg->hash[ih & libmap_hash_mask]; } static inline struct move_stats * -libmap_move_stats(struct libmap_hash *lm, hash_t hash, struct move move) +libmap_move_stats(struct libmap_hash *lm, struct libmap_group *lg, hash_t hash, struct move move) { - struct libmap_context *lc = libmap_group_context(lm, hash); + struct libmap_context *lc = libmap_group_context(lm, lg, hash); if (!lc) return NULL; for (int i = 0; i < lc->moves; i++) { if (lc->move[i].move.coord == move.coord diff --git a/tactics/nlib.c b/tactics/nlib.c index c2a24d2..9cdc9fc 100644 --- a/tactics/nlib.c +++ b/tactics/nlib.c @@ -84,6 +84,7 @@ group_nlib_defense_check(struct board *b, group_t group, enum stone to_play, str continue; struct libmap_move_groupinfo lmgi; lmgi.group = group; + lmgi.color = color; lmgi.hash = group_to_libmap(b, group); lmgi.goal = to_play; can_atari_group(b, g2, stone_other(color), to_play, q, tag, lmgi, group_to_libmap(b, g2), true /* XXX */); -- 2.11.4.GIT