¶ Einleitung
Monte Carlo Tree Search (MCTS) ist ein Suchalgorithmus zur Entscheidungsfindung, der auf einem inkrementell aufgebauten Suchbaum basiert.[1] Er dient dazu, den nächsten, möglichst optimalen Spielzug zu bestimmen. Erste Vorläufer von Monte Carlo basierten Suchverfahren wurden bereits in den 1940er Jahren entwickelt und eingesetzt [2]. Seitdem wurde der Ansatz kontinuierlich weiterentwickelt, sodass heute zahlreiche Varianten und Erweiterungen existieren.
¶ Grundidee
Monte Carlo Tree Search ist ein stochastischer Suchalgorithmus, da er Zufallssimulationen („Rollouts“) nutzt, um die Qualität möglicher Züge zu bewerten. Dadurch kommt MCTS ohne heuristische Bewertungsfunktionen aus und kann auch in komplexen oder schlecht verstandenen Spielsituationen eingesetzt werden.[3]
Jede Simulation durchläuft vier wiederkehrende Phasen: Selection, Expansion, Simulation und Backpropagation. Diese Phasen werden iterativ ausgeführt und verbessern schrittweise die Bewertung der im Baum enthaltenen Spielzüge.[1:1]
¶ Suchbaum
Der Suchbaum bildet die zentrale Datenstruktur hinter dem Monte Carlo Tree Search Algorithmus. Ein Suchbaum umfasst dabei alle bereits untersuchten Fortführungen eines Spiels.[4] Die Knoten repräsentieren dabei Spielzustände und die Kanten entsprechen möglichen Spielzügen. Die Blätter des Baumes sind entweder Endzustände eines Spiels oder noch nicht weiter verfolgte Zustände.
Jeder Knoten speichert dabei, zum einen die kumulierte oder durchschnittliche Bewertung des Zuges und zum anderen die Anzahl für diesen Knoten durchgeführter Simulationen.[5]
Aus diesen Informationen lässt sich bestimmen, welcher Zweig als Nächstes weiter untersucht werden sollte. Die Auswahl kann dabei nach unterschiedlichen Kriterien erfolgen. Die Auswahl erfolgt häufig über die UCT Formel (Upper Confidence Bounds applied to Trees), die eine Balance zwischen Exploration und Exploitation herstellt. [3:1]
Der Baum wird während der Suche schrittweise erweitert. Ausgehend vom Startzustand werden mögliche Folgezustände als neue Knoten hinzugefügt. Simulationen führen zu den Blättern des Baumes und liefern statistische Informationen über die Erfolgsaussichten eines Zuges. Vielversprechende Zweige werden häufiger besucht und dadurch stärker vertieft [6]. Die Tiefe des Baumes variiert somit dynamisch und hängt von der Relevanz der jeweiligen Spielverläufe ab.
¶ Die vier Phasen des MCTS
Die folgende Abbildung veranschaulicht den iterativen Ablauf des Monte Carlo Tree Search Algorithmus mit seinen vier charakteristischen Phasen:[7]
Selection (Selektion): Ausgehend vom Wurzelknoten wird der Baum traversiert, bis ein Knoten erreicht wird, der noch nicht vollständig expandiert wurde. Die Auswahl der Kindknoten erfolgt dabei nach der UCT-Formel, die vielversprechende Knoten (Exploitation) mit wenig besuchten Knoten (Exploration) abwägt. In der Abbildung ist dies durch den Pfad vom Wurzelknoten zu einem ausgewählten Blattknoten dargestellt.
Expansion (Erweiterung): Sobald ein Knoten erreicht wird, der noch unerforschte Kindknoten besitzt, wird einer dieser möglichen Züge ausgewählt und als neuer Knoten zum Baum hinzugefügt. Der neue Knoten repräsentiert einen bisher nicht untersuchten Spielzustand. In der Grafik wird dies durch das Hinzufügen eines neuen Knotens visualisiert.
Simulation (Rollout): Vom neu hinzugefügten Knoten aus wird ein zufälliges Spiel bis zum Ende simuliert. Dabei werden zufällige Züge für beide Spieler ausgeführt, bis ein Endzustand erreicht ist (Sieg, Niederlage oder Unentschieden). Diese Phase benötigt keine Erweiterung des Suchbaums, sondern dient ausschließlich der Bewertung des neuen Knotens.
Backpropagation (Rückführung): Das Ergebnis der Simulation wird entlang des Pfades vom simulierten Knoten zurück zur Wurzel propagiert. Dabei werden die Besuchszähler und Bewertungen aller Knoten auf diesem Pfad aktualisiert. Knoten, die zu gewonnenen Simulationen geführt haben, erhalten eine höhere Bewertung, was ihre zukünftige Auswahl wahrscheinlicher macht.
Diese vier Phasen werden iterativ wiederholt, bis ein vorgegebenes Zeitlimit oder eine maximale Anzahl an Iterationen erreicht ist. Mit jeder Iteration wird der Suchbaum präziser und die Bewertungen der Züge zuverlässiger.
¶ Upper Confidence Bounds applied to Trees (UCT)
UCT ist eine Formel die in der Selection Phase benutzt wird um eine Balance zwischen der Auswahl von aussichtsreichen und noch nicht betrachteten Knoten herzustellen. Der MCTS Algorithmus besitzt ohne UCT die Möglichkeit in einem lokalen Maximum festzustecken, während ein aussichtsreicherer Pfad nicht betrachtet wird.
:= Anzahl Siege des Knotens
:= Anzahl Simulationen des Knotens
:= Konstante zur Balance zwischen Exploration und Exploitation
:= Anzahl Simulationen des Elternknoten
¶ Merkmale
Der Monte Carlo Tree Search Algorithmus wird durch einige Eigenschaften ausgezeichnet, die ihn von anderen Algorithmen unterscheidet:
-
Effizienz in großen Zustandsräumen: Da nur ausgewählte Teile des Baumes untersucht werden, eignet sich MCTS besonders für Spiele mit vielen möglichen Zuständen.[3:2]
-
Keine feste Suchtiefe: Der Algorithmus kann Spielzüge bis zum Spielende simulieren und dadurch langfristige Auswirkungen berücksichtigen.[6:1] [1:2]
-
Robustheit bei unvollständigen Informationen: MCTS funktioniert auch dann gut, wenn Bewertungsfunktionen fehlen oder unzuverlässig sind.[6:2]
-
Anytime‑Eigenschaft: Der Algorithmus kann jederzeit abgebrochen werden. In diesem Fall liefert er die aktuell beste bekannte Entscheidung, was ihn ideal für Szenarien mit begrenzter Rechenzeit macht.[3:3]
-
Vielfältige Verwendung: Die Verwendung von MCTS ist nicht auf Spieler beschränkt, sondern kann auch auf weitere Probleme angewendet werden. [3:4]
¶ Anwendungsbereiche
MCTS wird vor allem zur Lösung von Brettspielen und in der KI von Computerspielen eingesetzt. Darüber hinaus findet der Algorithmus Anwendung in der allgemeinen Planung und Entscheidungsfindung sowie in verschiedenen Optimierungsproblemen.
¶ MCTS-RAVE
MCTS RAVE gehört zur Familie der Monte Carlo Tree Search Algorithmen und erweitert den klassischen MCTS Ansatz, der auf dem UCT Wert basiert. Ziel ist es, die Konvergenz der Aktionsbewertungen zu beschleunigen, insbesondere in Spielen mit großem Aktionsraum wie Go. Grundlage hierfür ist die „All Moves As First“ Heuristik (AMAF),[8] die erstmals im Kontext von Monte Carlo Go beschrieben wurde [9].
¶ Grundidee von RAVE
Die Grundidee hinter MCTS RAVE besteht darin, jede Aktion, die irgendwann im Rollout ausgeführt wurde, so zu behandeln, als wäre sie direkt nach dem aktuellen Knoten ausgeführt worden [1:3]. Dadurch tragen nicht nur die unmittelbar ausgeführten Aktionen, sondern auch spätere Aktionen im Rollout zur Bewertung eines Knotens bei. Das führt zu einer deutlich schnelleren Lernkurve, da viel mehr Datenpunkte pro Aktion gesammelt werden.
Jeder Knoten erhält dafür zusätzlich zum klassischen MCTS Wert einen zweiten Wert:
Dieser basiert auf allen Simulationen, in denen Aktion a irgendwann später im Rollout vorkam [9:1].
¶ Formel
Bei MCTS-RAVE wird die Formel des UCT-Werts, welcher die verschiedenen Aktionen bewertet durch den AMAF-Wert ergänzt. Die kombinierte Bewertungsfunktion lautet:[1:4]
= akkumulierte Belohnung der Aktion im klassischen MCTS
= akkumulierte Belohnung aus allen Simulationen, in denen Aktion irgendwann vorkam
= Anzahl der direkten Besuche der Aktion
= Anzahl dieser AMAF‑Simulationen
= Menge der Geschwisterknoten von (alle Knoten, die als Elternknoten teilen)
Der Gewichtungsparameter steuert die Balance zwischen klassischem UCT-Wert und AMAF-Wert. Dieser Wert kann folgendermaßen berechnet werden [1:5]:
Damit wird der Einfluss des AMAF-Werts mit zunehmender Anzahl klassischer Besuche automatisch abgeschwächt, um Verzerrungen zu vermeiden[1:6].
¶ Anwendungsbereiche
MCTS RAVE wird vor allem in frühen Suchphasen eingesetzt, in denen klassische MCTS Werte noch wenig aussagekräftig sind. Mit zunehmender Anzahl an Simulationen übernimmt der klassische UCT Wert, da dieser präziser ist [9:2].
RAVE ist besonders effektiv in Spielen mit großem Aktionsraum, wie etwa Go, wo frühe Schätzungen entscheidend sind [3:5].
¶ MCTS vs. MCTS-RAVE
| MCTS | MCTS RAVE |
|---|---|
| Nutzt nur Informationen über Aktionen, die direkt im Knoten ausgeführt wurden | Nutzt zusätzlich Informationen aus späteren Zügen im Rollout [10] |
| Keine Generalisierung zwischen verwandten Aktionen[9:3] | Kann Wissen zwischen Knoten austauschen (AMAF) |
| Benötigt viele Simulationen für stabile Werte | Kann gute Züge bereits nach wenigen Simulationen abschätzen [3:6] |
| Gut für späte Suchphasen | Besonders effektiv in frühen Suchphasen |
¶ Vorteile
- da mehr Daten erhoben werden, wird die Lernkurve beschleunigt und der Algorithmus liefert schneller, bessere ergebnisse[1:7]
- kann den besten Zug oft bereits nach wenigen Simulationen bestimmen [10:1]
- effizientere Nutzung von Rollout Informationen [9:4]
- Ermöglicht tiefere Suche bei gleicher Rechenzeit [9:5]
- Besonders nützlich bei Spielen mit großem Branching Faktor [9:6]
¶ Nachteile
- Ergebnisverzerrung: AMAF kann Werte verfälschen, wenn spätere Aktionen in anderem Kontext auftreten als frühere [1:8]
- Voreingenommene Schätzung: RAVE‑Werte sind weniger präzise als klassische MCTS‑Werte[9:7]
- Die RAVE-Erweiterung ist teilweise ungenau in späten Suchphasen, weshalb der Einfluss über reduziert wird [8:1]
- RAVE kann zu Fehlbewertungen führen, wenn Rollouts nicht repräsentativ sind [3:7]
¶ Referenzen
¶ Bildquellen
¶ Literaturverzeichnis
Ameneyro, Fred Valdez, Edgar Galván, and Ángel Fernando Kuri Morales. “Playing carcassonne with monte carlo tree search.” 2020 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 2020 pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Nikolaus, Metropole; Stanislaw, Ulam (1949). "Die Monte Carlo Methode". In: Journal of the American Statistical Association. 44 (247): 335– 341. pdf ↩︎
ŚWIECHOWSKI, Maciej, et al. Monte Carlo tree search: A review of recent modifications and applications. Artificial Intelligence Review, 2023, 56. Jg., Nr. 3, S. 2497-2562.
pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎https://www.wiwi.uni-siegen.de/technologiemanagement/forschung/agce_gomputer_poster.pdf (letzter Zugriff 05.01.2026 um 17:17 Uhr) ↩︎
BABENKOVA, Katherina; MARC, Zweitbetreuer Prof Dr. Varianten der Monte-Carlo Tree Search für das Brettspiel Gomoku unter Berücksichtigung der Sudden win/death Problematik [online]. 2023. pdf ↩︎
https://web.informatik.uni-mannheim.de/cmeilicke/grundlagen/KIX-06-MCTS.pdf ↩︎ ↩︎ ↩︎
Stack Overflow: Monte Carlo Tree Search Implementation for Tic-Tac-Toe. https://i.sstatic.net/EieiQ.png (letzter Zugriff 14.01.2026) ↩︎
BOZYEL, Kerem. Eine Untersuchung zu Monte-Carlo Tree Search mit Anwendung auf MAXSAT. pdf ↩︎ ↩︎
GELLY, Sylvain; SILVER, David. Monte-Carlo tree search and rapid action value estimation in computer Go. Artificial Intelligence, 2011, 175. Jg., Nr. 11, S. 1856-1875. pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
RIMMEL, Arpad; TEYTAUD, Fabien; TEYTAUD, Olivier. Biasing Monte-Carlo simulations through RAVE values. In: International Conference on Computers and Games. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. S. 59-68. pdf ↩︎ ↩︎