Funkcja oceniająca do algorytmu minimaksu w grze warcaby

RAPORT Z PROJEKTU KURSU:
METODY I ALGORYTMY SZTUCZNEJ INTELIGENCJI, ARE3513

AUTOR:Michał Mielnicki
PROWADZĄCY:dr inż. Witold Paluszyński
DATA:18 czerwca 2009

Evaluate function for mimax algorithm in chceckers.

THIS REPORT DESCRIBES A PROJECT DONE TO FULFILL THE REQUIREMENTS FOR THE COURSE:
METHODS AND ALGORITHMS OF ARTIFICIAL INTELLIGENCE, ARE3513

AUTHOR:Michał Mielnicki
CONDUCTED BY:dr inż. Witold Paluszyński
DATE:June 18th, 2009

DESCRIPTION:

This report describes evaluate function for minmax algorithm. My task was to write an evaluate function, that can compete with human. I created few functions and then i consolidated them into one function that evaluate numer for minmax algorithm.

1 Wstęp:

Problemem do rozwiązania jest zbudowanie odpowiedniej strategii gracza w grze warcaby. Moim zadaniem jest napisanie funkcji oceniającej do gotowego algorytmu minimaksu dostępnego na stronie kursu (aplet). Temat jest bardzo popularny, jednak ciężko znaleźć fachowe informacje. Większość informacji przedstawia jedynie algorytmy przeszukiwania (szczególnie min-max) i tylko wspomina o funkcji oceniającej. Funkcja napisana przeze mnie w Javie zawiera skondensowane informacje na temat strategii gracza znalezione w internecie.

2. Krótko o algorytmie minimaksowy

Algorytm min-max polega na przeszukiwaniu wszystkich możliwych ruchów w celu wykrycia optymalnego zagrania. Każdej sytuacji na planszy przyporządkowania zostaje liczba zależna od stanu gry. Na podstawie tej gry program wybiera najlepszą ścieżkę i wykonuje związany z nią ruch. Algorytm. przeszukuje zarówno ruchy obydwu graczy. Np. jeśli gracz nr 1 sprawdza dopuszczalne ruchy to algorytm będzie szukał maksymalnej ścieżki wśród możliwych ruchów gracza i minimalnej wśród ruchów jego przeciwnika. W ten sposób znajdywana jest najlepsza ścieżka z punktu widzenia gracza nr 1.
Algorytm minmax
Dobrym sposobem na zmniejszenie ilości przeszukiwanych ruchów jest sprawdzanie ich dopuszczalności. Pozwala to zmniejszyć straty obliczeniowe na samo przeszukiwanie.

3. Funkcja oceniająca

3.1. Ilość i rodzaj pionków

Podstawowym elementem oceny strategii gracza jest sprawdzenie siły bojowej graczy. Jest to również najprostszy do zaimplementowanie element strategi gracza. Polega na przeszukaniu całej szachownicy w poszukiwaniu pionków gracza i jego przeciwnika. Znalezione pionki/damki sumuje się z odpowiednimi wagami i dodaje do całkowitej wartości zwracanej przez funkcje oceniającą.

3.2. Znajdywanie bić

Najważniejszym elementem w warcabach jest zbicie pionków przeciwnika. Bez tego nie da się wygrać rozgrywki. Dlatego zaimplementowanie wykrywania możliwości bić było jednym z kluczowych elementów. Wykrywanie bić polega na przeszukiwaniu szachownicy w celu znalezienia pionków gracza i przeciwnika znajdujących się obok siebie, a następnie sprawdzeniu, czy jest możliwość zbicia pionka, tzn. czy za pionkiem znajduje się miejsce puste. Jeśli tak to do końcowej wartości zwracanej przez funkcję jest dodawana odpowiednia stała określająca bicie.
Wykrywanie bic

3.3. Wykrywanie wielokrotnych bić

