Wie funktioniert die Monte-Carlo-Suche?

15

Ich habe in einem Reddit-Post über Alpha Go von diesem Konzept gehört. Ich habe versucht, die Zeitung und den Artikel durchzugehen, konnte aber den Algorithmus nicht wirklich verstehen.

Kann jemand eine leicht verständliche Erklärung geben, wie der Monte-Carlo-Suchalgorithmus funktioniert und wie er zum Erstellen von KI-Bots zum Spielen verwendet wird?

gaming monte-carlo-tree-search Dawny33
quelle
Eine ausführliche Beschreibung des MCTS-Algorithmus finden Sie unter: https://towardsdatascience.com/monte-carlo-tree-search-in-reinforcement-learning-b97d3e743d0f .
nbro

Antworten:

12

Die Monte-Carlo-Methode ist ein Ansatz, bei dem Sie eine große Anzahl von Zufallswerten oder Simulationen generieren und auf der Grundlage der allgemeinen Muster wie Mittelwerte und Varianzen Schlussfolgerungen ziehen.

Sie können es beispielsweise für Wettervorhersagen verwenden . Die Vorhersage von Langzeitwetter ist recht schwierig, da es sich um ein chaotisches System handelt, bei dem kleine Änderungen zu sehr unterschiedlichen Ergebnissen führen können. Mit Monte-Carlo-Methoden können Sie eine große Anzahl von Simulationen mit jeweils geringfügig unterschiedlichen atmosphärischen Veränderungen durchführen. Anschließend können Sie die Ergebnisse analysieren und beispielsweise die Regenwahrscheinlichkeit an einem bestimmten Tag berechnen, basierend auf der Anzahl der Simulationen, bei denen Regen aufgetreten ist.

Für die Verwendung von Monte Carlo in Alpha Go wird anscheinend die sogenannte Monte Carlo-Baumsuche verwendet . Bei diesem Ansatz erstellen Sie einen Baum möglicher Züge, einige Kurven in die Zukunft, und versuchen, die beste Sequenz zu finden. Da die Anzahl der möglichen Züge im Go-Spiel jedoch sehr groß ist, können Sie nicht weit vorausschauen. Dies bedeutet, dass einige der Bewegungen, die jetzt gut aussehen, sich später als schlecht herausstellen könnten.

In der Monte-Carlo-Baumsuche wählen Sie also eine vielversprechende Abfolge von Zügen aus und führen eine oder mehrere Simulationen aus, wie das Spiel von diesem Punkt aus weitergehen könnte. Dann können Sie die Ergebnisse dieser Simulation verwenden, um eine bessere Vorstellung davon zu bekommen, wie gut diese bestimmte Abfolge von Zügen wirklich ist, und Sie können den Baum entsprechend aktualisieren. Wiederholen Sie den Vorgang nach Bedarf, bis Sie einen guten Zug gefunden haben.

Wenn Sie weitere Informationen benötigen oder sich einige Abbildungen ansehen möchten, habe ich einen interessanten Artikel zum Thema gefunden: C. Browne et al., Eine Übersicht über Monte-Carlo- Baumsuchmethoden ( offenes Repository / permanenter Link (kostenpflichtig) )

Entzauberter Lurker
quelle
Was monte carlo in alphago also im Grunde tut, ist, langfristige Strategien zu entwickeln, indem verschiedene Zugkombinationen in Betracht gezogen werden und nicht umgekehrt (wählen Sie eine Strategie und dann die Züge, um sie zu erreichen)?
Diego Antonio Rosario Palomino
Das Schlüsselelement des Monte-Carlo-Ansatzes, das stochastische Element, das in die Auswahl der verfügbaren Moves zur Untersuchung einbezogen ist, wird nicht erwähnt. Auch der Kompromiss zwischen der Genauigkeit und der Erzielung einer schlankeren Verarbeitung wurde nicht erwähnt. Dies sind die beiden wichtigsten Aspekte und fehlen in der Antwort. Stattdessen wurde "eine große Anzahl von Zufallswerten oder Simulationen" erwähnt, wenn eine geringere Anzahl von Simulationen aus Pseudozufallsfaktoren (eine weniger erschöpfende Suche) für die Monte-Carlo-Konvergenz charakteristisch ist.
FauChristian