logo

TechCodeview

Minimax-Algorithmus in der Spieltheorie | Set 4 (Alpha-Beta-Schnitt)

Voraussetzungen: Minimax-Algorithmus in der Spieltheorie , Bewertungsfunktion in der Spieltheorie
Beim Alpha-Beta-Pruning handelt es sich eigentlich nicht um einen neuen Algorithmus, sondern vielmehr um eine Optimierungstechnik für den Minimax-Algorithmus. Es reduziert die Rechenzeit um einen enormen Faktor. Dadurch können wir viel schneller suchen und sogar in tiefere Ebenen im Spielbaum vordringen. Es schneidet Zweige im Spielbaum ab, die nicht durchsucht werden müssen, da bereits ein besserer Zug verfügbar ist. Es wird Alpha-Beta-Bereinigung genannt, weil es zwei zusätzliche Parameter in der Minimax-Funktion übergibt, nämlich Alpha und Beta.

Definieren wir die Parameter Alpha und Beta.

Alpha ist der beste Wert, den die Maximierer kann derzeit auf diesem Niveau oder darüber garantieren.
Beta ist der beste Wert, den die Minimierer kann derzeit auf diesem Niveau oder darunter garantieren.



Pseudocode:

 function minimax(node, depth, isMaximizingPlayer, alpha, beta): if node is a leaf node : return value of the node if isMaximizingPlayer : bestVal = -INFINITY for each child node : value = minimax(node, depth+1, false, alpha, beta) bestVal = max( bestVal, value) alpha = max( alpha, bestVal) if beta <= alpha: break return bestVal else : bestVal = +INFINITY for each child node : value = minimax(node, depth+1, true, alpha, beta) bestVal = min( bestVal, value) beta = min( beta, bestVal) if beta <= alpha: break return bestVal>
 // Calling the function for the first time. minimax(0, 0, true, -INFINITY, +INFINITY)>

Lassen Sie uns den obigen Algorithmus anhand eines Beispiels verdeutlichen.

Wofür steht Google?

Alpha-Beta-Beschneidung

  • Der erste Anruf beginnt ab A . Der Wert von Alpha beträgt hier -UNENDLICHKEIT und der Wert von Beta ist +UNENDLICH . Diese Werte werden an nachfolgende Knoten im Baum weitergegeben. Bei A Der Maximierer muss max von wählen B Und C , Also A Anrufe B Erste
  • Bei B Dabei muss der Minimierer min wählen D Und UND und daher Anrufe D Erste.
  • Bei D betrachtet es sein linkes untergeordnetes Element, das ein Blattknoten ist. Dieser Knoten gibt einen Wert von 3 zurück. Jetzt ist der Wert von Alpha bei D ist max( -INF, 3), also 3.
  • Um zu entscheiden, ob es sich lohnt, auf den rechten Knoten zu schauen oder nicht, prüft es die Bedingung Beta<=Alpha. Dies ist falsch, da Beta = +INF und Alpha = 3. Daher wird die Suche fortgesetzt.
    • D betrachtet nun sein rechtes Kind, das einen Wert von 5.At zurückgibt D , alpha = max(3, 5), was 5 ist. Nun der Wert von node D ist 5 D gibt einen Wert von 5 zurück B . Bei B , beta = min( +INF, 5) was 5 ist. Dem Minimierer wird nun ein Wert von 5 oder weniger garantiert. B ruft jetzt an UND um zu sehen, ob er einen niedrigeren Wert als 5 erreichen kann.
  • Bei UND Die Werte von Alpha und Beta sind nicht -INF und +INF, sondern -INF bzw. 5, da der Wert von Beta geändert wurde B und das ist es B weitergegeben an UND
  • Jetzt UND schaut auf sein linkes Kind, das 6 ist. At UND , alpha = max(-INF, 6), was 6 ist. Hier wird die Bedingung wahr. Beta ist 5 und Alpha ist 6. Beta<=Alpha ist also wahr. Daher bricht es und UND gibt 6 an zurück B
  • Beachten Sie, dass es egal war, wie hoch der Wert war UND Das richtige Kind ist. Es hätte +INF oder -INF sein können, es wäre trotzdem egal. Wir mussten es uns nicht einmal ansehen, da dem Minimierer ein Wert von 5 oder weniger garantiert wurde. Sobald der Maximierer die 6 sah, wusste er, dass der Minimierer niemals in diese Richtung kommen würde, weil er auf der linken Seite eine 5 bekommen konnte B . Auf diese Weise mussten wir uns diese 9 nicht ansehen und sparten somit Rechenzeit.
    • E gibt einen Wert von 6 zurück B . Bei B , Beta = min( 5, 6), was 5 ist. Der Wert des Knotens B ist auch 5

Bisher sieht unser Spielbaum so aus. Die 9 ist durchgestrichen, da sie nie berechnet wurde.

