|
|
pl:dydaktyka:ggp:mcts [2016/05/18 01:41] msl [Monte Carlo Tree Search] |
pl:dydaktyka:ggp:mcts [2019/06/27 15:50] |
====== 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 ==== | |
| |
- bazując na kodzie z poprzednich zajęć proszę zaimplementować gracza ''SampleMCGamer.java'' | |
* metoda maszyny stanowej ''getRandomJointMove'' może okazać się pomocna | |
* średni wynik powinien zostać wyliczony poprzez formułę: ${z_i + 0.5*r_i}\over{n_i}$, gdzie $z_i$ to liczba zwycięstw przy $i$-tym ruchu, $r_i$ to liczba remisów, a $n_i$ to liczba wszystkich symulacji z wykonaniem $i$-tego ruchu | |
- proszę przeprowadzić pojedynek między algorytmem Alpha-Beta 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} + \sqrt{{2n}\over{n_i+1}$$ | |
| |
gdzie: | |
* $\overline{wynik_i}$ to dotychczasowy średni wynik $i$-tej maszyny | |
* $n$ to liczba rozegranych gier | |
* $n_i$ to liczba gier rozegranych na $i$-tej maszynie | |
* $+ 1$ dodane jest tylko po to, żeby uniknąć dzielenia przez zero | |
| |
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 chociaż jeden możliwy ruch z przeszukiwanego węzła ma policzone statystyki (już kiedyś był zagrany) używamy formuły UCT, aby wybrać ruch. :!: **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: $\sqrt{{2n}\over{n_i+1}} + (1 - \overline{wynik_i})$. Powtarzamy to tak długo jak możemy. | |
- rozrost: jeżeli żaden ruch z danego węzła nie był nigdy grany, wybieramy losowy 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 | |
| |
{{ :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 ==== | |
| |
- Proszę zaimplementować gracza ''SampleMCTSGamer.java'' | |
- Proszę przeprowadzić serię pojedynków ''SampleMCTSGamer.java'' vs ''SampleMCGamer.java'' w warcaby normalnych rozmiarów, czy widać różnicę między wynikami tych botów? | |