2: Od Monte Carlo do Monte Carlo Tree Search

Monte Carlo jest to znana od lat czterdziestych dwudziestego wieku metoda przybliżonego rozwiązywania zagadnień, które przy tradycyjnym podejściu, a więc rekurencyjnym lub iteracyjnym, byłyby ze względu na złożoność problemu nierozwiązywalne w sensownym czasie.

W dużym skrócie polega ona na stosowaniu ogromnych ilości przypadkowych symulacji jakiegoś procesu. Metoda ta nie jest w stanie dostarczyć odpowiedzi ze stuprocentową pewnością, jednak jej dokładność w wielu zastosowaniach jest wystarczająca. Gdy użycie metod analizujących wszystkie przypadki jest ze względu na ograniczenia czasowe niemożliwe, metoda Monte Carlo często pozostaje jedynym wyborem. Znalazła ona liczne zastosowania między innymi w fizyce, meteorologii czy klimatologii. Swoją skuteczność potwierdziła też w rozstrzyganiu klasycznego w teorii przetwarzania informacji Problemu Komiwojażera.
Pomysł na wykorzystanie w programach grających w gry logiczne losowych rozgrywek do oceny wartości ruchu pojawił się w połowie lat osiemdziesiątych. W przypadku gry w go pionierem był Niemiec Bernd Brügmann, który w 1993 napisał program Gobble. Pierwotna idea była bardzo prosta i polegała na rozgrywaniu dla każdego legalnego zagrania w zastanej sytuacji na planszy pewnej dużej liczby równo rozłożonych symulacji partii, w których ruchy byłyby całkowicie przypadkowe. Jedynymi ograniczeniami nakładanymi na takie zagrania miała być ich zgodność z regułami gry oraz zasada niezapełniania jednopunktowego oka. Ta druga reguła była konieczna, by grę dawało się doprowadzić do końca, czyli do dwóch pasów, i uniemożliwić zapętlenia. Przy zastosowaniu chińskich reguł możliwe było policzenie i zapamiętanie wyniku dla każdej rozegranej symulacji gry. Na koniec wybierałoby się zagranie, które miało najlepszą statystykę zwycięstw. Brügmann policzył jednak, że aby uzyskać tą metodą ruch, który przeważnie byłby właściwym zagraniem, należałoby przeprowadzać setki tysięcy symulacji. Były to jednak czasy 16 bitowych komputerów i bardzo słabych procesorów, a więc, nawet przy założeniu, że partia rozgrywana by była na małej planszy (9x9 skrzyżowań, a nie 19x19), komputer musiałby poświęcić na wykonanie każdego zagrania kilka dni. To oczywiście nie wchodziło w rachubę. Brügmann wykorzystał więc pewną cechę go, polegającą na tym, że jeśli jakieś zagranie okazuje się dobre w wielu sekwencjach w dalszym etapie partii, to często należy je zagrać już wcześniej. Program zapisywał statystyki dla zagrań wykonanych w każdej symulacji w dwóch tablicach. Rozmiarem tablice odpowiadały wielkości planszy. Pierwsza tablica dla każdego miejsca na planszy przechowywała uśredniony wynik losowych rozgrywek, w których komputer w pewnym momencie partii wykonał w tym miejscu ruch. Druga tablica –analogicznie, dla miejsc, gdzie w symulacjach zagrał przeciwnik, średni wynik obliczony z jego perspektywy. Algorytm pierwszą symulację przeprowadzał, zaczynając ją w przypadkowym miejscu na planszy, jednak rozpoczynając kolejne losowe rozgrywki, korzystał ze swojej tablicy i większe prawdopodobieństwo przyznawał wybraniu jako pierwszego któregoś z zagrań o najlepszej statystyce. Również przebieg symulacji opierał się na analogicznej zasadzie - tak komputer, jak i jego przeciwnik, z możliwych do wykonania zagrań preferowali te, które w ich tablicach miały lepsze uśrednione wyniki. Ostatecznie, po wykonaniu około tysiąca symulacji program wybierał to zagranie, które miało najlepsze statystyki, gdy było wybierane jako pierwsze. Program Brügmanna grał jednak słabo. Wyraźnie gorzej od większości znanych wtedy “tradycyjnych” programów. Testy programu Gobble przeprowadzane były na małej planszy 9x9 skrzyżowań i autor ocenił, że program ma tam siłę około 25 kyu, czyli osoby zupełnie początkującej. Możemy powiedzieć niemal z całkowitą pewnością, że na planszy 19x19 siła ta byłaby jeszcze niższa.
Idea użycia metody Monte Carlo w komputerowym go została jednak podchwycona przez innych. Pojawiły się pomysły wykorzystania formuły decyzyjnej UCB, czyli matematycznego wzoru, który szuka równowagi między sprawdzaniem nowych, niezbadanych ścieżek, a dokładniejszą eksploatacją tych, które zdają się przynosić lepsze wyniki. Przykładowo, mogłoby to wyglądać tak: wykonałem 30 symulacji, zaczynając od jakiegoś ruchu i 20 z nich zakończyło się zwycięstwem. Dla innego wykonałem 25 symulacji i uzyskałem 15 zwycięstw. Pozostałe zagrania sprawdzałem tylko po 5 razy i uzyskiwałem w nich od zera do dwóch zwycięstw. Czy powinienem teraz nadal sprawdzać ten najlepszy wariant, czy może któryś inny? Jeśli inny, to który dokładnie? Oczywiste bowiem było, że zagraniom dającym lepszą statystykę należy poświęcić więcej czasu analizy, bo prawdopodobieństwo, że to któreś z nich jest prawidłowym ruchem, jest duże. Nie warto jednak gubić szans na analizę zagrań, których wyniki przy małej liczbie iteracji nie wyglądają zachęcająco. Na początku XXI wieku moc komputerów wzrosła już na tyle, że można się było pokusić o stosowanie coraz to lepszych algorytmów wykorzystujących metodę Monte Carlo.
Przełomowy był rok 2006, kiedy to częściowo niezależnie, częściowo wspierając się na swoich pracach, tacy informatycy jak Levente Kocsis, Csaba Szepesvári, Sylvain Gelly i Rémi Coulom opracowali to, co dziś nazywamy algorytmem Monte Carlo Tree Search, albo w skrócie MCTS. Idea polegała na sprytnym połączeniu tego, co dawały tradycyjne algorytmy bazujące na drzewie przeszukiwań, i jednoczesnym oparciu heurystyki na losowych rozgrywkach. Bardziej szczegółowo opiszę MCTS za tydzień. O tym, jak przełomowy był to pomysł, niech świadczy fakt, że od początku 2007 roku wszystkie liczące się programy grające w go bazują właśnie na tym algorytmie. Nie inaczej było w przypadku AlphaGo i jego następców. MCTS odegrał kluczową rolę nie tylko w działaniu tych programów, decydując o ich sile w trakcie rozgrywanych partii, ale także na etapie trenowania sieci neuronowych. O tym opowiem jednak dalej.

