¶ Allgemeines
Nested Monte Carlo Search (NMCS)[1] ist ein rekursiver Suchalgorithmus, der primär zur Lösung von Optimierungsproblemen und Einpersonenspielen (Puzzles) eingesetzt wird.
¶ Grundidee
Abb. 1 Überblick über die verschachtelte Suche bei NMCS
Die Grundidee von NMCS ist die Rekursion. Anstatt in einer Simulation nur völlig zufällige Züge zu machen, oder eine Heuristik zu nutzen die auf Domänenwissen basiert, nutzt NMCS eine Suche auf niedrigerer Ebene, um die Suche auf der aktuellen Ebene zu leiten.
Ein NMCS-Algorithmus wird durch ein Level definiert:
- Level 0: Entspricht einem rein zufälligen Rollout (Zufallszüge) bis zum Spielende.
- Level 1: Führt für jeden möglichen Zug im aktuellen Zustand eine Level-0-Suche aus und wählt den Zug, der das beste Endergebnis geliefert hat.
- Level : Führt für jeden möglichen Zug eine Level-()-Suche aus.
Durch diese Verschachtelung „lernt“ der Algorithmus bereits während eines einzelnen Durchgangs, welche Pfade vielversprechend sind, da jede Ebene die Ergebnisse der darunterliegenden Ebene zur Entscheidungsfindung nutzt.
¶ Suchprozess
Im Gegensatz zu Monte Carlo Tree Search baut NMCS keinen expliziten, persistenten Suchbaum im Speicher auf, der über viele Iterationen wächst. Stattdessen konzentriert sich NMCS darauf, die beste Sequenz von Zügen zu finden.
- Erkunden: Auf jedem Level der Suche werden alle möglichen Züge des aktuellen Zustands geprüft.
- Rekursion: Für jeden Zug wird eine vollständige Simulation auf dem nächsttieferen Level (n−1) gestartet.
- Merken: Wenn eine Simulation auf einem beliebigen Level ein Ergebnis liefert, das besser ist als das bisherige globale Besturteil, wird diese Zugfolge gespeichert.
- Entscheiden: Der Algorithmus wählt den Zug, der im Rahmen der verschachtelten Suche zum besten Endergebnis geführt hat, und rückt in den daraus resultierenden Zustand vor.
¶ Merkmale
Der NMCS-Algorithmus weist spezifische Merkmale auf, die ihn für bestimmte Problemstellungen ideal machen:
- Hervorragend für Einpersonenspiele: NMCS hat Weltrekorde in Spielen wie Morpion Solitaire oder SameGame aufgestellt, bei denen es darum geht, eine optimale Sequenz von Zügen zu finden.
- Keine Heuristik erforderlich: Wie MCTS benötigt NMCS nur die Spielregeln und eine Bewertungsfunktion für den Endzustand.
- Hohe Rechentiefe: Durch die Rekursion können sehr tiefe Pfade erkundet werden, die bei einer Breitensuche (wie teilweise in MCTS) erst spät erreicht würden.
- Exploitation-fokussiert: NMCS neigt dazu, vielversprechende Pfade sehr intensiv zu verfolgen, was bei Puzzles mit „engen“ Lösungswegen vorteilhaft ist.
- Skalierbarkeit: Die Anzahl an Simulationen steigt mit jedem Level Exponentiell. In der Praxis führt das dazu, dass Level höher als 4 kaum nutzbar sind.
¶ Anwendungsbereich
NMCS wird primär dort eingesetzt, wo eine optimale Pfadsuche in großen Zustandsräumen erforderlich ist. Dazu gehören kombinatorische Optimierungen wie beim Scheduling und Einpersonenspiele (Puzzles) wie Sudoku, Morpion Solitaire und Kakuro.
¶ Weiterentwicklung
Die wichtigste Weiterentwicklung von NMCS ist Nested Rollout Policy Adaption (NRPA)[2]. Während NMCS die Züge auf Level 0 rein zufällig wählt, lernt NRPA während der Suche eine Policy (eine Strategie), um die Rollouts zu steuern.
¶ Grundidee von NRPA
NRPA kombiniert die verschachtelte Suche von NMCS mit dem Lernen einer Aktionsbewertung. Auf jedem Level der Rekursion passt der Algorithmus eine Gewichtstabelle für Züge an. Wenn eine Sequenz von Zügen zu einem neuen Rekordergebnis führt, werden die Gewichte dieser Züge erhöht (Reinforcement Learning Prinzip).
Dadurch werden „gute“ Züge in zukünftigen Simulationen auf derselben Ebene mit höherer Wahrscheinlichkeit gewählt.