- Mini-max algoritme er en rekursiv eller tilbagesporende algoritme, som bruges i beslutningstagning og spilteori. Det giver et optimalt træk for spilleren, forudsat at modstanderen også spiller optimalt.
- Mini-Max-algoritmen bruger rekursion til at søge gennem spiltræet.
- Min-Max-algoritmen bruges mest til spil i AI. Såsom skak, dam, tic-tac-toe, go og forskellige tow-spillere. Denne algoritme beregner minimax-beslutningen for den aktuelle tilstand.
- I denne algoritme spiller to spillere spillet, den ene hedder MAX og den anden hedder MIN.
- Begge spillere kæmper mod det, da modstanderspilleren får den mindste fordel, mens de får den maksimale fordel.
- Begge spillere i spillet er modstandere af hinanden, hvor MAX vil vælge den maksimerede værdi og MIN vil vælge den minimerede værdi.
- Minimax-algoritmen udfører en dybde-først søgealgoritme til udforskning af det komplette spiltræ.
- Minimax-algoritmen fortsætter helt ned til træets terminalknude, og sporer derefter træet tilbage som rekursion.
Pseudo-kode for MinMax-algoritmen:
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
Indledende opkald:
Minimax(node, 3, sand)
Funktion af Min-Max-algoritmen:
- Funktionen af minimax-algoritmen kan let beskrives ved hjælp af et eksempel. Nedenfor har vi taget et eksempel på game-tree, som repræsenterer to-spiller spillet.
- I dette eksempel er der to spillere, den ene hedder Maximizer og den anden hedder Minimizer.
- Maximizer vil forsøge at få den maksimalt mulige score, og Minimizer vil forsøge at få den mindst mulige score.
- Denne algoritme anvender DFS, så i dette spiltræ skal vi hele vejen gennem bladene for at nå terminalknuderne.
- Ved terminalknudepunktet er terminalværdierne givet, så vi sammenligner disse værdier og sporer træet tilbage, indtil starttilstanden indtræffer. Følgende er de vigtigste trin, der er involveret i løsningen af to-spiller spiltræet:
Trin 1: I det første trin genererer algoritmen hele spiltræet og anvender hjælpefunktionen for at få nytteværdierne for terminaltilstandene. I nedenstående trædiagram, lad os tage A er træets begyndelsestilstand. Antag, at maximizer tager den første tur, som har worst-case initial værdi =-infinity, og minimizer vil tage den næste tur, som har worst case initial værdi = +uendeligt.
Trin 2: Først finder vi hjælpeværdien for Maximizer, dens startværdi er -∞, så vi vil sammenligne hver værdi i terminaltilstand med initialværdien af Maximizer og bestemmer de højere nodeværdier. Det vil finde maksimum blandt alle.
- For node D max(-1,- -∞) => max(-1,4)= 4
- For node E max(2, -∞) => max(2, 6)= 6
- For Node F max(-3, -∞) => max(-3,-5) = -3
- For node G max(0, -∞) = max(0, 7) = 7
Trin 3: I det næste trin er det en tur til minimizer, så det vil sammenligne alle noder værdi med +∞, og vil finde 3rdlag node værdier.
- For node B= min(4,6) = 4
- For node C= min (-3, 7) = -3
Trin 4: Nu er det en tur til Maximizer, og den vil igen vælge den maksimale værdi af alle noder og finde den maksimale værdi for rodnoden. I dette spiltræ er der kun 4 lag, derfor når vi straks til rodnoden, men i rigtige spil vil der være mere end 4 lag.
- For node A max(4, -3)= 4
Det var den komplette arbejdsgang i minimax to-spiller spillet.
Egenskaber for Mini-Max-algoritmen:
Begrænsning af minimax-algoritmen:
Den største ulempe ved minimax-algoritmen er, at den bliver rigtig langsom til komplekse spil som skak, go osv. Denne type spil har en enorm forgreningsfaktor, og spilleren har masser af valg at bestemme. Denne begrænsning af minimax-algoritmen kan forbedres fra alfa-beta beskæring som vi har diskuteret i næste emne.