3: Co to takiego MCTS

(obraz za Wikipedia)

Zacznę od przedstawienia mechanizmu działania MCTS. Jest to algorytm, który tworzy w pamięci komputera drzewo analizy.

Klasyczny wariant MCTS heurystykę, czyli wycenę pozycji w liściu, opiera na przeprowadzeniu symulacji losowej rozgrywki. Wycena taka na pewno nie jest precyzyjna, może być jednak wykonana stosunkowo szybko. Drzewo może więc posiadać dużo rozgałęzień i liści. Statystyki wyników losowych rozgrywek są na bieżąco aktualizowane w odpowiednich węzłach drzewa. Algorytm opiera się na wielu kolejno przeprowadzanych “iteracjach”, z których każda rozpoczyna się w “korzeniu drzewa” - czyli reprezentacji bieżącej sytuacji na planszy w rzeczywistej grze - i składa się z czterech kroków:

• Krok pierwszy, nazywany “selekcją” albo “wyborem”, to wędrówka po istniejącym w pamięci komputera drzewie w jego dotychczasowym kształcie od korzenia do jednego z liści. Po drodze dla każdego węzła, przez który przechodzimy, podejmowana jest decyzja, w które rozgałęzienie będziemy się zagłębiać z naszą analizą. Za każdym razem decyzja taka jest próbą wyważenia między tym, na ile “obiecująca” wydaje się jakaś gałąź, a tym, na ile inne gałęzie są jeszcze niezbadane. Istnieje kilka wzorów matematycznych wynikających z teorii statystyki, które optymalizują sposób podejmowania takich decyzji.
• Krok drugi iteracji MCTS to ekspansja, czyli rozrost. Jest to zamiana liścia, do którego dotarliśmy, w węzeł poprzez dodanie do niego jakiejś ustalonej liczby nowych liści. Liczba ta, zależnie od wariantu MCTS, może się wahać od jednego do liczby wszystkich możliwych zagrań w danej pozycji.
• Krok trzeci to – w klasycznym wariancie algorytmu - losowa rozgrywka od każdego z nowo dodanych liści aż do końca symulowanej partii i zapamiętanie jej wyniku. Jedynym ograniczeniem takich rozgrywek jest zgodność ruchów z regułami gry (w przypadku go dodatkowo zasada niezapełniania jednopunktowego oka).
• Krok czwarty nazywany jest wsteczną propagacją wyników. Polega on na zaktualizowaniu informacji o liczbie zwycięstw i liczbie odwiedzin we wszystkich węzłach całej ścieżki łączącej liść z korzeniem. Aktualizacja ta sprowadza się do powiększenia o jeden licznika zwycięstw w co drugim węźle ścieżki, a dokładnie - w tych węzłach, w których ruch wykonuje ten gracz, który zwyciężył symulację. Równocześnie dla każdego węzła powiększany jest o jeden licznik jego odwiedzin. Realizacja kroku czwartego jest kluczowa dla sterowania procesem budowania drzewa, bo algorytm selekcji bazuje na liczbie odwiedzin i liczbie zwycięstw gracza, który wykonuje w odpowiadającej węzłowi pozycji ruch.

Gdy algorytm wykona zadaną liczbę iteracji, wówczas na podstawie statystyk węzłów będących bezpośrednimi “dziećmi” korzenia wybiera zagranie, które ostatecznie pojawi się na planszy. Natura sposobu budowania drzewa MCTS jest taka, że najlepiej jest wybrać to zagranie, które najczęściej było wybierane w iteracjach, czyli to, którego ścieżki są najlepiej przebadane.

Istnieje wiele wariantów MCTS odbiegających od opisanego tu kanonu, które odegrały później swoją rolę w rozwoju komputerowego go i Sztucznej Inteligencji. Wymienię tu:

• dodawanie nowych liści do węzłów niebędących liśćmi;
• ekspansja dopiero po pewnej liczbie odwiedzin liścia (a więc pominięcie kroku drugiego, jeśli liść nie był wystarczającą liczbę razy odwiedzony);
• podparcie selekcji wiedzą dziedzinową lub systemami AI;
• użycie w liściach zamiast losowej rozgrywki jakiejś innej heurystyki lub użycie zarówno heurystyki, jak i losowych rozgrywek, a następnie uśrednienie oceny;
• uwzględnianie na etapie selekcji dodatkowej wiedzy zdobytej podczas rozgrywek (która łącznie ze statystykami zwycięstw zapisywana jest podczas propagacji wstecznej).

