Wyszukiwanie drzewa Monte Carlo - Monte Carlo tree search

Wyszukiwanie drzew w Monte Carlo

Klasa	Algorytm wyszukiwania

W informatyce , Monte Carlo wyszukiwania drzewo ( MCTS ) jest heurystyczny algorytm wyszukiwania dla niektórych rodzajów procesów decyzyjnych , zwłaszcza osób zatrudnionych w oprogramowaniu , który gra w gry planszowe . W tym kontekście MCTS służy do rozwiązywania drzewa gry .

MCTS został połączony z sieciami neuronowymi w 2016 roku dla komputera Go . Był używany w innych grach planszowych, takich jak szachy i shogi , grach z niepełnymi informacjami, takich jak brydż i poker , a także w turowych grach strategicznych (takich jak implementacja Total War: Rome II w kampanii wysokiego poziomu AI). MCTS został również wykorzystany w samochodach autonomicznych, na przykład w oprogramowaniu Tesli Autopilot.

Historia

Metoda Monte Carlo

Metoda Monte Carlo , która wykorzystuje losowe próbkowanie do problemów deterministycznych, trudnych lub niemożliwych do rozwiązania innymi podejściami, sięga lat 40. XX wieku. W swojej pracy doktorskiej z 1987 r. Bruce Abramson połączył wyszukiwanie minimaksowe z modelem oczekiwanego wyniku opartym na losowych rozgrywkach do końca, zamiast zwykłej statycznej funkcji oceny . Abramson powiedział, że model oczekiwanych wyników „okazuje się być precyzyjny, dokładny, łatwy do oszacowania, wydajnie obliczalny i niezależny od dziedziny”. Eksperymentował dogłębnie z kółkiem i krzyżykiem, a następnie z generowanymi maszynowo funkcjami oceny dla Otella i szachów .

Takie metody zostały następnie zbadane i z powodzeniem zastosowane do wyszukiwania heurystycznego w dziedzinie automatycznego dowodzenia twierdzeń przez W. Ertela, J. Schumanna i C. Suttnera w 1989 r., poprawiając w ten sposób wykładnicze czasy wyszukiwania nieinformowanych algorytmów wyszukiwania, takich jak np. wyszukiwanie wszerz , wyszukiwanie w głąb lub pogłębianie iteracyjne .

W 1992 roku B. Brügmann zastosował go po raz pierwszy w programie Go-playing . W 2002 roku Chang i in. zaproponowali ideę „rekurencyjnego rozwijania i wycofywania” z „adaptacyjnymi” wyborami próbkowania w swoim algorytmie Adaptive Multi-stage Sampling (AMS) dla modelu procesów decyzyjnych Markowa. AMS był pierwszą pracą badającą ideę eksploracji i eksploatacji opartej na UCB w konstruowaniu próbkowanych/symulowanych drzew (Monte Carlo) i był głównym źródłem UCT (górne drzewa ufności).

Wyszukiwanie drzew Monte Carlo (MCTS)

Ranking najlepszych programów do grania w Go na serwerze KGS od 2007 roku. Od 2006 roku wszystkie najlepsze programy korzystają z wyszukiwania drzewa Monte Carlo.

W 2006 roku, zainspirowany tymi poprzednikami, Rémi Coulom opisał zastosowanie metody Monte Carlo do przeszukiwania drzewa gry i ukuł nazwę przeszukiwania drzewa Monte Carlo, L. Kocsis i Cs. Szepesvári opracował algorytm UCT (górne granice ufności stosowane do drzew), a S. Gelly i in. wdrożył UCT w swoim programie MoGo. W 2008 roku MoGo osiągnęło poziom dan (mistrz) w 9×9 Go, a program Fuego zaczął wygrywać z silnymi amatorami w 9×9 Go.

W styczniu 2012 roku program Zen wygrał 3:1 w meczu Go na planszy 19×19 z amatorskim graczem 2 dan . Firma Google Deepmind opracowała program AlphaGo , który w październiku 2015 r. stał się pierwszym programem Computer Go, który pokonał profesjonalnego gracza w Go bez utrudnień na pełnowymiarowej planszy 19x19. W marcu 2016 AlphaGo otrzymał honorowy poziom 9-dan (mistrz) w 19×19 Go za pokonanie Lee Sedola w pięciomeczowym meczu z końcowym wynikiem cztery do jednego. AlphaGo stanowi znaczną poprawę w stosunku do poprzednich programów Go, a także kamień milowy w uczeniu maszynowym, ponieważ wykorzystuje wyszukiwanie drzewa Monte Carlo ze sztucznymi sieciami neuronowymi ( metoda głębokiego uczenia ) w celu określenia zasad (wybór ruchu) i wartości, co znacznie przewyższa poprzednie programy .

