Monte Carlo Tree Search (MCTS)
Monte-Carlo-Baumsuche (MCTS) wählt Aktionen aus, indem sie einen Suchbaum anhand simulierter Spielverläufe erweitert und vielversprechende Züge bevorzugt. Sie kommt in AlphaGo und Robotern zum Einsatz.
Die Monte-Carlo-Baumsuche (MCTS) ist ein Planungsalgorithmus, der die nächste Aktion auswählt, indem er ausgehend von zahlreichen simulierten Spielverläufen einen Baum möglicher Zukünfte aufbaut. Dabei verwendet er einen größeren Teil seines Budgets auf die vielversprechendsten Züge. Der Algorithmus benötigt lediglich eine Möglichkeit, zulässige Züge und Ergebnisse zu erzeugen, etwa die Regeln eines Spiels oder einen Simulator, aber keine von Hand geschriebene Bewertungsfunktion. Er kann außerdem jederzeit beendet werden: Dann gibt er den bis dahin besten gefundenen Zug zurück, und mehr Zeit liefert ein besseres Ergebnis. Rémi Coulom prägte den Namen des Verfahrens 2006, im selben Jahr, in dem Levente Kocsis und Csaba Szepesvári UCT veröffentlichten, die Auswahlregel, die zur Standardform des Verfahrens wurde. MCTS veränderte innerhalb weniger Jahre das Computergospiel, trieb später AlphaGo und AlphaZero an und wird heute zur Planung des Verhaltens von Robotern und Fahrzeugen sowie zur Suche nach Denkschritten in großen Sprachmodellen (LLMs) eingesetzt.
So funktioniert MCTS#
Die Suche verwaltet einen Baum, dessen Wurzel die aktuelle Position ist. Seine Knoten speichern, wie oft sie besucht wurden und wie oft diese Besuche zu einem Sieg führten. Jede Iteration umfasst vier Phasen:
- Auswahl: Ausgehend von der Wurzel geht die Suche durch vollständig untersuchte Knoten abwärts und wählt jeweils das Kind mit dem höchsten UCT-Wert. Dieser bringt hohe Siegquoten und selten ausprobierte Züge in ein ausgewogenes Verhältnis.
- Erweiterung: Beim ersten Knoten mit einem noch nicht ausprobierten Zug wird dieser als neues Kind hinzugefügt.
- Simulation: Vom neuen Kind aus wird das Spiel bis zum Ende durchgespielt, klassischerweise mit zufälligen Zügen, um ein Ergebnis zu erhalten.
- Rückpropagation: Die Suche geht den Pfad zurück nach oben und aktualisiert anhand des Ergebnisses die Besuchszahl und die Gesamtzahl der Siege jedes Knotens.
Wenn das Budget aufgebraucht ist, spielt der Algorithmus den am häufigsten besuchten Kindknoten der Wurzel aus. Das ist eine stabilere Wahl als der Zug mit dem höchsten Durchschnittswert.
Erkundung und Nutzung gegeneinander abwägen#
UCT behandelt die Auswahl an jedem Knoten als Multi-Armed-Bandit-Problem und verwendet die UCB1-Formel: Der Wert eines Kindknotens ist seine Siegquote w/n plus c·√(ln N / n), wobei n die Besuchszahl des Kindknotens, N die seines Elternknotens und c eine Erkundungskonstante ist. In der Theorie gilt √2; in der Praxis wird der Wert abgestimmt. Der zweite Term nimmt ab, je öfter ein Zug ausprobiert wird. Dadurch kann ein Zug mit einigen glücklichen Siegen die übrigen Züge nicht verdrängen, und ein vernachlässigter Zug wird irgendwann erneut geprüft.
Dieses Python-Beispiel führt MCTS für ein kleines Spiel aus: Die Spielenden nehmen jeweils ein bis drei Steine von einem Haufen mit 10 Steinen. Wer den letzten Stein nimmt, gewinnt.
import math
import random
# Game: players take 1-3 stones in turn, and whoever takes the last stone wins
random.seed(0)
N, W = {(10,): 0}, {} # visits and wins per node; a node is the sequence of pile sizes from the root
def rollout(stones):
"""Play random moves to the end and return 1 if the player to move wins."""
turn = 0
while stones:
stones -= random.randint(1, min(3, stones))
turn ^= 1
return turn
def search(node):
"""Run one MCTS iteration below a node and return 1 if the player to move there wins."""
if node[-1] == 0:
return 0 # the opponent took the last stone
children = [(*node, node[-1] - k) for k in (1, 2, 3) if k <= node[-1]]
unvisited = [c for c in children if c not in N]
if unvisited: # expansion, then simulation
child = random.choice(unvisited)
N[child], W[child] = 0, 0
result = 1 - rollout(child[-1])
else: # selection by UCT, balancing win rate against how rarely a child was tried
child = max(children, key=lambda c: W[c] / N[c] + 1.4 * math.sqrt(math.log(N[node]) / N[c]))
result = 1 - search(child)
N[child] += 1 # backpropagation, with wins counted for the player who moved into the child
W[child] += result
return result
for _ in range(2000):
search((10,))
N[(10,)] += 1
for take in (1, 2, 3):
child = (10, 10 - take)
print(f"Take {take}: {N[child]} visits, win rate {W[child] / N[child]:.2f}")Das Nehmen von zwei Steinen erhält 1.889 der 2.000 Besuche und gewinnt 91 % der Simulationen. Zum Vergleich: Für das Nehmen eines Steins gibt es 68 Besuche, für das Nehmen von drei Steinen 43. Das ist der Gewinnzug: Wenn 8 Steine übrig bleiben, also ein Vielfaches von 4, kann die erste Person auf jeden Gegenzug mit einem Zug antworten, der den Haufen wieder auf ein Vielfaches von 4 bringt, bis er leer ist. Die Suche fand den Zug allein anhand zufälliger Spielverläufe und Besuchsstatistiken, ohne dass eine Strategie einprogrammiert wurde.
Von AlphaGo über AlphaZero bis MuZero#
Der durchschnittliche Verzweigungsfaktor von Go liegt bei etwa 250 zulässigen Zügen, verglichen mit rund 35 beim Schach. Damit war eine vollständige Suche ausgeschlossen, und MCTS trieb ab Ende der 2000er-Jahre den Leistungssprung des Computergos voran. DeepMinds AlphaGo lenkte MCTS mit einem Richtliniennetz, das wahrscheinliche Züge vorschlug und Positionen sowohl mit einem Wertnetz als auch mit schnellen Spielverläufen bewertete. Im März 2016 besiegte es Lee Sedol mit 4:1. AlphaZero und MuZero gingen noch weiter. AlphaZero verzichtete vollständig auf Spielverläufe, bewertete Blattpositionen mit einem Wertnetz und trainierte dieses Netz mit Partien gegen sich selbst. Dabei dienten die Besuchszahlen jeder Suche als Zielwerte für das Richtliniennetz, wodurch MCTS innerhalb des bestärkenden Lernens zu einem Schritt der Richtlinienverbesserung wird. MuZero führte dieselbe Suche in einem gelernten Umgebungsmodell aus und konnte so Go, Schach, Shogi und Atari-Spiele spielen, ohne deren Regeln zu kennen.
MCTS für Planung und Schlussfolgerungen#
Roboter und autonome Fahrzeuge nutzen MCTS, um sich in unsicheren Situationen wie dem Einfädeln in den Verkehr zurechtzufinden. Varianten wie POMCP erweitern das Verfahren auf teilweise beobachtbare Markow-Entscheidungsprozesse, indem sie eine Wahrscheinlichkeitsverteilung über verborgene Zustände verfolgen. Eine Suche, die auf Grundlage von Kamerabildern plant, benötigt einen Zustand als Wurzel. Ein Schach spielender Roboterarm kann zum Beispiel ein Ultralytics-YOLO26-Modell nutzen, das mit Bildern des Schachbretts trainiert wurde, um alle Figuren zu lokalisieren. Die ermittelte Position bildet dann die Wurzel der Suche.
Beim Schlussfolgern mit LLMs steht jeder Knoten für eine Teillösung und jede Kante für einen Schlussfolgerungsschritt. Ein Prozess-Belohnungsmodell oder eine Prüfung der Antwort bewertet die Verzweigungen. Microsofts rStar-Math nutzte MCTS mit einem Prozesspräferenzmodell, um Qwen2.5-Math-7B im MATH-Benchmark von 58,8 % auf 90,0 % zu steigern. Tree of Thoughts durchsucht Schlussfolgerungsschritte stattdessen mit einer Breitensuche oder Tiefensuche. MCTS ließ sich während des Trainings schwerer einsetzen: DeepSeek führte es als einen der erfolglosen Versuche für DeepSeek-R1 auf, da der Suchraum für Tokenfolgen viel größer als bei einem Brettspiel ist und sich das wertbestimmende Modell, das die Suche leitet, nur schwer trainieren lässt. Stattdessen trainierte DeepSeek R1 mit bestärkendem Lernen anhand überprüfbarer Belohnungen.










