Rafał Piotrowski

Warcaby i uczenie się ze wzmocnieniem

Sprawozdanie z projektu ze Sztucznej Inteligencji
Wrocław 07.06.2004

1. Historia gry w warcaby.

Historia gry w warcaby sięga 3000 lat p.n.e. kiedy to w starożytnym Egipcie, znana była planszowa gra Senet - prekursorka dzisiejszych warcabów. Jej twórcą, wedle wierzeń dawnych Egipcjan, był bóg Tot - bóg mądrości i wynalazca pisma (hieroglifów). W starożytnej Helladzie Grecy pasjonowali się grą w Petteia (kamyki) - warcaby greckie. Według mitologii greckiej jeden z jej bohaterów Palamades wynalazł grę w warcaby podczas oblężenia Troi. Grecka Petteia w starożytnym Rzymie przekształciła sie w Latrunculi (grę w rozbójników) - obecnie znana głównie pod nazwą warcabów rzymskich. Współczesne warcaby, powstałe na południu Europy w średniowieczu, pochodzą prawdopodobnie od gry nazywanej Alquerque (opartej na znanej przed 1000 r. Arabom grze El-Quirkat). Istnieją uzasadnione podejrzenia, że to właśnie do gry w Alquerque, na południu Francji, pierwszy raz użyto planszy złożonej z ułożonych na przemian jasnych i ciemnych pól - czyli dzisiaj znanej nam szachownicy.

W pierwszej połowie XVIII w. na terenie Francji pojawiła się nowa wówczas odmiana gry w warcaby na 100-polowej planszy nazwana przez samych Francuzów "warcabami na wzór polski", dziś nosząca miano warcabów międzynarodowych. Według legendy twórcą nowych warcabów miał być polski oficer Franciszek Żubr. Z Francji poprzez Belgię i Holandię warcaby polskie podbiły niemal cały kontynent europejski. Dziś są najbardziej znaną oraz popularną odmianą warcabów na całym świecie, szczególnie jako dyscyplina sportowa.

2. Odmiany warcabów.

Istnieje bardzo wiele odmian gry w warcaby. Odmiany te różnią się głównie:

• rozmiarem planszy (od 6 do 12 pól szerokości bądź długości)
• liczbą pionów (od 8 do 30 na zawodnika)
• zasadami bicia
• sposobem poruszania się damki

Mniej istotne różnice dotyczą:

• kolorów (barw) pól i pionów
• przebiegu czarnej przekątnej
• notacji i oznaczeń pól
• rozpoczynającego

Przykłady najpopularniejszych odmian:

• warcaby polskie (międzynarodowe) nazywane też 100-polowymi (10x10)
• angielskie; w USA nazywane "checkers" (8x8)
• hiszpańskie (8x8)
• włoskie (8x8)
• rosyjskie (8x8)
• kanadyjskie (12x12)
• klasyczne (64-polowe, w świecie nazywane brazylijskimi)

3. Program Checkers4

Program checkers4, który wykorzystano w projekcie można ściągnąć z serwera http://rusi.cjb.net/ za pomocą CVS. (np. poleceniem cvs -d :pserver:anonymous@rusi.cjb.net:/cvsroot/public co checkers4). Jest to program napisany w języku Java rozpowszechniany na licencji GNU GPL. Dzięki niemu nie trzeba było pisać interfejsu użytkownika. Zasady, które zostały ustalone dla gry są nietypowe, są to w gruncie rzeczy warcaby angielskie. To znaczy:

• plansza ma wymiar 8 x 8
• kamienie mogą sie poruszać tylko o jedno pole i tylko do przodu po przekątnych (po jasnych polach)
• bicie kamień może wykonać tylko do przodu (bicie do tyłu jest zabronione)
• damka (king) może poruszać się do tyłu lub do przodu, ale tylko o jedno pole po przekątnych (po jasnych polach)
• bicie damką można wykonać do przodu i do tyłu
• bicie jest obowiązkowe
• jeżeli istnieje więcej niż jedna możliwość wykonania bicia można wybrać dowolną z nich
• dopuszczalne jest wielokrotne bicie, o ile jest możliwe
• celem gry jest pozbawienie przeciwnika możliwości wykonania ruchu (zbicie wszystkich kamieni przeciwnika lub ich zablokowanie).

Jednak w programie checker4 plansza jest "odwrócona do góry nogami" w stosunku do planszy w warcabach angielskich, a pierwszy ruch wykonuje gracz grający jasnymi pionkami (kiedy w warcabach angielskich pierwszy ruch należy do ciemnych pionków). Każdy "gracz" w programie jest reprezentowany jako (odpowiednia) klasa.

4. Wykorzystane algorytmy.

4.1 Wybór ruchu.

