← Back to concept explainers

Concept Fable

Tree search

Conclusion first:It expands a decision problem into a tree structure: the current state is the root node, each action produces child nodes, future possible states continue to expand, and finally a better path is chosen through evaluation.

Tree Search · Inference

Read the story first. There is no rush to give a definition here; let the question grow on its own first.

Fable

The chess player places small flags before the fork

When the young chess player first entered a major tournament, he played every move by feel. His teacher asked him: if you make this move, how might your opponent respond? And then what next? The young player shook his head; he saw only the square in front of him and remembered only the piece that had just been captured.

The master drew an upside-down tree on the table. The root was the current board position, and each branch was a possible move. Reaching a new node, the opponent had several branches again. Further down, the positions multiplied like a forest.

The youth tried to follow every branch to the end and soon broke down. After three steps there were already thousands of positions, and even calculating until dark would not finish. He first thought that an expert was someone who could see all paths, but the master said that being clever is not the same as exhausting everything.

They plant a small flag at each node: is this position probably favorable or unfavorable; is this path still worth pursuing; if it is already lost, there is no need to expand further; if several paths are similar, first explore the uncertain but potentially better one.

The first fix was not stable. The youth picked only the branches that looked best, and as a result missed the opponent's hidden counterattack; later he looked at a little of every branch, but the depth was insufficient and he was still ambushed. The master taught him to adjust back and forth between expansion, estimation, pruning and rollback.

What truly won the youth over was an endgame position. He captured a piece in front of him by feel, but was checkmated three moves later; if he had first let that piece go, he could instead force his opponent into a dead corner. For the first time, immediate gain and the later position separated in his mind.

Later, the youth played chess half a beat slower, but much more steadily. Each of his moves was no longer just an action, but a finite expanding tree walked through in his mind: probe, evaluate, prune, backtrack, then choose the branch that looked best at the moment.

Later the boy didn't think of every move as an entire forest either. When the position was simple, he played fast; when it was dangerous, he expanded more layers. The master said the little flags weren't meant to slow you down but to keep you from being fooled by a single stone in front of you at a critical fork. Later, when reviewing each game, he would also mark which branch was examined too early and which was pruned wrongly, making the next expansion more accurate.

Reveal

This story is about: tree search

It expands a decision problem into a tree structure: the current state is the root node, each action produces child nodes, future possible states continue to expand, and finally a better path is chosen through evaluation.

Tree search is often used in board games, planning, reasoning, and decision-making. The difficulty is that the number of branches explodes, so evaluation functions, pruning, backtracking, heuristic search, or Monte Carlo methods are needed to find a good enough choice within limited computational cost.

Metaphor mapping

  • Current board state: the root node of the search tree
  • Every possible move: action branch
  • The situation after the opponent responds: the next-layer state node
  • Planting small flags: position evaluation function
  • Cut away hopeless paths: pruning, reducing computational cost

Andy Ren Xu's judgment

Tree search reminds us that Agent planning is not a single flash of inspiration, but the exploration of possible paths under limited computation. In products, you need to control expansion depth, evaluation criteria, and failure fallback.

MCTStest-time computereasoningplanning
京ICP备2026014272号