---

Stworzenie komputerowego gracza Backgammon'a

z wykorzystaniem algorytmu TD(λ)

Creating a computer Backgammon player

using TD(λ) algorithm

---

Sztuczna inteligencja

Instytut Informatyki Uniwersytetu Wrocławskiego

Szymon Ślęzak, Mateusz Fedkowicz, 05.06.2013

---

---

1. Spis treści

1. Introduction
2. Cel zadania
3. Krótka historia komputerowych graczy w Backgammon'a
4. Opis gry
5. Obsługa programu
6. Implementacja
7. Opis rozwiązania
8. Wyniki
9. Co dalej?
10. Wnioski
11. Literatura

---

1. Introduction

Our goal was to implement neural network named TD-Gammon, which is able to teach itself to play Backgammon by playing against itself and learning from each game played.

TD-Gammon neural network is using TD(λ) (temporal difference) learning. This type of reinforced learning updates neural network weights after each move played in game and it's like backpropagation where for one neural input ideal value is next move's neural input value.

Our neural network was trained in about 100,000 games in different variants. After that we tested it against random player - winning ratio was above 80%. It's quide good score for a random game like Backgammon (luck in rolling dices). Also, we analyzed our games in proffesional Backgammon program called GNU Backgammon. Our neural network predictions differed from expert neural network by about 0,5% per move. We didn't reproduce results from original experiment, but our network performance is like average human player or above. We think we wasn't able to fully reproduce original results because of initial network weights (they are random in this approach) or bad choice of constants.

2. Cel zadania

Celem zadania było stworzenie i wyuczenia komputerowego gracza w grze Backgammon. Wykorzystaliśmy do tego sieć neuronową zaczerpniętą z projektu TD-Gammon 0.0 [1].

3. Krótka historia komputerowych graczy w Backgammon'a

Backgammon jest bardzo ciekawą grą z punktu widzenia dziedziny jaką jest sztuczna inteligencja. Jest tak przede wszystkim dlatego, że liczba stanów planszy i losowość gry uniemożliwia właściwie zastosowanie standardowych algorytmów (takich jak np. MinMax) używanych w innych grach - np. w szachach czy też warcabach. Podczas gdy np. w szachach drzewo rozgrywki ma współczynnik rozgałęzienia do 80 nowych gałęzi z danego stanu planszy, w Backgammonie ilość ta może dochodzić nawet do 400 nowych gałęzi. Algorytmy przeszukujące drzewo rozgrywki w poszukiwaniu najlepszego ruchu są tu mało wydajne.

Pierwszym ważnym komputerowym graczem w Backgammon'a był program Neurogammon stworzony przez Gerard'a Tesauro w roku 1989. Był to pierwszy program do gry w Backgammon'a, który używał sieci neuronowej. Sieć ta była uczona przy użyciu propagacji wstecznej na około 400 grach rozegranych przez autora. Program wygrał pierwszą komputerową olimpiadę w Londynie w roku 1989 pokonując wszystkich przeciwników. Jego poziom gry określić można jako poziom średnio zaawansowanego ludzkiego gracza.

Drugim bardzo ważnym programem był TD-Gammon - gracz stworzony przez tego samego autora w roku 1992. Jego nazwa wzięła się stąd, że program był uczony na sieci neuronowej przy użyciu algorytmu TD(λ) (temporal difference learning). Tym razem jednak program nie był uczony na podstawie gier przeprowadzanych przez człowieka. Innowacyjnym podejściem był fakt, iż program posiadał jedynie minimalną niezbędną wiedzę do gry (prawidłowe posunięcia itp.), ale nie posiadał żadnej początkowej wiedzy na temat dobrych ruchów. Przy użyciu algorytmu TD i rozegraniu około 300,000 gier, w których TD-Gammon grał sam przeciwko sobie udało mu się osiągnąć poziom niewiele niższy niż większość ówczesnych ludzkich graczy. Efekty były tak zaskakujące, że doprowadziły do zmian w teorii gry na temat najlepszych ruchów. TD-Gammon odkrył przed ludźmi całkiem nowe strategie gry, o których nigdy wcześniej nie myślano.

