Wyuczalność gry w Tysiąca

Spis treści

1. Abstract

Our task was to create web application that allows us to play thousand card game. We focused on variant for three players. We can combine computer and human players. Our goal was to teach, using Q-learning[3,5], computer players basic strategies to reach level of average human player.
Our application allowed us to simulate thousand of games between three computer players. Almost all of them reach expected average of 60 points per game. From this we assume, that they have similarly high level. When combining skilled player with new (nearly new) computer player we can see, that this new player is much weaker than our skilled agent.
As far as we concern this experiment proves that thousand card game is fully learnable using our Q-learning method.

2. Opis zadania

Zadanie polegało na stworzeniu aplikacji webowej umożliwiającej grę w tysiąca. Rozgrywka może przebiegać pomiędzy dowolną kombinacją graczy i agentów.

3. O grze w tysiąca

4. Rozwiązanie

• Metoda i model

  Do wykonania projektu użyliśmy uczenia ze wzmocnieniem[1]. Metoda ta polega na nagradzaniu lub karaniu agenta, według całkowitoliczbowej funkcji oceny, za akcje wykonane w ramach danej strategii. Agent nic nie wie o otaczającym go środowisku, posiada tylko listę akcji które może wykonywać. Wykorzystujemy Q-learning z eksploracją. W przypadku rozgrywki w tysiąca celem agenta było zmaksymalizowanie wyniku punktowego pojedyńczego rozdania. Charakterystykę uczenia ze wzmocnieniem określa się poprzez dobranie odpowiednich wartości parametrów. Są to:

  1. random - określający prawdopodobieństwo wybrania losowej akcji zamiast wskazanej przez sień neuronową,
  2. alpha - Stała opisująca jak szybko nowo zyskane informacje nadpiszą wcześniejsze dane,
  3. gamma - Stałą określająca jak ważne są przyszłe nagrody względem tymczasowych,
  4. lambda - Określa poziom potrzebny do zakwalifikowania ścieżki do zapomnienia,
  5. czy chcemy używać funkcji aproksymacji stanów Boltzmana[6] i jej temperatura (parametr tej funkcji).

  Dla znalezienia optymalnego zbioru stałych przeprowadziliśmy wiele testów. Zaprojektowana aplikacja pozwoliła nam wprowadzić wielu agentów którzy rozgrywali ze sobą gry. Na tej podstawie wyklarował się dość optymalny zbiór tych stałych.

• Przestrzeń stanów

  Przestrzeń stanów programu opisana jest dwudziestoma pięcioma stałymi. Każdą z 24 kart opisujemy jedną liczbą z zakresu [0-3] określającą, czy:

  1. dana karta znajduje się na mojej ręce,
  2. została już zagrana we wcześniejszym ruchu,
  3. znajduje się na stole,
  4. jest u któregoś z przeciwników (nie ma o niej jeszcze informacji).

  Do tego opis stanu uzupełniony jest o atu stołu. Daje nam to 4^24 * 5 stanów.

• Funkcja nagrody

  W procesie tworzenia aplikacji przetestowaliśmy kilka funkcji oceny. Jako pierwszą wykorzystaliśmy funkcję która brała tylko wartość kart na stole. Była ona skuteczna - dając średni wynik w okolicy 58-60 punktów na rozgrywkę. Rozpatrywaliśmy też wariant z uwzględnieniem kary za meldunek przeciwnika, lecz strategia ta powodowała złe wyuczanie. Agenci unikali dobrych ruchów, bo po ich wystąpieniu przeciwnik meldował w poprzednich grach. Ostatecznie zdecydowaliśmy się na nieco cięższą, lecz wciąż jedną z najprostszych - liniową w zależności od wyniku ostatniej lewy (w punktach z pominięciem meldunku przeciwnika). Ta funkcja oceny dawała wyniki dokładnie takie same jak pierwsza funkcja którą testowaliśmy. Naszym zdaniem jest to spowodowane wymuszeniem przez zasady przebijania jeżeli jest to możliwe.

