• Mini-max algoritme er en rekursiv eller tilbakesporende algoritme som brukes i beslutningstaking og spilleteori. Det gir et optimalt trekk for spilleren forutsatt at motstanderen også spiller optimalt.
• Mini-Max-algoritmen bruker rekursjon for å søke gjennom spilltreet.
• Min-Max-algoritmen brukes mest for spill i AI. Slik som sjakk, dam, tic-tac-toe, go, og forskjellige tow-spillere. Denne algoritmen beregner minimumsavgjørelsen for gjeldende tilstand.
• I denne algoritmen spiller to spillere spillet, en heter MAX og den andre heter MIN.
• Begge spillerne kjemper mot det som motstanderspilleren får minimum fordel mens de får maksimal fordel.
• Begge spillerne i spillet er motstandere av hverandre, der MAX vil velge den maksimerte verdien og MIN vil velge den minimaliserte verdien.
• Minimax-algoritmen utfører en dybde-først-søkealgoritme for utforskning av hele spilltreet.
• Minimax-algoritmen fortsetter helt ned til terminalnoden til treet, og sporer deretter treet som rekursjon.

Pseudokode for MinMax Algorithm:

 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 

Første samtale:

Minimax(node, 3, sann)

Arbeid av Min-Max-algoritmen:

• Arbeidet til minimax-algoritmen kan enkelt beskrives ved hjelp av et eksempel. Nedenfor har vi tatt et eksempel på game-tree som representerer to-spiller spillet.
• I dette eksemplet er det to spillere, en heter Maximizer og den andre heter Minimizer.
• Maximizer vil prøve å få maksimalt mulig poengsum, og Minimizer vil prøve å få minst mulig poengsum.
• Denne algoritmen bruker DFS, så i dette spilltreet må vi gå hele veien gjennom bladene for å nå terminalnodene.
• Ved terminalnoden er terminalverdiene gitt, så vi vil sammenligne disse verdiene og spore treet tilbake til starttilstanden oppstår. Følgende er hovedtrinnene som er involvert i å løse spilltreet for to spillere:

Trinn 1: I det første trinnet genererer algoritmen hele spilltreet og bruker verktøyfunksjonen for å få verktøyverdiene for terminaltilstandene. I trediagrammet nedenfor, la oss ta A er starttilstanden til treet. Anta at maksimering tar den første svingen som har den verste startverdien =-uendelig, og minimiseringen vil ta neste sving som har den verste innledende verdien = +uendelig.

Steg 2: Nå, først finner vi verktøyverdien for Maximizer, dens startverdi er -∞, så vi vil sammenligne hver verdi i terminaltilstand med initialverdien til Maximizer og bestemmer de høyere nodeverdiene. Det vil finne maksimum blant alle.

• For node D maks(-1,- -∞) => maks(-1,4)= 4
• For node E maks(2, -∞) => maks(2, 6)= 6
• For node F maks(-3, -∞) => maks(-3,-5) = -3
• For node G maks(0, -∞) = maks(0, 7) = 7

Trinn 3: I neste trinn er det en tur for minimisering, så den vil sammenligne alle nodeverdier med +∞, og vil finne 3^rdlagnodeverdier.

• For node B= min(4,6) = 4
• For node C= min (-3, 7) = -3

Trinn 4: Nå er det en tur for Maximizer, og den vil igjen velge maksimalverdien av alle noder og finne maksimalverdien for rotnoden. I dette spilltreet er det bare 4 lag, derfor når vi umiddelbart til rotnoden, men i ekte spill vil det være mer enn 4 lag.

• For node A maks(4, -3)= 4

Det var den komplette arbeidsflyten til minimax-spillet for to spillere.

Egenskaper til Mini-Max-algoritmen:

Fullstendig-Min-Max-algoritmen er fullført. Den vil definitivt finne en løsning (hvis den finnes), i det endelige søketreet.Optimal-Min-Max-algoritmen er optimal hvis begge motstanderne spiller optimalt.Tidskompleksitet-Ettersom den utfører DFS for spilltreet, er tidskompleksiteten til Min-Max-algoritmen det O(b^m) , hvor b er forgreningsfaktoren til vilttreet, og m er den maksimale dybden til treet.Plass kompleksitet-Plasskompleksiteten til Mini-max-algoritmen ligner også på DFS som er Om .

Begrensning av minimax-algoritmen:

Den største ulempen med minimax-algoritmen er at den blir veldig treg for komplekse spill som sjakk, go osv. Denne typen spill har en enorm forgreningsfaktor, og spilleren har mange valg å bestemme seg for. Denne begrensningen av minimax-algoritmen kan forbedres fra alfa-beta beskjæring som vi har diskutert i neste emne.