Istotnym elementem strategii gracza jest zbicie większej ilości pionków niż przeciwnik. Dlatego ważnym elementem jest sprawdzanie wielokrotnych bić. Aby tego dokonać należy zmodyfikować przedstawiony powyżej algorytm wykrywania bić i dodać do niego rekurencyjną funkcję przeszukiwania dalszych możliwości posunięć. W przypadku pionków nie ma problemu, gdyż w zamieszonym na stronie internetowej kursu nie mają one możliwości bicia do tyłu, przeszukiwanie wielokrotnych bić nigdy nie jest głębsze niż 3 (wynika to budowy szachownicy). W przypadku damki sprawa się nieco komplikuje, gdyż należy sprawdzać również możliwość bicia do tyłu. W przypadku damki istnieje ryzyko zapętlenia się ruchów, co prowadzi do zawieszenia działania całego programu. Aby temu zapobiec wprowadzono mapę pionków zbitych. Po zbiciu pionka funkcja oceniająca zapamiętuje jego pozycję i przy kolejnych próbach bicia tego samego pionka (tylko w przypadku damki) będzie on widziany przez program jako pole puste.
Wielokrotne bicie

3.5. Opłacalność wymiany

Opłacalność wymiany bić jest najważniejszym elementem strategii gracza. Można ją rozumieć na kilka sposobów i jest ona bardzo trudnym elementem do zaimplementowania. Po pierwsze opłacalność jako wielokrotne bicie pionków przeciwnika, podczas pojedynczego bicia przez przeciwnika. Drugi aspekt to wymiana pionków po której nastąpi (w kolejnym ruchu) zbicie przeciwnikowi pionka (bądź kilku) bez żadnej straty. Kolejna interpretacja opłacalności działania to celowe oddanie pionka w celu zmiany położenia pionka przeciwnika, która np. wprowadzi go w blokadę, lub umożliwi przejście pionkowi gracza np. w celu stania się damką.

3.6. Poziomy

Damka jest najsilniejszą figurą (z resztą też jedyną) w warcabach, gdyż posiada możliwość poruszania się w każdym kierunku. Aby pionek stał się damką musi dotrzeć do tzw. linii promocji, czyli przeciwległej krawędzi szachownicy. Wykonując każdy ruch pionkiem i tak zbliża się on do linii promocji. Po co więc zajmować się tym zagadnieniem? Po to aby ruchy nie były losowe, tylko zorganizowane i przemyślane. Można poruszać najbardziej wysuniętym pionkiem, aby jak najszybciej dotrzeć do linii promocji, albo najbardziej oddalonym, aby wszystko pionki przesuwały się z taką samą prędkością. W moim algorytmie wybrałem tę drugą możliwość. Uznałem, że pionki poruszające się w grupie dają większą możliwość bojową, niż pojedynczy kamikadze. Uwzględniłem jednak sytuację, w której najbardziej wysunięty pionek ma możliwość bezstratnego przejścia do linii promocji (sytuacja, gdy przed nim nie znajdują, i nigdy nie znajdą się pionki przeciwnika). Wtedy ma on możliwość szybkiego stania się damką i powrócenia na pole bitwy aby wspomóc pozostałe na polu walki siły.
poziomy_4
Rysunek przedstawiający poziomy. Najbardziej punktowany jest poziom 4 i kolejno następnie mniej
poziomy

3.7. Funkcja krawędziowa

Funkcja krawędziowa polega na zapobieganiu poruszania się pionków w skrajnych polach szachownicy. Zmniejsza to znacznie ich możliwości ruchowe. Pionki znajdujące się w obszarze I są najlepiej punktowane a w obszarze III najgorzej.
obszary
Rysunek przedstawia Podział na obszary.
funkcja krawedziowa
Powyższy rysunek przedstawia przykład działania funkcji.

3.8. Bezpieczeństwo