Na zakończenie wprowadzę kilka terminów związanych z analizą drzewiastą, których będę używał w następnym wpisie – w całości poświęconym MCTS. Drzewo jest to struktura złożona z korzenia, węzłów i liści połączonych krawędziami. Korzeń, każdy węzeł i każdy liść reprezentują jakąś sytuację w grze, która jest przez komputer analizowana przed dokonaniem wyboru zagrania. Korzeń odpowiada bieżącej sytuacji na planszy, w której ruch ma wykonać komputer. Krawędzie reprezentują zagrania. Każda krawędź prowadzi od jakiegoś węzła do innego i symbolizuje wybór określonego zagrania dostępnego w sytuacji reprezentowanej przez węzeł wcześniejszy (bliższy korzenia). Taki “wcześniejszy węzeł” nazywamy “ojcem” tego, do którego prowadzi. Tamten z kolei odpowiada sytuacji po wykonaniu ruchu i jest nazywany “dzieckiem”. Ciąg, na który składają się: korzeń, jedno z jego dzieci, dziecko tego dziecka i tak dalej, nazywany bywa gałęzią lub ścieżką. Liściem nazywamy węzeł, który nie posiada dzieci. Drzewa buduje się po to, by komputer mógł przeanalizować sytuację podczas rozgrywki i wykonać najlepsze znalezione zagranie. Po wprowadzeniu do komputera zagrania przeciwnika algorytm rozbudowuje drzewo. Na podstawie tak przeprowadzonej analizy wybiera najbardziej obiecującą odpowiedź i wykonuje ruch. Budowa drzewa może się odbywać w sposób rekurencyjny – na przykład można zacząć od dodania pod korzeniem węzłów odpowiadających wszystkim sytuacjom, do jakich doprowadzą wszystkie legalne zagrania w danej pozycji. Następnie kolejno dla każdego z tamtych węzłów dodać wszystkie ich dzieci. I tak dalej. Można też zacząć od stworzenia pojedynczej, długiej gałęzi. Prowadziłaby ona od korzenia do liścia położonego tak głęboko, jak głęboką analizę chcemy przeprowadzać. W tym liściu dokonywalibyśmy heurystycznej oceny sytuacji. Specyficzną technikę budowy drzewa przyniósł ze sobą algorytm MCTS. Opowiem o tym w następnym wpisie.