Die Monte-Carlo-Baumsuche (englisch Monte-Carlo Tree Search, MCTS) ist ein Suchverfahren für Entscheidungsprobleme wie Brettspiele: Statt alle Fortsetzungen zu prüfen, bewertet sie Züge anhand zufällig zu Ende gespielter Partien und vertieft die Suche dort, wo die Ergebnisse vielversprechend aussehen. Bekannt wurde sie durch AlphaGo.
Zusammenfassung
Bei Spielen wie Go ist die Zahl der Fortsetzungen so groß, dass eine vollständige Durchmusterung ausscheidet. Die Monte-Carlo-Baumsuche umgeht das Problem mit Stichproben: Eine Stellung wird bewertet, indem man den Ausgang mehrerer zufälliger Fortsetzungen mittelt (Coulom 2007).
Zwei Arbeiten aus dem Jahr 2006 beschreiben das Verfahren in seinen frühen Formen. Rémi Coulom verband Baumsuche und Zufallsbewertung zu einem gemeinsamen Rahmen, Levente Kocsis und Csaba Szepesvári nutzten mit dem Verfahren UCT Ideen der Banditenforschung, um die Stichproben zu lenken (Coulom 2007; Kocsis/Szepesvári 2006).
Die Grundidee
Eine Monte-Carlo-Bewertung schätzt eine Stellung, indem sie den Ausgang mehrerer zufälliger Fortsetzungen mittelt. Dieser Wert kann an den Blättern eines klassischen Minimax-Baums die Bewertungsfunktion ersetzen (Coulom 2007).
Coulom ging einen Schritt weiter. Er trennte nicht mehr zwischen einer Minimax-Phase nahe der Wurzel und einer Zufallsphase weiter unten. Stattdessen definierte er einen Rückgabeoperator, der mit wachsender Zahl der Simulationen schrittweise vom Mittelwert zum Minimax-Wert übergeht. Damit lässt sich das Wachstum des Baums bis auf die Ebene einzelner Simulationen steuern (Coulom 2007).
In Grundzügen arbeitet das Verfahren also in Wiederholungen: Eine Simulation läuft durch den bisherigen Baum, wird zufällig zu Ende gespielt, und ihr Ergebnis aktualisiert die Bewertung der Züge auf ihrem Weg. Je mehr Simulationen laufen, desto verlässlicher werden die Werte, und desto stärker konzentriert sich die Suche auf die besten Züge.
Entwicklung
Crazy Stone. Coulom setzte den Algorithmus in einem Go-Programm für das 9×9-Brett um, Crazy Stone, das das zehnte KGS-Turnier für Computer-Go gewann (Coulom 2007). Seine Arbeit erschien im Tagungsband der Konferenz Computers and Games.
UCT. Kocsis und Szepesvári stellten auf der Europäischen Konferenz über Maschinelles Lernen 2006 das Verfahren UCT vor, das Ideen aus der Banditenforschung nutzt, um die Zufallsplanung zu lenken. Sie zeigen, dass der Algorithmus konsistent ist, und leiten Schranken für den Schätzfehler bei endlich vielen Stichproben ab. In Experimenten war er in mehreren Anwendungsfeldern deutlich effizienter als die Alternativen (Kocsis/Szepesvári 2006).
Coulom selbst vermerkt auf der Seite zu seiner Arbeit, er habe den Algorithmus seither stark verbessert. Eine spätere Arbeit von ihm erkläre, wie sich die Spielstärke durch Musterwissen erheblich steigern lässt (Coulom o. J.).
Rolle in AlphaGo
In AlphaGo steht die Baumsuche nicht allein. Silver und Kollegen beschreiben 2016 in Nature ein neues Suchverfahren, das Monte-Carlo-Simulation mit Wertnetzen und Politiknetzen verbindet. Wertnetze bewerten Stellungen, Politiknetze wählen Züge (Silver u. a. 2016).
Bemerkenswert ist die Einordnung der Autor:innen: Schon die Netze allein, ohne jede Vorausschau, spielten auf dem Niveau damaliger Spitzenprogramme, die auf Monte-Carlo-Baumsuche beruhten und Tausende zufälliger Partien simulierten. Mit der kombinierten Suche gewann AlphaGo nach ihren Angaben 99,8 Prozent der Partien gegen andere Go-Programme und schlug den Europameister Fan Hui mit 5:0 (Silver u. a. 2016).
Die Nachfolger AlphaZero und MuZero führen die Verbindung von gelernter Bewertung und Baumsuche weiter. MuZero verzichtet dabei auf die Regeln des Spiels und plant mit einem selbst gelernten Modell.
Grenzen
Ein Simulator wird gebraucht. Das Verfahren bewertet Züge, indem es Fortsetzungen durchspielt. Es setzt daher voraus, dass sich Fortsetzungen erzeugen lassen, in Spielen also die Regeln oder ein Ersatzmodell dafür.
Rechenaufwand und Zufall. Die Werte sind Schätzungen aus Stichproben. Wie verlässlich sie sind, hängt davon ab, wie viele Simulationen laufen und wie gut die Spielzüge der Zufallsphase gewählt werden. Couloms Hinweis auf Verbesserungen durch Musterwissen deutet darauf hin, dass reine Zufallspartien nur eine Ausgangsstufe sind (Coulom o. J.).
Reichweite der Belege. Die hier ausgewerteten Arbeiten behandeln Brettspiele und Planungsprobleme mit Markow-Entscheidungsmodellen. Wie weit sich das Verfahren auf andere Felder übertragen lässt, belegen sie nicht.
Verwandte Begriffe
- AlphaZero – Nachfolger von AlphaGo, der ohne menschliche Partien lernt
- MuZero – plant mit einem gelernten Modell statt mit den Spielregeln
- Reinforcement Learning – Lernverfahren, mit dem die Netze verbessert wurden
- Deep Learning – Verfahren hinter den Bewertungs- und Zugnetzen
Quellenangaben
- Coulom, Rémi, o. J. Efficient Selectivity and Back-up Operators in Monte-Carlo Tree Search. Projektseite mit Zusammenfassung und Hinweisen. https://www.remi-coulom.fr/CG2006/
- Coulom, Rémi, 2007. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. In: Computers and Games (CG 2006), Lecture Notes in Computer Science 4630, Springer, S. 72–83. DOI: 10.1007/978-3-540-75538-8_7
- Kocsis, Levente / Szepesvári, Csaba, 2006. Bandit Based Monte-Carlo Planning. In: Machine Learning: ECML 2006, Lecture Notes in Computer Science 4212, Springer, S. 282–293. DOI: 10.1007/11871842_29
- Silver, David u. a., 2016. Mastering the Game of Go with Deep Neural Networks and Tree Search. In: Nature 529, S. 484–489. DOI: 10.1038/nature16961