Monte-Carlo Tree Search

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

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 ${\displaystyle R,}$ wybieraj kolejne węzły potomne, aż dotrzesz do liścia drzewa ${\displaystyle 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 ${\displaystyle L}$ nie kończy gry, utwórz w nim jeden lub więcej węzłów potomnych i wybierz z nich jeden węzeł ${\displaystyle C.}$
• Symulacja (ang. playout): rozegraj losową symulację z węzła ${\displaystyle C.}$
• Propagacja wstecz (ang. backpropagation): na podstawie wyniku rozegranej symulacji uaktualnij informacje w węzłach na ścieżce prowadzącej od ${\displaystyle C}$ do ${\displaystyle 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

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 ${\displaystyle {\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}}$ osiąga największą wartość. W tym wzorze:

• ${\displaystyle w_{i}}$ oznacza liczbę wygranych w danym węźle po ${\displaystyle i}$-tym ruchu,
• ${\displaystyle n_{i}}$ oznacza liczbę symulacji w danym węźle po ${\displaystyle i}$-tym ruchu,
• ${\displaystyle c}$ to parametr eksploracji – teoretycznie równy ${\displaystyle {\sqrt {2}},}$ a w praktyce zwykle dobierany empirycznie,
• ${\displaystyle N_{i}}$ oznacza liczbę symulacji w rodzicu danego węzła po ${\displaystyle i}$-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 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 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

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^[16]. Heurystyki te mogą się opierać na wynikach poprzednich symulacji (np. heurystyka last good reply^[17]) 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^[18]. Paradoksalnie jednak, nie zawsze silniejsza gra w symulacjach przekłada się na silniejszą grę programów korzystających z metody MCTS^[19].

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^[18].

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^[20]. Zbliżony sposób, zwany progressive bias, polega na dodaniu do wzoru UCB1 składnika ${\displaystyle {\frac {b_{i}}{n_{i}}},}$ gdzie ${\displaystyle b_{i}}$ to heurystyczna ocena ${\displaystyle i}$-tego ruchu^[21].

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)^[20]. 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 ${\displaystyle N}$ w drzewie wariantów, jego węzły potomne ${\displaystyle 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 ${\displaystyle N}$ i poniżej niego, w których wystąpił ruch ${\displaystyle i}$ (także jeśli zagrano go w drzewie, pomiędzy węzłem ${\displaystyle 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 ${\displaystyle (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 ${\displaystyle {\tilde {w}}_{i}}$ i ${\displaystyle {\tilde {n}}_{i}}$ oznaczają liczbę wygranych symulacji zawierających ruch ${\displaystyle i}$ i liczbę wszystkich symulacji zawierających ruch ${\displaystyle i,}$ a funkcja ${\displaystyle \beta (n_{i},{\tilde {n}}_{i})}$ powinna przyjmować odpowiednio wartości bliskie jedności oraz zera dla ${\displaystyle n_{i}}$ i ${\displaystyle {\tilde {n}}_{i}}$ stosunkowo niewielkich oraz stosunkowo dużych. Jeden z wielu zaproponowanych wzorów na ${\displaystyle \beta (n_{i},{\tilde {n}}_{i}),}$ który pochodzi od D. Silvera^[22] mówi, że w zrównoważonych pozycjach można przyjąć ${\displaystyle \beta (n_{i},{\tilde {n}}_{i})={\frac {{\tilde {n}}_{i}}{n_{i}+{\tilde {n}}_{i}+4b^{2}n_{i}{\tilde {n}}_{i}}},}$ gdzie ${\displaystyle 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^[23].

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^[24]:

• 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^[25].

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^[11], ale jego pomysłu nie potraktowano wówczas poważnie. W roku 2006, zwanym rokiem rewolucji Monte Carlo w go^[26], R. Coulom opisał zastosowanie metody Monte Carlo do przeszukiwania drzew wariantów i wprowadził nazwę Monte-Carlo Tree Search^[27], L. Kocsis i Cs. Szepesvári opracowali algorytm UCT^[13], a S. Gelly i inni zastosowali UCT w swoim programie MoGo^[18]. W roku 2008 program MoGo osiągnął poziom dan (mistrzowski) w go na planszy o rozmiarach 9×9^[28], a program Fuego zaczął wygrywać w go na planszy o rozmiarach 9×9 z silnymi amatorami^[29]. 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^[30].

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^[31].