This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:dydaktyka:ggp:game_tree_2 [2019/01/07 13:20] msl |
en:dydaktyka:ggp:game_tree_2 [2019/06/27 15:49] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Monte Carlo Tree Search ====== | ====== Monte Carlo Tree Search ====== | ||
| - | Poniższe laboratorium jest kontynuacją [[en:dydaktyka:ggp:game_tree|laboratorium o klasycznych algorytmach działających na drzewie gry_1]] 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. | + | This class continues topic introduced in [[en:dydaktyka:ggp:game_tree_1|the previous lab]]. This time we will focus on the famous Monte Carlo Tree Search (MCTS). While MiniMax with alpha/beta pruning uses [[https://en.wikipedia.org/wiki/Branch_and_bound|branch and bound]] approach to search the game tree **exhaustively**, some game trees are just too big to be explored, e.g. Go game). |
| - | Algorytm MCTS należy do dużej rodziny algorytmów próbkujących, często używanych w przypadku rozumowań probabilistycznych. | + | MCTS on the other hand is a probabilistic algorithm, only sampling the game tree in the indeterministic manner. |
| - | Powiązane materiały: | + | Related info: |
| - | * [[https://en.wikipedia.org/wiki/Monte_Carlo_tree_search|wyjątkowo dobra strona wikipedii]] | + | * [[https://en.wikipedia.org/wiki/Monte_Carlo_tree_search|surprisingly good wikipedia page]] |
| - | * [[https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/|tutorial, jak zaimplementować MCTS w pythonie]] | + | * [[https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/|tutorial about the python implementation]] |
| - | ===== Algorytm Monte Carlo ===== | + | ===== 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. | + | {{ :pl:dydaktyka:ggp:one-armed-bandit.jpg?300|}} The Monte Carlo algorithms are named after the famous casions, where you can play the 'one-armed bandit' slot machines. The idea is that one has many different slot machines to choose from in the casino and every machine has different unknown winning chance. Problem to solve: having a fixed amount of game tokens, how to find a machine that maximizes profits? |
| + | |||
| + | In games a "slot-machine" is represented by a possible move with unknown impact on the game, and we have to find the best move, having limited amount of computational resources (tokens). The simplest approach would be to choose moves at random and simulate the game (such simulation is called **playout**) until the end. We do it as long as we can, then we check which move had the best wins to playouts ratio. | ||
| <code python> | <code python> | ||
| + | as long as we can: | ||
| + | move = choose_random_move() | ||
| + | score = payout(move) | ||
| + | save_score(move) | ||
| - | dopóki starczy czasu: | + | calculate_average_win_ratio() |
| - | pierwszy_ruch = wybierz_losowy_ruch() | + | choose_move_with_the_best_ratio() |
| - | wynik = losowa_symulacja(pierwszy_ruch) | + | |
| - | zapisz_wynik(pierwszy_ruch) | + | |
| - | + | ||
| - | policz_średnie_wyniki_dla_każdego_ruchu() | + | |
| - | wybierz_ruch_o_największym_średnim_wyniku() | + | |
| </code> | </code> | ||
| - | ==== Ćwiczenia ==== | + | ==== Assignments ==== |
| - | - proszę przyjrzeć się przykładowej implementacji algorytmu Monte Carlo z pliku ''SampleMonteCarloGamer.java'' | + | - check the basic Monte Carlo implementation ''SampleMonteCarloGamer.java'' |
| - | - proszę przeprowadzić pojedynek między algorytmem Alpha-Beta (lub przynajmniej zwykłym MiniMax) i algorytmem Monte Carlo: | + | - run several matches Alpha-Beta vs Monte Carlo: |
| - | * na małej grze, np. kółko i krzyżyk | + | * at some simple game, e.g. tic-tac-toe, |
| - | * na dużej grze, np. warcabach normalnych rozmiarów | + | * at something bigger, e.g. checkers |
| - | * w obu przypadkach algorytmy powinny dbać o to, żeby nie było timeoutów. | + | * make sure that neither of them times out without making a move |
| ===== Monte Carlo Tree Search ===== | ===== 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: | + | Monte Carlo wasn't the smartest approach to the problem - we can be more intelligent than some random sampling. The idea behind a more advanced Monte Carlo Tree Search is to choose moves, according to a simple scoring formula: |
| + | |||
| + | $UCT = \overline{score_i} + c*\sqrt{{n}\over{n_i} $ | ||
| - | $$UCT = \overline{wynik_i} + c*\sqrt{{n}\over{n_i}$$ | + | where: |
| + | * $\overline{score_i} $ the average score of the $i $-th move | ||
| + | * $n $ is total number of playouts | ||
| + | * $n_i $ is number of playouts after choosing the $i $-th move | ||
| + | * $c$ is a constant parameter, from theoretical reasons set traditionally to $\sqrt{2}$ | ||
| - | gdzie: | + | As you see, the UCT assigns high scores to machines that: |
| - | * $\overline{wynik_i}$ to dotychczasowy średni wynik $i$-tej maszyny | + | * have high average score ($\overline{score_i} $ is high) |
| - | * $c$ to parametr odpowiadający za to, jaką część czau algorytm poświęci na eksplorację nieznanych ruchów: | + | * haven't been tried too many times (low $\over{n_i}$). |
| - | * 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. | + | This way we balance both exploration and exploitation of the search space. |
| + | The algorithm is called Tree Search because in essence it explores tree in a intelligent manner --- you can say that it approximates MiniMax by randomized exploration. | ||
| - | 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. | + | The algorithm always starts in the current game state (root of the tree) and consists in four phases: |
| + | - selection: | ||
| + | - if the node has been explored (all possible moves were tried at least once) we use the UCT formula to choose one of them to get another node. We repeat this process until we get a node, that has at least one previously unplayed move. | ||
| + | * :!: **ATTENTION/ACHTUNG/UWAGA** :!: like in the MiniMax algorithm, we assume that we play zero-sum game and our opponent would like to minimize our score. So when selecting his moves we have to be smart enough to either minimize the UCT score, or store the scores in an intelligent manner. | ||
| + | - growth: we choose one of the unplayed moves (some implementation can choose more, e.g. all unplayed moves from the current node) | ||
| + | - simulation: we make a playout starting with the chosen move. Most basic way to implement playout is to do totally random game simulation. | ||
| + | - backprogation: we store results of the playout in the nodes belonging to the tree branch we have explored. | ||
| - | Algorytm można podzielić na cztery fazy: | + | We repeat those phases as long as we can - finally we select a move that had the highest number of playouts - we know it's the best because algorithm favors the most promising moves when sampling. |
| - | - 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 |}} | + | Below you can see illustration of one MCTS cycle. There are two things worth of noting: |
| + | - this is not first cycle of the algorithm, the tree is already expanded; | ||
| + | - gray moves belong to our opponent, so during backpropagation we store our loss as his win. | ||
| - | <WRAP center round important 60%> | + | {{:en:dydaktyka:ggp:mcts-phases.png?700 | https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#/media/File:MCTS_(English)_-_Updated_2017-11-19.svg}} |
| - | 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 ==== | + | ==== Assignments ==== |
| - | - Bazując na graczu ''SampleMonteCarloGamer.java'', proszę zaimplementować gracza ''SampleMCTSGamer.java'' | + | - Based on the ''SampleMonteCarloGamer.java'', implement the ''SampleMCTSGamer.java'' player |
| - | * 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. | + | * MCTS assumes that won games has score 1, not 100 as in the ggp framework. Tie also should be equal 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? | + | - Run several matches ''SampleMCTSGamer.java'' vs ''SampleMonteCarloGamer.java'' at some big game (chess, checkers?). Does any of them have an upper hand? |
| - | - 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? | + | - Repeat experiment with diffrent $c$ values: 0, 1, 2, 5, 42. Which is the most effective? |
| - | - 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? | + | - Modify MCTS by mixing it with the plain Monte Carlo. First run some random playouts (Monte Carlo) for a limited amount of time (e.g. 20% of the total time given for the deliberation). Does it improve results? |
