MCTS: How to select children when none of them are visited?

Question

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);
            this.children.push(child);
        }
    }

    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();

        node.expand();

        const winner = node.simulate();

        node.backpropagate(winner);
    }

    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?

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.