Kurs: Metody i Algorytmy Sztucznej Inteligencji
Prowadzący kurs: dr inż. Witold Paluszyński
Temat projektu: Próba implementacji algorytmu Thread Space Search (TSS) dla gry GOMOKU
1 Wstęp
1.1 Źródła informacji
Projekt został zrealizowany w oparciu o artykuł "Go-Moku and Threat-Space Search" L.V. Allis, H. J. van den Herik, M. P. H. Huntjens. Autorzy tej publikacji rozwiązali grę Gomoku przy użyciu algorytmów TSS (thread-space search) i PNS (proof-number search). Algorytm TSS jest ich pomysłem.
1.2 Zasady gry Gomoku
Gra Gomoku jest rozgrywana na planszy 15x15 pól. Każde pole może mieć jeden ze stanów: X, O albo jest puste. X to znak pierwszego gracza, O - drugiego gracza. Gra polega na stawianiu naprzemian swoich znaków na planszy, tak aby utworzyć ich ciąg o długości pięciu w jednej linii. Gracz, który pierwszy to zrobi wygrywa.
1.3 Gra olimpijska
Oczywiście gracz X ma pewną przewagę nad graczem O w przypadku gry osób. Są różne sposoby rozpoczynania gry Gomoku, aby wyrównać szansę. Do roku 1992 gra Gomoku była grą olimpijską. Organizowano zawody algorytmów sztucznej inteligencji, które brały udział w rozgrywkach Gomoku. W 1991 roku wygrał program Polygon. W 1992 pojawił się już program Victoria, który był oparty na algorytmach TSS i PNS. Jeśli grą gracza X steruje komputer w oparciu o algorytmy TSS (thread-space search) i PNS (proof-number search) to gracz O nie ma żadnych szans na wygraną. Oznacza to, że gra została rozwiązana. W rozgrywkach z 1992 roku Victoria wygrała z Polygon, gdy zaczynała grę, przegrała gdy była drugim graczem. Jednak wygrana dla pierwszego gracza jest pewna. Wraz z rozwiązaniem gry Gomoku zlikwidowano rozgrywki tej gry na olimpiadzie.
1.4 Temat projektu
W artykule opisanym na początku jest zawarty opis algorytmu TSS. Tematem tego projektu jest próba implementacji tego algorytmu i opisanie wszystkich jego kroków. Implementacja programu jest będzie przy użyciu C++ i biblioteki QT.
Rysunek 1: Program GOMOKU napisany na potrzeby tego projektu.
2 Algorytm Thread-Space Search
2.1 Opis działania
Sam algorytm TSS nie wygra rozgrywki. Algorytm ten wyszukuje możliwości tworzenia zagrożeń, czyli sytuacji, w których przeciwnik będzie musiał odparować atak, aby nie przegrać. Algorytm TSS ma za zadanie wyszukać taki ciąg zagrożeń, który będzie sekwencją zwycięstwa. Sekwencja zwycięstwa to ciąg ruchów gracza, takich że drugi gracz cały czas się broni. W przypadku gry Gomoku nie ma szans na obronę.
Co wtedy gdy nie ma możliwości stworzenia zagrożenia? Są dwie takie sytuacje. Pierwsza to początek gry. Tutaj trzeba pierwsze 4 ruchy mieć zapamiętane w bazie danych. Biorąc ilość mozliwości ruchów przeciwnika powinniśmy mieć zapamiętane około 200 przypadków rozpoczęcia gry. Drugi przypadek jest wtedy, gdy gra już jest po fazie początkowej, ale zagrożenia nie można stworzyć. Wówczas można wspierać się standardowym algorytmem przeszukiwania, autorzy programu Victoria użyli PNS (proof-number search).
2.2 Schemat działania TSS
- Dokonujemy początkowej rozgrywki. Pierwsze 4 ruchy są oparte o bazę danych otwarć gry Gomoku. Takich możliwości jest około 200.
- Szukamy możliwości stworzenia zagrożenia. Kolejność szukania zagrożeń jest ważna.
Zagrożenia jakie kolejno możemy stworzyć są następujące:
- X X X X -
- - X X X X
- - X X X X -
- - - X X X - -
- - X X X - -
- - - X X X -
- - X - X X -
- - X X - X -
- Jeśli znajdziemy taką możliwość to tworzymy zagrożenie. Może być odparowane przez przeciwnika, ale my możemy stworzyć kolejne zagrożenie. Wygramy gdy doprowadzimy do podwójnego zagrożenia albo do czwórki w linii. Jeśli nie mamy możliwości stworzyć zagrożenia to używamy PNS albo innego przeszukiwania. Możemy też kolejne ruchy wykonywać tak, aby tworzyć sekwencje, z których możemy doprowadzić do zagrożenia.
3 Implementacja TSS
3.1 Opis
Program Gomoku, który zawiera implementację TSS jest napisany tak, aby można było pominąć momenty wymagające użycia PNS oraz bazy danych otwarć. Jest przygotowany do testowania i implementowania tylko algorytmu TSS.
3.2 Schemat algorytmu
Gdy kolej na nasz ruch:
- ATAK: Szukamy sekwencji '- X X X X' albo 'X X X X -'. Jeśli znaleźliśmy to mamy wygraną.
- OBRONA: Szukamy sekwencji '- O O O O' albo 'O O O O -'. Jeśli znaleźliśmy to odparowujemy atak. Jeśli jest to sekwencja '- O O O O -' to przegraliśmy.
- ATAK: Szukamy nieodparowanych zagrożeń. Jeśli są takie, to wygralismy.
- OBORNA: Jeśli nie odparowaliśmy zagrożeń przeciwnika, to przegraliśmy.
- ATAK: Tworzymy zagrożenie. Jeśli nie możemy patrz kolejny punkt.
- OBRONA: Szukamy zagrożeń ze strony przeciwnika. Jeśli są, to odparowujemy atak, najlepiej w taki sposób, aby stworzyć zagrożenie.
- ATAK: Dokonujemy ruch, który zbliży nas do stworzenia zagrożenia. Najlepiej postawić ruch w miejscu, gdzie mogą przecinają się potencjalne zagrożenia, albo w jednej linii z nimi. Ruch musi być odpowiednio blisko wierzchołków pól zajętych przez nas.
3.3 Sposób tworzenia zagrożenia
- Najpierw szukamy możliwości stworzenia zagrożenia.
- Wszyskie takie możliwości umieszczamy na liście.
- Dla każdego potencjalnego zagrożenia symulujemy obronne ruchy przeciwnika w miejscu zagrożenia (algorytm w Victorii symuluje obronę stawiając na wszystkich wolnych polach zagrożenia znaki przeciwnika).
- Następnie w podwójnej pętli dla każdego potencjalnego zagrożenia i dla każdego potencjalnego ruchu obronnego dla danego zagrożenia sprawdzamy, czy dane zagrożenie jest częścią sekwencji zagrożeń prowadzących do wygranej.
- Jeśli jest to tworzymy zagrożenie.
3.4 Przykład działania
Rysunek 2: Stan początkowy przykładu. Ruch należy do gracza X.
Rysunek 3: Rozgrywka. Przebieg gry przy pomocy TSS. Wyszukiwanie zagrożeń.
Wyświetlana liczba to ilość przeszukanych stanów w danych ruchu.
3.5 Wyniki
Niestety moja próba implementacji nie powiodła się do końca. Są przypadki, kiedy program wykonuje "głupie" ruchy. Jest to uzależnione od pewnych błędów samej implementacji, a nie samej idei działania algorytmu TSS. Dokładnie nie jestem wtanie określić w czym tkwi problem. Gdybym wiedział, to bym naprawił. Źródła programu to plik gomoku-1.0.tar.gz. Plik Makefile zawiera instrukcje kompilowania wsparte przez program qmake z QT 4.3. W tym pliku Makefile program qmake jest wywoływany poleceniem qt4-qmake, proszę o modyfikacje do qmake, jeśle jest to zgodne z docelowym systemem.
4 Podsumowanie
Oczywiście w implementacji TSS kryje się wiele szczegółów samej realizacji kodu w C++, których nie opisano w tym artykule. TSS linearyzuje część związaną z przeszukiwaniem stanów gry. Jest to metoda bardziej naturalna, bardziej podobna do metod używanych przez ludzi podczas gry. Algorytm TSS powstał właśnie w wyniku obserwacji metod działania ludzi.
Autor: Ariel Bogdziewicz 2007
