Jak działa „wyszukiwanie Monte-Carlo”?

16

Słyszałem o tej koncepcji w poście Reddit o Alpha Go. Próbowałem przejrzeć artykuł i artykuł, ale nie mogłem zrozumieć algorytmu.

Czy ktoś może w łatwy sposób wyjaśnić, jak działa algorytm wyszukiwania Monte-Carlo i jak jest wykorzystywany w budowaniu botów AI?

gaming monte-carlo-tree-search Dawny33
źródło
Ładny opis algorytmu MCTS można znaleźć na stronie : https://towardsdatascience.com/monte-carlo-tree-search-in-reinforcement-learning-b97d3e743d0f .
nro

Odpowiedzi:

13

Metoda Monte Carlo to podejście polegające na generowaniu dużej liczby losowych wartości lub symulacji i tworzeniu pewnego rodzaju konkluzji w oparciu o ogólne wzorce, takie jak średnie i wariancje.

Jako przykład możesz użyć go do prognoz pogody . Prognozowanie pogody długoterminowej jest dość trudne, ponieważ jest to chaotyczny system, w którym niewielkie zmiany mogą prowadzić do bardzo różnych rezultatów. Stosując metody Monte Carlo, możesz przeprowadzić dużą liczbę symulacji, każda z nieco innymi zmianami atmosferycznymi. Następnie możesz przeanalizować wyniki i na przykład obliczyć prawdopodobieństwo deszczu w danym dniu na podstawie liczby symulacji, które zakończyły się deszczem.

Jeśli chodzi o użycie Monte Carlo w Alpha Go, wydaje się, że korzystają one z tak zwanego wyszukiwania drzewa Monte Carlo . W tym podejściu wykonujesz drzewo możliwych ruchów, kilka zwrotów w przyszłość i próbujesz znaleźć najlepszą sekwencję. Ponieważ jednak liczba możliwych ruchów w grze go jest bardzo duża, nie będziesz mógł eksplorować bardzo daleko. Oznacza to, że niektóre ruchy, które wyglądają teraz dobrze, mogą później okazać się złe.

Tak więc podczas wyszukiwania drzewa w Monte Carlo wybierasz obiecującą sekwencję ruchów i uruchamiasz jedną lub więcej symulacji tego, jak gra może przebiegać od tego momentu. Następnie możesz skorzystać z wyników tej symulacji, aby uzyskać lepszy obraz tego, jak dobra jest konkretna sekwencja ruchów, i odpowiednio zaktualizować drzewo. Powtarzaj w razie potrzeby, aż znajdziesz dobry ruch.

Jeśli chcesz uzyskać więcej informacji lub spojrzeć na kilka ilustracji, znalazłem interesujący artykuł na ten temat: C. Browne i in., A Survey of Monte Carlo Tree Search Methods ( open repository / permanent link (paywalled) )

Odczarowany Lurker
źródło
Więc w zasadzie to, co Monte Carlo robi w alphago, to tworzyć strategie długoterminowe, biorąc pod uwagę różne kombinacje ruchów, zamiast na odwrót (wybierz strategię, a następnie ruchy, aby ją osiągnąć)?
Diego Antonio Rosario Palomino
Nie ma wzmianki o kluczowym elemencie podejścia Monte Carlo, który jest elementem stochastycznym zintegrowanym z wyborem dostępnych ruchów do zbadania. Nie wspomniano również o kompromisie dokładności w celu uzyskania bardziej uproszczonego przetwarzania. Są to najważniejsze dwa aspekty i nie ma ich w odpowiedzi. Zamiast tego wspomniano o „dużej liczbie losowych wartości lub symulacji”, gdy jest to mniejsza liczba symulacji z czynników pseudolosowych (mniej wyczerpujące poszukiwanie), która jest charakterystyczna dla konwergencji Monte Carlo.
FauChristian