To jest stara wersja strony!
Drzewo Gry - Monte Carlo Tree Search
Poniższe laboratorium jest kontynuacją 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 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:
Algorytm Monte Carlo
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.
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()
Ćwiczenia
bazując na kodzie z poprzednich zajęć proszę zaimplementować gracza SampleMCGamer.java
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:
gdzie:
![Math $\overline{wynik_i}$](/lib/exe/fetch.php?media=wiki:latex:/imga4bc874fcb45c9bc8e44f3e4ab02ac0a.png)
to dotychczasowy średni wynik
![Math $i$](/lib/exe/fetch.php?media=wiki:latex:/img77a3b857d53fb44e33b53e4c8b68351a.png)
-tej maszyny
![Math $n$](/lib/exe/fetch.php?media=wiki:latex:/img55a049b8f161ae7cfeb0197d75aff967.png)
to liczba rozegranych gier
![Math $n_i$](/lib/exe/fetch.php?media=wiki:latex:/imgde3e4ddbaf93c2db6b330ad1998cc995.png)
to liczba gier rozegranych na
![Math $i$](/lib/exe/fetch.php?media=wiki:latex:/img77a3b857d53fb44e33b53e4c8b68351a.png)
-tej maszynie
![Math $+ 1$](/lib/exe/fetch.php?media=wiki:latex:/img506b6e62fc2c9ff2f1e3951238b20878.png)
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 ![:!:](/lib/images/smileys/icon_exclaim.gif)
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:
![Math $\sqrt{{2n}\over{n_i+1}} + (1 - \overline{wynik_i})$](/lib/exe/fetch.php?media=wiki:latex:/img7fad2f57983a4a02cfd48393944e2e0e.png)
. 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 statysyki odpowiednich ruchów
Szare kółka (ruchy wroga) minimalizują liczbę naszych zwycięstw.
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?