Algorytm mini-max

Data dodania: 2011-09-18, Autor: Michał Jurczyński, Dodał: Karol, Wyświetleń: 768

Opisywany w tym artykule 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.

Strategia “mini-max”

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:

gracz wygra: 1 remis: 0 gracz przegra: -1

Jak widać na poziomie gracza wybierany jest stan maksymalny z pośród wszystkich stanów do których może doprowadzić, na poziomie przeciwnika wybierany jest stan minimalny.

Ł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.

Pseudokod algorytmu “mini-max”:

MINI-MAX(sytuacja, gracz, głębokość)
 . . if głębokość > limit_głębokości then
 . . . return OCEŃ_SYTUACJĘ(sytuacja)

 . . r = WYGENERUJ_MOŻLIWE_RUCHY(sytuacja, gracz)

 . . if gracz = 0
 . . . minimax := 0
 . . else
 . . . minimax := inf

 . . . foreach x in r
 . . . . sytuacja' := WYKONAJ_RUCH(sytuacja, x)
 . . . . t := MINI-MAX(sytuacja, PRZECIWNIK(gracz), głębokość + 1)
 . . . . if gracz = 0 and t > minimax then
 . . . . . minimax:=t
 . . . . else if gracz = 1 and t < minimax then
 . . . . . minimax:=t

 . . return minimax

Obcinanie alfa-beta

Oczywistą sprawą jest to, że niezależnie od rodzaju gry i doboru funkcji stanu, im głębiej przeszukujemy drzewo gry tym lepszym graczem jest nasz program. W podejściu standardowym drzewo poszukiwania nie może być zbyt głębokie. (np. mój program grający w warcaby nie może zejść poniżej głębokości 5 w analizie – odpowiada to, zgodnie z literaturą, poziomowi początkującego gracza). Można jednak prowadzić głębszą analizę nie zajmując się przypadkami, które są w oczywisty sposób bezsensowne. Jeżeli analizując drzewo gry mamy wykonać ruch po którym stan gry będzie gorszy od najlepszego gwarantowanego, nie przeprowadzamy dalszej analizy tej gałęzi drzewa.

Funkcje oceny stanu stosowane w różnych grach

Warcaby

Podejście podstawowe

Zwracamy uwagę jedynie na liczbę pionków swoich i przeciwnika, damki liczą się jako n pionków.

Podejście z obszarami strategicznymi

Punktujemy każdego pionka znajdującego się w obszarze niebieskim, czerwonym, zielonym odpowiednio x, y, z punktami, damkę traktujemy jako n pionków (od swoich punktów odejmujemy punkty przeciwnika)

Podejście Chellapila i Fogel'a

Sytuacja jest punktowana przez sieć neuronową zbudowaną z kilku warstw, pierwsza jest podłączona do pól planszy, ostatnia zbudowana jest z pojedynczego neuronu zwracającego wynik. Istotną wadą tej metody jest bardzo duża liczba parametrów (po kilka-kilkanaście dla każdego neuronu; łącznie około 5000) które koniecznie trzeba dobierać stosując algorytmy genetyczne, co autorom tego podejścia zajęło około 8 miesięcy.

Kółko i krzyżyk

W tej grze nie występują pionki, które można by punktować, więc trzeba sobie radzić inaczej. W grze na nieskończonej planszy do pięciu, można dawać graczowi punkty za rozpoczęte ciągi krzyżyków lub kółek, w zależności od ich długości.

Szachy

Ze względu na popularność tej gry, programy grające w szachy są najbardziej rozwinięte i ciekawe. Stosuje się w nich wiele usprawnień zwykłego podejścia “mini-max”:

-początkowe ruchy nie są wyznaczane metodą “mini-max”, ale wybierane z wygenerowanego wcześniej (na przykład przez super komputer, albo na podstawie przebiegów gier mistrzów) słownika -ponieważ liczba możliwych do przeprowadzenia gier jest większa niż występująca w praktyce liczba stanów gry, opłaca się zapisywanie wyników pracy funkcji MINI-MAX w tablicy z haszowaniem -podczas przeszukiwania drzewa dba się o to, aby zaczynać od ruchów potencjalnie najlepszych (co istotnie zwiększa efektywność obcinania alfa-beta) -poza punktowaniem poszczególnych figur i pionków, dodaje się punkty za ilość pól znajdującą się pod biciem gracza, nagrody za doprowadzenie do szachu, kary za izolowane pionki, kary za nie chronione figury, etc.

Gry wiedzy niepełnej

Ponieważ nie jest znany cały stan gry, nie można stworzyć funkcji która by go wprost oceniała. Programy grające (uczciwie) w gry karciane stosują funkcje obliczające prawdopodobieństwo tego, że dana sytuacja jest korzystna.

Genetyczna metoda dobierania współczynników

Jak widać do napisania programu grającego w jakąkolwiek grę potrzebna jest cała masa współczynników. Czasami można je intuicyjnie dobrać, ale często jest ich zbyt dużo, albo ich rola nie jest oczywista i nie jesteśmy tego w stanie zrobić dobrze. Autorzy wielu programów posługują się algorytmami genetycznymi dla znalezienia tych współczynników. Uogólniony pseudokod takiego algorytmu wygląda następująco:

1.Niech S będzie początkową populacją n osobników
2.Zastosuj n-krotnie rekombinację genów na osobnikach z S
3.Zastosuj n-krotnie mutację dla osobników z S
4.Przeprowadź turniej 3n osobników
5.Niech S będzie grupą n najlepszych osobników w turnieju
6.Przejdź do punktu 2.

W zależności od rodzaju gry wybiera się co ma być genomem, jak mają działać operatory genetyczne oraz nakłada się ograniczenia na wartości współczynników. Zwiększanie liczby parametrów obliczanych przez algorytm genetyczny pozwala na osiągnięcie przez program wyższego poziomu gry, ale może znacznie zwiększyć czas potrzebny na “wyewoluowanie” wyniku.

Turniej przeprowadza się w taki sposób, aby osiągnąć kompromis pomiędzy ilością walk w turnieju, a miarodajnością jego rezultatu. Dobrym pomysłem jest przeprowadzanie turnieju w taki sposób, że każdy osobnik walczy z k losowymi innymi osobnikami zaczynając grę. Mamy wtedy nk walk, oraz każdy osobnik gra średnio 2k razy.

Jaki jest poziom mistrzów świata?

Program grający w warcaby implementujący podejście zaproponowane przez Chellapila i Fogel'a został wpisany do Księgi Rekordów Guiness'a jako pierwszy komputer, który pokonał ludzkiego mistrza świata w jakiejkolwiek grze. Głębokość analizy w tym programie sięgała powyżej 70. Dla porównania, aby pokonać początkującego gracza wystarczy analiza 5-7 ruchów wgłąb, dla gracza średnio zaawansowanego potrzeba ich 11.