MCTS
Monte Carlo Tree Search; a search algorithm used in game-playing AIs like AlphaGo to explore possible move sequences.
As defined in dwarkesh_agi_is_still_30_years_away_ege_erdil_tamay_besirog
Where it comes up · 1
Most important claims · 10 of 11Search all claims for “MCTS” →
- MCTS acts as a policy-improvement operator: for every action taken in a game (whether the game was won or lost), the search provides a strictly better action/distribution to imitate, giving one low-variance supervision target per move rather than a single noisy win/loss signal for the whole trajectory.Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch
- MCTS is only guaranteed to improve the policy if the value estimates at the leaves are accurate; if training data lacks late-stage resolutions (e.g., bots resign rather than play to Tromp-Taylor end), bad terminal values propagate up through backups and PUCT, making MCTS produce a worse distribution than the raw policy—so the value function must be grounded, e.g. by forcing some games to resolve fully.Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch
- AlphaGo Lee averaged the value network estimate with a real policy-vs-policy playout to the end (α·Vθ + (1−α)·rollout) to ground value estimates, but all subsequent papers removed this; Jang's implementation also dropped it, which speeds things up greatly since you don't roll games out on every simulation.Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch
- AlphaGo is an elegant RL algorithm because it never has to start at a zero-percent success rate or solve the exploration problem of reaching non-zero success; every step is stable supervised learning (value classification plus policy KL minimization) on improved labels, so you can train arbitrarily large networks stably with simple infrastructure and never sit in a flat-gradient local minimum.Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch
- AlphaGo's core conceptual breakthrough was using neural networks to make Go's search problem tractable by shrinking both the breadth (a ~361 branching factor) and depth (~300 moves) of an otherwise astronomically large game tree (on the order of 361^300, more than the atoms in the universe), a problem long thought intractable this century.Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch
- By distilling the MCTS-improved distribution back into the raw policy network, you amortize the work that thousands of search simulations do into a single forward pass, so the next round of self-play starts from a much stronger base and reaches higher win rates for the same simulation budget.Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch
- Andy Jones's 'Scaling Scaling Laws with Board Games' showed you can trade off test-time compute and training compute—spending more compute on MCTS search yields performance equivalent to more training compute—anticipating LLM inference scaling, and additionally predicted how much compute is needed to solve a larger version of a board game.Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch
- The reason MCTS is so much more sample-efficient than LLM/robotics RL is that you can locally improve your policy per move—the search, truncated by a working value function, suggests a better next move even without unrolling the whole trajectory or being able to win the game—whereas in normal LLM/robotics RL there is no way to evaluate and improve a move independent of actually solving the whole problem.Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch
- Although AlphaGo vs. Lee used tens of thousands of simulations per move on a TPU pod, modern Go bots need little test-time compute because the policy improvement progressively pushes the search burden into the raw network, so most work is done in one forward pass with search only adding extra strength.Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch
- MCTS works for Go because value estimation is concrete (groundable) and the action space is discrete and bounded, suiting the PUCT exploration heuristic; for LLMs this breaks down because the √N/(1+Na) term assumes you re-sample the same child, but language's vast open-ended action space means you almost never sample the same continuation twice, so PUCT is too greedy and not the right way to guide tree search.Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch