Monte-Carlo-Baumsuche (MCTS) ist ein heuristischer Baumsuchalgorithmus, der in Entscheidungsprozessen eingesetzt wird, insbesondere in Software, die Brettspiele spielt. Er löst den Spielbaum, indem er sich auf die vielversprechendsten Züge konzentriert und den Suchbaum basierend auf einer Zufallsstichprobe des Suchraums erweitert. MCTS wurde 2016 mit neuronalen Netzen kombiniert und wird seitdem bei Spielen wie Schach, Shogi, Damespiel, Backgammon, Bridge, Go, Scrabble und Clobber sowie bei rundenbasierten Strategiespielen und Nicht-Spiel-Anwendungen eingesetzt.
Der Algorithmus arbeitet durch wiederholte Playouts, auch Roll-outs genannt, bei denen das Spiel mit zufälligen Zügen bis zum Ende gespielt wird. Die Ergebnisse dieser Playouts werden verwendet, um Knoten im Spielbaum zu gewichten, wodurch bessere Knoten bei zukünftigen Playouts mit höherer Wahrscheinlichkeit ausgewählt werden. Dieser Ansatz unterscheidet sich von der traditionellen Minimax-Suche, indem er eine statische Bewertungsfunktion vermeidet und stattdessen auf simulierte Ergebnisse setzt.
Geschichte
Die Monte-Carlo-Methode, die Zufallsstichproben für deterministische Probleme verwendet, geht auf die 1940er Jahre zurück. 1987 kombinierte Bruce Abramson die Minimax-Suche mit einem erwarteten Ergebnismodell, das auf zufälligen Spielplayouts basiert, und demonstrierte dessen Genauigkeit und Domänenunabhängigkeit bei Tic-Tac-Toe, Othello und Schach. 1989 wandten W. Ertel, J. Schumann und C. Suttner ähnliche Methoden auf das automatisierte Beweisen von Theoremen an und verbesserten damit uninformierte Suchalgorithmen. 1992 verwendete B. Brügmann den Ansatz erstmals in einem Go-Programm. 2002 schlugen Chang et al. Adaptive Multi-stage Sampling (AMS) vor, das UCB-basierte Exploration und Exploitation in Monte-Carlo-Bäumen einführte und damit die Grundlage für UCT legte.
Im Jahr 2006 prägte Rémi Coulom den Namen Monte-Carlo-Baumsuche, während L. Kocsis und Cs. Szepesvári den UCT-Algorithmus (Upper Confidence bounds applied to Trees) entwickelten. S. Gelly et al. implementierten UCT im Programm MoGo, das bis 2008 das Dan-Niveau im 9×9-Go erreichte. Das Fuego-Programm begann ebenfalls um diese Zeit, starke Amateure im 9×9-Go zu schlagen. Im Januar 2012 gewann das Zen-Programm 3:1 gegen einen Amateur mit 2. Dan auf einem 19×19-Brett.
Google DeepMind entwickelte AlphaGo, das im Oktober 2015 als erstes Programm einen professionellen menschlichen Go-Spieler ohne Vorgaben auf einem vollständigen Brett besiegte. Im März 2016 besiegte AlphaGo Lee Sedol mit 4:1 und erhielt einen Ehren-9. Dan. AlphaGo kombinierte MCTS mit künstlichen neuronalen Netzen, einer Methode des Deep Learning, für die Politik- und Wertebewertung und markierte damit einen bedeutenden Meilenstein im maschinellen Lernen.
Funktionsprinzip
MCTS konzentriert sich auf die Analyse der vielversprechendsten Züge, indem es den Suchbaum basierend auf Zufallsstichproben erweitert. Jede Runde besteht aus vier Schritten:
- Auswahl: Beginnend vom Wurzelknoten (aktueller Spielzustand) werden nacheinander Kindknoten ausgewählt, bis ein Blattknoten erreicht ist. Die Auswahl ist darauf ausgerichtet, vielversprechende Züge zu bevorzugen, oft unter Verwendung von UCT.
- Erweiterung: Sofern der Blattknoten das Spiel nicht beendet, werden ein oder mehrere Kindknoten erstellt, die legale Züge darstellen.
- Simulation: Ein zufälliges Playout wird von einem ausgewählten Kindknoten aus durchgeführt, bis das Spiel entschieden ist.
- Rückpropagierung: Die Knoten auf dem Pfad vom Kind zum Wurzelknoten werden mit dem Playout-Ergebnis aktualisiert, wobei Simulationszähler und Gewinnzähler entsprechend erhöht werden.
Bei Spielen mit Unentschieden erhöht ein Unentschieden den Zähler für beide Spieler um 0,5 im Zähler und um 1 im Nenner. Dies stellt sicher, dass die Entscheidungen jedes Spielers sich in Richtung der Züge ausweiten, die ihren eigenen Wert maximieren.
UCT-Algorithmus
Der UCT-Algorithmus, eingeführt 2006, wendet Upper Confidence Bounds auf die Baumsuche an. Er balanciert Exploration und Exploitation, indem er Kindknoten basierend auf ihrer durchschnittlichen Belohnung und einem Bonus für weniger besuchte Knoten auswählt. Dies ermöglicht es dem Suchbaum, sich in Richtung der vielversprechendsten Züge auszuweiten, während Alternativen weiterhin erkundet werden. UCT wurde zum Standard für MCTS-Implementierungen, einschließlich in MoGo und späteren Programmen.
Anwendungen
MCTS wurde in Programmen für Brettspiele wie Hex, Havannah, Spiel der Amazonen und Arimaa sowie in Echtzeit-Videospielen wie Ms. Pac-Man und Fable Legends eingesetzt. Es behandelt auch nichtdeterministische Spiele wie Skat, Poker, Magic: The Gathering und Die Siedler von Catan. In rundenbasierten Strategiespielen verwendet Total War: Rome II MCTS in seiner KI für die Kampagnenführung auf hoher Ebene. Über Spiele hinaus findet MCTS Anwendungen in Planungs- und Optimierungsproblemen.
Die Kombination von MCTS mit neuronalen Netzen, wie in AlphaGo, hat sich als besonders effektiv erwiesen. Dieser hybride Ansatz verwendet neuronale Netze, um die Auswahl zu steuern und Positionen zu bewerten, wodurch der Bedarf an umfangreichen zufälligen Playouts reduziert wird. Nachfolgende Programme wie AlphaZero haben dies auf Schach und Shogi ausgeweitet und übermenschliche Leistungen erzielt.