Wybór ruchu dokonywany jest na podstawie wartości funkcji oceniającej. Wykorzystany jest standardowy algorytm MinMax, jeśli wiele ruchów ma tą samą (maksymalną) wartość, to wybierany jest losowo jeden z nich. W celu przyspieszenia działania programu zastosowano odcięcia alfa-beta.

4.2 Uczenie się ze wzmocnieniem.

Jest kilka sposobów uczenia się. Jednym z ciekawszych i wykorzystywanych w praktyce jest uczenie się ze wzmocnieniem (ang. reinforcement learning). Metoda uczenia się ze wzmocnieniem nie zakłada, że agent (ucząca się maszyna) ma jakąkolwiek wiedzę początkową. Celem jest nauczenie się na podstawie własnych doświadczeń, własnych sukcesów i porażek. To co jest porażką, a co sukcesem musi zostać sprecyzowane na początku (jeśli chodzi o gry nie ma z tym żadnego problemu). W metodzie uczenia się ze wzmocnieniem agent po każdej wykonanej akcji dostaje nagrodę lub karę (ogólnie wartość liczbową, czyli wzmocnienie), na podstawie której może zmienić swoje późniejsze zachowanie. W programie przyjęto, że agent dostaje nagrodę +1 po zwycięskim zakończeniu partii (po ostatnim ruchu), -1 po przegranej (również po ostatnim ruchu), natomiast 0 we wszystkich pozostałych przypadkach, tzn po ruchach nie doprowadzających jeszcze do rozstrzygnięcia oraz po remisach. Głównym celem agenta jest nauczenie się uzyskiwania jak największej nagrody, a więc w przypadku gry - nauczenie się wygrywać. Agent musi w jakiś sposób wybierać swoje akcje, dlatego potrzebna jest mu funkcja oceniająca poszczególne stany. Wraz z nauką, wartości tej funkcji powinny zmieniać się, tak aby agent nauczył się dokonywać optymalnych wyborów. Najprostszą formą takiej funkcji jest odwzorowanie ze stanów na ich wartości. Agent musi więc nauczyć się prawidłowych wartości wszystkich stanów. Wraz ze zdobywanym doświadczeniem wartości te można poprawiać według wzoru:


s₁, s₂, ..., s_n to kolejne stany, w których znajduje się agent, alfa to współczynnik uczenia się (z przedziału (0,1]), im mniejszy tym uczenie jest powolniejsze, ale dokładniejsze, gamma to również parametr algorytmu, dopierany do konkretnego problemu.

Najczęściej nie jest fizycznie możliwe obliczenie wartości wszystkich stanów, ze względu na ich ogromna liczbę. Rozwiązaniem jest funkcja aproksymująca te wartości na podstawie pewnych cech stanów. Takie właśnie rozwiązanie wybrano w programie. Używana jest liniowa funkcja kilku cech planszy:

gdzie f to liczba cech, w to wagi - współczynniki cech planszy (a). Oto wzory pokazujące jak poprawiane są współczynniki tej funkcji:

Innym pojęciem związanym z omawianą metodą jest "śledzenie wybieralności" (ang. eligibility traces). W metodzie tej podczas poprawiania wartości stanów pod uwagę brane są wartości wielu poprzednich stanów, a nie tylko jednego, jak jest w standardowej metodzie. Przy korzystaniu z funkcji aproksymującej branie są pod uwagę również te cechy, które wystąpiły w poprzednich stanach. Tak wygląda powyższy wzór po uwzględnieniu tego mechanizmu.:


W wzorze tym występuje gradient, dlatego metodę "śledzenia wybieralności" z jego wykorzystaniem nazywa się zmniejszaniem gradientowym (ang. gradien-descent). W przypadku liniowej funkcji aproksymującej gradient wyraża się prostym wzorem:

4.3 Funkcja aproksymująca.

Tak jak wspominano wyżej funkcja oceniające planszę jest liniową funkcją kilku jej cech. W tabelce poniżej znajduje się opis użytych cech. Aktywną stroną nazwano stronę dla której jest liczona wartość planszy, pasywną - stronę przeciwną.

Wśród wszystkich graczy, najczęściej stosowana jest funkcja z mniejszą liczbą składowych, np. 4, 14. Dalej opisane są różnice występujące u graczy, a później tabela podsumowująca (z nazwami, numerami i opisami).

5. Wyniki.

W celu przeprowadzenia testów napisano kilkunastu graczy. Głównym celem było dobranie jak najlepszej wersji algorytmu i jak najlepszych jego parametrów.

5.1 Testowanie.

