22.06.2006

Warcaby ze wzmocnieniem

Metody i algorytmy sztucznej inteligencji

Raport z wykonania projektu

Wykonali:

Stefan Guzik 127727

Sławomir Śledź 128423

  1. Cel Projektu

    Głównym celem projektu było napisanie warcab z wykorzystaniem algorytmów uczących się, a dokładnie algorytmu nauki ze wzmocnieniem.

  2. Historia

  3. Odmiany Warcabów

    Ogólne zasady gry można przeczytać na http://www.warcaby.beep.pl/reguly.html .

    W naszym projekcie wykorzystane zostały następujące zasady:

  4. Wykorzystane Algorytmy

    Algorytm MinMax

    Wybór ruchu dokonywany jest na podstawie wartości funkcji oceniającej. Wykorzystany jest standardowy algorytm MinMax, jeśli wiele ruchów ma tą samą (maksymalną) wartość, to wybierany jest pierwszy który został znaleziony. Opis algorytmu algorytmu MinMax.

    Uczenie ze wzmocnieniem

    Jest wiele sposobów uczenia się. Wykorzystaliśmy algorytm uczenia ze wzmocnieniem. Metoda uczenia się ze wzmocnieniem nie zakłada, że agent (komputer uczący się) ma jakąkolwiek wiedze początkową. Celem uczenia się jest wybór właściwych ruchów na podstawie wcześniej rozegranych partii. Za każdą wygraną partię agent dostaje nagrodę +1 punkt, za każdą przegraną partię -1. Wszystkie formy remius dają 0 punktów. Po zakończonej partii agent modyfikuje swoje parametry funkcji oceny poszczególnych stanów w zależności od stanu partii. Celem agenta jest tak modyfikować swoje parametry żeby jego funkcja oceny była jak najlepsza i zdobywał najwięcej nagród. W przypadku gry w warcaby polega to na nauczeniu agenta wygrywać partie. Dokonywane zmiany parametrów powinny prowadzić do wyborów ruchów najbardziej optymalnych i w rezultacie do wygrania partii. Możliwe jest uczenie na bieżąco i po zakończeniu partii. Przedstawimy tylko metodę uczenia po zakończeniu partii gdyż taka jest zaimplementowana w naszym programie.
    Co każdy ruch agent zachowuje swoje stany w celu po zakończeniu partii ich analizy. Analiza stanów partii:
    wzor
    gdzie s1,s2,... są kolejnymi stanami gry.
    alfa - współczynnik uczenia się z przedziału [0-1]. W naszym projekcie przyjeliśmy alfa=0.01
    W warcabach wszystkich stanów nie jesteśmy w stanie obliczyć ze względu na ich bardzo dużą liczbę. Dlatego stosuję się funkcje aproksymującą wartość funkcji na postawie kilku wybranych cech.
    wzor
    gdzie:
    n - liczba wszystkich cech
    w - wagi współczynników cech
    Poniższy wzór przedstawia jak modyfikowane są wartości cech
    wzor

    Powyższy algorytm nosi nazwę TD (Temporal Differences). Wykorzystuje on metodę różnic czasowych czyli swoją wiedze zdobywa na podstawie interekcji ze środowiskiem. Metody różnic czasowych są pewnego rodzaju niestandartowym podejściem do wieloetapowych problemów predykcyjnych. W takich problemach na każdym etapie należy wygenerować prognozę pewnej nieznanej końcowej wartości, na podstawie dostępnej w tym kroku cząstkowej informacji. Przyjmuje się, że w każdym kolejnym kroku informacja ta jest coraz bardzie wiarygodniejsza. Zatem powinna umożliwiać coraz lepsze stawianie prognozy.

  5. Wyniki

    W celu testostowania algorytmu uczenia się ze wzmocnieniem napisaliśmy od podstaw własną aplikacje warcab. Program do został napisany w Javie. Stworzyliśmy kilku agentów. Agenta wykonującego ruchy przypadkowo, Agenta opartego na czystym algorytmie MinMax oraz agenta wykorzystującego uczenie ze wzmocnieniem bez wiedzy początkowej. Agent uczący się wykorzystuje 6 cech planszy:
    cecha[0] - liczba pionków strony grającej
    cecha[1] - liczba pionków strony przeciwnej
    cecha[2] - liczba damek strony grającej
    cecha[3] - liczba damek strony przeciwnej
    cecha[4] - liczba bezpiecznych bić strony grającej
    cecha[5] - liczba bezpiecznych bić strony przeciwnej

    Agent stają się maksymalizować swoje parametry przy jednoczesnym minimalizowani cech przeciwnika. U wszystkich agentów wykorzystujących algorytm MinMax przyjeliśmy głębokość przeszukiwań równą 4 co znacznie przyśpiesza działanie programu a jednocześnie pokaże jak duży wpływ ma algorytm uczenia się na liczbę wygranych partii.

    Agent MinMax posiada wagi cech:
    cecha[0] cecha[1] cecha[2] cecha[3] cecha[4] cecha[5]
    Wartość początkowa 15 -17 260 -350 22 -20

    Wpływ współczynnika gamma na wartości wag cech. Po 10 partiach z agentem MinMax
    Wartość gamma cecha[0] cecha[1] cecha[2] cecha[3] cecha[4] cecha[5]
    Początkowe 0.046 -0.025 0.028 0.038 0.042 -0.048
    gamma = 1 0.527 -0.191 0.129 0.038 0.041 -0.081
    gamma = 0.9 0.116 -0.114 0.065 -0.036 0.037 -0.048
    gamma = 0.8 0.105 -0.105 0.045 -0.035 0.028 -0.053
    gamma = 0.5 0.056 -0.056 0.021 -0.041 0.028 -0.040

    Wynik przeprowadzonego turnieju bez wiedzy agenta uczącego się. Przy nastawach alfa=0.01 i gamma=1
    Random MinMax ReinformerLerner (bez wiedzy)
    Random - 2:8 5:5
    MinMax 9:1 - 9:1
    ReinformerLerner (bez wiedzy) 3:7 2:8 -

    Wynik przeprowadzonego turnieju z agentem posiadającym wiedze z własnego doświadczenia. Przy nastawach alfa=0.01 i gamma=1
    Random MinMax ReinformerLerner
    Random - 1:9 0:10
    MinMax 9:1 - 4:6
    ReinformerLerner 10:0 7:3 -

  6. Wnioski

    Wraz ze wzrostem współczynnika gamma wzrasta różnica wag pomiedzy przeciwstawnymi cechami planszy. Im większa gamma tym agent starał się bardziej grać pionkami i nie pozwalał zdobywać damki przeciwnikowi. Dla gamma=1 uczący się agent wogóle nie pozwolił zdobyć przeciwnikowi damki. Z tego powodu waga odpowiedzialna za damki przeciwnika nie zmieniła swojej wartości.
    Zaobserwowaliśmy również, iż jeżeli wartość cechy pionków własnych jest większa od wartości cechy damek własnych to agent jeśli nie ma potrzeby to nie wymienia pionków na damki. Z przeprowadzonych eksperymentów wynika, że początkowo zawsze wygrywa algorytm MinMax ze względu, że ma dobrze dobrane parametry cech. Jednak wraz ze wzrostem przeprowadzonych partii agenci z algorytmem nauki zaczynają stopniowo wygrywać partie z agentami opartymi na algorytmie MinMax. Jednak ze względu że agenci uczą się jedynie na podstawie tylko kilku cech nigdy będą poważnymi przeciwnikami dla doświadczonych graczy albo dla agentów którzy wykorzystują większą liczbę cech planszy. Kolejną przeszkodą którą zaobserwowaliśmy jest, że agent uczący się był coraz trudniejszym przeciwnikiem to musi rozegrać dużą liczbę partii i najlepiej z zawodnikiem dużo lepszym odniego samego.

  7. Applet

    Applet działa tylko pod Firefox-em.
    Miłej Gry!

  8. Literatura

    1. Systemy uczące się - Paweł Cichosz
    2. Reinforcement Learning:An Introduction - Richard S. Sutton and Andrew G. Barto
    3. A Reinforcement Learning base Neural Multi-Agent-System for Control of a Combustion Process - V.Stephan, K.Debes

  9. Materiały z internetu

    1. http://www.cs.washington.edu/research/jair/abstracts/kaelbling96a.html.
    2. http://www.cs.ualberta.ca/%7Esutton/book/ebook/the-book.html.
    3. http://en.wikipedia.org/wiki/Reinforcement_learning.
    4. http://www.answers.com/topic/reinforcement-learning.
    5. http://www-anw.cs.umass.edu/rlr/.
    6. http://www.cs.ualberta.ca/%7Esutton/book/ebook/the-book.html.

Valid HTML 4.01 Transitional