Alpha-Beta-Beschneidung 2

    B gibt 5 an zurück A . Bei A , alpha = max( -INF, 5) was 5 ist. Jetzt wird dem Maximierer ein Wert von 5 oder mehr garantiert. A ruft jetzt an C um zu sehen, ob es einen höheren Wert als 5 erreichen kann.
  • Bei C , Alpha = 5 und Beta = +INF. C Anrufe F
  • Bei F , Alpha = 5 und Beta = +INF. F schaut auf sein linkes Kind, das eine 1 ist. alpha = max( 5, 1) was immer noch 5 ist.
    • F betrachtet sein rechtes Kind, das eine 2 ist. Daher ist der beste Wert dieses Knotens 2. Alpha bleibt immer noch 5. F gibt einen Wert von 2 zurück C . Bei C , Beta = min( +INF, 2). Die Bedingung Beta <= Alpha wird wahr, wenn Beta = 2 und Alpha = 5. Sie bricht also zusammen und es muss nicht einmal der gesamte Teilbaum von berechnet werden G .
  • Die Intuition hinter diesem Abbruch ist, dass C Dem Minimierer wurde ein Wert von 2 oder weniger garantiert. Dem Maximierer wurde jedoch bereits ein Wert von 5 garantiert, wenn er dies wünscht B . Warum sollte sich also der Maximierer jemals entscheiden? C und einen Wert kleiner als 2 erhalten? Auch hier können Sie sehen, dass es keine Rolle spielte, wie hoch die letzten beiden Werte waren. Wir haben auch viel Rechenaufwand gespart, indem wir einen ganzen Unterbaum übersprungen haben.
    • C gibt jetzt einen Wert von 2 zurück A . Daher das beste Preis-Leistungs-Verhältnis A ist max( 5, 2), was eine 5 ist.
  • Daher ist der optimale Wert, den der Maximierer erhalten kann, 5

So sieht unser endgültiger Spielbaum aus. Wie du sehen kannst G wurde durchgestrichen, da es nie berechnet wurde.

Alpha-Beta-Beschneidung 3

CPP




// C++ program to demonstrate> // working of Alpha-Beta Pruning> #include> using> namespace> std;> // Initial values of> // Alpha and Beta> const> int> MAX = 1000;> const> int> MIN = -1000;> // Returns optimal value for> // current player(Initially called> // for root and maximizer)> int> minimax(>int> depth,>int> nodeIndex,> >bool> maximizingPlayer,> >int> values[],>int> alpha,> >int> beta)> {> > >// Terminating condition. i.e> >// leaf node is reached> >if> (depth == 3)> >return> values[nodeIndex];> >if> (maximizingPlayer)> >{> >int> best = MIN;> >// Recur for left and> >// right children> >for> (>int> i = 0; i <2; i++)> >{> > >int> val = minimax(depth + 1, nodeIndex * 2 + i,> >false>, values, alpha, beta);> >best = max(best, val);> >alpha = max(alpha, best);> >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> >else> >{> >int> best = MAX;> >// Recur for left and> >// right children> >for> (>int> i = 0; i <2; i++)> >{> >int> val = minimax(depth + 1, nodeIndex * 2 + i,> >true>, values, alpha, beta);> >best = min(best, val);> >beta = min(beta, best);> >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> }> // Driver Code> int> main()> {> >int> values[8] = { 3, 5, 6, 9, 1, 2, 0, -1 };> >cout <<>'The optimal value is : '><< minimax(0, 0,>true>, values, MIN, MAX);;> >return> 0;> }> 

>

>

Java




// Java program to demonstrate> // working of Alpha-Beta Pruning> import> java.io.*;> class> GFG {> // Initial values of> // Alpha and Beta> static> int> MAX =>1000>;> static> int> MIN = ->1000>;> // Returns optimal value for> // current player (Initially called> // for root and maximizer)> static> int> minimax(>int> depth,>int> nodeIndex,> >Boolean maximizingPlayer,> >int> values[],>int> alpha,> >int> beta)> {> >// Terminating condition. i.e> >// leaf node is reached> >if> (depth ==>3>)> >return> values[nodeIndex];> >if> (maximizingPlayer)> >{> >int> best = MIN;> >// Recur for left and> >// right children> >for> (>int> i =>0>; i <>2>; i++)> >{> >int> val = minimax(depth +>1>, nodeIndex *>2> + i,> >false>, values, alpha, beta);> >best = Math.max(best, val);> >alpha = Math.max(alpha, best);> >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> >else> >{> >int> best = MAX;> >// Recur for left and> >// right children> >for> (>int> i =>0>; i <>2>; i++)> >{> > >int> val = minimax(depth +>1>, nodeIndex *>2> + i,> >true>, values, alpha, beta);> >best = Math.min(best, val);> >beta = Math.min(beta, best);> >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> }> >// Driver Code> >public> static> void> main (String[] args)> >{> > >int> values[] = {>3>,>5>,>6>,>9>,>1>,>2>,>0>, ->1>};> >System.out.println(>'The optimal value is : '> +> >minimax(>0>,>0>,>true>, values, MIN, MAX));> > >}> }> // This code is contributed by vt_m.> 

