Monte-Carlo-Baumsuche

In Spielen wie Schach oder Go hat man in jeder Stellung viele erlaubte Züge. Nach jedem Zug antwortet der Gegner, dann folgt der nächste Zug, und die Zahl der möglichen Verläufe wächst ins Unvorstellbare. Alles bis zum Ende durchzurechnen ist deshalb aussichtslos. Die Monte-Carlo-Baumsuche geht anders vor: Sie probiert von jedem Zug aus einige Fortsetzungen aus, oft mit zufälligen Entscheidungen, und merkt sich, wie diese Partien ausgingen. Züge, die dabei häufig zum Sieg führten, werden anschließend genauer untersucht. Der Name kommt von Monte Carlo, dem berühmten Casino-Ort, weil das Verfahren bewusst mit Zufall arbeitet.

Warum Zufall besser rechnet als Vollständigkeit

Klassische Spielprogramme arbeiten mit einer Bewertungsfunktion. Das ist eine Formel, die einer Stellung eine Punktzahl gibt, etwa nach dem Materialwert der Figuren. In Schach funktioniert das gut, weil man ungefähr weiß, was eine starke Stellung ausmacht. Im Brettspiel Go versagt dieser Ansatz lange: Steine haben alle den gleichen Wert, und ob eine Position gut ist, hängt vom gesamten Muster ab.

Genau hier hilft die Baumsuche mit Zufallspartien. Sie braucht keine gute Formel für Zwischenstellungen. Sie braucht nur die Regeln des Spiels und das Ergebnis am Ende. Deshalb war sie der Durchbruch für Go-Programme, nachdem klassische Verfahren dort jahrzehntelang schwach blieben.

Ein zweiter Vorteil ist Fairness gegenüber der Rechenzeit. Man kann das Verfahren nach zehn Millisekunden abbrechen oder nach zehn Minuten. Es liefert immer eine Antwort, nur eine schlechtere oder bessere. Diese Eigenschaft nennt man Anytime-Verhalten und sie ist im Wettkampf wie in Produkten wertvoll.

Die vier Schritte pro Durchlauf

Das Verfahren baut nach und nach einen Suchbaum auf. Ein Suchbaum ist eine Struktur, in der jeder Knoten für eine Spielstellung steht und jede Verzweigung für einen möglichen Zug. Ein Durchlauf besteht aus vier Schritten: Auswahl, Erweiterung, Simulation und Rückmeldung. Diese vier Schritte werden tausend- oder millionenfach wiederholt.

Bei der Auswahl läuft das Programm vom Startknoten nach unten und wählt an jeder Verzweigung einen Zug. Dabei gilt eine Abwägung: Züge mit guter bisheriger Bilanz sind attraktiv, aber selten getestete Züge auch. Diese Abwägung heißt Exploration versus Exploitation, also Erkunden gegen Ausnutzen. Eine gängige Formel dafür trägt den Namen UCT und gewichtet beide Seiten gegeneinander.

Am Ende dieses Pfades wird ein neuer Knoten angehängt. Von dort startet die Simulation: Das Spiel wird bis zum Ende durchgespielt, früher rein zufällig, heute meist von einem trainierten Modell gesteuert. Das Ergebnis wird anschließend an alle Knoten des Pfades zurückgemeldet, die dadurch ihre Statistik aktualisieren. So verdichtet sich der Baum genau dort, wo es spannend ist, und bleibt in unwichtigen Bereichen dünn.

Von AlphaGo bis zu heutigen Sprachmodellen

Bekannt wurde das Verfahren durch AlphaGo, das 2016 den Weltklassespieler Lee Sedol besiegte. AlphaGo kombinierte die Baumsuche mit neuronalen Netzen, also lernenden Programmen, die aus Beispielen Muster erkennen. Ein Netz schlug aussichtsreiche Züge vor, ein zweites bewertete Stellungen. Der Nachfolger AlphaZero lernte Schach und Go ganz ohne menschliche Partien, allein durch Spiele gegen sich selbst.

Auch abseits von Brettspielen taucht das Prinzip auf. Es steckt in Programmen, die Fahrpläne oder Lieferrouten planen, und in Systemen, die chemische Syntheseschritte vorschlagen. Voraussetzung ist immer, dass man Entscheidungen simulieren und das Ergebnis bewerten kann.

In den Nachrichten begegnet dir der Begriff derzeit oft im Zusammenhang mit Sprachmodellen. Wenn ein Chatbot vor der Antwort mehrere Lösungswege durchspielt und den besten auswählt, ist das eine verwandte Idee. Ein häufiger Irrtum ist übrigens, die Baumsuche für ein Lernverfahren zu halten. Sie lernt nichts dauerhaft, sondern rechnet für die aktuelle Situation neu; erst die Kombination mit lernenden Netzen macht sie so stark.