mariai.cpp

#include "mariai.h"
#include "pattern.h"

Mariai::Mariai(Board *b, Draw *d) : it(0) {
  p_board = b;
  p_draw = d;
  Q_values.clear();
  fastrand_seed();
  lehmer64_seed();
}

Mariai::~Mariai() {}

Board *Mariai::gb() { return p_board; }

Draw *Mariai::gd() { return p_draw; }

void Mariai::init_tree(Node *root, Board &b) { expand_node(root, b); }

void Mariai::run_mcts(Node *root, Board &b) {
  for (int n = 0; n < PLAYOUTS; n++) {
    Node *head = NULL;
    Board vb = b;
    bool quit = false;

    // TREE POLICY: selection & expansion
    tie(quit, head) = select_path(root, vb);

    // DEFAULT POLICY: playout using Monte-Carlo method
    fast_rollout(vb, quit);

    // BACKUP: backpropagation
    quit = backpropagation(head, root, vb.whose_turn(), vb.check_tied());
    if (quit)
      return;
    else
      it++;
    show_progress();
  }
}

tuple<bool, Node *> Mariai::select_path(Node *node, Board &vb) {
  // TREE POLICY: selection
  while (!node->leaf) {
    node = &node->children[node->children_iQ[0]];
    if (move_and_check_quit(node, vb))
      return make_pair(true, node);
  }

  // TREE POLICY: expansion
  if (is_expandable(node)) {
    expand_node(node, vb);
    node = &node->children[node->children_iQ[0]];
    if (move_and_check_quit(node, vb))
      return make_pair(true, node);
  }
  return make_pair(false, node);
}

void Mariai::expand_node(Node *node, Board &vb) {
  Board g = vb;
  VecCoords candy = gen_candy(g);
  uint8_t node_index = 0;
  for (auto q : candy) {
    insert_node(node, q, g.whose_turn());
    node->children_iQ.push_back(node_index++);
  }
  node->leaf = false;
}

void Mariai::insert_node(Node *node, Coords q, Stone s) {
  node->children.push_back(Node(node, q, s, node->depth + 1));
}

void Mariai::fast_rollout(Board &vb, bool quit) {
  while (!quit) {
    int x, y;
    while (1) {
      x = randint(0, N - 1);
      y = randint(0, N - 1);
      if (!vb.make_move(x, y))
        break;
    }
    quit = vb.check_quit(x, y);
    if (!quit)
      vb.toggle_turn();
  }
}

float Mariai::calc_ucb(const Node *node) {
  static const float n = log(PLAYOUTS);
  float exploitation = node->reward / node->visit;
  float exploration = UCB_C * pow(n / node->visit, UCB_POW);
  return exploitation + exploration;
}

bool Mariai::backpropagation(Node *node, Node *root, Stone turn, bool tied) {
  while (node != NULL) {
    node->visit++;
    float reward = pow(GAMMA, node->depth);
    // fast-decision
    if (node != root && node->visit > EARLY_CUT)
      return true;
    if (!tied && node->turn == turn) {
      node->win++;
      node->reward += reward;
    }
    if (node != root) {
      node->Q = calc_ucb(node);
      Q_values.push_back(node->Q);
    }
    sort_children_by_Q(node);
    node = node->prev;
  }
  return false;
}

bool Mariai::is_expandable(Node *node) {
  return node->leaf && node->visit >= BRANCHING && node->depth <= MCTS_PLY;
}

bool Mariai::move_and_check_quit(Node *node, Board &vb) {
  Coords q = node->coords;
  int x, y;
  tie(x, y) = q;
  vb.make_move(x, y);
  if (vb.check_quit(x, y))
    return true;
  vb.toggle_turn();
  return false;
}

Coords Mariai::pick_best(Node *node) {
  Node *best = get_most_visited_child(node);
  float winning_prob = 1. * best->win / best->visit;
  gb()->eB =
      (best->turn == BLACK) ? 100 * winning_prob : 100 * (1 - winning_prob);
  gb()->eW = 100 - gb()->eB;
  return best->coords;
}

void Mariai::sort_children_by_Q(Node *node) {
  if (node->prev == NULL)
    return;

  sort(node->prev->children_iQ.begin(), node->prev->children_iQ.end(),
       [&](const size_t a, const size_t b) {
         return node->prev->children[a].Q > node->prev->children[b].Q;
       });
}

Node *Mariai::get_most_visited_child(Node *node) {
  int max = -1;
  Node *most_visited = NULL;
  for (auto &child : node->children) {
    if (child.visit > max && child.Q > 0) {
      max = child.visit;
      most_visited = &child;
    }
  }
  return most_visited;
}

VecCoords Mariai::gen_candy(Board &b) {
  Pattern p;
  VecCoords candy;
  p.find_candidates(b, candy);
  return candy;
}

Coords Mariai::next_move() {
  if (gb()->moves == 0)
    return make_pair(N / 2, N / 2);
  Node root(NULL, make_pair(-1, -1), EMPTY, 0);
  it = 0;

  // Init tree: forced first expansion
  init_tree(&root, *gb());
  // MCTS based on UCB1
  run_mcts(&root, *gb());

#if PRINT_TREE
  string move = to_string(gb()->moves);
  string fname = "gtree_" + string(3 - move.length(), '0') + move + ".log";
  ofstream fout(fname, ios::app);
  print_tree(&root, 0, fout);
  fout.close();
#endif

  // Q-dist
  float mean, stdev;
  tie(mean, stdev) = get_dist_Q();
  float threshold = mean - 0.7 * stdev;

  // Rebuild tree if necessary
  Node *best_node = get_most_visited_child(&root);
  if (best_node->Q < threshold)
    return next_move();
  else
    return pick_best(&root);
}

Qdist Mariai::get_dist_Q() {
  if (Q_values.empty()) {
    return {0, 0};
  }
  float mean =
      accumulate(Q_values.begin(), Q_values.end(), 0.0) / Q_values.size();
  float sq_sum =
      inner_product(Q_values.begin(), Q_values.end(), Q_values.begin(), 0.0);
  float stdev = sqrt(sq_sum / Q_values.size() - mean * mean);
  Q_values.clear();
  return {mean, stdev};
}

void Mariai::show_progress() {
  if (gd() == NULL)
    return;
  if (it % LINE_BUFFER == 0)
    gd()->dump_progress(1.0 * it / PLAYOUTS);
}

void Mariai::print_tree(Node *node, int set_width, ofstream &fout) {
  Node *head = node;
  string color;
  if (!fout.is_open())
    return;
  switch (head->turn) {
  case BLACK:
    color = "B";
    break;
  case WHITE:
    color = "W";
    break;
  default:
    color = "ROOT";
  }
  if (head->Q > -2) {
    fout << setw(set_width) << "[";
    fout << "(" << (head->coords).first << ", " << (head->coords).second << ", "
         << color << "), "
         << "Q: " << head->Q << ", "
         << "w: " << head->win << ", "
         << "v: " << head->visit << "]"
         << "\n";
  }
  if (!head->leaf) {
    vector<size_t> indices(node->children.size());
    iota(indices.begin(), indices.end(), 0);
    sort(indices.begin(), indices.end(), [&](const size_t a, const size_t b) {
      return node->children[a].visit > node->children[b].visit;
    });
    for (auto i : indices) {
      print_tree(&head->children[i], set_width + 3, fout);
    }
  }
}