Monte Carlo Tree Search (MCTS)

MCTS operates through a cyclical four-phase process applied repeatedly until a computational budget is exhausted:

• Selection: Starting from the root (target molecule), the algorithm traverses the tree using a tree policy (like UCT) to find the most urgent expandable node.
• Expansion: A new child node is added to the tree by applying a single-step retrosynthetic transformation to the selected molecule.
• Simulation (Rollout): From the new node, a default policy (often random or fast heuristic) plays out the synthesis until a terminal state (buyable building block or max depth) is reached.
• Backpropagation: The outcome of the simulation (e.g., route cost, success/failure) is propagated back up the tree, updating the visit count and value statistics of all ancestor nodes.

UCT is the mathematical formula that governs the Selection phase, balancing the exploration-exploitation trade-off. It scores a node i using: UCT(i) = (w_i / n_i) + c * sqrt(ln(N) / n_i).

• Exploitation Term (w_i / n_i): The average reward (e.g., route viability) of node i. Favors nodes with historically high success.
• Exploration Term (c * sqrt(ln(N) / n_i)): Increases for nodes with few visits (n_i) relative to the parent's total visits (N). The constant c tunes the exploration weight.
• This ensures that no potentially viable disconnection is permanently ignored due to early poor random sampling.

Unlike classical breadth-first or depth-first searches that expand nodes uniformly, MCTS grows the retrosynthetic tree asymmetrically. Computational effort is dynamically concentrated on the most promising branches.

• Deep Pathways: If a particular disconnection consistently leads to cheap, buyable precursors during rollouts, the algorithm will rapidly deepen that specific branch.
• Pruning by Neglect: Unpromising branches (e.g., those leading to complex, unstable intermediates) receive exponentially fewer visits and effectively self-prune.
• This property is critical for navigating the vast combinatorial explosion of chemical space without exhausting memory or time.

The Simulation phase relies on a fast, lightweight policy to estimate the value of a new state. In retrosynthesis, common rollout policies include:

• Random Disconnection: A transformation is selected uniformly at random from the set of applicable reactions until termination.
• Heuristic-Guided: A rapid, hand-crafted function scores disconnections based on simplicity (e.g., reducing molecular weight, lowering SAScore) and selects the best one greedily.
• Rollout Depth Limiting: To maintain speed, rollouts are typically capped at a shallow depth (e.g., 5-10 steps) or terminated immediately upon reaching a commercially available building block.

Modern chemical MCTS implementations replace the random rollout with a learned value network and guide expansion with a policy network, a technique popularized by AlphaGo.

• Policy Network: Predicts the prior probability of a specific disconnection being viable for a given molecule, drastically narrowing the branching factor during Expansion.
• Value Network: Directly estimates the expected route cost or success probability from a given molecular state, replacing the noisy Simulation step entirely.
• This hybrid approach allows the search to leverage deep chemical intuition learned from reaction databases like USPTO or Pistachio.

The definition of a terminal state and the associated reward signal directly shapes the search behavior:

• Terminal Condition: The search stops when a molecule is found in a Building Block Library (in-stock compounds) or when a maximum search depth is exceeded.
• Cost-Aware Reward: The backpropagated value is often the negative sum of step costs (e.g., reagent price, estimated yield loss). The algorithm maximizes this cumulative reward.
• Convergent Bonus: A reward shaping technique that provides a bonus when two independently synthesized branches can be joined, encouraging the discovery of more efficient Convergent Synthesis routes.