When search runs out
World models · 2026 · Part 2 of The drone and the world model
Board games can be searched because the rules say exactly what happens after every move. This page follows that idea from a tiny game tree to AlphaGo’s tree search, counts what it costs, and shows where it breaks once the rules are gone.
World models · part 2
When Search Runs Out
Chess and Go fell to the same trick: imagine every move, look at where it leads, pick the best one. A machine can do that because the rules of the game tell it exactly what happens next. So why can't a self-driving car just search its way through a roundabout?
This page follows the trick from a tiny game tree to AlphaGo's search, then counts what it costs and shows where it breaks. Each idea has a lab. Wherever a shortcut version of an equation is commonly written, it's marked COMMON SLIP and the correct form is shown.
Notation
Nine symbols for this page
1 · Looking ahead
Pick the move whose worst case is best
From the board st, list every move. Under each move, list every reply the opponent could make. Keep going for n moves, then score each final position with a value function V. Now choose.
The tempting rule is “choose the move that leads to the highest score anywhere below it”. That rule quietly assumes the opponent will help you. They won't: after your move, they pick the reply that is worst for you.
Lab 1 · Hopeful versus careful
3 moves for me, 3 replies each, scores from my sidePositions are drawn at random, then kept only if the two rules disagree, so you can see the difference every time.
Each extra ply multiplies the leaves by the number of moves. Chess has about 35 moves per position, so 6 plies is already about 1.8 billion leaves (356). The rest of this page is about how to look ahead without visiting all of them.
2 · Sizing up three problems
Chess, Go and driving, by the STAR numbers
STAR asks four questions: how many States, what is the Transition (what happens next), how many Actions, and what Reward. Red cells are the ones that hurt.
| Chess | Go (19×19) | Driving | |
|---|---|---|---|
| |S| | about 4.8 × 1044 legal positions“3264” is a common overcount | 3361 ≈ 1.7 × 10172 ways to fill the boardabout 2.1 × 10170 are legal | camera pixels, other cars, weather: effectively endlesssurvivable: a network squeezes it into a small latent |
| T | the rules, known exactlyonly the opponent's choice is unknown | the rules, known exactlyonly the opponent's choice is unknown | unknown, and other drivers react to youno rulebook to search with |
| |A| | 20 at the start, about 35 on average | 362 (361 points + pass), about 250 legal on average | continuous: any steering angle, any pedal force |
| R | +1 / 0 / −1 at the end | z = +1 or −1 at the end | safe, smooth, on time, legal: many goals, scored all the time |
Common slip: “T = ?” for chess and Go
In board games the transition is not a mystery. The rules say exactly which board follows each move, for free and with no error. The only unknown is which move the opponent picks, and in self-play the opponent is a copy of yourself. That perfect simulator is the reason search works so well here. Driving is the first column where T really is unknown.
3 · One network, two answers
A gut feeling for moves, and a guess at who wins
AlphaGo Zero (2017) uses one network fθ. It reads the board and gives two answers at once: a probability for every move, and a single number saying who is winning.
Training data comes from self-play. The best network so far plays games against itself, guided by the search in section 4. Each position s is saved with two labels: π, how the search spread its effort over the moves, and z, who finally won (+1 if the player to move in s won, −1 if not). The loss pulls the network towards both labels:
Lab 2 · Train on one position
6 candidate moves; the search already chose πMoves: network guess p (filled) vs search target π (outline)
Who wins: guess v vs result z
Loss terms
Each step is a real gradient step on this one position (learning rate 0.5 on the move scores, 0.3 on the value). The policy term never reaches zero: its floor is the entropy of π, drawn as the thin marker. The first AlphaGo (2016) used two separate networks and fast random play-outs; the single two-headed network and this exact loss come from AlphaGo Zero.
4 · Monte Carlo tree search
Spend your look-aheads where they matter
Instead of expanding every branch, the search runs many short simulations. Each one walks down from the root, choosing one move at every level. When it reaches a position nobody has looked at yet, it asks the network once for p and v. Then it walks back up, adding v to every move on the path. At each step down it chooses the move with the highest score:
Lab 3 · Watch a search think
7 moves at the root, 5 replies under each; the network's favourite is not the best moveRoot moves
| move | P | N | Q | bonus |
|---|
π = N / ΣN, the training target
★ marks the truly best move, which the lab knows and the search doesn't. Node size is visits, colour is the average value Q (green good, red bad). To keep the numbers readable, this toy has one player and stops growing at depth 2; in Go the value flips sign at each level, because the levels alternate between you and your opponent.
When the search ends, the move is chosen from the visit counts, not from Q. The share of visits per move is π, and that same π becomes the target in the loss above. The search acts like a teacher: slow but careful. The network learns to imitate it, and then the next search starts from a better prior. The tree itself is thrown away after each move.
5 · The bill
What one move costs
AlphaZero runs 800 simulations per move, and AlphaGo Zero ran 1,600 (about 0.4 seconds per move on its hardware). Each simulation calls the network once, at the new position it reaches. On the way down, the rules give the next board and the stored counts pick the moves, so no network call is needed there.
Common slip: 800 × 30 = 24,000 calls per move
Multiplying by the depth counts a network call at every level of every simulation. That's not how the search works: it's 800 simulations, so about 800 calls (sent to the network in small batches). The depth isn't fixed at 30 either. Each simulation goes as deep as the tree has grown along its path, often only a few levels.
Lab 4 · Grow the board
keep the ratio of 800 simulations per 361 moves (about 2.2 visits per move)moves |A|
362
simulations per move
800
network calls
800
the slip's count (×30)
24,000
Thinking time per move (log scale), at 4,000 network calls per second
4,000 calls per second is AlphaGo Zero's own pace: 1,600 simulations in about 0.4 s. Visiting every move about twice is a pessimistic rule. A good prior lets the search ignore most moves, and on a 19×19 board most of the 800 simulations go to a handful of moves. But the prior has to be good across all of |A|, and for a steering wheel you can't even list the moves.
6 · Leaving the board
Three things Go gives you that the road doesn't
A small, listable |A|
Search adds up visit counts per move. That needs a short list of moves. A car's steering and pedals are continuous, so any list is an approximation, and a fine one is enormous.
A perfect, unchanging simulator
Every simulation asks the rules what happens next. The rules of Go are exact and never change. A market, a startup or a busy street has no rulebook, and its behaviour drifts over time.
Time to think
In the 2016 match against a world champion, each side had 2 hours plus three 60-second overtime periods. A driving planner usually re-plans about 10 times a second, which leaves about 0.1 s.
Common slip: “homoscedastic”
Homoscedastic is a statistics word. It means the noise has the same spread everywhere, for example the errors of a regression line. The property Go has, and the real world lacks, is a different one: the environment is stationary (the rules don't change over time) and known (you can simulate it exactly).
7 · Self-driving
The car that never moves
A huge state space is survivable: a network can squeeze camera images into a small latent, the same way AlphaGo's network squeezes the board. The hard part of driving is T. Your own car follows Newton's laws, but every other car has a driver, and drivers react to you.
Suppose you predict the other cars as if they were rocks on fixed paths: they keep their speed whatever you do. Then in dense traffic every way of joining collides with somebody. The safest plan becomes “never move”. Robotics calls this the freezing robot problem. Real drivers merge by edging in and trusting the car behind to ease off. To plan that, your model has to include the other drivers' reactions to your action.
Lab 5 · Join the traffic
the violet car waits at the side road; dashed boxes are what its model predicts if it goes nowcars merged
0
waiting for
0.0 s
closest gap so far
–
The simulated traffic always reacts: each driver keeps a safe gap to whatever is ahead, braking up to 6 m/s². Only the waiting car's model changes. “Rocks” goes only if a 2 m gap survives 5 s of the other cars holding their speed. “React” goes if its model of the drivers says no one comes within 1 m and the car behind brakes no harder than 4 m/s². Here the “react” model is the true driver behaviour; a real car would have to learn it from data.
8 · Where this leads
Search needs a simulator. A world model is a learned one.
Every piece of AlphaGo's search leaned on the rules to answer “if I play this, what board comes next?”. Take the rules away and the search has nothing to walk on. The next step was to learn that answer. MuZero (2019) learns a model that predicts the next latent state, the reward and the value, and runs the same tree search inside it. With that it plays Atari, Go, chess and shogi without being told the rules.
MuZero still needs a short list of moves and plenty of thinking time, so two of the three problems above remain. Handling continuous actions and acting in real time is where the newer world models in this section come in.
Based on minutes 20–40 of the YC Decoded video “World Models: An intuitive introduction” (July 2026). The equations were checked against the video's whiteboard and corrected where needed.
Sources. AlphaGo (Nature 2016) · AlphaGo Zero (Nature 2017) · AlphaZero (2017) · MuZero (2019) · 2016 match rules · Counting Go positions · Robot navigation in dense crowds: the case for cooperation · Getting robots unfrozen in dense crowds · Homoscedasticity