Monte-Carlo Tree Search

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Monte-Carlo Tree Search (w skrócie MCTS) – heurystyka podejmowania decyzji w pewnych zadaniach sztucznej inteligencji, używana zwłaszcza do wyboru ruchów w grach. Sztandarowy przykład jej zastosowania to współczesne programy komputerowe do gry w go[1]. Metodę MCTS stosuje się również w programach grających w inne gry planszowe (między innymi Hex[2], Havannah[3], Amazonki[4] i Arimaa[5]), w gry czasu rzeczywistego (na przykład Ms. Pac-Man[6]) oraz w gry niedeterministyczne (na przykład skata[7], pokera[8], Magic: The Gathering[9], czy Osadników z Catanu[10]). Metoda MCTS skupia się na analizie najbardziej obiecujących ruchów, opierając rozrost drzewa wariantów na losowym próbkowaniu przestrzeni przeszukiwań.

Zasada działania[edytuj | edytuj kod]

Podstawę metody MCTS w grach stanowią symulacje (ang. playouts), czyli szybkie rozgrywki złożone z losowych ruchów. Wynik symulacji to informacja o tym, który gracz został jej zwycięzcą.

Najprymitywniejszy sposób użycia symulacji to wykonanie, po każdym ruchu dopuszczalnym dla bieżącego gracza, tej samej liczby symulacji, a następnie wybór tego ruchu, po którym najwięcej symulacji zakończyło się wygraną tego gracza[11]. Wydajność tej metody rośnie, gdy z biegiem czasu przydziela się więcej symulacji tym ruchom, po których poprzednie symulacje częściej prowadziły do wygranej danego gracza. Pełna metoda MCTS polega na rekurencyjnym zastosowaniu tego pomysłu nie na jednym, lecz na wielu poziomach głębokości drzewa wariantów. Każda tura tej metody składa się z czterech kroków[12]:

  • Wybór (ang. selection): zaczynając od korzenia drzewa R, wybieraj kolejne węzły potomne, aż dotrzesz do liścia drzewa L. Poniżej więcej o takim sposobie wyboru węzłów potomnych, dzięki któremu drzewo wariantów rozrasta się w kierunku najbardziej obiecujących ruchów, co stanowi clou metody MCTS.
  • Rozrost (ang. expansion): o ile L nie kończy gry, utwórz w nim jeden lub więcej węzłów potomnych i wybierz z nich jeden węzeł C.
  • Symulacja (ang. playout): rozegraj losową symulację z węzła C.
  • Propagacja wstecz (ang. backpropagation): na podstawie wyniku rozegranej symulacji uaktualnij informacje w węzłach na ścieżce prowadzącej od C do R.

Przykładowe kroki jednej tury przedstawiono na poniższym rysunku. Każdy węzeł drzewa przechowuje informacje o liczbie wygranych/liczbie wykonanych symulacji.

Kroki metody Monte-Carlo Tree Search

Takie tury się powtarza, dopóki starczy czasu przydzielonego na wybór ruchu. Następnie wybiera się jeden z ruchów dopuszczalnych w korzeniu drzewa, ale nie ten o najwyższej średniej wygranej, tylko ten o największej liczbie wykonanych symulacji.

Eksploracja a eksploatacja[edytuj | edytuj kod]

Podstawowa trudność przy wyborze węzłów potomnych to zachowanie pewnej równowagi między eksploatacją głębokich wariantów po ruchach o wysokiej średniej wygranej a eksploracją mało sprawdzonych ruchów. Pierwszy wzór równoważący eksploatację i eksplorację w kontekście gier, zwany UCT (Upper Confidence Bound 1 applied to trees), wprowadzili L. Kocsis i Cs. Szepesvári[13], opierając się na wzorze UCB1, wyprowadzonym w pracy Auera, Cesa-Bianchiego i Fischera[14]. Kocsis i Szepesvári zalecają w każdym węźle drzewa wariantów wybór tego ruchu, dla którego wyrażenie \frac{w_i}{n_i} + c\sqrt{\frac{\ln t}{n_i}} osiąga największą wartość. W tym wzorze:

  • w_i oznacza liczbę wygranych po i-tym ruchu;
  • n_i oznacza liczbę symulacji po i-tym ruchu;
  • c to parametr eksploracji – teoretycznie równy \sqrt{2}, a w praktyce zwykle dobierany empirycznie;
  • t oznacza łączną liczbę symulacji w danym węźle drzewa, równą sumie wszystkich n_i.

