Monte Carlo Tree Search

Monte Carlo Tree Search (MCTS) is an algorithm commonly used for finding optimal decisions in a given domain by taking random samples in the decision space and building a search tree based on the results. It is most famously used in board games like Go and Chess but has applications in various fields such as robotics, resource management, and artificial intelligence in general.

MCTS has gained widespread attention because of its simplicity and effectiveness, particularly in scenarios where the decision space is too large to exhaustively search. It is also a suitable choice for problems where the transition model and reward function are not known or too complex to describe with a simple formula.

How MCTS Works

The MCTS algorithm consists of four main steps repeated multiple times:

1. Selection: Starting at the root node (representing the current game state), a tree policy guides the selection of child nodes down to a leaf node. The tree policy is typically based on a balance between exploiting nodes with high average reward and exploring less-visited nodes.
2. Expansion: Once a leaf node is reached, one or more child nodes are added to expand the search tree, based on the available actions.
3. Simulation: A simulation is run from the new leaf node according to a default policy to produce an outcome. This step is also called a "rollout."
4. Backpropagation: The result of the rollout is backpropagated up the tree to update the information stored in the nodes visited during the selection phase.

After a predefined number of iterations or a computational budget has been reached, the algorithm picks the action leading to the node that appears most promising based on the stored values.

Example Python Code

Here's a simplified Python code snippet illustrating a very basic MCTS. Note that this example is very minimal and doesn't include all the optimizations you might find in a full-fledged implementation.

import random

class Node:
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent
        self.children = []
        self.visits = 0
        self.value = 0

def rollout(node):
    # Simulate a game from this node to a terminal state and return the reward
    # For now, let's return a random reward
    return random.choice([-1, 1])

def select(node):
    # Implement your tree policy here to select a child node from the given node
    # For simplicity, let's choose a random child node
    return random.choice(node.children) if node.children else None

def expand(node):
    # Generate a child node and add it to the children of the current node
    # For this example, let's assume the state is an integer and the action is to add 1 or 2
    new_state = node.state + random.choice([1, 2])
    child = Node(new_state, parent=node)
    node.children.append(child)
    return child

def backpropagate(node, reward):
    # Propagate the reward back to the root
    while node:
        node.visits += 1
        node.value += reward
        node = node.parent

def mcts(root, iterations=1000):
    for _ in range(iterations):
        node = root
        while node.children:
            node = select(node)
        if node.visits == 0:
            reward = rollout(node)
        else:
            node = expand(node)
            reward = rollout(node)
        backpropagate(node, reward)

# Example usage
root = Node(state=0)
mcts(root)