Algorytm


W naszym programie zastosowaliśmy algorytm MiniMax, a dokładniej jego ulepszoną wersję czyli MiniMax z cięciami alfa-beta (MiniMax with alpha-beta prunning). Jest to efektywny algorytm często stosowany przy programowaniu gier logicznych.
Zacznijmy może od 'czystego' algorytmu MiniMax.
Algorytm ten zakłada istnienie dwóch graczy: Min'a i Max'a. Grę zaczyna Max. Max stara się wykonać ruch jak najlepszy, czyli ruch dla którego Min da najgorszą odpowiedź. Innymi słowy Max ze wszystkich swoich ruchów, wybiera ten po którym nawet najlepsze posunięcie Mina, będzie mniej efektywne niż jakakolwiek odpowiedz Mina w przypadku gdy Max wykonałby dowolnie inny ruch.

Wydaje się to troche skomplikowane, jednak wszystko wyjaśnia poniższe drzewo.
MAX        0             1             -1      1 ruch prowadzący do wygranej
          / \           / \            / \     0 ruch prowadzący do remisu
         /   \         /   \          /   \    -1 ruch prowadzący do przegranej
MIN     0     -1     -1     -1       1     1
       / \   / \     / \    / \     / \   / \
      .   . .   .   .   .  .   .   .   . .   .
      .   . .   .   .   .  .   .   .   . .   .
MAX  -1   0 1   -1  1   1  1   1  -1  -1 -1 -1

             I              II             III
Oczywiście ruch II jest najlepszy dla Max'a, ponieważ prowadzi do wygranej. Wiaże się to z tym, iż maksimum z wszystkich wartości odpowiedzi Mina jest najmniejsze (w porownaniu z ruchem I i III). Zatem zgodnie z tym co mówiliśmy wcześniej ruch ten będzie najlepszy dla Maksa.

Aby jednak dokładnie ocenić jak dobre jest posunięcie, należałoby analizować wszystkie możliwe posunięcia i odpowiedzi na nie, aż do osiągnięcia końcowego stanu gry czyli wygranej lub przegranej. O ile możemy zaprogramować idealną grę w kółko i krzyżyk (liczba kombinacji ruchów jest na tyle mała, że można obliczyć ją w sensownym czasie), o tyle w przypadku gry w warcaby nie jest to już możliwe. Ilość kombinacji posunięć (a konkretnie czas ich analizowania) jest powodem dla którego należy ograniczyć się tylko do pewnej liczby przewidywanych posunięć.
Dokładne ocenienie ruchu bez osiągnięcia końcowego stanu jest jednak niemożliwe. Dlatego efektywność posunięcia musimy oszacować. Oszacowania tego dokonuje funkcja oceniająca aktualne ustawienie. W naszym przypadku jest to różnica między ilością białych i czarnych figur (im więcej białych figur tym ruch lepszy dla grającego białymi). Oczywiście należy wprowadzić pewne wartościowanie (pionek damce nie równy), dlatego przyjęliśmy, iż wartość damki jest trzy razy wieksza niż pionka. Oczywiście to ile pionek jest wart w stosunku do damki, zależy od konkretnej sytuacji na planszy, a my przyjęliśmy pewne przybliżenie. Przyczyną dla której zastosowaliśmy tak prostą funkcję oceniającą jest fakt, iż czas jej pojedynczego wykonania jest krótki. Oznacza to, że program przewidzi więcej ruchów niż w przypadku bardziej czasochłonnej funkcji oceniającej. Ważne jest aby znaleźć kompromis między dokładnością oceniania i ilością przewidzianych ruchów.

Zastosowanie prostej funkcji oceniającej wiąże się jednak z pewnym niebezpieczeństwem.
Jeśli np. program przewiduje 10 ruchów do przodu, a w 11 ruchu przeciwnik będzie mógł zbić kilka pionków w jednym posunięciu, to po 10 ruchu sytuacja drastycznie się zmienia, co w efekcie może prowadzić do przegranej.

Niestety algorytm ten nie był zbyt efektywny (przewidywanie więcej niż 9 posunięc do przodu trwało zbyt długo). Dlatego też zmodyfikowaliśmy nieco algorytm, wprowadzając cięcia. Okazuje się, że nie trzeba przeszukiwać wszystkich gałęzi drzewa (oczywiście do pewnej ustalonej głębokości).
Jeśli Max ma mykonać ruch, po którym Min będzie mógł wykonać jak najgorsze ruchy to nie trzeba przeszukiwać wszytkich gałęzi dla ruchu nr II, ponieważ ruch reprezentowany przez pierwszą gałąź (-5) ma juz wiekszą wartość od najbardziej wartościowej gałęzi dla ruchu nr 1 (z punktu widzenia Maks'a). A więc jakie by nie były ruchy reprezentowene przez pozostałe gałęzie ruchu II, to i tak bedzie on gorszy od ruchu I (z punktu widzenia Max'a) A co za tym idzie ruch nr 2 jest lepszy dla Mina niż ruch nr 1. A zatem oczywiste jest, że Max nie może wybrać ruchu nr 2, który jest dla niego gorszy.

MAX          10             5             -3
            / \            / \            / \
           /   \          /  odcinamy    /  odcinamy
MIN      -20   -10      -5     -10      3     1
         / \   / \      / \    / \     / \   / \
        .   . .   .    .   .  .   .   .   . .   .
        .   . .   .    .   .  .   .   .   . .   .
MAX    20  10 25  10   1   1  10  3  -3  -7 -2 -1

             I              II             III
W ten sposob oszczędza się sporo czasu. Oczywiscie wszystko zależny od kolejności sprawdzanych ruchów, bo gdyby ruchy te były analizowane w kolejnośći III -> II -> I, to te cięcia by już nie wystąpiły. Dlatego powinniśmy zadbać o to, aby pierwszy analizowany ruch był jak najlepszy (tylko jak to wcześniej ocenić???).