Die Monte-Carlo-Baumsuche bewertet Züge nicht mit einer von Hand gebauten Formel, sondern indem sie von einer Stellung aus viele Partien zufällig zu Ende spielt und die Ergebnisse mittelt. Sie ist das Verfahren hinter dem Go-Durchbruch.
Minimax mit Alpha-Beta-Pruning braucht eine Bewertungsfunktion für abgebrochene Stellungen. Bei Schach lässt sie sich formulieren — Material zählen, Königssicherheit bewerten. Bei Go gelang das jahrzehntelang nicht: Wer im Go führt, ist an der Stellung kaum abzulesen. Dazu kommt der Verzweigungsfaktor von rund 250 gegenüber etwa 35 beim Schach. Beide Gründe machten Go zum Prüfstein der Spiel-KI.
Statt die Stellung zu bewerten, spielt das Verfahren von ihr aus die Partie mehrfach mit zufälligen Zügen zu Ende und zählt, wie oft das gut ausgeht. Ein einzelner solcher Durchlauf (Playout oder Rollout) sagt wenig; über Tausende gemittelt ergibt sich ein brauchbares Maß. Der Name verweist auf das Spielkasino von Monte Carlo als Sinnbild für Zufallsverfahren.
Jeder Durchlauf besteht aus vier Phasen: Auswahl — vom Wurzelknoten aus wird der Baum entlang der bisher aussichtsreichsten Züge durchlaufen; Expansion — am Rand des Baums kommt ein neuer Knoten hinzu; Simulation — von dort wird zufällig ausgespielt; Rückführung — das Ergebnis wird entlang des begangenen Pfads nach oben verrechnet. So wächst der Baum ungleichmäßig: dort dicht, wo es interessant wird.
Bei der Auswahl stellt sich dieselbe Frage, die auch Bestärkendes Lernen beschäftigt: den bisher besten Zug weiter vertiefen oder einen wenig geprüften ausprobieren? Die übliche Antwort ist die obere Konfidenzgrenze (UCB): Jeder Zug erhält einen Bonus, der mit der Zahl seiner Besuche fällt. Selten geprüfte Züge werden dadurch von Zeit zu Zeit erneut betrachtet.
2016 schlug AlphaGo von DeepMind den Weltklassespieler Lee Sedol mit 4:1. Das Programm ersetzte die Zufallszüge und die reine Zählstatistik durch zwei tiefe Neuronales Netz: eines schlug Züge vor, ein zweites bewertete Stellungen. Der Nachfolger AlphaZero lernte 2017 ohne jedes menschliche Partiematerial allein durch Spiel gegen sich selbst. Die Verbindung aus Baumsuche und gelernter Bewertung gilt seither als Muster dafür, wie klassische Suchverfahren und Deep Learning zusammenwirken.
Das Verfahren verlangt kein Vorwissen über die Bedeutung einer Stellung, nur die Spielregeln und ein Ergebnis am Ende. Deshalb wird es auch außerhalb von Brettspielen eingesetzt — bei Planungsaufgaben, in der Verfahrenstechnik und überall dort, wo sich Abläufe simulieren, aber schwer bewerten lassen.
Hallo! Ich bin dein KI-Tutor.
Melde dich an, um mit mir zu chatten — ich erinnere mich dann auch an eure letzten Gespräche.
