¶ Nested Monte Carlo Search
In seiner einfachsten Form (genannt Iterative Sampling) führt ein Monte Carlo Suchalgorithmus zufällige Spielzüge aus, bis entweder eine Lösung gefunden wurde, oder die Zeit abgelaufen ist[1].
Nested Monte Carlo Search (NMCS) erweitert dieses Prinzip durch Rekursion und das Speichern der besten gefundenen Sequenz. Dabei gibt level die Tiefe der Rekursion an. In der Regel findet ein höheres Level eine bessere Lösung als ein niedrigeres, vorausgesetzt die beste Sequenz wird gespeichert[1:1].
¶ Pseudocode
In Pseudocode sieht der Alrogithmus wie folgt aus:
NMCS(level,node):
if level==0: //base rollout policy
ply = 0, seq = {}
while num_children(node)>0:
choose seq[ply] = child i with probability 1/num_children(node)
node = child(node,seq[ply])
ply += 1
return (score(node(), seq)
else:
ply = 0, seq = {}
best_score = -infinity
while num_children(node)>0:
for children i of node:
temp = child(node,i)
(result,new) = NMCS(level-1, temp)
if result>best_score:
best_score = result
seq[ply] = i
seq[ply+1…] = new
node = child(node,seq[ply])
ply += 1
return (best_score, seq)
ply: Rekursionstiefe
seq: (beste) gefundene Sequenz
best_Score: beste gefundene Punktzahl
node: Spielzustand
NMCS Pseudocode wie in [2].
Gestartet wird eine Suche mit NMCS(level, root()), wobei root() den aktuellen Spielstand zurückgibt. Der einzig einstellbare Parameter ist level, doch hier gibt es wenige sinnvolle Werte, da die Laufzeit mit höheren Leveln stark ansteigt[2:1].
¶ Funktionsweise
Das Grundprinzip von NMCS funktioniert wie folgt: Von der Wurzel aus, also dem aktuellen Zustand und a in der nebenstehenden Abb. 1, wird so lange NMCS mit level-1 auf alle verfügbaren Kinder des Knotens aufgerufen, bis Level 0 erreicht ist. Auf Level 0 gleicht NMCS den Rollouts der Monte Carlo Tree Search (MCTS). Diese folgen einem einzigen Pfad im Suchbaum und wählen pro Knoten ein zufälliges Kind, bis sie einen Blattknoten erreichen. Die abgelaufene Sequenz wird gespeichert und an Level 1 zurückgegeben, welches widerum die beste gefundene Sequenz an Level 2 gibt. Das geht so weiter, bis das höchste Level alle rekursiv gefundenen Werte erhalten hat. Alle Level größer als Null merken sich unabhängig voneinander die beste ihnen bekannte Sequenz und Punktzahl[1:2].
Am Ende gibt die Funktion die ingesamt in allen Rollouts beste gefundene Punktzahl mit der entsprechenden Sequenz zurück und es kann der erste Zug der besten Sequenz ausgeführt werden.
Dass mit diesem Algorithmus die beste globale Punktzahl gefunden wird, ist nicht garantiert, wie in der nebenstehenden Abb. 1 zu sehen. Gefunden wird 12, 21 allerdings nicht. Das ist auf die zufällige Art der Rollouts zurückzuführen und darauf, dass nicht alle möglichen Wege abgesucht werden. Es gibt einen Kompromiss zwischen Laufzeit und dem Versuch, das globale Optimum zu finden.
In der Praxis sind Suchbäume normalerweise deutlich verzweigter und tiefer als in der nebenstehenden Abb. 1. Buzer & Cazenave fanden beispielsweise in der ersten Spielhälfte von Morpion Solitaire zwischen 10 und 28 Kinder pro Spielstand, im Endspiel immerhin noch 2 bis 9[3]. Im selben Spiel steigt die Suchtiefe bis zu 178[2:2]. Entsprechend ist es nicht möglich, in einer annehmbaren Laufzeit alle möglichen Pfade abzusuchen und es wird zu Alternativen wie NMCS gegriffen, die trotzdem für viele Probleme eine gute Lösung liefern.
¶ Überblick
NMCS kann angewendet werden, wenn für ein Problem keine gute Heuristik vorhanden ist und es eine sehr große Menge möglicher Zustände gibt[1:3]. Über einen Knoten und seine Kinder muss ausschließlich ihr Platz im Baum bekannt sein[2:3]. Um die Suche zu lenken, wird Rekursion verwendet und die beste gefundene Sequenz gespeichert, da mit zufälligen Rollouts nicht zwingend immer eine Verbesserung zu einer vorherigen Suche gefunden wird. Besonders gute Ergebnisse liefert es bei einer engen Verknüpfung der Punktzahl mit der Baumstruktur (Cazenave beschreibt dies an dem Left Most Path und dem Left Move Problem, auf die in dem referenzierten Paper genauer eingegangen wird)[1:4].
Mögliche domainspezifische Anpassungen können zum Beispiel sein, den Suchbaum mit Domänenwissen günstiger aufzubauen oder, wenn eine Heuristik vorliegt, diese bei dem Level 0 Rollout zu berücksichtigen[2:4].
¶ Bildquellen
Abb. 1: Animation und Beispiel selbst erstellt, Abbildung des Suchbaums von https://www.tutorialspoint.com/prolog/images/tree_data_structure.jpg
¶ Referenzen
Cazenave, T. (2009, July). Nested Monte-Carlo Search. Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI) (Vol. 9, pp. 456-461). | pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Rosin, C. D. (2011, July). Nested rollout policy adaptation for Monte Carlo tree search. Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI) (Vol. 2011, pp. 649-654). DOI ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Buzer, L., & Cazenave, T. (2021, August). Playout Optimization for Monte-Carlo Search Algorithms. Application to Morpion Solitaire. In 2021 Institute of Electrical and Electronics Engineers' (IEEE) Conference on Games (CoG) (pp. 01-08). IEEE. | pdf | DOI ↩︎