Algorytm MCTS był również wykorzystywany w programach grających w inne gry planszowe (np. Hex , Havannah , Game of the Amazons i Arimaa ), gry wideo czasu rzeczywistego (np. Ms. Pac-Man i Fable Legends ) oraz gry niedeterministyczne (takich jak skat , poker , Magic: The Gathering lub Settlers of Catan ).

Zasada działania

MCTS koncentruje się na analizie najbardziej obiecujących ruchów, rozszerzając drzewo poszukiwań na podstawie losowego próbkowania przestrzeni poszukiwań. Zastosowanie wyszukiwania drzewa Monte Carlo w grach opiera się na wielu playoutach, zwanych również roll- outami . W każdej rozgrywce gra toczy się do samego końca, wybierając losowo ruchy. Ostateczny wynik każdej rozgrywki jest następnie wykorzystywany do ważenia węzłów w drzewie gry, dzięki czemu w przyszłych rozgrywkach istnieje większe prawdopodobieństwo, że zostaną wybrane lepsze węzły.

Najbardziej podstawowym sposobem wykorzystania playoutów jest zastosowanie tej samej liczby playoutów po każdym legalnym ruchu bieżącego gracza, a następnie wybranie ruchu, który doprowadził do największej liczby zwycięstw. Skuteczność tej metody — zwanej Pure Monte Carlo Game Search — często wzrasta wraz z upływem czasu, ponieważ do ruchów, które często skutkowały zwycięstwem bieżącego gracza zgodnie z poprzednimi rozegraniami, przypisywanych jest więcej playoutów. Każda runda przeszukiwania drzewa Monte Carlo składa się z czterech kroków:

• Wybór : Start z głównego R i wybrać kolejne węzły potomne aż węzeł liść L została osiągnięta. Korzeń to aktualny stan gry, a liść to dowolny węzeł, który ma potencjalne dziecko, od którego nie zainicjowano jeszcze żadnej symulacji (odtwarzania). Poniższa sekcja mówi więcej o sposobie promowania wyboru węzłów podrzędnych, który pozwala drzewu gry rozwijać się w kierunku najbardziej obiecujących ruchów, co jest esencją przeszukiwania drzewa Monte Carlo.
• Rozszerzenie : O ile L nie zakończy gry zdecydowanie (np. wygrana/przegrana/remis) dla któregoś z graczy, stwórz jeden (lub więcej) węzłów potomnych i wybierz węzeł C z jednego z nich. Węzły potomne to wszelkie prawidłowe ruchy z pozycji gry określonej przez L .
• Symulacja : Wykonaj jedną losową playout z węzła C . Ten krok jest czasami nazywany również odtwarzaniem lub wdrażaniem. Rozgrywka może być tak prosta, jak wybieranie jednolitych losowych ruchów, dopóki gra nie zostanie rozstrzygnięta (na przykład w szachach gra jest wygrana, przegrana lub zremisowana).
• Wstecznej Use wynikiem playout do aktualizacji informacji w węzłach na drodze od C do badań .

Krok wyszukiwania drzewa Monte Carlo.

Ten wykres przedstawia kroki związane z jedną decyzją, przy czym każdy węzeł pokazuje stosunek wygranych do łącznej liczby rozgrywek od tego punktu w drzewie gry dla gracza, którego reprezentuje węzeł. Na diagramie wyboru czarny ma zamiar się poruszyć. Węzeł główny pokazuje, że jak dotąd jest 11 wygranych z 21 rozegranych dla białych z tej pozycji. Uzupełnia on sumę 10/21 czarnych wygranych pokazanych wzdłuż trzech czarnych węzłów pod nim, z których każdy reprezentuje możliwy ruch czarnych.

Jeśli biały przegra symulację, wszystkie węzły wzdłuż zaznaczenia zwiększyły swoją liczbę symulacji (mianownik), ale wśród nich tylko czarne węzły otrzymały wygrane (licznik). Gdyby zamiast tego białe węzły wygrały, wszystkie węzły wzdłuż zaznaczenia nadal zwiększyłyby liczbę symulacji, ale wśród nich tylko białe węzły zostałyby przypisane zwycięstwom. W grach, w których możliwe są remisy, remis powoduje zwiększenie licznika zarówno czarnego, jak i białego o 0,5, a mianownika o 1. Zapewnia to, że podczas selekcji wybory każdego gracza rozszerzają się w kierunku najbardziej obiecujących ruchów dla tego gracza, co odzwierciedla celem każdego gracza, aby zmaksymalizować wartość swojego ruchu.

