Forudsætninger: Minimax-algoritme i spilteori , Evalueringsfunktion i spilteori
Alpha-Beta beskæring er faktisk ikke en ny algoritme, men derimod en optimeringsteknik for minimax-algoritmen. Det reducerer beregningstiden med en enorm faktor. Dette giver os mulighed for at søge meget hurtigere og endda gå ind på dybere niveauer i spiltræet. Den skærer grene af i spiltræet, som ikke skal søges i, fordi der allerede findes et bedre træk. Det kaldes Alpha-Beta-beskæring, fordi det passerer 2 ekstra parametre i minimax-funktionen, nemlig alfa og beta.
Lad os definere parametrene alfa og beta.
Alfa er den bedste værdi, som maksimerer i øjeblikket kan garantere på det niveau eller derover.
Beta er den bedste værdi, som minimer i øjeblikket kan garantere på det niveau eller derunder.
Pseudokode:
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)>
Lad os gøre ovenstående algoritme klar med et eksempel.
- Det indledende opkald starter kl EN . Værdien af alfa her er -UENDELIGHED og værdien af beta er +INFINITY . Disse værdier overføres til efterfølgende noder i træet. På EN maximizeren skal vælge max af B og C , så EN opkald B først
- På B det skal minimizeren vælge min af D og OG og derfor opkald D først.
- På D , den ser på sit venstre barn, som er en bladknude. Denne node returnerer en værdi på 3. Nu værdien af alfa ved D er max( -INF, 3), hvilket er 3.
- For at afgøre, om det er værd at se på dens højre knude eller ej, tjekker den betingelsen beta<=alpha. Dette er falsk, da beta = +INF og alfa = 3. Så den fortsætter søgningen. D ser nu på dets højre underordnede, som returnerer en værdi på 5.At D , alpha = max(3, 5) som er 5. Nu værdien af node D er 5 D returnerer en værdi på 5 til B . På B , beta = min( +INF, 5) som er 5. Minimeren er nu garanteret en værdi på 5 eller mindre. B ringer nu OG for at se, om han kan få en lavere værdi end 5.
- På OG værdierne af alfa og beta er ikke -INF og +INF, men i stedet for henholdsvis -INF og 5, fordi værdien af beta blev ændret kl. B og det er hvad B gået i arv til OG
- Nu OG ser på sit venstre barn som er 6. Kl OG , alpha = max(-INF, 6) som er 6. Her bliver betingelsen sand. beta er 5 og alfa er 6. Så beta<=alfa er sandt. Derfor går den i stykker og OG returnerer 6 til B
- Bemærk, hvordan det var ligegyldigt, hvad værdien af OG ’s rette barn er. Det kunne have været +INF eller -INF, det ville stadig være ligegyldigt. Vi behøvede aldrig engang at se på det, fordi minimizeren var garanteret en værdi på 5 eller mindre. Så så snart maximizeren så 6'eren vidste han, at minimizeren aldrig ville komme på denne måde, fordi han kan få en 5'er i venstre side af B . På denne måde behøvede vi ikke at se på den 9 og sparede derfor beregningstid. E returnerer en værdi på 6 til B . På B , beta = min( 5, 6) som er 5. Værdien af node B er også 5
Indtil videre er det sådan vores spiltræ ser ud. 9 er streget over, fordi det aldrig er blevet beregnet.
- B returnerer 5 til EN . På EN , alpha = max( -INF, 5) som er 5. Nu er maksimeringsværktøjet garanteret en værdi på 5 eller større. EN ringer nu C for at se, om den kan få en højere værdi end 5.
- På C , alfa = 5 og beta = +INF. C opkald F
- På F , alfa = 5 og beta = +INF. F ser på dets venstre barn, som er en 1. alpha = max( 5, 1), som stadig er 5. F ser på dets højre underordnede, som er en 2. Derfor er den bedste værdi af denne node 2. Alfa forbliver stadig 5 F returnerer en værdi på 2 til C . På C , beta = min( +INF, 2). Betingelsen beta <= alpha bliver sand, da beta = 2 og alfa = 5. Så den går i stykker, og den behøver ikke engang at beregne hele undertræet af G .
- Intuitionen bag dette break-off er, at kl C minimeren var garanteret en værdi på 2 eller mindre. Men maksimeren var allerede garanteret en værdi på 5, hvis han valgte B . Så hvorfor skulle maksimeren nogensinde vælge C og få en værdi mindre end 2 ? Igen kan du se, at det var lige meget, hvad de sidste 2 værdier var. Vi sparede også en masse beregninger ved at springe et helt undertræ over. C returnerer nu en værdi på 2 til EN . Derfor den bedste værdi til EN er max( 5, 2), hvilket er en 5.
- Derfor er den optimale værdi, som maksimeringen kan få, 5
Sådan ser vores sidste spiltræ ud. Som du kan se G er streget over, da det aldrig er blevet beregnet.
CPP
gør mens loop java
// 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.> |
>
sorteret tuple python
>
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#
// 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> |
>
>
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> > |
generiske java
>
>Produktion
The optimal value is : 5>