logo

Mini-Max algoritam u umjetnoj inteligenciji

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

Mini-Max algoritam u AI

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
Mini-Max algoritam u AI

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
Mini-Max algoritam u AI

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
Mini-Max algoritam u AI

To je bio kompletan tijek rada minimax igre za dva igrača.

Svojstva Mini-Max algoritma:

    Kompletan-Min-Max algoritam je dovršen. Definitivno će pronaći rješenje (ako postoji) u konačnom stablu pretraživanja.Optimalno-Min-Max algoritam je optimalan ako oba protivnika igraju optimalno.Vremenska složenost-Budući da izvodi DFS za stablo igre, vremenska složenost Min-Max algoritma je O(bm) , gdje je b faktor grananja stabla igre, a m najveća dubina stabla.Svemirska složenost-Prostorna složenost Mini-max algoritma također je slična DFS-u koji je O(bm) .

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.