Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:ggp:mcts [2016/05/18 07:27] msl [Ćwiczenia] |
pl:dydaktyka:ggp:mcts [2016/05/18 09:37] msl [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: | 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+1}$$ | $$UCT = \overline{wynik_i} + c*\sqrt{{n}\over{n_i}$$ |
| |
gdzie: | gdzie: |
* $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. |
| |
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. Powtarzamy to tak długo jak możemy na kolejnych węzłach. | - 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. : $\sqrt{{2n}\over{n_i+1}} + (1 - \overline{wynik_i})$, albo odpowiednio zapisujemy wyniki. | * :!: **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 ruch. | - 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 statystyki 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 |}} |
- Bazując na graczu ''SampleMonteCarloGamer.java'', proszę zaimplementować gracza ''SampleMCTSGamer.java'' | - 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. | * 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, czy widać różnicę między wynikami tych botów? | - 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ę 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? |