Differences

This shows you the differences between two versions of the page.

Link to this comparison view

en:dydaktyka:ggp:game_tree_2 [2019/01/07 12:20]
msl created
en:dydaktyka:ggp:game_tree_2 [2019/01/08 23:19] (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]] i zakłada zrozumienie przedstawionych na nim treściW 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 gryo tyle w przypadku gier o dużym współczynniku rozgałęzienia jest to niemożliwenpw 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 explorede.g. Go game).
  
-Algorytm ​MCTS należy do dużej rodziny algorytmów próbkującychczęsto używanych w przypadku rozumowań probabilistycznych.+MCTS on the other hand is a probabilistic algorithmonly 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 kasynw 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ęstwaKaż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 automatuna 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 ​(losowyz nich. Następnie zapisujemy wynik z gry i ponawiamy grę losując automatRobimy ​to tak długo jak tylko jesteśmy w stanie - cały czas zapisując wyniki gierNastępnie wybieramy ten automatktó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 casionswhere you can play the '​one-armed bandit'​ slot machinesThe idea is that one has many different slot machines ​to choose from in the casino and every machine has different unknown winning chanceProblem to solve: having a fixed amount of game tokenshow to find 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 movehaving 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 endWe do it as long as we canthen 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 grzenpkółko i krzyżyk +    * at some simple gamee.g. tic-tac-toe,​ 
-    * na dużej grzenpwarcabach normalnych rozmiarów +    * at something biggere.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 gryZamiast losowo wybierać automat do gryfaworyzujemy 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 samplingThe idea behind a more advanced Monte Carlo Tree Search is to choose movesaccording ​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ł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 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ęźleDla wszystkich możliwych do wykonania ruchów prowadzimy statystykę liczby zwycięstw i wszystkich symulacji danego ruchuZ początku ruchy są losowepóźniej jednak zaczynają faworyzować tę część drzewa gryktó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 nodeWe repeat this process until we get a node, that has at least one previously unplayed move 
 +    * :!: **ATTENTION/​ACHTUNG/​UWAGA** :!: like in the MiniMax algorithmwe 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 scoreor 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 ​move that had the highest number of playouts - we know it'the best because algorithm favors the most promising moves when sampling.
-  ​wybór: jeżeli wszystkie możliwe ruchy z przeszukiwanego węzł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 wrogaminimalizują 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 frameworkTie 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 przeszukiwaniaczy widać różnicę między wynikami tych botów+  - Run several matches ​''​SampleMCTSGamer.java''​ vs ''​SampleMonteCarloGamer.java'' ​at some big game (chesscheckers?). 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?
en/dydaktyka/ggp/game_tree_2.1546863604.txt.gz · Last modified: 2019/01/07 12:20 by msl
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0