UCB*: urg_randoma, urg_randomm for urgency randomization
[pachi/peepo.git] / uct / policy / ucb1.c
blob42a12e355ed0da2986fd61c7315feb4e4dc14cdf
1 #include <assert.h>
2 #include <math.h>
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <string.h>
7 #include "board.h"
8 #include "debug.h"
9 #include "move.h"
10 #include "random.h"
11 #include "uct/internal.h"
12 #include "uct/tree.h"
14 /* This implements the basic UCB1 policy. */
16 struct ucb1_policy {
17 /* This is what the Modification of UCT with Patterns in Monte Carlo Go
18 * paper calls 'p'. Original UCB has this on 2, but this seems to
19 * produce way too wide searches; reduce this to get deeper and
20 * narrower readouts - try 0.2. */
21 float explore_p;
22 /* First Play Urgency - if set to less than infinity (the MoGo paper
23 * above reports 1.0 as the best), new branches are explored only
24 * if none of the existing ones has higher urgency than fpu. */
25 float fpu;
26 /* Equivalent experience for prior knowledge. MoGo paper recommends
27 * 50 playouts per source. */
28 int eqex, gp_eqex, policy_eqex;
29 int urg_randoma, urg_randomm;
33 struct tree_node *
34 ucb1_choose(struct uct_policy *p, struct tree_node *node, struct board *b, enum stone color)
36 struct tree_node *nbest = NULL;
37 for (struct tree_node *ni = node->children; ni; ni = ni->sibling)
38 // we compare playouts and choose the best-explored
39 // child; comparing values is more brittle
40 if (!nbest || ni->u.playouts > nbest->u.playouts) {
41 /* Play pass only if we can afford scoring */
42 if (is_pass(ni->coord)) {
43 float score = board_official_score(b);
44 if (color == S_BLACK)
45 score = -score;
46 //fprintf(stderr, "%d score %f\n", color, score);
47 if (score <= 0)
48 continue;
50 nbest = ni;
52 return nbest;
56 struct tree_node *
57 ucb1_descend(struct uct_policy *p, struct tree *tree, struct tree_node *node, int parity, bool allow_pass)
59 /* We want to count in the prior stats here after all. Otherwise,
60 * nodes with positive prior will get explored _LESS_ since the
61 * urgency will be always higher; even with normal FPU because
62 * of the explore coefficient. */
64 struct ucb1_policy *b = p->data;
65 float xpl = log(node->u.playouts + node->prior.playouts) * b->explore_p;
67 struct tree_node *nbest = node->children;
68 float best_urgency = -9999;
69 for (struct tree_node *ni = node->children; ni; ni = ni->sibling) {
70 /* Do not consider passing early. */
71 if (likely(!allow_pass) && unlikely(is_pass(ni->coord)))
72 continue;
73 int uct_playouts = ni->u.playouts + ni->prior.playouts;
74 ni->prior.value = (float)ni->prior.wins / ni->prior.playouts;
75 float urgency = uct_playouts ? (parity > 0 ? ni->u.value : 1 - ni->u.value) + sqrt(xpl / uct_playouts) : b->fpu;
77 #if 0
79 struct board b2; b2.size = 9;
80 fprintf(stderr, "[%s -> %s] UCB1 urgency %f (%f + %f : %f)\n", coord2sstr(node->coord, &b2), coord2sstr(ni->coord, &b2), urgency, ni->u.value, sqrt(xpl / ni->u.playouts), b->fpu);
82 #endif
83 if (b->urg_randoma)
84 urgency += (float)(fast_random(b->urg_randoma) - b->urg_randoma / 2) / 1000;
85 if (b->urg_randomm)
86 urgency *= (float)(fast_random(b->urg_randomm) + 5) / b->urg_randomm;
87 if (urgency > best_urgency) {
88 best_urgency = urgency;
89 nbest = ni;
92 return nbest;
95 void
96 ucb1_prior(struct uct_policy *p, struct tree *tree, struct tree_node *node, struct board *b, enum stone color, int parity)
98 /* Initialization of UCT values based on prior knowledge */
99 struct ucb1_policy *pp = p->data;
101 #if 0
102 /* Q_{even} */
103 /* This somehow does not work at all. */
104 node->prior.playouts += p->eqex;
105 node->prior.wins += p->eqex / 2;
106 #endif
108 /* Q_{grandparent} */
109 if (pp->gp_eqex && node->parent && node->parent->parent && node->parent->parent->parent) {
110 struct tree_node *gpp = node->parent->parent->parent;
111 for (struct tree_node *ni = gpp->children; ni; ni = ni->sibling) {
112 /* Be careful not to emphasize too random results. */
113 if (ni->coord == node->coord && ni->u.playouts > pp->gp_eqex) {
114 node->prior.playouts += pp->gp_eqex;
115 node->prior.wins += pp->gp_eqex * ni->u.wins / ni->u.playouts;
116 node->hints |= 1;
121 /* Q_{playout-policy} */
122 if (pp->policy_eqex) {
123 float assess = NAN;
124 struct playout_policy *playout = p->uct->playout;
125 if (playout->assess) {
126 struct move m = { node->coord, color };
127 assess = playout->assess(playout, b, &m);
129 if (!isnan(assess)) {
130 if (parity < 0)
131 assess = 1 - assess;
132 node->prior.playouts += pp->policy_eqex;
133 node->prior.wins += pp->policy_eqex * assess;
134 node->hints |= 2;
138 if (node->prior.playouts) {
139 node->prior.value = (float) node->prior.wins / node->prior.playouts;
140 tree_update_node_value(node, true);
143 //fprintf(stderr, "%s,%s prior: %d/%d = %f (%f)\n", coord2sstr(node->parent->coord, b), coord2sstr(node->coord, b), node->prior.wins, node->prior.playouts, node->prior.value, assess);
146 void
147 ucb1_update(struct uct_policy *p, struct tree_node *node, enum stone color, struct playout_amafmap *map, int result)
149 /* It is enough to iterate by a single chain; we will
150 * update all the preceding positions properly since
151 * they had to all occur in all branches, only in
152 * different order. */
153 for (; node; node = node->parent) {
154 node->u.playouts++;
155 node->u.wins += result;
156 tree_update_node_value(node, true);
161 struct uct_policy *
162 policy_ucb1_init(struct uct *u, char *arg)
164 struct uct_policy *p = calloc(1, sizeof(*p));
165 struct ucb1_policy *b = calloc(1, sizeof(*b));
166 p->uct = u;
167 p->data = b;
168 p->descend = ucb1_descend;
169 p->choose = ucb1_choose;
170 p->update = ucb1_update;
172 b->explore_p = 0.2;
173 b->fpu = INFINITY;
174 b->gp_eqex = b->policy_eqex = -1;
176 if (arg) {
177 char *optspec, *next = arg;
178 while (*next) {
179 optspec = next;
180 next += strcspn(next, ":");
181 if (*next) { *next++ = 0; } else { *next = 0; }
183 char *optname = optspec;
184 char *optval = strchr(optspec, '=');
185 if (optval) *optval++ = 0;
187 if (!strcasecmp(optname, "explore_p") && optval) {
188 b->explore_p = atof(optval);
189 } else if (!strcasecmp(optname, "prior")) {
190 b->eqex = optval ? atoi(optval) : 50;
191 if (b->eqex)
192 p->prior = ucb1_prior;
193 } else if (!strcasecmp(optname, "prior_gp") && optval) {
194 b->gp_eqex = atoi(optval);
195 } else if (!strcasecmp(optname, "prior_policy") && optval) {
196 b->policy_eqex = atoi(optval);
197 } else if (!strcasecmp(optname, "fpu") && optval) {
198 b->fpu = atof(optval);
199 } else if (!strcasecmp(optname, "urg_randoma") && optval) {
200 b->urg_randoma = atoi(optval);
201 } else if (!strcasecmp(optname, "urg_randomm") && optval) {
202 b->urg_randomm = atoi(optval);
203 } else {
204 fprintf(stderr, "ucb1: Invalid policy argument %s or missing value\n", optname);
209 if (b->gp_eqex < 0) b->gp_eqex = b->eqex;
210 if (b->policy_eqex < 0) b->policy_eqex = b->eqex;
212 return p;