<commit_before>#include "UCT.h"

#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <time.h>

#include <atomic>
#include <cstdlib>
#include <mutex>
#include <random>
#include <thread>

#include "Common.h"
#include "Patterns.h"

#if _MSC_VER
#define snprintf _snprintf
#endif

// Implemented using http://www.cameronius.com/cv/mcts-survey-master.pdf

std::mutex treePolicyMutex;
std::mutex backUpMutex;
std::atomic<int> simulationCount;


double diffclock(timespec start, timespec finish) {
  double elapsed = static_cast<double>(finish.tv_sec - start.tv_sec);
  elapsed += static_cast<double>(finish.tv_nsec - start.tv_nsec)/1000000000.0;
  return elapsed * (-1000);
}

void printNode(UCTNode* n, char* spaces) {
  printf("%sn(%d %d) V %d R %f\n", spaces, n->move.row, n->move.column,
    n->visits, n->totalRewards);
  // std::cout << spaces << "n (" << n->move.row << " " << n->move.column
    // << ") V " << n->visits << " R " << n->totalRewards << std::endl;

  UCTNode* next = n->child;
  while (next != nullptr) {
    char moreSpaces[100];
    snprintf(moreSpaces, sizeof(spaces), "%s ", spaces);
    printNode(next, moreSpaces);
    next = next->sibling;
  }
}

UCTNode* bestChild(UCTNode* node) {
  node->mutex.lock();
  const double c = 1;  // / sqrt(static_cast<float>(2));
  // const double c = 1;
  UCTNode* bestChild = node->child;
  double bestScore = -100000;
  UCTNode* next = node->child;
  while (next != nullptr) {
    double uctScore = next->totalRewards / next->visits
      + c*sqrt((2*log(static_cast<float>(node->visits))) / next->visits);
    if (bestScore < uctScore) {
      bestChild = next;
      bestScore = uctScore;
    }
    next = next->sibling;
  }
  node->mutex.unlock();
  return bestChild;
}

UCTNode* getNewChild(UCTNode* node, std::default_random_engine& engine) {
  node->mutex.lock();
  if (node->possibleChildren.empty() && node->child == nullptr) {
    auto state = node->getState();
    auto legalMoves = state->getPossibleMoves();
    for (unsigned short i = 0; i < legalMoves.size(); ++i) {
      UCTNode* child = new UCTNode(*legalMoves[i], node);
      node->possibleChildren.push_back(child);
    }

    Point pass(BOARD_SIZE, BOARD_SIZE);
    UCTNode* passChild = new UCTNode(pass, node);
    node->possibleChildren.push_back(passChild);
  }

  if (node->possibleChildren.size() == 0) {
    node->mutex.unlock();
    return nullptr;
  }
  // else //Pick random child
  // {
    std::uniform_int_distribution<> dist(0, (int)node->possibleChildren.size()-1);
    unsigned int choice = dist(engine);
    UCTNode* chosenChild = node->possibleChildren[choice];
    // for(unsigned int i = 0; i < possibleChildren.size(); i++)
    //  if(i != choice)
    //    delete possibleChildren[i];
    // node->possibleChildren.erase(&node->possibleChildren.begin()+choice);
    node->possibleChildren[choice] = node->possibleChildren.back();
    node->possibleChildren.pop_back();
    node->mutex.unlock();
    return chosenChild;
  //  }
}

UCTNode* TreePolicy(UCTNode* node, std::default_random_engine& engine) {
  Point passPoint(BOARD_SIZE, BOARD_SIZE);
  while (!(node->move == passPoint && node->parent != nullptr && node->parent->move != passPoint)) {  // Not terminal
    UCTNode* newChild = getNewChild(node, engine);
    if (newChild != nullptr) {
      node->addChild(newChild);
      return newChild;
    } else {
      node = bestChild(node);
    }
  }
  Point pass(BOARD_SIZE, BOARD_SIZE);
  if (node->move != pass
    && node->move.color != Empty) {
    assert(false);
  }
  return node;
}