Opisany powyżej program figuruje w licznych opracowaniach pod nazwą TD-Gammon 0.0. Nazwa bierze się stąd, iż początkowo program nie wykorzystywał żadnego przeszukiwania ruchów naprzód. W kolejnych latach powstały ulepszenia programu - TD-Gammon 1.0, TD-Gammon 2.0 oraz TD-Gammon 3.0. Numer programu odpowiada ilości ruchów rozpatrywanych naprzód przy wyborze najlepszego aktualnego ruchu przez sieć neuronową.

Wszystkie powyższe programy popchnęły rozwój komputerowych graczy w Backgammon'a naprzód. Obecnie jednym z najlepszych programów do gry w Backgammon'a, oferującym poziom mistrzowski, jest GNU Backgammon, który przeszukuje do 4 ruchów naprzód. Innymi programami są np.: JellyFish, Snowie oraz eXtreme Gammon. Poza możliwością rozgrywki programy te udostępniają także narzędzia do analizy gier i szczegółowych porównań poszczególnych ruchów. Siła powyższych aplikacji leży w wagach sieci neuronowych trenowanych przez wiele miesięcy. Bez tych sieci programy te są zdolne grać co najwyżej na poziomie nowicjuszy.

4. Opis gry

Plansza

Plansza do gry w Backgammon'a składa się z 24 podłużnych pól określanych jako linie (ang. point) i przedstawianych w postaci trójkątów o naprzemiennych kolorach. Plansza jest podzielona na 4 ćwiartki, po 6 linii w każdej. Gracze posiadają swoje ćwiartki domowe i ćwiartki zewnętrzne, które są oddzielone pionowym pasem nazywanym bandą (ang. bar). Każdy z dwóch graczy biorących udział w grze dysponuje 15 pionami (ang. checker). Kiedy pionek przeciwnika zostanie zbity, musi zostać umieszczony na bandzie i może wejść na planszę tylko przez dom przeciwnika. Sposób w jaki piony są rozmieszczone na planszy przy rozpoczynaniu rozgrywki nazywa się pozycją startową: dwa pionki znajdują się na 24 linii każdego z graczy, pięć na linii 13, trzy na linii 8 i po pięć na linii 6. Pionki mogą wędrować tylko w jednym kierunku: z domu przeciwnika, przez jego ćwiartkę zewnętrzną, przez swoją ćwiartkę zewnętrzną, do swojego domu i ostatecznie poza planszę. Początkowe ustawienie pionów na planszy przedstawia poniższy obrazek.

Cel gry

Celem gry dla każdego z graczy jest przeprowadzenie wszystkich swoich pionów do ćwiartki domowej a następnie zdjęcie ich z planszy. Zwycięzcą zostaje pierwszy gracz, któremu uda się usunąć wszystkie swoje pionki.

Rozpoczęcie gry

Przed rozpoczęciem gry każdy z graczy rzuca jedną kostką (ang. dice). Pierwszy ruch należy do osoby, której udało się wyrzucić większą liczbę oczek. Jeśli na obydwu kostkach wypadnie ta sama liczba oczek, rzut jest powtarzany do czasu, gdy liczby będą się różnić. Po wykonaniu pierwszego ruchu, gracze wykonują ruchy na zmianę, rzucając dwiema kostkami.

Przesuwanie pionów

Piony na planszy można przesuwać tylko w kierunku własnego domu. Liczbę linii, o jakie można przesuwać piony, wyznacza się rzucając dwie kostki, przy czym oczek nie należy sumować. Przesunięcia wykonuje się jedno po drugim: najpierw o liczbę oczek z jednej kostki, a następnie o liczbę z drugiej. Dla przykładu, jeżeli gracz wyrzuci 6 i 4 to może przesunąć jeden pionek o 4 pozycje (ale tylko na otwartą, czyli nie zajętą przez przeciwnika linię) i inny pionek o 6 pozycji, albo też przesunąć tylko jeden pionek o całe 10 linii (o ile linie środkowe – oddalone o 4 lub 6 pozycje od bieżącego miejsca pionka – są wolne). Banda nie jest liczona jako dodatkowa linia.

