Minimax ist eine Art Backtracking-Algorithmus, der in der Entscheidungsfindung und Spieltheorie verwendet wird, um den optimalen Zug für einen Spieler zu finden, vorausgesetzt, dass Ihr Gegner ebenfalls optimal spielt. Es wird häufig in rundenbasierten Spielen für zwei Spieler wie Tic-Tac-Toe, Backgammon, Mancala, Schach usw. verwendet.
Bei Minimax heißen die beiden Player Maximierer und Minimierer. Der Maximierer versucht, die höchstmögliche Punktzahl zu erreichen, während die Minimierer versucht das Gegenteil zu tun und die niedrigstmögliche Punktzahl zu erzielen.
Jedem Platinenstatus ist ein Wert zugeordnet. Wenn in einem bestimmten Zustand der Maximierer die Oberhand hat, wird die Punktzahl des Bretts tendenziell einen positiven Wert haben. Wenn der Minimierer in diesem Platinenzustand die Oberhand hat, wird es tendenziell einen negativen Wert geben. Die Werte des Bretts werden durch einige Heuristiken berechnet, die für jede Art von Spiel einzigartig sind.
Beispiel:
Stellen Sie sich ein Spiel vor, das 4 Endzustände hat und die Pfade zum Erreichen des Endzustands von der Wurzel bis zu den 4 Blättern eines perfekten Binärbaums reichen, wie unten gezeigt. Angenommen, Sie sind der maximierende Spieler und erhalten die erste Chance, sich zu bewegen, d. h. Sie befinden sich an der Wurzel und Ihr Gegner auf der nächsten Ebene. Welchen Zug würden Sie als maximierender Spieler machen, wenn Ihr Gegner ebenfalls optimal spielt?
Da es sich um einen auf Backtracking basierenden Algorithmus handelt, probiert er alle möglichen Züge aus, geht dann zurück und trifft eine Entscheidung.
- Der Maximierer geht nach LINKS: Jetzt sind die Minimierer an der Reihe. Der Minimierer hat nun die Wahl zwischen 3 und 5. Als Minimierer wählt er definitiv den kleinsten von beiden, also 3
- Der Maximierer geht nach rechts: Jetzt sind die Minimierer an der Reihe. Der Minimierer hat nun die Wahl zwischen 2 und 9. Er wird 2 wählen, da dies der kleinste der beiden Werte ist.
Als Maximierer würden Sie den größeren Wert wählen, nämlich 3. Daher ist die optimale Bewegung für den Maximierer, nach LINKS zu gehen, und der optimale Wert ist 3.
Jetzt sieht der Spielbaum wie folgt aus:
Der obige Baum zeigt zwei mögliche Ergebnisse, wenn der Maximierer Links- und Rechtsbewegungen ausführt.
Hinweis: Auch wenn im rechten Teilbaum der Wert 9 vorhanden ist, wird der Minimierer diesen niemals auswählen. Wir müssen immer davon ausgehen, dass unser Gegner optimal spielt.
Nachfolgend finden Sie die entsprechende Implementierung.
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 macht eine While-Schleife
>
>
Java
binärer Suchbaum
// 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> |
>
>
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.> |
>
>
Java-Index von
Python3
# 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
Dereferenzierungszeiger c
> // 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);> > > > |
>
>
Ausgabe:
The optimal value is: 12>
Zeitkomplexität: O(b^d) b ist der Verzweigungsfaktor und d ist die Anzahl der Tiefe oder Lage des Diagramms oder Baums.
Raumkomplexität: O(bd) wobei b der Verzweigungsfaktor in d ist, ähnlich wie bei DFS, die maximale Tiefe des Baums.
Die Idee dieses Artikels besteht darin, Minimax anhand eines einfachen Beispiels vorzustellen.
- Im obigen Beispiel gibt es für einen Spieler nur zwei Möglichkeiten. Im Allgemeinen kann es mehr Auswahlmöglichkeiten geben. In diesem Fall müssen wir alle möglichen Züge wiederholen und das Maximum/Minimum finden. Bei Tic-Tac-Toe kann der Startspieler beispielsweise 9 mögliche Züge ausführen.
- Im obigen Beispiel werden uns die Punkte (Blätter des Spielbaums) gegeben. Für ein typisches Spiel müssen wir diese Werte ableiten
Wir werden bald Tic Tac Toe mit dem Minimax-Algorithmus behandeln.
Dieser Artikel wurde verfasst von Akshay L. Aradhya.