Rysunek 1. Przykładowe Bazy.
Metody i algorytmy sztucznej inteligencji
Prowadzący: dr inż. Witold Paluszyński
Gra w kropki
Raport z dużego zadania wykonanego w ramach projektu.
Politechnika Wrocławska, Wydział Elektroniki, AiR (ARR) IV rok.
Przemysław Sperzyński
Wrocław, 5 lipca 2007
1. Opis problemu.
Celem Projektu była próba zaimplementowania gracza komputerowego do popularnej gry w kropki. Jest to gra szczególnie popularna w Polsce i Rosji. Określana jest jako modyfikacja znanej na całym świecie gry w GO. W internecie są fora dyskusyjne i programy turniejowe do gry lecz jest niewiele programów, które pozwalałyby na ćwiczenie gry z graczem komputerowym, bez potrzeby łączenia się poprzez internet.
Jednym z programów dostępnych do gry off-line jest program napisany przez Pana Bartka Dydę. Jest to program typu open-source dostępny pod licencją GNU GPL. Moim Celem będzie próba implementacji kolejnego gracza komputerowego, który wygrywałby z już istniejącym.
2. Opis gry.
Poniższy opis jest w całości zamieszczony z opisu gry umieszczonego na portalu pl.wikipedia.org [1], i nie jest w jakikolwiek sposób edytowany.
Kropki to gra strategiczna polegająca na otaczaniu kropek przeciwnika własnymi kropkami. Jest to go przeniesione na kartkę papieru, jednak niewielkie różnice zasad związane z innym rodzajem planszy, sprawiły że rozgrywka w kropki bardzo się różni od go. Do gry wystarczy kartka w kratkę i dwa długopisy (bądź kredki, flamastry) w różnych kolorach; dzięki temu i prostym zasadom kropki zyskały popularność wśród młodzieży szkolnej.
2.1. Zasady
Na początku gry plansza jest pusta, ruch polega na postawieniu kropki na pustym przecięciu linii. Gracze wykonują ruchy na przemian, starając się otoczyć przeciwnika - gdy to się uda, kropki otaczające łączy się linią i powstaje baza (rys. 1) lub stop (takim słowem niekiedy określa się samo utworzenie bazy). Linię można poprowadzić między kropkami, jeśli są one oddalone o jedną kratkę w pionie, poziomie lub na ukos. W odróżnieniu od go otoczonych kropek nie da się usunąć. Jest to największa różnica między tymi grami.
Rysunek 1. Przykładowe Bazy.
Wielkość kartki na której się gra jest dowolna, najczęściej stosuje się kartkę z zeszytu formatu A5. W kropki zwykle gra się w dwie osoby, jednak w rozgrywce może brać udział więcej graczy, pod warunkiem że każdy używa innego koloru. Gra kończy się z chwilą zapełnienia całej kartki, lub do momentu gdy jeden z graczy się podda, albo obaj się zgodzą skończyć grę i podliczyć punkty.
2.2. Niedozwolone ruchy.
Rysunek 2. Niedozwolone ruchy.
2.3. Liczenie punktów
Często po zakończeniu gry na pierwszy rzut oka widać, kto wygrał, jednak w przypadku wyrównanej rozgrywki konieczne może się okazać podliczenie punktów. Punkty otrzymuje się za każdą otoczoną kropkę przeciwnika, oraz traci za otoczone własne kropki, nie ma jednak jednego systemu punktacji, zależy od tego co ustalą na początku gracze. Można stosować zróżnicowaną ilość punktów - np. +2pkt. lub +3pkt. za kropki tworzące bazę przeciwnika, -2pkt., -3pkt. za otoczoną własną kropkę, jednak pojawiają się problemy typu: Ile punktów dać za własną kropkę czy bazę w otoczonej bazie przeciwnika?
2.4. Podstawowe pojęcia
Terminologia gry nie jest ustalona odgórnie i często gracze tworzyli ją na własne potrzeby, dlatego też poniższe pojęcia mogą mieć różne nazwy.
3. Metoda i Implementacja.
3.1. Zastosowany Algorytm.
Dla własnego gracza zastosowałem algorytm minimax opisany na stronie [5]. Do oceny stanu gry w kolejnych krokach, posłużyłem się informacją o zamkniętych kropkach, zarówno swoich jak i przeciwnika. Wzór funkcji celu przedstawia się następująco:
F(x,y) = k1*Waznosc(x,y) + k2*Minimax(zajetych_kropek - straconych_kropek)
gdzie:
x,y - współrzędne postawionej kropki na planszy.
k1,k2 - niezerowe współczynniki,spełniające zależność 0 < k1 << k2.
Waznosc (x,y) - poziom ważności danej kropki.
Ważność kropki, jest to wartość z przedziału <-1,1>, przyporządkowana wg. szablonu, jeżeli postawienie kropki w punkcie x,y pasuje do szablonu to otrzymuje ona dany poziom ważności. Szablony przedstawia tab. 1.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tabela 1. Szablony oznaczające ważność danej kropki.
Biała kropka z czarną obwódką w środku każdego szablonu oznacza, rozpatrywaną pozycję na planszy. Biała oznacza Wolne pole, niebieska oznacza kropkę postawioną przez nas i odpowiednio czerwona przez przeciwnika. Kropki różowa i błękitna oznaczają że w danym miejscu może być postawiona kropka (przez nas - błękitna, przez przeciwnika - różowa), lecz nie musi więc może być tam również wolne pole.
Przedstawione są powyżej 33 szablony, które oczywiście nie oddają wszystkich sytuacji na planszy. Wartości ważności danych sytuacji są przyporządkowane według własnych odczuć. Przy sprawdzaniu poprawności danej sytuacji, należy sprawdzić zarówno lustrzane odbicia szablonów (pionowe jak i poziome), jak i zarówno ich rotację. Daje to dużą liczbę 33*16=528 różnych szablonów. Jednak jak można zauważyć szablony te są w większości symetryczne więc ich liczba nie zwiększa się tak drastycznie (dokładnie jest to liczba 190 szablonów).
Wyrażenie Minimax() we wzorze na funkcję F oznacza wartość zamkniętych kropek przeciwnika i swoich. Różnica ta jest obliczana tylko w liściach drzewa przeszukiwań algorytmu minimax. Następnie przekazywana jest rekurencyjnie wyżej ku korzeniowi, zgodnie z definicją algorytmu, raz brane jest pod uwagę minimum wartości, a następnie maksimum.
Jeżeli dana pozycja na planszy nie pasuje do żadnego z szablonów, to można przyjąć jej ważność na poziomie 0,05 lub niższym. Dodatkowo sprawdzanie pozycji nie odbywa się, biorąc pod uwagę wszystkie kropki, lecz w marginesie danym przez daną sytuację na planszy. Za każdym razem obliczany jest prostokąt obejmujący wszystkie kropki na planszy, powiększany jest o 1. Następnie sprawdzane są pozycje tylko w tym prostokącie. Zmniejsza to ilość wierzchołków drzewa przeszukiwania. Jest to spowodowane także tym iż kropki postawione dalej od już wstawionych na planszy nie powodują zamknięcia żadnego obszaru, w krótkim czasie. rys. 3 przedstawia, wcześniej wspomniany prostokąt, ograniczający pole przeszukiwań. Białe kropki na rys. 3 przedstawiają pozycje które zostaną rozwinięte na drzewie przeszukiwań, do dalszego zbadania.
Rysunek 3. Margines ograniczający pole przeszukiwań.
3.2. Implementacja.
W celu implementacji, posłużyłem się programem napisanym przez Pana Bartka Dydę [4]. Jest to program, niekorzystający z jakichkolwiek bibliotek graficznych prócz X11. Dopisałem własnego gracza do istniejącego programu, zastępując gracza ludzkiego. W ten sposób tuż po uruchomieniu aplikacji, obydwoje graczy komputerowych (istniejący - niebieskie kropki i mój dopisany - czerwone kropki) automatycznie zaczyna grę. rys. 4 przedstawia obraz gry, po uruchomieniu.
Rysunek 4. Zrzut ekranu gry w kropki.
Współrzędne planszy są liczone tak jak współrzędne ekranowe, tzn. od górnego lewego rogu (punkt o współrzędnych 0,0) do dolnego prawego rogu (punkt o współrzędnych wlkx-1,wlky-1). Zmienne wlkx, oraz wlky są zmiennymi globalnymi. W celu otrzymania informacji o postawionych kropkach na planszy służy funkcja WezUC. Należy jednak podać współrzędne x, y o 2 większe czyli wywołując tą funkcję należy podawać w liście argumentów x+2,y+2, aby otrzymać informację o stanie planszy. Informacja o postawionych kropkach znajduję się w obiekcie gra klasy TGra,w tablicy rozgr. Następną potrzebną tablicą jest plansz_p, która przetrzymuje informację o polach zamkniętych. Jeżeli funkcja WezUC wywołana z wskaźnikiem na tablice plansz_p zwróci 0 to oznacza że pole jest niezamknięte. Następnie funkcja WezUC wywołana z argumentem rozgr, zwróci 0 to oznacza ze tam nie ma kropki, 1 oznacza kropkę pierwszego gracza oraz analogicznie 2 kropkę drugiego gracza.
Kolejną ważną funkcją programu jest funkcja WykonajRuch, która stawia kropkę na planszy, sprawdza czy ona zamyka jakiś teren, oraz aktualizuje punktacje gry. Funkcja ZrobPanstwo sprawdza czy postawiona kropka zamyka teren aktualizuje tablice podane jako parametr oraz zwraca ilość zdobytych punktów. Jest to przydatna funkcja ponieważ nie korzysta ona z globalnej planszy gry lecz tylko z podanych parametrów.
Aby skopiować stan gry do swoich tablic, należy korzystać z obiektu plansze, który mam metody alokujące, czyszczące, oraz zwalniające tablice. Dzieje się tak ponieważ w programie wszystkie plansze także te tworzone na potrzebę analizy trzymane są na jednym stosie przetrzymanym właśnie w obiekcie plansze.
Własny gracz zapisany jest w klasie CPlayer. W momencie ruchu człowieka w pętli głównej programu, wykonywana jest metoda doTheJob która zwraca pozycję kropki do postawienia. Wyżej opisane szablony reprezentowane są poprzez klasę CTemplate, a zebrane są w jedną kolekcję w klasie CTemplateCollection.
4. Testy.
4.1. Cechy istniejącego gracza komputerowego.
Przy testowaniu programu, zauważyłem iż zaimplementowany gracz, stawia pułapki które przydają się w ostatniej części rozgrywki. Rys. 5 przedstawia sposób stawiania kropek przez gracza komputerowego. Jeżeli skończą się wolne pozycje na planszy, zostają takie pozycje jak białe zaznaczone na rys. 5. Postawienie kropki w takim polu powoduje natychmiastowe zamknięcie kropki.
Rysunek 5. Pułapki stosowane przez gracza komputerowego.
Aby takich pułapek uniknąć utworzyłem 34 szablon, który będzie promował blokowanie stawiania takich pułapek. Rys. 6 przedstawia stworzony szablon. Następnie zbadałem jaka wartość ważności daje najlepsze efekty dla tego szablonu. Po testach wynika że najskuteczniej mój gracz, gra dla wartości 0,8.
Rysunek 6. Dodatkowy 34 szablon.
4.2. Testy algorytmu.
Rysunek 7. Zrzut ekranu zmodyfikowanego programu.
Wszystkie testy wykonałem dla planszy wielkości 10x10, co przedstawia rys. 7. Daje to liczbę 100 pól, co i tak powoduje że drzewo przeszukiwania będzie się szybko rozrastać.
Na początku zacząłem testować program przy zagłębieniu 1. Ku zaskoczeniu przy braku zagłębiania się w przeszukiwaniu, jego skuteczność wynosi około 50% wygranych partii. Przy zwiększeniu zagłębienia do 3 pojawia się problem z wydajnością ponieważ algorytm w jednym kroku sprawdza około 100000 ruchów, co zajmuje mu dużo czasu. Ponadto zauważyłem iż spada jego efektywność.
5. Wnioski.
Po przeprowadzeniu testów, pierwszy wniosek jaki się nasuwa, jest taki, iż należy znacznie ograniczyć ilość sprawdzanych ruchów, poprzez obcięcie Alfa-Beta. Ponadto zauważyłem iż odpowiedni dobór szablonów lepiej wpływa na efektywność gracza, niż zwiększanie głębokości drzewa przeszukiwań. Kolejno duży wpływ ma także wartość ważności dla danego szablonu. Zauważyłem to przy sprawdzaniu szablonu który by blokował wcześniej opisane pułapki.
Skłania to do konkluzji iż lepiej zastosować tu algorytm uczenia ze wzmocnieniem, który dodawałby i modyfikował odpowiednio kolekcję szablonów. Następnie taki algorytm, który premiowałby i karał ruchy, poprzez zmianę ważności istniejących szablonów.
6. Bibliografia.
