1. Streszczenie

Celem projektu było stworzenie samouczącego gracza do gry w gomoku. Wykorzystano metodę TD uczenie ze wzmocnieniem. Docelowo gracz powinien rozgrywać partie z człowiekiem.

Postawiony problem ma bardzo dużą przestrzeń stanu, dlatego w trakcie realizacji projektu konieczne było zastosowanie aproksymatora funkcji wartości. Do obliczenia jej wartości użyto perceptron. Jako cechy przestrzeni stanu użyto ilość sekwencji zagrażających. Wykorzystane zostały definicje sekwencji zagrażających wzięte z metody Threat-Space Search dla gry Gomoku.

Ostatecznie okazało się, że uczenie ze wzmocnieniem nie jest dobrą metodą rozwiązywania problemu gry w gomoku. Otrzymane rezultaty nie są dobre. Zdarza się, że agent podejmuje dobre działania, mimo to jego gra jest na bardzo niskim poziomie.

1. Brief

The Goal of the project was to create learning control player for gomoku game. The TD method of reinforcement learning was used. The aim of the project was to teach the player to play game with human.

This problem has a huge space of states, so it was necessary to use value function estimator. Perceptron was used in order to count value function. Number of threat sequences was used as traits of state. Applied definitions of threat sequences were taken from Threat-Space Search method for Gomoku game.

Finally it proved that reinforcement learning is not a good solution for solving the problem in gomoku game. Received results are not good. Sometimes agent makes a good decision, but his play is still at a very low level.

2. Strategia

3. Funkcja wartości V

Do nauczenia funkcji wartości zastosowano algorytm TD. Metoda ta składa się z powtarzanych w pętli kilku kroków:

Normalnie oczekuje się, że funkcja ta jest zdefiniowana w sposób tablicowy, to znaczy, dla każdego stanu przypisana jest wartość. W trakcie uczenia wartości te są modyfikowane. W przypadku gry gomoku na planszy 19x19 pół dolne oszacowanie ilości stanów wynika z ilości możliwości rozstawienia pionków na planszy bez uwzględnienia ich kolorów. Mamy zatem nie mniej, niż 2^(19x19) stanów. Tak duża liczba uniemożliwia zastosowanie tablicowej metody reprezentacji funkcji wartości. Jak podaje pozycja [1], jednym ze sposobów aproksymacji funkcji wartości jest stworzenie perceptronu, który będzie obliczał wartość funkcji na podstawie wybranych cech stanu. Zatem funkcja wartości, zgodnie z [1], ma postać

Uczenie tej funkcji polega na odpowiedniej modyfikacji wag zgodnie ze wzorem

Aktualizacja wag odbywa się na podstawie błędu wag i z krokiem beta tak, jak mówi algorytm TD. Uchyby wag definiujemy, jak podaje pozycja [3], następująco:

4. Wektor cech

• Pięć kamieni w rzędzie
• "czwórka w linii"
• "czwórka"
• "trójka" - na 7 polach
• "rozbita trójka"
• "trójka" - na 6 polach

Każdy element wektora odpowiada pewnej sekwencji pionków. Wartość tego elementu zależy od ilość wystąpień odpowiedniej sekwencji pionków na planszy. Definicje poszczególnych sekwencji (oprócz pierwszej, która została dodana na potrzeby algorytmu) wyjaśnione są w artykule [2]. Odpowiadają one pięciu rodzajom zagrożeń. Jeśli gracz nie podejmie akcji w celu rozbicia takiej sekwencji, na pewno przegra. Pierwsza z cech odpowiada ułożeniu zwycięskiemu. Próbowano również użycie dodatkowej cechy odpowiadającej ułożeniu dwóch pionków obok siebie. Cecha ta niekorzystnie wpływała na strategię gry. Powodowała, że gracz układał swoje pionki w zwartą grupę, zamiast w linii. Jednocześnie brak tej cechy sprawia, że początkowy etap gry z punktu widzenia automatycznego gracza, ma charakter zupełnie losowy.

5. Wartość wzmocnienia R

6. Krok uczenia

7. Obserwacje i wnioski

• Podczas gry agenta z człowiekiem, agent często nie ma okazji do stworzenia sekwencji zagrażających. Powoduje to, że przez całą rozgrywkę odpowiednie wartości cech są równe 0, a tym samym agent nie ma okazji do modyfikowania odpowiadających im wag. W przypadku gry ze sobą dwóch agentów, gra ma przebieg bardzo losowy i uczenie jest nieefektywne - po takiej formie uczenia agent wykonuje na ogół zupełnie bezsensowne ruchy w rozgrywce z człowiekiem.
• Podczas gry agenta z człowiekiem, uczenie przebiega szybciej, gdy współczynniki maleją wolniej. Przyjęcie współczynnika nie spełniającego podanych warunków prowadzi czasem do rozbiegania wag do nieskończoności.
• Jako że postanowiono oprzeć algorytm działania agenta wyłącznie na metodzie uczenia ze wzmocnieniem, nie ma w nim elementu przewidywania ruchów w przód (dalej, niż to wynika z konieczności maksymalizacji wyrażenia wewnątrz funkcji określającej strategię), agent na początku rozgrywki wykonuje bardzo losowe zagrania. Późniejsze ruchy determinowane są przez grę człowieka.
• Przykładowy przebieg zmian wag w czasie wygląda następująco
  
• W praktyce agent nie wygrywa z człowiekiem. Jego gra ma charakter zdecydowanie obronny. Podczas próbnych 10 rozgrywek przegrał wszystkie. Czasem zdarza się, że agent doprowadza do sekwencji zagrażającej, ale na ogół w sytuacji, gdy powinien się bronić. Prowadzi to do przegranej agenta.
• Jako że w algorytmie funkcje nie są reprezentowane tablicowo, to w początkowej fazie gry algorytm nie ma odpowiednich akcji dla stanu początkowego. Na planszy mogą nie występować jeszcze sekwencje zagrażające, więc pierwsze ruchy agenta są praktycznie losowe.

8. Informacje o programie

9. Źródła

1. http://www.ise.pw.edu.pl/~cichosz/um/ - Paweł Cichosz, Materiały do wykładu "Uczenie się maszyn".
2. http://home.mit.bme.hu/~gtakacs/download/allis1994.pdf - "Go-Moku and Threat-Space Search" - L.V. Allis, H.J. van den Herik, M.P.H. Huntjens.
3. http://www.leemon.com/papers/1995b.pdf - "Residual Algorithms: Reinforcement Learning with Function Approximation" - Leemon Baird