Aby zbudować dobrego gracza powinien on nie tylko szukać wymiany, oraz możliwość zbijania pionków przeciwnika, ale również dbać o tyły. Defensywna jest równie ważna jak ofensywa, gdyż przeciwnik także stara się zbić jak najwięcej pionków. Bezpieczeństwo pionków to jedno z najbardziej rozbudowanych zagadnień w całej strategii gracza. Uznaje się, że pionek jest bezpieczny, gdy przeciwnik nie ma możliwości jego zbicia. W praktyce oznaczało by to, że najlepiej poruszać się po krawędziach szachownicy, gdyż pionek znajdujący się tuż przy linii bocznej nie może być w żaden sposób zbity. Czy jest to dobre rozwiązanie? Każdy gracz odpowie NIE. Dlaczego? Gdyż po pierwsze pionek znajdujący się przy krawędzi ma tylko jedną możliwość ruchu. Przeciwnik może to wykorzystać i ustawić swoje pionki w taki sposób, aby ruch tego pionka wystawiał go na zbicie. Po drugie ustawianie pionków na brzegach szachownicy powoduje zwolnienie środka, co daje przeciwnikowi przewagę w najważniejszej środkowej strefie. Dobrą strategią jeśli chodzi o bezpieczeństwo jest premiowanie takich posunięć, aby zapobiec przeciwnikowi zbicie pionka. W praktyce sprowadza się to do ustawiania (w razie potrzeby) pionka za pionkiem, który może być zbity.

3.9. Zapobieganie lukom

Sposób poruszania się pionków w wolnym przypadku (brak bić, niebezpiecznych sytuacji) nie powinien być losowy. Pionki powinny się poruszać w taki sposób, aby nie tworzyć niepotrzebnych luk pomiędzy nimi. Powinny poruszać się w szeregu. W tym celu algorytm zaimplementowany przeze mnie wykrywa luki (więcej niż jedno pole) pomiędzy pionkami i premiuje takie ruchy, które maja na celu zniwelowanie tej luki. Rozciąga to pole manewru pionków, zwiększa ich mobilność, gdyż na wzajem sobie nie przeszkadzają, oraz zmniejsza możliwość prześliźnięcia się przeciwnika pomiędzy pionkami gracza.

3.10. Poruszanie się grupami

Poruszanie się grupami polega na taki ustawianiu pionków aby poruszały się one w kierunku zwiększonego natężenia pionków przeciwnika. Aby wykryć grupy pionków przeciwnika podzielono obszar na mniejsze pod obszary o rozmiarach 4x4. Obszary te dzielą szachownicę w poziomie na dwie równe części a w pionie przemieszczają się co 2 pola. Do każdego sprawdzanego ruchu pionka dodawane jest odpowiednia stała odpowiedzialna za premiowanie ruchów w kierunku grup pionków przeciwnika.

3.11. Ryzyko blokady

Ważnym elementem jest wykrywanie możliwości zablokowania pionka gracza, przez przeciwnika. Takie nieporządne rozmieszczenie jest w przypadku, gdy pionek gracza nie ma możliwości ruchu, tzn. że na drodze pionka gracza znajduje się pionek uniemożliwiający wykonanie ruchu, a za nim następny (bądź pionek gracza) uniemożliwiający zbicie pionka przeciwnika. Wykrywanie takich blokad pozwala także na zapobieganie tunelom tworzonym się w czasie rozgrywki. Tunel polega na tym, że pionki ułożone są w dwóch rzędach, pomiędzy którymi znajduje się luka umożliwiająca przejście innego pionka bez możliwości zbicia go przez przeciwnika. Blokowanie jest nieporządanym efektem, dlatego powinno być mocniej punktowane, niż np. poruszanie się w kierunku grupy pionków przeciwnika.

3.12. Blokowanie przeciwnika

Wyżej opisane blokowanie nie jest stosowane w przeciwnym przypadku, tzn. jeżeli gracz ma możliwość takiego zablokowania przeciwnika. Jest nieco zmodyfikowane. Modyfikacja polega na tym, że pionki nie ustawiają się w taki sposób, aby uniemożliwić ruch przeciwnikowi, ale aby w przypadku jego ruchu był on skazany na zbicie. Daje to większą elastyczność ruchu, jak i szersze rozstawienie pionków. Np. gdy pionek przeciwnika znajduje się na środku szachownicy to zamiast użyć 4 pionków, aby całkowicie zablokować jego ruchy, wystarczą tylko dwa oddalone o jedno pole od przeciwnika. W takim przypadku każdy ruch przeciwnika spowoduje stratę pionka, a grasz zachowa dwa dodatkowe pionki do wykorzystania w innym celu.

