Metody i algorytmy sztucznej inteligencji

01.07.2007

Algorytm MinMax oraz uczenie ze wzmocnieniem w grze Mankala

Autor: Tomasz Elimer
Prowadzący: dr inż. Witold Paluszyński

Opis zadania

Celem zadania było zaimplementowanie algorytmu uczenia ze wzmocnieniem z wykorzystaniem metody MinMax w grze Mankala. W tym celu wykorzystana została aplikacja znajdująca się pod adresem [1]. Program ten jest wynikiem podobnego zadania projektowego i zawiera gotową implementację gry oraz kilka algorytmów graczy. Brak wśród nich metody badanej w tym projekcie, więc została ona zaimplementowana z wykorzystaniem istniejących modułów.

Zasady gry

[5] Plansza do gry złożona jest z ustawionych w dwóch rzędach pojemników, w których znajdują się 4 kulki (lub ziarenka) oraz dwóch pojemników końcowych, na początku pustych. Każdy rząd należy do jednego z graczy. Ruch odbywa się poprzez wyjęcie wszystkich kulek z jednego z własnych pojemników i umieszczaniu po jednej w kolejnych pojemnikach, w kierunku przeciwnym do ruchu wskazówek zegara, włącznie z własnym pojemnikiem końcowym. Jeżeli ostatnią kulkę umieścimy we własnym pojemniku końcowym, to przysługuje nam kolejny ruch. W przeciwnym przypadku rusza się przeciwnik. Jeżeli mamy więcej kulek, umieszczamy je w pojemnikach przeciwnika, a gdy dotrzemy do ostatniego z nich zostawiamy w nim wszystkie pozostałe kulki. Jeżeli zakończymy ruch we własnym pojemniku i jest on pusty, to ostatnią kulkę oraz wszystkie kulki z położonego naprzeciw pojemnika drugiego gracza przenosimy do naszego pojemnika końcowego. Gdy jeden z graczy pozbędzie się wszystkich kulek ze swoich pojemników, gra kończy się, a przeciwnik dodaje kulki ze swoich pojemników do swojego pojemnika końcowego. Wygrywa gracz, który zebrał więcej kulek.

Opis zastosowanego algorytmu

Dokładne omówienie metody MinMax oraz uczenia ze wzmocnieniem można znaleźć na stronach [2],[3]. W tej części przedstawione zostanie tylko ich dostosowanie do postawionego zadania.

Uczenie ze wzmocnieniem

Algorytm uczenia ze wzmocnieniem zakłada nagradzanie i karanie podjętych działań w zależności od ich efektu. Oceny dokonujemy po zakończeniu rozgrywki, odpowiednio modyfikując wartości każdego działania podjętego w zaistniałych w partii stanów.

Przyjete wartości nagród i kar:

Algorytm MinMax

Zastosowana metoda MinMax przewiduje posunięcia graczy na głębokość 3 tur poniżej aktualnego stanu. Warto zauważyć, że zgodnie z zasadami gry graczowi może przysługiwać więcej niż jeden ruch z rzędu, co dodatkowo zwiększa wartość posunięć. Wartość każdego zagrania szacowana jest funkcją:

moveValue = myGoal - oppGoal + Q
Jeśli dwa lub więcej ruchów mają taką samą wartość, zagranie wybieramy losowo spośród nich.

Implementacja

Pomijając kilka poprawek w pobranym kodzie źródłowym, implementacja algorytmów sprowadzała się do modyfikacji algorytmu Q-uczenia. Do przechowywania danych wykorzystana została baza danych mySQL składająca się z dwóch tabel q oraz nsa , o polach state, action, value. State i action określają odpowiednio stan planszy (zapisany jako String, w którym liczby rozdziela znak ':') i podjętą w nim akcję. Pole value przechowuje wartość Q lub ilość wystąpień danego stanu, w zależności od tabeli. Tabela nsa nie jest istotna w działaniu algorytmu, ale została zachowana w celu weryfikacji poprawności działania programu i ewentualnych badań częstotliwości wystąpień stanów.

Uruchamianie

Program jest aplikacją konsolową napisaną w języku Java i może być uruchamiany z linii poleceń wywołaniem:

java MancalaAgentPlay player1 player2 games

player1, player2 - określają algorytmy graczy, dopuszczalne są wartości: games - określa ilość rozgrywek