Pierwszy składnik powyższego wzoru odpowiada za eksploatację; przyjmuje on wysokie wartości dla ruchów o wysokiej średniej wygranej. Drugi składnik odpowiada za eksplorację; przyjmuje on wysokie wartości dla ruchów, dla których wykonano niewiele symulacji.

Większość współczesnych implementacji metody MCTS opiera się na jakimś wariancie metody UCT.

Wady i zalety[edytuj | edytuj kod]

Dowiedziono wprawdzie, że w metodzie MCTS ocena ruchów jest zbieżna do oceny min-max[15], jednak jej podstawowej wersji uzyskanie zbieżności może zajmować astronomicznie długi czas. Oprócz tej wady, którą zresztą częściowo znoszą podane niżej usprawnienia, ma ona pewne zalety w porównaniu z algorytmem alfa-beta i podobnymi.

W odróżnieniu od nich, metoda MCTS działa bez jawnej funkcji oceny pozycji. Wystarczy zakodować samą mechanikę gry, czyli generowanie ruchów dopuszczalnych w danej pozycji i warunki zakończenia gry. Dzięki temu można stosować tę metodę do nowoczesnych gier, których teoria jeszcze się wystarczająco nie rozwinęła, lub zgoła w programach zdolnych do wielu gier.

W metodzie MCTS drzewo wariantów rośnie asymetrycznie: skupia się ona na przeszukiwaniu jego bardziej obiecujących części. Dzięki temu osiąga ona lepsze wyniki od klasycznych algorytmów w grach o wysokim współczynniku rozgałęzienia, czyli liczbie ruchów dopuszczalnych w danej pozycji.

Ponadto działanie metody MCTS można przerwać kiedykolwiek, otrzymując ruch uznawany w danej chwili za najbardziej obiecujący.

Usprawnienia[edytuj | edytuj kod]

Zaproponowano rozmaite modyfikacje metody MCTS, mające na celu szybsze znajdowanie właściwych ruchów. Można je podzielić na usprawnienia korzystające z wiedzy eksperckiej z danej dziedziny i na usprawnienia od niej niezależne.

W metodzie MCTS można stosować zarówno tak zwane lekkie, jak i ciężkie symulacje (ang. light playouts, heavy playouts). Lekkie symulacje składają się z zupełnie losowych ruchów. W ciężkich symulacjach na wybór ruchów wpływają rozmaite heurystyki. Heurystyki te mogą się opierać na wynikach poprzednich symulacji (np. heurystyka last good reply[16]) lub na wiedzy eksperckiej z danej gry. Na przykład w wielu programach grających w go ustalone wzorce (ang. patterns) położenia kamieni na części gobanu wpływają na prawdopodobieństwa ruchów w tej części[17]. Paradoksalnie jednak, nie zawsze silniejsza gra w symulacjach przekłada się na silniejszą grę programów korzystających z metody MCTS[18].

Wzorce sytuacji hane (otaczania kamieni przeciwnika), używane w symulacjach przez program MoGo. Zarówno czarnym, jak i białym opłaca się położenie kamienia w miejscu środkowego kwadratu, oprócz prawego wzorca, gdzie położenie kamienia w miejscu kwadratu opłaca się tylko czarnym. Na podstawie [17].

Z wiedzy eksperckiej można też korzystać przy budowie drzewa wariantów, by wspomóc eksploatację niektórych z nich. Jeden ze sposobów takiego wspomagania polega na przypisaniu liczbie wygranych i liczbie symulacji a priori niezerowych wartości (ang. priors) przy tworzeniu węzła drzewa. Sztucznie zawyżona (bądź zaniżona) średnia wygrana spowoduje częstszy (bądź rzadszy) wybór tego węzła[19]. Zbliżony sposób, zwany progressive bias, polega na dodaniu do wzoru UCB1 składnika \frac{b_i}{n_i}, gdzie b_i to heurystyczna ocena i-tego ruchu[20].

