View source for Draft:Monte Carlo Tree Search (AlphaGO)

== Monte Carlo Tree Search at Google Deepmind ==

Monte Carlo tree search (MCTS) is used by Google DeepMind to help artificial intelligence systems make decisions, especially in complex games like Go. It works by simulating many possible future possibilities and using the results to guide decision-making.

MCTS builds a search tree representing different possible sequences of actions. It repeatedly selects good branches to explore further, simulates random playouts from those branches, and uses the results to update stats about which moves tend to lead to good outcomes. This allows the AI to focus its search on the most better lines of play, rather than exhaustively looking at every possibility.

== Definition ==
Monte Carlo tree search iteratively builds a search tree T representing the state space of a decision problem. Each node s in T represents a state, with child nodes representing possible next states after taking actions.

The core MCTS algorithm repeats these steps:

# Selection: Starting from the root, recursively select child nodes according to a tree policy π(s,a) until reaching a leaf node.
# Expansion: If the leaf node is not terminal, add one or more child nodes to it.
# Simulation: Perform a random playout from the new node(s) to a terminal state.
# Backpropagation: Use the result of the playout to update statistics in all nodes traversed in this iteration.

The tree policy π(s,a) balances exploration and exploitation, often using an equation like:

<math>\pi(s,a) = Q(s,a) + c * sqrt(ln(N(s)) / N(s,a))</math>

where <math>Q(s,a)</math> is the average outcome from taking action '''a''' in state '''s''', <math>N(s)</math> is the number of times '''s''' has been visited, <math>N(s,a)</math> is the number of times '''a''' was taken from '''s''', and '''c''' is an exploration constant.

== AlphaGO and Monte carlo tree search ==
'''Key Components:'''
# Policy Network: Predicts the probability distribution of moves given a board state.
# Value Network: Evaluates the likelihood of winning from a given position.
# Monte Carlo Tree Search: Explores possible future moves and outcomes.

'''MCTS Process in Alpha:'''
'''Alpha Go'''

'''''Selection'':''' Starting from the root node, select child nodes based on the UCT (Upper Confidence Bounds for Trees) formula:

<math>UCT=\frac{w_i}{n_i}+c\cdot \sqrt{\frac{lnN}{n_i}}</math>

where:
* <math>w_i</math> is the number of wins after the i-the move
* <math>n_i</math> is the number of simulations after the i-th move
* N is the total number of simulations run by the parent node
* c is the exploration parameters

'''''Expansion'':''' Add a new child node to the selected leaf node.

'''''Simulation'':''' Use the policy network to simulate the game from the new node.

'''''Backpropagation'':''' Update the statistics of all nodes in the path.

== Alpha Fold ==
# Sampling Protein Conformations: AlphaFold uses Monte Carlo sampling to explore the vast space of possible protein conformations.
# Refinement: Monte Carlo techniques are used in the refinement stage to optimize the predicted structures.
# Uncertainty Estimation: Monte Carlo dropout is used to estimate the uncertainty of predictions.


== Further Deepmind Projects ==

# AlphaZero: Generalized the MCTS approach used in AlphaGo to master multiple games (chess, shogi, and Go) without human knowledge2.
# MuZero: Further generalized the approach to learn the rules of the game, combining MCTS with model-based reinforcement learning.
# AlphaStar: While primarily using reinforcement learning, it incorporates Monte Carlo methods for exploring strategy spaces in StarCraft II.

== Results ==
DeepMind's use of MCTS in AlphaGo and subsequent systems produced several breakthrough results:
* In 2016, AlphaGo defeated world champion Lee Sedol at Go, considered a grand challenge for AI due to the game's enormous search space.
* AlphaGo Zero in 2017 surpassed all previous versions while learning entirely through self-play, without using human game data.
* The generalized AlphaZero algorithm achieved superhuman performance in chess, shogi, and Go using a single architecture.
These systems demonstrated how MCTS could be effectively combined with deep neural networks to tackle extremely complex decision problems.

== Decision-making for robotics with MCTS ==
MCTS is highly relevant to robotics decision-making as it provides a way to plan actions in large, uncertain state spaces. Some examples include:
* Path planning: MCTS can be used to find efficient robot paths through complex environments, considering obstacles and uncertainties.
* Task planning: For multi-step manipulation tasks, MCTS can plan sequences of actions to achieve goals.
* Human-robot interaction: MCTS can model human behavior and plan robot actions that account for potential human responses.
* 
The ability of MCTS to balance exploration and exploitation is particularly useful in robotics, where it's often necessary to make good decisions with limited time and computational resources.

== MCTS Variants ==
Several MCTS variants have been developed, including:
* UCT (Upper Confidence Bounds for Trees): The most common MCTS variant, using UCB1 for the tree policy.
* RAVE (Rapid Action Value Estimation): Shares value estimates between similar actions to speed up learning.
* PUCT (Predictor + UCT): Used in AlphaZero, incorporating a learned policy network to guide tree search.
*

== Applications ==
Beyond game-playing AI, MCTS has found applications in various domains:
* Planning and scheduling: Optimizing complex logistics or manufacturing processes.
* Autonomous vehicles: Decision-making for navigation and collision avoidance.
* Finance: Portfolio optimization and risk management.
* Healthcare: Treatment planning and drug discovery.

Some ongoing areas of MCTS research include:
* Improving sample efficiency to handle even larger state spaces.
* Developing better methods for handling partial observability and uncertainty.
* Integrating MCTS more tightly with deep learning and other AI techniques.
* Applying MCTS to increasingly complex real-world decision problems.

== References ==
<ref>{{cite web |title=A Novel Divide-and-Conquer Style Monte Carlo Tree Search Algorithm for Efficiently Collecting High-Quality Process Supervision Data |url=https://www.frontiersin.org/journals/neurorobotics/articles/10.3389/fnbot.2023.1039644/full |website=Frontiers in Neurorobotics |date=2023 |access-date=2024-10-11}}</ref>
<ref>{{cite web |title=Monte Carlo Tree Search: A Comprehensive Review |url=https://his.diva-portal.org/smash/get/diva2:1656144/FULLTEXT01.pdf |website=DIVA Portal |date=2023 |access-date=2024-10-11}}</ref>
<ref>{{cite web |title=Google DeepMind Researchers Propose a Novel Divide-and-Conquer Style Monte Carlo Tree Search (MCTS) Algorithm |url=https://www.marktechpost.com/2024/06/16/google-deepmind-researchers-propose-a-novel-divide-and-conquer-style-monte-carlo-tree-search-mcts-algorithm-omegaprm-for-efficiently-collecting-high-quality-process-supervision-data/ |website=MarkTechPost |date=2024-06-16 |access-date=2024-10-11}}</ref>
<ref>{{cite web |title=Monte Carlo Tree Search: An Introduction |url=https://towardsdatascience.com/monte-carlo-tree-search-an-introduction-503d8c04e168 |website=Towards Data Science |date=2021 |access-date=2024-10-11}}</ref>
<ref>{{cite web |title=Monte Carlo Tree Search: Key to AlphaGo Zero |url=https://www.linkedin.com/pulse/monte-carlo-tree-search-key-alphago-zero-toshifumi-kuga/ |website=LinkedIn |date=2023 |access-date=2024-10-11}}</ref>
<ref>{{cite web |title=Monte Carlo Tree Search for Games |url=https://dl.acm.org/doi/abs/10.1145/3543622.3573177 |website=ACM |date=2022 |access-date=2024-10-11}}</ref>
<references />