11 #include "uct/internal.h"
13 #include "uct/policy/generic.h"
15 /* This implements the basic UCB1 policy. */
18 /* This is what the Modification of UCT with Patterns in Monte Carlo Go
19 * paper calls 'p'. Original UCB has this on 2, but this seems to
20 * produce way too wide searches; reduce this to get deeper and
21 * narrower readouts - try 0.2. */
23 /* First Play Urgency - if set to less than infinity (the MoGo paper
24 * above reports 1.0 as the best), new branches are explored only
25 * if none of the existing ones has higher urgency than fpu. */
31 ucb1_descend(struct uct_policy
*p
, void **state
, struct tree
*tree
, struct tree_node
*node
, int parity
, bool allow_pass
)
33 /* We want to count in the prior stats here after all. Otherwise,
34 * nodes with positive prior will get explored _LESS_ since the
35 * urgency will be always higher; even with normal FPU because
36 * of the explore coefficient. */
38 struct ucb1_policy
*b
= p
->data
;
39 float xpl
= log(node
->u
.playouts
+ node
->prior
.playouts
);
41 uctd_try_node_children(node
, allow_pass
, ni
, urgency
) {
42 int uct_playouts
= ni
->u
.playouts
+ ni
->prior
.playouts
;
45 urgency
= (ni
->u
.playouts
* tree_node_get_value(tree
, parity
, ni
->u
.value
)
46 + ni
->prior
.playouts
* tree_node_get_value(tree
, parity
, ni
->prior
.value
))
48 urgency
+= b
->explore_p
* sqrt(xpl
/ uct_playouts
);
52 } uctd_set_best_child(ni
, urgency
);
53 return uctd_get_best_child();
57 ucb1_update(struct uct_policy
*p
, struct tree
*tree
, struct tree_node
*node
, enum stone node_color
, enum stone player_color
, struct playout_amafmap
*map
, float result
)
59 /* It is enough to iterate by a single chain; we will
60 * update all the preceding positions properly since
61 * they had to all occur in all branches, only in
63 for (; node
; node
= node
->parent
) {
64 stats_add_result(&node
->u
, result
, 1);
70 policy_ucb1_init(struct uct
*u
, char *arg
)
72 struct uct_policy
*p
= calloc(1, sizeof(*p
));
73 struct ucb1_policy
*b
= calloc(1, sizeof(*b
));
76 p
->descend
= ucb1_descend
;
77 p
->choose
= uctp_generic_choose
;
78 p
->update
= ucb1_update
;
81 b
->fpu
= 1.1; //INFINITY;
84 char *optspec
, *next
= arg
;
87 next
+= strcspn(next
, ":");
88 if (*next
) { *next
++ = 0; } else { *next
= 0; }
90 char *optname
= optspec
;
91 char *optval
= strchr(optspec
, '=');
92 if (optval
) *optval
++ = 0;
94 if (!strcasecmp(optname
, "explore_p") && optval
) {
95 b
->explore_p
= atof(optval
);
96 } else if (!strcasecmp(optname
, "fpu") && optval
) {
97 b
->fpu
= atof(optval
);
99 fprintf(stderr
, "ucb1: Invalid policy argument %s or missing value\n",