Projekt z przedmiotu Sztuczna Inteligencja.
Autor: Piotr Młynarczyk
Data: 22 czerwca 2008
Lines of Action(LOA) jest dwuosobową grą planszową o sumie zerowej. Gra LOA została wymyślona przez Claude Soucie około 1960r. Sid Sackson(1969) opisał ją w pierwszym wydaniu książki "A Gamut of Games".
Gra rozgrywana jest na kwadratowej planszy rozmiaru 8x8, przez dwóch graczy "Białego" i "Czarnego". Na początku rozgrywki pionki czarne ustawione są na sześciu środkowych polach pierwszego i ósmego wiersza(b1-g1 oraz b8-g8), białe natomiast na sześciu środkowych polach pierwszej i ósmej kolumny(a2-a7 oraz h2-h7). Początkowe ustawienie pionków przedstawia poniższy rysunek:
+-----------------+
8 | . B B B B B B . |
7 | W . . . . . . W |
6 | W . . . . . . W | B - black(czarne)
5 | W . . . . . . W | W - white(białe)
4 | W . . . . . . W | . - pole puste
3 | W . . . . . . W |
2 | W . . . . . . W |
1 | . B B B B B B . |
+-----------------+
a b c d e f g h
Gracze wykonują na przemian ruchy według zasad opisanych poniżej:
Celem gracza jest połączenie wszystkich jego pionków w jedną grupę(spójną składową). Pionki są połączone jeżeli stoją na sąsiednich polach, przy czym sąsiednie pola rozumiemy poprzez pola połączone w pionie, poziomie jak i diagonalnie. W przypadku równoczesnego połączenia pionków w jedną grupę przez obu graczy gra kończy się remisem. Jeżeli, gracz nie może wykonać ruchu jego kolejka jest pomijana. Jeżeli ta sama pozycja z tym samym graczem mającym wykonać ruch powtarza się po raz trzeci, gra również kończy się remisem.
Dodatkowo opis gry można znaleźć na angielskiej Wikipedii, oraz
na polskiej stronie pionek.pl(polska nazwa gry to "Szyki").
Celem projektu było napisanie programu grającego w grę LOA. Na program składają się następujące elementy:
Program napisałem w języku C++. Mój program umożliwia rozegranie gry z komputerem jak i rozegranie partii typu komputer-komputer. Program zawiera również drobny interfejs tekstowy wyświetlający plansze i opisy wykonywanych ruchów.
Gra LOA choć stosunkowo popularna w niektórych krajach Europy, nie jest grą łatwą. Poznając reguły gry nie do końca wiadomo jak grać, aby wygrać. Problemem może być chociażby rozstrzygnięcie czy warto zbijać pionki przeciwnika. Wydaje się, że skoro będzie miał ich mniej to łatwiej będzie połączyć wszystkie w jedną grupę. Natomiast jeżeli zbicie jednego pionka powoduje rozbicie pojedyńczej grupy na więcej mniejszych to może się okazać, iż jest to słuszne zagranie. Pozostaje także zastanowić się czy przenieść wszystkie pionki z jednego brzegu na drugi czy też ruszyć wszystkie pionki na środek planszy i tam budować jedną grupę. Dodatkowo skoro pionki nie mogą przeskakiwać pionków przeciwnika może warto rozważyć blokowanie pionków innego koloru.
Z przyczyn opisanych powyżaj jak i jeszcze kilku innych wynika, że ciężko jest określić sytuację w grze, oraz strategię jaką powinno się grać. Z analogicznych powodów ciężko jest zbudować dobrą funkcję heurystyczną oceny planszy. Jest to swojego rodzaju wyzwaniem.
W dowolnej sytuacji na planszy, każdy pionek może wykonać do 8 ruchów. Pionków na planszy jednego koloru może być(o ile żaden nie zostanie zbity) 12. Wynika z tego, iż gracz w pojedyńczym ruchu wybiera jedno z nawet 96 posunięć. W pracy doktorskiej "Informed Search in Complex Games" Mark Winands pisze, że z analizy różnych rozgrywek wynika, iż średnia liczba ruchów w jednej turze to 29, natomiast średnia długość gry to 44 ruchy. Stąd szacunkowa złożoność drzewa gry to O(10^64), oraz szacunkowa złożoność przestrzeni stanów to O(10^23). Wynika z tego, że przy dzisiejszej mocy komputerów gra LOA nie może być rozgrywana przy pomycy algorytmów typu brute-force.
Podobnie sytuacja wygląda z ilością stanów końcowych gry. Gra rozpoczyna się z 24 pionkami na planszy, jednak ich liczba może maleć podczas trwania rozgrywki. Większość końcowych stanów gry jednak nadal zawiera ponad 10 pionków, co sprawia, iż baza zakończeń gry nie może być wykorzystana w programie grającym. Mark Winands pisze, że baza zakończeń gry, na które składa się dokładnie 10 pionków zajmowałaby około 10 terabajtów.
Bazując głównie na pracy doktorskiej "Informed Search in Complex Games", której autorem jest Mark Winands, oraz pracy magisterskiej "Analysis and Implementation of Lines of Action" tego samego autora opiszę ważniejsze elementy, na które należy zwrócić uwagę budując heurystyczną funkcję oceny planszy.
Jeżeli gracz może w jednym ruchu połączyć wszystkie swoje pionki w jedną grupę, sytuacje taką nazywamy zagrożeniem(ang. threat). W takiej sytuacji zazwyczaj konieczne jest aby oponent rozbił swoją własną formację, aby uniemożliwić przeciwnikowi połączenie pionków w jedną grupę. Sytuacja taka bardzo często jest spotykana w grze. Podczas moich rozgrywek nie jednokrotnie się z nią spotkałem. Poniższy rysunek przedstawia przykładową sytuację: biały gracz ma możliwość połączenia wszystkich swoich pionków za pomocą ruchu e8-e6, jedyne co może w takiej sytuacji zrobić gracz czarny, aby nie przegrać to rozbić własną formację i wykonać ruch g4-e4.
+-----------------+
8 | . . . . W . . B |
7 | . . . . . . . . |
6 | . . . . . . . . |
5 | . . . W . . B . |
4 | . . . . W . B . |
3 | . W W W . . B . |
2 | . . B . . . . B |
1 | . . B . . . . . |
+-----------------+
a b c d e f g h
Formacją solidną nazywamy grupę pionków, które są połączone w więcej niż jednym kierunku. Inaczej mówiąc są to grupy, których nie można rozbić na mniejsze zbiciem tylko jednego pionka. Jednym z głównych przyczyn budowania takich formacji jest fakt, iż jest je bardzo trudno rozbić, jednak mają też swoje wady. Jadną z wad jest to, że zbudowanie takiej grupy zazwyczaj zabiera dużo więcej czasu i potrzeba do tego więcej ruchów. Przykład takiej formacji znajduje się na rysunku poniżej:
+-----------------+
8 | . . . . . . . . |
7 | . . . . . . . . |
6 | B . . . . . . . |
5 | . W . . . . . . |
4 | W B B B . . . . |
3 | W B B B . B . . |
2 | . W . W . . . . |
1 | . . . W B . . . |
+-----------------+
a b c d e f g h
Bardzo ważne jest aby podczas rozgrywki mieć dużo możliwości wykonania ruchu. Im większa mobilność tym łatwiej połączyć swoje pionki w jedną grupę, a także łatwiej rozbić formację przeciwnika. W mobilności nie liczy się jednak tylko ilość możliwych do wykonania ruchów, ale także jakie są to ruchy. Okazuje się, że niektóre powinny być bardziej punktowane od innych.
Ponieważ pionki nie mogą przeskakiwać pionków innego koloru, może się zdażyć, że jakiś pionek jest zablokowany. Sytuację taką przedstawia rysunek poniżej:
+-----------------+
8 | W B . . . . . . |
7 | B B . . . . . . |
6 | . . . . . . . . |
5 | . . . . W W . . |
4 | . . B W . . W W |
3 | . . . B B B . . |
2 | . . . . . B . B |
1 | . . . . . . . . |
+-----------------+
a b c d e f g h
Biały pionek na pozycji a8 nie może wykonać, żadnego ruchu. Aby wygrać biały gracz musi najpierw rozbić swoją formację i uwolnić pionka z pozycji a8. Na co niestety być może będzie potrzebował dużej liczby ruchów. Okazuje się, że nawet częściowe blokowanie może być całkiem skuteczne.
Centralizacja oznacza tyle, że pionki dominujące środek planszy są ważniejsze od innych. Tę własność można rozumieć na dwa sposoby. Jeden z nich to taki, że pionki będące w środku planszy są ważniejsze, drugi natomiast to, że pionki które ten środek kontrolują są ważniejsze. Zasada ta ma dosyć proste wytłumaczenie. Ponieważ pionki są początkowo na dwóch końcach planszy to oczywiste jest, że muszą(przynajmniej ich część) przejść przez jej środek.
Jak już wspomniałem wcześniej nie jest do końca jasne czy opłacalne może być zbijanie pionków przeciwnika(zupełnie inaczej wygląda to w grach takich jak Szachy czy Warcaby). Z jednej strony mniejsza liczba pionków oznacza, mniej pionków do połączenia. Z drugiej jednak strony są sytuację, w których zbicie pionka przeciwnika, może być bardzo dobrym ruchem. Przykładowo można zbijając pionka przeciwnika zlikwidować zagrożenie opisywane wyżej. Często zbicie pionka przeciwnika jest jedynym sposobem na odblokowanie własnego pionka. Jeszcze inna sytuacja to możliwość połączenia swoich pionków w jedną grupę wykonująć ruch bijący. Dodatkowo mając więcej pionków można mieć także większą mobilność, o której wspominałem wyżej.
W niektórych grach okazuje się, że któryś z graczy ma strategię wygrywającą. Dla niektórych z niech mimo, iż wiadomo który gracz ma strategię wygrywającą, strategia ta nie jest znana. Mimo to często gracz rozpoczynający gre ma większe szanse na zwycięstwo. Przykładowo jest tak w grze Szachy czy Go, z eksperymentów wynika, że podobnie jest w grze LOA. Dodatkowo pokazano, że w grze LOA na szchownicy rozmiaru 3x3 strategię wygrywającą ma gracz biały, natomiast dla gier 4x4 oraz 5x5 strategię ma gracz czarny. Dla planszy 3x3, to że strategię ma gracz biały jest wyjątkowe i wynika z małych rozmiarów planszy. Niestety nie wiadomo jak to jest dla planszy nxn dla więszych wartości n, jednak często wygrywa zawodnik grający pionkami czarnymi. Stąd też wniosek, że bardzo ważna jest inicjatywa.
W programach używających algorytmu Alfa-Beta, bardzo istotnym elementem jest zaimplementowanie generatora ruchów, który będzie szybki. W LOA generowani ruchów nie jest łatwe. Zauważmy, że liczba pól o jakie przesuwają się pionki zależy od ustawienia innych pionków, co utrudnia generowanie ruchów. Są natomiast pewne ułatwienia. Ruch zależy jedynie od ustawienia pionków w danej linii. Możliwe jest więc obliczenie, dla każdej możliwej linii ruchów i spamiętanie ich w tablicy. Teraz do wygenerowania wszystkich możliwych ruchów, wystarczy kilkadziesiąt razy(dokłądnie 46) odwołać się do tablicy i już mamy wszystkie możliwe do wykonania ruchy.
Podczas przeszukiwania drzewa gry, bardzo ważne jest wykrycie pozycji końcowych. Ponieważ każdy z węzłów w drzewie może być stanem końcowym, to w każdym z węzłów należy sprawdzić czy tak jest. Stąd też procedura sprawdzania czy aktualny stan jest stanem końcowym gry musi być zaimplementowana tak aby działała szybko. W grze LOA to zadanie nie jest łatwe i pochłania więcej czasu niż w grach takich jak Warcaby. Jednym z oczywistych sposobów do sprawdzenia czy aktualny stan jest stanem końcowym jest sprawdzenie czy liczba spójnych składowych jest równa jeden lub też czy w jakiejś spójnej składowej znajdują się wszystkie pionki. Dokonać tego można stosując algorytm przeszukiwania DFS. Jak się okazuje nic lepszego nie da się zrobić. Jedyna możliwość to dobre zaimplementowanie algorytmu DFS. W moim programie algorytm ten realizuje na maskach bitowych, co znacznie go przyśpiesza. Jednakże jest jeszcze jedno drobne ułatwienie. Jak pisze Winands w swojej pracy magisterskiej istnieje heurystyka wykrywająca 99% przypadków, w których gra napewno nie jest zakończona. Polega ona na policzeniu odpowiednich "czwórek". Czwórką nazywamy kwadrat składający się z czterech pól. W grze LOA wyróżniamy sześć rodzajów czwórek(pomijając obroty i symetrie):
. . . . czwórka pusta . . . B czwórka z jednym pionkiem . B . B czwórka z dwoma pionkami B B . B czwórka z trzema pionkami B B B B czwórka z czterema pionkami B . . B czwórka z dwomia diagonalnie połączonymi pionkami
Aby obliczyć liczbę spójnych składowych obliczamy następującą liczbę (zwaną liczbą Eulera): E=(∑Q_1-∑Q_3-2*∑Q_d)/4. Gdzie Q_1 to czwórka zawierająca jeden pionek, Q_3 czwórka zawierająca trzy pionki, oraz Q_d to czwórka zawierająca dwa pionki połączone diagonalnie. Liczba ta mówi ile jest spójnych składowych minus liczba ścian w grafie(dokładniej grafie planarnym, ale z takim mamy tutaj doczynienie). Niestety jeżeli w grafie znajdą się jakieś ściany to liczba ta nie będzie równa liczbie spójnych składowych, jeżeli jednak liczba ta jest większa od jeden to gra napewno nie jest zakończona.
W moim programie plansza reprezentowana jest na kilka odmiennych sposobów. Wynika to z tego, iż różne elementy oceny planszy lepiej i szybciej oblicza się na innych reprezentacjach. Oczywiście większa liczba reprezentacji planszy powoduje zwiększenie liczby zmian podczas wykonywania ruchu jednakże koszt ten nie jest duży, a znacznie przyśpiesza obliczanie funkcji heurystycznej.
Jedna z reprezentacji planszy to zapis dla każdego pionka współrzędnych na których się on znajduje, a także informacji czy został już zbity. Do takiej reprezentacji dodatkowo potrzebne są informacje z planszy jaki pionek(pionek o jakim numerze) stoi na danej pozycji.
Inna reprezentacja to reprezentacja pionków każdego z kolorów w maskach bitowych. Ponieważ pól na planszy jest 64 i na każdym z nich pionek albo jest albo go nie ma, to wszystkich możliwości rozmieszczenia pionków jednego koloru na planszy jest 2^64. Łatwo więc jest to reprezentować jako jedna liczba typu unsigned long long. Taka reprezentacja pozwala łatwo i stosunkowo szybko wykonać algorytm DFS do wykrycia stanu końcowego gry.
Kolejną reprezentacją jaką zastosowałem w moim programie jest reprezentowanie planszy przez zapis jako maski bitowe poszczególnych linii(pionowych, poziomych i ukośnych). Taka reprezentacja pozwala szybko generować możliwe do wykonania ruchy, oraz obliczać niektóre elementy funkcji heurystycznej, gdyż niektóre wartości można wcześniej spamietać dla poszczególnych lini, a następnie tylko się odwołać do tablicy.
Ostatnia już reprezentacja jest to reprezentowanie planszy poprzez "czwórki" jakie zawiera. Pozwala to na szybkie i łatwe używanie funkcji heurystycznej sprawdzania czy stan jest stanem końcowym gry, oraz szybkie obliczanie składnika funkcji oceny planszy zwanego "Czwórki".
Funkcja oceniająca stan planszy bazuje na elementach opisanych wyżej. Wszystkie elementy tej funkcji zaczerpnięte zostały również z pracy "Informed Search in Complex Games", której autorem jest autor jednego z najlepszych obecnie programów grających w tę gre. Jego program "MIA", niejednokrotnie wygrywał na zawodach Computer Olympiad. W swojej pracy zdradził, przynajmniej fragmentarczynie składniki jego funkcji heurystycznej oceny planszy. Dodatko bardzo ważne jest aby funkcja ta była bardzo szybko obliczana. Poniżej opisuje też sposoby, dzięki którym uzyskałem nie najgorsze rezultaty czasowe.
Jest to pierwszy składnik funkcji oceniającej plansze, bazujący na zagrożeniach i solidnych formacjach. Jego celem jest zmierzenie jak blisko siebie są pionki. Właściwość ta jest obliczana na podstawie środka masy pionków(opisany poniżej). W moim programie obliczam ją analogicznie do tego jak jest wyliczana w programie MIA. Na początku obliczany jest środek masy pionków jako średnia ich współrzędnych. Natępnie dla każdego pionka wyliczana jest minimalna ilość pól do środka masy. W kolejnym kroku od sumy tych odległości odejmowana jest minimalna sumaryczna odległość jaką można uzyskać z aktualną liczbą pionków na planszy. Wynika to z tego, iż przykładowo mając 10 pionków nie da się ich ułożyć lepiej niż tak, żeby sumarczna minimalna odległość wynosiła mniej jak 10. Stąd dla układu 10 pionków od symy odległości zostanie odjęte 10. Aby przyśpieszyć obliczenia wartości minimalnych sumarycznych odległości dla każdej ilości pionków są obliczone wcześniej i przechowywane w tablicy. Jako wynik funkcji zwracana jest wartość 1/(obliczona_suma - minimalna_suma).
Ten składnik funkcji oceniającej planszę bazuje na własności planszy opisanej wyżej pod tą samą nazwą, jak również na właściowości blokowania. Zgodnie z tą właściwością pionki znajdujące się bliżej środka planszy otrzymują więcej punktów niż te, które znajdują się przy brzegach. Dodatkowo pionki znajdujące się na brzegach otrzymują ujemne punkty gdyż łatwo jest je zablokować. Największą ujemną wartość otrzymują pionki znajdujące się na rogach planszy, gdyż te jest najłatwiej zablokować. W programie oblczanie tej podfunkcji realizowane jest poprzez tablicę wartości pól, do której wystarczy się odwołać, aby otrzymać wartość danej pozycji.
W tym składniku funkcji oceniającej obliczany jest środek masy pionków, następnie w zależności od jego pozycji na planszy przydzielane są mu punkty. Im bliżej środka planszy tym więcej punktów. Składnik ten broni przed budowaniem formacji na brzegach planszy, które to są łątwe do zablokowania. Pewnym zagrożeniem jest, iż to, że środek masy wypada blisko środka wcale nie oznacza, że pionki są blisko siebie. Jeżeli środek masy jest w środku planszy pionki mogą być równomiernie rozłożone na brzegach, natomiast jeżeli środek masy jest na brzegu to pionki muszą znajdować się blisko siebie. Inaczej jakieś pionki musiałyby być poza planszą.
Kolejnym ważnym elementem funkcji oceniającej są "czwórki", które bazują na właściwości solidnych formacji. W funkcji oceniającej pod uwagę bierzemy czwórki zawierające 3 i 4 pionki, gdyż te reprezentują grupę pionków połączonych w więcej niż jednym kierunku. Ponieważ nie chcemy aby solidne formacje budowane były na brzegach i daleko od środka masy to do funkcji wliczamy(podobnie jak w programie MIA) tylko te czwórki, które znajdują się w odległości co najwyżej dwóch pól od środka masy.
Ta podfunkcja oblicza mobilność pionków i wywodzi się z własności o tej samej nazwie. Każdy z pionków za każdy możliwy do wykonania ruch otrzyma pewne punkty. Ilość punktów ściśle zależy od jakości danego ruchu. Punkty ruchu pionka przesuwającego go na brzeg planszy są dzielone przez dwa, podobnie punkty ruchu wzdłóż brzegu planszy. Natomiast punkty ruchu bijącego są przemnażane przez dwa.
Jak już wiemy ilość ruchów w jednej turze może być stosunkowo duża, więc aby szybko obliczyć wartość tej funkcji zauważamy, iż ruch w danej linii nie zależy od ustawienia pionkow w innych liniach, stąd wszystkie wartości dla opisu jednej linii są obliczone wcześniej i przechowywane w tablicy. Następnie podczas obliczania wartości funkcji wystarczy kilkanaście odwołań do tablicy i już znamy wartość funkcji.
Ta część funkcji jest stosunkowo prosta w interpretacji. Polega ona na obliczniu ilości połączeń między pionkami na planszy, a następnie pod uwagę brana jest średnia liczba połączeń przypadająca na jednego pionka(podobnie zrobione jest to w programie MIA, inaczej jednak w programie YL, którego autorem jest Yngvi Bjornsson, gdzie wliczana jest sumaryczna liczba połączeń).
Aby szybko obliczać wartość tej funkcji podobnie jak w funkcji obliczjącej mobilność, wartości dla opisu pojedyńczej linii są obliczone wcześcniej i przechowywane w tablicy.
Ostatni już składnik, funkcji oceny planszy to bardzo prosta w obliczeniu wartość, a jednocześnie stosunkowo skuteczna i dobrze opisująca sytuację na planszy. Jednolitość jest obliczana jako pole najmniejszego prostokąta zawierającego wszystkie pionki danego koloru. Im pole to jest mniejsze tym więcej punktów w ocenie.
Funkcja oceniające planszę składa się z podfunkcji opisanych powyżej. Wszystkie jej składniki są brane do niej z odpowiednią wagą. Wagi dla każdej z funkcji dobrałem eksperymentalnie. Początkowo sprawdzałem jak funkcja ocenie plansze, które są dostępne jako testy na stronie Mark'a Winands'a. Następnie rozgrywając partie z programem MIA jak i z samym sobą poprawiałem wagi tak aby program nie gral ukierunkowanie pod jedną ze składowych funkcji. Tak zaimplementowana funkcja heurystyczna wraz z generowaniem ruchów i sprawdzaniem końca gry pozwoliła osiągnąć poziom przeszukiwania równy 6(na pojedyńczy ruch czekam do 20 sekund). Dla poziomu 7 niestety czasami poczekać trzeba, aż do 4-5 minut.
W zamierzeniu program miał grać bardzo dobrze. Na tyle dobrze, żeby być może nie równym ale trudnym przeciwnikiem dla najlepszych programów grających w LOA. Cel postawiony był wysoko i nie do końca udało się go zrealizować. Oczywiście program wygrywa ze mną jak również z moimi kolegami. Jednak nie zawsze dorze radził sobie z przeciwnikiem w postaci innego programu. Swoje testy przeprowadzałem stopniowo na różnych etapach budowy funkcji oceniającej. Dało się zauważyć, że im bardziej rozbudowana jest funkacja oceniająca tym lepiej gra program.
Program Loa 1.0 jest programem tekstowym, grającym w grę LOA. Moj program wygrywał z tym programem stosunkowo szybko(po wprowadzeniu dopiero kilku elementów funkcji oceniającej. Ostateczna wersja mojego programu również wygrywała z tym programem. Takiego rezultatu można się było spodziewać, gdyż z tego co mi wiadomo program Loa 1.0 w funkcji oceniającej pod uwagę bierze jedynie liczbę grup pionków.
Program Loa 2D(można go też znaleźć pod nazwą Loa3.5) jest kolejnym programem, z którym postanowiłem skonfrontować mój program. Program ten udostępnia 10 poziomów trudności, jednak nawet na poziomie 10 opisanym jako "very hard" mój program poradził sobie i wygrał rozgrywkę. Loa 2D przegrał nawet, kiedy grał na najwyższym poziomie i sam rozpoczynał grę.
Kolejny program jaki postawiłem naprzeciw mojemu był program Loaw4. Jak się okazało był to kolejny program, który nie potrafił wygrać z moim. Udostępnia on 5 poziomów trudności, jednak nawet na najwyższym mój program okazał się być lepszym. Niestety nie udało mi się tak uruchomić tego programu aby on rozpoczynał grę.
W pewnym momencie nadszedł czas zmierzenia się z największym przeciwnikiem. Program MIA jest uznawany obecnie za najlepszy grający w grę LOA. Niejednokrotnie wygrywał turnieje rozgrywane w ramach Computer Olympiad. Program MIA jest udostępniany jako program GameMaster Beta, umożliwiający rozegranie gry z różnymi wersjami programu MIA. Umożliwia także zmianę niektórych parametrów funkcji oceniającej plansze programów MIA. Jak się można było spodziewać program MIA był najtrudniejszym przeciwnikiem. Niestety, mimo bardziej rozbudowanej funkcji oceniającej udało mi się wygrać z nim tylko 3 razy i za każdym razem grając z wersją pierwszą programu MIA i dodatkowo wyłączonymi wszystkimi opcjami ułatwiającymi mu rozgrywkę.
Pierwsza wygrana mojego programu nastąpiła na stosunkowo wczesnym etapie budowy funkcji oceniającej. Jednak wygrana ta okazuje się być dość przypadkowa. Program MIA również stosuje funkcje oceniajcą, która widocznie błędnie oceniała układy budowane przez mój program. Całkiem ciekawy okazał się koniec rozgrywki, gdyż na koniec zostały na planszy po 3 pionki każdego koloru. Końcówka przebiegu rozgrywki znajduje sie na rysunku poniżej:
ruch: c5 na c4 ruch: a3 na b4 ruch: e5 na d5 +-----------------+ +-----------------+ +-----------------+ 8 | . . . . . . . . | 8 | . . . . . . . . | 8 | . . . . . . . . | 7 | . . . . . . . . | 7 | . . . . . . . . | 7 | . . . . . . . . | 6 | . W . . . . . . | 6 | . W . . . . . . | 6 | . W . . . . . . | 5 | . . . . B . . . | 5 | . . . . B . . . | 5 | . . . B . . . . | 4 | . . B W . . . . | 4 | . W B W . . . . | 4 | . W B W . . . . | 3 | W B . . . . . . | 3 | . B . . . . . . | 3 | . B . . . . . . | 2 | . . . . . . . . | 2 | . . . . . . . . | 2 | . . . . . . . . | 1 | . . . . . . . . | 1 | . . . . . . . . | 1 | . . . . . . . . | +-----------------+ +-----------------+ +-----------------+ a b c d e f g h a b c d e f g h a b c d e f g h
Kolejne dwie wygrane mojego programu nastąpiły przy ostatecznej już funkcji oceniającej, na etapie dobierania odpowiednich współczynników. Wygrane te następowały po stosunkowo wyrównanej walce. Po ostatecznym ustaleniu wsółczynników mój program rozgrywa wyrównaną walkę z programem MIA1 i długo nie widać kto ma przewagę i kto wygra. Jednak pod koniec okazuje się, że program MIA znajduje drogę do zwycięstwa.
Każda inna wersja programu MIA okazuje się być, znacznie lepsza od mojego programu i z nim wygrywa. Mimo tego mój program nie jest łatwym przeciwnikiem dla tych programów.
Dodatkowe partie rozegrałem z programem napisanym przez Pawła Pająka(program również napisany jako projekt z przedmiotu Sztuczna Inteligencja). Mój program okazał się nieco szybszy, od programu Pawła, co prawdopodobnie wynika z użycia przeze mnie wielu reprezentacji planszy, na podstawie których łatwiej obliczane są składniki funkcji oceniającej. Ostatnie partie rozegraliśmy zanim ustaliłem ostateczne współczynniki w moim programie. Zasadniczo partia kończyła się wygraną gracza rozpoczynającego partię, poza dwoma wyjątkami. Jedna z sytuacji to gdy poziom przeszukiwaniu ustawiliśmy na 3, niezależnie czy zaczynał mój program, czy też program Pawła wygrywał program wykonujący drugi ruch(grający kolorem białym). Druga to sytuacja, gdy poziom przeszukiwania ustawiony był na poziomie 6 pomimo tego, że mój program rozpoczynał grę, to wygrał program Pawła. Sytuacja taka najprawdopodobniej wynika z nie do końca dobrze ustawionych współczynników w moim programie. Niestety po ostatecznym ustawieniu współczynników nasze programy nie grały ze sobą.
Podczas testów, dało się zauważyć pewne różnice czasowe w działaniu programów. Część tych różnic może być spowodowana bardziej rozbudowaną funkcją heurystyczną w moim programie. Z drugiej strony program MIA działa szybciej od mojego programu, a w niektórych wersjach tego programu jego funkcja jest jeszcze bardziej rozbudowana. Jednakże jego szybkość wynika z zastosowania innych dodatkowych heurystyk przyśpieszających przeszukiwanie drzewa gry.
Jak się okazuje, co zresztą potwierdza Mark Winands w swojej pracy, że algorytm alfa-beta jest dobrą podstawą do zbudowania dobrego programu grającego. Bardzo ważne jednak przy tego typu algorytmach jest zaimplementowanie dobrej(dobrze oddającej sytuację na planszy) funkcji oceniającej. W grze takiej jak LOA zbudowanie takiej funkcji nie jest prostym zadaniem. Zwykłe porównanie ilości spójnych grup okazuje się nie być dobrym pomysłem(programy grające w ten sposób przegrywają z moim), tym bardziej, że już na początku gry każdy gracz ma zaledwie dwie takie grupy.
Jak daje się zauważyć po rozegraniu kilkudziesięciu gier z programem MIA, bardzo istotne jest nie tylko wybranie dobrej funkcji oceniającej, ale również należy dobrze dobrać współczynniki dla elementów składających się na nią. Istotnym elementem w programie grającym mogą okazać się też dodatkowe heurystyki przyśpieszające przeszukiwanie drzewa gry, a także zastosowanie dodatkowych algorytmów takich jak "proof number search". Bardzo pomocne może być także zaimplementowanie maszynowego uczenia się co pomoże ustalić dobre współczynniki.