Algorytm MCTS rozwiązywał naraz kilka problemów. Dostarczał zdecydowanie silniejszej heurystyki dla go niż jakakolwiek, którą wcześniej próbowano stworzyć (jej siła była tym większa, im bliższych korzeniowi sytuacji dotyczyła). MCTS był zdecydowanie lepszy od algorytmu Alpha-Beta, bo żadna gałąź nigdy nie była w ostateczny sposób “odcinana” i komputer mógł powrócić do jej analizowania, gdy inne zagrania zawodziły. Dodajmy, że każda, nawet najlepsza heurystyka jest obarczona jakimś błędem. Algorytm Alpha-Beta propagował ten błąd w kierunku korzenia drzewa – ku ważnym decyzyjnym węzłom. MCTS bazując na statystykach wyników losowych rozgrywek, był bardziej precyzyjny. W dodatku budowane przez niego drzewo było silnie asymetryczne – znacznie dokładniej analizowało warianty złożone z silnych zagrań komputera i silnych kontr jego przeciwnika. MCTS w znakomity sposób trzymał równowagę między poświęcaniem większej liczby przebiegów gałęziom, które zdawały się lepiej rokować, a sprawdzaniem wariantów słabo rozpoznanych. Kolejną jego zaletą była łatwość zarządzania czasem – na przykład można było przyjąć, że na znalezienie każdego ruchu w rozgrywanej z człowiekiem partii komputer wykona ustaloną liczbę iteracji, gdzie czas każdej z nich był z góry znany, albo wręcz nałożyć ograniczenia czasowe w sposób bezpośredni. W innych algorytmach drzewiastych panowanie nad czasem analizy było znacznie trudniejsze – nie wiedziano, jaką liczbę gałęzi jak głęboko trzeba będzie przeanalizować.

Dla algorytmu MCTS charakterystyczne było to, że tworzył on drzewo, które w pobliżu korzenia miało pewną liczbę zdecydowanie rozsądnych ruchów o dużej liczbie odwiedzin, podczas gdy pozostałe, rzadziej odwiedzane, odpowiadały zagraniom słabszym. Precyzja dobieranych kandydatów spadała wprawdzie wraz z dystansem od korzenia, jednak przy wyborze zagrania w partii nie miało to większego znaczenia. MCTS okazał się znacznie silniejszy od wszystkich algorytmów wykorzystywanych wcześniej w komputerowym go.

W 2008 roku stworzony przez zespół francuskich informatyków program MoGo osiągnął na planszy o rozmiarach 9×9 poziom silnych amatorów. Zaraz potem sukces MoGo powtórzył rozprowadzany w darmowej wersji Open Source program Fuego, który na małej planszy wygrał nawet partię z zawodowcem. Obydwa te programy radziły sobie całkiem nieźle również na “pełnowymiarowej” planszy 19x19, zbliżając się do poziomu 4 kyu. Zarówno MoGo, jak i Fuego zmodyfikowały klasyczny algorytm MCTS, wykorzystując tę samą cechę gry w go, na którą w swoim usprawnieniu zwrócił uwagę Brügmann. W tym przypadku miała ona wpływać na sposób budowania drzewa. Zagrania, które często pojawiały się w zwycięskich losowych rozgrywkach, miały większą szansę na dołączenie ich do rozbudowywanego drzewa jako liście. Jeśli zaś już znajdowały się w drzewie, to zwiększała się szansa wybrania ich na etapie selekcji. MoGo w losowych rozgrywkach wykorzystywał bazę maleńkich kształtów (3x3) oraz zwracał uwagę, czy kamień lub łańcuch może być zbity. Fuego miał wbudowane podobne mechanizmy, a dodatkowo rozbudowaną bazę otwarć. Pokazało to, że istnieją usprawnienia MCTS, które choć spowalniają lekko iteracje, jednak na tyle podnoszą ich jakość, że zwiększają siłę gry programu.

W 2011 roku napisany przez Rémiego Couloma program CrazyStone, grając na planszy normalnych rozmiarów (19x19), osiągnął poziom 4-5 dan, a więc zdecydowanie silnego amatora, a dwa lata później pokonał japońskiego gracza zawodowego o sile 9 dan Ishidę Yoshio. Co prawda program dostał od mistrza cztery kamienie handicapów (mniej więcej tyle, co wieża forów w szachach), jednak wynik uznano za przełomowy. Potwierdziło się, że siła CrazyStone to około 5 dan. Warto tu opowiedzieć, czym program Couloma różnił się od innych, też wykorzystujących MCTS. Otóż CrazyStone posługiwał się wytrenowanym przez stosunkowo prosty mechanizm Sztucznej Inteligencji systemem rozpoznawania kształtów, jakie powstają na planszy podczas partii silnych graczy ludzkich. Zarówno w fazie dodawania liści do drzewa, jak i w losowych rozgrywkach, brane były pod uwagę wyłącznie ruchy “podpowiadane” przez ten system. Budowana w ten sposób struktura drzewa bardziej odpowiadała temu, co pojawia się w głowie silnego gracza podczas analizy pozycji, niż budowana w dość przypadkowy sposób struktura powstająca przy klasycznym wariancie MCTS. Podobnie do CrazyStone, i z podobnymi wynikami, grał wówczas japoński program Zen.

Sukces programu Couloma dostarczył inspiracji innym informatykom, którzy zaledwie trzy lata po partii z Ishidą Yoshio mieli dokonać tego, co jeszcze niedawno wydawało się zupełnie niemożliwe. O tym jednak opowiem w dalszym wpisie.

Na koniec dodam tylko, że w niektórych grach logicznych, w przeciwieństwie do go, możliwe było stworzenie silnej heurystyki opartej na wiedzy dziedzinowej. W wielu z nich zaczęto z powodzeniem wykorzystywać warianty MCTS, w których nie używano już losowych rozgrywek idących od liścia do końca symulowanej partii. Można powiedzieć, że brały one z algorytmu MCTS wyłącznie technikę budowania drzewa, bo ta, dla wielu zastosowań okazała się znacznie lepsza od techniki Alpha-Beta.

Rozmaite odmiany MCTS wykroczyły w swych zastosowaniach daleko poza świat gier.