W zależności od konfiguracji systemu może być konieczne pobranie oraz instalacja serwera bazy danych mySQL oraz specjalnego pliku umożliwiającego aplikacji połączenie z nim. Pliki te znajdują się na stronie [4]. Aplikacja została przetestowana na bazach danych w wersji 4.1 oraz 5.0. Do połączenia można wykorzystać J/Connector w wersji 3.09 lub 3.1. Aplikację należy uruchomić z parametrem -cp "ścieżka do pliku J/Connector.jar;"( pamiętając o średniku na końcu).

Badania eksperymentalne

Przeprowadzone badania miały na celu określenie wydajności uczenia badanego algorytmu oraz porónanie go z metodami dostępnymi w programie. Autorzy programu zaimplementowali algorytm Q-uczenia z bazą wiedzy przechowywaną w bazie danych mySQL oraz wersję ANN z bazą wiedzy przechowywaną w sieci neuronowej. Dokładniejszy opis można znaleźć na stronie projektu [1].

W pierwszym etapie badań każdy zawodnik rozegrał po 100 partii z każdym z przeciwników. W ten sposób oceniamy jego poziom początkowy w każdej parze. Następnie przeprowadzona została sesja treningowa, czyli uczenie algorytmów w sesjach po 200 gier z każdym przeciwnikiem, w tym także z samym sobą. Badania postępów polegały na ponownym rozegraniu 100 partii z każdym z pozostałych graczy, z wykorzystaniem zdobytej wiedzy. W tabelach zebrane zostały wyniki badań.

Wyniki badań

Ilość wygranych i przegranych partii przed uczeniem
random simple Q-Learning MinMaxANN
Q-learning 88:9 0:0 X 61:39 0:0
MinMax 88:942:54 ? X 52:46
ANN 82:12 0:0 ? 59:41X

? - algorytm z niewyjaśnionych przyczyn nie działa w roli drugiego gracza

Ilość wygranych i przegranych partii po uczeniu
random simple Q-Learning MinMaxANN
Q-learning 78:18 100:0 X 22:62 84:11
MinMax 92:7100:0 ? X 87:12
ANN / / ? /X

/ - "brak pamięci" uniemożliwił przeprowadzenie badań

Wnioski

Uzyskane wyniki są jedynie małą częścią badań, jakie należałoby przeprowadzić, aby w pełni obiektywnie ocenić postępy w nauce algorytmów. Jednak już w takiej próbce można zaobserwować pewne różnice w poziomie gry. Jak widać, nawet krótki trening wystarczy, aby całkowicie przewyższych najprostszą strategię. W przypadku Q-uczenia okazuje się on niewystarczający, aby sprostać losowemu wybieraniu ruchów. Porażka z algorytmem MinMax prawdopodobnie wiąże się z jego lepszym wyszkoleniem, co widać w uzyskanych wynikach. Wpływ na jakość uczenia może mieć także kolejność trenowania poszczególnych zawodników. Ostatniemu uczestnikowi treningu przeciwstawiani są zawodnicy już wyuczeni, co może pozwolić mu na poznanie ich gry już podczas treningu (a oni takiej możliwości nie mieli), bądź też postawić go przed zadaniem trudniejszym niż mieli jego poprzednicy. Przy większej ilości gier treningowych różnica ta prawdopodobnie nie byłaby, aż tak istotna.

W trakcie badań natrafiono na liczne utrudnienia, ale na podstawie uzyskanych wyników można stwierdzić, że algorytm MinMax okazał się najskuteczniejszy. Taka skuteczność ma jednak swoją cenę. Serie z udziałem tego gracza trwały nawet 10-krotnie dłużej niż średnia seria innych zawodników. Tak długi czas działania związany jest z dużą ilością możliwości sprawdzanych przed podjęciem decyzji, dodatkowo obciążonych niezbyt szybkim dostępem do bazy wiedzy.

Materiały źródłowe

  1. Strona wykorzystanego projektu
    http://www.public.iastate.edu/~cstras/cs572project/cs572project-webpage.html
  2. Omówienie algorytmu MinMax
    http://ai-depot.com/articles/minimax-explained/
    http://www.seanet.com/~brucemo/topics/minmax.htm
  3. Omówienie uczenia ze wzmocnieniem
    http://www.cs.ualberta.ca/%7Esutton/book/ebook/the-book.html
  4. Strona domowa mySQL
    http://www.mySQL.org
  5. Więcej o grze Mankala
    http://www.wikimanqala.org/wiki/Main_Page