liveBook · Manning

Monte Carlo Tree Search

As explained in Grokking Bayes

Monte Carlo tree search is a sequential decision algorithm that simulates selected future branches and propagates their outcomes through a search tree.

When a decision unfolds over several steps, choosing the best immediate action may miss better futures. Monte Carlo tree search (MCTS) addresses this by simulating many, but not all, possible futures and using their outcomes to guide the next action. section 12.10 section 12.11

MCTS works as a strategic approximation rather than an exhaustive calculation:

  • Represent possible actions and their consequences as branches in a search tree. section 12.10
  • Select several promising branches instead of examining every possible future. section 12.10
  • Simulate future outcomes, then propagate terminal utilities back toward the initial decision nodes. section 12.10
  • Allocate more effort to promising actions, balancing useful exploration with the cost of an intractable full calculation. section 12.10 section 12.11

Game-playing engines

MCTS is used in sophisticated decision-making engines for board games, including high-performing systems such as AlphaZero for chess and AlphaGo for Go. section 12.10

How Grokking Bayes covers it

How deep it goes
Explains selective branch exploration, simulation, and utility backpropagation, but does not specify a complete implementation procedure.
Examples
Uses board-game engines such as AlphaZero for chess and AlphaGo for Go as practical examples.
What it assumes
Assumes utility, expected utility, and sequential decision-making as the surrounding decision framework.
What you can do after
Evaluate/understand how sampled futures approximate expected-utility decisions in sequential problems.
How it connects
Connects Bayesian decision theory, expected utility, sequential decision-making, and the exploitation–exploration tradeoff.

Also explained in

Compare how 2 books explain Monte Carlo Tree Search →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking Bayes. The section links point to the parts of the book it draws on.