Monte Carlo Tree Search (MCTS)

The idea

Monte Carlo Tree Search picks strong moves by learning from experience instead of a hand-written scoring rule. It grows a search tree of possible moves, and for the promising ones it plays out many fast, random games to the finish to see how often they lead to a win. The more it looks, the smarter it gets, and it can stop and answer at any moment. This is the engine behind many top game-playing AIs, including AlphaGo.

How it works

1. Start with a tree that holds just the current game position (the root).
2. SELECTION: from the root, walk down the tree by repeatedly picking the child that scores best on UCB1, a formula that balances 'moves that have won a lot' against 'moves we've barely tried'.
3. EXPANSION: when you reach a position whose moves aren't all in the tree yet, add one new child node for an untried move.
4. SIMULATION (rollout): from that new node, play the rest of the game with quick random moves until someone wins, loses, or draws.
5. BACKPROPAGATION: take that result and update every node on the path back to the root, adding one visit and recording the win/loss.
6. Repeat selection to backpropagation as many times as your time or compute budget allows.
7. When time runs out, pick the root's child with the most visits (the most-tested, most-trusted move) and play it.

OPEN, CLOSED & the data structures

["A game tree of nodes, where each node is a game position.", "Per node: N (number of times visited) and W (total reward/wins accumulated) — these two counters are the whole memory of what has been learned.", "Each node also knows its untried moves (for expansion) and its parent (so results can travel back up).", "The UCB1 score, computed on the fly during selection from each child's N and W plus the parent's total visits — no stored heuristic table."]

Pseudocode

function MCTS(root, budget):
    while within budget:
        node = SELECT(root)         # walk down using UCB1
        child = EXPAND(node)        # add one new untried move
        result = SIMULATE(child)    # random rollout to game end
        BACKPROPAGATE(child, result)
    return most_visited_child(root).move

function SELECT(node):
    while node fully expanded and not terminal:
        node = argmax over children c of
               (c.W / c.N) + C * sqrt(ln(node.N) / c.N)   # UCB1
    return node

function BACKPROPAGATE(node, result):
    while node is not null:
        node.N = node.N + 1
        node.W = node.W + result    # from that node's player's view
        node = node.parent

At a glance