Raport do projektu wykonanego w ramach przedmiotu Sztuczna Inteligencja

Wirtualny gracz w warcaby

7.06.2006 Politechnika Wrocławska

Wykonał: Paweł Rak
Przedmiot: Metody i algorytmy sztucznej inteligencji
Prowadzący: dr inż. Witold Paluszyński
Opis zadania
Zadanie polega na napisaniu algorytmu grającego z użytkownikiem w warcaby z zachowaniem zasad gry oraz stuprocentowej uczciwości. Ze względu na dużą popularność gry nie opisuje zasad. Zasady gry można przeczytać na http://www.warcaby.beep.pl

Użyte pojęcia przy opisanej metodzie rozwiązania zadania

 Stan początkowy - początkowe ustawienie pionków na planszy
Stan końcowy - wygrana, przegrana bądź remis osoby rozpoczynającej grę
Drzewo gry- wszystkie możliwe ustawienia pionków od stanu początkowego do stanu końcowego
Stan gry - aktualna sytuacja na planszy
Opis zastosowanej metody rozwiązania zadania
Algorytm:

Do rozwiązania problemu użyłem metody stosowanej w większości grach logicznych tj. algorytmu MinMax. Algorytm MinMax zakłada istnienie dwóch graczy: gracz Max oraz gracz Min. Grę zaczyna gracz Max,  gracz Max wykonuje najlepszy z możliwych swoich ruchów tzn. taki, po którym gracz Min da  jak najgorszą odpowiedź. Jak znaleźć taki ruch? Najlepiej byłoby przeanalizować wszystkie możliwe posunięcia ze stanu początkowego gry do stanu końcowego, jednak jest to niemożliwe ze względu na ogromną złożoność obliczeniową przeszukiwania oraz budowy drzewa gry. Drzewo gry budujemy do pewnego poziomu, do którego jesteśmy w stanie w rozsądnym czasie znaleźć najlepsze nasze posunięcie. Na poniższej ilustracji pokazano sposób wyboru ruchu prze algorytm MinMax.
minmax
W liściach drzewa zapisane są liczby oznaczające sytuacje na planszy po wykonaniu kolejno ruchów od stanu początkowego. Wartością wierzchołka Max w drzewie będzie maksimum z wartości w jego synach, natomiast wartością dla wierzchołka Min jest minimum z wartości w jego synach. Pamiętajmy o tym, że z wierzchołka wychodzi więcej gałęzi, wybieramy gałąź, w której znajduje się wartość maksymalna. W ten oto prosty sposób znajdujemy najlepszy dla nas ruch.

Ten oraz inne algorytmy są opisane w pracy ([1]).

Funkcja oceniająca:

Ostatnim pytaniem jest jak ocenić sytuacje na planszy? Ocenę sytuacji można dokonywać na wiele sposobów, należy pamiętać jedynie o złożoności obliczeniowej funkcji oceniającej i skuteczności jej działania, należy znaleźć kompromis pomiędzy złożonością obliczeniową a skutecznością oceny. W swoim algorytmie, oceny dokonuje na podstawie ilości pionków. Pionki mają po jeden punkt a damki po trzy, sumuje punkty Max-a i Min-a, odejmuje od siebie i otrzymuje ocenę - stan gry.

Pomysł na funkcje oceniającą zaczerpnąłem ze strony http://www.wpk.p.lodz.pl/~pawian/warcaby/algorytm.html
 
Opisany algorytm został zaimplementowany w c++ w Borland Builder6.0. Wszystkie użyte funkcje w algorytmie zostały napisane przeze mnie od podstaw. Pracę nad programem rozpocząłem od definicji pionków, damek oraz ich ruchów i bić. W kolejnym etapie napisałem rekurencyjną funkcje budowy drzewa gry oraz ocenę i wybór ruchu.

Wyniki działania programu
Najbardziej interesujące wyniki jakie może przedstawić tego typu algorytm to to czy jest w stanie wygrać, jeśli tak po ilu ruchach oraz jaki czas zajmuje mu wybór ruchu.

Sposób pomiaru czasu:

Podczas pojedynczej gry mierzyłem czas każdego wykonanego ruchu przez algorytm i na końcu gry obliczałem średnią arytmetyczną, uzyskałem w ten sposób średni czas działania algorytmu przy wykonaniu pojedyńczego ruchu. Wyniki umieszczam w poniższej tabeli.

ilość faz
Max+Min
 czas
[s]
1
 0
2
 0
3
 0,015
4
 0,125
5
 0,965
6
 6,422
7
 57,531

Z przedstawionych w tabeli wyników widać, że czas trwania obliczeń dla pojedyńczego posunięcia gwałtownie wzrasta po przekroczeniu głębokości drzewa 5, jeszcze dla głębokości 6 można z programem grać i świetnie się bawić, jeśli głębokość zwiększymy do 7 zmuszeni jesteśmy do długiego oczekiwania na ruch komputera co powoduje, że gra staje się nudna i uciążliwa.
Jeśli chodzi o skuteczność wykonywanych ruchów przez algorytm testy przeprowadziłem dla głębokości 4, 5, 6 i 7, ponieważ dla niższych głębokości algorytm jest mało skuteczny i mógłby wygrać tylko graczem, który rozegrał kilka partii w życiu, natomiast dla głębokości większej od 7 na przeszkodzie stoi czas obliczeń prowadzonych przez algorytm.
Wraz ze wzrostem głębokości drzewa algorytm wykonuje coraz lepsze posunięcia i po osiągnięciu głębokości 5 jego ruchy stają sie całkiem sensowne i radzi sobie całkiem nieźle. Dla głębokości 6 aby wygrać z algorytmem należy już więcej pogłówkować i dla tej głębokości algorytm potrafi wygrać z graczem który popełni błąd lub obierze kiepską taktykę. Niestety jeśli porównać mój algorytm z innymi grami to wypada on bardzo słabo, spowodowane to głównie jest głębokością drzewa.

Wnioski
Głównym wnioskiem do tego projektu jest fakt o coraz lepszej grze komputera przy zwiększającej się ilości możliwych do przewidzenia ruchów oraz, że wraz ze wzrostem przewidywanych ruchów drastycznie wzrasta czas obliczeń. Do uzyskania "wirtualnego gracza", który będzie grał na wysokim poziomie czysty algorytm MinMax nie wystarcza,  należy zastosować bardziej efektywne algorytmy, które zostały opisane w pracy ([1]).


Materiały źródłowe
[1] Paweł Pelc, Zastosowanie metod przeszukiwania heurystycznego w grach opartych na zasadach warcabów.,Praca magisterska napisana pod   kierunkiem prof. dr hab. Krzysztofa Lorysia