Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:ggp:mcts [2016/05/18 01:28] msl [Ćwiczenia] |
pl:dydaktyka:ggp:mcts [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 3: | Linia 3: | ||
| 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. | 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óbujących, często używanych w przypadku rozumowań probabilistycznych. | + | 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: | Powiązane materiały: | ||
| Linia 26: | Linia 26: | ||
| ==== Ćwiczenia ==== | ==== Ćwiczenia ==== | ||
| - | - bazując na kodzie z poprzednich zajęć proszę zaimplementować gracza ''SampleMCGamer.java'' | + | - proszę przyjrzeć się przykładowej implementacji algorytmu Monte Carlo z pliku ''SampleMonteCarloGamer.java'' |
| - | - metoda maszyny stanowej ''getRandomJointMove'' może okazać się pomocna | + | - proszę przeprowadzić pojedynek między algorytmem Alpha-Beta (lub przynajmniej zwykłym MiniMax) i algorytmem Monte Carlo: |
| - | - proszę dla każdego ruchu zapisać liczbę zwycięstw i ogólną liczbę jego wykonań; średnie wyniki należy liczyć dopiero na koniec, na podstawie tych informacji | + | * na małej grze, np. kółko i krzyżyk |
| - | - proszę przeprowadzić pojedynek między algorytmem Alpha-Beta i algorytmem Monte Carlo: | + | * na dużej grze, np. warcabach normalnych rozmiarów |
| - | - na małej grze, np. kółko i krzyżyk | + | * w obu przypadkach algorytmy powinny dbać o to, żeby nie było timeoutów. |
| - | - 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 ===== | ===== Monte Carlo Tree Search ===== | ||
| Linia 38: | Linia 36: | ||
| 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: | 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}$$ | + | $$UCT = \overline{wynik_i} + c*\sqrt{{n}\over{n_i}$$ |
| gdzie: | gdzie: | ||
| * $\overline{wynik_i}$ to dotychczasowy średni wynik $i$-tej maszyny | * $\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$ to liczba rozegranych gier | ||
| * $n_i$ to liczba gier rozegranych na $i$-tej maszynie | * $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. | 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. | ||
| Linia 51: | Linia 50: | ||
| Algorytm można podzielić na cztery fazy: | 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 (minimalizować nasze - $\sqrt{{2n}\over{n_i+1}} - \overline{wynik_i}$) | + | - 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. |
| - | - rozrost: jeżeli żaden ruch z danego węzła nie był nigdy grany, wybieramy losowy 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 (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 | - symulacja: z węzła wybranego w fazie rozrostu, przeprowadzamy losową symulację Monte Carlo | ||
| - | - propagacja wyników wstecz: po wygranej lub przegranej, odpowiednio aktualizujemy statysyki odpowiednich ruchów | + | - 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 |}} | {{ :pl:dydaktyka:ggp:mcts-fazy.png?700 |}} | ||
| Linia 66: | Linia 66: | ||
| ==== Ćwiczenia ==== | ==== Ćwiczenia ==== | ||
| - | - Proszę zaimplementować gracza ''SampleMCTSGamer.java'' | + | - Bazując na graczu ''SampleMonteCarloGamer.java'', 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? | + | * 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? | ||