Aby sprawdzić możliwości uczenia się danej wersji algorytmu, gracz wielokrotnie grał sam ze sobą, później grał kilkukrotnie z innymi graczami. Po "nauczeniu" w opisany sposób kilku graczy porównywano ich możliwości organizując gry między nimi. Na koniec zorganizowano również dwa turnieje, w którym wzięli udział wszyscy gracze. Podczas pierwszego turnieju gracze nie uczyli się w trakcie (tzn. nie poprawiali swoich funkcji oceniających). Miał on na celu sprawdzenie, którzy gracze najlepiej umieli wykorzystać swoje doświadczenie (czyli wcześniejszy trening) i wyliczyli możliwie najlepsze wagi funkcji aproksymującej. Podczas drugiego turnieju gracze uczyli się w trakcie jego trwania. Miał on na celu sprawdzenie, którzy gracze najlepiej uczą się od swoich przeciwników. W dalszej części najpierw następuje bezpośrednie porównanie i omówienie wersji zastosowanego algorytmu, dalej znajdują się wyniki turniejów.

5.2 Uczenie się na bieżąco i na końcu.

Wzór poprawiający funkcję oceniającą może być stosowane po każdym wykonanym ruchu jak następuje:

double delta = r + gamma*estimate(thisState) - estimate(previousState);
for (int j = 0; j < weights.length; j++)
    weights[j] += alfa * delta * thisState[j];

lub dopiero po całej skończonej rozgrywce. W tym drugim przypadku można dokonać obliczeń niejako wstecz, tzn w następującej pętli:

for (i = s.length - 2; i >= 0; --i)
    double delta = r + gamma*estimate(s[i+1]) -  estimate(s[i]);
    r = 0.0;
    for (j = 0; j < weights.length; ++j)
        weights[j] += alfa * delta * s[i][j];

Nagroda r przyjmuje wartość +1/-1 (ewentualnie 0 przy remisie) tylko po ostatnim ruchu w partii (w pozostałych jest równe 0), kiedy poprawia się funkcję po każdym ruchu, nagroda wpływa na wartości tylko raz, natomiast w powyższej pętli jest propagowana dalej, wpływa (pośrednio) na całość obliczeń. Wyniki bezpośredniego porównania nie są zaskakujące. Po każdej rundzie każdy z graczy grał kilkadziesiąt razy sam ze sobą, jak widać gracz uczący się na końcu (RafalBack) okazał się być lepszy, choć w późniejszych turniejach przewaga ta nie była zbyt widoczna, RafalForw był tylko nieznacznie gorszy.

5.3 Różne wartości Gamma.

Wartość gamma we wzorze można ustalić zależnie od konkretnego problemu. Przeprowadzono eksperymenty z wartościami 1.0, 0,9, 0,8, i 0,7. W bezpośrednim porównaniu najlepsza okazała się wartość 0.8. Pokazuje to fragment tabeli z drugiego turnieju:

Gracze ujęci w powyższej tabeli brali pod uwagę 4 cechy planszy. Wśród graczy którzy wykorzystują więcej cech znalazło się też dwóch którzy mieli wartości gamma równe 0.8, jednak wypadli oni znaczenie gorzej od analogicznych graczy z gamma = 1.0. Jak widać ciężko jest dobrać odpowiednią wartość tego parametru, jednak 1.0 wydaje sie być najbardziej uniwersalną (i najczęściej stosowaną wśród implementacji wykorzystujących uczenie sie ze wzmocnieniem do rozwiązywania jakiś problemów).

5.4 Cechy wielowartościowe i binarne.

Wartości cech mogą przyjmować wiele wartości lub być binarne. Cechy wielowartościowe można często w łatwy sposób odzwierciedlić za pomocą wielu cech binarnych. Jeśli dana cecha przyjmuje wartości całkowite (dyskretne) to można użyć w zamian tylu cech binarnych ile wartości przyjmuje ta cecha (tak właśnie uczyniono w tym eksperymencie). W przypadku cech o wartościach ciągłych można przedział wartości podzielić na pewną liczbę przedziałów i użyć tylu cech binarnych ile jest przedziałów. Przeprowadzenie tego eksperymentu zostało zainspirowane faktem, iż w książce Reinforcement learning - An Introdution we wszystkich przykładach ilustrujących użycie funkcji aproksymujących cechy były zawsze binarne. Okazało się jednak, że w większości przypadków lepsi okazali się gracze korzystający z cech wielowartościowych niż z cech binarnych.

5.5 Śledzenie wybieralności.

Jak powiedziano wcześniej metoda ta ma na celu branie pod uwagę większej liczby wartości poprzednich stanów. Wartości te muszą być mnożenie przez pewien współczynnik - lambda, 0 <= lambda < 1, który wskazuje jak wiele poprzednich stanów chcemy brać pod uwagę. Dla każdego współczynnika w[j] utrzymujemy wartość e[j], która mówi jak często występowała dana cecha stanu (planszy) b[j] wśród poprzednich stanów. Kiedy dana cecha wystąpi można kumulować jej wartość (e[j] = e[j] + a[j]) lub zastępować ją (e[j] = a[j]). Pętla poprawiająca współczynniki funkcji wygląda więc następująco:

