Nested Monte Carlo Search (NMCS) Algorithms#

This tutorial demonstrates how to use Nested Monte Carlo Search (NMCS) and Lazy NMCS algorithms for retrosynthetic planning in SynPlanner.

Background#

Nested Monte Carlo Search (NMCS) is a recursive search algorithm introduced by Cazenave (2009) for single-player optimization problems. Unlike iterative MCTS (UCT), NMCS performs a deterministic, nested search:

At level 0: A playout is performed using a configured mode (greedy, random, or policy-guided)
At level n (n > 0): For each possible move, a level (n-1) search is performed, and the move leading to the best outcome is selected

Lazy NMCS is an extension that uses percentile-based pruning to reduce the branching factor, making it faster while maintaining search quality.

Key Differences from UCT#

Aspect	UCT (MCTS)	NMCS / Lazy NMCS
Search type	Iterative	One-shot recursive
Iterations	Many (100-1000+)	Single pass
Exploration	UCB-based selection	Nested rollouts
Stopping	Iteration/time limit	Exhaustive within level

1. Setup and Data Loading#

First, let’s download the necessary data and load our resources.

[ ]:

from pathlib import Path
from synplan.utils.loading import download_preset

# Download SynPlanner preset data
paths = download_preset("synplanner-article", save_to="synplan_data")

# Paths to resources
ranking_policy_network = paths["ranking_policy"]
reaction_rules_path = paths["reaction_rules"]
building_blocks_path = paths["building_blocks"]

[2]:

from synplan.utils.loading import load_building_blocks, load_reaction_rules, load_policy_function

# Load resources
building_blocks = load_building_blocks(building_blocks_path, standardize=True)
reaction_rules = load_reaction_rules(reaction_rules_path)
policy_function = load_policy_function(weights_path=ranking_policy_network)

print(f"Loaded {len(building_blocks)} building blocks")
print(f"Loaded {len(reaction_rules)} reaction rules")

Lightning automatically upgraded your loaded checkpoint from v1.9.5 to v2.5.1.post0. To apply the upgrade to your files permanently, run `python -m pytorch_lightning.utilities.upgrade_checkpoint synplan_data/uspto/weights/ranking_policy_network.ckpt`

Loaded 189144 building blocks
Loaded 24094 reaction rules

[ ]:

from synplan.chem.utils import mol_from_smiles

# Capivasertib (FDA-approved 2023 for breast cancer)
example_smiles = "NC1(C(=O)N[C@@H](CCO)c2ccc(Cl)cc2)CCN(c2nc[nH]c3nccc2-3)CC1"
target_molecule = mol_from_smiles(example_smiles, clean2d=True, standardize=True, clean_stereo=True)

print(f"Target molecule: {example_smiles}")
target_molecule

2. Evaluation Strategy#

We’ll use rollout evaluation for node scoring.

[4]:

from synplan.utils.config import RolloutEvaluationConfig
from synplan.utils.loading import load_evaluation_function

eval_config = RolloutEvaluationConfig(
    policy_network=policy_function,
    reaction_rules=reaction_rules,
    building_blocks=building_blocks,
    min_mol_size=6,
    max_depth=9,
)

evaluation_function = load_evaluation_function(eval_config)

3. Using NMCS Algorithm#

NMCS is configured through TreeConfig by setting algorithm="nmcs". Key parameters:

nmcs_level: Nesting depth (default: 2). Higher = more thorough but slower.
nmcs_playout_mode: How level-0 playouts select moves:
- "greedy": Select move with highest value score
- "random": Random selection
- "policy": Select move with highest policy probability

Important: NMCS completes in a single iteration. Set max_iterations=1 and use max_time for stopping.

[ ]:

from synplan.utils.config import TreeConfig
from synplan.mcts.tree import Tree
from synplan.route_quality.scorer import ProtectionRouteScorer

# Protection-aware route scorer (uses bundled SMARTS and incompatibility matrix)
route_scorer = ProtectionRouteScorer.from_config()

