Die Monte-Carlo-BaumSuche (MCTS) ist ein heuristischer Suchalgorithmus, der in der künstlichen Intelligenz eingesetzt wird, um komplexe Entscheidungsprozesse zu bewältigen. Der Name setzt sich aus zwei Komponenten zusammen: der Monte-Carlo-Methode, die zufällige Stichproben verwendet, um Ergebnisse zu schätzen, und der BaumSuche, die eine hierarchische Struktur von Möglichkeiten durchkämmt.
MCTS ist besonders nützlich in Situationen, in denen die Anzahl der möglichen Aktionen oder Zustände sehr groß ist, wie etwa bei Computerspielen oder Robotik. Der Algorithmus beginnt mit einer Wurzelknoten, die den aktuellen Zustand darstellt, und erstellt einen Baum, dessen Knoten mögliche Zustände abbilden. Jeder Knoten enthält statistische Informationen über die durchschnittliche Belohnung, die bei der Auswahl dieses Knotens erzielt wurde.
Das Verfahren kombiniert zwei Phasen: die Auswahl und die Ausweitung. In der Auswahlphase wird ein Pfad durch den Baum gewählt, der das beste Gleichgewicht zwischen Nutzen (exploitation) und Erkundung (exploration) bietet. Dies wird oft mit dem Upper Confidence Bound-Algorithmus (UCB) gesteuert. In der Ausweitungsphase wird der ausgewählte Knoten durch zufällige Simulationen weiter erforscht, um dessen potenzielle Belohnung zu schätzen.
MCTS ist in vielen Anwendungen wie Spielcomputern, Autonomer Robotik und Finanzsimulierungen erfolgreich eingesetzt. Es ist besonders effizient, weil es komplexe Zustandsräume mit begrenztem Rechenaufwand bewältigt und eine gute Balance zwischen Erkundung und Ausbeutung findet.