Autor: Paweł Pająk
Data: 2008-06-17
Program grający w LOA
Projekt z przedmiotu "Sztuczna inteligencja"
Lines of Action (LOA) jest dwuosobową grą planszową o sumie zerowej. Pod pewnymi względami podobna jest do szachów - pionki przesuwane są po planszy i mogą być bite przez przeciwnika. LOA rozgrywane jest na planszy do szachów - przyjęła się także odpowiednia notacja ruchów (np. a6-d6). Celem gry jest połączenie własnych pionków, tak aby utworzyły one spójny obszar. Zasady i historię LOA można znaleźć na stronie angielskiej Wikipedii.
Gra w LOA jest ciekawym problemem Sztucznej Inteligencji. Jej główne cechy, które za tym przemawiają, to:
Celem projektu było stworzenie programu, który grałby w LOA na zadowalającym poziomie. Jako ocenę sukcesu przyjąłem liczbę spełnionych warunków:
Będąc świadomym tego, że zarówno Loa2D jak i MIA, to programy pisane przez profesjonalistów w ciągu dłuższego okresu czasu, w trakcie rozgrywek pozwalałem własnemu programowi na dłuższe działanie niż przeciwnikowi. Grając z MIA ustawiałem jak najniższe parametry ( tj. pierwsza wersja programu, 5 sekund na ruch, przeszukiwanie alfa-beta i brak dodatkowych usprawnień (jak np. null move) )
Jako główny algorytm gry w LOA, przyjąłem przeszukiwanie alfa-beta z dobrą funkcją ewaluacyjną. Stworzona przeze mnie funkcja istotnie korzysta z pracy doktorskiej Dr. Mark H.M. Winands'a.
Jako środek masy pionków danego gracza definiuję pozycję na planszy będącą średnią arytmetyczną pozycji wszystkich pionków tego gracza (po współrzędnych X i Y).
Na ocenę danej konfiguracji pionków na planszy w moim programie składają się wyniki działania następujących podfunkcji:
Idea: Chcąc wygrać, gracz musi zgromadzić własne pionki blisko siebie.
Zadaniem tej funkcji jest sprawdzenie jak blisko siebie są pionki danego gracza. Funkcja ta wysoko ocenia konfiguracje, w których suma odległości pionków od środka masy wszystkich pionków jest mała.
Idea: Lepiej mieć więcej pionków w centrum niż na brzegach.
Funkcja ta wysoko ocenia konfiguracje, w których większość pionków gracza znajduje się w centrum planszy. Za pionki na brzegach i w rogach przydzielana jest kara.
Idea: Bezpiecznie mieć pozycję środka masy pionków bliżej krawędzi niż w centrum.
Paradoksalnie, pozycja środka masy w centrum planszy nie jest dobra. Bardzo często oznacza ona, że pionki są rozrzucone po brzegach planszy. Środek masy blisko krawędzi gwarantuje, że pionki są blisko siebie ( w przeciwnym razie część pionków musiałaby być poza planszą, żeby zrównoważyć pozycję środka masy).
Idea: Konfiguracje pokazane na poniższych rysunkach stanowią silną formację, trudną do zniszczenia przez przeciwnika, dającą podstawę budowy zwartej grupy połączonych pionków.
Funkcja pozytywnie ocenia powstanie czwórki lub trójki połączonych ze sobą pionków. Ze względu na zagrożenie, że taka formacja może utworzyć się daleko od reszty pionków, brane są pod uwagę tylko takie formacje, które są oddalone nie dalej niż 2 pola od środka masy pionków.
Idea: Im więcej możliwych ruchów do wyboru ma gracz, tym większą ma możliwość na stworzenie spójnej grupy własnych pionków lub uniemożliwienia działań przeciwnikowi.
Funkcja zlicza liczbę możliwych ruchów dla danego gracza. Wyżej punktowany jest ruch bijący pionek przeciwnika, a niżej np. ruch przesuwający pionek do rogu planszy.
Idea: Chcąc wygrać, gracz musi zgromadzić własne pionki blisko siebie.
Idea tej funkcji jest taka sama jak funkcji Skupienie. Tym razem znajdowany jest najmniejszy prostokąt, w którym zawarte są wszystkie pionki gracza. Im mniejsze ma pole, tym wyższa jest ocena konfiguracji.
Idea: Dobrą pozycję cechuje duża liczbą pionków, które znajdują się na sąsiednich polach.
Funkcja ta oblicza średnią liczbę sąsiadów pionków tego samego koloru. Im wyższa, tym konfiguracja jest uznawana za lepszą.
Jednym z głównych celów było stworzenie efektywnej implementacji podanych wyżej (pod)funkcji ewaluacyjnych oraz dodatkowych procedur związanych z przeszukiwaniem alfa-beta. W tej części raportu omówię (w skrócie) jak to zrobiłem.
Pisząc o preprocessingu mam na myśli funkcję, która wywoływana jest tylko raz, na początku rozgrywki.
W programie plansza reprezentowana jest jako dwie zmienne typu unsigned long long ( 64 bity ). W każdej z tych zmiennych zapisana jest bitowo pozycja wszystkich pionków jednego z graczy. Zalety takiej reprezentacji:
Generowanie wszystkich możliwych ruchów w LOA z danej konfiguracji nie jest łatwe. Implementowanie go wprost w samym przeszukiwaniu znacząco spowolniłoby cały program. Zauważmy jednak, że mając obliczone wszystkie możliwe ruchy dla każdej możliwej konfiguracji linii ( takich konfiguracji jest mniej niż 2^18 ) możemy szybko wygenerować je podczas przeszukiwania drzewa gry. Dzięki temu, generowanie ruchów sprowadza się do przepisania odpowiednich pozycji z tablic wypełnionych wartościami podczas preproccesingu.
Jak wiadomo - kolejność przetwarzania ruchów w przeszukiwaniu alfa-beta jest ważna. Jeżeli program będzie rozpatrywał ruchy od najgorszych, alfa-beta prawie w ogóle nie wykona cięć w drzewie. Przetwarzanie ruchów od najlepszych sprawia, że spora część drzewa nie jest w ogóle eksplorowana. W moim programie, ruchy przesuwające pionki do centrum planszy rozpatrywane są jako pierwsze. Właśnie takie ruchy najczęściej są ruchami dobrymi. Rzadko zdarza się, że ruch przesuwający pionek na krawędź planszy jest tym najlepszym.
UWAGA: Program, rozpatrujący ruchy w losowym porządku działa ponad 3 razy wolniej!. Decyzja o sortowaniu ruchów pozwoliła na w miarę komfortową grę z programem przeszukującym drzewo do głębokości 6.
Na pierwszy rzut oka, ciężko sprawdzić czy dana konfiguracja jest terminalna inaczej niż poprzez przeszukanie (np. BFS-em) 'grafu' planszy od jakiegoś pionka i sprawdzenie czy zostały odwiedzone wszystkie pionki danego gracza. Procedura ta niestety musi zostać wywołana w każdym wierzchołku drzewa przeszukiwań i może kosztować sporo czasu.
Powiemy, że linia pozioma planszy jest zajęta, jeżeli znajduje się w niej przynajmniej jeden pionek danego gracza. Zauważmy, że jeżeli konfiguracja jest terminalna to zajęte linie poziome muszę tworzyć zwarty ciąg (np. jeżeli zajęte linie poziome to linie 4,5,6 - to konfiguracja może być terminalna, jeżeli zajęte są linie 2,4,5,6 to konfiguracja nie jest terminalna). Ta sama uwaga tyczy się linii pionowych. Dzięki bitowej reprezentacji planszy, sprawdzenie tych warunków wymaga zaledwie kilku operacji.
W moim programie przyjąłem wyżej opisaną implementację sprawdzania konfiguracji terminalnej - najpierw sprawdzane są zajętości linii poziomych i pionowych, a dopiero później przeszukuję całą planszę. Takie podejście zaowocowało przyspieszeniem programu o 10%.
Wyżej wymienione funkcje zaimplementowałem wprost - każda wymaga przeglądnięcia wszystkich pozycji pionków gracza i wykonania kilku prostych operacji. Dodatkowo, w pozycyjności i pozycji środka masy, korzystam z tablicy wartości pozycji zapisanej na stałe w kod programu.
Podczas preprocessingu, dla każdej pary możliwych linii, liczę liczbę czwórek i trójek, pamiętając wynik w tablicy quads[1<<8][1<<8][8]. Trzeci wymiar tej tablicy odpowiada kolumnie, w której znajduje się potencjalny środek masy ( pamiętajmy, że interesują nas tylko takie czwórki i trójki, które są nie dalej niż dwa pola od środka masy pionków).
Następnie w funkcji ewaluacyjnej, dla każdej pary poziomych sąsiednich linii, odległych od środka masy o co najwyżej dwa pola, odczytywana jest wartość z odpowiedniego miejsca tablicy quads.
Podobnie jak czwórki, podczas preprocessingu dla każdej pary możliwych linii liczę liczbę połączeń między pionkami. Dalej, tak samo w funkcji ewaluacyjnej wystarczy kilka razy odwołać się do odpowiedniego miejsca w tablicy.
Idea na spamiętanie wyników jest podobna do generowania ruchów - wystarczy, zamiast ruchów, zapisać ocenę mobilności konkretnej linii. Przyjąłem następujące założenia:
W pierwszej wersji mojego programu, jeżeli na którymś poziomie drzewa gry, program stwierdzał terminalność konfiguracji, zwracana była duża wartość ('nieskończoność') z odpowiednim znakiem. Jak okazało się później w praktyce - nie było to do końca dobre rozwiązanie. Zauważmy, że w takiej implementacji, jeżeli program będzie miał możliwość zakończenia gry np. w 4 ruchach, to prawdopodobnie będzie sporo ruchów, które pozwolą mu to zrobić dopiero w 6 ruchach. Takich, trochę 'gorszych' ruchów, jest zazwyczaj więcej, co skutkuje odwlekaniem własnego zwycięstwa tak długo jak to możliwe.
Rozwiązanie okazało się proste - wystarczy, aby zamiast nieskończoności zwracana była wartość nieskończoność-D, gdzie D to głębokość węzła w drzewie gry. W ten sposób, większą wartość mają ruchy, które szybciej doprowadzają do zwycięstwa.
W pierwszej wersji mojego programu, nie uwzględniłem, z pozoru mało ważnej zasady, która obowiązuje w wielu grach (np. w szachach) - jeżeli konfiguracja planszy powtórzy się 3-krotnie to wynikiem gry jest remis. Remis, sam w sobie, nie jest złym rezultatem - jednakże, jeżeli oba programy grające nie uwzględniają tego, może dojść do zapętlenia się, tj. powtarzana jest ciągle ta sama sekwencja ruchów. Uniemożliwia to rozgrywanie większej ilości partii między programami (zwłaszcza jeżeli program gra sam z sobą).
Rozwiązanie okazało się także nietrudne - ze względu na prostą reprezentację planszy ( dwie 64-bitowe zmienne), wystarczy zapamiętać w programie jakie konfiguracje planszy już były, i blokować odpowiednie ruchy na 1 poziomie przeszukiwań drzewa gry. Ponieważ, partie są zazwyczaj krótkie, sprawdzenie dla każdego węzła na 1 poziomie drzewa gry czy nie reprezentuje konfigurację, która powtórzyła się już 2-krotnie, nie wpływa na czas działania programu.
Tak jak już napisałem, funkcja ewaluacyjna składa się z kilku podfunkcji. Ponieważ, każda z tych podfunkcji ocenia co innego na swój niezależny sposób, konieczne jest przemnożenie ich wyników przez odpowiednie współczynniki. Mark H.M. Winands, przeprowadzając eksperymenty, sugeruje następującą hierarchię ważności cech dobrej konfiguracji:
skupienie > mobilność > czwórki > pozycyjność > {rozproszenie, połączenia} > pozycja środka masy
Dobierając kolejne współczynniki, zastosowałem następującą procedurę:
1. Ustaliłem wartość współczynnika dla podfunkcji skupienie. Resztę współczynników ustawiłem na 0.
2. Dla każdej następnej podfunkcji z wyżej wymienionego ciągu:
a) poprzez gry programu z samym sobą, szukałem dobrych kandydatów na wartość nowego współczynnika
b) rozgrywałem turniej między znalezionymi dobrymi kandydatami i wybierałem zwycięzce na wartość nowego współczynnika
3. Na koniec, nieznacznie poprawiałem ręcznie niektóre współczynniki, jednocześnie sprawdzając czy przynosi to zamierzony skutek.
Jestem świadomy tego, że do ustalania współczynników, najlepiej nadają się standardowe algorytmy uczenia się (np. TD). Ze względu na ramy czasowe projektu, nie udało mi się tego zaimplementować.
Jako demonstrację działania stworzonego przeze mnie programu, pokażę i omówię 2 partie rozegrane z programem LOA2D i MIA. W obu przypadkach korzystam z interfejsu graficznego 'przeciwnika'.
Gracz biały: mój program, głębokość przeszukiwania drzewa gry 6.
Gracz czarny: LOA2D, Level:10 (Very Hard).
Warto zwrócić uwagę na pierwszy ruch mojego programu - należy on do typowych ruchów otwierających grę - jednocześnie przesuwamy niewygodny pionek ze skraju planszy i blokujemy ruchy pionków przeciwnika po prawej stronie. Po pierwszych 5 ruchach, mój program kontroluję górę planszy, przesuwając się w stronę centrum.
Kolejne 6 ruchów nieco pogarsza sytuację gracza białego. Niebezpiecznie blokowany jest biały pionek na pozycji F8. Warto zwrócić uwagę na ostatni ruch mojego programu - uniemożliwił on graczu czarnemu budowę silnej formacji w prawym górny rogu planszy.
Gracz biały próbuje zbudować zwartą grupę własnych pionków na dole planszy. Pionki gracza czarnego pozostają w kilku grupkach, zachowując jednak dużą mobilność.
W kilku ruchach, gracz biały buduje zwartą grupę własnych pionków w centrum planszy. Pionki gracza czarnego, zostały podzielone na dwie grupy. Nie są one jednak w żaden sposób blokowane i stanowią spore zagrożenie dla gracza białego.
Tak jak można było się spodziewać - gracz czarny w kilku ruchach łączy prawie wszystkie swoje pionki. Sytuacja wydaje się być dramatyczna dla gracza białego - bardzo trudno jest ruszyć pionek z E8, a gracz czarny do zwycięstwa potrzebuje tylko dołączyć swój ostatni, nieblokowany pionek.
A jednak - ze względu na dużą liczbę pionków w każdej linii graczowi czarnemu trudno jest dołączyć ostatni pionek do grupy. Tymczasem gracz biały wycofuje swój pionek i wykonuje piękne bicie wzdłuż przekątnej. LOA2D pokonane!
Gracz czarny: MIA.
Gracz biały: Mój program, głębokość przeszukiwania drzewa gry 6.
Tym razem, przeciwnik zaczyna pierwszy. Już na początku partii MIA wypracowuje pewną przewagę częściowo blokując lewą linię gracza białego.
Gracz czarny kontynuuje budowę formacji na lewej stronie planszy. Gracz biały ciągle rusza się tylko pionkami z prawej strony.
W ostatnim ruchu gracz biały przeprowadza atak na lewą stronę, co chwilowo znacząco polepsza jego sytuację.
Wyrównana walka w lewej części planszy. Niestety, pozycja białego jest znacząco gorsza - gracz czarny bardzo łatwo może rozdzielić białe pionki na dwie grupy przechodząc na 4 wiersz planszy.
Gracz biały został zepchnięty do defensywy. Mimo bliskości pionków, nie jest w stanie stworzyć solidnej formacji.
Ostatnie 10 ruchów to walka białego o przetrwanie. Ze względu na blokadę pionka na A6, biały nie może w żaden sposób zagrozić stworzeniem spójnej. Wygrywa gracz biały - MIA.
Moim zdaniem program gra dość dobrze - wygrał z LOA2D na najwyższym poziomie i nie poddał się łatwo MIA. Warto też dodać, że regularnie ( przynajmniej do chwili pisania tego raportu) wygrywał z programem kolegi, któremu udało się z MIA wygrać.
Oczywiście, wiele da się jeszcze zrobić - w szczególności brakuje funkcji która wykrywałaby 'ściany' budowane przez przeciwnika. Widać to na początku partii z MIA, kiedy mój program pozwolił zablokować sobie pionki na lewej krawędzi. Lepsze dobranie współczynników, także znacząco poprawiłoby grę programu.
Uważam, że program jest dość szybki - przeszukując drzewo gry do 6 poziomu, generowanie kolejnego ruchu trwa nie dłużej niż 30 sekund. Przeszukując do głębokości 5 - nie dłużej niż 7 sekund. Czasy te można poprawić, zauważając, że wszystkie cechy poza Mobilnością, zależą tylko od pozycji pionków konkretnego gracza. Dzięki temu, większość wyników można zapisać w tablicy hashującej i korzystać z gotowych odpowiedzi przy powtórzeniach konfiguracji.
Gra w LOA i stworzenie programu grającego było ciekawym doświadczeniem. Swoją złożonością i różnorodnością strategii LOA ustępuje tylko takim grom jak Szachy czy GO.