Autor: Tomasz Tylenda
Data: maj/czerwiec 2006
Projekt został przygotowany na przedmiot Sztuczna Inteligencja.
Reversi, zwane również othello, to gra rozgrywana na planszy o wymiarach 8x8 przy użyciu dwukolorowych pionków. Celem gry jest zdobycie jak największej liczby pionków. Gracze układają je na przemian na planszy, gdy dołożenie kolejnego spowoduje, że w linii znajdą się pionek gracza, pionki przeciwnika i pionek gracza, te należące do przeciwnika są odwracane (zmieniają kolor). Dokładniejszy opis gry można znaleźć w Wikipedii.
Obecnie istniejące programy grające w reversi radzą sobie znacznie lepiej niż ludzie. Dotyczy to nie tylko przeciętnych graczy, ale także tych najlepszych.
Moim celem było opracowanie programu, który umiałby grać w reversi. Program taki musi się składać z następujących części:
Program napisałem w języku Prolog, korzystałem z implementacji SWI-Prolog 5.6.1. Logike gry i funkcje oceny pozycji zaprogramowałem samodzielnie, algorytm minimax jest modyfikacją kodu znalezionego w Internecie. Program umożliwia rozergranie partii z komputerem (interfejs tekstowy), grę dwóch agentów przeciwko sobie oraz automatyczną grę z programem Edax.
Reversi jest popularną grą planszową i liczy już ponad 120 lat, dzieki temu opracowano pewne proste reguły pozwalające skutecznie grać.Większośc z nich da się łatwo zaimplementować na komputerze. Poniżej opisuje elementy strategii, które posłużyły mi do konstrukcji heurystyk. Szerszy opis poniższych technik, pochodzący od Emmanuela Lazarda, można znaleźć na stronie www.radagast.se/othello/Help/strategy.html.
Celem gry jest zdobyć jak największej liczby pionków, więc oczywistym kryterium oceny ruchu jest maksymalizacja liczby pionków własnego koloru. Jest to też strategia, którą wybierają początkujący gracze. Ponieważ w reversi jeden ruch może odwrócić wiele pionków przeciwnika, może się okazać, że mimo naszej przewagi liczebnej, przeciwnik w następnym ruchu z łatwością zmieni sytuacje na naszą niekorzyść.
Bardzo cenne dla graczą są pionki, których przeciwnik nie będzie mógł odwrócić. Są to pionki położone na rogach planszy, przy brzegach oraz osłonięte przez inne nieodwracalne pionki. Oto przykład:
1 2 3 4 5 6 7 8 1 . . . . . . . . 2 . . . . . . . . 3 . . . . . . . . 4 . . . . . . . . 5 . . . . . . . B 6 . . . . . . B B 7 . . . . . B B B 8 . . . B B B B B
Kropki oznaczaja puste pola, znaki B oznaczaja czarne pionki, oczywiscie powyższa sytuacja nie może się zdarzyć w prawdziwej grze.
Okazuje się, że stawianie pionków na niektóre pola jest korzystne, a na niektóre przeciwnie. Szczególnie wartościowe są narożniki, ponieważ umożliwiają uzyskanie nieodrwacalnych pionków, wartościowe są również brzegi (wyjątek - poniżej). Analiza wielu gier wskazuje, że stawianie pionka na tzw. C-squares i X-squares jest złym wyborem. Na poniższym rysunku zaznaczyłem C-squares i X-squares:
1 2 3 4 5 6 7 8 1 . C . . . . C . 2 C X . . . . X C 3 . . . . . . . . 4 . . . . . . . . 5 . . . . . . . . 6 . . . . . . . . 7 C X . . . . X C 8 . C . . . . C .
Doświadczeni gracze starają się wykonywać ruchy tak, aby zmniejszyć liczbę możliwych ruchów, które może wykonać przeciwnik. W szczególności oznacza to zmuszenie przeciwnika do postawienia pionka na C-square lub X-square, albo pozbawienie go możliwości ruchu (strata tury).
Inteligentny agent grajacy w Reversi korzysta z kilku heurystyk z różnymi wagami,
jeżeli f_1(B),...,f_n(B) to rożne funkcje heurystyczne, to agent określony
ciągiem a_1, ... a_n ocenia pozycję następująco:
h(B) = a_1 * f_1(B) + ... + a_n * f_n(B)
Współczynniki a_i dobierałem eksperymentalnie.
Okazało się, że program potrafi grać lepiej ode mnie, co mnie nie zaskoczyło. Przeprowadziłem także porównania mojego programu z dwoma innymi.
KReversi jest programem dołączanym do środowiska okienkowego KDE. Celem autorów było stworzenie programu, który ma grać z ludzimi. Program posiada 7 stopni trudności, 1. jest przeznaczony dla początkujących, 4. dla średnio zaawansowanych, a 7. dla najlepszych graczy. Mój program potrafi łatwo wygrać z KReversi na poziomach 1-3, po zwiększeniu głebokości przeszukiwania dochodzi do poziomu 4., a więc potrafi grać na poziomie przeciętnego człowieka.
Podczas gry z KReversi odkryłem, że mój program wykonuje ruchy zalecane w artykułach o strategii w Reversi, chociaż nie były one zapisane wprost w heurystyce — stawia swoje pionki pomiędzy dwa pionki przeciwnika.
Edax należy do innej kategorii programów grających w reversi. Został on napisany z myślą o rozgrywaniu partii z innymi programami, na poziomie trudności niedostępnym ludziom. Dysponuje on zaawansowanymi algorytmami, np. potrafi się uczyć, zmienia zachowanie w różnych fazach gry, ponadto może używać księgi otwarć zawierającej najpopularniejsze warianty początkowego etapu gry. Istnieje także możliwość ograniczenia siły gry. Swój program przetestowałem z dość prostymi ustawieniami Edaksa, mimo to na 9 rozegranych partii, mój program odniósł zwycięstwo tylko w jednej. Co ciekawe jedyna wygrana partia zakończyła się wynikiem 34:0 co oznacza, że Edax dopuścił do sytuacji w której wszystkie jego pionki zostały odwrócone i nie mógł wykonać ruchu. Zazwyczaj rozgrywka kończy się gdy na planszy znajdą się wszystkie 64 pionki lub niewiele mniej.
W czasie testów zauważyłem, że mój program jest wielokrotnie wolniejszy od KReversi i Edaksa. Podejrzewam, że dzieje się tak z dwóch powodów: większość programów grających w reversi jest napisana w C/C++ więc powinny być szybsze od tych napisanych w Prologu. Drugim ważniejszym powodem może być to, że nie wykonują one pełnego przeszukania drzewa gry do określonej głębokości (za pomocą minimaksu z ewentualnymi odcięciami alfa-beta), lecz dość szybko odcinają gałęzie, które źle rokują na przyszłość.
Szybkość działania mojego programu jasno pokazuje, że minimax nie jest wlasciwym algorytmem do przeszukiwania drzewa gry. Jak podaje Gunnar Andersson w środkowej fazie rozgrywki z każdej pozycji można przejść do około 10 innych, co ogranicza głębokość przeszukiwania do około 9 (na początku i na końcu partii jest mniej możliwości). Mi udało się osiągnąć głębokość około 5-6 (wlasciwie 6-7, bo heurystyka mobilności oblicza ile ruchów można wykonać z danego stanu), zależnie od szybkości komputera i cierpliwości.
Stosowane w wielu programach przeszukiwanie z odcinaniem źle rokujących scieżek pozwala na zwiększenie głębokości przeszukiwania do ponad 20 ruchów. Jednak używane algorytmu są wrażliwe na błędy w funkcji heurystycznej: mogą one powodować odcinanie dobrych ruchów, lub powodować marnowanie czasu na rozwijanie złych.