mcts.cpp

Node* mcts(Node* root) {
    save();
    while (true) {
        if (TIME >= TIME_LIMIT) break;

        // select
        Node* node = root;
        while (!isTerminal() && node->isExpanded()) {
            node = node->uctChild();
            apply(node->action);
        }
        // expand
        if (!isTerminal() && !node->isExpanded()) {
            node = node->children[node->explored++];
            apply(node->action);
            node->init();
        }
        // simulate
        while (!isTerminal()) {
            auto acts = getActions();
            apply(acts[rnd(acts.size())]);
        }
        // backprop
        double score = getScore();
        while (node) {
            node->update(score);
            node = node->parent;
        }
        load();
    }

    return root->bestChild();
}