int DefaultPolicy(std::default_random_engine& engine, UCTNode* node, Board* clone, Patterns* patterns) {
  for (Group* g : clone->blackGroups)
    delete g;
  clone->blackGroups.clear();
  for (Group* g : clone->whiteGroups)
    delete g;
  clone->whiteGroups.clear();

  auto state = node->getState();

  GameResult r;
  if (patterns != nullptr && patterns->initialized)
    r = state->playGame(patterns, engine);
  else
    r = state->playRandomGame(engine);

  if ((node->getState()->turn == Black ? White : Black) == static_cast<int>(r))
    return 1;
  else if (r != Draw)
    return -1;<commit_msg>Changed UCT::DefaultPolicy to not call UCTNode::getState an extra time.<commit_after>#include "UCT.h"

#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <time.h>

#include <atomic>
#include <cstdlib>
#include <mutex>
#include <random>
#include <thread>

#include "Common.h"
#include "Patterns.h"

#if _MSC_VER
#define snprintf _snprintf
#endif

// Implemented using http://www.cameronius.com/cv/mcts-survey-master.pdf

std::mutex treePolicyMutex;
std::mutex backUpMutex;
std::atomic<int> simulationCount;


double diffclock(timespec start, timespec finish) {
  double elapsed = static_cast<double>(finish.tv_sec - start.tv_sec);
  elapsed += static_cast<double>(finish.tv_nsec - start.tv_nsec)/1000000000.0;
  return elapsed * (-1000);
}

void printNode(UCTNode* n, char* spaces) {
  printf("%sn(%d %d) V %d R %f\n", spaces, n->move.row, n->move.column,
    n->visits, n->totalRewards);
  // std::cout << spaces << "n (" << n->move.row << " " << n->move.column
    // << ") V " << n->visits << " R " << n->totalRewards << std::endl;

  UCTNode* next = n->child;
  while (next != nullptr) {
    char moreSpaces[100];
    snprintf(moreSpaces, sizeof(spaces), "%s ", spaces);
    printNode(next, moreSpaces);
    next = next->sibling;
  }
}

UCTNode* bestChild(UCTNode* node) {
  node->mutex.lock();
  const double c = 1;  // / sqrt(static_cast<float>(2));
  // const double c = 1;
  UCTNode* bestChild = node->child;
  double bestScore = -100000;
  UCTNode* next = node->child;
  while (next != nullptr) {
    double uctScore = next->totalRewards / next->visits
      + c*sqrt((2*log(static_cast<float>(node->visits))) / next->visits);
    if (bestScore < uctScore) {
      bestChild = next;
      bestScore = uctScore;
    }
    next = next->sibling;
  }
  node->mutex.unlock();
  return bestChild;
}

UCTNode* getNewChild(UCTNode* node, std::default_random_engine& engine) {
  node->mutex.lock();
  if (node->possibleChildren.empty() && node->child == nullptr) {
    auto state = node->getState();
    auto legalMoves = state->getPossibleMoves();
    for (unsigned short i = 0; i < legalMoves.size(); ++i) {
      UCTNode* child = new UCTNode(*legalMoves[i], node);
      node->possibleChildren.push_back(child);
    }

    Point pass(BOARD_SIZE, BOARD_SIZE);
    UCTNode* passChild = new UCTNode(pass, node);
    node->possibleChildren.push_back(passChild);
  }

  if (node->possibleChildren.size() == 0) {
    node->mutex.unlock();
    return nullptr;
  }
  // else //Pick random child
  // {
    std::uniform_int_distribution<> dist(0, (int)node->possibleChildren.size()-1);
    unsigned int choice = dist(engine);
    UCTNode* chosenChild = node->possibleChildren[choice];
    // for(unsigned int i = 0; i < possibleChildren.size(); i++)
    //  if(i != choice)
    //    delete possibleChildren[i];
    // node->possibleChildren.erase(&node->possibleChildren.begin()+choice);
    node->possibleChildren[choice] = node->possibleChildren.back();
    node->possibleChildren.pop_back();
    node->mutex.unlock();
    return chosenChild;
  //  }
}

UCTNode* TreePolicy(UCTNode* node, std::default_random_engine& engine) {
  Point passPoint(BOARD_SIZE, BOARD_SIZE);
  while (!(node->move == passPoint && node->parent != nullptr && node->parent->move != passPoint)) {  // Not terminal
    UCTNode* newChild = getNewChild(node, engine);
    if (newChild != nullptr) {
      node->addChild(newChild);
      return newChild;
    } else {
      node = bestChild(node);
    }
  }
  Point pass(BOARD_SIZE, BOARD_SIZE);
  if (node->move != pass
    && node->move.color != Empty) {
    assert(false);
  }
  return node;
}

int DefaultPolicy(std::default_random_engine& engine, UCTNode* node, Board* clone, Patterns* patterns) {
  for (Group* g : clone->blackGroups)
    delete g;
  clone->blackGroups.clear();
  for (Group* g : clone->whiteGroups)
    delete g;
  clone->whiteGroups.clear();

  auto state = node->getState();
  auto startingTurn = state->turn;

  GameResult r;
  if (patterns != nullptr && patterns->initialized)
    r = state->playGame(patterns, engine);
  else
    r = state->playRandomGame(engine);

  if ((startingTurn == Black ? White : Black) == static_cast<int>(r))
    return 1;
  else if (r != Draw)
    return -1;
{'fraction_non_alphanumeric': 0.16636936615530978, 'fraction_numerical': 0.008324414317992627, 'mean_word_length': 3.6489773355444997, 'pattern_counts': {'":': 0, '<': 81, '<?xml version=': 0, '>': 140, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4339226', 'n_tokens_mistral': 2943, 'n_tokens_neox': 2862, 'n_words': 628}