Wrocław, 18 czerwca 2009
Raport przygotowany na zaliczenie przedmiotu: "Metody i algorytmy sztucznej inteligencji."
Wrocław, 18 June 2009
This report has been prepared as a requirement for the course: "Methods and algorithms of artificial intelligence."The purpose of my job was to apply the reinforcement learning algorithm in the game "Connect 4". "Connect 4" is very popular board game. I decided to apply "Q-learning" algorithm. I wrote a special program in Borland C + + Builder Personal. The results of my work are positive, the player learns how to play. Received results are not good, because agent need too much time to learn. I wrote what can be improve in the program.
„Connect 4” wprowadził pierwszy raz do sprzedaży Harrison Heath. Nad grą pracowali James D. Allen i Victor Allis, badania prowadzono niezależnie. Pierwszy z nich opisał grę w październiku 1988 roku, natomiast drugi 16 dni później. Jednym z nich najważniejszych wniosków było stwierdzenie, że pierwszy gracz powinien umieścić żeton w środkowej kolumnie, aby zapewnić sobie największe szanse na zwycięstwo.
Popularna gra „Connect 4” jest znana pod wieloma nazwami np. „Four In row” czy w Polsce jako „Cztery w rzędzie”. Gra przeznaczona jest dla dwóch graczy i polega na naprzemiennym wrzucaniu żetonów do tablicy 6x7. W tablicy działa grawitacja i żetony zajmują zawsze najniższą z możliwych pozycję. Wygrywa gracz, który ułoży cztery żetony obok siebie w pionie, poziomie lub na skos. W przypadku wyczerpania wszystkich żetonów i nie uzyskania czterech żetonów obok siebie jest remis. Dokładniejszy opis gry można przeczytać na stronie [5] lub w wersji angielskiej [3].
Gracz został napisany jako przeciwnik dla gracza uczącego się. Wyszukuje on na planszy trzech żetonów w linii i wrzuca ostatni żeton tak, aby wygrać lub zablokować zwycięstwo przeciwnika w przeciwnym wypadku wrzuca on żetony tak, aby znalazły się jak najbliżej grona innych swoich żetonów. Gracz nie zawsze wybiera najlepsze ruchy i nie jest zbyt trudnym przeciwnikiem dla człowieka, jednak wybiera ruch bardzo szybko.
W sieci można odnaleźć wiele prób implementacji algorytmu uczenia ze wzmocnieniem w grze „Connect 4”. W większości jest to algorytm uczenia ze wzmocnieniem metodą różnic czasowych (TD). Można o tym poczytać w publikacji odnośnie nauki ze wzmocnieniem w grach planszowych [4]. Dobry opis algorytmu znajdziemy też w książce [1] i na stronie [2]. Warto dokładnie zapoznać się z dokładnym opisem.
Algorytm, który postanowiłem zastosować to uczenie ze wzmocnieniem metodą „Q-learning”.
Opis algorytmu znajduje się na rysunku poniżej:
Wzmocnienie, które stosuję następuje po każdym starciu i jest to +1 za wygranie i -1 za przegranie. Wybór akcji to po prostu: „wrzuć do jednej z siedmiu kolumn”. Stan jest opisany przez ilość żetonów w grze i ich ułożenie. Uczeń odszukuje aktualny stan i wykonuje najlepszą akcję, gdy stanu nie ma to dodaje go.
Dla celów projektowych napisałem specjalny program w Borland C++ Builder Personal.
Program posada wygodny interfejs użytkownika i umożliwi trzy tryby gry: dwóch graczy, gracz i komputer, komputer i algorytm. Dodatkowo można rozegrać zawody i ustawić do ilu wygranych starć ma być mecz i jaką liczbę meczy rozegrać. Wyniki można przedstawić na wykresie.
Algorytmy grające są trzy. Algorytm losowy, który wykonuje losowe ruchy. Algorytm „gracz inteligentny” i algorytm naszego ucznia.
Wygląd programu przedstawiam na rysunku poniżej:
Przeprowadziłem wiele testów (właściwiej byłoby napisać wiele godzin testów). Poniżej przedstawie wyniki uczenia dla naszego ucznia oraz wyniki potyczek „gracza inteligentnego” z algorytmem losującym. Wszystkie wyniki przedstawiają ilość wygranych starć w danej partii dla 10 partii. Partia jest to 1000 meczy do 10 zwycięstw.
Poniższa tabela i wykresy przedstawiają starcia „gracza inteligentnego” z graczem losującym:
| Numer partii | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Rozgrywka I | 122 | 53 | 127 | 24 | 55 | 57 | 86 | 48 | 156 | 123 |
| Rozgrywka II | 189 | 27 | 56 | 178 | 84 | 171 | 27 | 43 | 24 | 111 |
| Rozgrywka III | 37 | 91 | 86 | 56 | 133 | 137 | 112 | 89 | 136 | 158 |
Widać wyraźnie, że gracz losujący wygrywa lub przegrywa różne ilości starć pomimo kolejnych partii. Jego wynik jest raz lepszy, raz gorszy… w zasadzie losowy.
Poniższa tabela i wykresy przedstawiają starcia „gracza inteligentnego” z graczem uczącym się:
| Numer partii | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Rozgrywka I | 89 | 124 | 129 | 117 | 138 | 149 | 141 | 156 | 151 | 154 |
| Rozgrywka II | 137 | 126 | 133 | 129 | 136 | 131 | 165 | 158 | 166 | 183 |
| Rozgrywka III | 133 | 148 | 157 | 139 | 147 | 154 | 159 | 163 | 172 | 183 |
Tutaj natomiast widzimy, że gracz uczący się wygrywa małe ilości starć, jednak zawsze w podobnej ilości. Z czasem ilość starć zaczyna wzrastać.
Udało mi się napisać grę w Borland C++ Builder i zaimplementować gracza uczącego się. Gracz faktycznie „uczy się”.
Uważam, że części składowe algorytmu nie zostały dobrze opisane. Wzmocnienie i wybór akcji są poprawne, jednak opis stanów jest zbyt dokładny. Nie trudno policzyć, ze dla 6x7=42 pól i dla trzech możliwości (zielony, czerwony, pusty) otrzymujemy ogromną liczbę stanów. Stany można było zapisać ogólniej, jednak wtedy nie mogłem znaleźć właściwego opisu wyboru akcji. Wykonałem, więc dokładny opis stanów i wprowadziłem dodatkowy element jakim jest ilość żetonów. Element ten odegrał rolę indeksu, przez co wyszukiwanie stanu przebiegało znacznie szybciej.
Wady programu to niewątpliwie czas liczenia, no i czas uczenia. Ogromna liczba stanów wydłuża czas pracy programu niewyobrażalnie. Zaskoczyło mnie, gdy przy dziesiątej partii uczenia, program liczył prawie 1,5 godziny. Czas pracy jest tutaj ogromną wadą programu.
Zaletą jest prosty interfejs użytkownika, możliwość rozegrania cyklu starć oraz przedstawienie wyników za pomocą wykresu. Sam wybór tematu, pracę nad nim jak i otrzymane rezultaty uważam, za osobisty „mały” sukces. Zająłem się tematem dość mało popularnym i metodą, która praktycznie nie została zastosowana w tego typu grach. Badań w tej dziedzinie jest bardzo mało, a jeżeli już są to tylko w formie obcojęzycznej. Może program pozostawia wiele do życzenia i nie jest w pełni sprawny to i tak uważam, że moja praca, uzyskane efekty, wnioski i przemyślenia nad tym co można jeszcze wykonać to krok do przodu, a każdy taki krok przybliża do całkowitego rozwiązania problemu.
Warto pomyśleć nad rozwiązaniem sposobu opisu stanów, przyśpieszyło by to znacznie pracę programu. Można też program rozbudować o bazy danych. Można stany przetrzymywać w specjalnych bibliotekach i tam sprawnie je wyszukiwać. Spróbować można także zmienić sposób wzmocnień. Można wzmacniać po każdym ruchu, przez co uczenie trwałoby znacznie krócej. Projekt był dość rozbudowany i byłoby łatwiej, gdyby pracowały nad nim dwie osoby.
Nauka ze wzmocnieniem:
[1] http://www.cs.ualberta.ca/%7Esutton/book/ebook/the-book.html
[2] http://en.wikipedia.org/wiki/Reinforcement_learning
Nauka ze wzmocnieniem w grze "Connect 4":
[3] http://en.wikipedia.org/wiki/Connect_Four
[4] http://www.cs.bris.ac.uk/Publications/Papers/2000100.pdf