- 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 3rdlagnodeverdier.
- 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:
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.