# NMCS Configuration
nmcs_config = TreeConfig(
    algorithm="nmcs",           # Use Nested Monte Carlo Search
    nmcs_level=2,                # Nesting level (1-3 recommended)
    nmcs_playout_mode="greedy",  # Playout mode: "greedy", "random", or "policy"
    max_iterations=1,            # NMCS completes in single iteration
    max_time=60,                 # Time limit in seconds
    max_depth=9,
    min_mol_size=6,
    search_strategy="expansion_first",
)

print("NMCS Configuration:")
print(f"  - Algorithm: {nmcs_config.algorithm}")
print(f"  - Nesting level: {nmcs_config.nmcs_level}")
print(f"  - Playout mode: {nmcs_config.nmcs_playout_mode}")
print(f"  - Max time: {nmcs_config.max_time}s")

[ ]:

# Create and run NMCS tree
nmcs_tree = Tree(
    target=target_molecule,
    config=nmcs_config,
    reaction_rules=reaction_rules,
    building_blocks=building_blocks,
    expansion_function=policy_function,
    evaluation_function=evaluation_function,
    route_scorer=route_scorer,
)

# Run the search
for solved, node_id in nmcs_tree:
    pass  # NMCS completes in first iteration

print(nmcs_tree)

4. Using Lazy NMCS Algorithm#

Lazy NMCS adds percentile-based pruning to reduce computation:

All candidate moves are quickly evaluated using greedy playouts
Only moves scoring above a percentile threshold are explored with full NMCS recursion

Additional parameter:

lnmcs_ratio: Pruning threshold (default: 0.2). A value of 0.2 means only top 80% candidates are explored.

[7]:

# Lazy NMCS Configuration
lazy_nmcs_config = TreeConfig(
    algorithm="lazy_nmcs",       # Use Lazy NMCS with pruning
    nmcs_level=2,                # Nesting level
    nmcs_playout_mode="greedy",  # Playout mode for level-1 rollouts
    lnmcs_ratio=0.2,             # Prune bottom 20% candidates
    max_iterations=1,            # Single iteration
    max_time=60,                 # Time limit
    max_depth=9,
    min_mol_size=6,
    search_strategy="expansion_first",
)

print("Lazy NMCS Configuration:")
print(f"  - Algorithm: {lazy_nmcs_config.algorithm}")
print(f"  - Nesting level: {lazy_nmcs_config.nmcs_level}")
print(f"  - Playout mode: {lazy_nmcs_config.nmcs_playout_mode}")
print(f"  - Pruning ratio: {lazy_nmcs_config.lnmcs_ratio} (explore top {100*(1-lazy_nmcs_config.lnmcs_ratio):.0f}%)")

Lazy NMCS Configuration:
  - Algorithm: lazy_nmcs
  - Nesting level: 2
  - Playout mode: greedy
  - Pruning ratio: 0.2 (explore top 80%)

[ ]:

# Create and run Lazy NMCS tree
lazy_nmcs_tree = Tree(
    target=target_molecule,
    config=lazy_nmcs_config,
    reaction_rules=reaction_rules,
    building_blocks=building_blocks,
    expansion_function=policy_function,
    evaluation_function=evaluation_function,
    route_scorer=route_scorer,
)

# Run the search
for solved, node_id in lazy_nmcs_tree:
    pass

print(lazy_nmcs_tree)

5. Comparing with UCT (Standard MCTS)#

Let’s run UCT on the same target for comparison.

[ ]:

# UCT Configuration (standard MCTS)
uct_config = TreeConfig(
    algorithm="uct",
    max_iterations=100,
    max_time=60,
    max_depth=9,
    min_mol_size=6,
    ucb_type="uct",
    c_ucb=0.1,
    search_strategy="expansion_first",
)