W zwykłej metodzie MCTS potrzeba wielu tur, by zebrać dane wystarczające do wyróżnienia najbardziej obiecujących ruchów. Zanim to nastąpi, wybierane są ruchy o dość losowej jakości. Tę początkową fazę można w grach pewnego typu znacznie skrócić, stosując metodę RAVE (Rapid Action Value Estimation)[19]. Chodzi tu o gry, w których permutacje danego ciągu ruchów prowadzą do tej samej pozycji, a zwłaszcza o gry planszowe, w których ruchy polegają na dołożeniu na planszę pionka czy kamienia. W takich grach często na wartość danego ruchu tylko nieznacznie wpływają ruchy wykonane gdzie indziej.

W metodzie RAVE dla danego węzła N w drzewie wariantów, jego węzły potomne C_i przechowują oprócz zwykłej statystyki zwycięstw w symulacjach także statystykę zwycięstw we wszystkich tych symulacjach rozpoczętych w węźle N i poniżej niego, w których wystąpił ruch i (także jeśli zagrano go w drzewie, pomiędzy węzłem N a symulacją). W ten sposób na zawartość węzłów drzewa oprócz ruchów zagranych w danej pozycji wpływają również te same ruchy zagrane później.

RAVE na przykładzie gry w kółko i krzyżyk. Na czerwono zaznaczono węzły drzewa, w których po symulacji b1-a2-b3 zostanie uaktualniona statystyka RAVE.

W metodzie RAVE w kroku wyboru węzła potomnego wybiera się ten węzeł, dla którego zmodyfikowany wzór UCB1 (1-\beta(n_i, \tilde{n}_i))\frac{w_i}{n_i} + \beta(n_i, \tilde{n}_i)\frac{\tilde{w}_i}{\tilde{n}_i} + c\sqrt{\frac{\ln t}{n_i}} przyjmuje największą wartość. We wzorze tym \tilde{w}_i i \tilde{n}_i oznaczają liczbę wygranych symulacji zawierających ruch i i liczbę wszystkich symulacji zawierających ruch i, a funkcja \beta(n_i, \tilde{n}_i) powinna przyjmować odpowiednio wartości bliskie jedności oraz zera dla n_i i \tilde{n}_i stosunkowo niewielkich oraz stosunkowo dużych. Jeden z wielu zaproponowanych wzorów na \beta(n_i, \tilde{n}_i), który pochodzi od D. Silvera[21] mówi, że w zrównoważonych pozycjach można przyjąć \beta(n_i, \tilde{n}_i)=\frac{\tilde{n}_i}{n_i+\tilde{n}_i+4b^2 n_i\tilde{n}_i}, gdzie b to empirycznie dobrana stała.

Heurystyki stosowane w metodzie MCTS często zależą od licznych parametrów. Opracowano metody automatycznego dopasowywania wartości tych parametrów pod kątem maksymalizacji częstości wygranych partii[22].

Metodę MCTS może jednocześnie wykonywać wiele wątków lub procesów. Istnieje kilka zasadniczo różnych sposobów jej współbieżnego wykonywania[23]:

  • Zrównoleglanie w liściach, czyli równoległe wykonywanie wielu symulacji z jednego liścia drzewa wariantów.
  • Zrównoleglanie w korzeniu, czyli równoległe budowanie niezależnych drzew wariantów, a po upłynięciu zadanego czasu wybór ruchu na podstawie gałęzi wychodzących z korzeni wszystkich tych drzew.
  • Zrównoleglanie w drzewie, czyli równoległe budowanie tego samego drzewa wariantów, z zabezpieczeniem danych przed równoczesnym zapisem przy użyciu bądź to jednej, globalnej blokady (ang. mutex), bądź to większej liczby blokad, bądź też synchronizacji nieblokującej[24].

Historia[edytuj | edytuj kod]

