Budowa strategii gracza oparta na grze logicznej warcaby.

Autor: Dariusz  Wielgosz
Prowadzący: dr inż. Witold Paluszyński
Data: 11 czerwiec 2006

Rozpatrywany Problem:

Głównym zadaniem projektu było opracowanie algorytmu wyznaczającego najlepszy ruch pionka w oparciu o wartość funkcji oceniającej. Do tego celu wykorzystany został standardowy algorytm MiniMax.

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.

Wykorzystane algorytmy:

W grze został wykorzystany algorytm "mini-max".Jest to algorytm składający się z dwóch typów węzłow : max i mini. Algorytm jest standardowo stosowany we wszelkich programach grających w gry planszowe i nie tylko. Celem algorytmu jest wskazanie w danej sytuacji ruchu dającego graczowi strategię wygrywającą, lub przynajmniej dającego możliwie duże prawdopodobieństwo zwycięstwa.

Nazwa algorytmu bierze źródło od przyjętej w nim strategii postępowania: symulując na zmianę ruchy własne i przeciwnika, znajdując się na poziomie przeciwnika wybieramy ruch najgorszy dla gracza, natomiast na poziomie gracza wybieramy ruch dla niego najlepszy. Poniższe drzewo ilustruje tą strategię. Stan gry oceniany jest następująco: 

Łatwo się domyślić, że analizując drzewo gry w ten sposób, nie da się dojść do liści drzewa, tj. do sytuacji w której gra jest rozegrana. Zmusza to do zastosowania heurystycznych funkcji oceniających stan gry. Algorytm przeszukuje wtedy drzewo gry do pewnego ustalonego poziomu na którym stan gry jest ustalany przez zadaną funkcję. Odpowiednie tej funkcji jest kluczem do sukcesu programu.                                                                                                            Rys. 1

                                                                                                                           Rys.2

Na Rys. 2 przedstawiona jest plansza do gry w warcaby wraz z początkowym ustawieniem pionków do gry, a także zaznaczone są  trzy obszary oznaczone odpowiednio kolorami: niebieskim, zielonym i czerwonym. Funkcja oceny polega na rozpoznaniu położenia pionka  i przyporządkowaniu mu wartości tego obszaru (punktujemy każdego pionka znajdującego się w obszarze niebieskim, czerwonym, zielonym odpowiednio x, y, z punktami,damkę traktujemy jako n pionków).Następnie wyznaczamy sumę wszystkich wartośći pionków gracza oraz przeciwnika i odejmujemy sumę wartości pionków gracza od sumy wartośći pionków przeciwnika.

                                                                                                          Funkcja pionkowa (prosta):

                                                                                                                                 Rys.3

Powyższy rysunek przedstawia sposób  realizacji  funkcji pionkowej. Jest to bardzo prosta funkcja oceniająca polegająca  na  punktowaniu  każdego pionka gracza i pionka przeciwnika taką samą  liczbą punktów, (każdego pionka punktowałem 2 pkt natomiast damke 5 pkt), następnie obliczamy liczbę pionków obu graczy i  dla każdego z nich sumujemy ich punkty w zależności od wartości pionka. Po wykonaniu operacji sumowania wyznaczamy ich różnice. Otrzymany wynik porównujemy z pozostałymi ocenami.. 

                                                                                                             Funkcja krawędziowa:

                                                                                                           Rys.4

W funkcji tej rozróżniamy dwa rodzaje pionków. Pionki krawędziowe znajdujące sie na polach  przylegających  do krawędzi  planszy , a także pionki  środkowe znajdujący się poza obszarem oznaczonym czerwoną linia. Każdy z pionków  krawędziowych  punktujemy podwójnie w przypadku damek sytuacja jest podobna.
Następnie wykonujemy standardową operację sumowania i odejmowania.

Testowanie funkcji oceniających:

Po zaimplementowaniu poszczególnych funkcji oceniających przyszedł czas na ich testowanie. Każda z funkcji podłączona została do drzewa w którym głębokość przeszukiwania wynosiła 6. Dla każdej funkcji oceniającej przeprowadzono po dziesięć partii gier kontrolnych które pozwoliły uzyskać  podstawowe informacje  o  efektywności każdej z funkcji oceniających. W tym teście najlepiej  wypadła  funkcja  oceniająca  "trzech obszarów" dlatego tez na niej skupiłem największą uwagę.
W celu poprawienia efektywności  powyższego algorytmu  wykonywałem  pewne zamiany  położenia i wielkości punktowanych obszarów. Wykonywane w tym celu testy nie przyniosły większych efektów w postaci poprawienia funkcji oceniającej.
 

Opis wykonanego programu:

                                                                                             Rys.5

Do testowania funkcji oceny wykorzystałem w całości napisany przeze mnie program do gry w warcaby. Ruchy pionków gracza  wykonywane są za pomocą myszki. Gra rozpoczyna się od  ruchu gracza. Wszystkie ruchy gracza i komputera  zapisywane są  w kolumnach  obok planszy. Program został napisany  w środowisku programistycznym Borland Builder6. Poszczególne funkcje oceniające były podpinane do kodu źródłowego.

Ciekawostka:   

Jaki jest poziom mistrzów świata?