Alpha Beta Pruning ist eine Optimierungstechnik für den Minimax-Algorithmus. Im Laufe dieses Blogs werden wir diskutieren, was Alpha-Beta-Beschneidung bedeutet, wir werden den Minimax-Algorithmus diskutieren, Regeln, um eine gute Ordnung zu finden, und mehr.
- Einführung
- Minimax-Algorithmus
- Schlüsselpunkte beim Alpha-Beta-Beschneiden
- Funktionsweise des Alpha-Beta-Beschneidens
- Verschieben der Reihenfolge beim Beschneiden
- Regeln zum Finden einer guten Reihenfolge
- Codes in Python
Einleitung
Das Wort ‚Beschneiden‘ bedeutet das Fällen von Ästen und Blättern. In der Datenwissenschaft ist Pruning ein viel verwendeter Begriff, der sich auf Post- und Pre-Pruning in Entscheidungsbäumen und Random Forest bezieht. Alpha-Beta-Beschneidung ist nichts anderes als das Beschneiden nutzloser Zweige in Entscheidungsbäumen. Dieser Alpha-Beta-Beschneidungsalgorithmus wurde in den 1900er Jahren unabhängig von Forschern entdeckt.
Alpha-Beta-Beschneidung ist eine Optimierungstechnik für den Minimax-Algorithmus, die im nächsten Abschnitt erörtert wird. Die Notwendigkeit des Beschneidens ergab sich aus der Tatsache, dass Entscheidungsbäume in einigen Fällen sehr komplex werden. In diesem Baum erhöhen einige nutzlose Zweige die Komplexität des Modells. Um dies zu vermeiden, kommt das Alpha-Beta-Beschneiden ins Spiel, damit der Computer nicht den gesamten Baum betrachten muss. Diese ungewöhnlichen Knoten machen den Algorithmus langsam. Daher wird der Algorithmus durch Entfernen dieser Knoten schnell.
Erfahren Sie mehr über den A*-Algorithmus.
Minimax-Algorithmus
Minimax ist eine klassische Tiefensuch-Technik für ein sequentielles Zwei-Spieler-Spiel. Die beiden Spieler heißen MAX und MIN. Der Minimax-Algorithmus wurde entwickelt, um den optimalen Zug für MAX, den Spieler am Wurzelknoten, zu finden. Der Suchbaum wird erstellt, indem alle Knoten von der Wurzel aus rekursiv tiefenorientiert erweitert werden, bis entweder das Ende des Spiels oder die maximale Suchtiefe erreicht ist. Lassen Sie uns diesen Algorithmus im Detail untersuchen.
Wie bereits erwähnt, gibt es zwei Spieler im Spiel, nämlich- Max und Min. Max macht den ersten Schritt. Max hat die Aufgabe, seine Belohnung zu maximieren, während Min die Aufgabe hat, Maxs Belohnung zu minimieren und gleichzeitig seine eigene Belohnung zu erhöhen. Angenommen, Max kann die Aktionen a, b oder c ausführen. Welche davon gibt Max die beste Belohnung, wenn das Spiel endet? Um diese Frage zu beantworten, müssen wir den Spielbaum ausreichend tief untersuchen und davon ausgehen, dass Min optimal spielt, um die Belohnung von Max zu minimieren.
Hier ist ein Beispiel. Vier Münzen sind in einer Reihe und jeder Spieler kann eine Münze oder zwei Münzen in seinem Zug abholen. Der Spieler, der die letzte Münze aufnimmt, gewinnt. Angenommen, Max spielt zuerst, welchen Zug sollte Max machen, um zu gewinnen?
Wenn Max zwei Münzen auswählt, bleiben nur noch zwei Münzen übrig und Min kann zwei Münzen auswählen und gewinnen. Wenn Sie also 1 Münze aufheben, wird die Belohnung von Max maximiert.
Wie Sie vielleicht bemerkt haben, haben die Knoten des Baumes in der Abbildung unten einige Werte, die als Minimax-Wert bezeichnet werden. Der Minimax-Wert eines Knotens ist der Wert des Knotens, wenn es sich um einen Terminalknoten handelt.
Wenn der Knoten ein nicht terminaler Max-Knoten ist, ist der Minimax-Wert des Knotens das Maximum der Minimax-Werte aller Nachfolger des Knotens. Wenn der Knoten hingegen ein nicht terminaler Min-Knoten ist, ist der Minimax-Wert des Knotens das Minimum der Minimax-Werte aller Nachfolger des Knotens.
Jetzt werden wir die Idee hinter dem Alpha-Beta-Beschneiden diskutieren. Wenn wir Alpha-Beta-Beschneidung auf den Standard-Minimax-Algorithmus anwenden, gibt es die gleiche Entscheidung wie die des Standardalgorithmus, aber es beschneidet oder schneidet die Knoten ab, die im Entscheidungsbaum ungewöhnlich sind, dh die die endgültige Entscheidung des Algorithmus nicht beeinflussen. Dies wird dazu beitragen, die Komplexität bei der Interpretation komplexer Bäume zu vermeiden.
Sehen Sie, wie der KNN-Algorithmus funktioniert.
Lassen Sie uns nun die Intuition hinter dieser Technik diskutieren. Versuchen wir, die Minimax-Entscheidung im folgenden Baum zu finden :
In diesem Fall,
Minimax Entscheidung = MAX {MIN {3, 5, 10}, MIN {2, a, b}, MIN {2, 7, 3}}
= MAX {3, c, 2} = 3
Hier im obigen Ergebnis müssen Sie Zweifel haben, wie wir das Maximum aus dem fehlenden Wert finden können. Also, hier ist auch die Lösung Ihres Zweifels:
Im zweiten Knoten wählen wir den Minimalwert als c, der kleiner oder gleich 2 ist, dh c <= 2. Wenn nun c <= 3 ist und wir das Maximum von 3, c, 2 wählen müssen, ist der Maximalwert 3.
Wir haben eine Entscheidung getroffen, ohne diese Knoten zu betrachten. Und hier kommt das Alpha-Beta-Pruning ins Spiel.
Schlüsselpunkte beim Alpha-Beta-Beschneiden
- Alpha: Alpha ist die beste Wahl oder der höchste Wert, den wir in jedem Fall auf dem Weg von Maximizer gefunden haben. Der Anfangswert für Alpha ist – ∞.
- Beta: Beta ist die beste Wahl oder der niedrigste Wert, den wir in jedem Fall auf dem Weg des Minimierers gefunden haben. Der Anfangswert für Alpha ist + ∞.
- Die Bedingung für das Alpha-Beta-Beschneiden ist, dass α >= β .
- Jeder Knoten muss seine Alpha- und Beta-Werte verfolgen. Alpha kann nur aktualisiert werden, wenn MAX an der Reihe ist, und Beta kann nur aktualisiert werden, wenn MIN an der Reihe ist.
- MAX aktualisiert nur Alpha-Werte und MIN Player aktualisiert nur Beta-Werte.
- Die Knotenwerte werden an die oberen Knoten anstelle von Alpha- und Beta-Werten übergeben, wenn sie in den umgekehrten Baum wechseln.
- Alpha- und Beta-Werte werden nur an untergeordnete Knoten übergeben.
Arbeiten von Alpha-Beta Pruning
- Wir werden zuerst mit dem ersten Schritt beginnen. Wir werden zunächst die Alpha- und Beta-Werte als den schlimmsten Fall definieren, dh α = -∞ und β= +∞. Wir werden den Knoten nur beschneiden, wenn Alpha größer oder gleich Beta wird.
2. Da der Anfangswert von Alpha kleiner als Beta ist, haben wir ihn nicht beschnitten. Jetzt ist MAX an der Reihe. Am Knoten D wird also der Wert von Alpha berechnet. Der Wert von Alpha am Knoten D ist max (2, 3). Der Wert von Alpha am Knoten D ist also 3.
3. Jetzt ist der nächste Zug auf Knoten B und für MIN jetzt an der Reihe. Am Knoten B ist der Wert von Alpha beta also min (3, ∞). Am Knoten B sind die Werte also alpha = – ∞ und Beta ist 3.
Im nächsten Schritt durchlaufen Algorithmen den nächsten Nachfolger von Knoten B, der Knoten E ist, und die Werte α = -∞ und β = 3 werden ebenfalls übergeben.
4. Jetzt ist MAX an der Reihe. Am Knoten E suchen wir also nach MAX. Der aktuelle Wert von Alpha bei E ist – ∞ und wird mit 5 verglichen. Also, MAX (- ∞, 5) wird 5 sein. Also, am Knoten E, alpha = 5, Beta = 5. Nun, wie wir sehen können, ist Alpha größer als Beta, was die Beschneidungsbedingung erfüllt, sodass wir den richtigen Nachfolger von Knoten E beschneiden können und der Algorithmus nicht durchlaufen wird und der Wert an Knoten E 5 beträgt.
6. Im nächsten Schritt kommt der Algorithmus wieder von Knoten B zu Knoten A. Am Knoten A wird alpha auf den Maximalwert als MAX (- ∞, 3) geändert. Jetzt ist der Wert von Alpha und Beta an Knoten A jeweils (3, + ∞) und wird an Knoten C übertragen. Dieselben Werte werden an Knoten F übertragen.
7. Am Knoten F wird der Wert von Alpha mit dem linken Zweig verglichen, der 0 ist. Also, MAX (0, 3) wird 3 sein und dann mit dem rechten Kind verglichen, das 1 ist, und MAX (3,1) = 3 noch α bleibt 3, aber der Knotenwert von F wird 1.
8. Jetzt gibt Knoten F den Knotenwert 1 an C zurück und vergleicht ihn mit dem Beta-Wert bei C. Jetzt ist MIN an der Reihe. Also, MIN (+ ∞, 1) wird 1 sein. Nun ist am Knoten C α = 3 und β = 1 und alpha ist größer als beta, was wiederum die Schnittbedingung erfüllt. Also, der nächste Nachfolger von Knoten C, dh. G wird beschnitten und der Algorithmus hat nicht den gesamten Teilbaum G berechnet.
Jetzt gibt C den Knotenwert an A zurück und der beste Wert von A ist MAX (1, 3) ist 3.
Der oben dargestellte Baum ist der endgültige Baum, der die Knoten zeigt, die berechnet werden, und die Knoten, die nicht berechnet werden. Für dieses Beispiel ist der optimale Wert des Maximierers also 3.
Schauen Sie sich Open-Source-Python-Bibliotheken an.
Bewegungsreihenfolge beim Beschneiden
Die Wirksamkeit des Alpha– Beta-Beschneidens basiert auf der Reihenfolge, in der der Knoten untersucht wird. Die Reihenfolge der Bewegungen spielt eine wichtige Rolle beim Alpha-Beta-Beschneiden.
Es gibt zwei Arten der Zugreihenfolge in Alpha Beta.:
- Schlechteste Reihenfolge: In einigen Fällen von Alpha-Beta-Beschneidung wird keiner der Knoten vom Algorithmus beschnitten und funktioniert wie der Standard-Minimax-Algorithmus. Dies verbraucht viel Zeit als Folge von Alpha- und Beta-Faktoren und gibt auch keine effektiven Ergebnisse. Dies wird als schlechteste Reihenfolge beim Beschneiden bezeichnet. In diesem Fall erfolgt die beste Bewegung auf der rechten Seite des Baumes.
- Ideale Reihenfolge: In einigen Fällen von Alpha Beta Beschneiden viele der Knoten durch den Algorithmus beschnitten. Dies wird als ideale Reihenfolge beim Beschneiden bezeichnet. In diesem Fall erfolgt die beste Bewegung auf der linken Seite des Baumes. Wir wenden DFS an, daher sucht es zuerst links vom Baum und geht in der gleichen Zeit doppelt so tief wie der Minimax-Algorithmus.
Regeln, um eine gute Reihenfolge zu finden
- Der beste Zug erfolgt vom untersten Knoten
- Verwenden Sie Domänenwissen, während Sie den besten Zug finden
- Die Reihenfolge der Knoten sollte so sein, dass die besten Knoten zuerst berechnet werden
Schauen Sie sich dieses Python-Tutorial für Anfänger an
Codes in Python
class MinimaxABAgent: """ Minimax agent """ def __init__(self, max_depth, player_color): """ Initiation Parameters ---------- max_depth : int The max depth of the tree player_color : int The player's index as MAX in minimax algorithm """ self.max_depth = max_depth self.player_color = player_color self.node_expanded = 0 def choose_action(self, state): """ Predict the move using minimax algorithm Parameters ---------- state : State Returns ------- float, str: The evaluation or utility and the action key name """ self.node_expanded = 0 start_time = time.time() print("MINIMAX AB : Wait AI is choosing") list_action = AIElements.get_possible_action(state) eval_score, selected_key_action = self._minimax(0,state,True,float('-inf'),float('inf')) print("MINIMAX : Done, eval = %d, expanded %d" % (eval_score, self.node_expanded)) print("--- %s seconds ---" % (time.time() - start_time)) return (selected_key_action,list_action) def _minimax(self, current_depth, state, is_max_turn, alpha, beta): if current_depth == self.max_depth or state.is_terminal(): return AIElements.evaluation_function(state, self.player_color), "" self.node_expanded += 1 possible_action = AIElements.get_possible_action(state) key_of_actions = list(possible_action.keys()) shuffle(key_of_actions) #randomness best_value = float('-inf') if is_max_turn else float('inf') action_target = "" for action_key in key_of_actions: new_state = AIElements.result_function(state,possible_action) eval_child, action_child = self._minimax(current_depth+1,new_state,not is_max_turn, alpha, beta) if is_max_turn and best_value < eval_child: best_value = eval_child action_target = action_key alpha = max(alpha, best_value) if beta <= alpha: break elif (not is_max_turn) and best_value > eval_child: best_value = eval_child action_target = action_key beta = min(beta, best_value) if beta <= alpha: break return best_value, action_target
In diesem Dokument haben wir eine wichtige Komponente der Spieltheorie gesehen. Obwohl die Leistung des Minimax-Algorithmus gut ist, ist der Algorithmus langsam. Um es schnell zu machen, verwenden wir einen Alpha-Beta-Beschneidungsalgorithmus, der die ungewöhnlichen Knoten aus dem Entscheidungsbaum entfernt, um die Leistung zu verbessern. Heutzutage ist ein schneller und gut ausgeführter Algorithmus weit verbreitet.
Schauen Sie sich diese Kurse für künstliche Intelligenz und maschinelles Lernen an, von großartigem Lernen bis hin zu Weiterbildung in der Domäne und Beherrschung des Alpha-Beta-Beschneidens und anderer solcher Algorithmen.
Weiterführende Literatur
- A * Suchalgorithmus in der künstlichen Intelligenz (KI)
- Entscheidungsbaumalgorithmus mit Beispielen erklärt
- Bester erster Suchalgorithmus in der KI / Konzept, Implementierung, Vorteile, Nachteile
- Was ist künstliche Intelligenz? Wie funktioniert KI, Typen und Zukunft davon?