Cognition · Software component
MCTS Planner
Software componentCognitionCognition & Memoryarc:MCTSPlanner
A task planner that incrementally grows a search tree from the current state by repeated selection, expansion, simulation and backpropagation cycles, returning the most-visited action within a compute budget.
Responsibility. Selects the next action by sampling-guided asymmetric tree search over possible futures.
Also known as: Monte Carlo Tree Search controller, MCTS search controller, Simulation-based planner
Variant of Task Planner abstract
When to choose. Choose when heuristics are hard to design, the state space is enormous, near-optimal solutions are acceptable for faster computation, transitions are stochastic or partially observable, or asymmetric tree growth pays off (game playing, robotic task planning, chemical retrosynthesis, navigation among dynamic crowds).
Relationships
is configured by structural
invokes dependency
reads dependency
writes dependency
emits telemetry to dynamic
sends data to dynamic
is constrained by control
is evaluated by assurance
- Task Success Evaluator abstract Ch5.5
alternative to variability
Design guidance
- SHOULD select the final action by highest visit count rather than highest average value.
- SHOULD tune the exploration constant C per domain, larger for noisy rewards and smaller for consistent feedback.
- SHOULD log tree depth and visit-count distribution to detect insufficient simulation budget or poorly tuned exploration.
- SHOULD choose parallelization by simulation cost: root or coarse-grained for cheap rollouts, tree parallelization for expensive neural evaluations.
- MUST use statistically independent random number generation for each simulation, e.g., thread-local RNG in parallel implementations.
Quantitative guidance
As stated by the sources; verify before use.
- Go has about 10^170 possible board positions (Ch5.5).
- Default exploration constant C = sqrt(2) ~= 1.414; C < 0.5 causes premature convergence and C > 3 excessive exploration; C ~= 1.0 for low-variance and ~= 2.0 for high-variance domains (Ch5.5).
- Well-tuned C shows a clear winner with 30-60% visit share and competitive alternatives at 10-20% each (Ch5.5).
- Branching factor: chess 30-35, Go ~250 in the opening; 100 simulations at branching 30 expand only 2-3 levels; 10x budget is a reasonable remediation (Ch5.5).
- Real-time budgets: ~1 s per game move, 50 ms for autonomous-vehicle control, 500 ms for web navigation (Ch5.5).
- AlphaGo ran 100,000 simulations per move with network evaluation; pure MCTS needs 10-100x more rollout-based simulations; near-linear speedup to 48 workers (Ch5.5).
Classification
- Patterns
- Monte Carlo Tree Search (MCTS)UCT (Upper Confidence Bound applied to Trees)UCB1 exploration-exploitationSelective one-child expansionOutcome sampling for stochastic transitionsProgressive wideningAction pruningTree reuseMost-visited final action selectionLeaf parallelizationTree parallelizationRoot parallelizationNeural-guided MCTS (AlphaGo/AlphaZero)Negated backpropagation for two-player zero-sum gamesDiscretization of continuous actions
- Quality attributes
- Performance efficiency (ISO/IEC 25010)Reliability (ISO/IEC 25010 | NIST AI RMF: valid and reliable)
- Risks mitigated
- Exhaustive search intractabilityPremature convergence on locally optimal actions
Sources
- Ch5.5: T. Nguyen, "Monte Carlo Tree Search Fundamentals," in Mastering Agentic AI Systems: Guide for the NVIDIA NCP-AAI Exam, 1st ed. 2026, ch. 5.5. ISBN: 9798244538229.