Rundy poszukiwań są powtarzane, dopóki pozostaje czas przydzielony na ruch. Następnie ruch z największą liczbą wykonanych symulacji (tj. z najwyższym mianownikiem) jest wybierany jako ostateczna odpowiedź.

Czyste wyszukiwanie gier Monte Carlo

Ta podstawowa procedura może być zastosowana do każdej gry, której pozycje z konieczności mają skończoną liczbę ruchów i skończoną długość. Dla każdej pozycji określane są wszystkie możliwe ruchy: k losowych gier jest rozgrywanych do samego końca, a wyniki są rejestrowane. Wybierany jest ruch prowadzący do najlepszego wyniku. Remisy są łamane przez uczciwe rzuty monetą. Pure Monte Carlo Game Search zapewnia silną grę w kilku grach z elementami losowymi, tak jak w grze EinStein würfelt nicht! . Zbiega się do optymalnej gry (ponieważ k dąży do nieskończoności) w grach planszowych z losową kolejnością tur, na przykład w Hex z losową kolejnością tur. AlphaZero DeepMind zastępuje etap symulacji oceną opartą na sieci neuronowej.

Eksploracja i eksploatacja

Główną trudnością w doborze węzłów potomnych jest zachowanie równowagi między wykorzystywaniem głębokich wariantów po ruchach o wysokim średnim współczynniku wygranych a badaniem ruchów z kilkoma symulacjami. Pierwszą formułę równoważenia eksploatacji i eksploracji w grach, zwaną UCT (ang. Upper Confidence Bound 1 w odniesieniu do drzew ), wprowadzili Levente Kocsis i Csaba Szepesvári . UCT opiera się na formule UCB1 wyprowadzonej przez Auera, Cesę-Bianchi i Fischera oraz algorytmie AMS (Adaptive Multi-stage Sampling), który został po raz pierwszy zastosowany do wieloetapowych modeli decyzyjnych (w szczególności procesów decyzyjnych Markowa ) przez Changa, Fu, Hu i Marcusa. Kocsis i Szepesvári zalecają, aby w każdym węźle drzewa gry wybrać ruch, dla którego wyrażenie ma największą wartość. W tej formule: ${\displaystyle {\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_ {i}}{n_ {i}}}}}$

• w _i oznacza liczbę wygranych dla węzła rozpatrywanego po i -tym ruchu
• n _i oznacza liczbę symulacji dla węzła rozpatrywanego po i -tym ruchu
• N _i oznacza całkowitą liczbę symulacji po i -tym ruchu wykonanym przez węzeł macierzysty rozważanego
• c jest parametrem eksploracji — teoretycznie równym √ 2 ; w praktyce zwykle wybierane empirycznie

Pierwszy składnik powyższej formuły odpowiada eksploatacji; jest wysoka dla ruchów o wysokim średnim współczynniku wygranych. Drugi składnik odpowiada eksploracji; jest wysoki dla ruchów z kilkoma symulacjami.

Większość współczesnych implementacji przeszukiwania drzewa Monte Carlo opiera się na pewnym wariancie UCT, który wywodzi swoje korzenie z algorytmu optymalizacji symulacji AMS do estymacji funkcji wartości w skończonych procesach decyzyjnych Markowa (MDPs) wprowadzonego przez Chang i in. (2005) w badaniach operacyjnych . (AMS był pierwszą pracą badającą ideę eksploracji i eksploatacji opartej na UCB w konstruowaniu próbkowanych/symulowanych drzew (Monte Carlo) i był głównym zalążkiem UCT.)

Zalety i wady

Chociaż udowodniono, że ocena ruchów w przeszukiwaniu drzewa Monte Carlo zbiega się do minimaksu , podstawowa wersja przeszukiwania drzewa Monte Carlo zbiega się tylko w grach zwanych „Monte Carlo Perfect”. Jednak przeszukiwanie drzewa metodą Monte Carlo ma znaczną przewagę nad przycinaniem alfa-beta i podobnymi algorytmami, które minimalizują przestrzeń wyszukiwania.

