Monte-Carlo-Baumsuche

Die Monte-Carlo-Baumsuche, abgekürzt MCTS, versucht nicht, jede Variante bis zur gleichen Tiefe zu untersuchen. Sie lässt einen Baum schrittweise wachsen und nutzt die gesammelten Ergebnisse, um zu entscheiden, wohin der nächste Teil der Rechenleistung fließen soll. Ein häufig besuchter Zug ist nicht automatisch gut, doch seine Schätzung wird gewöhnlich durch mehr Suche gestützt.

Ein MCTS-Zyklus

1. Selektion: Die Suche beginnt an der Ausgangsstellung und folgt vorhandenen Zweigen. Dabei wägt sie Züge, die bereits stark erscheinen, gegen noch unsichere Züge ab.
2. Expansion: Eine Stellung oder ein Zug, den der Baum noch nicht entwickelt hat, wird hinzugefügt.
3. Bewertung: Das Ergebnis aus der neuen Stellung wird geschätzt. Klassische Verfahren können simulierte Partien zu Ende spielen, während moderne Systeme ein neuronales Netz verwenden können, also ein trainiertes Modell zur Mustererkennung, das die Stellung bewertet.
4. Rückpropagation: Das Ergebnis wird entlang des besuchten Pfads zurückgeführt, und dessen Besuchszahlen sowie Schätzwerte werden aktualisiert.

Die Wiederholung dieses Zyklus gleicht Ausnutzung und Erkundung aus. Ausnutzung bedeutet, mehr Aufwand dort einzusetzen, wo die bisherigen Hinweise günstig sind. Erkundung bedeutet, unsichere Alternativen zu prüfen, damit eine Überraschung nicht zu früh verworfen wird. Die genaue Regel für diesen Ausgleich hängt von der Implementierung ab.

Anders als Minimax entscheidet MCTS häufig anhand der während der Suche gesammelten Hinweise, wie intensiv ein Zweig untersucht wird, und nicht allein nach einer einheitlichen Tiefe. In manchen auf neuronalen Netzen beruhenden Schachprogrammen liefert ein Netz eine Policy, die wahrscheinliche Züge vorschlägt, und einen Value, der das Ergebnis schätzt. Der Value erfüllt eine mit einer Bewertungsfunktion verwandte Aufgabe, obwohl der gesamte Suchprozess anders aufgebaut ist.