>

>

Machen Sie eine While-Schleife in Java

Python3




# Python3 program to demonstrate> # working of Alpha-Beta Pruning> # Initial values of Alpha and Beta> MAX>,>MIN> => 1000>,>->1000> # Returns optimal value for current player> #(Initially called for root and maximizer)> def> minimax(depth, nodeIndex, maximizingPlayer,> >values, alpha, beta):> > ># Terminating condition. i.e> ># leaf node is reached> >if> depth>=>=> 3>:> >return> values[nodeIndex]> >if> maximizingPlayer:> > >best>=> MIN> ># Recur for left and right children> >for> i>in> range>(>0>,>2>):> > >val>=> minimax(depth>+> 1>, nodeIndex>*> 2> +> i,> >False>, values, alpha, beta)> >best>=> max>(best, val)> >alpha>=> max>(alpha, best)> ># Alpha Beta Pruning> >if> beta <>=> alpha:> >break> > >return> best> > >else>:> >best>=> MAX> ># Recur for left and> ># right children> >for> i>in> range>(>0>,>2>):> > >val>=> minimax(depth>+> 1>, nodeIndex>*> 2> +> i,> >True>, values, alpha, beta)> >best>=> min>(best, val)> >beta>=> min>(beta, best)> ># Alpha Beta Pruning> >if> beta <>=> alpha:> >break> > >return> best> > # Driver Code> if> __name__>=>=> '__main__'>:> > >values>=> [>3>,>5>,>6>,>9>,>1>,>2>,>0>,>->1>]> >print>(>'The optimal value is :'>, minimax(>0>,>0>,>True>, values,>MIN>,>MAX>))> > # This code is contributed by Rituraj Jain> 

>

>

C#

Java-Regex $




// C# program to demonstrate> // working of Alpha-Beta Pruning> using> System;> > class> GFG> {> // Initial values of> // Alpha and Beta> static> int> MAX = 1000;> static> int> MIN = -1000;> // Returns optimal value for> // current player (Initially called> // for root and maximizer)> static> int> minimax(>int> depth,>int> nodeIndex,> >Boolean maximizingPlayer,> >int> []values,>int> alpha,> >int> beta)> {> >// Terminating condition. i.e> >// leaf node is reached> >if> (depth == 3)> >return> values[nodeIndex];> >if> (maximizingPlayer)> >{> >int> best = MIN;> >// Recur for left and> >// right children> >for> (>int> i = 0; i <2; i++)> >{> >int> val = minimax(depth + 1, nodeIndex * 2 + i,> >false>, values, alpha, beta);> >best = Math.Max(best, val);> >alpha = Math.Max(alpha, best);> >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> >else> >{> >int> best = MAX;> >// Recur for left and> >// right children> >for> (>int> i = 0; i <2; i++)> >{> > >int> val = minimax(depth + 1, nodeIndex * 2 + i,> >true>, values, alpha, beta);> >best = Math.Min(best, val);> >beta = Math.Min(beta, best);> >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> }> // Driver Code> public> static> void> Main (String[] args)> {> > >int> []values = {3, 5, 6, 9, 1, 2, 0, -1};> >Console.WriteLine(>'The optimal value is : '> +> >minimax(0, 0,>true>, values, MIN, MAX));> }> }> // This code is contributed by 29AjayKumar> 

>

Java-Listenknoten 

>

Javascript




> // Javascript program to demonstrate> // working of Alpha-Beta Pruning> // Initial values of> // Alpha and Beta> let MAX = 1000;> let MIN = -1000;> // Returns optimal value for> // current player (Initially called> // for root and maximizer)> function> minimax(depth,nodeIndex,maximizingPlayer,values,alpha,beta)> {> >// Terminating condition. i.e> >// leaf node is reached> >if> (depth == 3)> >return> values[nodeIndex];> > >if> (maximizingPlayer)> >{> >let best = MIN;> > >// Recur for left and> >// right children> >for> (let i = 0; i <2; i++)> >{> >let val = minimax(depth + 1, nodeIndex * 2 + i,> >false>, values, alpha, beta);> >best = Math.max(best, val);> >alpha = Math.max(alpha, best);> > >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> >else> >{> >let best = MAX;> > >// Recur for left and> >// right children> >for> (let i = 0; i <2; i++)> >{> > >let val = minimax(depth + 1, nodeIndex * 2 + i,> >true>, values, alpha, beta);> >best = Math.min(best, val);> >beta = Math.min(beta, best);> > >// Alpha Beta Pruning> >if> (beta <= alpha)> >break>;> >}> >return> best;> >}> }> // Driver Code> let values=[3, 5, 6, 9, 1, 2, 0, -1];> document.write(>'The optimal value is : '> +> >minimax(0, 0,>true>, values, MIN, MAX));> // This code is contributed by rag2127> > 

>

>

Ausgabe 

The optimal value is : 5>