Przesuwany pion może bez żadnych ograniczeń przeskakiwać linie zajęte przez inne piony., ale ruch musi się kończyć tylko na wolnej linii, czyli takiej, na której nie znajdują się dwa lub więcej pionków przeciwnika. Natomiast jeżeli na linii znajduje się dokładnie jeden pionek drugiego gracza, zostaje on zbity (ang. hit) i musi zostać umieszczony na bandzie.

W celu ochrony swoich pionków przed zbiciem, gracz może unikać pozostawiania pojedynczych pionków na liniach, próbując zajmować linie przez co najmniej dwa pionki. Dzięki temu staje się on "właścicielem" danej linii i jego przeciwnik nie może na nią wchodzić.

O ile to możliwe, gracz musi wykonać przesunięcia o liczbę oczek z obydwu kostek (jeśli zdarzy się tak, że na obydwu kostkach wyrzucona zostanie jednakowo liczba oczek, gracz wykonuje wtedy cztery przesunięcia zamiast dwóch). Jeśli może wykonać przesunięcie o liczbę oczek tylko z jeden kostki, wykonuje to jedno przesunięcie. Jeśli może wykonać tylko jedno przesunięcie, ale o liczbę oczek z dowolnej z kostek, wykonuje przesunięcie o większą liczbę oczek. Jeśli nie może wykonać żadnego przesunięcia, traci kolejkę. W przypadku, gdy jest to rzut podwójny, gracz musi wykonać tyle ruchów, ile tylko może.

Banda

Banda jest środkowym pasem rozdzielającym planszę na dwie połowy. Kiedy pionek zostanie zbity i znajdzie się na bandzie, zostaje tam do chwili, gdy może zostać wprowadzony do domu przeciwnika na pozycję określoną przez rzut kostką.

Opuszczanie bandy

Pionek, który znajduje się na bandzie, może ją opuścić tylko wtedy, gdy graczowi uda się wyrzucić liczbę oczek pozwalającą na przesunięcie pionka na wolną pozycję. Jeśli wyprowadzenie nie jest możliwe (odpowiednie linie są zajęte), to gracz traci kolejkę. W przypadku, gdy przeciwnik posiada wszystkie 6 linii swojego domu, nie możesz rzucać kostką aż do chwili, gdy jedna z linii stanie się wolna. Gracz, który posiada na bandzie swoje piony, ma obowiązek wprowadzenia ich wszystkich z powrotem do gry zanim będzie mógł normalnie kontynuować grę. Podobnie jak przy przesuwaniu, gracz, o ile jest to możliwe, musi wykorzystać liczbę oczek z każdej z kostek, więc gdy tylko wszystkie twoje pionki znajdą się na planszy możesz wykorzystać pozostałą liczbę oczek do przemieszczania innych pionów.

Opuszczanie planszy

Etap opuszczania planszy (nazywany również wyprowadzaniem pionów na dwór) jest ostatnią fazą gry, ale nie możesz jej rozpocząć dopóty, dopóki wszystkie 15 twoich pionków nie znajdzie się w twojej domowej ćwiartce. Kiedy twoi ludzie są już w domu, możesz ich zdejmować z planszy zgodnie z wyrzuconą liczbą oczek. Ponieważ trzeba wykorzystać wszystkie wyrzucone oczka, wyprowadzać na dwór można piony znajdujące się na liniach oddalonych od dworu dokładnie o liczbę oczek. Zatem jeśli na przykład wyrzucisz 5 oczek, ale nie masz pionów na 5 lub 6 linii, to musisz zdjąć pionek znajdujący się na najdalszej linii. Jeśli wyrzucisz 5 oczek i nie masz pionów na linii piątej, ale masz co najmniej jeden pionek na linii 6, to musisz przesunąć go o 5 pozycji ma linię pierwszą. Wykonywanie wyprowadzenia na dwór nie jest obowiązkowe i jeśli gracz posiada możliwość wykonania przesunięcia pionka, może to zrobić. Natomiast jeżeli twojemu przeciwnikowi uda się zbić jakiś pionek podczas gdy opuszczasz planszę, musisz go umieścić na bandzie i przebyć całą drogę do domu, zanim będziesz mógł kontynuował opuszczanie. Gracz, który jako pierwszy wyśle wszystkie swoje piony na dwór, wygrywa partię.

5. Obsługa programu