W szczególności, czyste przeszukiwanie drzewa Monte Carlo nie wymaga jawnej funkcji oceny . Samo zaimplementowanie mechaniki gry wystarczy do eksploracji przestrzeni poszukiwań (tj. generowania dozwolonych ruchów w danej pozycji i warunków zakończenia gry). Jako takie, przeszukiwanie drzewa Monte Carlo może być stosowane w grach bez rozwiniętej teorii lub w ogólnej grze .

Drzewo gry w wyszukiwaniu drzewa Monte Carlo rośnie asymetrycznie, ponieważ metoda koncentruje się na bardziej obiecujących poddrzewach. Dzięki temu osiąga lepsze wyniki niż klasyczne algorytmy w grach o wysokim współczynniku rozgałęzienia .

Wadą jest to, że w niektórych pozycjach mogą pojawić się ruchy, które wydają się pozornie silne, ale w rzeczywistości prowadzą do przegranej subtelną linią gry. Takie „stany pułapki” wymagają dokładnej analizy, aby były prawidłowo obsługiwane, szczególnie podczas gry z doświadczonym graczem; jednak MCTS może nie „widzieć” takich linii ze względu na swoją politykę selektywnego rozszerzania węzłów. Uważa się, że mogło to być jedną z przyczyn porażki AlphaGo w czwartym meczu z Lee Sedolem . Zasadniczo wyszukiwanie próbuje przyciąć sekwencje, które są mniej istotne. W niektórych przypadkach luz może prowadzić do bardzo specyficznej linii gry, która jest istotna, ale która jest pomijana podczas przycinania drzewa, a zatem wynik ten jest „poza radarem poszukiwań”.

Ulepszenia

Zaproponowano różne modyfikacje podstawowej metody przeszukiwania drzewa Monte Carlo w celu skrócenia czasu przeszukiwania. Niektóre z nich wykorzystują wiedzę ekspercką specyficzną dla danej dziedziny, inne nie.

Wyszukiwanie drzewa Monte Carlo może używać zarówno lekkich, jak i ciężkich playoutów. Lekkie playouty składają się z losowych ruchów, podczas gdy ciężkie playouty stosują różne heurystyki, aby wpłynąć na wybór ruchów. Te heurystyki mogą wykorzystywać wyniki poprzednich rozgrywek (np. heurystykę Last Good Reply) lub wiedzę ekspercką na temat danej gry. Na przykład w wielu programach do gry w Go pewne wzory kamieni w części planszy wpływają na prawdopodobieństwo przemieszczenia się do tego obszaru. Paradoksalnie, nieoptymalne granie w symulacjach czasami sprawia, że ​​program przeszukiwania drzewa Monte Carlo jest ogólnie silniejszy.

Wzory hane (otaczające kamienie przeciwnika) używane w playoutach przez program MoGo. Korzystne jest, aby zarówno czarny, jak i biały umieścić kamień na środkowym kwadracie, z wyjątkiem wzoru znajdującego się najbardziej po prawej stronie, gdzie faworyzuje tylko czarny.

Wiedza specyficzna dla domeny może być wykorzystana podczas budowania drzewa gry, aby pomóc w wykorzystaniu niektórych wariantów. Jeden z takich sposobów przypisuje niezerowe liczby a priori do liczby wygranych i rozegranych symulacji podczas tworzenia każdego węzła podrzędnego, co prowadzi do sztucznie podniesionych lub obniżonych średnich współczynników wygranych, które powodują, że węzeł jest wybierany odpowiednio częściej lub rzadziej na etapie wyboru. Pokrewna metoda, zwana progresywnym obciążeniem, polega na dodaniu do wzoru UCB1 elementu, gdzie b _i jest wynikiem heurystycznym i-tego ruchu. ${\ Displaystyle {\ Frac {b_ {i}} {n_ {i}}}}$

Podstawowe przeszukiwanie drzewa Monte Carlo zbiera wystarczającą ilość informacji, aby znaleźć najbardziej obiecujące ruchy dopiero po wielu rundach; do tego czasu jego ruchy są zasadniczo losowe. Ta faza eksploracji może zostać znacznie skrócona w pewnej klasie gier za pomocą RAVE ( Oszacowanie wartości szybkiego działania ). W tych grach permutacje sekwencji ruchów prowadzą do tej samej pozycji. Zazwyczaj są to gry planszowe, w których ruch polega na umieszczeniu pionka lub kamienia na planszy. W takich grach na wartość każdego ruchu często tylko nieznacznie wpływają inne ruchy.

