Minimax is een soort backtracking-algoritme dat wordt gebruikt in de besluitvorming en de speltheorie om de optimale zet voor een speler te vinden, ervan uitgaande dat je tegenstander ook optimaal speelt. Het wordt veel gebruikt in turn-based spellen voor twee spelers, zoals Tic-Tac-Toe, Backgammon, Mancala, Chess, enz.
In Minimax worden de twee spelers 'maximizer' en 'minimizer' genoemd. De maximalisatie probeert de hoogst mogelijke score te behalen terwijl de minimaliseren probeert het tegenovergestelde te doen en een zo laag mogelijke score te behalen.
Aan elke bestuursstaat is een waarde verbonden. Als in een bepaalde situatie de maximizer de overhand heeft, zal de score van het bord de neiging hebben een positieve waarde te hebben. Als de minimalisator de overhand heeft in die bordstatus, zal deze de neiging hebben een negatieve waarde te hebben. De waarden van het bord worden berekend aan de hand van een aantal heuristieken die uniek zijn voor elk type spel.
Voorbeeld:
Beschouw een spel met vier eindtoestanden en de paden om de eindtoestand te bereiken lopen van de wortel tot vier bladeren van een perfecte binaire boom, zoals hieronder weergegeven. Stel dat jij de maximaliserende speler bent en dat je de eerste kans krijgt om te bewegen, dat wil zeggen dat jij aan de basis staat en je tegenstander op het volgende niveau. Welke zet zou jij doen als maximaliserende speler, aangezien je tegenstander ook optimaal speelt?
Omdat dit een op backtracking gebaseerd algoritme is, probeert het alle mogelijke zetten, keert vervolgens terug en neemt een beslissing.
- Maximizer gaat LINKS: Nu zijn de minimalizers aan de beurt. De minimalisator heeft nu de keuze tussen 3 en 5. Omdat hij de minimalisator is, zal hij zeker de minste van beide kiezen, dat wil zeggen 3
- Maximizer gaat RECHTS: Nu zijn de minimalizers aan de beurt. De minimalisator heeft nu de keuze tussen 2 en 9. Hij zal 2 kiezen omdat dit de kleinste van de twee waarden is.
Als maximizer zou je de grotere waarde, namelijk 3, kiezen. De optimale zet voor de maximalisator is dus om naar LINKS te gaan en de optimale waarde is 3.
Nu ziet de spelboom er als volgt uit:
Java-stapels
De bovenstaande boom toont twee mogelijke scores wanneer de Maximizer bewegingen naar links en naar rechts maakt.
Opmerking: ook al staat er een waarde van 9 in de rechter subboom, de minimalisator zal die waarde nooit kiezen. We moeten er altijd van uitgaan dat onze tegenstander optimaal speelt.
Hieronder vindt u de implementatie hiervoor.
C++
// A simple C++ program to find> // maximum score that> // maximizing player can get.> #include> using> namespace> std;> // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is> // of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> int> minimax(>int> depth,>int> nodeIndex,>bool> isMax,> >int> scores[],>int> h)> {> >// Terminating condition. i.e> >// leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> >// If current move is maximizer,> >// find the maximum attainable> >// value> >if> (isMax)> >return> max(minimax(depth+1, nodeIndex*2,>false>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>false>, scores, h));> >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> min(minimax(depth+1, nodeIndex*2,>true>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>true>, scores, h));> }> // A utility function to find Log n in base 2> int> log2(>int> n)> {> >return> (n==1)? 0 : 1 + log2(n/2);> }> // Driver code> int> main()> {> >// The number of elements in scores must be> >// a power of 2.> >int> scores[] = {3, 5, 2, 9, 12, 5, 23, 23};> >int> n =>sizeof>(scores)/>sizeof>(scores[0]);> >int> h = log2(n);> >int> res = minimax(0, 0,>true>, scores, h);> >cout <<>'The optimal value is : '> << res << endl;> >return> 0;> }> |
>
>
Java
hacken verwerking
// A simple java program to find maximum score that> // maximizing player can get.> import> java.io.*;> class> GFG {> > // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> >static> int> minimax(>int> depth,>int> nodeIndex,>boolean> isMax,> >int> scores[],>int> h)> {> >// Terminating condition. i.e leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> >// If current move is maximizer, find the maximum attainable> >// value> >if> (isMax)> >return> Math.max(minimax(depth+>1>, nodeIndex*>2>,>false>, scores, h),> >minimax(depth+>1>, nodeIndex*>2> +>1>,>false>, scores, h));> >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> Math.min(minimax(depth+>1>, nodeIndex*>2>,>true>, scores, h),> >minimax(depth+>1>, nodeIndex*>2> +>1>,>true>, scores, h));> }> // A utility function to find Log n in base 2> >static> int> log2(>int> n)> {> return> (n==>1>)?>0> :>1> + log2(n/>2>);> }> // Driver code> >public> static> void> main (String[] args) {> >// The number of elements in scores must be> >// a power of 2.> >int> scores[] = {>3>,>5>,>2>,>9>,>12>,>5>,>23>,>23>};> >int> n = scores.length;> >int> h = log2(n);> >int> res = minimax(>0>,>0>,>true>, scores, h);> >System.out.println(>'The optimal value is : '> +res);> > >}> }> // This code is contributed by vt_m> |
>
java string vervangen
>
C#
// A simple C# program to find maximum score that> // maximizing player can get.> using> System;> public> class> GFG> {> > // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> static> int> minimax(>int> depth,>int> nodeIndex,>bool> isMax,> >int> []scores,>int> h)> {> >// Terminating condition. i.e leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> >// If current move is maximizer, find the maximum attainable> >// value> >if> (isMax)> >return> Math.Max(minimax(depth+1, nodeIndex*2,>false>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>false>, scores, h));> >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> Math.Min(minimax(depth+1, nodeIndex*2,>true>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>true>, scores, h));> }> // A utility function to find Log n in base 2> static> int> log2(>int> n)> {> >return> (n==1)? 0 : 1 + log2(n/2);> }> // Driver code> static> public> void> Main ()> {> >// The number of elements in scores must be> >// a power of 2.> >int> []scores = {3, 5, 2, 9, 12, 5, 23, 23};> >int> n = scores.Length;> >int> h = log2(n);> >int> res = minimax(0, 0,>true>, scores, h);> >Console.WriteLine(>'The optimal value is : '> +res);> > }> }> // This code is contributed by ajit.> |
>
>
Python3
geheel getal vergelijken met Java
# A simple Python3 program to find> # maximum score that> # maximizing player can get> import> math> def> minimax (curDepth, nodeIndex,> >maxTurn, scores,> >targetDepth):> ># base case : targetDepth reached> >if> (curDepth>=>=> targetDepth):> >return> scores[nodeIndex]> > >if> (maxTurn):> >return> max>(minimax(curDepth>+> 1>, nodeIndex>*> 2>,> >False>, scores, targetDepth),> >minimax(curDepth>+> 1>, nodeIndex>*> 2> +> 1>,> >False>, scores, targetDepth))> > >else>:> >return> min>(minimax(curDepth>+> 1>, nodeIndex>*> 2>,> >True>, scores, targetDepth),> >minimax(curDepth>+> 1>, nodeIndex>*> 2> +> 1>,> >True>, scores, targetDepth))> > # Driver code> scores>=> [>3>,>5>,>2>,>9>,>12>,>5>,>23>,>23>]> treeDepth>=> math.log(>len>(scores),>2>)> print>(>'The optimal value is : '>, end>=> '')> print>(minimax(>0>,>0>,>True>, scores, treeDepth))> # This code is contributed> # by rootshadow> |
>
>
Javascript
> // Javascript program to find maximum score that> // maximizing player can get.> // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> >function> minimax(depth, nodeIndex, isMax,> >scores, h)> {> >// Terminating condition. i.e leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> > >// If current move is maximizer, find the maximum attainable> >// value> >if> (isMax)> >return> Math.max(minimax(depth+1, nodeIndex*2,>false>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>false>, scores, h));> > >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> Math.min(minimax(depth+1, nodeIndex*2,>true>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>true>, scores, h));> }> > // A utility function to find Log n in base 2> >function> log2(n)> {> return> (n==1)? 0 : 1 + log2(n/2);> }> > // Driver Code> >// The number of elements in scores must be> >// a power of 2.> >let scores = [3, 5, 2, 9, 12, 5, 23, 23];> >let n = scores.length;> >let h = log2(n);> >let res = minimax(0, 0,>true>, scores, h);> >document.write(>'The optimal value is : '> +res);> > > > |
naamgevingsconventie van Java
>
>
Uitgang:
The optimal value is: 12>
Tijdcomplexiteit: O(b^d) b is de vertakkingsfactor en d is de telling van de diepte of laag van een grafiek of boom.
Ruimtecomplexiteit: O(bd) waarbij b de vertakkingsfactor is naar d is de maximale boomdiepte vergelijkbaar met DFS.
Het idee van dit artikel is om Minimax te introduceren met een eenvoudig voorbeeld.
- In het bovenstaande voorbeeld zijn er slechts twee keuzes voor een speler. Over het algemeen kunnen er meer keuzes zijn. In dat geval moeten we alle mogelijke zetten herhalen en het maximum/minimum vinden. In Tic-Tac-Toe kan de startspeler bijvoorbeeld 9 mogelijke zetten maken.
- In het bovenstaande voorbeeld worden de scores (bladeren van Game Tree) aan ons gegeven. Voor een typisch spel moeten we deze waarden afleiden
We zullen binnenkort Tic Tac Toe behandelen met het Minimax-algoritme.
Dit artikel is bijgedragen door Akshay L. Aradhya.