Program można uruchomić poleceniem java -jar Backgammon.jar. W katalogu lib w folderze z plikiem Backgammon.jar musi znaleźć się biblioteka encog-core-3.2.0-SNAPSHOT.jar (framework do sieci neuronowych). W folderze images potrzebne są także wszystkie obrazki. Plik out.txt jest zapisem wag używanej przez program do oceny ruchów sieci neuronowej.

Po uruchomieniu programu pokazuje się następujące okno:

Mamy do wyboru dwie opcje rozgrywki:

• Dwaj komputerowi gracze przeciwko sobie w trybie uczenia się ("Computer vs Computer"), przy tej opcji możemy także ustawiać opóźnienie, z którym wykonywane są ruchy ("Animation delay")
• Człowiek przeciwko komputerowi - tutaj możemy sami zagrać czarnymi przeciwko białym ("Human vs Computer")

Aby rozpocząć grę należy nacisnąć przycisk "Start game", w każdej chwili możemy porzucić aktualną rozgrywkę klikając przycisk "End game"
Poniżej zamieszczone są zrzuty ekranu z przykładowej rozgrywki.

W naszym ruchu najpierw rzucamy kośćmi klikając przycisk "Roll dices". Żółte strzałki podpowiadają nam, którymi pionkami możemy ruszyć przy danym rzucie kostką. Ruch wykonujemy zaznaczając pionek (wtedy strzałki pokazują gdzie można go przestawić) a następnie klikając kolumnę, do której chcemy go przenieść. W każdej chwili możemy cofnąć nasze ruchy klikając przycisk "Undo move". Kiedy jesteśmy zadowoleni z wykonanych ruchów klikamy przycisk "Confirm move" oddając sterowanie przeciwnikowi.

6. Implementacja

Do implementacji sieci neuronowych wykorzystaliśmy framework Encog w wersji 3.2. Umożliwia on szybkie tworzenie sieci typu feed-forward z generowaniem losowych wag. Pozwala on na szybkie wyliczanie wartości sieci dla danych, co było kluczowe dla naszego projektu. Ponadto pozwala na dość intuicyjny dostęp do wag sieci oraz wartości neuronów w warstwie ukrytej co było potrzebne do implementacji algorytmu TD. Posiada on także dużą bazę metod do nauki sieci neuronowych, ale specyfika naszego problemu nie pozwalała nam z nich skorzystać. Kod naszej metody uczącej oparty jest na pseudokodzie zawartym w pracy [3]. Wszystkie metody związane z nauką sieci neuronowej znajdują się w klasie MyBackpropagation, a dodatkowe funkcje to działania na sieci neuronowej w klasie BackgammonNeuralNetworkService. Testowaliśmy różne warianty sieci neuronowej - zmienialiśmy ilość wyjść oraz funkcje ewaluującą ruchy. Także stałe były modyfikowane.

7. Opis rozwiązania

Do nauki sieci wykorzystaliśmy metodę temporal difference learning. Podstawowym zamysłem tej metody jest nauka na różnicach pomiędzy wartościami kolejnych stanów - w naszym wypadku pomiędzy wartościami sieci neuronowej pomiędzy kolejnymi ustawieniami planszy podczas rozgrywki. Celem tej metody jest to, by ocenienie przez naszą sieć 2 kolejnych stanów plansz wybieranych przez nią ruchów zwracało bliskie sobie rezultaty. Nasza sieć neuronowa posiada 198 neuronów wejściowych.

Dla każdego pola na planszy mamy 4 neurony odpowiadające za umiejscowienie białych pionków. Jeżeli na pozycji x znajduje się co najmniej 1 biały pionek w x-tej czwórce pierwszy neuron ustawiany jest na 1, jeśli co najmniej 2 drugi, jeśli co najmniej 3 także trzeci a w wypadku jeżeli białych pionków jest więcej niż 3 to na 4 pozycji ustawiana jest wartość (n-3)/2, gdzie n to ilość tych pionków. Następnie mamy drugie tyle neuronów dla czarnych pionków. Plansza do Backgammon'a ma 24 pola co daje już w sumie 192 neurony. Dodatkowo 2 następne neurony opisują ile pionków zostało zbitych (przyjmują wartość n/2), kolejne 2 opisują ile pionków doszło do celu (wartość n/15), a ostatnie 2 są binarnym zapisem czyj jest ruch ([1,0] - białe, [0,1] - czarne). Warstwa ukryta sieci neuronowej składa się z 40 neuronów a warstwa wyjściowa z 2 neuronów odpowiadających prawdopodobieństwu że dany gracz wygra. Funkcje aktywacji dla obu warstw zostały ustawione na funkcje sigmoidalne zwracające wartości w zakresie (0,1] - dobrze symulujące prawdopodobieństwo:

