selfatari_cousin(): Suggest counter-captures
[pachi/peepo.git] / uct / policy / ucb1amaf.c
blob821965bc6040279a583a35194898f177fe68b826
1 #include <assert.h>
2 #include <limits.h>
3 #include <math.h>
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <string.h>
8 //#define DEBUG
10 #include "board.h"
11 #include "debug.h"
12 #include "move.h"
13 #include "random.h"
14 #include "tactics/util.h"
15 #include "uct/internal.h"
16 #include "uct/tree.h"
17 #include "uct/policy/generic.h"
19 /* This implements the UCB1 policy with an extra AMAF heuristics. */
21 struct ucb1_policy_amaf {
22 /* This is what the Modification of UCT with Patterns in Monte Carlo Go
23 * paper calls 'p'. Original UCB has this on 2, but this seems to
24 * produce way too wide searches; reduce this to get deeper and
25 * narrower readouts - try 0.2. */
26 floating_t explore_p;
27 /* Rescale virtual loss value to square root of #threads. This mitigates
28 * the number of virtual losses added in case of a large amount of
29 * threads; it seems that with linear virtual losses, overly diverse
30 * exploration caused by this may cause a wrong mean value computed
31 * for the parent node. */
32 bool vloss_sqrt;
33 /* In distributed mode, encourage different slaves to work on different
34 * parts of the tree by adding virtual wins to different nodes. */
35 int virtual_win;
36 int root_virtual_win;
37 int vwin_min_playouts;
38 /* First Play Urgency - if set to less than infinity (the MoGo paper
39 * above reports 1.0 as the best), new branches are explored only
40 * if none of the existing ones has higher urgency than fpu. */
41 floating_t fpu;
42 unsigned int equiv_rave;
43 bool sylvain_rave;
44 /* Give more weight to moves played earlier. */
45 int distance_rave;
46 /* Give 0 or negative rave bonus to ko threats before taking the ko.
47 1=normal bonus, 0=no bonus, -1=invert rave bonus, -2=double penalty... */
48 int threat_rave;
49 /* Coefficient of local tree values embedded in RAVE. */
50 floating_t ltree_rave;
51 /* Coefficient of criticality embedded in RAVE. */
52 floating_t crit_rave;
53 int crit_min_playouts;
54 floating_t crit_plthres_coef;
55 bool crit_negative;
56 bool crit_negflip;
57 bool crit_amaf;
58 bool crit_lvalue;
62 static inline floating_t fast_sqrt(unsigned int x)
64 static const floating_t table[] = {
65 0, 1, 1.41421356237309504880, 1.73205080756887729352,
66 2.00000000000000000000, 2.23606797749978969640,
67 2.44948974278317809819, 2.64575131106459059050,
68 2.82842712474619009760, 3.00000000000000000000,
69 3.16227766016837933199, 3.31662479035539984911,
70 3.46410161513775458705, 3.60555127546398929311,
71 3.74165738677394138558, 3.87298334620741688517,
72 4.00000000000000000000, 4.12310562561766054982,
73 4.24264068711928514640, 4.35889894354067355223,
74 4.47213595499957939281, 4.58257569495584000658,
75 4.69041575982342955456, 4.79583152331271954159,
76 4.89897948556635619639, 5.00000000000000000000,
77 5.09901951359278483002, 5.19615242270663188058,
78 5.29150262212918118100, 5.38516480713450403125,
79 5.47722557505166113456, 5.56776436283002192211,
80 5.65685424949238019520, 5.74456264653802865985,
81 5.83095189484530047087, 5.91607978309961604256,
82 6.00000000000000000000, 6.08276253029821968899,
83 6.16441400296897645025, 6.24499799839839820584,
84 6.32455532033675866399, 6.40312423743284868648,
85 6.48074069840786023096, 6.55743852430200065234,
86 6.63324958071079969822, 6.70820393249936908922,
87 6.78232998312526813906, 6.85565460040104412493,
88 6.92820323027550917410, 7.00000000000000000000,
89 7.07106781186547524400, 7.14142842854284999799,
90 7.21110255092797858623, 7.28010988928051827109,
91 7.34846922834953429459, 7.41619848709566294871,
92 7.48331477354788277116, 7.54983443527074969723,
93 7.61577310586390828566, 7.68114574786860817576,
94 7.74596669241483377035, 7.81024967590665439412,
95 7.87400787401181101968, 7.93725393319377177150,
97 if (x < sizeof(table) / sizeof(*table)) {
98 return table[x];
99 } else {
100 return sqrt(x);
104 #define URAVE_DEBUG if (0)
105 static inline floating_t
106 ucb1rave_evaluate(struct uct_policy *p, struct tree *tree, struct uct_descent *descent, int parity)
108 struct ucb1_policy_amaf *b = p->data;
109 struct tree_node *node = descent->node;
110 struct tree_node *lnode = descent->lnode;
112 struct move_stats n = node->u, r = node->amaf;
113 if (p->uct->amaf_prior) {
114 stats_merge(&r, &node->prior);
115 } else {
116 stats_merge(&n, &node->prior);
119 if (p->uct->virtual_loss) {
120 /* Add virtual loss if we need to; this is used to discourage
121 * other threads from visiting this node in case of multiple
122 * threads doing the tree search. */
123 floating_t vloss_coeff = b->vloss_sqrt ? sqrt(p->uct->threads) / p->uct->threads : 1.;
124 struct move_stats c = { .value = parity > 0 ? 0. : 1., .playouts = node->descents * vloss_coeff };
125 stats_merge(&n, &c);
128 /* Local tree heuristics. */
129 assert(!lnode || lnode->parent);
130 if (p->uct->local_tree && b->ltree_rave > 0 && lnode
131 && (p->uct->local_tree_rootchoose || lnode->parent->parent)) {
132 struct move_stats l = lnode->u;
133 l.playouts = ((floating_t) l.playouts) * b->ltree_rave / LTREE_PLAYOUTS_MULTIPLIER;
134 URAVE_DEBUG fprintf(stderr, "[ltree] adding [%s] %f%%%d to [%s] RAVE %f%%%d\n",
135 coord2sstr(node_coord(lnode), tree->board), l.value, l.playouts,
136 coord2sstr(node_coord(node), tree->board), r.value, r.playouts);
137 stats_merge(&r, &l);
140 /* Criticality heuristics. */
141 if (b->crit_rave > 0 && (b->crit_plthres_coef > 0
142 ? node->u.playouts > tree->root->u.playouts * b->crit_plthres_coef
143 : node->u.playouts > b->crit_min_playouts)) {
144 floating_t crit = tree_node_criticality(tree, node);
145 if (b->crit_negative || crit > 0) {
146 floating_t val = 1.0f;
147 if (b->crit_negflip && crit < 0) {
148 val = 0;
149 crit = -crit;
151 struct move_stats c = {
152 .value = tree_node_get_value(tree, parity, val),
153 .playouts = crit * r.playouts * b->crit_rave
155 URAVE_DEBUG fprintf(stderr, "[crit] adding %f%%%d to [%s] RAVE %f%%%d\n",
156 c.value, c.playouts,
157 coord2sstr(node_coord(node), tree->board), r.value, r.playouts);
158 stats_merge(&r, &c);
162 floating_t value = 0;
163 if (n.playouts) {
164 if (r.playouts) {
165 /* At the beginning, beta is at 1 and RAVE is used.
166 * At b->equiv_rate, beta is at 1/3 and gets steeper on. */
167 floating_t beta;
168 if (b->sylvain_rave) {
169 beta = (floating_t) r.playouts / (r.playouts + n.playouts
170 + (floating_t) n.playouts * r.playouts / b->equiv_rave);
171 } else {
172 /* XXX: This can be cached in descend; but we don't use this by default. */
173 beta = sqrt(b->equiv_rave / (3 * node->parent->u.playouts + b->equiv_rave));
176 value = beta * r.value + (1.f - beta) * n.value;
177 URAVE_DEBUG fprintf(stderr, "\t%s value = %f * %f + (1 - %f) * %f (prior %f)\n",
178 coord2sstr(node_coord(node), tree->board), beta, r.value, beta, n.value, node->prior.value);
179 } else {
180 value = n.value;
181 URAVE_DEBUG fprintf(stderr, "\t%s value = %f (prior %f)\n",
182 coord2sstr(node_coord(node), tree->board), n.value, node->prior.value);
184 } else if (r.playouts) {
185 value = r.value;
186 URAVE_DEBUG fprintf(stderr, "\t%s value = rave %f (prior %f)\n",
187 coord2sstr(node_coord(node), tree->board), r.value, node->prior.value);
189 descent->value.playouts = r.playouts + n.playouts;
190 descent->value.value = value;
192 return tree_node_get_value(tree, parity, value);
195 void
196 ucb1rave_descend(struct uct_policy *p, struct tree *tree, struct uct_descent *descent, int parity, bool allow_pass)
198 struct ucb1_policy_amaf *b = p->data;
199 floating_t nconf = 1.f;
200 if (b->explore_p > 0)
201 nconf = sqrt(log(descent->node->u.playouts + descent->node->prior.playouts));
202 struct uct *u = p->uct;
203 int vwin = 0;
204 if (u->max_slaves > 0 && u->slave_index >= 0)
205 vwin = descent->node == tree->root ? b->root_virtual_win : b->virtual_win;
206 int child = 0;
208 uctd_try_node_children(tree, descent, allow_pass, parity, u->tenuki_d, di, urgency) {
209 struct tree_node *ni = di.node;
210 urgency = ucb1rave_evaluate(p, tree, &di, parity);
212 /* In distributed mode, encourage different slaves to work on different
213 * parts of the tree. We rely on the fact that children (if they exist)
214 * are the same and in the same order in all slaves. */
215 if (vwin > 0 && ni->u.playouts > b->vwin_min_playouts && (child - u->slave_index) % u->max_slaves == 0)
216 urgency += vwin / (ni->u.playouts + vwin);
218 if (ni->u.playouts > 0 && b->explore_p > 0) {
219 urgency += b->explore_p * nconf / fast_sqrt(ni->u.playouts);
221 } else if (ni->u.playouts + ni->amaf.playouts + ni->prior.playouts == 0) {
222 /* assert(!u->even_eqex); */
223 urgency = b->fpu;
225 } uctd_set_best_child(di, urgency);
227 uctd_get_best_child(descent);
231 /* Return the length of the current ko (number of moves up to to the last ko capture),
232 * 0 if the sequence is empty or doesn't start with a ko capture.
233 * B captures a ko
234 * W plays a ko threat
235 * B answers ko threat
236 * W re-captures the ko <- return 4
237 * B plays a ko threat
238 * W connects the ko */
239 static inline int ko_length(bool *ko_capture_map, int map_length)
241 if (map_length <= 0 || !ko_capture_map[0]) return 0;
242 int length = 1;
243 while (length + 2 < map_length && ko_capture_map[length + 2]) length += 3;
244 return length;
247 void
248 ucb1amaf_update(struct uct_policy *p, struct tree *tree, struct tree_node *node,
249 enum stone node_color, enum stone player_color,
250 struct playout_amafmap *map, struct board *final_board,
251 floating_t result)
253 struct ucb1_policy_amaf *b = p->data;
254 enum stone winner_color = result > 0.5 ? S_BLACK : S_WHITE;
256 /* Record of the random playout - for each intersection coord,
257 * first_move[coord] is the index map->game of the first move
258 * at this coordinate, or INT_MAX if the move was not played.
259 * The parity gives the color of this move.
261 int first_map[board_size2(final_board)+1];
262 int *first_move = &first_map[1]; // +1 for pass
264 #if 0
265 struct board bb; bb.size = 9+2;
266 for (struct tree_node *ni = node; ni; ni = ni->parent)
267 fprintf(stderr, "%s ", coord2sstr(node_coord(ni), &bb));
268 fprintf(stderr, "[color %d] update result %d (color %d)\n",
269 node_color, result, player_color);
270 #endif
272 /* Initialize first_move */
273 for (int i = pass; i < board_size2(final_board); i++) first_move[i] = INT_MAX;
274 int move;
275 assert(map->gamelen > 0);
276 for (move = map->gamelen - 1; move >= map->game_baselen; move--)
277 first_move[map->game[move]] = move;
279 while (node) {
280 if (!b->crit_amaf && !is_pass(node_coord(node))) {
281 stats_add_result(&node->winner_owner, board_local_value(b->crit_lvalue, final_board, node_coord(node), winner_color), 1);
282 stats_add_result(&node->black_owner, board_local_value(b->crit_lvalue, final_board, node_coord(node), S_BLACK), 1);
284 stats_add_result(&node->u, result, 1);
286 bool *ko_capture_map = &map->is_ko_capture[move+1];
287 int max_threat_dist = b->threat_rave <= 0 ? ko_length(ko_capture_map, map->gamelen - (move+1)) : -1;
289 /* This loop ignores symmetry considerations, but they should
290 * matter only at a point when AMAF doesn't help much. */
291 assert(map->game_baselen >= 0);
292 for (struct tree_node *ni = node->children; ni; ni = ni->sibling) {
293 if (is_pass(node_coord(ni))) continue;
295 /* Use the child move only if it was first played by the same color. */
296 int first = first_move[node_coord(ni)];
297 if (first == INT_MAX) continue;
298 assert(first > move && first < map->gamelen);
299 int distance = first - (move + 1);
300 if (distance & 1) continue;
302 int weight = 1;
303 floating_t res = result;
305 /* Don't give amaf bonus to a ko threat before taking the ko.
306 * http://www.grappa.univ-lille3.fr/~coulom/Aja_PhD_Thesis.pdf
308 if (distance <= max_threat_dist && distance % 6 == 4) {
309 weight = - b->threat_rave;
310 res = 1.0 - res;
311 } else if (b->distance_rave != 0) {
312 /* Give more weight to moves played earlier */
313 weight += b->distance_rave * (map->gamelen - first) / (map->gamelen - move);
315 stats_add_result(&ni->amaf, res, weight);
317 if (b->crit_amaf) {
318 stats_add_result(&ni->winner_owner, board_local_value(b->crit_lvalue, final_board, node_coord(ni), winner_color), 1);
319 stats_add_result(&ni->black_owner, board_local_value(b->crit_lvalue, final_board, node_coord(ni), S_BLACK), 1);
321 #if 0
322 struct board bb; bb.size = 9+2;
323 fprintf(stderr, "* %s<%"PRIhash"> -> %s<%"PRIhash"> [%d/%f => %d/%f]\n",
324 coord2sstr(node_coord(node), &bb), node->hash,
325 coord2sstr(node_coord(ni), &bb), ni->hash,
326 player_color, result, move, res);
327 #endif
329 if (node->parent) {
330 assert(move >= 0 && map->game[move] == node_coord(node) && first_move[node_coord(node)] > move);
331 first_move[node_coord(node)] = move;
332 move--;
334 node = node->parent;
339 struct uct_policy *
340 policy_ucb1amaf_init(struct uct *u, char *arg, struct board *board)
342 struct uct_policy *p = calloc2(1, sizeof(*p));
343 struct ucb1_policy_amaf *b = calloc2(1, sizeof(*b));
344 p->uct = u;
345 p->data = b;
346 p->choose = uctp_generic_choose;
347 p->winner = uctp_generic_winner;
348 p->evaluate = ucb1rave_evaluate;
349 p->descend = ucb1rave_descend;
350 p->update = ucb1amaf_update;
351 p->wants_amaf = true;
353 b->explore_p = 0;
354 b->equiv_rave = board_large(board) ? 4000 : 3000;
355 b->fpu = INFINITY;
356 b->sylvain_rave = true;
357 b->distance_rave = 3;
358 b->threat_rave = 0;
359 b->ltree_rave = 0.75f;
361 b->crit_rave = 1.1f;
362 b->crit_min_playouts = 2000;
363 b->crit_negative = 1;
364 b->crit_amaf = 0;
366 b->vloss_sqrt = true;
368 b->virtual_win = 5;
369 b->root_virtual_win = 30;
370 b->vwin_min_playouts = 1000;
372 if (arg) {
373 char *optspec, *next = arg;
374 while (*next) {
375 optspec = next;
376 next += strcspn(next, ":");
377 if (*next) { *next++ = 0; } else { *next = 0; }
379 char *optname = optspec;
380 char *optval = strchr(optspec, '=');
381 if (optval) *optval++ = 0;
383 if (!strcasecmp(optname, "explore_p")) {
384 b->explore_p = atof(optval);
385 } else if (!strcasecmp(optname, "fpu") && optval) {
386 b->fpu = atof(optval);
387 } else if (!strcasecmp(optname, "equiv_rave") && optval) {
388 b->equiv_rave = atof(optval);
389 } else if (!strcasecmp(optname, "sylvain_rave")) {
390 b->sylvain_rave = !optval || *optval == '1';
391 } else if (!strcasecmp(optname, "distance_rave") && optval) {
392 b->distance_rave = atoi(optval);
393 } else if (!strcasecmp(optname, "threat_rave") && optval) {
394 b->threat_rave = atoi(optval);
395 } else if (!strcasecmp(optname, "ltree_rave") && optval) {
396 b->ltree_rave = atof(optval);
397 } else if (!strcasecmp(optname, "crit_rave") && optval) {
398 b->crit_rave = atof(optval);
399 } else if (!strcasecmp(optname, "crit_min_playouts") && optval) {
400 b->crit_min_playouts = atoi(optval);
401 } else if (!strcasecmp(optname, "crit_plthres_coef") && optval) {
402 b->crit_plthres_coef = atof(optval);
403 } else if (!strcasecmp(optname, "crit_negative")) {
404 b->crit_negative = !optval || *optval == '1';
405 } else if (!strcasecmp(optname, "crit_negflip")) {
406 b->crit_negflip = !optval || *optval == '1';
407 } else if (!strcasecmp(optname, "crit_amaf")) {
408 b->crit_amaf = !optval || *optval == '1';
409 } else if (!strcasecmp(optname, "crit_lvalue")) {
410 b->crit_lvalue = !optval || *optval == '1';
411 } else if (!strcasecmp(optname, "virtual_win") && optval) {
412 b->virtual_win = atoi(optval);
413 } else if (!strcasecmp(optname, "root_virtual_win") && optval) {
414 b->root_virtual_win = atoi(optval);
415 } else if (!strcasecmp(optname, "vwin_min_playouts") && optval) {
416 b->vwin_min_playouts = atoi(optval);
417 } else if (!strcasecmp(optname, "vloss_sqrt")) {
418 b->vloss_sqrt = !optval || *optval == '1';
419 } else {
420 fprintf(stderr, "ucb1amaf: Invalid policy argument %s or missing value\n",
421 optname);
422 exit(1);
427 return p;