# Monte Carlo Tree Search (MCTS)
Monte Carlo Tree Search (MCTS) is a technique that provides an effective way to search game trees that have a high branching factor. Instead of performing exhaustive search, MCTS relies on random simulations that construct the tree while guided by statistical physics. This technique has gained popularity recently due to its use and success in beating the World Go Champion in the ancient game of Go. Unfortunately, Go has a high branching factor, requires a high compute budget, thus making traditional game tree search techniques ineffective.
MCTS is effective for such computationally intractable problems. It considers the current state as multi-arm bandit problem approach to add bias to the sampling step, whereby investing the available compute budget or time in exploring parts of the tree that look the most promising from a perspective of a given player. MCTS implementation is relatively simple and doesn’t require game specific knowledge or careful crafting of the domain specific evaluation function,thus making it useful for general game playing.
MCTS starts by building a partial tree that represents a subset of paths you could follow from a given state s. Like other game trees, the nodes represent the game states and edges/arcs represent the available moves. The tree gets updated with each iteration, thus growing over time in an asymmetrical manner due to bias used in the simulations. Each iteration of MCTS has available four functions which would be called upon depending on the situation. They are illustrated in the Figure below
**Selection**:In this step we start from the root node and traverse the tree all the way down to the leaf node or a node that hasn’t fully been expanded yet. At each level we select the node that looks potentially most promising. UCB1 Algorithms provides a specific way to do it instead of picking it randomly. The step is repeated until we have collected the statistics for all child positions.
**Expansion:**We perform this step by randomly picking an unexplored child when we cant apply the UCB1 algorithm. The result is a new node where we record the statistics.
**Simulation/Sampling:Using** the default policy defined earlier we per-form a Monte Carlo simulation random playout between the two players involved. We could also make use of weighting heuristics depending branching factor, the compute budget and associated cost of heuristics.
**Backpropagation**: At the end of each iteration we rollback while updating the statistic results that represent the reward value collected in the simulation. In most cases we record the number of times that a given node was part of the path that led to success outcome and total number of times it was explored.
When the available compute budget is utilized completely it uses this information to return the a decision on the best move selection
**Complete Algorithm:**
**reference**: A Survey of Monte Carlo Tree Search Methods:
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://hitchhikerguide.gitbook.io/graphs/monte-carlo-tree-search-mcts.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.