Na początku ustawiliśmy w sieci małe wagi, które następnie były modyfikowane przez algorytm TD. Opisany on jest przez następujące równania (zaczerpnięte z: [3]):

Gdzie:

•   - są wagami z ukrytego neuronu j do wyjścia k
•   - są wagami z wejścia i do ukrytego neutronu j
•   - jest wyjściem
•   - jest różnicą pomiędzy wyjściem w czasie k+1 i k
•   - to stałe nauki
•   - reprezentują informację przenoszoną z jednej sesji nauki do następnej. Wyliczane są ze wzoru:

•   - parametr zapomnienia
•   - wartość neuronu wyjściowego k w czasie t
•   - wartość neuronu ukrytego j w czasie t
•   - wartość neuronu wejściowego j w czasie t

Lambda odpowiada za to, w jaki sposób aktualny błąd wpływa na wcześniejsze wyliczenia. Na podstawie tych wzorów po każdym ruchu komputerowego gracza wagi w sieci neuronowej są odpowiednio modyfikowane. Ruchy są wybierane na podstawie wyliczeń sieci neuronowej. Na początku, gdy sieć jest jeszcze niewyuczona często wybierane są ruchy losowe, przez co rozgrywki trwają dłużej. Jako, że Backgammon jest grą, której wynik może być tylko wygraną lub przegraną, dopiero po rozegraniu partii możemy rozpropagować ostateczny i pewny wynik - [1,0] wygrana białych, [0,1] w.p.p. Dzięki temu sieć nabiera poprawnej wiedzy.

Przy opisie rozwiązania warto nadmienić, że testowaliśmy dwa warianty sieci neuronowej - z jednym oraz dwoma neuronami wyjściowymi. Prz jednym neuronie wyjściowym zawierał on informację o prawdopodobieństwie wygrania rozgrywki przez gracza białego. Dla dwóch neuronów wyjściowych zawierały one odpowiednio - prawdopodobieństwo wygranej gracza białego oraz czarnego. Dla jednego neuronu wyjściowego funkcją ewaluującą wyjście była po prostu identyczność. Dla dwóch neuronów wyjściowych funkcja ewaluująca wyjście (oceniająca ruch na podstawie neuronów ostatniej warstwy sieci) zwracała dla gracza białego różnicę pomiędzy prawdopodobieństwem wygrania przez niego gry, a prawdopodobieństwem wygrania gry przez gracza czarnego. Dla gracza czarnego funkcja ta brała przeciwną różnicę.

8. Wyniki

Nasze sieci neuronowe testowaliśmy na dwa sposoby:

• Pierwszym sposobem było przeprowadzenie 1000 gier, w których wyuczony przez nas gracz miał za przeciwnika gracza, który wykonywał ruchy losowe. Najpierw trzeba było sprawdzić, czy przeciwnik gra wystarczająco losowo. Przeprowadziliśmy w tym celu test gry dla dwóch graczy losowych na około 10,000 gier. Wyniki były zgodne z oczekiwaniami - dwaj gracze losowi wygrywali ze sobą prawdopodobieństwem 50%. Następnie przeprowadziliśmy właściwy test dla 10,000 gier. Poniżej przedstawione są wyniki:

