Tekst źródłowy strony Monte-Carlo Tree Search

{{Dopracować|aktualizacja}}
'''Monte-Carlo Tree Search''' (w skrócie '''MCTS''') – [[heurystyka (informatyka)|heurystyka]] podejmowania decyzji w pewnych zadaniach [[sztuczna inteligencja|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]]<ref>{{cytuj stronę |url=http://www.mcts.ai/?q=mcts |tytuł=MCTS.ai: Everything Monte Carlo Tree Search |data dostępu=2012-02-19}}</ref>. Metodę MCTS stosuje się również w programach grających w inne gry planszowe (między innymi [[Hex (gra planszowa)|Hex]]<ref>{{cytuj pismo |autor=Broderick Arneson, Ryan Hayward, Philip Henderson |tytuł=MoHex Wins Hex Tournament |url=http://webdocs.cs.ualberta.ca/~hayward/papers/rptPamplona.pdf|czasopismo=ICGA Journal |wolumin=32 |wydanie=2 |strony=114–116 |rok=2009 |miesiąc=czerwiec}}</ref>, [[Havannah]]<ref>{{cytuj książkę |autor=Timo Ewalds |tytuł=Playing and Solving Havannah |url=http://havannah.ewalds.ca/thesis.pdf|wydawca=Praca magisterska, University of Alberta |rok=2011}}</ref>, [[Amazonki (gra)|Amazonki]]<ref>{{cytuj książkę |tytuł=Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings |inni=H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H.M. Winands (red.) |autor r=Richard J. Lorentz |rozdział=Amazons Discover Monte-Carlo |strony=13–24 |wydawca=Springer |rok=2008 |isbn=978-3-540-87607-6}}</ref> i [[Arimaa]]<ref>{{cytuj książkę |autor=Tomáš Kozelek |tytuł=Methods of MCTS and the game Arimaa |url=http://arimaa.com/arimaa/papers/TomasKozelekThesis/mt.pdf|wydawca=Praca magisterska, Uniwersytet Karola w Pradze |rok=2009}}</ref>), w gry czasu rzeczywistego (na przykład ''[[Ms. Pac-Man]]''<ref>{{cytuj pismo |autor=Xiaocong Gan, Yun Bao, Zhangang Han |tytuł=Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man |czasopismo=ICGA Journal |strony=209–222 |wolumin=34 |wydanie=4 |rok=2011 |miesiąc=grudzień}}</ref>) oraz w gry niedeterministyczne (na przykład [[skat]]a<ref>{{cytuj książkę |tytuł=IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009 |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.3077 |inni=Craig Boutilier (red.) |autor r=Michael Buro, Jeffrey Richard Long, Timothy Furtak, Nathan R. Sturtevant |rozdział=Improving State Evaluation, Inference, and Search in Trick-Based Card Games |strony=1407–1413 |rok=2009 }}</ref>, [[poker]]a<ref>{{cytuj pismo |autor=Jonathan Rubin, Ian Watson |tytuł=Computer poker: A review |url=http://www.cs.auckland.ac.nz/~jrub001/files/CPReviewPreprintAIJ.pdf|czasopismo=Artificial Intelligence |wolumin=175 |wydanie=5–6 |rok=2011 |miesiąc=kwiecień |doi=10.1016/j.artint.2010.12.005}}</ref>, ''[[Magic: The Gathering]]''<ref>{{cytuj książkę |tytuł=CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games |url=http://www.ieee-cig.org/cig-2009/Proceedings/proceedings/papers/cig2009_002e.pdf|autor r=C.D. Ward, P.I. Cowling |rozdział=Monte Carlo Search Applied to Card Selection in Magic: The Gathering |wydawca=IEEE Press |rok=2009}}</ref> czy ''[[Osadnicy z Catanu|Osadników z Catanu]]''<ref>{{cytuj książkę |tytuł=Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers |url=https://www.ualberta.ca/~szita/papers/SzitaChaslotSpronck09Monte-Carlo.pdf|inni=H. Jaap van den Herik, Pieter Spronck (red.) |autor r=István Szita, Guillaume Chaslot, Pieter Spronck |rozdział=Monte-Carlo Tree Search in Settlers of Catan |strony=21–32 |wydawca=Springer |rok=2010 |isbn=978-3-642-12992-6}}</ref>). 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 ==
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<ref name="Bruegmann">{{cytuj książkę |nazwisko=Brügmann |imię=Bernd |tytuł=Monte Carlo Go |url=http://www.ideanest.com/vegos/MonteCarloGo.pdf |wydawca=Raport techniczny, wydział fizyki, Syracuse University |rok=1993}}</ref>. 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<ref>{{cytuj książkę |tytuł=Proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference, October 22–24, 2008, Stanford, California, USA |url=http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf|inni=Christian Darken, Michael Mateas (red.) |autor r=Guillaume Chaslot, Sander Bakkes, Istvan Szita, Pieter Spronck |rozdział=Monte-Carlo Tree Search: A New Framework for Game AI |strony=216–217 |rok=2008 |wydawca=The AAAI Press |isbn=978-1-57735-391-1}}</ref>:
* Wybór (ang. ''selection''): zaczynając od korzenia drzewa <math>R,</math> wybieraj kolejne węzły potomne, aż dotrzesz do liścia drzewa <math>L.</math> 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 <math>L</math> nie kończy gry, utwórz w nim jeden lub więcej węzłów potomnych i wybierz z nich jeden węzeł <math>C.</math>
* Symulacja (ang. ''playout''): rozegraj losową symulację z węzła <math>C.</math>
* Propagacja wstecz (ang. ''backpropagation''): na podstawie wyniku rozegranej symulacji uaktualnij informacje w węzłach na ścieżce prowadzącej od <math>C</math> do <math>R.</math>
Przykładowe kroki jednej tury przedstawiono na poniższym rysunku. Każdy węzeł drzewa przechowuje informacje o liczbie wygranych/liczbie wykonanych symulacji.
[[Plik:MCTS (Polish) Fixed.svg|centruj|ramka|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 ==
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<ref name="Kocsis-Szepesvari">{{cytuj książkę |tytuł=Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006, Proceedings. Lecture Notes in Computer Science 4212 |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296 |inni=Johannes Fürnkranz, Tobias Scheffer, Myra Spiliopoulou (red.) |nazwisko r=Kocsis |imię r=Levente |nazwisko2 r=Szepesvári |imię2 r=Csaba |rozdział=Bandit based Monte-Carlo Planning |isbn=3-540-45375-X |strony=282–293 |rok=2006 |wydawca=Springer |doi=10.1007/11871842_29}}</ref>, opierając się na wzorze UCB1, wyprowadzonym w pracy Auera, Cesa-Bianchiego i Fischera<ref>{{cytuj pismo |nazwisko=Auer |imię=Peter |nazwisko2=Cesa-Bianchi |imię2=Nicolò |nazwisko3=Fischer |imię3=Paul |tytuł=Finite-time Analysis of the Multiarmed Bandit Problem |url=http://moodle.technion.ac.il/pluginfile.php/192340/mod_resource/content/0/UCB.pdf|czasopismo=Machine Learning |wolumin=47 |strony=235–256 |rok=2002}}</ref>. Kocsis i Szepesvári zalecają w każdym węźle drzewa wariantów wybór tego ruchu, dla którego wyrażenie <math>\frac{w_i}{n_i} + c\sqrt\frac{\ln N_i}{n_i}</math> osiąga największą wartość. W tym wzorze:
* <math>w_i</math> oznacza liczbę wygranych w danym węźle po <math>i</math>-tym ruchu,
* <math>n_i</math> oznacza liczbę symulacji w danym węźle po <math>i</math>-tym ruchu,
* <math>c</math> to parametr eksploracji – teoretycznie równy <math>\sqrt{2},</math> a w praktyce zwykle dobierany empirycznie,
* <math>N_i</math> oznacza liczbę symulacji w rodzicu danego węzła po <math>i</math>-tym ruchu.

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 [[Implementacja (informatyka)|implementacji]] metody MCTS opiera się na jakimś wariancie metody UCT.

== Wady i zalety ==
Dowiedziono wprawdzie, że w metodzie MCTS ocena ruchów jest zbieżna do [[algorytm min-max|oceny min-max]]<ref>{{cytuj książkę |tytuł=IEEE Symposium on Computational Intelligence and Games, April 1–5, 2007, Hilton Hawaiian Village, Honolulu, Hawaii |url=http://ewh.ieee.org/cmte/cis/mtsc/ieeecis/tutorial2007/Bruno_Bouzy_2007.pdf|nazwisko r=Bouzy |imię r=Bruno |rozdział=Old-fashioned Computer Go vs Monte-Carlo Go}}</ref>, 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 [[algorytm alfa-beta|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 ==
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<ref>Swiechowski, M.; Mandziuk, J., "Self-Adaptation of Playing Strategies in General Game Playing" (2010), ''IEEE Transactions on Computational Intelligence and AI in Games'', vol: 6(4), pp. 367-381, doi: 10.1109/TCIAIG.2013.2275163, http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6571225&isnumber=4804729</ref>. Heurystyki te mogą się opierać na wynikach poprzednich symulacji (np. heurystyka ''last good reply''<ref>{{cytuj pismo |nazwisko=Drake |imię=Peter |tytuł=The Last-Good-Reply Policy for Monte-Carlo Go |czasopismo=ICGA Journal |wolumin=32 |wydanie=4 |strony=221–227 |rok=2009 |miesiąc=grudzień}}</ref>) 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 [[goban]]u wpływają na prawdopodobieństwa ruchów w tej części<ref name="Gelly-et-al">{{cytuj książkę |autor=Sylvain Gelly, Yizao Wang, Rémi Munos, Olivier Teytaud |tytuł=Modification of UCT with Patterns in Monte-Carlo Go |url=http://hal.inria.fr/docs/00/11/72/66/PDF/MoGoReport.pdf|rok=2006 |miesiąc=listopad |wydawca=Raport z badań, INRIA}}</ref>. Paradoksalnie jednak, nie zawsze silniejsza gra w symulacjach przekłada się na silniejszą grę programów korzystających z metody MCTS<ref>{{cytuj książkę |tytuł=Proceedings of the 2010 International Conference on Artificial Intelligence, ICAI 2010, July 12–15, 2010, Las Vegas Nevada, USA |inni=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.) |autor r=Seth Pellegrino, Peter Drake |rozdział=Investigating the Effects of Playout Strength in Monte-Carlo Go |strony=1015–1018 |wydawca=CSREA Press |rok=2010 |isbn=1-60132-148-1}}</ref>.

[[Plik:Mogo-hane.svg|frame|center|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<ref name="Gelly-et-al" />.]]

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<ref name="Gelly-Silver">{{cytuj książkę |tytuł=Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20–24, 2007 |url=http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf|inni=Zoubin Ghahramani (red.) |autor r=Sylvain Gelly, David Silver |rozdział=Combining Online and Offline Knowledge in UCT |strony=273–280 |wydawca=ACM |rok=2007 |isbn=978-1-59593-793-3}}</ref>. Zbliżony sposób, zwany ''progressive bias'', polega na dodaniu do wzoru UCB1 składnika <math>\frac{b_i}{n_i},</math> gdzie <math>b_i</math> to heurystyczna ocena <math>i</math>-tego ruchu<ref>{{cytuj pismo |autor=G.M.J.B. Chaslot, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik, B. Bouzy |tytuł=Progressive Strategies for Monte-Carlo Tree Search |url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.3015 |czasopismo=New Mathematics and Natural Computation |wolumin=4 |wydanie=3 |strony=343–359 |rok=2008 |doi=10.1142/S1793005708001094}}</ref>.

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'')<ref name="Gelly-Silver" />. 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 <math>N</math> w drzewie wariantów, jego węzły potomne <math>C_i</math> przechowują oprócz zwykłej statystyki zwycięstw w symulacjach także statystykę zwycięstw we wszystkich tych symulacjach rozpoczętych w węźle <math>N</math> i poniżej niego, w których wystąpił ruch <math>i</math> (także jeśli zagrano go w drzewie, pomiędzy węzłem <math>N</math> 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.

[[Plik:Tic-tac-toe-RAVE-Polish.svg|frame|center|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 <math>(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}</math> przyjmuje największą wartość. We wzorze tym <math>\tilde{w}_i</math> i <math>\tilde{n}_i</math> oznaczają liczbę wygranych symulacji zawierających ruch <math>i</math> i liczbę wszystkich symulacji zawierających ruch <math>i,</math> a funkcja <math>\beta(n_i, \tilde{n}_i)</math> powinna przyjmować odpowiednio wartości bliskie jedności oraz zera dla <math>n_i</math> i <math>\tilde{n}_i</math> stosunkowo niewielkich oraz stosunkowo dużych. Jeden z wielu zaproponowanych wzorów na <math>\beta(n_i, \tilde{n}_i),</math> który pochodzi od D. Silvera<ref>{{cytuj książkę |autor=David Silver |tytuł=Reinforcement Learning and Simulation-Based Search in Computer Go |url=http://papersdb.cs.ualberta.ca/~papersdb/uploaded_files/1029/paper_thesis.pdf|wydawca=Rozprawa doktorska, University of Alberta |rok=2009}}</ref> mówi, że w zrównoważonych pozycjach można przyjąć <math>\beta(n_i, \tilde{n}_i)=\frac{\tilde{n}_i}{n_i+\tilde{n}_i+4b^2 n_i\tilde{n}_i},</math> gdzie <math>b</math> 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<ref>{{cytuj książkę |tytuł=ACG 2011: Advances in Computer Games 13 Conference, Tilburg, the Netherlands, November 20–22 |url=http://remi.coulom.free.fr/CLOP/|autor r=Rémi Coulom |rozdział=CLOP: Confident Local Optimization for Noisy Black-Box Parameter Tuning}}</ref>.

Metodę MCTS może jednocześnie wykonywać wiele [[wątek (informatyka)|wątków]] lub [[proces (informatyka)|procesów]]. Istnieje kilka zasadniczo różnych sposobów jej [[przetwarzanie współbieżne|współbieżnego]] wykonywania<ref>{{cytuj książkę |tytuł=Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings |url=http://www.personeel.unimaas.nl/m-winands/documents/multithreadedMCTS2.pdf|inni=H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H.M. Winands (red.) |autor r=Guillaume M.J-B. Chaslot, Mark H.M. Winands, H. Jaap van den Herik |rozdział=Parallel Monte-Carlo Tree Search |strony=60–71 |wydawca=Springer |rok=2008 |isbn=978-3-540-87607-6}}</ref>:
* 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 [[blokada (informatyka)|blokady]] (ang. ''mutex''), bądź to większej liczby blokad, bądź też [[synchronizacja nieblokująca|synchronizacji nieblokującej]]<ref>{{cytuj książkę |tytuł=Advances in Computer Games: 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009, Revised Papers |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.161.1984 |inni=H. Jaap Van Den Herik, Pieter Spronck (red.) |autor r=Markus Enzenberger, Martin Müller |rozdział=A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm |strony=14–20 |wydawca=Springer |rok=2010 |doi=10.1007/978-3-642-12993-3_2 |isbn=978-3-642-12992-6}}</ref>.

== Historia ==
[[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<ref name="Bruegmann" />, ale jego pomysłu nie potraktowano wówczas poważnie. W roku 2006, zwanym rokiem rewolucji Monte Carlo w go<ref>{{cytuj książkę |tytuł=Japanese-French Frontiers of Science Symposium |url=http://remi.coulom.free.fr/JFFoS/JFFoS.pdf|autor r=Rémi Coulom |rozdział=The Monte-Carlo Revolution in Go |rok=2008}}</ref>, R. Coulom opisał zastosowanie metody Monte Carlo do przeszukiwania drzew wariantów i wprowadził nazwę Monte-Carlo Tree Search<ref>{{cytuj książkę |tytuł=Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Revised Papers |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.81.6817 |inni=H. Jaap van den Herik, Paolo Ciancarini, H.H.L.M. Donkers (red.) |autor r=Rémi Coulom |rozdział=Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search |strony=72–83 |wydawca=Springer |rok=2007 |isbn=978-3-540-75537-1 |doi=10.1007/978-3-540-75538-8_7}}</ref>, L. Kocsis i Cs. Szepesvári opracowali algorytm UCT<ref name="Kocsis-Szepesvari" />, a S. Gelly i inni zastosowali UCT w swoim programie MoGo<ref name="Gelly-et-al" />. W roku 2008 program MoGo osiągnął poziom ''[[Stopnie i rankingi w go|dan]]'' (mistrzowski) w go na planszy o rozmiarach 9×9<ref>{{cytuj pismo |autor=Chang-Shing Lee, Mei-Hui Wang, Guillaume Chaslot, Jean-Baptiste Hoock, Arpad Rimmel, Olivier Teytaud, Shang-Rong Tsai, Shun-Chin Hsu, Tzung-Pei Hong |tytuł=The Computational Intelligence of MoGo Revealed in Taiwan’s Computer Go Tournaments |url=http://hal.inria.fr/docs/00/36/97/86/PDF/TCIAIG-2008-0010_Accepted_.pdf|czasopismo=IEEE Transactions on Computational Intelligence and AI in Games |strony=73–89 |wolumin=1 |wydanie=1 |rok=2009}}</ref>, a program Fuego zaczął wygrywać w go na planszy o rozmiarach 9×9 z silnymi amatorami<ref>{{cytuj książkę |autor=Markus Enzenberger, Martin Mūller |tytuł=Fuego – An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search |url=https://www.cs.ualberta.ca/system/files/tech_report/2009/TR09-08_0.pdf|wydawca=Raport techniczny, University of Alberta |rok=2008}}</ref>. 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''<ref>{{cytuj stronę |url=http://dcook.org/gobet/ |tytuł=The Shodan Go Bet |data dostępu=2012-05-02}}</ref>.

[[Plik:Computer-go-ratings-Polish.svg|frame|center|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<ref>{{cytuj stronę |url=http://senseis.xmp.net/?KGSBotRatings |tytuł=Sensei’s Library: KGSBotRatings |data dostępu=2012-05-03}}</ref>.]]

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{cytuj pismo |autor=Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, Simon Colton |tytuł=A Survey of Monte Carlo Tree Search Methods |url=http://www.cameronius.com/cv/mcts-survey-master.pdf|czasopismo=IEEE Transactions on Computational Intelligence and AI in Games |wolumin=4 |wydanie=1 |miesiąc=marzec |rok=2012 |odn=nie}}
* {{cytuj pismo |autor=Maciej Świechowski, Konrad Godlewski, Bartosz Sawicki, Jacek Mańdziuk |tytuł=Monte Carlo Tree Search: a review of recent modifications and applications|url=https://link.springer.com/article/10.1007/s10462-022-10228-y|czasopismo= Springer Nature Artificial Intelligence Review |wolumin=56| strony= 497–2562 (66 stron)|miesiąc=lipiec | rok=2022 |wydanie=3 |doi=10.1007/s10462-022-10228-y|arxiv=2103.04931 }}


[[Kategoria:Algorytmy grafowe]]
[[Kategoria:Produkcja gier komputerowych]]