Autorzy: | Prowadzący: |
Postawiliśmy sobie za cel stworzenie inteligentnego przeciwnika w grze w warcaby. Chcieliśmy sprawdzić, jak skutecznego zawodnika uda nam się zaprojektować.
Do implementacji algoytmu został użyty język C++. Nasz projekt podzieliliśmy na trzy etapy:
2.1 Analiza dostępnych materiałów oraz ocena ich przydatności do implementacji naszego algorytmu.
Żródła informacji, to przede wszystkim literatura książkowa. Są to dwa tomy Leonarda Bolca traktujące o Metodach przeszukiwania heurystycznego. Kolejna pozycją jest tutaj książka Haliny Kwaśnickiej i Artura Spirydowicza "Uczący się komputer. Programowanie gier logicznych".
2.2 Implementacja funkcji wyszykiwania najlepszych posunięć.
Na funkcję oceny w naszym programie mają wpływ następujące parametry:Funkcja oceny ma następującą postać:
ocena = (priorytet pola + bezpieczeństwo ruchu + odległość ) * typ pionka;
Ilość zbitych pionków nie ma w tym momencie wpływu, lecz jest
wykorzystywana w momencie, gdy mamy do wyboru wiecej niż jedno bicie.
Krótka charakterystyka powyższych parametrów ma następującą postać:
- Priorytet pola jest opisany na rysunku obok. Warcabnica jest podzielona na cztery obszary o różnym znaczeniu strategicznym. Według nas im bliżej brzegu, tym mniejsza szansa na zbicie przez pionek przeciwnika, dlatego też wartość tego parametru jest ustalona na 2^(x-1), gdzie x jest priorytetem pola.
- Typ pionka jest jednym z ważniejszych parametrów, gdyż damka ma większe możliwości niż pionek, dlatego też pionek ma wartość 1, a damka 5.
- Odległość od końca planszy. Generalnie rzecz biorąc, im bliżej końca tym lepiej, gdyż bliźsi jesteśmy uzyskania damki, lecz te rejony są też bardziej niebezpieczne, jeżeli chodzi o możliwośc bicia, dlatego też nie ma ten parametr wielkiego wpływu i ogranicza się do liniowej zależności (wartość parametru odległości = 8 - odległość rzeczywista).
- Bezpieczeństwo ruchu ma u Nas jedno z kluczowych znaczeń, gdyż nie chcemy, żeby nasz gracz komputerowy się "podkładał", dlatego też sprawdzamy bliskość pionków przeciwnika i odpowiednio to oceniamy. Jeżeli pionek nie będzie zagrożony, to wartość parametru wzrasta o 4. Dodatkowo jeżeli ruch odbędzie się na pole z największym priorytetem, wartość wzrasta o kolejne 4 punkty.
- Ilość zbitych pionków nie ma znaczenia, gdy mamy do wyboru jedno bicie, lecz ma znaczenie, gdy komputer ma kilka bić do wyboru. Wtedy oczywiście wybierze ten ruch, który zabierze więcej pionków.
Poniżej przedstawiony jest przykład podwójnego bicia (komputer - "1", człowiek - "2") :
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
2.3 Wizualizacja rozgrywki przy pomocy biblioteki Qt.
Wybór wyżej wymienionej biblioteki nie był przypadkowy. Zdecydowaliśmy się na takie rozwiązanie ze względu na platformową niezalezność tego narzędzia.
Na rysunkach poniżej widać, że komputer (brązowe kamienie) stara się wykonywać jak najbezpieczniejsze posunięcia na początku partii. Wszystkie kamienie umieszcza na polach o najwyższej wadze.
3. Budowa programu.
Program składa się z trzech zasadniczych elementów.
Klas Matrix oraz checker - definiują je pliki classes.h oraz classes.cpp
GUI programu - zdefiniowane za pomocą środowiska Qt-Designer
Klasy:Założeniem naszego projektu było stworzenie drzewa ruchów na podstawie algorytmu MiniMax i jego ulepszenia, czyli algorytmu alfa-beta cięć. Niestety nie udało nam się zaimplementować tych metod, dlatego skierowaliśmy nasze wysiłki na stworzenie odpowiedniej funkcji oceniającej, która na podstawie aktualnego rozmieszczenia pionków i przyjętych przez nas parametrów zwracałaby najlepsze lokalnie posuniecie. Zaimplementowany przez nas gracz komputerowy jest możliwy do pokonania przez uważnego gracza, gdyż nie analizuje ruchów "wprzód". Można z nim jednak prowadzić w miarę wyrównaną walkę.
Halina Kwaśnicka, Artur Spirydowicz "Uczący się komputer. Programowanie gier logicznych", Oficyna Wydawnicza Politechniki Wrocławskiej.
Leonard Bolc, Jerzy Cytowski - "Moetody przeszukiwania heurystycznego. T. 1, 2.", Państwowe Wydawnictwo Techniczne
Tomasz Rostański "Programowanie gier planszowych", III konferencja młodych informatyków >> .
Strona zawierająca obszerne informacje nt. gry w warcaby - www.warcaby.beep.pl