uct_tree = Tree(
    target=target_molecule,
    config=uct_config,
    reaction_rules=reaction_rules,
    building_blocks=building_blocks,
    expansion_function=policy_function,
    evaluation_function=evaluation_function,
    route_scorer=route_scorer,
)

for solved, node_id in uct_tree:
    pass

print(uct_tree)

[10]:

# Summary comparison
print("Algorithm Comparison:")
print("=" * 60)
print(f"{'Algorithm':<15} {'Routes Found':<15} {'Nodes':<10} {'Time (s)':<10}")
print("-" * 60)
print(f"{'NMCS':<15} {len(nmcs_tree.winning_nodes):<15} {len(nmcs_tree):<10} {nmcs_tree.curr_time:.1f}")
print(f"{'Lazy NMCS':<15} {len(lazy_nmcs_tree.winning_nodes):<15} {len(lazy_nmcs_tree):<10} {lazy_nmcs_tree.curr_time:.1f}")
print(f"{'UCT':<15} {len(uct_tree.winning_nodes):<15} {len(uct_tree):<10} {uct_tree.curr_time:.1f}")

Algorithm Comparison:
============================================================
Algorithm       Routes Found    Nodes      Time (s)
------------------------------------------------------------
NMCS            0               2860       0.0
Lazy NMCS       0               2002       0.0
UCT             0               1225       11.6

6. Visualizing Results#

Let’s visualize any found routes.

[11]:

from IPython.display import SVG, display
from synplan.utils.visualisation import get_route_svg

def show_routes(tree, algorithm_name, max_routes=2):
    """Display found routes for a tree."""
    if not tree.winning_nodes:
        print(f"\n{algorithm_name}: No routes found")
        return

    print(f"\n{algorithm_name}: Found {len(tree.winning_nodes)} route(s)")
    for i, node_id in enumerate(tree.winning_nodes[:max_routes]):
        print(f"  Route {i+1} (node {node_id}, score: {tree.route_score(node_id):.3f})")
        display(SVG(get_route_svg(tree, node_id)))

# Show routes from each algorithm
show_routes(nmcs_tree, "NMCS")
show_routes(lazy_nmcs_tree, "Lazy NMCS")
show_routes(uct_tree, "UCT")


NMCS: No routes found

Lazy NMCS: No routes found

UCT: No routes found

7. Parameter Tuning Guidelines#

NMCS Level#

Level	Behavior	Use Case
1	Single playout per move	Fast but shallow
2	Nested search (recommended)	Good balance
3+	Deep nested search	Complex molecules, more time

Playout Mode#

Mode	Description	When to Use
`greedy`	Select highest-value moves	Default, good general performance
`policy`	Select highest-probability moves	When policy is well-trained
`random`	Random selection	Exploration, diversity

LazyNMCS Ratio#

Ratio	Candidates Explored	Trade-off
0.0	100% (no pruning)	Slowest, most thorough
0.2	Top 80%	Recommended default
0.5	Top 50%	Faster, may miss solutions
0.8	Top 20%	Very fast, aggressive pruning

[12]:

# Example: Higher nesting level for complex molecules
deep_nmcs_config = TreeConfig(
    algorithm="nmcs",
    nmcs_level=3,                # Deeper search
    nmcs_playout_mode="policy",  # Use policy probabilities
    max_iterations=1,
    max_time=120,                # More time for deeper search
    max_depth=9,
    min_mol_size=6,
)

print("Deep NMCS config created (nmcs_level=3, playout_mode=policy)")
print("Use this for complex molecules that require more thorough search.")

Deep NMCS config created (nmcs_level=3, playout_mode=policy)
Use this for complex molecules that require more thorough search.

Summary#

NMCS (algorithm="nmcs"): Recursive nested search, good for thorough exploration
Lazy NMCS (algorithm="lazy_nmcs"): Faster variant with pruning
Both complete in a single iteration (set max_iterations=1)
Key parameters: nmcs_level, nmcs_playout_mode, lnmcs_ratio

For more details, see the official documentation.