Metoda Monte Carlo, oparta na koncepcji losowego próbkowania, powstała w latach 1940. W roku 1992 B. Brügmann jako pierwszy zastosował ją w programie do gry w go[11], ale jego pomysłu nie potraktowano wówczas poważnie. W roku 2006, zwanym rokiem rewolucji Monte Carlo w go[25], R. Coulom opisał zastosowanie metody Monte Carlo do przeszukiwania drzew wariantów i wprowadził nazwę Monte-Carlo Tree Search[26], L. Kocsis i Cs. Szepesvári opracowali algorytm UCT[13], a S. Gelly i inni zastosowali UCT w swoim programie MoGo[17]. W roku 2008 program MoGo osiągnął poziom dan (mistrzowski) w go na planszy o rozmiarach 9×9[27], a program Fuego zaczął wygrywać w go na planszy o rozmiarach 9×9 z silnymi amatorami[28]. W styczniu 2012 program Zen wygrał stosunkiem punktów 3:1 mecz w go na planszy o normalnych rozmiarach 19×19 z Johnem Trompem, graczem poziomu 2 dan[29].

Ranking najlepszych programów do gry w go na serwerze KGS od 2007 roku. Od 2006 roku wszystkie najlepsze programy stosują metodę MCTS. Źródło danych:[30].