for (i = bs.length - 2; i >= 0; --i)
    for (j = 0; j < features; ++j) {
        e[j] *= gamma * lambda;
        e[j] += s[i][j]; // kumulacja  albo: e[j] = s[i][j];  // zamiana
    double delta = r + gamma*estimate(s[i+1]) - estimate(s[i]);
    r = 0.0;
    for (j = 0; j < weights.length; j++)
        weights[j] += alfa * delta * e[j];

5.6 Inne metody.

Podczas szukania informacji na temat gry w warcaby i uczenia się ze wzmocnieniem znalazłem stronę dr. Marka Burge'a. To właśnie tam natrafiłem na program checkers4 (napisany przez jednego z jego studentów), który był wykorzystywany podczas jednego z kursów prowadzonych przez dr. Burge'a. W materiałach (niedostępnych obecnie na jego stronach) przedstawia on inny niż w książce Reinforcement learning - An Introdution sposób poprawiania współczynników funkcji aproksymującej:

Vt[b.length - 1] = r;
for (i = b.length - 1; i >= 0; --i)
    double err = Vt[i] - estimate(b[i]);
    for (j = 0; j < weights.length; ++j)
        weights[j] += alfa * err * s[i][j];
    if (i > 0)
        Vt[i-1] = estimate(bs[i]);

Okazał się on być niezwykle dobry, gracz RafalBurge realizujący go przegrywał tylko z RafalMore oraz z graczami, którzy wykorzystywali więcej niż on cech planszy.

5.7 Gracze - podsumowanie

5.8 Turniej bez uczenia się.

Konkurs został zdominowany głównie przez ostatniego gracza, co było spowodowane, tym że miał on największą głębokość przeszukiwania w algorytmie MinMax. Warto jednak zwrócić uwagę na gry RafalMore (numer 6), który wygrał wszystkie pojedynki, w tym również z RafalMMore (numer 11), który bierze pod uwagę więcej cech planszy od gracza RafalMore i ma dokładnie te same parametry algorytmu. Może to oznaczać, że bardzo trudno nauczyć się prawidłowych współczynników dla tych dodatkowych cech. W kolejnym turnieju wprowadzono jeszcze jednego gracza - RafalMoreD, miał on z założenia pokonać wszystkich (włącznie z RafalMMoreD), tak też się stało. Zrezygnowano natomiast z przeprowadzenia wszystkich gier z RafalMoreD, ponieważ są one dość czasochłonne i nie wprowadziłyby zapewne nowych informacji.

5.9 Turniej z uczeniem się.

W konkursie z uczeniem się każdy pojedynek składał się z dwóch rund po 10 gier każda, pomiędzy rundami gracze grali kilkadziesiąt razy (20-30) sami ze sobą. W niektórych pojedynkach różnice pomiędzy wynikami pierwszej i drugiej rundy były diametralnie różne. Najwyraźniej widać to u graczy, gdzie gamma była mniejsza od 1, po niewielkiej liczbie gier potrafili (z niektórymi graczami) wygrać lub zremisować w drugiej rundzie po przegraniu pierwszej.

5.10 Podsumowanie.

Stworzeni gracze nie są arcymistrzami i nigdy nimi nie będą, jednak nie można ich pokonać grając bezmyślnie. Ich autor ma bardzo duże trudności w doprowadzeniu do swojej wygranej z najsilniejszymi graczami, jest on jednak graczem amatorem. Nieco łatwiej jest doprowadzić do remisu. Graczom brakuje inwencji jak zakończyć grę, mimo ewidentnej przewagi (np 2 damki przeciwko 5). Rozwiązaniem tego problemu mogła by być baza danych z wszystkimi możliwymi zakończeniami dla 2-3 pionków przeciwnika na planszy. Takie metody stosuje się w najlepszych programach do gry w warcaby (oprócz tego są stosowane bazy danych rozpoczęć gry). W czasie turnieju okazało się, że faworyt (gracz biorący pod uwagę największą liczbę cech planszy) zawiódł. Lepszy okazał sie gracz oceniający planszę z użyciem kilku cech mniej, było to zaskoczeniem.

6. Bibliografia i odnośniki.

1. Reinforcement Learning: An Introduction Richard S. Sutton, Andrew G. Barto

2. Some studies in machine learning using the game of checkers, A. L. Samuel

3. Some Studies in Machine Learning Using the Game of Checkers. II - Recent Progress, A. L. Samuel

4. Reinforcement Learning: A Survey Leslie Pack Kaelbling, Michael L. Littman

5. Strona dr. Marka Burge'a

6. Strona z programem checkers4

7. Reinforcement Learning Repository

8. Chinook - niepokonany przez człowieka program grający w warcaby