Monte Carlo Tree Search

In games like chess or Go, there are many legal moves available in every position. After each move the opponent responds, then the next move follows, and the number of possible sequences grows beyond imagination. Calculating everything through to the end is therefore hopeless. Monte Carlo Tree Search takes a different approach: from each move, it tries out a number of continuations, often using random decisions, and remembers how these games ended. Moves that frequently led to a win are then examined more closely. The name comes from Monte Carlo, the famous casino town, because the method deliberately works with chance.

Why randomness computes better than completeness

Classical game programs work with an evaluation function. This is a formula that assigns a score to a position, for example based on the material value of the pieces. In chess this works well, because one roughly knows what makes a strong position. In the board game Go, this approach failed for a long time: stones all have the same value, and whether a position is good depends on the overall pattern.

This is exactly where tree search with random games helps. It doesn’t need a good formula for intermediate positions. It only needs the rules of the game and the outcome at the end. That is why it was the breakthrough for Go programs, after classical methods had remained weak there for decades.

A second advantage is fairness with respect to computing time. One can stop the procedure after ten milliseconds or after ten minutes. It always delivers an answer, just a worse or better one. This property is called anytime behavior, and it is valuable both in competitions and in products.

The four steps per iteration

The procedure gradually builds up a search tree. A search tree is a structure in which each node represents a game position and each branch represents a possible move. One iteration consists of four steps: selection, expansion, simulation, and backpropagation. These four steps are repeated thousands or millions of times.

During selection, the program moves downward from the start node and chooses a move at each branch. Here a trade-off applies: moves with a good track record so far are attractive, but rarely tested moves are as well. This trade-off is called exploration versus exploitation. A common formula for this is named UCT, and it weighs both sides against each other.

At the end of this path, a new node is attached. From there the simulation starts: the game is played out to the end, in the past purely at random, today usually guided by a trained model. The result is then reported back to all nodes along the path, which update their statistics accordingly. In this way, the tree becomes denser exactly where things are exciting, and stays sparse in unimportant areas.

From AlphaGo to today’s language models

The method became well known through AlphaGo, which defeated the world-class player Lee Sedol in 2016. AlphaGo combined tree search with neural networks, that is, learning programs that recognize patterns from examples. One network suggested promising moves, a second evaluated positions. Its successor, AlphaZero, learned chess and Go entirely without human games, solely through games against itself.

The principle also appears outside of board games. It is found in programs that plan timetables or delivery routes, and in systems that propose chemical synthesis steps. The prerequisite is always that one can simulate decisions and evaluate the outcome.

In the news you currently encounter the term often in connection with language models. When a chatbot plays through several solution paths before answering and selects the best one, that is a related idea. A common misconception, by the way, is to mistake tree search for a learning method. It does not learn anything permanently, but rather computes anew for the current situation; only the combination with learning networks makes it so powerful.