uct/dynkomi.c

   1 #define DEBUG
   2 #include <assert.h>
   3 #include <math.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7
   8 #include "board.h"
   9 #include "debug.h"
  10 #include "tactics.h"
  11 #include "uct/dynkomi.h"
  12 #include "uct/internal.h"
  13 #include "uct/tree.h"
  14
  15
  16 static void
  17 uct_dynkomi_generic_done(struct uct_dynkomi *d)
  18 {
  19         if (d->data) free(d->data);
  20         free(d);
  21 }
  22
  23
  24 /* NONE dynkomi strategy - never fiddle with komi values. */
  25
  26 struct uct_dynkomi *
  27 uct_dynkomi_init_none(struct uct *u, char *arg, struct board *b)
  28 {
  29         struct uct_dynkomi *d = calloc(1, sizeof(*d));
  30         d->uct = u;
  31         d->permove = NULL;
  32         d->persim = NULL;
  33         d->done = uct_dynkomi_generic_done;
  34         d->data = NULL;
  35
  36         if (arg) {
  37                 fprintf(stderr, "uct: Dynkomi method none accepts no arguments\n");
  38                 exit(1);
  39         }
  40
  41         return d;
  42 }
  43
  44
  45 /* LINEAR dynkomi strategy - Linearly Decreasing Handicap Compensation. */
  46 /* At move 0, we impose extra komi of handicap_count*handicap_value, then
  47  * we linearly decrease this extra komi throughout the game down to 0
  48  * at @moves moves. */
  49
  50 struct dynkomi_linear {
  51         int handicap_value;
  52         int moves;
  53         bool rootbased;
  54 };
  55
  56 float
  57 uct_dynkomi_linear_permove(struct uct_dynkomi *d, struct board *b, struct tree *tree)
  58 {
  59         struct dynkomi_linear *l = d->data;
  60         if (b->moves >= l->moves)
  61                 return 0;
  62
  63         float base_komi = board_effective_handicap(b, l->handicap_value);
  64         float extra_komi = base_komi * (l->moves - b->moves) / l->moves;
  65         return extra_komi;
  66 }
  67
  68 float
  69 uct_dynkomi_linear_persim(struct uct_dynkomi *d, struct board *b, struct tree *tree, struct tree_node *node)
  70 {
  71         struct dynkomi_linear *l = d->data;
  72         if (l->rootbased)
  73                 return tree->extra_komi;
  74         /* We don't reuse computed value from tree->extra_komi,
  75          * since we want to use value correct for this node depth.
  76          * This also means the values will stay correct after
  77          * node promotion. */
  78         return uct_dynkomi_linear_permove(d, b, tree);
  79 }
  80
  81 struct uct_dynkomi *
  82 uct_dynkomi_init_linear(struct uct *u, char *arg, struct board *b)
  83 {
  84         struct uct_dynkomi *d = calloc(1, sizeof(*d));
  85         d->uct = u;
  86         d->permove = uct_dynkomi_linear_permove;
  87         d->persim = uct_dynkomi_linear_persim;
  88         d->done = uct_dynkomi_generic_done;
  89
  90         struct dynkomi_linear *l = calloc(1, sizeof(*l));
  91         d->data = l;
  92
  93         if (board_size(b) - 2 >= 19)
  94                 l->moves = 200;
  95         l->handicap_value = 7;
  96
  97         if (arg) {
  98                 char *optspec, *next = arg;
  99                 while (*next) {
 100                         optspec = next;
 101                         next += strcspn(next, ":");
 102                         if (*next) { *next++ = 0; } else { *next = 0; }
 103
 104                         char *optname = optspec;
 105                         char *optval = strchr(optspec, '=');
 106                         if (optval) *optval++ = 0;
 107
 108                         if (!strcasecmp(optname, "moves") && optval) {
 109                                 /* Dynamic komi in handicap game; linearly
 110                                  * decreases to basic settings until move
 111                                  * #optval. */
 112                                 l->moves = atoi(optval);
 113                         } else if (!strcasecmp(optname, "handicap_value") && optval) {
 114                                 /* Point value of single handicap stone,
 115                                  * for dynkomi computation. */
 116                                 l->handicap_value = atoi(optval);
 117                         } else if (!strcasecmp(optname, "rootbased")) {
 118                                 /* If set, the extra komi applied will be
 119                                  * the same for all simulations within a move,
 120                                  * instead of being same for all simulations
 121                                  * within the tree node. */
 122                                 l->rootbased = !optval || atoi(optval);
 123                         } else {
 124                                 fprintf(stderr, "uct: Invalid dynkomi argument %s or missing value\n", optname);
 125                                 exit(1);
 126                         }
 127                 }
 128         }
 129
 130         return d;
 131 }
 132
 133
 134 /* ADAPTIVE dynkomi strategy - Adaptive Situational Compensation */
 135 /* We adapt the komi based on current situation:
 136  * (i) score-based: We maintain the average score outcome of our
 137  * games and adjust the komi by a fractional step towards the expected
 138  * score;
 139  * (ii) value-based: While winrate is above given threshold, adjust
 140  * the komi by a fixed step in the appropriate direction.
 141  * These adjustments can be
 142  * (a) Move-stepped, new extra komi value is always set only at the
 143  * beginning of the tree search for next move;
 144  * (b) Continuous, new extra komi value is periodically re-determined
 145  * and adjusted throughout a single tree search. [TODO] */
 146
 147 struct dynkomi_adaptive {
 148         /* Do not take measured average score into regard for
 149          * first @lead_moves - the variance is just too much.
 150          * (Instead, we consider the handicap-based komi provided
 151          * by linear dynkomi.) */
 152         int lead_moves;
 153         /* Maximum komi to pretend the opponent to give. */
 154         float max_losing_komi;
 155
 156         /* Value-based adaptation. */
 157         bool value_based;
 158         float zone_red, zone_green;
 159         int score_step;
 160         bool use_komi_latch;
 161         float komi_latch; // runtime, not configuration
 162
 163         float (*adapter)(struct dynkomi_adaptive *a, struct board *b);
 164         float adapt_base; // [0,1)
 165         /* Sigmoid adaptation rate parameter; see below for details. */
 166         float adapt_phase; // [0,1]
 167         float adapt_rate; // [1,infty)
 168         bool adapt_aport; // alternative game portion determination
 169         /* Linear adaptation rate parameter. */
 170         int adapt_moves;
 171         float adapt_dir; // [-1,1]
 172 };
 173 #define TRUSTWORTHY_KOMI_PLAYOUTS 200
 174
 175 float
 176 adapter_sigmoid(struct dynkomi_adaptive *a, struct board *b)
 177 {
 178         /* Figure out how much to adjust the komi based on the game
 179          * stage. The adaptation rate is 0 at the beginning,
 180          * at game stage a->adapt_phase crosses though 0.5 and
 181          * approaches 1 at the game end; the slope is controlled
 182          * by a->adapt_rate. */
 183         float game_portion;
 184         if (!a->adapt_aport) {
 185                 int total_moves = b->moves + 2 * board_estimated_moves_left(b);
 186                 game_portion = (float) b->moves / total_moves;
 187         } else {
 188                 int brsize = board_size(b) - 2;
 189                 game_portion = 1.0 - (float) b->flen / (brsize * brsize);
 190         }
 191         float l = game_portion - a->adapt_phase;
 192         return 1.0 / (1.0 + exp(-a->adapt_rate * l));
 193 }
 194
 195 float
 196 adapter_linear(struct dynkomi_adaptive *a, struct board *b)
 197 {
 198         /* Figure out how much to adjust the komi based on the game
 199          * stage. We just linearly increase/decrease the adaptation
 200          * rate for first N moves. */
 201         if (b->moves > a->adapt_moves)
 202                 return 0;
 203         if (a->adapt_dir < 0)
 204                 return 1 - (- a->adapt_dir) * b->moves / a->adapt_moves;
 205         else
 206                 return a->adapt_dir * b->moves / a->adapt_moves;
 207 }
 208
 209 float
 210 uct_dynkomi_adaptive_permove(struct uct_dynkomi *d, struct board *b, struct tree *tree)
 211 {
 212         struct dynkomi_adaptive *a = d->data;
 213         if (DEBUGL(3))
 214                 fprintf(stderr, "m %d/%d ekomi %f permove %f/%d\n",
 215                         b->moves, a->lead_moves, tree->extra_komi,
 216                         tree->score.value, tree->score.playouts);
 217         if (b->moves <= a->lead_moves)
 218                 return board_effective_handicap(b, 7 /* XXX */);
 219
 220         /* Get lower bound on komi value so that we don't underperform
 221          * too much. XXX: We rely on the fact that we don't use dynkomi
 222          * as white for now. */
 223         float min_komi = - a->max_losing_komi;
 224
 225         /* Perhaps we are adaptive value-based, not score-based? */
 226         if (a->value_based) {
 227                 /* In that case, we have three zones:
 228                  * red zone | yellow zone | green zone
 229                  *        ~45%           ~60%
 230                  * red zone: reduce komi
 231                  * yellow zone: do not touch komi
 232                  * green zone: enlage komi.
 233                  *
 234                  * Also, at some point komi will be tuned in such way
 235                  * that it will be in green zone but increasing it will
 236                  * be unfeasible. Thus, we have a _latch_ - we will
 237                  * remember the last komi that has put us into the
 238                  * red zone, and not use it or go over it. We use the
 239                  * latch only when giving extra komi, we always want
 240                  * to try to reduce extra komi we take.
 241                  *
 242                  * TODO: Make the latch expire after a while. */
 243                 if (tree->root->u.playouts < TRUSTWORTHY_KOMI_PLAYOUTS)
 244                         return tree->extra_komi;
 245                 float value = tree->root->u.value;
 246                 float extra_komi = tree->extra_komi;
 247                 if (value < a->zone_red) {
 248                         /* Red zone. Take extra komi. */
 249                         if (extra_komi > 0) a->komi_latch = extra_komi;
 250                         extra_komi -= a->score_step; // XXX: we depend on being black
 251                         return extra_komi > min_komi ? extra_komi : min_komi;
 252                 } else if (value < a->zone_green) {
 253                         /* Yellow zone, do nothing. */
 254                         return extra_komi;
 255                 } else {
 256                         /* Green zone. Give extra komi. */
 257                         extra_komi += a->score_step; // XXX: we depend on being black
 258                         return !a->use_komi_latch || extra_komi < a->komi_latch ? extra_komi : a->komi_latch - 1;
 259                 }
 260         }
 261
 262         if (tree->score.playouts < TRUSTWORTHY_KOMI_PLAYOUTS)
 263                 return tree->extra_komi;
 264
 265         struct move_stats score = tree->score;
 266         /* Almost-reset tree->score to gather fresh stats. */
 267         tree->score.playouts = 1;
 268
 269         /* Look at average score and push extra_komi in that direction. */
 270         float p = a->adapter(a, b);
 271         p = a->adapt_base + p * (1 - a->adapt_base);
 272         if (p > 0.9) p = 0.9; // don't get too eager!
 273         float extra_komi = tree->extra_komi + p * score.value;
 274         if (DEBUGL(3))
 275                 fprintf(stderr, "mC %f + %f * %f = %f\n",
 276                         tree->extra_komi, p, score.value, extra_komi);
 277         return extra_komi > min_komi ? extra_komi : min_komi;
 278 }
 279
 280 float
 281 uct_dynkomi_adaptive_persim(struct uct_dynkomi *d, struct board *b, struct tree *tree, struct tree_node *node)
 282 {
 283         return tree->extra_komi;
 284 }
 285
 286 struct uct_dynkomi *
 287 uct_dynkomi_init_adaptive(struct uct *u, char *arg, struct board *b)
 288 {
 289         struct uct_dynkomi *d = calloc(1, sizeof(*d));
 290         d->uct = u;
 291         d->permove = uct_dynkomi_adaptive_permove;
 292         d->persim = uct_dynkomi_adaptive_persim;
 293         d->done = uct_dynkomi_generic_done;
 294
 295         struct dynkomi_adaptive *a = calloc(1, sizeof(*a));
 296         d->data = a;
 297
 298         if (board_size(b) - 2 >= 19)
 299                 a->lead_moves = 20;
 300         else
 301                 a->lead_moves = 4; // XXX
 302         a->max_losing_komi = 10;
 303         a->adapter = adapter_sigmoid;
 304         a->adapt_rate = 20;
 305         a->adapt_phase = 0.5;
 306         a->adapt_moves = 200;
 307         a->adapt_dir = -0.5;
 308
 309         a->zone_red = 0.45;
 310         a->zone_green = 0.6;
 311         a->score_step = 2;
 312         a->use_komi_latch = true;
 313         a->komi_latch = 1000;
 314
 315         if (arg) {
 316                 char *optspec, *next = arg;
 317                 while (*next) {
 318                         optspec = next;
 319                         next += strcspn(next, ":");
 320                         if (*next) { *next++ = 0; } else { *next = 0; }
 321
 322                         char *optname = optspec;
 323                         char *optval = strchr(optspec, '=');
 324                         if (optval) *optval++ = 0;
 325
 326                         if (!strcasecmp(optname, "lead_moves") && optval) {
 327                                 /* Do not adjust komi adaptively for first
 328                                  * N moves. */
 329                                 a->lead_moves = atoi(optval);
 330                         } else if (!strcasecmp(optname, "max_losing_komi") && optval) {
 331                                 a->max_losing_komi = atof(optval);
 332
 333                         } else if (!strcasecmp(optname, "value_based")) {
 334                                 a->value_based = !optval || atoi(optval);
 335                         } else if (!strcasecmp(optname, "zone_red") && optval) {
 336                                 a->zone_red = atof(optval);
 337                         } else if (!strcasecmp(optname, "zone_green") && optval) {
 338                                 a->zone_green = atof(optval);
 339                         } else if (!strcasecmp(optname, "score_step") && optval) {
 340                                 a->score_step = atoi(optval);
 341                         } else if (!strcasecmp(optname, "use_komi_latch")) {
 342                                 a->use_komi_latch = !optval || atoi(optval);
 343
 344                         } else if (!strcasecmp(optname, "adapter") && optval) {
 345                                 /* Adaptatation method. */
 346                                 if (!strcasecmp(optval, "sigmoid")) {
 347                                         a->adapter = adapter_sigmoid;
 348                                 } else if (!strcasecmp(optval, "linear")) {
 349                                         a->adapter = adapter_linear;
 350                                 } else {
 351                                         fprintf(stderr, "UCT: Invalid adapter %s\n", optval);
 352                                         exit(1);
 353                                 }
 354                         } else if (!strcasecmp(optname, "adapt_base") && optval) {
 355                                 /* Adaptation base rate; see above. */
 356                                 a->adapt_base = atof(optval);
 357                         } else if (!strcasecmp(optname, "adapt_rate") && optval) {
 358                                 /* Adaptation slope; see above. */
 359                                 a->adapt_rate = atof(optval);
 360                         } else if (!strcasecmp(optname, "adapt_phase") && optval) {
 361                                 /* Adaptation phase shift; see above. */
 362                                 a->adapt_phase = atof(optval);
 363                         } else if (!strcasecmp(optname, "adapt_moves") && optval) {
 364                                 /* Adaptation move amount; see above. */
 365                                 a->adapt_moves = atoi(optval);
 366                         } else if (!strcasecmp(optname, "adapt_aport")) {
 367                                 a->adapt_aport = !optval || atoi(optval);
 368                         } else if (!strcasecmp(optname, "adapt_dir") && optval) {
 369                                 /* Adaptation direction vector; see above. */
 370                                 a->adapt_dir = atof(optval);
 371                         } else {
 372                                 fprintf(stderr, "uct: Invalid dynkomi argument %s or missing value\n", optname);
 373                                 exit(1);
 374                         }
 375                 }
 376         }
 377
 378         return d;
 379 }