fast_frandom() always returns float, not floating_t
[pachi/t.git] / uct / policy / ucb1.c
blobbd439ed9758083b52cca34bdeaa2e64278543b2b
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"
13 #include "uct/policy/generic.h"
15 /* This implements the basic UCB1 policy. */
17 struct 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. */
22 floating_t explore_p;
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. */
26 floating_t fpu;
30 void
31 ucb1_descend(struct uct_policy *p, struct tree *tree, struct uct_descent *descent, 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 floating_t xpl = log(descent->node->u.playouts + descent->node->prior.playouts);
41 uctd_try_node_children(tree, descent, allow_pass, parity, p->uct->tenuki_d, di, urgency) {
42 struct tree_node *ni = di.node;
43 int uct_playouts = ni->u.playouts + ni->prior.playouts;
45 /* XXX: We don't take local-tree information into account. */
47 if (uct_playouts) {
48 urgency = (ni->u.playouts * tree_node_get_value(tree, parity, ni->u.value)
49 + ni->prior.playouts * tree_node_get_value(tree, parity, ni->prior.value))
50 / uct_playouts;
51 urgency += b->explore_p * sqrt(xpl / uct_playouts);
52 } else {
53 urgency = b->fpu;
55 } uctd_set_best_child(di, urgency);
57 uctd_get_best_child(descent);
60 void
61 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, struct board *final_board, floating_t result)
63 /* It is enough to iterate by a single chain; we will
64 * update all the preceding positions properly since
65 * they had to all occur in all branches, only in
66 * different order. */
67 enum stone winner_color = result > 0.5 ? S_BLACK : S_WHITE;
68 for (; node; node = node->parent) {
69 stats_add_result(&node->u, result, 1);
70 if (!is_pass(node_coord(node))) {
71 stats_add_result(&node->winner_owner, board_at(final_board, node_coord(node)) == winner_color ? 1.0 : 0.0, 1);
72 stats_add_result(&node->black_owner, board_at(final_board, node_coord(node)) == S_BLACK ? 1.0 : 0.0, 1);
78 struct uct_policy *
79 policy_ucb1_init(struct uct *u, char *arg)
81 struct uct_policy *p = calloc2(1, sizeof(*p));
82 struct ucb1_policy *b = calloc2(1, sizeof(*b));
83 p->uct = u;
84 p->data = b;
85 p->descend = ucb1_descend;
86 p->choose = uctp_generic_choose;
87 p->update = ucb1_update;
89 b->explore_p = 0.2;
90 b->fpu = 1.1; //INFINITY;
92 if (arg) {
93 char *optspec, *next = arg;
94 while (*next) {
95 optspec = next;
96 next += strcspn(next, ":");
97 if (*next) { *next++ = 0; } else { *next = 0; }
99 char *optname = optspec;
100 char *optval = strchr(optspec, '=');
101 if (optval) *optval++ = 0;
103 if (!strcasecmp(optname, "explore_p") && optval) {
104 b->explore_p = atof(optval);
105 } else if (!strcasecmp(optname, "fpu") && optval) {
106 b->fpu = atof(optval);
107 } else {
108 fprintf(stderr, "ucb1: Invalid policy argument %s or missing value\n",
109 optname);
110 exit(1);
115 return p;