Wrocław, 1 lipca 2009

Raport opracowany na zaliczenie przedmiotu.
Nazwa: Metody i algorytmy sztucznej inteligencji
Kod kursu: ARE3513

Zastosowanie uczenia ze wzmocnieniem do rozwiązywania problemu gry Saper

Autor: Rafał Toboła, 149151

Poniższa praca prezentuje wyniki z próby zaadaptowania uczenia ze wzmocnieniem do rozwiązania problemu gry Saper. Algorytm który został zaimplementowany to Q-learning. Okazuje się że Saper to nie jest prosty problem, którego maszyna mogłaby łatwo się nauczyć.

---

Wrocław, 1st July 2009

Report has been prepared as a requirement for the course.
Name: Methods and algorithms of artifical intelligence
Course code: ARE3513

Application of reinforcement learning to solve the problem of the game Minesweeper

Author: Rafał Toboła, 149151

This work presents results of experiments with adapting reinforcement learning to solve problem of Minesweeper. Algorithm which has been implemented was Q-learning. It occurs that Minesweeper isn't simple problem, which machine can easly learn.

---

Wstęp

Saper jest prostą grą dołączaną do systemów Microsoft Windows od 1991 roku. Gracz ma w niej za zadanie odkrycie wszystkich pól na planszy, które nie są minami. Po odkryciu pola pojawia się na nim liczba, która określa ile jest min w sąsiedztwie tego pola. Jeżeli gracz odkryje minę - przegrywa. Możliwe jest też oznaczanie miejsc na mapie, jako miejsca w których naszym zdaniem są miny. Na przestrzeni ostatnich lat, powstało wiele strategii dla graczy oraz algorytmów próbujących rozwiącać problem sapera. Z punktu widzenia programisty, saper jest problemem NP-zupełnym.

Saper, a uczenie ze wzmocnieniem

Problem sapera możę zostać rozwiązany przy pomocy uczenia ze wzmocnieniem. Największym problemem jaki musimy tutaj pokonać jest ogromna przestrzeń stanów. Jeżeli przyjmiemy że w każdym z pól mogą pojawić się wartości: 1, 2, 3, 4, 5, 6, 7, 8 oraz pole puste, to dla planszy 4 × 4 mamy 3,6 · 10¹³; kombinacji! Okazuje się jednak, że konfiguracji poprawnych jest tylko 3,2 · 10⁶; [1], czyli o 10 milionów razy mniej! Jest to jednak nadal ponad milion, co odbija się na zużyciu pamięci. Biorąc pod uwagę średnią ilość pamięci jaką posiadają obecne komputery osobiste, nie jest możliwe rozwiązanie problemu sapera dla plansz większych niż 4 × 4 korzystając z metody uczenia ze wzmocnieniem.

Implementacja

Początkowo planowano skorzystać z źródeł sapera znalezionych pod adresem [2]. Szybko jednak okazało się, że istnieje wersja specjalnie przygotowana do testowania własnych algorytmów rozwiązywania tego problemu [3]. Interfejs programu przedstawiony został na poniższym rysunku.

Kolorem żółtym zaznaczone są zakryte miny, kolorem czerwonym miny na które ,,wpadł'' gracz, kolorem niebieskim pola oznaczone przez gracza jako pola pod którymi znajdują się miny, a cyfry pojawiają się w odkrytych przez gracza polach, w których nie było min. Program umożliwia napisanie własnej strategii (w formie klasy dziedziczącej ze Strategy), a następnie obserwowanie jej działania. Możliwe jest też uruchomienie określonej liczby gier, program zwraca wtedy wyniki w formie tekstowej.

Jako algorytm uczenia ze wzmocnieniem wykorzystano Q-learning. Testy, z powodów przedstawionych w poprzednim punkcie przeprowadzono tylko dla plansz o wymiarach 3 × 3 oraz 4 × 4. Do celów badań zmienione zostało źródło gry. Parametry jakie przekazać można do programu przedstawione zostały poniżej.

• -b - początkujący poziom trudości (10 min, plansza 8 × 8)
• -i - średniozaawansowany poziom trudności (40 min, plansza 13 × 15)
• -e - zaawansowany poziom trudności (99 min, plansza 16 × 30)
• -custom - plansza użytkownika
• -mines - liczba min
• -rows - liczba wierszy
• -columns - liczba kolumn
• -boom_reward - nagroda (kara) za odkrycie miny
• -no_boom_reward - nagroda za odkrycie pola bez miny
• -memory - rozmiar pamięci
• -s - wybrana strategia
• -n - ilość gier do rozegrania

Przykładowe wywołanie programu:
java -jar bin.jar -custom -s my.MyStrategy -n 50000 -rows 4 -columns 4 -mines 4 -boom_reward -25 -no_boom_reward 1 -memory 2500 > wyniki.txt

Wyniki zwracane przez program były automatycznie parsowane przez program napisany w jężyku ruby, a następnie przesyłane do programu octave, który generował wykresy wydajności uczenia się.

Badania

Badania przeprowadzono dla plansz o wymiarach 3 × 3 (przy 1-8 min) oraz 4 × 4 (przy 1-15 min). Zaimplementowana strategia rozgrywała 1.000, 10.000 lub 50.000 gier, przy rozmiarach pamięci 200, 500, 1.000, 2.000, 5.000, 10.000, 50.000. Kary za przegraną wynosiły -10 lub -100, a nagrody za odkrycie niezaminowanego pola 10 lub 1. Ponieżej przedstawiono przykładowe wykresy.

Podsumowanie

Okazuje się że problem gry w Sapera nie daje się łatwo rozwiązać poprzez metodę uczenia ze wzmocnieniem. Dla przykładu na planszy 4 × 4 z jedną miną, strategia korzystająca z metody Q-learning wygrywa tylko w niecałych 7% przypadków, natomiast zwykła matematyczna strategia EqnStrategy, zaimplementowana przez autora programu PGMS [3], w 100%! Uczenie się tylko tych przypadków, których nie da się rozwiązać matematycznie, wydaje się również mało skuteczne, gdyż są to przypadki losowe, w których wszystkie kombinacje pojawiają się z tym samym prawdopodobieństwem.

Bibliografia

[1] Preslav Nakov, Zile Wei. MINESWEEPER, #MINESWEEPER. http://www.cs.berkeley.edu/~zile/CS294-7-Nakov-Zile.pdf.
[2] Źródło gry saper napisanej w Javie. http://timvandenbulcke.objectis.net/minesweeper-in-java/minesweeper.zip/view.
[3] Programmer's Minesweeper. http://www.ccs.neu.edu/home/ramsdell/pgms.