can_atari_group(): When switching to selfatari cousin, check defense_is_hopeless()
[pachi/json.git] / uct / policy / ucb1amaf.c
blobc81dda32b72449d359d884816d2288de2d2ef94a
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 UCB1 policy with an extra AMAF heuristics. */
17 struct ucb1_policy_amaf {
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;
27 unsigned int equiv_rave;
28 bool check_nakade;
29 bool sylvain_rave;
30 /* Coefficient of local tree values embedded in RAVE. */
31 floating_t ltree_rave;
32 /* Coefficient of criticality embedded in RAVE. */
33 floating_t crit_rave;
34 int crit_min_playouts;
35 bool crit_negative;
36 bool crit_amaf;
40 static inline floating_t fast_sqrt(unsigned int x)
42 static const floating_t table[] = {
43 0, 1, 1.41421356237309504880, 1.73205080756887729352,
44 2.00000000000000000000, 2.23606797749978969640,
45 2.44948974278317809819, 2.64575131106459059050,
46 2.82842712474619009760, 3.00000000000000000000,
47 3.16227766016837933199, 3.31662479035539984911,
48 3.46410161513775458705, 3.60555127546398929311,
49 3.74165738677394138558, 3.87298334620741688517,
50 4.00000000000000000000, 4.12310562561766054982,
51 4.24264068711928514640, 4.35889894354067355223,
52 4.47213595499957939281, 4.58257569495584000658,
53 4.69041575982342955456, 4.79583152331271954159,
54 4.89897948556635619639, 5.00000000000000000000,
55 5.09901951359278483002, 5.19615242270663188058,
56 5.29150262212918118100, 5.38516480713450403125,
57 5.47722557505166113456, 5.56776436283002192211,
58 5.65685424949238019520, 5.74456264653802865985,
59 5.83095189484530047087, 5.91607978309961604256,
60 6.00000000000000000000, 6.08276253029821968899,
61 6.16441400296897645025, 6.24499799839839820584,
62 6.32455532033675866399, 6.40312423743284868648,
63 6.48074069840786023096, 6.55743852430200065234,
64 6.63324958071079969822, 6.70820393249936908922,
65 6.78232998312526813906, 6.85565460040104412493,
66 6.92820323027550917410, 7.00000000000000000000,
67 7.07106781186547524400, 7.14142842854284999799,
68 7.21110255092797858623, 7.28010988928051827109,
69 7.34846922834953429459, 7.41619848709566294871,
70 7.48331477354788277116, 7.54983443527074969723,
71 7.61577310586390828566, 7.68114574786860817576,
72 7.74596669241483377035, 7.81024967590665439412,
73 7.87400787401181101968, 7.93725393319377177150,
75 if (x < sizeof(table) / sizeof(*table)) {
76 return table[x];
77 } else {
78 return sqrt(x);
82 #define LTREE_DEBUG if (0)
83 static floating_t inline
84 ucb1rave_evaluate(struct uct_policy *p, struct tree *tree, struct uct_descent *descent, int parity)
86 struct ucb1_policy_amaf *b = p->data;
87 struct tree_node *node = descent->node;
88 struct tree_node *lnode = descent->lnode;
90 struct move_stats n = node->u, r = node->amaf;
91 if (p->uct->amaf_prior) {
92 stats_merge(&r, &node->prior);
93 } else {
94 stats_merge(&n, &node->prior);
97 /* Local tree heuristics. */
98 if (p->uct->local_tree && b->ltree_rave > 0 && lnode) {
99 struct move_stats l = lnode->u;
100 l.playouts = ((floating_t) l.playouts) * b->ltree_rave / LTREE_PLAYOUTS_MULTIPLIER;
101 LTREE_DEBUG fprintf(stderr, "[ltree] adding [%s] %f%%%d to [%s] RAVE %f%%%d\n",
102 coord2sstr(lnode->coord, tree->board), l.value, l.playouts,
103 coord2sstr(node->coord, tree->board), r.value, r.playouts);
104 stats_merge(&r, &l);
107 /* Criticality heuristics. */
108 if (b->crit_rave > 0 && node->u.playouts > b->crit_min_playouts) {
109 floating_t crit = tree_node_criticality(tree, node);
110 if (b->crit_negative || crit > 0) {
111 struct move_stats c = {
112 .value = tree_node_get_value(tree, parity, 1.0f),
113 .playouts = crit * r.playouts * b->crit_rave
115 LTREE_DEBUG fprintf(stderr, "[crit] adding %f%%%d to [%s] RAVE %f%%%d\n",
116 c.value, c.playouts,
117 coord2sstr(node->coord, tree->board), r.value, r.playouts);
118 stats_merge(&r, &c);
123 floating_t value = 0;
124 if (n.playouts) {
125 if (r.playouts) {
126 /* At the beginning, beta is at 1 and RAVE is used.
127 * At b->equiv_rate, beta is at 1/3 and gets steeper on. */
128 floating_t beta;
129 if (b->sylvain_rave) {
130 beta = (floating_t) r.playouts / (r.playouts + n.playouts
131 + (floating_t) n.playouts * r.playouts / b->equiv_rave);
132 } else {
133 /* XXX: This can be cached in descend; but we don't use this by default. */
134 beta = sqrt(b->equiv_rave / (3 * node->parent->u.playouts + b->equiv_rave));
137 value = beta * r.value + (1.f - beta) * n.value;
138 } else {
139 value = n.value;
141 } else if (r.playouts) {
142 value = r.value;
144 descent->value.playouts = r.playouts + n.playouts;
145 descent->value.value = value;
146 return tree_node_get_value(tree, parity, value);
149 void
150 ucb1rave_descend(struct uct_policy *p, struct tree *tree, struct uct_descent *descent, int parity, bool allow_pass)
152 struct ucb1_policy_amaf *b = p->data;
153 floating_t nconf = 1.f;
154 if (b->explore_p > 0)
155 nconf = sqrt(log(descent->node->u.playouts + descent->node->prior.playouts));
157 uctd_try_node_children(tree, descent, allow_pass, parity, p->uct->tenuki_d, di, urgency) {
158 struct tree_node *ni = di.node;
159 urgency = ucb1rave_evaluate(p, tree, &di, parity);
161 if (ni->u.playouts > 0 && b->explore_p > 0) {
162 urgency += b->explore_p * nconf / fast_sqrt(ni->u.playouts);
164 } else if (ni->u.playouts + ni->amaf.playouts + ni->prior.playouts == 0) {
165 /* assert(!u->even_eqex); */
166 urgency = b->fpu;
168 } uctd_set_best_child(di, urgency);
170 uctd_get_best_child(descent);
174 void
175 ucb1amaf_update(struct uct_policy *p, struct tree *tree, struct tree_node *node,
176 enum stone node_color, enum stone player_color,
177 struct playout_amafmap *map, struct board *final_board,
178 floating_t result)
180 struct ucb1_policy_amaf *b = p->data;
181 enum stone winner_color = result > 0.5 ? S_BLACK : S_WHITE;
182 enum stone child_color = stone_other(node_color);
184 #if 0
185 struct board bb; bb.size = 9+2;
186 for (struct tree_node *ni = node; ni; ni = ni->parent)
187 fprintf(stderr, "%s ", coord2sstr(ni->coord, &bb));
188 fprintf(stderr, "[color %d] update result %d (color %d)\n",
189 node_color, result, player_color);
190 #endif
192 while (node) {
193 if (node->parent == NULL)
194 assert(tree->root_color == stone_other(child_color));
196 if (!b->crit_amaf) {
197 stats_add_result(&node->winner_owner, board_at(final_board, node->coord) == winner_color ? 1.0 : 0.0, 1);
198 stats_add_result(&node->black_owner, board_at(final_board, node->coord) == S_BLACK ? 1.0 : 0.0, 1);
200 stats_add_result(&node->u, result, 1);
201 if (amaf_nakade(map->map[node->coord]))
202 amaf_op(map->map[node->coord], -);
204 /* This loop ignores symmetry considerations, but they should
205 * matter only at a point when AMAF doesn't help much. */
206 assert(map->game_baselen >= 0);
207 for (struct tree_node *ni = node->children; ni; ni = ni->sibling) {
208 enum stone amaf_color = map->map[ni->coord];
209 assert(amaf_color != S_OFFBOARD);
210 if (amaf_color == S_NONE)
211 continue;
212 if (amaf_nakade(map->map[ni->coord])) {
213 if (!b->check_nakade)
214 continue;
215 unsigned int i;
216 for (i = map->game_baselen; i < map->gamelen; i++)
217 if (map->game[i].coord == ni->coord
218 && map->game[i].color == child_color)
219 break;
220 if (i == map->gamelen)
221 continue;
222 amaf_color = child_color;
225 floating_t nres = result;
226 if (amaf_color != child_color) {
227 continue;
229 /* For child_color != player_color, we still want
230 * to record the result unmodified; in that case,
231 * we will correctly negate them at the descend phase. */
233 if (b->crit_amaf) {
234 stats_add_result(&ni->winner_owner, board_at(final_board, ni->coord) == winner_color ? 1.0 : 0.0, 1);
235 stats_add_result(&ni->black_owner, board_at(final_board, ni->coord) == S_BLACK ? 1.0 : 0.0, 1);
237 stats_add_result(&ni->amaf, nres, 1);
239 #if 0
240 struct board bb; bb.size = 9+2;
241 fprintf(stderr, "* %s<%"PRIhash"> -> %s<%"PRIhash"> [%d/%f => %d/%f]\n",
242 coord2sstr(node->coord, &bb), node->hash,
243 coord2sstr(ni->coord, &bb), ni->hash,
244 player_color, result, child_color, nres);
245 #endif
248 if (!is_pass(node->coord)) {
249 map->game_baselen--;
251 node = node->parent; child_color = stone_other(child_color);
256 struct uct_policy *
257 policy_ucb1amaf_init(struct uct *u, char *arg)
259 struct uct_policy *p = calloc2(1, sizeof(*p));
260 struct ucb1_policy_amaf *b = calloc2(1, sizeof(*b));
261 p->uct = u;
262 p->data = b;
263 p->choose = uctp_generic_choose;
264 p->winner = uctp_generic_winner;
265 p->evaluate = ucb1rave_evaluate;
266 p->descend = ucb1rave_descend;
267 p->update = ucb1amaf_update;
268 p->wants_amaf = true;
270 b->explore_p = 0; // 0.02 can be also good on 19x19 with prior=eqex=40
271 b->equiv_rave = 3000;
272 b->fpu = INFINITY;
273 b->check_nakade = true;
274 b->sylvain_rave = true;
275 b->ltree_rave = 0.75f;
277 b->crit_rave = 1.0f;
278 b->crit_min_playouts = 2000;
279 b->crit_negative = 1;
280 b->crit_amaf = 0;
282 if (arg) {
283 char *optspec, *next = arg;
284 while (*next) {
285 optspec = next;
286 next += strcspn(next, ":");
287 if (*next) { *next++ = 0; } else { *next = 0; }
289 char *optname = optspec;
290 char *optval = strchr(optspec, '=');
291 if (optval) *optval++ = 0;
293 if (!strcasecmp(optname, "explore_p")) {
294 b->explore_p = atof(optval);
295 } else if (!strcasecmp(optname, "fpu") && optval) {
296 b->fpu = atof(optval);
297 } else if (!strcasecmp(optname, "equiv_rave") && optval) {
298 b->equiv_rave = atof(optval);
299 } else if (!strcasecmp(optname, "sylvain_rave")) {
300 b->sylvain_rave = !optval || *optval == '1';
301 } else if (!strcasecmp(optname, "check_nakade")) {
302 b->check_nakade = !optval || *optval == '1';
303 } else if (!strcasecmp(optname, "ltree_rave") && optval) {
304 b->ltree_rave = atof(optval);
305 } else if (!strcasecmp(optname, "crit_rave") && optval) {
306 b->crit_rave = atof(optval);
307 } else if (!strcasecmp(optname, "crit_min_playouts") && optval) {
308 b->crit_min_playouts = atoi(optval);
309 } else if (!strcasecmp(optname, "crit_negative")) {
310 b->crit_negative = !optval || *optval == '1';
311 } else if (!strcasecmp(optname, "crit_amaf")) {
312 b->crit_amaf = !optval || *optval == '1';
313 } else {
314 fprintf(stderr, "ucb1amaf: Invalid policy argument %s or missing value\n",
315 optname);
316 exit(1);
321 return p;