MONTE CARLO TREE SEARCH

Overview

MCTS is a probabilistic algorithm that uses random sampling to make decisions in games and optimization problems. It builds a search tree asymmetrically, focusing computational resources on promising paths.

Four Phases

1.Selection - Navigate to leaf node
2.Expansion - Add new child nodes
3.Simulation - Random playout
4.Backpropagation - Update statistics

UCB1 Formula

UCB1 = w_i/n_i + c√(ln(N)/n_i)

where:
w_i = wins for node i
n_i = visits for node i  
N   = total parent visits
c   = exploration constant

Advantages

Works without domain knowledge

Anytime algorithm

Handles large search spaces

Asymmetric tree growth