Piłkarzyki to popularna dwuosobowa gra odbywająca się na kartce papieru - na prostokątnym polu o rozmiarze 8 na 10 kratek. Gracze wykonują swoje ruchy naprzemiennie, pierwszy ruch wykonywany jest z kropki znajdującej się na środku boiska, każdy kolejny z kropki, na której skończył się poprzedni ruch. Ruch polega na narysowaniu odcinka z kropki, z której rozpoczyna się ruch, do kropki, na której ruch ten ma się zakończyć. Ruch można poprowadzić tylko do kropki sąsiadującej w linii poziomej, pionowej lub po skosie. Rysowana linia nie może pokrywać się z żadną z inną linią, zarówno powstałą w wyniku wcześniejszych ruchów, jak i okalającą boisko. Kiedy gracz kończy swój ruch na kropce, przez którą przechodzi wcześniej narysowana linia zostaje mu przyznany dodatkowy ruch. Punkt zdobywa się umieszczając kropkę w bramce przeciwnika lub wówczas gdy przeciwnik doprowadzi do zablokowania gry (sytuacji w której nie ma on możliwości kontynuowania swojej tury). [1] [2]
Zastosowany przez nas algorytm to uczenie ze wzmocnieniem metodą Q-learning. Wzmocnienie następuje w przypadku wygrania rozgrywki (+1) lub jej przegrania (-1). Możliwe do wykonania akcja to oczywiście ruch w którymś z kierunków, a przyjęty przez nas opis stanu to sekwencja kolejnych ruchów. Początkowo rozważaliśmy opis stanu poprzez przedstawienie dokładnej sytuacji na boisku (tzn. określenie zaznaczonych kropek oraz narysowanych odcinków dla każdego pola boiska), pomysł został zarzucony ponieważ przyjęte rozwiązanie jest w pełni wystarczające, a zarazem znacznie oszczędniejsze pamięciowo.
Pseudokod przedstawiający zaimplementowany algorytm uczący się [3]:
Program został zaimplementowany w języku C# w środowisku MS Visual Studio 2005. Aplikacja posiada funkcje ułatwiające przeprowadzanie testów - możliwość określenia liczby gier do przeprowadzenia, prędkości animacji (opóźnienia pomiędzy kolejnymi ruchami), wynik gry jest wyświetlany na bieżąco. Rozgrywka może być prowadzona przez człowieka, algorytm uczący się, algorytm wykonywający ruchy losowe, algorytm minimax oraz prosty algorytm starający się w miarę możliwości wykonywać ruchy do wewnątrz boiska oraz w kierunku bramki. Ten ostatni został wykorzystany jako nasz przeciwnik dla algorytmu uczącego się.
Interfejs programu:
Program tworzy plik z przechowywaną wiedzą gracza uczącego się. Dzięki czemu niewymagane jest uczenie algorytmu od początku każdorazowo po uruchomieniu aplikacji.
Do testów uczenia ze wzmocnieniem został utworzony prosty algorytm starający się poruszać w kierunku środkowej linii boiska oraz w kierunku bramki przeciwnika. Początkowe próby były niezbyt optymistyczne, algorytm uczący się - nie mając żadnej wiedzy - w ogóle nie szedł w kierunku właściwej bramki, co więcej uzyskiwane przypadkowo punkty (w wyniku wykonania przez oponenta ruchu blokującego w rogu planszy) powodowały że coraz częściej chciał się on kierować właśnie w tym błędnym kierunku... Dlatego też przeprowadziliśmy kilka rozgrywek algorytmu uczącego przeciwko człowiekowi, gry te z premedytacją przegraliśmy, co trochę ułatwiło dalsze uczenie. Następne partię gracz uczący się przeprowadzał już ze wspomnianym na początku prostym algorytmem.
Wyniki osiągnięte przez algorytm uczenia ze wzmocnieniem w kolejnych próbach (każda po 99 rozgrywek), ostatnia kolumna przedstawia procent wygranych gier:
Naszemu algorytmowi wykorzystującemu uczenie ze wzmocnieniem nie udało się osiągnąć wysokiego poziomu gry. Wynika to zapewne z ogromnej przestrzeni stanu i niewystarczającego dla tego problemu czasu uczenia, boisko ma bowiem wymiary 8x10, a w każdym punkcie możemy podjąć aż do 8 różnych możliwych akcji. Mimo to końcowe wyniki są dość dobre, wynika to jednak z tego, że przeciwnikiem gracza uczącego się był bardzo prymitywny algorytm. Grając przeciwko człowiekowi lub algorytmowi minimax, potrafiącym ocenić oraz przewidzieć dalszy przebieg rozgrywki, gracz uczący się nie miałby większych szans (albo wymagałby znacznie dłuższego czasu nauki).
[2] Zasady gry [PL] http://pl.wikipedia.org/wiki/Pi%C5%82karzyki_na_papierze
[3] R. Sutton, A. Barto, „Reinforcement Learning: An Introduction”
[4] http://www.ise.pw.edu.pl/~cichosz/um/wyklad/wyklad12/wyklad12.html
[5] http://www.ise.pw.edu.pl/~cichosz/um/wyklad/wyklad13/wyklad13.html