3.13. Spalony

Określenie spalony zaczerpnąłem z nazewnictwa piłkarskiego. Nie jest jednak one dokładnie odwzorowane. Spalony w warcabach polega na tym, że pionek przeciwnika znajduje się bliżej swojej linii promocji, niż pionek gracza, który jej broni. Zapobieganie spalonemu sprowadza się w praktyce do unikania przerw pomiędzy pionkami, zapobieganie wymianom przy użyciu najbardziej defensywnych pionków. Wyjątkiem jest damka która może bić do tyłu. Zapobieganie spalonemu w praktyce oznacza ujemne premiowanie pionków przeciwnika znajdujących się blisko (swojej) linii premiowanej.

4. Badania

Implementowanie funkcji oceniającej były podzielone na wiele etapów. Każdy etap składał się z napisania powyżej opisanych części funkcji oceniającej oraz sprawdzenie działania każdej z nich osobno. Sprawdzanie polegało na uruchomieniu gry, w której jednym graczem była napisana funkcja oceniająca, a drugim graczem był człowiek. Zachowanie człowieka nie miało na celu wygrania z przeciwnikiem, a wywołanie odpowiedniej reakcji na swoje ruchy. Poniżej przedstawiono przykładowe reakcje komputera na ruchy człowieka. Następnie po zaimplementowaniu wszystkich funkcji przystąpiono do skonsolidowania wszystkiego w jedną całość. Po wklejeniu wszystkiego do jednego pliku i poprawieniu kilku błędów kompilatora przystąpiłem do badań całego algorytmu. Pierwszym spostrzeżeniem było nieco wolniejsze działanie apletu przy tak wielkiej funkcji. Do badań użyto głębokości przeszukiwania równej 5, oraz ilości potyczek po 10 na każdy eksperyment. Po przeprowadzonych badaniach uzyskano następujące rezultaty:
1. Program ani razu nie przegrał z człowiekiem,
2. Po zmierzeniu go z funkcjami zaimplementowanymi przeze mnie w trakcie projektu także wygrał wszystkie spotkania,
3. Program również wygrał wszystkie spotkania z algorytmem zaimplementowanym przeze mnie na zajęciach. Na najniższym poziomie przeszukiwania program dało mi się wygrać z programem. Funkcje cząstkowe wciąż jednak nie mogły sobie z nim poradzić.
Victory!!!
Rysunek przedstawia jedną z zakończonych rozgrywek wygraną przez mój program
Do przeprowadzonych badań przyjąłem następujące wartości stałych:
pionek=5 pkt
damka=50 pkt
pionek w strefie I +2pkt
pionek w strefie II +1pkt
ruch w kierunku grupy przeciwnika +2pkt
możliwość bicia +30pkt za każde bicie
poziom IV +20 pkt
poziom III +3 pkt
poziom II +1 pkt

5. Wnioski

Skonstruowana przez mnie funkcja nie miała żadnych problemów z pokonywaniem człowieka jak i innych funkcji porównujących. Nie wiem jednak jak by wyglądała jej potyczka z innymi algorytmami zaimplementowanymi w grach komputerowych, gdyż nie udało mi się uzyskać o nich żadnych informacji. złożoność obliczeniowa funkcji nie wpływa znacząco na złożoność całego algorytmu, gdyż nie ma tam pętli większych niż 2 zagnieżdżenia. Skonstruowana funkcja potrafi przewidzieć większość znanym mi posunięć w warcabach oraz odpowiednio na nie zareagować.

LITERATURA:

Valid HTML 4.01 Transitional