[[
✎ pl:dydaktyka:ggp:mcts
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== Drzewo Gry - Monte Carlo Tree Search ====== Poniższe laboratorium jest kontynuacją [[pl:dydaktyka:ggp:game_tree|laboratorium o klasycznych algorytmach działających na drzewie gry]] i zakłada zrozumienie przedstawionych na nim treści. W ramach laboratorium zaprezentowany będzie sławny algorytm Monte Carlo Tree Search (MCTS). O ile algorytm MiniMax z cięciami Alpha-Beta reprezentuje podejście [[https://en.wikipedia.org/wiki/Branch_and_bound|branch and bound]] do **wyczerpującego** przeszukiwania drzewa gry, o tyle w przypadku gier o dużym współczynniku rozgałęzienia jest to niemożliwe, np. w przypadku sławnej gry Go. Algorytm MCTS należy do dużej rodziny algorytmów próbkujących, często używanych w przypadku rozumowań probabilistycznych. Powiązane materiały: * [[https://en.wikipedia.org/wiki/Monte_Carlo_tree_search|wyjątkowo dobra strona wikipedii]] * [[https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/|tutorial, jak zaimplementować MCTS w pythonie]] ===== Algorytm Monte Carlo ===== {{ :pl:dydaktyka:ggp:one-armed-bandit.jpg?300|}} Nazwa Monte Carlo pochodzi od sławnych kasyn, w których znaleźć można automaty typu "jednoręki bandyta". W przypadku drzewa gier mamy w danej turze to wyboru kilka ruchów, które mogą (lecz nie muszą) zapewnić nam zwycięstwa. Każdy możliwy ruch możemy potraktować jako automat do gry z nieznanym prawdopodobieństwem wygranej, a wybór ruchu to po prostu wybór automatu, na którym przepuścimy kolejny żeton. Na początku nie wiemy, który automat daje większą szansę na zwycięstwo - dlatego też wybieramy dowolny (losowy) z nich. Następnie zapisujemy wynik z gry i ponawiamy grę losując automat. Robimy to tak długo jak tylko jesteśmy w stanie - cały czas zapisując wyniki gier. Następnie wybieramy ten automat, który dał nam najwięcej zwycięstw. W przełożeniu na język drzewa gry - wykonujemy możliwie dużo losowych symulacji gier i wybieramy ten ruch, który średnio najczęściej doprowadzał do zwycięstwa. <code python> dopóki starczy czasu: pierwszy_ruch = wybierz_losowy_ruch() wynik = losowa_symulacja(pierwszy_ruch) zapisz_wynik(pierwszy_ruch) policz_średnie_wyniki_dla_każdego_ruchu() wybierz_ruch_o_największym_średnim_wyniku() </code> ==== Ćwiczenia ==== - proszę przyjrzeć się przykładowej implementacji algorytmu Monte Carlo z pliku ''SampleMonteCarloGamer.java'' - proszę przeprowadzić pojedynek między algorytmem Alpha-Beta (lub przynajmniej zwykłym MiniMax) i algorytmem Monte Carlo: * na małej grze, np. kółko i krzyżyk * na dużej grze, np. warcabach normalnych rozmiarów * w obu przypadkach algorytmy powinny dbać o to, żeby nie było timeoutów. ===== Monte Carlo Tree Search ===== Bardziej ambitnym rozszerzeniem algorytmu Monte Carlo jest **inteligentne** próbkowanie automatów do gry. Zamiast losowo wybierać automat do gry, faworyzujemy automaty, które sprawowały się najlepiej, tj. z początku gramy zupełnie losowo, z czasem coraz bardziej przekonując się do wybierania automatów, z którymi dotychczas najczęściej wygrywaliśmy. Matematycznie, można to wyrazić za pomocą formuły: $$UCT = \overline{wynik_i} + c*\sqrt{{n}\over{n_i}$$ gdzie: * $\overline{wynik_i}$ to dotychczasowy średni wynik $i$-tej maszyny * $c$ to parametr odpowiadający za to, jaką część czau algorytm poświęci na eksplorację nieznanych ruchów: * domyślna wartość wynikająca z teorii wynosi $\sqrt{2}$ * $n$ to liczba rozegranych gier * $n_i$ to liczba gier rozegranych na $i$-tej maszynie Formuła UCT z jednej strony faworyzuje ruchy, które mają duży średni wynik; z drugiej strony druga część formuły zwraca większe wartości dla ruchów mniej sprawdzonych. W przypadku przeszukiwania drzewa gry podobny problem należy rozwiązać w każdym przeszukiwanym węźle. Dla wszystkich możliwych do wykonania ruchów prowadzimy statystykę liczby zwycięstw i wszystkich symulacji danego ruchu. Z początku ruchy są losowe, później jednak zaczynają faworyzować tę część drzewa gry, która zawiera obiecujące ruchy. Algorytm można podzielić na cztery fazy: - wybór: jeżeli wszystkie możliwe ruchy z przeszukiwanego węzła mają policzone statystyki (każdy już kiedyś był zagrany) używamy formuły UCT, aby wybrać ruch. Jeśli nie, przechodzimy do fazy rozrostu. * :!: **UWAGA** :!: podobnie jak w algorytmie MiniMax zakładamy, że na przemian wykonywane są ruchy nasze i wroga. Jeżeli wróg wykonuje ruch, stara się maksymalizować swoje wyniki (lub minimalizować nasze, co jest tożsame w przypadku gier o sumie zerowej). Zatem, albo modyfikujemy formułę UCT, np. : $(1 - \overline{wynik_i}) + c*\sqrt{{n}\over{n_i}}$, albo odpowiednio zapisujemy wyniki. - rozrost: jeżeli żaden ruch z danego węzła nie był nigdy grany, wybieramy losowy jeszcze niegrany ruch. - symulacja: z węzła wybranego w fazie rozrostu, przeprowadzamy losową symulację Monte Carlo - propagacja wyników wstecz: po wygranej lub przegranej, odpowiednio aktualizujemy statystyki odpowiednich ruchów (nie obejmuje to ruchów wykonanych w ramach symulacji). {{ :pl:dydaktyka:ggp:mcts-fazy.png?700 |}} <WRAP center round important 60%> Szare kółka (ruchy wroga) minimalizują liczbę naszych zwycięstw. </WRAP> Powyższe fazy powtarzają się tak długo, jak jest to możliwe. Na końcu wybieramy ten ruch, który został zasymulowany największą ilość razy. Jego jakość jest zapewniona poprzez fakt, że algorytm z natury skupia przeszukiwanie wokół najlepszych możliwości. ==== Ćwiczenia ==== - Bazując na graczu ''SampleMonteCarloGamer.java'', proszę zaimplementować gracza ''SampleMCTSGamer.java'' * należy zauważyć, że algorytm MCTS zakłada, że nagroda za zwycięstwo wynosi 1, a nie 100. Podobnie remis powinien być traktowany jako 0,5. - Proszę przeprowadzić serię pojedynków ''SampleMCTSGamer.java'' vs ''SampleMonteCarloGamer.java'' w warcaby normalnych rozmiarów lub inną grę o dużej przestrzeni przeszukiwania, czy widać różnicę między wynikami tych botów? - Proszę powtórzyć serię pojedynków, zmieniając stałą eksploracji $c$ na wartości: 0, 1, 2, 5, 42. Która z nich daje najlepsze wyniki? - Proszę zmodyfikować algorytm MCTS tak, żeby przed przejściem do wyboru z użyciem UCT, najpierw zagrał pewną liczbę (np. tyle, ile zdążyć przez 1/5 dozwolonego czasu) czystych symulacji Monte Carlo. Czy poprawia to jakość wyników?
pl/dydaktyka/ggp/mcts.txt
· ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry