Celem mojego projektu było napisanie programu grającego w grę Lines of Action. Jest to gra przeznaczona dla dwóch osób. Rozgrywka odbywa się na planszy 8x8. Ustawienie początkowe obrazuje rysunek
Gracze wykonują na przemian ruchy w poziomie, pionie lub po przekątnych, każdorazowo przesuwając się o dokładnie tyle pól, ile pionów znajduje się w linii. Nie można przeskakiwać pionów przeciwnika, można natomiast zbijać jego piony, wykonując ruch na pole zajęte przez niego. Gra kończy się, gdy jeden z graczy połączy wszystkie swoje piony.
Szczegółowe zasady gry opisane są w [0].
Wykorzystałam algorytm minimax z odcięciami alfa-beta. Funkcja oceny planszy zaimplementowana w moim programie była silnie inspirowana pracą doktorską [1], poświęconą opisowi MIA, jednego z silniejszych programów grających w LoA. Funkcja heurystyczna składa się z następujących elementów:
Mierzy, jak blisko siebie położone są piony gracza. Nagradzamy układy, w których piony są blisko -- prościej jest wtedy spowodować zagrożenie (czyli układ, który zmusza przeciwnika do rozbicia własnej formacji pionów), ułatwione jest także tworzenie bloków, których nie da się rozbić w jednym ruchu.
Przy pomocy tej funcji wykonywane jest wykrywanie układów połączonych w więcej, niż jednym kierunku. Zliczamy ilość kwadratów 2x2 w których zajęte są przynajmniej 3 pola, ponieważ takie układy są trudniejsze do rozbicia.
Układy, w których piony mają dużą średnią odległość od centralnego kwadratu planszy, są oceniane niżej. Ponieważ nie można przeskakiwać pionów przeciwnika, zdominowanie centralnego obszaru planszy zmniejsza mobilność oponenta.
Eliminuje zagrożenie wystąpienia jednego piona mocno oddalonego od wszystkich pozostałych. Badamy pole prostokąta, obejmującego wszystkie piony gracza -- im to pole jest mniejsze, tym rozstawienie bardziej zwarte.
Program grający jest zaimplementowany w języku C++. Celem poprawienia wydajności plansza gry opisywana jest zbiorami wektorów bitowych, osobnymi dla każdego z graczy. Takie podejście pozwala na szybsze sprawdzenie poprawności ruchu, a także upewnienie się, czy dany układ planszy nie wystąpił już dwukrotnie (zgodnie z zasadami trzykrotne wystąpienie tego samego układu na planszy oznacza koniec gry). Większość składowych funkcji heurystycznej jest spamiętywana i uaktualniana w trakcie działania programu, dzięki czemu właściwe obliczenie części składowych nie wymaga odwoływania się bezpośrednio do planszy gry.
Program był porównywany z dwoma aplikacjami grającymi w LoA - MIA1[2] oraz LoA2D[3], a także z programem stworzonym przez Pawła Pająka(PP). Szczegółowy przebieg wszystkich zapisanych rozgrywek dostępny jest w archiwum, wyniki są następujące:
Przy głębokości przeszukiwania 6 program nieźle radzi sobie nawet grając jako biały, działa jednak stosunkowo długo (do 30 sekund na ruch); zmniejszeniu głębokości na 5 jego wyniki nie są już tak dobre, ale nadal rozpoczynając partię -- często jest w stanie doprowadzić do zwycięstwa. W rozgrywkach z programem LoA2D zwraca uwagę znacząca różnica szybkości -- mój program gra nawet do 5-6 razy szybciej, niż przeciwnik, a mimo to z nim wygrywa.
Właściwe dobranie współczynników dla składowych funkcji oceny to jeden z kluczowych problemów przy ulepszaniu funkcji heurystycznych. Zastosowanie znajduje tu uczenie metodą różnic czasowych.
Odpowiednie uszeregowanie ruchów rozważanych przez algorytm alfa-beta znacząco przyspiesza odcięcia. Do obliczenia średniej optymalnej kolejności wykorzystuje się sieci neuronowe.
Opis eksperymentów z wymienionymi tu usprawnieniami opisany jest w pracy [4]
[0] Lines of Action na angielskiej wikipedii
[1] Informed Search in Complex Games, Mark H.M. Winands
[2] Mark's LOA Homepage - udostępnia aplet MIA1