Strategia pokonująca algorytm, głębokość przeszukiwania 0.
Wrocław, 2004-06-12
Bartosz Tarnowski, nr indeksu 139073
Sztuczna inteligencja, U.Wr. 2004
zadanie 4
Celem projektu było zaimplementowanie algorytmu grającego w dwuosobową grę "Piłkarzyki".
Gra toczy się na kratkowanej kartce. Plansza ma kształt prostokątu o parzystych wymiarach z dwoma "bramkami" w kształcie prostokątów 1x2. Polami planszy są punkty przecięcia linii tworzących kratki. Gracze zaczynają ze środkowego pola i wykonują ruchy na przemian. Ruch polega na postawieniu kreski z bieżącego pola do jednego z pól z nim sąsiadujących (z dołu, z góry, z boku lub na ukos). Kreskę można postawić oczywiście tylko wtedy, gdy wcześniej jej w tym miejscu nie było. Można natomiast zakończyć kreskę na polu, które było już zajęte. Jeżeli pole docelowe było puste, to następuje kolej na ruch przeciwnika. Jeżeli było zajęte, to aktualny gracz może wykonać kolejny ruch.
Wygrywa ten z graczy, który trafi do bramki przeciwnika. Jeżeli w pewnym momencie nie można wykonać poprawnego ruchu, to gra kończy się remisem.
Zastosowałem zmodyfikowaną procedurę MiniMax bez obcięć, o stałej głębokości przeszukiwania oraz dwie heurystyki.
Po wykonaniu ruchu inicjatywa może przejść na stronę przeciwnika, ale może też zostać przy aktualnym graczu, albo,
mówiąc innymi słowami, kolejka jednego gracza może zająć kilka ruchów. Dlatego trudno jest zastosować standardowy
MiniMax. Trzeba odróżnić ruchy, po których możemy wykonać następny ruch od takich, po których ruch ma przeciwnik.
Dlatego zastosowałem następujące podejście: niech ocena(pozycja, gracz) będzie funkcją oceny. Wtedy
ocena(pozycjaX, gracz1) = -ocena(pozycjaX, gracz2) (w praktyce nie zawsze tak będzie, ale przybliżenie
jest dobre). Mówiąc innymi słowami: pierwszemu graczowi jest tak dobrze jak drugiemu graczowi źle. Takie podejście
nie jest bynajmniej oczywiste. Można wyobrazić sobie grę, w której obu graczom może być dobrze, obu być źle, lub
jednemu dobrze a drugiemu źle (na przykład gra na planszy nie będącej prostokątem; czasami obu graczom opłaca się
iść w tą samą stronę). Mój algorytm nie sprawdza się w takich sytuacjach. Jednak w większości przypadków pozwala na
zastosowanie następującej sztuczki: jeżeli oceniamy pozycję z punktu widzenia przeciwnika, to bierzemy przeciwieństwo
funkcji oceny, wybieramy liczbę największą i bierzemy przeciwieństwo tej liczby. Jest to część "min" algorytmu
MiniMax. Może się to wydawać trywialne, ale ważne są tutaj wartości funkcji oceny (a nie tylko ich relacje
większa/mniejsza): przeciwnik oceniłby swoją sytuacją tak samo, jak my go oceniamy, ale ze zmienionym znakiem.
Ocena heurystyczna jest prosta: zwraca ona współrzędną y aktualnej pozycji na planszy, licząc środek boiska za
początek układu, czyli im bliżej bramki, tym lepiej. Pozycję z golem oceniamy na 100000 lub -100000, zależnie kto
komu strzelił gola. Ze względu na ograniczenia pamięciowe, wynikła potrzeba następującego przekazywania parametrów
do funkcji oceny: podajemy gracza, głębokość iteracji, pozycję wyjściową (ocenianą) oraz pewien ciąg ruchów. Funkcja
oceny ma za zadanie ocenić pozycję powstałą przez zastosowanie podanego ciągu ruchów do podanej pozycji wyjściowej.
Umożliwia to jednak jeszcze jedną sztuczkę: zmniejszamy ocenę w zależności od długości ciągu ruchów. Daje to pewną
informację nie tylko o tym CZY da się dojść do dobrej pozycji ale także JAK SZYBKO da się do niej dojść. Poza tymi
usprawnieniami dodajemy punkt do oceny jeżeli po wykonaniu ruchu dalej mamy inicjatywę. To właśnie ta reguła sprawia,
że nie zawsze ocena(pozycjaX, gracz1) = -ocena(pozycjaX, gracz2).
Algorytmy sztucznej inteligencji, przebieg rozgrywki i procedury obsługujące grę napisałem w C. Interfejs użytkownika - w C++ z wykorzystaniem biblioteki graficznej QT. Gra chodzi pod Linuxem w środowisku X-Window.
Kompilowałem program poleceniem: g++ *.c *.cpp -DQT_THREAD_SUPPORT -lqt-mt -L/usr/lib/qt/lib.
Plik pilkadisplay.moc.cpp wygenerowałem poleceniem moc -o pilkadisplay.moc.cpp pilkadisplay.hpp.
Plik config.h zawiera definicje zmieniające stosowaną heurystykę i głębokość przeszukiwania.
W pliku main.cpp znajdują się trywialne funkcje graficzne sklejające interfejs graficzny stosowany
w grze z systemem klas QT.
Planszę zapamiętuję jako tablicę rekordów z informacją czy dane pole jest zajęte i czy wykonano z niego ruch w określonym kierunku. Iteracyjną funkcję oceny wykonuję w następujący sposób: przekazuję jej w parametrach początkowy stan planszy, początkowego gracza, początkową pozycję i ciąg ruchów. Funkcja oceny kopiuje aktualną planszę do statycznej tablicy, wykonuje podane ruchy i ocenia otrzymaną pozycję. Taka implementacja pozwala zaoszczędzić pamięć.
Uruchomiłem grę z różnymi głębokościami przeszukiwania i dwoma heurystykami: normalną i osłabioną. Heurystyka osłabiona nie uwzględnia w punktacji długości ruchu i przejęcia inicjatywy przez przeciwnika.
Strategia pokonująca algorytm, głębokość przeszukiwania 0.
Jest to gra przeciwko czystej heurystyce. Program sprawdza, który z możliwych ruchów jest najlepszy według heurystyki i wykonuje go. Ze względu na implementację, najczęściej wybiera drogę prosto do przodu. Człowiek z łatwością rozpracowuje taktykę programu i strzela gola.
Głębokość przeszukiwania 1. Algorytm da się pokonać, ale... Ostatni ruch zaznaczono jaśniejszym kolorem.
Funkcja oceny rozważa wszystkie możliwe ruchy długości 1 od pola, które oceniamy i na tej podstawie podaje wynik. Taki algorytm jest zdolny do drobnych złośliwości, ale znowu można znaleźć prostą taktykę, która go pokona. Należy jednak uważać, gdyż ujawnia się tutaj charakterystyczna cecha mojego algorytmu: tendencja do robienia wielkich sekwencji ruchów przez całe boisko.
Gra bardzo przypomina grę z żywym człowiekiem. Najczęściej zdarza się sytuacja, gdy obaj zawodnicy kopią piłkę w kierunku bandy i dopiero tam toczy się walka o pozycję. Gracz, który ostatni kopnie piłkę przed dojściem do bandy ma mniejsze szanse, dlatego program stara się unikać takiej sytuacji i kopie piłkę prosto do przodu gdy stanie blisko bandy.
Program jest "zachłanny" jak niektórzy ludzie, tzn. kiedy ma możliwość zrobienia kilku ruchów i powrotu do punktu wyjścia, to właśnie tak zrobi. Ma to takie uzasadnienie, że algorytm stara się odcinać przeciwnikowi drogę ucieczki. Są jednak sytuacje, gdy wykonuje cztery "puste" ruchy, a następnie właściwy, silny ruch. Wydaje mi się to dziwne, gdyż program ma możliwość sprawdzenia co najwyżej trzech ruchów od sytuacji wyjściowej. Interpretuję to w następujący sposób: Algorytm nie wybiera od razu właściwego ruchu, gdyż obawia się, że łatwo z niego powrócę i uzyskam mocniejszą pozycję. Dlatego wybiera ruch, na którym nic nie można stracić, czyli skok o jedno pole do tyłu i powrót na początkową linię. Z tej pozycji znowu nie może od razu wykonać właściwego ruchu, dlatego ponawia poprzednią taktykę. Po tych czterech ruchach mam odciętą drogę ucieczki i program nie boi się już wykonać właściwego ruchu. Strategia ta daje algorytmowi dużą przewagę.
Kiedy nadarzy się okazja, algorytm bardzo chętnie wykonuje dalekie skoki przez całe boisko, tak jak przy głębokości przeszukiwania 1.
Program jest silny i nie udało mi się go pokonać.
Program gra bardzo dziwnie. Zamiast kopać piłkę jak najszybciej w kierunku bandy na przemian wykonuje ruchy prosto do przodu i na ukos w kierunku bandy. Nie robi tak przy głębokości przeszukiwania 3, zatem istnieje jakaś sekwencja ruchów długości 4, która daje algorytmowi przewagę. Poza tym grał podobnie jak przy głębokości 3. Nie udało mi się go pokonać.
Dla głębokości 4 program grał tak samo jak przy głębokości 3.
Dla głębokości 5 algorytm mniej chętnie odbijał się od bandy. Kiedy miał możliwość wykonania najpierw krótszego
ruchu, który nie osłabiał jego pozycji, to właśnie ją wybierał. Winna jest prawdopodobnie heurystyka, która nisko
ocenia długie ruchy. Daje ona trzy punkty za jedno pole bliżej bramki i minus jeden punkt za ruch. Zatem sekwencja
pięciu ruchów przybliżająca do bramki o dwa pola jest oceniana na 2 * 3 - 5 = 1, a jeden ruch przybliżający do bramki o
jedno pole na 1 * 3 - 1 = 2.
Dla głębokości 6 algorytm grał podobnie jak przy głębokości 5. Nie wykonywał już ruchów "zachłannych" i nie robił długich podań przez całe boisko. Wydawało mi się, że grał słabiej niż przy głębokości przeszukiwania 3. Czasami wykonywał ewidentdnie słabe ruchy (np. celował we własną bramkę). Mimo to nie udało mi się go pokonać.
Algorytm gra tak samo jak ze zwykłą heurystyką przy głębokości 0.
Algorytm gra tak samo jak ze zwykłą heurystyką przy głębokości 1.
Program grał podobnie jak przy zwykłej heurystyce, ale minimalnie słabiej. Nie udało mi się go pokonać.
Program grał tak jak przy zwykłej heurystyce z głębokością przeszukiwania 3, ale słabiej. Czasami wykonywał słabe ruchy (strzelał w stronę własnej bramki). Nie miał skrupułów, by wykonywać "zachłanne" ruchy. Robił podania przez całe boisko. Bał się odbijać piłkę od bandy.
Program miał te same wady, co przy głębokości przeszukiwania 4. Wykonywał bardzo zachłanne ruchy. Raz udało mu się wykonać sekwencję dwunastu "pustych" ruchów, zanim zdecydował się na kopnięcie piłki do przodu. Prawdopodobnie duża głębokość przeszukiwania pozwala mu stwierdzać, że dana sekwencja jest bezpieczna.
Program miał te same wady, co przy głębokości przeszukiwania 4. Wykonywał jeszcze bardziej zachłanne ruchy niż przy głębokości 5 (rekord - 16 ruchów). Miał opory przed robieniem wielkich sekwencji prosto w bok; prawdopodobnie były one oceniane tak samo jak zwykły ruch o jedno pole do przodu, a w takim wypadku program wybiera w pierwszej kolejności ruchy w kierunku do bramki.
Heurystyka osłabiona była słabsza od normalnej. Różnice w grze z różnymi heurystykami były widoczne dla głębokości przeszukiwania większych lub równych 2. Dla dużych głębokości przeszukiwania program często wydawał się słabszy niż dla małych; prawdpodobnie winne jest złe dostrojenie parametrów - słabsze ruchy były oceniane wyżej, gdyż heurystyka przeceniała znaczenie nieistotnych kryteriów.
Program miał problemy, gdy znajdował się blisko bramki. W tym miejscu zastosowana heurystyka nie dawała dobrej informacji, gdyż kazała kopać piłkę do przodu, w stronę przybramkowej bandy. Dla dużych głębokości przeszukiwania szybciej znajdował ruch prowadzący do gola, jeżeli taki istniał.
Dla głębokości przeszukiwania 0 i 1 algorytm był trywialnie prosty do pokonania. Dla głębokości większych od 1 jego pokonanie było dla mnie niemożliwe, nawet mimo osłabienia heurystyki.
Gra "Piłkarzyki" okazała się prosta dla komputera. Miał na to wpływ mały stopień drzewa przeszukiwań (nie większy niż 8) i trudne dla ludzkiego oka wychwycenie bardzo długich możliwych sekwencji ruchów, które często komputer wykorzystywał. Najbardziej zbliżony do stylu ludzkiej gry był sposób gry przy głębokości przeszukiwania 2, dlatego wnioskuję, że człowiek planuje trzy ruchy do przodu podczas gry w "Piłkarzyki".
Należałoby sprawdzić, jak program zachowuje się w czasie gry na nieprostokątnej planszy. Wyzwaniem byłoby napisanie heurystyki, która automatycznie dopasowuje się do kształtu planszy.