Wrocław, 5 czerwca 2006

Paweł Pszona, 150906

Pracownia ze sztucznej inteligencji

Gra HEX

1. HEX – historia i reguły

HEX został wymyślony niezależnie przez dwóch matematyków – najpierw w 1942 roku przez Pieta Heina w Danii, a następnie przez Johna Nasha w 1948 roku w Princeton.
Gra toczy się na planszy w kształcie rombu. Najbardziej typowymi rozmiarami planszy są 10×10 i 11×11.

rys.1 Plansza rozmiaru 11×11

Gra jest przeznaczona dla dwóch osób. Wykonują oni na przemian ruchy, polegające na stawianiu na wolnych polach planszy żetonów w swoich kolorach (zazwyczaj niebieskim i czerwonym).
Celem gry jest połączenie dwóch przeciwległych fragmentów planszy ciągiem sąsiednich żetonów jednego koloru, przy czym gracz niebieski chce połączyć krawędzie lewą dolną z prawą górną, a gracz czerwony – odwrotnie.

rys.2 Zwycięstwo gracza czerwonego

Partia HEX-a nie może zakończyć się remisem. Oznacza to, że jedynym sposobem na powstrzymanie przeciwnika przed połączeniem jego krawędzi jest połączenie własnych krawędzi (czyli wygranie gry). Ponieważ wszystkie informacje o stanie gry są jawne, więc musi istnieć strategia wygrywająca dla któregoś z graczy. Łatwo pokazać, że istnieje ona dla gracza rozpoczynającego grę – w przeciwnym przypadku (gdyby drugi gracz miał strategię wygrywającą) mógłby on zacząć ruchem, który chciał wykonać jego przeciwnik i kontynuować to postępowanie aż do zwycięstwa. Taki dowód (opierający się na metodzie podkradania strategii) jest jednak niekonstrukcyjny. Obecnie największym rozmiarem planszy, dla którego znana jest strategia wygrywająca, jest 7×7.

2. Cel zadania

Celem, który sobie postawiłem w tym zadaniu, było stworzenie programu, który w miarę inteligentnie będzie grał w HEX-a.

3. Podejścia nieudane

HEX okazał się być trudny (nieco bardziej niż na to wskazuje jego PSPACE-trudność:). Na tyle trudny, że moje pierwsze podejścia do problemu nie przyniosły zadowalających rezultatów. Trudność automatycznego grania w HEX-a polega na tym, że w każdej sytuacji jest bardzo wiele możliwych do wykonania ruchów (ok. 100), co powoduje, że wybór dobrego posunięcia jest trudniejszy niż w szachach (ok. 40 ruchów) i warcabach (8).

3.1 Wyczerpujące przeszukiwanie

Najpierw zakładałem granie w HEX-a w sposób standardowy – z wykorzystaniem minimaksowego algorytmu przeszukiwania drzewa gry z obcięciami typu alfa i beta. Aby uzyskać przeszukiwanie, które pozwalałoby zajrzeć daleko w głąb drzewa gry, potrzebowałem szybkiej (niekosztownej obliczeniowo) heurystycznej funkcji, oceniającej wartość sytuacji na planszy oraz przypisującej wagi możliwym ruchom w celu wybrania najlepszych. I właśnie to okazało się najtrudniejsze -- próbowałem m. in. oceny wg liczby sąsiednich pól w tym samym kolorze, tego, czy wybór danego pola pozwoli na połączenie dwóch grup sąsiednich pól w jedną oraz odległości od krawędzi, do których dążymy.
Wszystkie te podejścia okazały się w wysokim stopniu niezadowalające – program grał bardzo schematycznie i skupiał się na dokładaniu pól do już stworzonej grupy, w dużym stopniu ignorując ruchy przeciwnika, który tymczasem szybko kończył grę.

3.2 Dziel i (nie) zwyciężaj

Spróbowałem również podejścia, w którym podzieliłem całe pole do gry na mniejsze pola (rozmiaru 3×3 lub 4×4). Strategia miała polegać na ustalaniu kolejności przejścia ścieżki pól przez takie większe pola (np. wchodzę do dużego pola nr 1 jego lewą dolną krawędzią i chcę wyjść jego górną lewą krawędzią i pójść do dużego pola nr 2 itd.). Pomimo, że podprzypadki (jak wykonywać przejścia w większym polu) były rozpatrzone dokładnie, to głównymi wadami takiego sposobu gry było niezauważanie kluczowych sytuacji na obszarze wspólnym dużych pól oraz lokalność działania w takim dużym polu.

4. Podejścia (raczej) udane

