System koewolucyjny dla gry w warcaby
Metody i Algorytmy Sztucznej Inteligencji

prowadzący dr.inż. Witold Paluszynski
wykonał Włodzimierz Lipert 133120

Date: 19.06.07

Problem

Tematem mojej pracy są gry należące go klasy z ``sumą zerową'', klasyfikację taką podał po raz pierwszy von Neumann i Morgenstern [1]. Charakterystykę tej klasy można opisać bardzo zwięźle jako: ``Zysk jednego z graczy jest realizowany kosztem drugiego'', do tej kategorii należą takie gry jak szachy, kółko i krzyżyk, go, warcaby i wiele wiele innych. Głównym problemem w tej klasie jest opracowanie strategii, względem której będą wykonywane kolejne ruchy, niemożliwe jest dokonanie pełnego przeszukiwania drzewa gry ponieważ problem jest natury eksponencjalnej. Jednym ze sposobów rozwiązania problemu poszukiwania strategii jest użycie funkcji heurystycznych i ograniczenie na głębokość przeszukiwania w drzewie gry, rezultaty takiego rozwiązania są bardzo dobre, ale jak każde rozwiązanie posiada pewne mankamenty, mianowicie jeżeli ktoś zna algorytm funkcji heurystycznej może znaleźć pewne słabe punkty i je wykorzystać. Alternatywą dla statycznych funkcji heurystycznych jest zastosowanie sieci neuronowej, która mogłaby spełniać podobne funkcje, lecz posiadałaby pewne zalety i wady. Zaletą zastosowania sieci neuronowej jako heurystyki jest jej możliwość uczenia, co czyni ją w pewnym sensie nieprzewidywalną, wadą natomiast jest sposób w jaki można podjąć uczenie takiej sieci. W tej pracy postaram się uzyskać rozwiązania na wcześniej przedstawione problemy.

Jakość ruchu

W grach o bardzo dużych drzewach jest bardzo trudno ocenić jakość poszczególnych ruchów a tym bardziej wykryć który ruch prowadzi do porażki albo do sukcesu. Ta cecha znacznie utrudnia zastosowanie popularnych algorytmów uczenia dla sieci neuronowych np. backstepping. Rozwiązanie jakie zastosowałem pochodzi z pracy [2], jest to algorytm genetyczny. Zastosowanie tego algorytmu umożliwia przeprowadzenie naturalnej selekcji wśród osobników, jakimi są sieci neuronowe. Zgodnie z darwinowską teorią ewolucji po pewnej ilości pokoleń pozostaną osobniki najbardziej przystosowane ( najlepiej grające w warcaby ).

Algorytmy

Przeszukiwanie drzewa gry

Do przeszukiwania drzewa gry zastosowałem algorytm Alpha-Beta-CutOff, który jest przedstawiony w materiałach do wykładu [3]. Jest to algorytm skonstruowany na potrzeby gier należących do klasy `` z sumą zerową''. Aby bliżej zapoznać się z algorytmem odsyłam do wyżej wymienionego źródła.

Ocena stanu

Aby ocenić jakość konkretnego stanu zastosowałem sieć neuronową, strukturę sieci zaczerpnąłem z [2] i jest ona przedstawiona na rysunku 3.2

Sieć składa się z 4 warstw neuronów. Pierwsza warstwa ocenia przestrzenne rozmieszczenie elementów na warcabnicy, na wejścia tej warstwy należy podać wszystkie możliwe kombinacje kwadratów 3x3, 4x4, 5x5, 6x6, 7x7, 8x8. Po podliczeniu można stwierdzić, że do pierwszej warstwy należą 91 neurony. Drugą warstwę stanowią 40 neurony, trzecia 10 a czwartą zaledwie jeden. Tylko pierwsza warstwa jest unikalna kolejne posiadają typową strukturę feedforward.

Proces ewolucji

Algorytm ewolucyjny działa w następujący sposób

-

generuj populację osobników początkowych ( lub pobierz populację z kroku poprzedniego );

-

przeprowadź reprodukcję i mutację;

-

rozegraj pewną ( zadaną przez użytkownika ) ilość partii pomiędzy losowo wybranymi osobnikami i oceń jakość gry poszczególnych osobników;

-

zastosuj funkcję selekcji do usunięcia osobników najsłabszych, albo tych co mają pecha :).

-

powtarzaj wyżej wymienione kroki aż do uzyskania zadowalających rezultatów

Uwagi

Zastosowanie wyżej wymienionego podejścia wymaga bardzo dużą ilość rozegranych partii aby prawidłowo wytrenować sieć, autorzy tego pomysłu dla celów pracy [2] przeprowadzili 1440 godzin symulacji ( około 60 dni ), najlepsza sieć, uzyskana na drodze takiego treningu, gra na poziomie eksperta ( jeden poziom niżej od mistrzów świata ).

Program

Program jaki wykorzystałem do przeprowadzenia symulacji jest w całości mojego autorstwa, został napisany w języku C++, i jest przenośny pomiędzy platformami. Program umożliwia przeprowadzenie procesu treningu populacji sieci neuronowych i obejrzenie rozgrywek pomiędzy sieciami w czasie rzeczywistym.

Rezultaty symulacji

W poniższej tabelce są przedstawione statystyki najlepszych osobników w danym pokoleniu. Oznaczenia literowe są następujące:

P - ilość osobników składających się na jedno pokolenie;
R - ilość rund rozegranych pomiędzy jedną parą sieci
G - generacja;
W - ilość wygranych;
L - ilość przegranych;
F - fitness;

$P$	$R$	$G$	$W$	$L$	$F$
6	6	1	3	0	0.15
6	6	2	3	2	0.0842299
6	6	3	2	2	-0.0753863
6	6	4	2	1	0.00496597
6	6	5	1	0	0.00253249
6	6	6	2	0	0.152146
6	6	7	11	5	0.0202233
6	6	8	3	0	0.0502712
6	6	9	7	1	0.173849
6	6	10	6	0	0.169164
6	6	11	10	3	0.1648941

Przykładowa sekwencja ruchów

Literatura

1

Von Neumann J. and O. Morgenstern (1944) ``Theory of Game and Economic Behavior.''

2

Fogel, D.B. Kumar Chellapilla ``Evolution, Neural Networks, Games, and Intelligence.''

3

Witold Paluszyński ``Metody i Algorytmy Sztucznej Inteligencji.'' http://sequoia.ict.pwr.wroc.pl/ witold/aiarr/