playout.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 "engine.h"
  11 #include "move.h"
  12 #include "ownermap.h"
  13 #include "playout.h"
  14 #include "probdist.h"
  15
  16
  17 static coord_t
  18 try_probdist_move(struct board *b, enum stone color, struct playout_setup *setup)
  19 {
  20         /* First try probability distribution provided by
  21          * the engine for this move. */
  22         struct probdist pd;
  23         probdist_init(&pd, board_size2(b));
  24
  25         setup->probdist(setup, &pd, b);
  26         if (pd.moves[0] >= pd.total - __FLT_EPSILON__) {
  27                 probdist_done(&pd);
  28                 return pass;
  29         }
  30
  31         coord_t coord = probdist_pick(&pd);
  32         probdist_done(&pd);
  33
  34         /* If the pick is invalid, defer to policy. */
  35         if (!coord || is_pass(coord))
  36                 return pass;
  37         struct move m = { .coord = coord, .color = color };
  38         if (!board_is_valid_move(b, &m))
  39                 return pass;
  40
  41         return coord;
  42 }
  43
  44 int
  45 play_random_game(struct playout_setup *setup,
  46                  struct board *b, enum stone starting_color,
  47                  struct playout_amafmap *amafmap,
  48                  struct board_ownermap *ownermap,
  49                  struct playout_policy *policy)
  50 {
  51         assert(setup && policy);
  52
  53         int gamelen = setup->gamelen - b->moves;
  54         if (gamelen < 10)
  55                 gamelen = 10;
  56
  57         enum stone color = starting_color;
  58
  59         int passes = is_pass(b->last_move.coord) && b->moves > 0;
  60
  61         while (gamelen-- && passes < 2) {
  62                 coord_t coord = pass;
  63
  64                 if (setup->probdist) {
  65                         coord = try_probdist_move(b, color, setup);
  66                 }
  67
  68                 if (is_pass(coord)) {
  69                         /* Defer to policy move choice. */
  70                         coord = policy->choose(policy, b, color);
  71                 }
  72
  73                 if (is_pass(coord)) {
  74 play_random:
  75                         /* Defer to uniformly random move choice. */
  76                         board_play_random(b, color, &coord, (ppr_permit) policy->permit, policy);
  77
  78                 } else {
  79                         struct move m;
  80                         m.coord = coord; m.color = color;
  81                         if (board_play(b, &m) < 0) {
  82                                 if (DEBUGL(8)) {
  83                                         fprintf(stderr, "Pre-picked move %d,%d is ILLEGAL:\n",
  84                                                 coord_x(coord, b), coord_y(coord, b));
  85                                         board_print(b, stderr);
  86                                 }
  87                                 goto play_random;
  88                         }
  89                 }
  90
  91 #if 0
  92                 /* For UCT, superko test here is downright harmful since
  93                  * in superko-likely situation we throw away literally
  94                  * 95% of our playouts; UCT will deal with this fine by
  95                  * itself. */
  96                 if (unlikely(b->superko_violation)) {
  97                         /* We ignore superko violations that are suicides. These
  98                          * are common only at the end of the game and are
  99                          * rather harmless. (They will not go through as a root
 100                          * move anyway.) */
 101                         if (group_at(b, coord)) {
 102                                 if (DEBUGL(3)) {
 103                                         fprintf(stderr, "Superko fun at %d,%d in\n", coord_x(coord, b), coord_y(coord, b));
 104                                         if (DEBUGL(4))
 105                                                 board_print(b, stderr);
 106                                 }
 107                                 return 0;
 108                         } else {
 109                                 if (DEBUGL(6)) {
 110                                         fprintf(stderr, "Ignoring superko at %d,%d in\n", coord_x(coord, b), coord_y(coord, b));
 111                                         board_print(b, stderr);
 112                                 }
 113                                 b->superko_violation = false;
 114                         }
 115                 }
 116 #endif
 117
 118                 if (DEBUGL(7)) {
 119                         fprintf(stderr, "%s %s\n", stone2str(color), coord2sstr(coord, b));
 120                         if (DEBUGL(8))
 121                                 board_print(b, stderr);
 122                 }
 123
 124                 if (unlikely(is_pass(coord))) {
 125                         passes++;
 126                 } else {
 127                         /* We don't care about nakade counters, since we want
 128                          * to avoid taking pre-nakade moves into account only
 129                          * if they happenned in the tree before nakade nodes;
 130                          * but this is always out of the tree. */
 131                         if (amafmap) {
 132                                 if (amafmap->map[coord] == S_NONE || amafmap->map[coord] == color)
 133                                         amafmap->map[coord] = color;
 134                                 else if (amafmap->record_nakade)
 135                                         amaf_op(amafmap->map[coord], +);
 136                                 amafmap->game[amafmap->gamelen].coord = coord;
 137                                 amafmap->game[amafmap->gamelen].color = color;
 138                                 amafmap->gamelen++;
 139                                 assert(amafmap->gamelen < sizeof(amafmap->game) / sizeof(amafmap->game[0]));
 140                         }
 141
 142                         passes = 0;
 143                 }
 144
 145                 color = stone_other(color);
 146         }
 147
 148         float score = board_fast_score(b);
 149         int result = (starting_color == S_WHITE ? score * 2 : - (score * 2));
 150
 151         if (DEBUGL(6)) {
 152                 fprintf(stderr, "Random playout result: %d (W %f)\n", result, score);
 153                 if (DEBUGL(7))
 154                         board_print(b, stderr);
 155         }
 156
 157         if (ownermap)
 158                 board_ownermap_fill(ownermap, b);
 159
 160         return result;
 161 }