YOLO lizenzieren
Zurück zum Ultralytics-Glossar

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:

  1. 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.
  2. Erweiterung: Beim ersten Knoten mit einem noch nicht ausprobierten Zug wird dieser als neues Kind hinzugefügt.
  3. Simulation: Vom neuen Kind aus wird das Spiel bis zum Ende durchgespielt, klassischerweise mit zufälligen Zügen, um ein Ergebnis zu erhalten.
  4. 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.

Lösungen entdecken

Computer Vision im Sport

Computer Vision im Sport

Entdecke, wie Ultralytics YOLO die Sportbildanalyse voranbringt – mit Spieler- und Ballverfolgung, Leistungsanalysen, Erkenntnissen für das Coaching und der Rehabilitation von Athleten.
Mehr erfahren
Computer Vision für Luftbilder

Computer Vision für Luftbilder

Verwandle Drohnen- und Luftbilder mit Ultralytics YOLO in Echtzeit-Erkenntnisse für Landwirtschaft, Aquakultur, Naturschutz und Geodatenanalyse.
Mehr erfahren
Computer Vision in der Luft- und Raumfahrt

Computer Vision in der Luft- und Raumfahrt

Setze Computer Vision in der Luft- und Raumfahrt mit Ultralytics YOLO ein – für Flugzeuginspektionen, die Erkennung von Fremdkörpern auf Start- und Landebahnen, den Bodenbetrieb am Flughafen und die Erkennung von Verbundwerkstofffehlern.
Mehr erfahren
Computer Vision im Sicherheitsbereich

Computer Vision im Sicherheitsbereich

Schütze jeden Standort mit Ultralytics YOLO-Modellen. Vision-KI ermöglicht die Überwachung von Grundstücksgrenzen, die Erkennung von Bedrohungen, die Kennzeichenerkennung und die Sicherheit am Arbeitsplatz.
Mehr erfahren
Computer Vision in der Robotik

Computer Vision in der Robotik

Mach Maschinen mit Ultralytics YOLO-Modellen leistungsfähiger. Vision-KI in der Robotik ermöglicht autonome Navigation, Wahrnehmung, Objektverfolgung und Steuerung in Echtzeit.
Mehr erfahren
Bildverarbeitung in der Logistik

Bildverarbeitung in der Logistik

Optimiere die Logistik mit Ultralytics YOLO-Modellen. Vision AI ermöglicht die Paketprüfung, Sortierung und Fahrzeugverfolgung sowie die Sicherheitsüberwachung von Lagerhäusern in Echtzeit.
Mehr erfahren
Bildverarbeitung im Einzelhandel

Bildverarbeitung im Einzelhandel

Gestalte den Einzelhandel mit Ultralytics YOLO-Modellen neu. Vision AI ermöglicht Bestandsverfolgung, Regalüberwachung und Warteschlangenmanagement und liefert bessere Einblicke in das Kundenverhalten.
Mehr erfahren
Bildverarbeitung im Gesundheitswesen

Bildverarbeitung im Gesundheitswesen

Entwickle Lösungen für das Gesundheitswesen mit Ultralytics YOLO-Modellen. Vision AI ermöglicht im Gesundheitswesen schnellere medizinische Bildgebung, bessere Diagnostik und die Überwachung von Patienten.
Mehr erfahren
Computer Vision in der Fertigung

Computer Vision in der Fertigung

Optimiere die Fertigung mit Ultralytics-YOLO-Modellen. Vision AI ermöglicht Qualitätskontrolle, Fehlererkennung, die Überprüfung der Einhaltung von Vorgaben zu persönlicher Schutzausrüstung und die Automatisierung von Montagelinien.
Mehr erfahren
Computer Vision in der Automobilbranche

Computer Vision in der Automobilbranche

Setze Computer Vision in der Automobilbranche mit Ultralytics-YOLO-Modellen ein. Vision AI verbessert die Verkehrssicherheit, Fahrerassistenz und Fahrzeugautomatisierung – für intelligentere Straßen.
Mehr erfahren
Computer Vision in der Landwirtschaft

Computer Vision in der Landwirtschaft

Setze mit Ultralytics YOLO-Modellen KI für Bildverarbeitung in der intelligenten Landwirtschaft ein. Ermögliche die Überwachung von Nutzpflanzen, die Verfolgung von Nutztieren und Präzisionslandwirtschaft für höhere und nachhaltigere Erträge.
Mehr erfahren

Lass uns gemeinsam die Zukunft der KI gestalten!

Starte deine Reise in die Zukunft des maschinellen Lernens