From 11783c2be17c8f4ad575c735c93cbb48d9dfd064 Mon Sep 17 00:00:00 2001 From: Petr Baudis Date: Fri, 28 Jan 2011 12:17:37 +0100 Subject: [PATCH] Remove the treepool feature The treepool has been a failed experiment so far, and it does not seem likely we will get to make it a real playing strength contribution anytime soon. Therefore, let's leave it just in the git history. I have kept the 'significant node' feature since it is used also in some unmerged branches, is a small piece of code and can come useful for other stuff I have in mind. --- uct/internal.h | 11 ------ uct/uct.c | 56 +-------------------------- uct/walk.c | 120 +-------------------------------------------------------- 3 files changed, 2 insertions(+), 185 deletions(-) diff --git a/uct/internal.h b/uct/internal.h index 7466991..324df89 100644 --- a/uct/internal.h +++ b/uct/internal.h @@ -68,17 +68,6 @@ struct uct { int val_points; bool val_extra; - int treepool_chance[2]; - int treepool_size; - enum treepool_type { - UTT_RAVE_PLAYOUTS, - UTT_RAVE_VALUE, - UTT_UCT_PLAYOUTS, - UTT_UCT_VALUE, - UTT_EVALUATE, - } treepool_type; - int treepool_pickfactor; - int random_policy_chance; int local_tree; int tenuki_d; diff --git a/uct/uct.c b/uct/uct.c index be2fcf9..e2fdc65 100644 --- a/uct/uct.c +++ b/uct/uct.c @@ -912,67 +912,13 @@ uct_state_init(char *arg, struct board *b) /** Other heuristics */ } else if (!strcasecmp(optname, "significant_threshold") && optval) { - /* Some heuristics (treepool) rely + /* Some heuristics (XXX: none in mainline) rely * on the knowledge of the last "significant" * node in the descent. Such a node is * considered reasonably trustworthy to carry * some meaningful information in the values * of the node and its children. */ u->significant_threshold = atoi(optval); - } else if (!strcasecmp(optname, "treepool_chance") && optval) { - /* Chance of applying the treepool heuristic: - * one of the best N children of the last - * significant node is tried on each turn - * of the simulation. */ - /* This is in form of two numbers: - * PREMOVE:POSTMOVE. Each is percentage - * value, one is the chance of the move - * tried before playout policy, one is the - * chance of it being applied if the policy - * has not picked anymove. */ - char *optval2 = strchr(optval, ':'); - if (!optval2) { - fprintf(stderr, "uct: treepool_chance takes two comma-separated numbers\n"); - exit(1); - } - u->treepool_chance[0] = atoi(optval); - optval = ++optval2; - u->treepool_chance[1] = atoi(optval); - } else if (!strcasecmp(optname, "treepool_size") && optval) { - /* Number of top significant children - * to pick from. Too low means low effect, - * too high means even lousy moves are - * played. */ - u->treepool_size = atoi(optval); - } else if (!strcasecmp(optname, "treepool_type") && optval) { - /* How to sort the children. */ - if (!strcasecmp(optval, "rave_playouts")) - u->treepool_type = UTT_RAVE_PLAYOUTS; - else if (!strcasecmp(optval, "rave_value")) - u->treepool_type = UTT_RAVE_VALUE; - else if (!strcasecmp(optval, "uct_playouts")) - u->treepool_type = UTT_UCT_PLAYOUTS; - else if (!strcasecmp(optval, "uct_value")) - u->treepool_type = UTT_UCT_VALUE; - else if (!strcasecmp(optval, "evaluate")) - /* The proper combination of RAVE, - * UCT and prior, as used through - * descent. */ - u->treepool_type = UTT_EVALUATE; - else { - fprintf(stderr, "uct: unknown treepool_type %s\n", optval); - exit(1); - } - } else if (!strcasecmp(optname, "treepool_pickfactor") && optval) { - /* Pick factor influencing children choice. - * By default (if this is 0 or 10), coords - * have uniform probability to be chosen; - * otherwise, children are tried from best - * to worst, each picked with probability - * (1/n * pickfactor/10). - * I.e., better children may be preferred - * if pickfactor > 10. */ - u->treepool_pickfactor = atoi(optval); /** Distributed engine slaves setup */ diff --git a/uct/walk.c b/uct/walk.c index 8f5e45a..b657e72 100644 --- a/uct/walk.c +++ b/uct/walk.c @@ -99,49 +99,13 @@ struct uct_playout_callback { struct uct *uct; struct tree *tree; struct tree_node *lnode; - - coord_t *treepool[2]; - int treepool_n[2]; }; static coord_t uct_playout_hook(struct playout_policy *playout, struct playout_setup *setup, struct board *b, enum stone color, int mode) { - struct uct_playout_callback *upc = setup->hook_data; - struct uct *u = upc->uct; - - if (UDEBUGL(8)) - fprintf(stderr, "treepool check [%d] %d, %p,%p\n", mode, u->treepool_chance[mode], upc->treepool[0], upc->treepool[1]); - - if (u->treepool_chance[mode] > fast_random(100) && upc->treepool[color - 1]) { - assert(upc->treepool_n[color - 1] > 0); - if (UDEBUGL(8)) { - fprintf(stderr, "Treepool: "); - for (int i = 0; i < upc->treepool_n[color - 1]; i++) - fprintf(stderr, "%s ", coord2sstr(upc->treepool[color - 1][i], b)); - fprintf(stderr, "\n"); - } - - coord_t treepool_move = pass; - if (u->treepool_pickfactor) { - /* With pickfactor=10, we get uniform distribution. */ - int prob = 1000 * u->treepool_pickfactor / (upc->treepool_n[color - 1] * 10); - for (int i = 0; i < upc->treepool_n[color - 1]; i++) { - treepool_move = upc->treepool[color - 1][i]; - if (prob > fast_random(1000)) break; - } - } else { - treepool_move = upc->treepool[color - 1][fast_random(upc->treepool_n[color - 1])]; - } - if (UDEBUGL(7)) - fprintf(stderr, "Treepool pick <%d> %s,%s\n", - upc->treepool_n[color - 1], - stone2str(color), coord2sstr(treepool_move, b)); - - if (board_is_valid_play(b, color, treepool_move)) - return treepool_move; - } + /* XXX: This is used in some non-master branches. */ return pass; } @@ -157,68 +121,6 @@ uct_playout_postpolicy(struct playout_policy *playout, struct playout_setup *set return uct_playout_hook(playout, setup, b, color, 1); } -double -treepool_node_value(struct uct *u, struct tree *tree, int parity, struct tree_node *node) -{ - /* XXX: Playouts get cast to double */ - switch (u->treepool_type) { - case UTT_RAVE_PLAYOUTS: - return node->amaf.playouts; - case UTT_RAVE_VALUE: - return tree_node_get_value(tree, parity, node->amaf.value); - case UTT_UCT_PLAYOUTS: - return node->u.playouts; - case UTT_UCT_VALUE: - return tree_node_get_value(tree, parity, node->u.value); - case UTT_EVALUATE: - { - struct uct_descent d = { .node = node }; - assert(u->policy->evaluate); - return u->policy->evaluate(u->policy, tree, &d, parity); - } - default: assert(0); - } - return -1; -} - -static void -treepool_setup(struct uct_playout_callback *upc, struct board *b, struct tree_node *node, int color) -{ - struct uct *u = upc->uct; - int parity = ((node->depth ^ upc->tree->root->depth) & 1) ? -1 : 1; - - /* XXX: Naive O(N^2) way. */ - for (int i = 0; i < u->treepool_size; i++) { - /* For each item, find the highest - * node not in the pool yet. */ - struct tree_node *best = NULL; - double best_val = -1; - - assert(node->children && is_pass(node->children->coord)); - for (struct tree_node *ni = node->children->sibling; ni; ni = ni->sibling) { - /* Do we already have it? */ - bool have = false; - for (int j = 0; j < upc->treepool_n[color]; j++) { - if (upc->treepool[color][j] == ni->coord) { - have = true; - break; - } - } - if (have) - continue; - - double i_val = treepool_node_value(u, upc->tree, parity, ni); - if (i_val > best_val) { - best = ni; - best_val = i_val; - } - } - - if (!best) break; - upc->treepool[color][upc->treepool_n[color]++] = best->coord; - } -} - static int uct_leaf_node(struct uct *u, struct board *b, enum stone player_color, @@ -255,26 +157,6 @@ uct_leaf_node(struct uct *u, struct board *b, enum stone player_color, .lnode = NULL, }; - coord_t pool[2][u->treepool_size]; - if (u->treepool_chance[0] + u->treepool_chance[1] > 0) { - for (int color = 0; color < 2; color++) { - /* Prepare tree-based pool of moves to try forcing - * during the playout. */ - /* We consider the children of the last significant - * node, picking top N choices. */ - struct tree_node *n = significant[color]; - if (!n || !n->children || !n->children->sibling) { - /* No significant node, or it's childless or has - * only pass as its child. */ - upc.treepool[color] = NULL; - upc.treepool_n[color] = 0; - } else { - upc.treepool[color] = (coord_t *) &pool[color]; - treepool_setup(&upc, b, n, color); - } - } - } - struct playout_setup ps = { .gamelen = u->gamelen, .mercymin = u->mercymin, -- 2.11.4.GIT