I am trying to implement MCTS for a custom word game I am working on. I feel like I have got all the pieces of code needed, but the algorithm seems to always return the first available move (first child of provided root note). I feel like this has something to do with the selection phase, as none of the children will have any visits after being created. Below is some of my code used in my implementation:

Node class containing game state, children/parent, visits/wins and functions for MCTS phases:

class MCTSNode {
    // Node stuff
    parent: MCTSNode | null;
    children: MCTSNode[];

    // Gamestate stuff
        I chose not to include this here as it is not important for the problem

    // Stats
    visits: number;
    wins: number;

    constructor(parent: MCTSNode | null) {
            Here I set all the gamestate stuff
        this.parent = parent;
        this.children = [];
        this.visits = 0;
        this.wins = 0;

    private getAvailablePlays(): Play[] {
            Returns an array of legal plays

    private play(play: Play): MCTSNode {
            Returns the resulting child node if a certain play is applied to the current node

    private getUCB1(biasParam: number = 2) {
        return this.wins / this.visits + Math.sqrt((biasParam * Math.log(this.parent!.visits)) / this.visits);

    private winner() {
            Returns winner of current node(game state) 
            null if game is not finished yet
            "" if game is draw
            "ai" if ai wins, "player" if player wins

    select(): MCTSNode {
        // implement logic to select a child node based on UCB1
        let node: MCTSNode = this;
        while (node.children.length > 0) {
            let bestNode = node.children[0];
            let bestUCB1 = -Infinity;
            for (let child of node.children) {
                let childUCB1 = child.getUCB1();
                if (childUCB1 > bestUCB1) {
                    bestNode = child;
                    bestUCB1 = childUCB1;
            node = bestNode!;
        return node;

    expand() {
        // Expand current node by adding all available child states(nodes) to children
        const availablePlays = this.getAvailablePlays();
        for (const play of availablePlays) {
            const child = this.play(play);

    simulate() {
        // implement logic to simulate a game from this node and return the score
        let currNode: MCTSNode = this;
        let winner = currNode.winner();

        while (winner === null) {
            let plays = currNode.getAvailablePlays();
            let play = plays[Math.floor(Math.random() * plays.length)];
            currNode = currNode.play(play);
            winner = currNode.winner();
        return winner;

    backpropagate(winner: string) {
        // implement logic to backpropagate the score to the parent nodes
        let currNode: MCTSNode | null = this;
        while (currNode !== null) {
            currNode.visits += 1;
            // Parent's choice (currNode.turn is either "ai" or "player")
            if (currNode.turn === winner) {
                currNode.wins += 1;
            currNode = currNode.parent;

MCTS Function that should return the most promising child node of root based on robust or max policy:

const mcts = (root: MCTSNode, rounds: number = 100, policy: string = "robust") => {
    for (let i = 0; i < rounds; i++) {
        let node = root.select();


        const winner = node.simulate();


    let max = 0;
    let bestNode: MCTSNode | null = null;
    for (let child of root.children) {
        if (policy === "robust" && child.visits > max) {
            max = child.visits;
            bestNode = child;
        if (policy === "max" && child.wins > max) {
            max = child.wins;
            bestNode = child;
    return bestNode;

I am mainly wondering if the select and mcts functions are implemented correctly. Furthermore I am currently storing the game state in each node. Is this a bad idea with regards to efficiency/memory?


1 Answer 1


Unexplored children

If a node has any unexplored children you have to select one of them, before computing UCB values and selecting the best one. Alternatively you could return +inf as the UCB value for nodes without any visits.

If you want to completely remove any bias towards the first move, you can also consider selecting a random unexplored one, instead of the first one. This is not that important though.

Storing the game state

For the game state you have two options:

  • store the game state in each node
  • compute the game state from scratch each time while selecting down the tree

This is a memory/compute tradeoff, depending on how large the board representation is and how expensive playing a move are both of them can make sense.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .