# Sprawozdanie ze Sztucznej Inteligencji ### Autorzy Jakub Fedorowicz Maciej Zakrzewski ## Wstęp Celem naszego projektu jest zaimplementowanie algorytmu uczenia ze wzmocnieniem - Q‑learningu w wariancie Deep Q-Learning do gry komputerowej. Na potrzeby projektu stworzony został prosty symulator gry w piłkę nożną w środowisku języka Python, klon gry Haxball (oryginał dostępny pod adresem https://www.haxball.com/). Do realizacji projektu została wykorzystana biblioteka TensorFlow wraz z modułem Keras. Mogliśmy nasze zadanie uprościć i sprowadzić do bardzo prostego problemu rozwiązywanego przy pomocy q-learningu, ale postawiliśmy poprzeczkę wyżej i stworzyć możliwie najlepszą sztuczną inteligencję, działającą na możliwie najbardziej złożonym problemie (bazującej na największej liczbie stanów i decyzji). ## Reinforcement learning Uczenie ze wzmocnieniem (ang. reinforcement learning) jest uznawane za jeden z trzech głównych, obok uczenia nadzorowanego i nienadzorowanego, paradygmatów uczenia maszynowego. Głównym celem tego podejścia jest wybór optymalnych decyzji, zależnie od aktualnego stanu środowiska. Najważniejszą cechą uczenia ze wzmocnieniem, jest brak danych wejściowych, z których wyciągane byłyby wnioski (jak w przypadku uczenia nadzorowanego i nienadzorowanego). Jedyna informacja, na której opiera się proces uczenia, to wartość *wzmocnienia* która rośnie przy podjemowaniu dobrych decyzji, a maleje przy podejmowaniu złych. Dobre efekty uzyskiwane przy pomocy algorytmów uczenia ze wzmocnieniem wymagają odpowiedniego balasnu między eksploracją a eksploatacją. Równomierny rozkład prawdopodobieństwa stanów i podejmowanych decyzji, pozwala w odpowiednio długiej perspektywie odkryć najkorzystniejszą strategię. Do tego celu zdefiniowana jest zmienna epsilon w zakresie <0,1&gt;, która określa prawdopodobieństwo na podjęcie losowej decyzji. Wartość 0 dla epsilonu oznacza więc stuprocentowe prawdopodobieństwo wykorzystania nauczonej do tej pory taktyki podczas podejmowania decyzji. Istnieje bardzo wiele algorytmów uczenia ze wzmocnieniem, wykorzystujących różne techniki i podejścia. Opiszemy szczegółowo te, które związane są z naszym projektem. ## Q-learning ### Opis ogólny Q-learning to jeden z najbardziej podstawowych algorytmów uczenia ze wzmocnieniem. Jedną z jego większych zalet jest brak sieci neuronowej, co czyni go jednym z łatwiejszych w implementacji. Jego oczywistą wadą jest ograniczoność. Algorytm przyzwoicie radzi sobie z bardzo prostymi problemami złożonymi z małej liczby stanów, ale przy trudniejszych zaczyna mieć problemy z odnalezieniem najlepszej strategii. Oczywistą wadą q-learningu jest też złożoność pamięciowa. Wraz te wzrostem liczby stanów, bardzo szybko zaczyna rosnąć rozmiar q-table, która jest potrzebna to oceny podejmowanych decyzji. Ta wada czyni ten algorytm praktycznie bezużytecznym dla bardziej złożonych problemów. Potencjalnym rozwiązaniem jest ograniczanie liczby stanów, co jest jednak związane ze spadkiem jakości podejmowanych decyzji. ### Szczegóły działania #### Q-Table Jest to tablica o rozmiarze S×A gdzie S to rozmiar przestrzeni możliwych stanów a A to rozmiar przestrzeni możliwych do podjęcia decyzji. Komórka *Q(s,a)* zawiera wartość *Q* dla wykonania akcji *a* w stanie *s*. Tabela ta jest wypełniana w procesie uczenia, a wartości Q zapisane w komórkach są wykorzystywane do podejmowania decyzji. Każda wartość Q w tabeli to inaczej maksymalna oczekiwana nagroda, jaką otrzyma się w przyszłości, jeśli wykona się daną akcję w danym stanie. Dla stanu S, za najkorzystniejszą, uznawana jest więc decyzja z największą wartością Q. W przypadku gdy przestrzeń stanów lub decyzji jest nieskończona, należy przeprowadzić jej dyskretyzację do skończonych rozmiarów (podział przestrzeni na przedziały i uznanie każdego z przedziałów za jeden stan/akcję). #### Parametry wzoru Nowa wartość Q dana jest wzorem: $Q_{t}(s,a)=Q_{t-1}(s,a)+\alpha(R(s,a)+\gamma \max_{a'}Q(s',a')-Q_{t-1}(s,a))$ * Nowa wartość *Q* dla danego stanu i akcji - $Q_{t}\left(s,a\right)$ * Poprzednia wartość *Q* dla danego stanu i akcji - $Q_{t-1}\left(s,a\right)$ * Maksymalna wartość *Q* możliwa do uzyskania po wykonaniu akcji *a* w stanie *s* - $max_{a'}Q\left(s',a'\right)$ * Wartość *R* (nagrody) za wykonanie akcji *a* w stanie *s* - $R\left(s,a\right)$** Modyfikowalne parametry których zmiana wpływa na jakość i sposób uczenia. * **Learning rate ($\alpha$)** - wartość rozmiaru kroku, określająca, w jakim stopniu nowo zdobyte informacje zastąpią poprzednio zebrane. Wartość 0 będzie oznaczała brak jakiejkolwiek nauki, a wartość 1 będzie w 100% nadpisywała poprzednie doświadczenia, niejako koncentrując algorytm na najnowszych doświadczeniach. Zazwyczaj learning rate jest wartością stałą dla całego algorytmu. * **Discount factor ($\gamma$)** - parametr określający istotność przyszłych nagród. Dla wartości 0 algorytm będzie brał pod uwagę tylko bieżące nagrody i podejmował decyzje prowadzące do natychmiastowego ich zwiększenia. Dla wartości zbliżających się do 1 algorytm będzie dążyć do maksymalizowania nagrody w przyszłości. Zbyt duża wartość discount może prowadzić do propagacji błędów. Wartość większa lub równa 1 z dużym prawdopodobieńswem uniemożliwi zbieganie się wartości Q. #### Przebieg uczenia Proces uczenia przy użyciu algorytmu q-learning może przebiegać następująco: * dla ustalonej wcześniej liczby pokoleń symulowany jest ich przebieg, * dla każdej akcji w pokoleniu podejmowana jest decyzja (losowa lub na bazie tabeli Q — zależnie od wartości epsilon), * po podjęciu decyzji, korzystając ze zdobytego doświadczenia, aktualizowana jest wartość Q według podanego w poprzednim punkcie wzoru. Przebieg procesu uczenia jest przedstawiony przy użyciu poniższego pseudokodu: ```c= Zainicjalizuj tabelę Q(s,a) Dla każdego pokolenia: Zainicjalizuj nowe środowisko (np. grę) Dla każdego kroku w pokoleniu: W zależności od stanu s i wartości epsilon, wybierz akcję a Pobierz kolejny stan s' i nagrodę r na bazie akcji a Zaaktualizuj tabelę komórkę Q(s,a) wykorzystując wzór podany wyżej s <- s' ``` #### Podejmowanie decyzji Aby podjąć decyzję dla stanu s na bazie tabeli Q, należy sprawdzić cały rząd s i wybrać kolumnę z maksymalną wartością. Rząd s ma wartości dla każdej z możliwych do podjęcia decyzji. W procesie uczenia wartości te uzupełniane są zależnie od ich opłacalności. Większa wartość będzie oznaczać korzystniejszą decyzję. ## Sieci neuronowe ### Opis ogólny Przed wprowadzeniem algorytmu Deep Q-learning, warto omówić pojęcie sztucznych sieci neuronowych. Są one podstawą dla dalszych podpunktów omawianych w tym sprawozdaniu. **Sztuczna sieć neuronowa** to system obliczeniowy, którego koncepcja jest oparta na działaniu biologicznych mózgów. Systemy te przetwarzają dowolnej wielkości zbiór parametrów wejściowych na dowolnej wielkości zbiór parametrów wyjściowych. Sieć neuronowa składa się z **neuronów** ułożonych w **warstwy**. Każda sieć posiada przynajmniej dwie warstwy — warstwę wejściową i wyjściową. Ich rozmiary są takie same jak rozmiary zbiorów parametrów. Warstwy pomiędzy warstwą wejściową i wyjściową są nazywane warstwami ukrytymi (hidden layers). Mogą one mieć dowolne rozmiary i może ich być dowolna ilość (może też nie być ich wcale). Sieć zawierającą warstwy ukryte nazywamy siecią głęboką (deep neural network). Każdy neuron jednej warstwy jest połączony z każdym neuronem warstwy następnej. ![](https://i.imgur.com/az0GwV9.png) > Źródło: https://medium.com/@jamesdacombe/an-introduction-to-artificial-neural-networks-with-example-ad459bb6941b </br> Sztuczne neurony : Mają one symulować biologiczne neurony znajdujące się w mózgu. Neuron przyjmuje ważoną sumę danych wejściowych, na podstawie której określa swój stan wewnętrzny (aktywację) za pomocą funkcji aktywacji i produkuje dane wyjściowe. </br> Połączenia i wagi : Sieć składa się z połączeń, każde połączenie jest jednocześnie wyjściem jednego neuronu i wejściem drugiego. Neurony mogą mieć wiele wejść i wyjść. Do każdego połączenia przypisana jest waga. W procesie uczenia to właśnie wartości tych wag są dostosowywane, aby uzyskiwać oczekiwane dane na warstwie wyjściowej. Gdy za pomocą połączenia przekazujemy wartość aktywacji neuronu z warstwy n do neuronu w warstwie n+1, wartość ta jest mnożona przez wagę odpowiadającą połączeniu między tymi neuronami. Aktywację neuronu z warstwy innej niż wejściowa określa więc suma ważona **y** przekazana dalej do funkcji aktywacji: $y = \sum(waga * otrzymana\_wartość) + przesunięcie$ </br> Warstwa : Neurony są zorganizowane w warstwy. Neurony jednej warstwy są połączone jedynie z neuronami warstwy następującej po niej według dowolnego wzorca (w przypadku połączenia pełnego są połączone z każdym neuronem warstwy kolejnej). Warstwa otrzymująca dane zewnętrzne to warstwa wejściowa a warstwa produkująca ostateczny wynik to warstwa wyjściowa. Każda warstwa posiada swoją liczbę neuronów oraz wspólną dla każdego neuronu funkcję aktywacji. </br> Funkcja aktywacyjna : Przypisana do każdej warstwy funkcja, do której wprowadzana jest ważona suma danych wejściowych przesunięta o stałą wartość. Wynik funkcji aktywacji określa aktywację neuronu, czyli jego wewnętrzny stan. Funkcja aktywacji określa sposób, w jaki zmiana danych wejściowych wpływa na stan neuronu. Może też ograniczyć wartości aktywacji do sztywnego przedziału (np. dziedzinę liczb rzeczywistych do przedziału (-1;1). Przykładowa funkcja aktywacyjna to funkcja sigmoid określona wzorem $S(x) = \frac{1}{1 + e^{-x}}$ ![](https://upload.wikimedia.org/wikipedia/commons/thumb/8/88/Logistic-curve.svg/1280px-Logistic-curve.svg.png) > Źródło: https://en.wikipedia.org/wiki/Sigmoid_function ### Proces uczenia Proces uczenia polega na takim dostosowywaniu wag połączeń między neuronami, aby zminimalizować wynik funkcji kosztu, która określa, jak bardzo wartości oczekiwane odbiegają od wartości wyjściowych sieci. W procesie uczenia wykorzystuje się m.in. metodę gradientu prostego. Do wyjaśnienia procesu uczenia wykorzystamy prosty model sieci neuronowej składający się z warstwy wejściowej o rozmiarze $n$ i warstwy wyjściowej zawierającej jeden neuron. Zakładając, że model sieci wykorzystuje funkcję aktywacyją ReLU, można określić przykładową funkcję kosztu, wykorzystując średni błąd kwadratowy: $C(X, Y, w, b) = \frac{1}{N}\displaystyle\sum_{i=1}^{N}(Y_i - ReLU(X_i))^2$ Po podstawieniu funkcji aktywacyjnej: $C(X, Y, w, b) = \frac{1}{N}\displaystyle\sum_{i=1}^{N}(Y_i - max(0, w \cdot X_i + b))^2$ gdzie: $N$ - ilość zestawów danych do treningu $X$ - wektor zestawów danych wejściowych, $Y$ - wektor wyników docelowych, $w = [w_1, w_2, ...,w_n]$ - wektor wag przypisanych do połączeń, $b$ - przesunięcie na neuronie wyjściowym. W tym przypadku naszą funkcją kosztu jest więc średni błąd kwadratowy między wartościami zwróconymi przez nasz model sieci a wartościami oczekiwanymi. Sieć będzie dążyć do zminimalizowania tego błędu. Dla zestawów danych wejściowych $X$ i wyników docelowych $Y$ funkcja kosztu zależy więc od tylko od wektorów wag $w$ i przesunięć $b$. Uczenie sieci polega na znalezieniu minimum funkcji kosztu w zależności od wag i przesunięć. Do określenia zmian, jakich należy dokonać w wartościach wag i przesunięć, aby zbliżyć się do minimum można użyć metody gradientu prostego, która wykorzystuje **gradient** funkcji kosztu, czyli wektor pochodnych cząstkowych po wszystkich zmiennych (w tym przypadku zmiennymi są wagi i przesunięcia). Wektor ten wskazuje kierunek, w jakim należy wykonać krok, aby wartość funkcji wzrosła najbardziej. W celu minimalizacji funkcji kosztu należy wykonać krok w kierunku przeciwnym, czyli tym wskazywanym przez **antygradient**. W przypadku sieci o większych rozmiarach warstw i ich ilości równanie przybiera bardziej skomplikowaną postać. Do wyznaczenia zależności funkcji kosztu od wszystkich wag i przesunięć używa się wtedy **propagacji wstecznej**. Wartości aktywacji neuronów ostatniej warstwy zależą od aktywacji połączonych z nimi neuronami warstwy poprzedniej, wag przypisanych do tych połączeń oraz przesunięć. Natomiast wartości aktywacji warstwy poprzedniej zależą analogicznie od aktywacji, wag i przesunięć związanych z warstwą poprzedzającą ją. W ten sposób dochodzimy do warstwy wejściowej, której poszczególne aktywacje na neuronach zależą już tylko od stałych w czasie jednego kroku uczenia danych wejściowych i przesunięcia. Można w ten sposób opisać zależność wartości funkcji kosztu od wartości wszystkich wag i przesunięć znajdujących się w sieci. Z kolei zależność ta pozwala nam na wyznaczenie gradientu oraz odpowiednie dostosowanie wag i przesunięć. ## Deep Q-learning ### Opis ogólny Przedstawiając wartości Q-table jako funkcję $Q(s)$ zwracającą wartości Q dla możliwych akcji w danym stanie możemy wykonać jej aproksymację. Umożliwia to określenie wartości Q nawet dla stanów z przestrzeni ciągłych. W Deep Q-learning używana jest sieć neuronowa do aproksymacji funkcji wartości Q. Użycie funkcji Q zamiast tabeli likwiduje problem złożoności pamięciowej, dzięki czemu algorytm może być użyty do bardziej złożonych problemów o nieograniczonej przestrzeni stanów. Stworzenie skutecznego modelu do aproksymacji funkcji Q jest, co oczywiste, znacznie trudniejsze niż implementacja klasycznego Q-learningu, ale posiada wiele zalet i pozwala na osiągnięcie rezultatów niemożliwych do uzyskania przy użyciu zwykłej tabeli. ### Szczegóły działania Model sieci neuronowej użyty do zaimplementowania Deep Q-learning będzie aproksymował funkcję wartości Q zdefiniowaną jako: $Q(s) = [{Q_{val}}_{s, a_0},{Q_{val}}_{s,a_1}, ..., {Q_{val}}_{s, a_n}]$ gdzie: : $s$ - dany stan, ${Q_{val}}_{s, a_i}$ - wartość $Q$ dla akcji $a_i$ w stanie $s$, $n$ - rozmiar przestrzeni akcji. Parametrem wejściowym sieci jest stan $s$ a wyjściem wartości $Q$ dla kolejnych możliwych akcji w stanie $s$. Przybliżanie funkcji $Q(s)$ jest problemem regresji, wartości docelowe nie są jednak z góry określone i zmieniają się w trakcie działania algorytmu. Możemy zdefiniować wartość docelową $Q$ w stanie $s$ jako: $target = R(s,a) + γ\max_{a'}Q(s',a')$ gdzie: $R(s, a)$ - nagroda za wykonanie akcji $a$ w stanie $s$, $s'$ - stan następujący po wykonaniu akcji $a$ w stanie $s$, $max_{a'}Q(s',a')$ - największa wartość $Q$ dla aktualnie najlepszej akcji $a'$ w stanie $s'$ ```c= Start z Q(s,a) = Q_0 dla każdego s,a Pobierz stan początkowy s ze środowiska Powtarzaj aż do zbieżności: Wykonaj akcję a w stanie s i pobierz stan s' (Na podstawie Q(s,a) lub losowo w zależności od ε) Jeśli stan s' jest terminalny: target = R(s,a) (Nagroda jest minimalna lub maksymalna w stanie terminalnym) Pobierz nowy stan początkowy s ze środowiska W przeciwnym wypadku: target = R(s,a) + γ*max(Q(s',a')) Przeprowadź uczenie dla stanu wejściowego s i docelowej wartości target ``` #### Przebieg uczenia Uczenie sieci następuje po każdym kroku wykonanym w środowisku. Do nauki wykorzystuje się ostatni stan i akcję wraz z obliczoną wartością docelową Q lub zestaw ostatnich ostatnich stanów o określonym rozmiarze. W wariancie DQN z powtórką doświadczeń do nauki wykorzystuje się losowo pobrany z pamięci agenta zestaw próbek o określonym wcześniej rozmiarze (tzw. batch) #### Powtórka doświadczeń Rozwiązanie to wprowadza do agenta pamięć. Po każdej akcji podjętej w środowisku agent zapisuje w pamięci wszystkie związane z tą akcją dane. Są to: * stan przed podjęciem akcji * podjęta akcja (indeks) * stan po podjęciu akcji * nagroda za znalezienie się w stanie następującym po akcji * informacja czy stan uzyskany był stanem terminalnym Po każdej podjętej decyzji następuje procesu uczenia. Z całego zbioru zapisanych próbek, losowany jest wtedy pozdbiór o rozmiarze określonym parametrem *batch_size*. Sieć jest uczona na bazie wylosowanego podzbioru, a następnie kontynuowany jest proces zbierania danych. Dane zbierane są do bufora o dowolnym rozmiarze. W przypadku ograniczonego bufora po jego przepełnieniu najstarsze dane będną nadpisywane nowymi. Zastosowanie powtórki doświadczeń zapewnia bardziej stabliny trening i uniezależnienie od siebie danych, co prowadzi do lepszej generalizacji rozwiązania. #### Target network W czasie procesu uczenia docelowe wartości funkcji $Q$ nieustannie się zmieniają, przez co często występuje problem ze zbieganiem się wartości $Q$ zwracanych przez sieć uczącą się. Aby zniwelować ten efekt, można wprowadzić do agenta DQN drugą, początkowo identyczną, sieć (tzw. target network), która będzie używana jedynie do ewaluacji fragmentu równania $max_{a'}Q(s',a')$. Target network może być synchronizowana z podstawową siecią agenta co określoną liczbę uczeń. Pomiędzy synchronizacjami wartości docelowe sieci podstawowej są stałe w czasie. Pozwala to uzyskać bardziej stabilny proces uczenia bardziej przypominający uczenie nadzorowane. #### Podejmowanie decyzji Decyzje podejmowane są analogicznie do podstawowego algorytmu Q-learning. Na wejście sieci podawany jest stan $s$, na wyjściu otrzymujemy wartości $Q$ dla kolejnych możliwych akcji. Następnie wybieramy akcję o indeksie takim jak najwyższa wartość $Q$ w zwracanym przez sieć wektorze. ## Double Deep Q-learning ### Opis ogólny W celu aproksymacji rzeczywistej wartości $Q$ dla stanu $s$ algorytm Q-learning bierze największą wartość $\max_{a'}Q(s',a')$. To podejście okazuje się nieoptymalne i może czasem prowadzić do przeszacowania wartości $Q$. Aby usprawnić algorytm Deep Q-learning i wyeliminować problem przeszacowania, można wykorzystać algortym Double Deep Q-learning, który wykorzystuje do działania wymienione wcześniej rozwiązanie 'Target network'. ### Szczegóły działania Double Deep Q-learning w pierwotnej postaci wykorzystywał dwie niezależne sieci neuronowe, które wzajemnie się aktualizowały. ![](https://i.imgur.com/XM8srdg.png) >Pseudo-code Source: “Double Q-learning” (Hasselt, 2010) </br> Pięć lat później, ten sam autor opublikował zaktualizowaną wersję DDQN, która korzysta z jednego modelu, aktualizowanego z pewnym określonym opóźnieniem. ![](https://i.imgur.com/Fm684vb.png) >Pseudo-code Source: “Deep Reinforcement Learning with Double Q-learning” (Hasselt, 2015) </br> W drugim wariancie (wykorzystanym także w naszym projekcie) mamy model główy $Q_{\theta}$ i jego kopię $Q_{\theta'}$. Model główny jest uczony na bieżąco, ale decyzje są podejmowane na jego kopii. Kopia modelu musi być regularnie aktualizowana. Aktualizację można przeprowadzić, kopiując wszystkie współczynniki co określoną ilość kroków, lub przy użyciu podanego wzoru: $\theta' \leftarrow \tau\theta + (1 - \tau)\theta'$ Zaprezentowane wyżej podejście daje znacznie lepsze wyniki dla wielu przykładów zaprezentowanych we wspomnianej pracy naukowej. ![](https://i.imgur.com/txqsxQm.png) ## Implementacja ### Cel projektu Celem naszego projektu było nauczyć agenta optymalnej taktyki do gry Haxball. ### Kod źródłowy Cały nasz projekt dostępny jest po linkiem: https://github.com/Qubaef/HaxballAI ### Opis środowiska Środowisko do uczenia zostało zaimplementowane na potrzeby projektu w języku python, wykorzystująć prostą bibliotekę pygame. Mechanika ruchu została oparta o wektory prędkości i położenia, co okazało się dodatkowym wyzwaniem w procesie ucznia. Samo boisko może przybierać dowolne rozmiary i było wielokrotnie modyfikiowane podczas procesu uczenia (na mniejszym boisku znacznie częściej gracze będą znajdowali się w podobnych stanach, a więc proces uczenia będzie przebiegał szybciej). Środowisko podczas procesu zbierania danych i uczenia nie było oczywiście wyświetlane. Wszystkie operacje odbywały się w tle, aby maksymalnie zoptymalizować wydajność algorytmu. Bez wyświetlania rezultatów i konieczności synchronizowania wyświtlanej liczby klatek z czasem rzeczywistym, symulacja gry mogła przebiegać nawet 1000 razy szybciej. Wszystkie paramerty uczenia są zdefiniowane w pliku głównym — AiEnviroment.py. Tam też można przy użyciu parametrów startowych określić sposób, w jaki ma uruchomić się program. >display_mode (liczba całkowita [0-3])- określa, w jakim trybie wyświetlania ma zostać uruchomiony program >>0 - brak wizualizacji gry >>1 - wizualizacja gry >>2 - wizualizacja gry, możliwość poruszania jednym z graczy za pomocą myszki >>3 - wizualizacja gry i wyświetlanie wykresów podsumowujących proces uczenia po każdej epoce >load_model (typ logiczny) - określa, czy przy inicjalizacji modelu sieci mają zostać wczytane wagi z pliku >>0 - brak wczytywanie >>1 - wczytywanie >save_model (typ logiczny) - określa, czy po każdej epoce wagi uczącego się modelu mają zostać zapisane do pliku >>0 - brak zapisywania >>1 - zapisywanie > >save_charts (typ logiczny) - określa, czy po każdej epoce wykresy podsumowujące proces uczenia mają zostać zapisane do plików >>0 - brak zapisywania >>1 - zapisywanie > >epochs_number (liczba całkowita dodatnia) - określa liczbę epok, po której ma zostać zakończone uczenie > >games_per_epoch (liczba całkowita dodatnia) - określa liczbę gier, jakie mają zostać zasymulowane w trakcie jednej epoki > >frames_per_game (liczba całkowita dodatnia) - określa liczbę klatek, jakie mają zostać zasymulowane w trakcie jednej gry, długość gry > >batch_size (liczba całkowita dodatnia) - określa rozmiar zestawu próbek używanego w trakcie jednego kroku uczenia > >gamma (liczba zmiennoprzecinkowa [0-1)) - wartość współczynnika γ, określającego wpływ nagrody możliwej do uzyskania w przyszłości na wybór optymalnej akcji > >epsilon (liczba zmiennoprzecinkowa [0-1)) - początkowa wartość zmiennej ϵ określającej prawdopodobieństwo eksploracji > >epsilon_decay (liczba zmiennoprzecinkowa [0-1)) - wartość przez którą mnożony jest zmienna ϵ po każdym uczeniu w celu jej zmniejszenia > >update_rate (liczba całkowita dodatnia) - liczba klatek co jaką następować będzie aktualizacja kopii modelu względem modelu głównego ![](https://i.imgur.com/pi5gPN7.png) > Wizualizacja środowiska do uczenia sieci ### Implementacja sieci Do algorytmu deep q-learning, wykorzystaliśmy sieć neuronową zaimplementowaną w bibliotece tensorflow.keras. Na początku spore trudności sprawiało nam zrozumienie całego procesu inicjalizacji sieci, ale z czasem zrozumieliśmy ogólną koncepcję działania tego modułu. Bardzo duży problem sprawiała nam optymalizacja bibioteki tensorflow. Czasy predykcji wartości i uczenia modelu były skrajnie długie, a my nie potrafiliśmy znaleźć źródła problemu. Dopiero po kilku tygodniach poszukiwań, natrafiliśmy na rozwiązanie, które w znaczny sposób zoptymalizowało proces uczenia. tf.compat.v1.disable_eager_execution() Powyższa linijka znacznie poprawiła wydajność naszego procesu uczenia. Nie udało nam się odnaleźć dokładnego opisu jej działania, z wyjątkiem takiego, że wyłącza ona "gorliwą egzekucję" (https://www.tensorflow.org/api_docs/python/tf/compat/v1/disable_eager_execution). ### Proces uczenia Rozpoczęliśmy tworzenie projektu od implementacji podstawowego algorytmu deep q-learning i rozoczęciu uczenia (liczyliśmy na jakiekolwiek efekty). Jak się szybko okazało, nie był to najlepszy pomysł, gdyż nasz model nie był uczony poprawnie i mimo bardzo wielu modyfikacji w kodzie, nie byliśmy w stanie osiągnąć żadnych zadowalających rezultatów. Wtedy też udaliśmy się na konsultacje, gdzie dowiedzieliśmy się, że najlepszym pomysłem będzie nasz problem uprościć. Postanowiliśmy więc zgodnie z zaleceniami prowadzącego, nauczyć nasz algorytm podejmować znacznie mniej złożone decyzje, a dopiero potem, w miare możliwości, komplikować problem i dodawać coraz to więcej możliwych stanów i akcji. Do obliczeń wykorzystywaliśmy nasze prywatne urządzenia oraz komputer koła naukowego Politechniki Gdańskiej - "Gradient". --- #### Ruch w jednym wymierze bez wektorów Uprościliśmy nasz problem do absolutnego minimum, modyfikując naszą sieć i funkcje nagrody, oraz przekazywane stany. W tym scenariuszu celem agenta było wyrównanie swojej pozycji x z pozycją x piłki. Warto wspomnieć, że dla tego scenariusza pominęliśmy ruch wektorowy. Przemieszczenie agenta dokonywało się przez bezpośrednią zmianę pozycji, a nie przez zmianę wektora prędkości (jak w późniejszych etapach). Parametry stanu (znormalizowane) : * pozycja x piłki * pozycja x agenta Akcje : * ruch w lewo (bezpośrednia zmiana pozycji) * ruch w prawo (bezpośrednia zmiana pozycji) Nagoda : Wartość nagrody była dla tego scenariusza była określona wzorem: $R = screen\_width - (agent\_x - ball\_x) / screen\_width$ Gdzie oczywiście: * $screen\_width$ - szerokośc ekranu * $agent\_x$ - wartość x wektora położenia agenta * $ball\_x$ - wartość x wektora położenia piłki Po wielu próbach i odpowiednim dostosowaniu parametrów udało się nam uzyskać satysfakcjonujący wynik. Niestety nie posiadamy żadnej dokumentacji tego etapu, gdyż wykresy i nagrania zostały wprowadzone w bardziej złożonych. --- #### Ruch w jednej osi z wektorami Po sukcesie osiągniętym w pierwszym scenariuszu skomplikowaliśmy problem dokładając kolejne parametry. Parametry stanu (znormalizowane) : * pozycja x piłki * wektor x prędkości piłki * pozycja x agenta * wektor x prędkośći agenta Akcje : * ruch w lewo (zmiana wektora prędkości) * stój w miejscu * ruch w prawo (zmiana wektora prędkości) Parametry algorytmu : * epsilon_decay = 0.9999 * learning_rate = 0.0001 * gamma = 1 * batch_size = 100 Nagoda : Wartość nagrody była dla tego scenariusza była określona wzorem: $R = screen\_width - (agent\_x - ball\_x) / screen\_width$ Gdzie oczywiście: * $screen\_width$ - szerokośc ekranu * $agent\_x$ - wartość x wektora położenia agenta * $ball\_x$ - wartość x wektora położenia piłki Dla powyższego scenariusza musieliśmy zmienić nasz model uczenia. Po kilku dniach prób i błędów udało się nam nauczyć poprawnie działającą sieć. Poniżej krótkie demo nauczonego algorytmu: ![](https://i.imgur.com/zgcVhNH.gif) Na powyższej prezentacji widać, że algorytm nie jest doskonały (gracze ustawiają się w pewnej pozycji od piłki). Wynika to z faktu, iż gracze nie znają swojej pozycji $y$, przez co nie wiedzą, czy ustawiając się bliżej piłki, przypadkiem nie zmienią jej położenia (zmniejszając tym samym swoją nagrodę). Poniżej prezentujemy wykres średniej zmiany nagrody na grę dla wyżej prezentowanego rezultatu: ![](https://i.imgur.com/q9BUYFh.png) Proces uczenia trwał 400 gier, każda po 400 klatek. Zgodnie z oczekiwaniami, średnia zmiana nagrody rośnie wraz z kolejnymi rozgrywanymi grami. --- #### Ruch za piłką bez wektorów Po osiągnięciu oczekiwanego rezultatu w przestrzeni jednowymiarowej przyszedł czas na skomplikowanie problemu i wprowadzenie ruchu na dwóch wymiarach. W tym scenariuszu celem było nauczenie agentów poruszenia się za piłką i w najbliższym jej sąsiedztwie uzyskiwali największą nagrodę. Warto zaznaczyć, że na tym etapie nagroda nie jest w żaden sposób uzależniona od pozycji na boisku (czy też pozycji piłki wobec bramek). Parametry stanu (znormalizowane) : * pozycja x piłki * pozycja y piłki * wektor x prędkości piłki * wektor y prędkości piłki * pozycja x agenta * pozycja y agenta * wektor x prędkośći agenta * wektor y prędkośći agenta Akcje : * ruch lewo-góra * ruch środek-góra * ruch prawo-góra * ruch lewo-środek * stój w miejscu * ruch prawo-środek * ruch lewo-dół * ruch środek-dół * ruch prawo-dół Parametry algorytmu : * epsilon_decay = 0.99999 * learning_rate = 0.0001 * gamma = 1 * batch_size = 100 Nagoda : Wartość nagrody była dla tego scenariusza była określona wzorem: $R =(d - (agent\_p - ball\_p).length()) / d$ Gdzie oczywiście: * $d$ - długość przekątnej ekranu * $agent\_p$ - wektor pozycji agenta * $ball\_p$ - wartość pozycji piłki Poniżej krótkie demo oraz wykres nauczonego algorytmu: ![](https://i.imgur.com/a9coJ3w.gif) ![](https://i.imgur.com/ibWYZmf.png) Tak jak w poprzednim scenariuszu, gracze ustawiają się w pewnej odległości od piłki. Wynika to najprawdopodobniej z próby uniknięcia scenariusza, w którym piłka zostanie kopnięta i oddali się od agenta, zmniejszając tym samym nagrodę. Wierzymy, że gdyby uczyć taki model wystarczająco długo, nauczyłby się on ustawiać maksymalnie blisko środka piłki, nie zmieniając jej położenia. Proces uczenia trwał 700 gier, każda po 400 klatek. Zgodnie z oczekiwaniami, średnia zmiana nagrody rośnie wraz z kolejnymi rozgrywanymi grami. --- #### Kompletna gra Kolejnym (i ostatnim) etapem, było nauczenie agenta skutecznej gry i ataku na bramkę. W tym etapie sporo czasu poświęciliśmy na poszukiwanie skutecznego modelu. **Tutaj też zdecydowaliśmy się na implementację ddqn, jako że algorytm dqn dawał bardzo mało satysfakcjonujące wyniki.** Do tego etapu, znacznie zmodyfikowaliśmy sposób, w jaki wyliczana była nagroda. Podany w tym scenariuszu wzór, jest najlepszym i najefektywniejszym, jaki udało nam się wypracować, chociaż nie wątpimy, że istnieją lepsze rozwiązania. Parametry stanu (wszystkie uzależnione od pozycji bramki i kierunku ataku; znormalizowane) : * pozycja x piłki * pozycja y piłki * wektor x prędkości piłki * wektor y prędkości piłki * pozycja x agenta * pozycja y agenta * wektor x prędkości agenta * wektor y prędkości agenta * pozycja x przeciwnika * pozycja y przeciwnika * wektor x prędkości przeciwnika * wektor y prędkości przeciwnika Akcje (także uzależnione od pozycji bramki i kierunku ataku) : * ruch lewo-góra * ruch środek-góra * ruch prawo-góra * ruch lewo-środek * stój w miejscu * ruch prawo-środek * ruch lewo-dół * ruch środek-dół * ruch prawo-dół Parametry algorytmu : * epsilon_decay = 0.999999 * learning_rate = 0.00001 * gamma = 0.75 * batch_size = 128 * update_rate = 400 (ilość klatek co którą ) Nagoda : Wartość nagrody była dla tego scenariusza była określona wzorem: $R =goal\_reward * 0.6 + ball\_vec\_reward * 0.2 + position\_reward* 0.2$ Gdzie: * $goal\_reward$ - nagroda za odległość piłki od bramki przeciwnika, określona wzorem: $(d - goal.get\_dist(ball\_p)) / d$, gdzie: * $d$ - długość przekątnej boiska * $goal.get\_dist(ball\_p)$ - odległość piłki od bramki przeciwnika * $ball\_vec\_reward$ - nagroda za kierunek wektora prędkości piłki, która wynosi 1 gdy piłka leci w bramkę przeciwnika, lub wynosi 0 gdy piłka leci w dowolnym innym kierunku * $position\_reward$ - nagroda za odległość agenta od piłki, określona wzorem $(d - (agent\_p - ball\_p).length()) / d$, gdzie: * $d$ - długość przekątnej boiska * $agent\_p$ - pozycja agenta * $ball\_p$ - pozycja piłki </br> Kluczowym elementem tego etapu było zrelatywizowanie pozycji obu graczy. We wcześniejszych etapach, problem był zdefiniowany dla obu używanych agentów tak samo. W tym etapie jeden z graczy miał za zadanie umieścić piłkę w bramce lewej, a drugi w bramce prawej. W rezulatcie sieć uczyła się obsługiwać obu graczy oddzielnie, ponieważ stany, w których nagroda była większa, były inne dla obu graczy. Było to oczywiście podjeście błędne, więc aby temu zapobiec, stan każdego gracza został określony względem bramki przeciwnika. Dzięki temu podejściu, z perspektywy sieci nie było róznicy między graczem 1 (atakującym w lewo) a graczem 2 (atakującym w prawo). Dostępne akcje także zostały zrelatywizowne, aby efekt względem bramki był dokładnie taki sam. </br> Na tym etapie natrafiliśmy też na poważny problem związany z kryzysem decyzyjnym naszej sztucznej inteligencji. Orzymując nagrodę za kilka niezależnych czynników, takich jak odległość agenta od piłki i odległość piłki od bramki, nasz wytrenowany algorytm nie potrafił odnaleźć najoptymalniejszego rozwiązania i zatrzymywał się w minimum lokalnym aproksymowanej funkcji. W rezultacie nauczona sieć ustawiała się bardzo szybko w najbliższym sąsiedztwie piłki, ale nie podejmowała żadnych akcji, żeby zbliżyć ją do bramki. Po bardzo długich poszukiwaniach rozwiązania opisanego problemu odkryliśmy że zmniejszenie wartości parametru $\gamma$ pozwala na rozwiązanie kryzysowej sytuacji. </br> Innym ważnym aspektem w tej części projektu było odpowiednie osłabianie graczy. Nasz algorytm uczył się z powtórek gier dwóch graczy rywalizujących ze sobą. Z uwagi na fakt, iż korzystali oni z tej samej sieci, algorytm uczył się perfekcyjnej gry przeciwko sobie samemu. Nie uczył się więc analizować wszystkich scenariuszy, najwęcej czasu poświęcając obronie przed autorską strategią. Aby rozwiązać ten problem, w każdej grze jeden z graczy był osłabiany poprzez zwiększanie jego wartości epsilon. Dzięki temu jego decyzje były częściej losowane, a nie podejmowane na bazie sieci. </br> Poniżej prezentujemy demo z naszym finalnym rezultatem, wraz z wykresami z przebiegu procesu uczenia. Wykres średniej zmiany nagrody w zależności od numeru gry: ![](https://i.imgur.com/MCqU5hF.png) Wykres funkcji straty od numeru uczenia: ![](https://i.imgur.com/nEGhOu7.png) Krótkie demo prezentujące grę sieci: ![](https://i.imgur.com/qriw1lE.gif) ### Wnioski Na bazie przeprowadzonego przez nas uczenia, można stwierdzić, iż mała zmiana w algorytmie (na przykład z DQN do DDQN) może znacznie poprawić jakość uzyskiwanych wyników. Po wprowadzeniu drobnych tylko zmian uzyskaliśmy satysfakcjonujący rezultat, którego nie potrafiliśmy osiągnąć podstawowym algorytmem DQN. Stworzenie odpowiedniego modelu sieci oraz funkcji nagrody dla algorytmu DQN dla nietrywialnego problemu wymaga jego głębszej analizy. Dlatego dobrym podejściem jest implementacja algorytmu dla uproszczonych wersji problemu i stopniowe zwiększanie jego złożoności. Pozwala to na szybsze znalezienie optymalnego modelu oraz ewentualnych błędów. Dodatkowo łatwo zauważyć, iż podstawowy algorytm Q-learning staje się mało użyteczny do bardziej złożonych problemów o dużej przestrzeni stanów. Dla przestrzeni nieskończonej, np. przedział liczb rzeczywistych, użycie zwykłego Q-learningu jest niemożliwe bez jej uprzedniej dyskretyzacji. Oczywiście wykorzystując dyskretyzację, można by zastosować algorytm Q-learning dla wszystkich scenariuszy z naszego projektu. Jednak jakość nauczonej taktyki dla problemu byłaby dużo niższa. Dyskretyzacja przestrzeni stanów do zbyt małej liczby powodowałoby znaczące uproszczenie problemu i rozwiązania, natomiast zbyt duża liczba powodowałaby dużą niestabilność algorytmu i znacząco wydłużałaby proces uczenia. Znalezienie optymalnej taktyki dla nieskończonej przestrzeni stanów umożliwia natomiast metoda Deep Q-Network. Na przykładzie naszego projektu, odstąpienie od standardowej metody Q-learningu na rzecz aproksymacji tabeli Q za pomocą uczenia głębokiego metodą DQN pozwoliło agentowi na wykonywanie bardzo płynnych ruchów wzdłuż dowolnych krzywych oraz możliwość podejmowania szybszych decyzji. W przypadku gier kompetytywnych takich jak wykorzystany w projekcie Haxball warto w trakcie treningu zapewnić losowe warunki początkowe w każdym epizodzie. Przyspiesza to proces uczenia i zapewnia lepszą generalizację rozwiązania.