• Der Mini-Max-Algorithmus ist ein rekursiver oder Backtracking-Algorithmus, der in der Entscheidungsfindung und Spieltheorie verwendet wird. Es bietet dem Spieler einen optimalen Zug, vorausgesetzt, dass der Gegner ebenfalls optimal spielt.
• Der Mini-Max-Algorithmus verwendet Rekursion, um den Spielbaum zu durchsuchen.
• Der Min-Max-Algorithmus wird hauptsächlich für KI-Spiele verwendet. Zum Beispiel Schach, Dame, Tic-Tac-Toe, Go und verschiedene Zwei-Spieler-Spiele. Dieser Algorithmus berechnet die Minimax-Entscheidung für den aktuellen Zustand.
• Bei diesem Algorithmus spielen zwei Spieler das Spiel, einer heißt MAX und der andere heißt MIN.
• Beide Spieler kämpfen dagegen, da der gegnerische Spieler den minimalen Vorteil erhält, während er den maximalen Vorteil erhält.
• Beide Spieler des Spiels sind Gegenspieler, wobei MAX den maximierten Wert und MIN den minimierten Wert auswählt.
• Der Minimax-Algorithmus führt einen Tiefensuchalgorithmus zur Erkundung des gesamten Spielbaums durch.
• Der Minimax-Algorithmus fährt bis zum Endknoten des Baums fort und verfolgt dann den Baum als Rekursion zurück.

Pseudocode für MinMax-Algorithmus:

 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 

Erster Anruf:

Minimax(Knoten, 3, wahr)

Funktionsweise des Min-Max-Algorithmus:

• Die Funktionsweise des Minimax-Algorithmus lässt sich anhand eines Beispiels leicht beschreiben. Unten haben wir ein Beispiel für einen Spielbaum genommen, der das Spiel für zwei Spieler darstellt.
• In diesem Beispiel gibt es zwei Spieler, einer heißt Maximizer und der andere heißt Minimizer.
• Maximizer versucht, die maximal mögliche Punktzahl zu erreichen, und Minimizer versucht, die minimal mögliche Punktzahl zu erreichen.
• Dieser Algorithmus wendet DFS an, sodass wir in diesem Spielbaum den gesamten Weg durch die Blätter gehen müssen, um die Endknoten zu erreichen.
• Am Endknoten werden die Endwerte angegeben, sodass wir diese Werte vergleichen und den Baum zurückverfolgen, bis der Anfangszustand eintritt. Im Folgenden sind die wichtigsten Schritte zur Lösung des Zwei-Spieler-Spielbaums aufgeführt:

Schritt 1: Im ersten Schritt generiert der Algorithmus den gesamten Spielbaum und wendet die Nutzenfunktion an, um die Nutzenwerte für die Endzustände zu erhalten. Nehmen wir im folgenden Baumdiagramm an, dass A der Anfangszustand des Baums ist. Nehmen wir an, dass der Maximierer die erste Runde macht, deren Anfangswert im ungünstigsten Fall =-unendlich ist, und dass der Minimierer die nächste Runde macht, deren Anfangswert im ungünstigsten Fall = +unendlich ist.

Schritt 2: Nun ermitteln wir zunächst den Dienstprogrammwert für den Maximizer. Sein Anfangswert ist -∞. Daher vergleichen wir jeden Wert im Endzustand mit dem Anfangswert des Maximizers und bestimmen die Werte der höheren Knoten. Es wird das Maximum unter allen finden.

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

Schritt 3: Im nächsten Schritt ist der Minimierer an der Reihe, sodass er alle Knotenwerte mit +∞ vergleicht und die 3 findet^rdLayer-Knotenwerte.

• Für Knoten B= min(4,6) = 4
• Für Knoten C= min (-3, 7) = -3

Schritt 4: Jetzt ist Maximizer an der Reihe und wählt erneut den Maximalwert aller Knoten und ermittelt den Maximalwert für den Wurzelknoten. In diesem Spielbaum gibt es nur 4 Schichten, daher gelangen wir direkt zum Wurzelknoten, aber in echten Spielen wird es mehr als 4 Schichten geben.

• Für Knoten A max(4, -3)= 4

Das war der komplette Arbeitsablauf des Minimax-Spiels für zwei Spieler.

Eigenschaften des Mini-Max-Algorithmus:

Vollständig-Der Min-Max-Algorithmus ist abgeschlossen. Es wird auf jeden Fall eine Lösung (falls vorhanden) im endlichen Suchbaum finden.Optimal-Der Min-Max-Algorithmus ist optimal, wenn beide Gegner optimal spielen.Zeitkomplexität-Da DFS für den Spielbaum durchgeführt wird, ist auch die zeitliche Komplexität des Min-Max-Algorithmus gleich O(geb^M) , wobei b der Verzweigungsfaktor des Wildbaums und m die maximale Tiefe des Baums ist.Raumkomplexität-Die räumliche Komplexität des Mini-Max-Algorithmus ähnelt auch der von DFS Um .

Einschränkung des Minimax-Algorithmus:

Der Hauptnachteil des Minimax-Algorithmus besteht darin, dass er bei komplexen Spielen wie Schach, Go usw. sehr langsam wird. Diese Art von Spielen hat einen großen Verzweigungsfaktor und der Spieler hat viele Entscheidungsmöglichkeiten. Diese Einschränkung des Minimax-Algorithmus kann verbessert werden Alpha-Beta-Schnitt was wir im nächsten Thema besprochen haben.