Po nieudanych doświadczeniach z wyczerpującym przeszukiwaniem postanowiłem skierować się w przeciwną stronę, tzn. nie przeglądać drzewa gry tak głęboko, ale za to zaoszczędzony czas wykorzystać do policzenia kosztowniejszej obliczeniowo funkcji heurystycznej, która lepiej będzie oddawała sytuację na planszy oraz wartość ruchów.

4.1 HEX a dowodzenie twierdzeń

W HEX-ie celem jest tworzenie połączeń. W tej sytuacji bardzo użyteczne jest spostrzeżenie, że między pewnymi punktami uda się stworzyć połączenie nawet jeśli przeciwnik będzie się starał nam to jak najbardziej utrudnić. Najprostszy tego przykład (tzw. 2-most) jest przedstawiony na rysunku:


rys.3 2-most między x i y

Jeśli pola 1 i 2 są wolne, to nawet jeśli przeciwnik będzie miał pierwszy ruch, to zawsze będziemy w stanie stworzyć połączenie pomiędzy polami x i y. Jest to dla nas dobre, ponieważ mając tę gwarancję, nie musimy tego robić teraz, tylko możemy uznać to za załatwione i zająć się grą w innej części planszy. Taką sytuację (pewność, że możemy połączyć 2 punkty) będziemy nazywać wirtualnym połączeniem. Można również wprowadzić podobne pojęcie (nazywane wirtualnym półpołączeniem, mówiące o tym, że potrafimy połączyć dwa punkty bez względu na to, co zrobi przeciwnik, ale pod warunkiem, że to my mamy pierwszy ruch. Przykład takiego połączenia widać na rysunku:


rys.4 półpołączenie między x i y

Teraz, jeśli przeciwnik miałby pierwszy ruch, to stawiając swój żeton na polu 1 będzie w stanie skutecznie nam przeszkodzić w połączeniu x z y. Natomiast jeśli to my zaczynamy, to wtedy postawimy nasz żeton na polu 1 doprowadzimy do 2-mostu między y a grupą {1,x} co, jak wiemy, jest sytuacją wygrywającą.
Skoro połączenia są tak użyteczne, to czy jest jakiś sposób na wyliczanie połączeń, które wybiegają wiele ruchów naprzód?
Okazuje się, że tak. Pomocne są tu dwie proste reguły. Wirtualne połączenie między x i y będziemy reprezentować jako


rys.5 połączenie

a półpołączenie jako


rys.6 półpołączenie

4.1.1 Połączenie szeregowe


rys.7 pierwsza reguła połączenia szeregowego


rys.8 druga reguła połączenia szeregowego

Mówią one o tym, że jeśli połączymy szeregowo wirtualne połączenia o wspólnym końcu (nie mające poza nim punktów wspólnych), to dostaniemy wirtualne połączenie (jeśli punkt wspólny jest w naszym kolorze) lub wirtualne półpołączenie (jeśli jest on niezajęty).

4.1.2 Połączenie równoległe


rys.9 reguła połączenia szeregowego

Tutaj obrazek nie mówi wszystkiego. Sama reguła stanowi, że jeśli mamy co najmniej dwa (tu: 4) wirtualne półpołączenia między dwoma punktami, a ponadto żadne pole nie należy jednocześnie do wszystkich półpołączeń, to taki układ tworzy połączenie (jest tak dlatego, że jeśli przeciwnik wybierze jakiś punkt, to przynajmniej jeden punkt kluczowy dla pewnego półpołączenia pozostanie nietknięty. Wstawiając tam nasz żeton dostajemy wirtualne połączenie).
Znajdowanie połączeń odbywa się za pomocą algorytmu podobnego do dowodzenia twierdzeń. Naszym celem jest udowodnienie twierdzenia „jest wirtualne połączenie między punktami x i y”, a możemy korzystać z reguł połączeń szeregowego i równoległego. Jako fakty atomowe podajemy, że między sąsiednimi polami na planszy istnieją wirtualne połączenia (nie wymagają one od nas żadnej dodatkowej pracy).

Znalezienie wirtualnego połączenia między krawędziami planszy gwarantuje zwycięstwo. Jednak nawet jeśli takiego połączenia nie uda się znaleźć, to znalezione wirtualne połączenia można wykorzystać w dość efektywny sposób.

4.2 Graf pozycji

Przez graf pozycji dla konkretnego gracza rozumiem graf, w którym wierzchołkami są grupy pól planszy (sąsiednie pola w kolorze gracza traktuję jako jeden wierzchołek; każde pole białe jest osobną grupą; graf nie zawiera wierzchołków odpowiadających polom w kolorze przeciwnika). Krawędzie między dwiema grupami istnieją, jeśli algorytm poszukiwania połączeń znalazł między nimi wirtualne połączenie lub półpołączenie. Długość krawędzi jest ustalana na podstawie głębokości połączenia (czyli maksymalnej liczby ruchów potrzebnej, aby połączenie wirtualne doprowadzić do tego, żeby było rzeczywistym połączeniem) i funkcja za to odpowiadająca jest jednym z kluczowych elementów mojej strategii.

4.2.1 Ocena pozycji

Rozpatrywałem kilka wariantów oceny grafu pozycji, jednak najlepsze rezultaty osiągnąłem w dwóch przypadkach. W obydwu korzystam z klasycznego algorytmu Dijkstry znajdowania najmniejszych odległości od jednego wierzchołka. W pierwszym podejściu liczyłem odległość najpierw od jednej, a potem od drugiej krawędzi, a następnie przyjmowałem za wagę wierzchołka sumę tych odległości. Wartością pozycji była największa z przypisanych wierzchołkom wartości. Następnie modyfikowałem te wartości wg tego, ilu wierzchołek ma sąsiadów w kolorze przeciwnika w pewnym otoczeniu (np. w rombie 3×3). Wierzchołki o dużej liczbie takich sąsiadów uważałem za ważniejsze.
W drugim podejściu wagi wierzchołkom przypisywałem w podobny sposób, lecz tym razem za wagę pozycji przyjmowałem wyznaczoną przez algorytm odległość pomiędzy przeciwległymi krawędziami.
Ponieważ samo poszukiwanie wirtualnych połączeń jest zadaniem złożonym obliczeniowo, więc przeszukiwanie drzewa gry nie może sięgać zbyt głęboko. Sprawdziłem dwie możliwości zrealizowania takiego przeszukiwania.

4.3 Płytkie przeszukiwanie

Typowy algorytm minimaksowy. Na każdym poziomie uruchamiałem wyszukiwanie wirtualnych połączeń i funkcję oceny wierzchołków, a następnie wybierałem kilka (do 6) najbardziej interesujących wierzchołków do rozpatrzenia na poziomie następnym. Głębokość poszukiwania sięgała do 4.

4.4 Bardzo płytkie przeszukiwanie

Tutaj sprawdzałem tylko jeden poziom, ale za to gruntownie – kilkadziesiąt wierzchołków, w celu znalezienia najciekawszego. To on był moim wyborem ruchu.

5. Realizacja

Projekt zrealizowałem w języku Java. Aby móc w pewien sposób kontrolować czas działania algorytmu poszukiwania połączeń wirtualnych (który konsumuje prawie cały czas działania programu), wprowadziłem dwa parametry. Pierwszy ograniczał liczbę różnych (złożonych z różnych pól) połączeń wirtualnych między parą wierzchołków, natomiast drugi – liczbę półpołączeń rozpatrywanych przy sprawdzaniu reguły połączenia równoległego. Java jest językiem interpretowanym, więc gra działa dość długo. Przepisanie programu na jakiś „szybki” język z pewnością zmniejszyłoby czas jego działania o rząd wielkości.

6. Testowanie

Dla każdego rozważanego podejścia najpierw rozgrywałem kilka partii z programem. Jeśli wprowadzane modyfikacje nic nie wnosiły i nie rokowały szans na poprawę, to zarzucałem te pomysły. Taki los spotkał podejścia opisane w punkcie 3.
Następnym etapem była gra między programami, która miała służyć doborowi parametrów w funkcjach oceny. Rozgrywały one po kilka-kilkanaście spotkań.
W końcu nadszedł czas na porównanie ich z innymi ludźmi. W tym celu dwa najlepsze (z punktów 4.3 i 4.4) wystawiłem do gry na planszy 10×10 przeciwko ludziom, korzystając ze strony internetowej kurnik.pl.
Na koniec znów porównywałem programy, aby sprawdzić, jak duży wpływ na wyniki mają ich parametry. Okazało się, że program, który przeglądał drzewo tylko na 2 poziomach, ale pozwalał na 6 różnych połączeń między parą wierzchołków, okazał się znacznie lepszy od tego, który sięgał 6 poziomów w głąb, ale pozwalał tylko na 2 różne połączenia między parą wierzchołków.

7. Podsumowanie i wnioski

Uzyskane w grze z ludźmi wyniki nie są zbyt dobre: oba programy rozegrały po 20 spotkań. Ten z płytkim przeszukiwaniem wygrał 6 spotkań, natomiast ten z bardzo płytkim przeszukiwaniem – 5. Oba są więc dość słabe. Na podstawie własnych doświadczeń mogę stwierdzić, że program jest zwykle o 1-3 błędów do tyłu (tzn. jego przeciwnik powinien wykonać tyle gorszych ruchów, aby siły się wyrównały albo aby program miał przewagę).

8. Materiały

Valid HTML 4.01 Transitional