- Mini-max-algoritmen är en rekursiv eller backtracking-algoritm som används i beslutsfattande och spelteori. Det ger ett optimalt drag för spelaren förutsatt att motståndaren också spelar optimalt.
- Mini-Max-algoritmen använder rekursion för att söka igenom spelträdet.
- Min-Max-algoritmen används mest för spel i AI. Såsom schack, dam, tic-tac-toe, go och olika tow-spelare. Denna algoritm beräknar minimaxbeslutet för det aktuella tillståndet.
- I denna algoritm spelar två spelare spelet, en heter MAX och den andra kallas MIN.
- Båda spelarna kämpar mot det eftersom motståndarspelaren får minsta fördelen medan de får maximal nytta.
- Båda spelarna i spelet är motståndare till varandra, där MAX väljer det maximerade värdet och MIN väljer det minimerade värdet.
- Minimaxalgoritmen utför en djup-först sökalgoritm för att utforska hela spelträdet.
- Minimaxalgoritmen fortsätter hela vägen ner till trädets terminalnod, och backar sedan trädet som rekursion.
Pseudokod för 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örsta samtalet:
Minimax(nod, 3, sant)
Arbete med Min-Max-algoritmen:
- Hur minimaxalgoritmen fungerar kan enkelt beskrivas med hjälp av ett exempel. Nedan har vi tagit ett exempel på spelträd som representerar tvåspelarspelet.
- I det här exemplet finns det två spelare, en heter Maximizer och den andra heter Minimizer.
- Maximizer kommer att försöka få högsta möjliga poäng, och Minimizer kommer att försöka få minsta möjliga poäng.
- Denna algoritm tillämpar DFS, så i detta spelträd måste vi gå hela vägen genom löven för att nå terminalnoderna.
- Vid terminalnoden ges terminalvärdena så vi kommer att jämföra dessa värden och backa trädet tills det initiala tillståndet inträffar. Följande är de viktigaste stegen för att lösa spelträdet för två spelare:
Steg 1: I det första steget genererar algoritmen hela spelträdet och tillämpar hjälpfunktionen för att få hjälpvärdena för terminaltillstånden. I träddiagrammet nedan, låt oss ta A är trädets initiala tillstånd. Anta att maximeraren tar första sväng som har sämsta utgångsvärde =- oändlighet, och minimering tar nästa sväng som har sämsta utgångsvärde = +oändlighet.
Steg 2: Nu, först hittar vi verktygsvärdet för Maximizern, dess initiala värde är -∞, så vi kommer att jämföra varje värde i terminaltillstånd med initialvärdet för Maximizer och bestämmer de högre nodvärdena. Det kommer att hitta det maximala bland alla.
- För nod D max(-1,- -∞) => max(-1,4)= 4
- För Nod E max(2, -∞) => max(2, 6)= 6
- För Nod F max(-3, -∞) => max(-3,-5) = -3
- För nod G max(0, -∞) = max(0, 7) = 7
Steg 3: I nästa steg är det en tur för minimering, så den kommer att jämföra alla nodvärden med +∞ och hittar 3:anrdlagernodvärden.
- För nod B= min(4,6) = 4
- För nod C= min (-3, 7) = -3
Steg 4: Nu är det en tur för Maximizer, och den kommer återigen att välja det maximala värdet av alla noder och hitta det maximala värdet för rotnoden. I det här spelträdet finns det bara 4 lager, därför når vi omedelbart till rotnoden, men i riktiga spel kommer det att finnas fler än 4 lager.
- För nod A max(4, -3)= 4
Det var hela arbetsflödet i minimax-spelet för två spelare.
Egenskaper för Mini-Max-algoritmen:
Begränsning av minimaxalgoritmen:
Den största nackdelen med minimax-algoritmen är att den blir riktigt långsam för komplexa spel som schack, go, etc. Den här typen av spel har en enorm förgreningsfaktor, och spelaren har många val att välja på. Denna begränsning av minimaxalgoritmen kan förbättras från alfa-beta beskärning som vi har diskuterat i nästa ämne.