Przypisy

  1. MCTS.ai: Everything Monte Carlo Tree Search. [dostęp 2012-02-19].
  2. Broderick Arneson, Ryan Hayward, Philip Henderson. MoHex Wins Hex Tournament. „ICGA Journal”. 32 (2), s. 114–116, czerwiec 2009. 
  3. Timo Ewalds: Playing and Solving Havannah. Praca magisterska, University of Alberta, 2011.
  4. Richard J. Lorentz: Amazons Discover Monte-Carlo. W: Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (red.). Springer, 2008, s. 13–24. ISBN 978-3-540-87607-6.
  5. Tomáš Kozelek: Methods of MCTS and the game Arimaa. Praca magisterska, Uniwersytet Karola w Pradze, 2009.
  6. Xiaocong Gan, Yun Bao, Zhangang Han. Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man. „ICGA Journal”. 34 (4), s. 209–222, grudzień 2011. 
  7. Michael Buro, Jeffrey Richard Long, Timothy Furtak, Nathan R. Sturtevant: Improving State Evaluation, Inference, and Search in Trick-Based Card Games. W: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009. Craig Boutilier (red.). 2009, s. 1407–1413. DOI:10.1.1.150.3077.
  8. Jonathan Rubin, Ian Watson. Computer poker: A review. „Artificial Intelligence”. 175 (5–6), kwiecień 2011. doi:10.1016/j.artint.2010.12.005. 
  9. C.D. Ward, P.I. Cowling: Monte Carlo Search Applied to Card Selection in Magic: The Gathering. W: CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games. IEEE Press, 2009.
  10. István Szita, Guillaume Chaslot, Pieter Spronck: Monte-Carlo Tree Search in Settlers of Catan. W: Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers. H. Jaap van den Herik, Pieter Spronck (red.). Springer, 2010, s. 21–32. ISBN 978-3-642-12992-6.
  11. 11,0 11,1 Bernd Brügmann: Monte Carlo Go. Raport techniczny, wydział fizyki, Syracuse University, 1993.
  12. Guillaume Chaslot, Sander Bakkes, Istvan Szita, Pieter Spronck: Monte-Carlo Tree Search: A New Framework for Game AI. W: Proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference, October 22–24, 2008, Stanford, California, USA. Christian Darken, Michael Mateas (red.). The AAAI Press, 2008, s. 216–217. ISBN 978-1-57735-391-1.
  13. 13,0 13,1 Levente Kocsis, Csaba Szepesvári: Bandit based Monte-Carlo Planning. W: Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006, Proceedings. Lecture Notes in Computer Science 4212. Johannes Fürnkranz, Tobias Scheffer, Myra Spiliopoulou (red.). Springer, 2006, s. 282–293. DOI:10.1.1.102.1296. ISBN 3-540-45375-X.
  14. Peter Auer, Nicolò Cesa-Bianchi, Paul Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. „Machine Learning”. 47, s. 235–256, 2002. 
  15. Bruno Bouzy: Old-fashioned Computer Go vs Monte-Carlo Go. W: IEEE Symposium on Computational Intelligence and Games, April 1–5, 2007, Hilton Hawaiian Village, Honolulu, Hawaii.
  16. Peter Drake. The Last-Good-Reply Policy for Monte-Carlo Go. „ICGA Journal”. 32 (4), s. 221–227, grudzień 2009. 
  17. 17,0 17,1 17,2 Sylvain Gelly, Yizao Wang, Rémi Munos, Olivier Teytaud: Modification of UCT with Patterns in Monte-Carlo Go. Raport z badań, INRIA, listopad 2006.
  18. Seth Pellegrino, Peter Drake: Investigating the Effects of Playout Strength in Monte-Carlo Go. W: Proceedings of the 2010 International Conference on Artificial Intelligence, ICAI 2010, July 12–15, 2010, Las Vegas Nevada, USA. Hamid R. Arabnia, David de la Fuente, Elena B. Kozerenko, José Angel Olivas, Rui Chang, Peter M. LaMonica, Raymond A. Liuzzi, Ashu M. G. Solo (red.). CSREA Press, 2010, s. 1015–1018. ISBN 1-60132-148-1.
  19. 19,0 19,1 Sylvain Gelly, David Silver: Combining Online and Offline Knowledge in UCT. W: Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20–24, 2007. Zoubin Ghahramani (red.). ACM, 2007, s. 273–280. ISBN 978-1-59593-793-3.
  20. G.M.J.B. Chaslot, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik, B. Bouzy. Progressive Strategies for Monte-Carlo Tree Search. „New Mathematics and Natural Computation”, s. 343–359, 2008. doi:10.1.1.106.3015. 
  21. David Silver: Reinforcement Learning and Simulation-Based Search in Computer Go. Rozprawa doktorska, University of Alberta, 2009.
  22. Rémi Coulom: CLOP: Confident Local Optimization for Noisy Black-Box Parameter Tuning. W: ACG 2011: Advances in Computer Games 13 Conference, Tilburg, the Netherlands, November 20–22.
  23. Guillaume M.J-B. Chaslot, Mark H.M. Winands, H. Jaap van den Herik: Parallel Monte-Carlo Tree Search. W: Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (red.). Springer, 2008, s. 60–71. ISBN 978-3-540-87607-6.
  24. Markus Enzenberger, Martin Müller: A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm. W: Advances in Computer Games: 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009, Revised Papers. H. Jaap Van Den Herik, Pieter Spronck (red.). Springer, 2010, s. 14–20. DOI:10.1.1.161.1984. ISBN 978-3-642-12992-6.
  25. Rémi Coulom: The Monte-Carlo Revolution in Go. W: Japanese-French Frontiers of Science Symposium. 2008.
  26. Rémi Coulom: Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. W: Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Revised Papers. H. Jaap van den Herik, Paolo Ciancarini, H. H. L. M. Donkers (red.). Springer, 2007, s. 72–83. DOI:10.1.1.81.6817. ISBN 978-3-540-75537-1.
  27. Chang-Shing Lee, Mei-Hui Wang, Guillaume Chaslot, Jean-Baptiste Hoock, Arpad Rimmel, Olivier Teytaud, Shang-Rong Tsai, Shun-Chin Hsu, Tzung-Pei Hong. The Computational Intelligence of MoGo Revealed in Taiwan’s Computer Go Tournaments. „IEEE Transactions on Computational Intelligence and AI in Games”. 1 (1), s. 73–89, 2009. 
  28. Markus Enzenberger, Martin Mūller: Fuego – An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search. Raport techniczny, University of Alberta, 2008.
  29. The Shodan Go Bet. [dostęp 2012-05-02].
  30. Sensei's Library: KGSBotRatings. [dostęp 2012-05-03].

Bibliografia[edytuj | edytuj kod]

  • Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, Simon Colton. A Survey of Monte Carlo Tree Search Methods. „IEEE Transactions on Computational Intelligence and AI in Games”. 4 (1), marzec 2012.