5. Program

• Zasada działania

  Po podaniu loginu gracz widzi ekran z listą aktywnych graczy, oraz listą graczy w kolejce. Używając górnego menu, możemy:

  1. zapisać się do kolejki,
  2. zapisać do kolejki agenta, używając przycisku “Wybierz gracza komputerowego”, a następnie klikając na symbol dyskietki,
  3. zobaczyć statystyki oraz właściwości agenta korzystając z przycisku “Wybierz gracza komputerowego”, a następnie klikając na symbol lupy,
  4. wiet' dodać nowego agenta, podając szczegółowe współczynniki wpływające na jego proces uczenia się,
  5. włączyć tryb autozapisywania agentów do kolejki po skończonej grze.

  W momencie gdy w kolejce będzie 3 graczy gra rozpocznie się automatycznie. Gracz który zaczyna zostanie wylosowany automatycznie. Gdy będzie nasz ruch, zobaczymy okno dialogowe z powiadomieniem. W grze używając menu kontekstowego możemy wyświetlić okna dialogowe wyświetlające punktację, ostatnią lewę, oraz karty które wziął każdy z graczy. Zagrywamy kartę poprzez kliknięcie na jej obrazek. Gdy możemy zameldować, pod odpowiednimi kartami pojawią się przyciski “Melduj”. Gra kończy się w momencie gdy ręce graczy są puste.

• Sesje uczące

  System uczy naszego agenta w każdej rozgrywce. Na początku gry wczytujemy bazę wiedzy zapisaną w pliku tekstowym (funkcja jest nam dostarczona przez framework z którego korzystamy). Po każdym ruchu agenta wywołujemy funkcję oceny i wzmocnienia stanu/akcji. Po zakończonej rozgrywce zapisujemy zmieniony stan wiedzy do tego samego pliku. Z racji na specyfikę aplikacji, i informacje jakie przechowuje agent, możemy w łatwy sposób porównywać ich między sobą w celu wyłonienia najlepszego zestawu stałych określających parametry wzmocnienia.

6. Implementacja

• Aplikacja

  Aplikacja została napisana w javie korzystając z następujących technologii:

  1. Java ee6
  2. JSF 2
  3. Primefaces 3.5
  4. EJB 3.1
  5. Hibernate 4
  6. Maven

  Użyliśmy wzorca aplikacyjnego MVC rozszerzonego o warstwę biznesową.

  

  Taka architektura umożliwiła sprawną równoległą pracę na wspólnej płaszyźnie, jaką był interfejs IPlayer.

• Agent

  Klasa ComputerPlayer reprezentuje agenta. Dzięki referencji na obiekt Game jest w stanie przekazywać wykonane ruchy do innych graczy. Przechowuje informacje pobrane z bazy danych, potrzebne do określenia agenta:

  1. nazwa agenta,
  2. liczba rozegranych gier,
  3. suma punktowa wszystkich gier,
  4. stałe potrzebne do inicjalizacji frameworka do nauki ze wzmocnieniem,
  5. ścieżka do pliku ze stanem wiedzy agenta.

  Klasa ComputerPlayer łączy napisaną przez nas aplikację z frameworkiem[7]. Do obliczania kolejnych ruchów wykorzystuje nadpisaną przez nas klasę MyPerception, dostarczoną przez framework. Znajduje się tam funkcja oceny stanu, oraz funkcja nagrody. Cała logika związana z obliczaniem kolejnych ruchów oraz uaktualnianiem stanu wiedzy znajduje się w klasie Brain będącej częścią frameworka. Do klasy Brain dostarczamy tablicę w której są zapisane wszystkie możliwe akcje.

7. Wyniki