W RAVE, dla danego węzła drzewa gry N , jego węzły potomne C _i przechowują nie tylko statystyki wygranych w playoutach rozpoczętych w węźle N, ale także statystyki wygranych we wszystkich playoutach rozpoczętych w węźle N i poniżej, jeśli zawierają ruch i (również wtedy, gdy ruch został zagrany w drzewie, między węzłem N a playoutem). W ten sposób na zawartość węzłów drzewa wpływają nie tylko ruchy zagrane od razu na danej pozycji, ale także te same ruchy zagrane później.

RAVE na przykładzie gry w kółko i krzyżyk. W czerwonych węzłach statystyki RAVE zostaną zaktualizowane po symulacji b1-a2-b3.

W przypadku korzystania z RAVE etap wyboru wybiera węzeł, dla którego zmodyfikowana formuła UCB1 ma największą wartość. W tym wzorze i oznaczają liczbę wygranych playoutów zawierających ruch i oraz liczbę wszystkich playoutów zawierających ruch i , a funkcja powinna być bliska jedności i zerowa odpowiednio dla stosunkowo małych i stosunkowo dużych n _i i . Jedna z wielu formuł na , zaproponowana przez D. Silvera, mówi, że w pozycjach zrównoważonych można przyjąć , gdzie b jest empirycznie wybraną stałą. ${\ Displaystyle (1-\ beta (n_ {i} {\ tylda {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}}}}}$${\ Displaystyle {\ tylda {w}} _ {i}}$${\ Displaystyle {\ tylda {n}} _ {i}}$${\ Displaystyle \ beta (n_ {i}, {\ tylda {n}} _ {i})}$${\ Displaystyle {\ tylda {n}} _ {i}}$${\ Displaystyle \ beta (n_ {i}, {\ tylda {n}} _ {i})}$${\ Displaystyle \ beta (n_ {i} {\ tylda {n}} _ {i}) = {\ Frac {{\ tylda {n}} _ {i}} {n_ {i} + {\ tylda { n}}_{i}+4b^{2}n_{i}{\tylda {n}}_{i}}}}$

Heurystyki stosowane w przeszukiwaniu drzewa Monte Carlo często wymagają wielu parametrów. Istnieją zautomatyzowane metody dostrajania parametrów w celu maksymalizacji współczynnika wygranych.

Wyszukiwanie drzewa Monte Carlo może być wykonywane jednocześnie przez wiele wątków lub procesów . Istnieje kilka zasadniczo różnych metod jego równoległego wykonywania:

• Równoległość liścia , czyli równoległe wykonywanie wielu playoutów z jednego liścia drzewa gry.
• Równoległość korzeni , czyli równoległe budowanie niezależnych drzew gry i wykonywanie ruchu na podstawie konarów wszystkich tych drzew.
• Równoległość drzewa , czyli równoległe budowanie tego samego drzewa gry, chroniąc dane przed równoczesnym zapisem albo z jednym, globalnym muteksem , z większą liczbą muteksów, albo z nieblokującą synchronizacją .

Zobacz też

• AlphaGo , program Go wykorzystujący wyszukiwanie drzewa Monte Carlo, uczenie ze wzmacnianiem i uczenie głębokie .
• AlphaGo Zero , zaktualizowany program Go wykorzystujący wyszukiwanie drzewa Monte Carlo, uczenie ze wzmocnieniem i uczenie głębokie .
• AlphaZero , uogólniona wersja AlphaGo Zero wykorzystująca wyszukiwanie drzewa Monte Carlo, uczenie ze wzmacnianiem i uczenie głębokie .
• Leela Chess Zero , darmowe oprogramowanie implementujące metody AlphaZero do gry w szachy, które jest obecnie jednym z wiodących programów do gry w szachy.

Bibliografia

Bibliografia

• Cameron Browne; Edwarda Powleya; Daniela Whitehouse'a; Szymon Lucas; Piotr I. Cowling; Philippa Rohlfshagena; Stephena Tavenera; Diego Pereza; Spyridon Samotraki; Simon Colton (marzec 2012). „Ankieta metod wyszukiwania drzewa Monte Carlo”. Transakcje IEEE dotyczące inteligencji obliczeniowej i sztucznej inteligencji w grach . 4 (1): 1-43. CiteSeerX  10.1.1.297.3086 . doi : 10.1109/tciaig.2012.2186810 . S2CID  9316331 .

Zewnętrzne linki

• Przewodnik dla początkujących do wyszukiwania drzew w Monte Carlo