Othello znane również pod nazwą
Reversi to wciągająca gra logiczna, której korzenie sięgają XVIII wieku. W
grę od XIX wieku gra niemal cała Europa. O jej wielkiej popularności
zadecydowały proste reguły (prostsze niż warcabów) i bogactwo kombinacyjne
dorównujące szachom. Od tych ostatnich gra jest jednak zdecydowanie bardziej
dynamiczna.
Rozgrywka toczy się na kwadratowej planszy podzielonej na 64 pola (8x8).
Gracze na zmianę wykonują ruchy dokładając
na planszy pionki w swoim kolorze.Pionki należy układać w taki sposób, aby pomiędzy pionkami gracza
(poziomo, pionowo lub na skos) znalazła się jak największa ilość pionków
przeciwnika. Po wykonaniu ruchu, wszystkie te pionki zostają przejęte i
zmieniają kolor. Jeżeli gracz nie może wykonać dozwolonego przepisami posunięcia,
musi pauzować (traci kolejkę).
Celem gry jest ułożenie na planszy jak największej ilości pionków,
tak aby zamienić pionki przeciwnika na własne.
Wygrywa ten z graczy, którego większa liczba pionków znajduje się na
planszy po zakończeniu gry. W przypadku równej ilości pionków, gra kończy
się remisem.
Ponieważ w naszym projekcie zajmujemy się głównie badaniem algorytmu uczenia, nie będziemy opisywać algortymu MiniMax.
Zainteresowanych odsyłamy do strony, z której korzystaliśmy przy pisaniu programu
MinMax.
Algorytm uczenia się ze wzmocnieniem:
W algorytmie tym istnieje zewnętrzna wartościująca informacjia trenująca.
Wartościowanie nie mówi systemowi uczącemu się, jakie akcje (jeśli w ogóle jakiekolwiek)
byłyby lepsze niż faktycznie wykonane przez niego lecz dostarcza jedynie pewnej względnej
liczbowej miary ich jakości.
Szczegółowy scenariusz uczenia się ze wzmocnieniem jest następujący:
Po każdej rozegranej partii system obserwuje aktualny stan środowiska i wykonuje pewną akcję,
zgodnie ze swoją aktualną strategią decyzyjną. Następnie otrzymuje on pewną wartość
tzw. wzmocnienia,nagrode o wartości 1 w przypadku wygranej partii, lub kare o wartości -1 gdy
przegrywa, kolejno następuje zmiana stanu środowiska.
Zadaniem systemu uczącego się jest skonstruowanie strategii prowadzącej do maksymalizacji
wartości wzmocnienia otrzymywanych w długim horyzoncie czasowym, czyli wykonanie odpowiedniej
akcji w danym stanie. Wybór ten dokonywany jest dzięki funkcji oceniającej dane stany,
której wartość w trakcie uczenia się zmienia się według wzoru:
gdzie:
S - stany gry,
alfa - współczynnik uczenia się (w przedziale (0,1)) im mniejsze tym uczenie powolniejsze,
ale dokładniejsze,
gamma - parametr algorytmu dobierany do odpowiednio do problemu.
W algorytmie korzystamy takżse z linowej funkcji aproksymującej wartości stanów, gdyż
obliczenie wartości wszytskich stanów, ze względu na ich dużą ilość jest niemożliwe. Wartość
ta jest przybliżana na podstawie cechy, w naszym projekcie określanej jako pojawienie się
pionka na planszy. Funkcja aproksymująca wartości stanów oraz równanie poprawiające jej
współczynniki przedstawiają poniższe wzory:
gdzie:
n - liczba cech,
w - wagi.
Zasada algorytmu przedstawiona w punktach:
Algorytm MiniMax z odcięciem alfa-beta, wykorzystywany jest dla dwóch graczy, z czego pionki białe wykorzystują dodatkowo algorytm uczenia się ze wzmocnieniem.
Macierz jaką posługuje się gracz czarny przedstawiona jest poniżej. Waratości dobrane są w sposób wynikający z naszego doświadczenia w tej grze. Kluczowymi dla rozgrwki są pola w rogach planszy, natomiast pola w środku są mało istotne. Należy jednak unikać ustwienia pionka w sąsiedztwie rogów.
| 100 | -20 | 10 | 5 | 5 | 10 | -20 | 100 |
| -20 | -50 | -2 | -2 | -2 | -2 | -50 | -20 |
| 10 | -2 | -1 | -1 | -1 | -1 | -2 | 10 |
| 5 | -2 | -1 | -1 | -1 | -1 | -2 | 5 |
| 5 | -2 | -1 | -1 | -1 | -1 | -2 | 5 |
| 10 | -2 | -1 | -1 | -1 | -1 | -2 | 10 |
| -20 | -50 | -2 | -2 | -2 | -2 | -50 | -20 |
| 100 | -20 | 10 | 5 | 5 | 10 | -20 | 100 |
Przeprowadzone doświadczenia polegały na tym, że gracz biały (uczący się), grał z graczem Czarnym, który
wykorzystywał algorytm MinMax. Gracze rozgrywali ze sobą 500 partii. Głębokość przeszukiwania dla czarnego ustwiona jest na
8, a dla Białego na 4. Zatem na początku gracz czarny jest znacznie lepszy od białego. Tak ustawiliśmy, aby możliwe było zaobserwowanie uczenia się zawodnika białego.
Wyniki testów przedstawione są w tabeli.
| Lp. rozegranych partii | Lp. wygranych przez białe | Lp. wygranych przez czarne | Lp. remisów |
|---|---|---|---|
| 5 | 2 | 3 | 0 |
| 10 | 2 | 8 | 0 |
| 15 | 3 | 12 | 0 |
| 20 | 3 | 17 | 0 |
| 25 | 7 | 18 | 0 |
| 30 | 11 | 24 | 0 |
| 50 | 22 | 28 | 0 |
| 65 | 32 | 32 | 1 |
| 75 | 41 | 33 | 1 |
| 100 | 61 | 37 | 2 |
| 150 | 90 | 58 | 2 |
| 200 | 119 | 75 | 6 |
| 300 | 155 | 130 | 15 |
| 400 | 213 | 172 | 15 |
| 500 | 256 | 227 | 15 |
Macierz ewaluacji dla gracza białego przed nauką:
| 50 | 4 | 16 | 12 | 12 | 16 | 4 | 50 |
| 4, | 30, | -4, | -5, | -5, | -4, | -30, | 4, |
| 16 | -4 | 1 | 0 | 0 | 1 | -4 | 16 |
| 12 | -5 | 0 | 0 | 0 | 0 | -5 | 12 |
| 12 | -5 | 0 | 0 | 0 | 0 | -5 | 12 |
| 16 | -4 | 1 | 0 | 0 | 1 | -4 | 16 |
| 4, | 30, | -4, | -5, | -5, | -4, | -30, | 4}, |
| 50 | 4 | 16 | 12 | 12 | 16 | 4 | 50 |
Maczierz po rozegraniu 500 partii:
| 69.95 | 23.89 | 36.04 | 31.32 | 31.57 | 35.88 | 23.97 | 70.08 |
| 25.05 | -10.12 | 15.41 | 14.44 | 14.43 | 15.99 | -9.11 | 24.93 |
| 36.70 | 15.60 | 20.91 | 19.21 | 19.98 | 21.32 | 16.44 | 37.04 |
| 31.97 | 14.83 | 20.45 | 0.00 | 0.00 | 20.34 | 15.88 | 33.04 |
| 31.99 | 14.24 | 20.64 | 0.00 | 0.00 | 20.48 | 15.99 | 33.10 |
| 36.01 | 16.05 | 20.84 | 19.98 | 20.60 | 21.76 | 16.68 | 37.04 |
| 23.97 | -10.36 | 16.24 | 14.93 | 15.65 | 16.63 | -9.09 | 25.02 |
| 70.11 | 24.48 | 36.81 | 32.73 | 33.22 | 37.19 | 25.12 | 71.15 |
Widząc, że powyższa macierz zmienia się tak aby po rogach były jak największe wartości, a zatem dąży do tego aby tam postwaic pionek. W pozycjach (2,2) (2,7) (7,2) i (7,7) algorytm ustalił liczby ujemne, czyli ma unikać stawiania tam pionków. Takie ustwianie jest zgodne z taktyką gry, najważniejsze w grze jest opanowanie narożników, natomiast środek pola jest mało istotny co widać też po macierzy. Algorytm dąży do wyrównania wartości w tych miejscach. Z przeprowadzonych wczesniej doświadczeń na samym algorytmie MinMax wynikało, że najlepsza jest macierz, w której rogach są duże wartości, a reszta pól wypełniona jest jedynkami. Algorytm grający z takimi cechami przegrywał niezmiernie rzadko. Można zaobserwować, że algorytm uczący się dąży do takiej macierzy, niestety po pięciuset rozgrywakch nie da się wyuczyć takich cech, przypuszczać można, że gracz biały potrzebowałby parę milionów rozgrywek, aby przekształcić macierz do takiej formy.
Przykład gdy macierz dla gracza uczącego się jest macierzą losowąMacierz przed nauką:
| 10 | -24 | 1 | -50 | -22 | 22 | -84 | 50 |
| 30 | 1 | 40 | 1 | -80 | 60 | 1 | 1 |
| -1 | -5 | 1 | 1 | 1 | 1 | 1 | 20 |
| 50 | 2 | 1 | 1 | 1 | 1 | 40 | 60 |
| -30 | 1 | 1 | 1 | 1 | 4 | 1 | 1 |
| -1 | 1 | 1 | -21 | 1 | 1 | 1 | 1 |
| -4 | 100 | 1 | 1 | 222 | 1 | 50 | 1 |
| -100 | 1 | 52 | 400 | 30 | 1 | 1 | 220 |
Macierz po nauce:
| -8.68 | -26.57 | 3.17 | -56.07 | -28.30 | 19.03 | -80.81 | 58.46 |
| 41.67 | 1.09 | 39.99 | -7.99 | -91.49 | 59.45 | 0.41 | 16.31 |
| 19.79 | 3.34 | -17.65 | -36.42 | -9.96 | -9.46 | -2.85 | 38.57 |
| 70.96 | 4.13 | -72.28 | 1.00 | 1.00 | -24.19 | 42.44 | -36.44 |
| -11.49 | 2.22 | -16.11 | 1.00 | 1.00 | -4.30 | 19.60 | 33.76 |
| 10.40 | 36.33 | 26.16 | -13.23 | 17.76 | 26.22 | 34.85 | 33.19 |
| 36.13 | 163.70 | 73.09 | 88.97 | 304.08 | 79.86 | 122.53 | 46.05 |
| 36.13 | 163.70 | 73.09 | 88.97 | 304.08 | 79.86 | 122.53 | 46.05 |
| -69.80 | 73.83 | 138.58 | 527.49 | 142.08 | 103.40 | 75.88 | 261.38 |
Po przeprowadzeniu 500 gier treningowych widać, że przy losowej macierzy startowej również wyraznie zwiększa się wartość po rogach. Jednak nauka jest nie wielka, pomimo zwiększenia współczynnika alfa, który odpowiada z predkośc uczenia się, został on zwiększony o połowę.
Z przeprowadzonych wczesniejszych doswiadczeń kiedy obaj zawodnicy grali tym samym algorytmem (MiniMax) wynika, że zwycięzca nie był jednoznaczny. Z tego powodu algorytm uczenia daje efekty dopiero przy dużej ilości partii treningowych. Niestety z powodu złożoności obliczeniowej, mającej wpływ na czas liczenia testy przeprowadziliśmy jedynie dla 500 partii.
Pomimo tak małej liczby rozegranych meczy uczących można stwierdzić, że algorytm uczenia działa. Najlepiej widać to na pierwszym przykładzie kiedy zawodnik biały grając z lepszym od siebie zawodnikiem po 75 rozegranych meczach zaczol wygrywac. Po 500 rozegranych spotkaniach wygrał już znacznie wiecej partii.
Z badań przeprowadzonych przez Nees Jan van Eck, Michiel van Wezel zamieszonych na stronie http://people.few.eur.nl/mvanwezel/rl.othello.ejor.pdf wynika, że algorytm uczenia daje widoczne efekty po 5 mln rpzegranych partii.
"Systemy uczące się " - Paweł Cichosz Wydawnictwo Naukowo Techniczne Warszawa 2000
"Algorytmy, struktury danych i techniki programowania" - Piotr Wróblewski Wydawnistwo Helion 1997