• Agent kontrolny

  Wszystkie parametry uczenia miał ustawione na 0, stąd grał całkowicie losowo. Jego średni wynik to 38. Na tej podstawie mogliśmy sprawdzić, czy proces uczenia przynosi pożądane rezultaty.

  

• Najgorszy agent używający opisu stanu nie uwzględniającego atu

  Rozegrał on ponad 30’000 gier i osiągnął średni wynik punktowy równy 51. Jest to zdecydowanie lepiej niż agent kontrolny, więc widać, że nauka przynosi efekty. Miał ustawione wartości uczenia: alfa = 0.2, gamma = 0.8, lambda = 0.8, random = 0.1 i używa funkcji aproksymacji Boltzmana[6] z temperaturą 0.005. Co ciekawe po rozegraniu 600 gier agent ten miał znacznie lepszy wynik na poziomie 60 oczek.

  

• Najgorszy agent używający opisu stanu uwzględniającego atu

  Osiągnął również średni wynik równy 51. Stałe miał takie same jak powyższy gracz z inną funkcją oceny poza randomem = 0.2 i temperaturą równą 0.5. Możemy po tym wnioskować, że ten zestaw stałych jest nieoptymalny dla uczenia ze wzmocnieniem w przypadku gry w tysiąca.

  

• Najlepszy gracz nie uwzględniający atu

  Osiągnął on średni wynik 61 oczek. Wartości uczenia ma takie same, jak domyślne dla frameworka. Alfa = 0.1, gamma i lambda - 0.9. Random na poziomie 0.1 i nie używa funkcji Boltzmanna. Wyniki które zapewniły średnią 60 oczek i więcej osiągnął po 1200 grach.

  

• Najlepszy gracz uwzględniający atu

  Osiągnął wynik na poziomie 60 oczek. Dane do wzmocnienia ma takie same jak gracz powyżej, jednak ten używa funkcji boltzmanna z temperaturą 0.004. Różni się od poprzedniego tym, że na poziom 60 oczek doszedł już po 150-200 grach.

  

  Zauważmy, że wyniki osiągane przez agentów z tymi dwoma funkcjami oceny dają praktycznie takie same wyniki. Specyfika zasad gry w tysiąca wymusza na graczach nie uwzględniających atu branie lewy jeżeli jest taka możliwość, stąd te wyniki nie różnią się zbytnio. Gracze mający pełen obraz uczą się jednak znacznie szybciej.

  Ważnym faktem jest, że średni wynik 60 punktów jest wynikiem bliskim ideału. Oznacza to, że wszyscy grający ze sobą gracze grali prawie optymalnie. W przypadku słabszych graczy takie wyniki nie są osiągalne (ze względu na utratę meldunków itd.). Maksymalizowanie wyniku można sprawdzać na testach w których nauczeni gracze grają ze słabszymi - widać wtedy, że słabsi gracze osiągają średnie wyniki na poziomie 40-45 punktów, a nasz wyuczony gracz znacznie wyższe.

8. Opinie testerów

9. Wnioski

Na podstawie przeprowadzonego doświadczenia stwierdzamy, że rozgrywka w tysiąca jest całkowicie wyuczalna. Gracze grający ciągle ze sobą osiągają podobny poziom w okolicy 60 pkt (według źródeł jest to bliskie średniej wartości punktowej przypadającej na jednego gracza).
Testerzy (włączając nas) wysoko oceniali poziom umiejętności agentów. Zauważyliśmy również, że zwiększenie ilości stanów nie poprawiło wyników, lecz znacznie przyspieszyło proces uczenia się. Aproksymacja funkcją Boltzmanna nie miała znaczącego wpływu na wyniki. Wśród najlepszych i najgorszych agentów znajdowały się te używające jej jak i te, które z niej nie korzystały. Pozostałe parametry były istotne. Na podstawie wielu testów możemy wskazać bliski optymalnemu zestaw stałych (są one wymienione w opisie wyników).

10. Słowniczek

11. Literatura