Monte-Carlo-Baumsuche (MCTS) ist ein heuristischer Baumsuchalgorithmus, der für Entscheidungsprozesse verwendet 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 zufälliger Stichprobenziehung des Suchraums erweitert. MCTS wurde 2016 mit neuronalen Netzen kombiniert und seitdem auf Spiele wie Schach, Shogi, Damespiel, Backgammon, Kontraktbridge, Go, Scrabble und Clobber sowie auf rundenbasierte Strategiespiele und andere Bereiche angewendet.
Der Algorithmus arbeitet durch wiederholte Playouts oder Roll-outs, bei denen Spiele mit zufälligen Zügen bis zum Ende simuliert werden. Die Ergebnisse dieser Playouts werden verwendet, um Knoten im Spielbaum zu gewichten und zukünftige Auswahlen zu vielversprechenderen Zügen zu lenken. Jede Runde von MCTS besteht aus vier Schritten: Selektion, Expansion, Simulation und Backpropagation.
Geschichte
Die Monte-Carlo-Methode, die zufällige Stichprobenziehung für deterministische Probleme verwendet, geht auf die 1940er-Jahre zurück. 1987 kombinierte Bruce Abramson die Minimax-Suche mit einem Erwartungswertmodell, das auf zufälligen Spielplayouts basiert, und demonstrierte ihre Wirksamkeit bei Tic-Tac-Toe und anderen Spielen. 1989 wandten W. Ertel, J. Schumann und C. Suttner ähnliche Methoden auf das automatisierte Beweisen von Theoremen an und verbesserten die Suchzeiten. 1992 verwendete B. Brügmann den Ansatz 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 die Grundlage für UCT legte.
2006 prägte Rémi Coulom den Begriff 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 Dan-Niveau im 9x9-Go erreichte. 2012 gewann das Programm Zen ein Match gegen einen Amateur-2-Dan-Spieler auf einem 19x19-Brett. Google DeepMinds AlphaGo, das MCTS mit neuronalen Netzen verwendete, war 2015 das erste Programm, das einen professionellen menschlichen Go-Spieler besiegte, und besiegte Lee Sedol 2016.
Funktionsprinzip
Der Fokus von MCTS liegt auf der Analyse der vielversprechendsten Züge, indem der Suchbaum basierend auf zufälliger Stichprobenziehung erweitert wird. Jedes Playout simuliert ein Spiel bis zum Ende, und die Ergebnisse gewichten Knoten, sodass bessere Züge häufiger ausgewählt werden. Die grundlegende Pure Monte Carlo Game Search wendet gleiche Playouts auf jeden legalen Zug an und wählt den Zug mit den meisten Siegen.
Jede Runde von MCTS umfasst vier Schritte:
- Selektion: Ausgehend von der Wurzel werden aufeinanderfolgende Kindknoten ausgewählt, bis ein Blattknoten erreicht ist.
- Expansion: Aus dem Blatt werden ein oder mehrere Kindknoten erstellt, sofern das Spiel nicht entschieden ist.
- Simulation: Ein zufälliges Playout wird vom neuen Knoten aus abgeschlossen.
- Backpropagation: Die Knotenstatistiken entlang des Pfads vom neuen Knoten zur Wurzel werden aktualisiert.
UCT-Algorithmus
Der UCT-Algorithmus balanciert Exploration und Exploitation mithilfe der Upper-Confidence-Bound-Formel. Er wählt Kindknoten basierend auf ihrer durchschnittlichen Gewinnrate und einem Bonus für weniger besuchte Knoten aus, wodurch sich der Baum zu vielversprechenden Zügen hin ausdehnt, während Alternativen weiterhin erkundet werden. Dieser Ansatz ist zentral für die Effizienz von MCTS.
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 verwendet. Es findet auch Anwendung auf nichtdeterministische Spiele wie Skat, Poker, Magic: The Gathering und Siedler von Catan. Über Spiele hinaus wurde MCTS in Planungs- und Optimierungsproblemen untersucht.
Bedeutung
Die Kombination von MCTS mit tiefen neuronalen Netzen, wie in AlphaGo, markierte einen Meilenstein in der künstlichen Intelligenz und im maschinellen Lernen. Sie zeigte, wie heuristische Suche mit Deep-Learning-Methoden integriert werden kann, um übermenschliche Leistungen in komplexen Bereichen zu erzielen, und beeinflusste nachfolgende Forschung in generativer KI und anderen Bereichen.