- Mini-max algoritam je rekurzivni ili backtracking algoritam koji se koristi u donošenju odluka i teoriji igara. Omogućuje optimalan potez za igrača pod pretpostavkom da protivnik također igra optimalno.
- Mini-Max algoritam koristi rekurziju za pretraživanje kroz stablo igre.
- Min-Max algoritam uglavnom se koristi za igranje igara u AI. Kao što su šah, dame, tic-tac-toe, go i razne igre za vuču. Ovaj algoritam izračunava minimax odluku za trenutno stanje.
- U ovom algoritmu dva igrača igraju igru, jedan se zove MAX, a drugi se zove MIN.
- Oba se igrača bore s tim jer protivnički igrač dobiva minimalnu korist, dok oni dobivaju maksimalnu korist.
- Oba igrača u igri su protivnici jedan drugome, gdje će MAX odabrati maksimalnu vrijednost, a MIN će odabrati minimalnu vrijednost.
- Minimax algoritam izvodi algoritam pretraživanja najprije u dubinu za istraživanje cijelog stabla igre.
- Minimax algoritam nastavlja sve do terminalnog čvora stabla, zatim vraća stablo unatrag kao rekurziju.
Pseudokod za MinMax algoritam:
function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva
Početni poziv:
Minimax(čvor, 3, istina)
Rad algoritma Min-Max:
- Rad minimax algoritma može se lako opisati pomoću primjera. U nastavku smo uzeli primjer stabla igre koje predstavlja igru za dva igrača.
- U ovom primjeru postoje dva igrača, jedan se zove Maximizer, a drugi Minimizer.
- Maximizer će pokušati dobiti maksimalni mogući rezultat, a Minimizer će pokušati dobiti najmanji mogući rezultat.
- Ovaj algoritam primjenjuje DFS, tako da u ovom stablu igre moramo proći cijeli put kroz lišće da bismo došli do terminalnih čvorova.
- Na terminalnom čvoru dane su terminalne vrijednosti pa ćemo te vrijednosti usporediti i vratiti se u stablo dok se ne pojavi početno stanje. Slijede glavni koraci uključeni u rješavanje stabla igre za dva igrača:
Korak 1: U prvom koraku, algoritam generira cijelo stablo igre i primjenjuje funkciju korisnosti kako bi dobio vrijednosti korisnosti za stanja terminala. U donjem dijagramu stabla, uzmimo da je A početno stanje stabla. Pretpostavimo da će maksimizator uzeti prvi krug koji ima početnu vrijednost u najgorem slučaju =- beskonačno, a minimizator će uzeti sljedeći krug koji ima početnu vrijednost u najgorem slučaju = +beskonačno.
Korak 2: Sada, prvo pronalazimo vrijednost pomoćnih programa za Maximizer, njegova početna vrijednost je -∞, pa ćemo svaku vrijednost u terminalnom stanju usporediti s početnom vrijednošću Maximizera i odrediti više vrijednosti čvorova. Naći će maksimum među svima.
- Za čvor D max(-1,- -∞) => max(-1,4)= 4
- Za čvor E max(2, -∞) => max(2, 6)= 6
- Za čvor F max(-3, -∞) => max(-3,-5) = -3
- Za čvor G max(0, -∞) = max(0, 7) = 7
Korak 3: U sljedećem koraku je red na minimizator, tako da će usporediti sve vrijednosti čvorova s +∞ i pronaći će 3rdvrijednosti čvora sloja.
- Za čvor B= min(4,6) = 4
- Za čvor C= min (-3, 7) = -3
Korak 4: Sada je red na Maximizer, i on će ponovno odabrati najveću vrijednost svih čvorova i pronaći maksimalnu vrijednost za korijenski čvor. U ovom stablu igre postoje samo 4 sloja, stoga odmah dolazimo do korijenskog čvora, ali u stvarnim igrama bit će više od 4 sloja.
- Za čvor A max(4, -3)= 4
To je bio kompletan tijek rada minimax igre za dva igrača.
Svojstva Mini-Max algoritma:
Ograničenje minimax algoritma:
Glavni nedostatak minimax algoritma je taj što postaje stvarno spor za složene igre kao što su šah, go, itd. Ova vrsta igara ima veliki faktor grananja, a igrač ima mnogo izbora za odlučivanje. Ovo ograničenje minimax algoritma može se poboljšati iz alfa-beta rezidba o čemu smo raspravljali u sljedećoj temi.