TechCodeview

• Mini-max-algoritme is een recursief of backtracking-algoritme dat wordt gebruikt in de besluitvorming en speltheorie. Het biedt een optimale zet voor de speler, ervan uitgaande dat de tegenstander ook optimaal speelt.
• Het Mini-Max-algoritme gebruikt recursie om door de spelboom te zoeken.
• Het Min-Max-algoritme wordt meestal gebruikt voor het spelen van games in AI. Zoals schaken, dammen, boter-kaas-en-eieren, go en verschillende sleepspelers. Dit algoritme berekent de minimax-beslissing voor de huidige status.
• In dit algoritme spelen twee spelers het spel, de ene heet MAX en de andere heet MIN.
• Beide spelers vechten ertegen, terwijl de tegenstander het minimale voordeel krijgt, terwijl zij het maximale voordeel behalen.
• Beide spelers van het spel zijn tegenstanders van elkaar, waarbij MAX de maximale waarde selecteert en MIN de minimale waarde selecteert.
• Het minimax-algoritme voert een diepte-eerst zoekalgoritme uit voor het verkennen van de volledige spelboom.
• Het minimax-algoritme gaat helemaal naar beneden tot aan het eindknooppunt van de boom en volgt vervolgens de boom terug als recursie.

Pseudo-code voor MinMax-algoritme:

 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 

Eerste oproep:

Minimax(knooppunt, 3, waar)

Werking van het Min-Max-algoritme:

• De werking van het minimax-algoritme kan eenvoudig worden beschreven aan de hand van een voorbeeld. Hieronder hebben we een voorbeeld genomen van een spelboom die het spel voor twee spelers voorstelt.
• In dit voorbeeld zijn er twee spelers, de ene heet Maximizer en de andere heet Minimizer.
• Maximizer zal proberen de maximaal mogelijke score te behalen, en Minimizer zal proberen de minimaal mogelijke score te behalen.
• Dit algoritme past DFS toe, dus in deze spelboom moeten we helemaal door de bladeren gaan om de eindknooppunten te bereiken.
• Bij het terminalknooppunt worden de terminalwaarden gegeven, dus we zullen die waarden vergelijken en de boom volgen totdat de beginstatus zich voordoet. Hieronder volgen de belangrijkste stappen bij het oplossen van de spelboom voor twee spelers:

Stap 1: In de eerste stap genereert het algoritme de volledige spelboom en past het de hulpprogrammafunctie toe om de hulpprogrammawaarden voor de terminalstatussen te verkrijgen. Laten we in het onderstaande boomdiagram aannemen dat A de begintoestand van de boom is. Stel dat de maximalisatie de eerste beurt neemt met de slechtste beginwaarde = - oneindig, en de minimalisator de volgende beurt zal nemen met de slechtste beginwaarde = + oneindig.

Stap 2: Nu vinden we eerst de nutswaarde voor de Maximizer, de initiële waarde is -∞, dus we vergelijken elke waarde in de terminalstatus met de initiële waarde van Maximizer en bepalen de hogere knooppuntwaarden. Het zal het maximale onder alles vinden.

• Voor knooppunt D max(-1,- -∞) => max(-1,4)= 4
• Voor knooppunt E max(2, -∞) => max(2, 6)= 6
• Voor knooppunt F max(-3, -∞) => max(-3,-5) = -3
• Voor knooppunt G max(0, -∞) = max(0, 7) = 7

Stap 3: In de volgende stap is het de beurt aan de minimalizer, dus het zal alle knooppuntwaarden vergelijken met +∞, en de 3 vinden^rdwaarden van laagknooppunten.

• Voor knooppunt B= min(4,6) = 4
• Voor knooppunt C= min (-3, 7) = -3

Stap 4: Nu is het de beurt aan Maximizer, en deze zal opnieuw de maximale waarde van alle knooppunten kiezen en de maximale waarde voor het hoofdknooppunt vinden. In deze spelboom zijn er slechts 4 lagen, daarom bereiken we onmiddellijk het hoofdknooppunt, maar in echte games zullen er meer dan 4 lagen zijn.

• Voor knooppunt A max(4, -3)= 4

Dat was de volledige workflow van het minimax-spel voor twee spelers.

Eigenschappen van het Mini-Max-algoritme:

Compleet-Min-Max-algoritme is voltooid. Het zal zeker een oplossing vinden (indien aanwezig), in de eindige zoekboom.Optimaal-Het Min-Max-algoritme is optimaal als beide tegenstanders optimaal spelen.Tijdcomplexiteit-Omdat het DFS uitvoert voor de spelboom, is de tijdscomplexiteit van het Min-Max-algoritme hetzelfde O(geb^M) , waarbij b de vertakkingsfactor van de wildboom is, en m de maximale diepte van de boom is.Ruimtecomplexiteit-De ruimtecomplexiteit van het Mini-max-algoritme is ook vergelijkbaar met die van DFS Over .

Beperking van het minimax-algoritme:

Het belangrijkste nadeel van het minimax-algoritme is dat het erg traag wordt bij complexe spellen zoals schaken, go, enz. Dit type spellen heeft een enorme vertakkingsfactor en de speler heeft veel keuzes om te beslissen. Deze beperking van het minimax-algoritme kan worden verbeterd alfa-bèta snoeien die we in het volgende onderwerp hebben besproken.