20. Czerwca 2006.
Metody i algorytmy sztucznej inteligencji
TEMAT: Opracowanie strategii gracza w grze warcaby,
opartej na algorytmie MINMAX oraz poszukiwania najlepszej
funkcji oceniajacej.
Wykonali: Waldemar Gemba 127684, Wojciech Fik 127656
Zalozenia projektu:
W projekcie naszym zalozylismy ,ze stworzymy i inteligentnego
zawodnika w grze warcaby (czlowiek-komputer). Oraz przeprowadzimy badania
i modyfikacje popularnych algorytmow. Najczesciej wykorzystywanym algorytmem
jest algorytm MIN-MAX lub jego rozbudowana wersja CIEC ALFA-BETA.
Opis gry warcaby:
Warcaby - klasyczne 8 x 8
Gra w warcaby toczy sie pomiedzy dwoma osobami (przeciwnikami) nazywanymi
warcabistami (warcabistkami w wypadku kobiet), ktore wykonuja ruchy bierkami
(warcabami) na kwadratowej planszy zwanej warcabnica.
Plansza kwadratowa (warcabnica) sluzaca do gry w warcaby jest podzielona
64 rownych pol (kwadratow) na przemian jasnych i ciemnych.
Gra w warcaby odbywa sie jedynie na ciemnych polach, nazywanych aktywnymi polami.
Warcabnica musi byc ustawiona miedzy graczami w ten sposob, ze kazde pierwsze
lewe pole dla kazdego z graczy jest polem ciemnym.
Do gry w warcaby uzywane sa warcaby (kamienie) jasne i warcaby (kamienie) ciemne.
W warcabach klasycznych 12 kamieniami. Przed rozpoczeciem partii kamienie
sa rozkladane na najblizszych, kazdemu z graczy, rzedach (liniach)
na ciemnych polach tak by dwa srodkowe rzedy pozostaly puste.
W czasie gry w warcaby rozrozniamy nastepujace warcaby :
- warcaby zwykle (kamienie)
- warcaby uprzywilejowane damki. Kamienie i damki roznia sie sposobem
poruszania i bicia. Przesuniecie warcaby z jednego pola na
inne nazywamy ruchem.
Gracze wykonuja kolejno po jednym ruchu, na przemian, wlasnymi warcabami.
Pierwszy ruch wykonuje zawsze gracz grajacy bialymi warcabami. Wykonanie
ruchu jest obowiazkowe - gracz nie moze sie z przypadajacego nan ruchu zrzec.
Warcaby (kamien) moze poruszac sie po przekatnej tylko do przodu na wolne
pole nastepnej linii.
W sytuacji gdy kamien dostanie sie na pole przemiany (ostatnia przeciwlegla
linia w stosunku do linii wyjsciowych tzw. podstawa przeciwnika), to staje sie damka. W celu odroznienia damki od kamienia na kamien ulegajacy przemianie naklada sie warcabe tego samego koloru - czyli korone damki.
Nowo utworzona damka moze wykonac ruch w nastepnym posunieciu po wykonaniu
ruchu przez przeciwnika.
Damka porusza sie po przekatnych (ciemnych polach) we wszystkich kierunkach
(do przodu i do tylu) na dowolne wolne pole.
Jezeli kamien znajduje sie w sasiedztwie po przekatnej warcaby przeciwnika,
za ktora jest wolne pole, to moze on przeskoczyc przez te warcabe i zajac to wolne pole. Warcaba przeciwnika po wykonaniu ruchu jest usuwana z warcabnicy. Calosc operacji nazywa sie zbiciem. Zdjeta z warcabnicy warcabe uwaza sie za zbita. Zbicie moze byc wykonane do przodu lub do tylu.
Jezeli damka po przekatnej znajduje sie bezposrednio lub w dalszym sasiedztwie warcaby przeciwnika, za ktora jest jedno lub wiecej wolnych pol, to moze prze skoczyc przez te warcabe i zajac dowolne wolne pole na tej przekatnej. Warcaba przeskoczona jest zdejmowana z warcabnicy. Calosc operacji nazywana jest zbiciem przez damke. Zbicie moze byc wykonane do przodu lub do tylu.
Zarowno kamien jak i damka moga wykonywac w jednym ruchu zbic wielokrotnych, przy czym w czasie wielokrotnego bicia wolno przechodzic wielokrotnie przez to samo pole, ale nie przez te sama warcabe przeciwnika, zas przeskoki p rzez wlasne warcaby sa niedozwolone. Zbite warcaby przeciwnika wolno usunac z warcabnicy dopiero po zakonczeniu bicia (zasada tureckiego bicia).
Bicie jest obowiazkowe i ma pierwszenstwo przed wykonaniem innego ruchu (zasada przymusu bicia)
W wypadku gdy istnieje wybor pomiedzy zbiciem roznych ilosci warcab przeciwnika, to obowiazkowym jest bicie wiekszej ilosci warcab (zasada bicia wiekszosci). Przy czym damka nie ma przywileju pierwszenstwa wykonania bici a przed biciem kamieniem.
Jezeli gracz ma dwie lub wiecej mozliwosci bicia takiej samej ilosci warcab przeciwnika, to moze wybrac jedna z nich.
Jezeli kamien (zwykla warcaba) przechodzi w czasie bicia przez jedno (z czterech) pol przemiany (w podstawie przeciwnika) i kontynuuje bicie to nie ulega przemianie w damke i nadal pozostaje kamieniem (zwykla warcaba).
Partia warcabowa moze sie zakonczyc wygrana jednego z graczy lub remisem (wynik nierozstrzygniety).
Gracza uznaje sie za zwyciezce w partii jesli jego przeciwnik nie moze wykonac ruchu z powodu:
- braku warcab na warcabnicy (wszystkie zostaly zbite)
- braku mozliwosci ruchu poniewaz jego warcaby zostaly zablokowane
(nie ma wolnych pol do ruchu), w po zostalych przypadkach partie
uznaje sie za zakonczona wynikiem remisowym.
Opis alorytmow:
ALGORYTM MINMAX
Algorytmy przegladajace mozliwe ruchy. Zastosowalismy algorytm MINMAX i dla niego przeprowadzilismy badania z roznymi funkcjami celu i wagami pionkow. Oraz rozbudowalismy nasz algorytm do algorytmu MINMAX z odcieciami (alfa-beta).
Algorytmy oparte na MINMAXie ktory przyjmuje ze jest dwoch graczy i kazdy przyjmy ruch najlepszy dla siebie i najgorszy dla przeciwnika.
Funkcja oceniajaca zwraca:
-1 oznacza ruch prowadzacy do przegranej i bez zmian +1 ruch prowadzacy do wygranej.
Aby moc jak najlepiej poprowadzic ruchy musieli bysmy rozbudowywac tak drzewo, Az do wygranej,
i przewidziec wszystkie mozliwe ruchu niestety jest to zbyt rozbudowane i niemozliwe do wykonania
czasowo i sprzetowo. Jak na razie nasz algorytm radzi sobie do 5 poziomu zaglebien w drzewo. Choc
juz znacznie odczuwamy niewydolnosc sprzetowa, badania odbywaja sie na CELERON-M 1,6 Ghz, 512 MB ram.
Dlatego tez zostalo wymyslona ulepszona wersja algorytmu MIN MAX mianowicie
Algorytm MINMAX z odcieciami lub ALFA-BETA.
Algorytm ten zaklada ze nie trzeba przeszukiwac kazdej galezi drzewa do konca,
leczy tylko do pewniej glebokosci jezeli badana galez nie jest obiecujaca porostu
odcina sie ja. Porostu nie sprawdzamy galezi najgorszych(do pewniej glebokosci)
dla MAX i najlepszych(do pewniej glebokosci) dla MIN bo po co ja wiadomo ze i
tak nie zostana wybrane.
Opis funkcji oceniajacej:
Funkcja oceniajaca ma za zadanie okreslac jaki jest aktualny stan planszy. Pozwala to porownywac inne mozliwe stany planszy ze soba i wyciagac wnioski ktory ruch byl lepszy.
Oczywiscie to jak zostanie oceniony stan planszy a co za tym idzie ruch ma bardzo znaczacy wplyw na podejmowane przez algorytm decyzje.
FUNKCJA 1:
Najprostsza postacia funkcji celu jest funkcja sumujaca wagi ktora:
ocena=ocena+(waga_pionka*pionek)
czyli przeglada cala plansze jezeli wykryje pionka rozpoznaje
go jezeli pionek nalezy do MAX to pionek = +1, a przeciwnik MIN
pionek = -1 i mnozymy przez gory ustalona wage pionkow domyslnie
waga_pionka = 50, waga_damki = 150.
FUNKCJA 2:
Nastepna rozpatrywana funkcja bedzie funkcja ktora zaklada istnienie np. 4 poziomow
Funkcja oceniajaca wyglada tak:
Patrzenie od strony koloru lekko szarego.
If (pionek == IpionekI){
ocena =ocena+(waga_pionkow)*pionek*(na jakim poziome sie znajduje).
}
Poziom1=1, Poziom2=2, Poziom3=3,Poziom4=4.
Dzieki temu otrzymujemy dodatkowa wlasnosc ,ze pionki staraja sie
jak najbardziej dazyc do przodu, aby zamienic sie w damki!!
Oczywiscie wada jest tego rozwiazania ze rozbudowujemy funkcje
oceniajaca o klika rozpatrywan if co z kolei moze spowodowac
wydluzenie liczenia funkcji oraz dzialanie calego algorytmu.
FUNKCJA 3:
Jezeli pionek znajdzie sie na 8 pozycji tj tam gdzie sie zmienia w damke
dajemy mu +300 pkt gratis, poniewaz o tego momentu juz bedzie damka co
spowoduje ze bedzie mial duzo wieksze mozliwosci.
If ((pozycja>=28)&&(pozycja <= 32 )){
Ocena = ocena+(waga_pionka*pionek)+300;
}else{
Ocena = ocena+(waga_pionka*pionek);
}
Badania:
W tej czesci postaramy sie przedstawic jak zadzialaly nasz modyfikacje
naszych algorytmow oraz wplyw postaci funkcji oceniajacej. Przedstawimy
jak sie ma wplyw rodzaj funkcji oceniajacej, waga pionkow, oraz ile zyskujemy
na zastosowaniu ulepszonego algorytmu MINMAX ALFA BETA w porownaniu
ze standardowym algorytmem MIN MAX.
Standardowa tabelka pomiarowa.
Tabela zbiorcza wszystkich tabelek pomiarowych.
Podsumowanie badan:
Nasze pomiary jak widac z tabelki pomiarowej byly wykonywane dla kazdego rodzaju algorytmu i funkcji 5 gier- rozgrywa czlowiek 5-gier rozgrywa komputer i byly brane pod uwage wartosci srednie. Pomiary wykonywalismy za pomoca wbudowanego timera w programie oraz stopera recznego(zegarek), roznice pomiedzy tymi pomiarami na pewno wplynely na wyniki, wykorzystane algorytmy MIN-MAX potrzebuja maksymalnej mocy obliczeniowej, badania byly prowadzone na komputerze mobilnym CELERON 1,6Ghz system operacyjny WINDOWS, czasami dostepna maksymalna moc obliczeniowa nie byla dostepna dla gry co bardzo znacznie wplynelo na badania (np. Tabelka pomiarowa 2 ). Bardzo czesto niektore pomiary czasu w danej tabelce pomiarowej(dla danego zestawienia) byly znaczaco sie rozniace os sredniej danego zagrania, spowodowane bylo to w/w oraz niezidentyfikowanymi zakloceniami, wiec po rozegraniu 10 parti, bardzo czesto czasy dwoch rozegran gry roznily sie od sredniej wiec zostaly joeszcze raz powtórzone.
Aby moc w automatyczny sposob wyciagnac wnioski z badan postanowilem wprowadzic sobie funkcje Fi ktora w mianowniku ma ilosc wygranych komputera (np. 6 = 60% bo mielismy 10 rozegran ) a w mianowniku sredni czas wykonywania jednej tury przez komputer. Na tej podstawie mozemy przyjac za grupe najlepszych pomiary (13,15,16,18),
Wszystkie naleza do algorytmu MINMAX- ALFA BETA co mozemy uznac za najlepszy algorytm przegladania drzewa, pomiary 13 i 16 za to pomiary dla Funkcji 1 a 15 i 18 dla Funkcji 3. Nieco lepsze wymiary dala Funkcja 3 od Funkcji jeden, sa one bardzo podobne do siebie i roznica miesci sie w bledzie pomiarowym wiec mozemy uznac ze F3 daje lepsze od F1 rezultaty lub takie same. Po prze analizowaniu w tabelce zbiorczej wszystkich wartosci Fi dla Funkcji 2 i 3 widac tez sama tendencje co widzimy z pomiarow 13,15,16,18.
Podzial roli:
Wojciech Fik :
przygotowanie merytoryczne do zagadnienia, poszukiwanie materialow, wymyslanie strategii, byl czlowiekiem grajacym z komputerem, przeprowadzil zmudne badania min 300 rozegran. Wspoltworca sprawozdania.
Waldemar Gemba :
glowny programista, pomyslodawca technicznych rozwiazan, wraz z ksiazka wyd. Helion VISUAL C++ 6.0.
Mial wplyw na zastosowanie niektorych rozwiazan teoretycznych ze wzgledu na techniczne mozliwosci. Rozegral niewyobrazalna ilosc rozegran aby wyszukac wszystkie bledy, no i w trakcie pisania testowanie tego co zostalo napisane.
Bibliografia, materialy, wiedza:
linki:
http://www.wpk.p.lodz.pl/~pawian/warcaby/index.html
http://www.warcaby.beep.pl
Znalezione w sieci:
Prace magisterskie:
1. Analiza algorytmow dla gier dwuosobowych Marcin Borkowski Pol. Warszawska
2. Programowanie gry w szachy i warcaby Monika Jaskier Pol. Warszawska
3.Liczne materialy znalezione glownie w sieci na stronach Polskich jak i Zagranicznych (bylo to tak spontanicznie znalezione w sieci ze niejstesmy teraz w stanie podac zrodla).