• Drugi sposób testowania wykorzystywał narzędzie do gry w Backgammon'a zwane GNU Backgammon. Jest to światowej klasy program grający, który udostępnia także narzędzie do analizowania ruchów i partii.
  Poniżej załączamy 3 tabelki podsumowujące wyniki z GNU Backgammon'a dla 3 losowych rozgrywek naszego programu z samym sobą (wyjaśnienia wymagają dwa ostatnie wiersze - Błąd ogółem jest to całościowy błąd w rozgrywce. Określa on o ile mniejsze prawdopodobieństwo wygranej ma nasz gracz w stosunku do eksperckiego gracza grającego wg najlepiej ocenianych przez GNU Backgammon'a ruchów. Błąd średni to błąd ogółem podzielony przez liczbę wykonanych ruchów). Program był wyuczony na 30,000 rozgrywek. Ponieważ wyuczanie programu trwa znaczną ilość czasu nie udało się go wyuczyć na znacznie większej liczbie partii. Gdyby jednak nasz program wyuczył się na większej ilości gier wyniki byłyby z pewnością lepsze. Jak widać wyniki wahają się średnio między 0,5% a 1,5% gorzej od optymalnego wg GNU BG na każdym ruchu. Jest to wynik zadowalający biorąc pod uwagę poziom zaawansowania narzędzia testującego.

9. Co dalej?

Patrząc na wyniki naszego programu można by się pokusić na kilka usprawnień, których ze względu na ograniczony czas nie udało nam się wprowadzić. Możliwe są między innymi następujące ulepszenia procesu uczenia się:

• lekkie przeszukiwanie w głąb - 1-ply search. Polega ono na tym, że dla kilku najlepiej ocenionych ruchów analizujemy wszystkie możliwe rzuty kostką przeciwnika i dalej jego możliwe ruchy i sprawdzamy do jak ocenionych stanów nas doprowadzą. Dzięki temu możliwość przewidywania naszego programu wzrasta, ale niestety ta metoda bez udoskonaleń jest bardzo czasochłonna - wykonujemy dla każdego ruchu nawet do kilku tysięcy dodatkowych ewaluacji (zazwyczaj wybiera się do 20 najlepszych ruchów, jest 21 różnych możliwych rzutów kością a każdy rzut generuje średnio możliwość około 20 różnych ruchów co daje 20 * 21 * 20 = 8400 ruchów do ewaluacji). Przez to nie zdążyliśmy wyuczyć naszego programu w ten sposób, ponieważ zajęłoby to dużo czasu. Idąc dalej tym tropem można zbudować przeszukiwanie jeszcze głębiej kosztem czasu - TD-Gammon 3.0 po dużych optymalizacjach programistycznych potrzebował ponad 10 sekund na ruch przy 3-ply search, a najnowszy GNUBG implementuje 4-ply search.
• rozbicie sieci na kilka mniejszych. W tym wypadku każda sieć uczy się innej części rozgrywki. Mamy sieć odpowiadającą za początek rozgrywki, następnie drugą dla długich rozgrywek, oraz inną dla końcówek.
• modyfikacja parametrów (metodą prób i błędów) odpowiedzialnych za szybkość zmian aplikowanych do sieci neuronowej. Można ustawić je na początku na wyższe i zmniejszać z biegiem czasu. Dzięki temu funkcja przybliżana przez sieć neuronową nie utknie w martwym punkcie.

10. Wnioski

Temat sieci neuronowych do gry w Backgammon'a jest bardzo rozległy. Nasz projekt jest oparty na rewolucyjnym algorytmie opracowanym przez Gerry'ego Tesauro w 1992 roku, który już dawno nie jest topowym graczem - w porównaniu np. ze złożonością programu GNU Backgammon. Jest to dziedzina ciągle rozwijana i bardzo wdzięczna dla miłośników sztucznej inteligencji.

Wyniki naszego eksperymentu są zadowalające - nie osiągnęliśmy co prawda poziomu TD-Gammon'a, ale zbliżyliśmy się do niego. Przy grach które nie mają tymczasowego wyniku i możliwa jest tylko wygrana i przegrana TD learning wydaje się idealnym rozwiązaniem. Algorytm, który zaimplementowaliśmy jest bardzo dobrym punktem wyjściowym do dalszych optymalizacji.

11. Literatura

[1] http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node108.html
[2] Programming backgammon using self-teaching neural nets, Gerald Tesauro pdf
[3] http://www.cse.unr.edu/robotics/bekris/cs482_f09/sites/cse.unr.edu.robotics.bekris.cs482_f09/files/backgammon.pdf
[4] http://www.heatonresearch.com/encog
[5] http://www.gnubg.org/