Förutsättningar: Minimax-algoritm i spelteori , Utvärderingsfunktion i spelteori
Alpha-Beta-beskärning är egentligen inte en ny algoritm, utan snarare en optimeringsteknik för minimaxalgoritmen. Det minskar beräkningstiden med en enorm faktor. Detta gör att vi kan söka mycket snabbare och till och med gå in på djupare nivåer i spelträdet. Den skär av grenar i spelträdet som inte behöver sökas eftersom det redan finns ett bättre drag tillgängligt. Det kallas för Alpha-Beta-beskärning eftersom det passerar 2 extra parametrar i minimaxfunktionen, nämligen alfa och beta.
Låt oss definiera parametrarna alfa och beta.
Alfa är det bästa värdet som maximerare för närvarande kan garantera på den nivån eller högre.
Beta är det bästa värdet som minimerare för närvarande kan garantera på den nivån eller lägre.
Pseudokod:
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)>
Låt oss göra ovanstående algoritm tydlig med ett exempel.
- Det första samtalet börjar kl A . Värdet av alfa här är -OÄNDLIGHET och värdet av beta är +ÄNDLIGHET . Dessa värden överförs till efterföljande noder i trädet. På A maximeraren måste välja max av B och C , alltså A samtal B först
- På B det måste minimeraren välja min av D och OCH och därav samtal D först.
- På D , den tittar på sitt vänstra barn som är en lövnod. Denna nod returnerar värdet 3. Nu värdet av alfa vid D är max( -INF, 3) vilket är 3.
- För att avgöra om det är värt att titta på dess högra nod eller inte, kontrollerar den villkoret beta<=alpha. Detta är falskt eftersom beta = +INF och alfa = 3. Så det fortsätter sökningen. D tittar nu på sitt högra barn som returnerar värdet 5.At D , alpha = max(3, 5) vilket är 5. Nu är nodens värde D är 5 D returnerar värdet 5 till B . På B , beta = min( +INF, 5) vilket är 5. Minimeraren är nu garanterad ett värde på 5 eller lägre. B ringer nu OCH för att se om han kan få ett lägre värde än 5.
- På OCH värdena för alfa och beta är inte -INF och +INF utan istället -INF respektive 5, eftersom betavärdet ändrades vid B och det är vad B gått i arv till OCH
- Nu OCH tittar på sitt vänstra barn som är 6. Kl OCH , alpha = max(-INF, 6) vilket är 6. Här blir villkoret sant. beta är 5 och alfa är 6. Så beta<=alfa är sant. Därför går det sönder och OCH returnerar 6 till B
- Notera hur det inte spelade någon roll vad värdet på OCH rätt barn är. Det kunde ha varit +INF eller -INF, det skulle fortfarande inte spela någon roll, vi behövde aldrig ens titta på det eftersom minimeraren garanterades ett värde på 5 eller lägre. Så fort maximeraren såg 6an visste han att minimizern aldrig skulle komma så här eftersom han kan få en 5:a på vänster sida av B . På så sätt behövde vi inte titta på den 9:an och sparade därför beräkningstid. E returnerar värdet 6 till B . På B , beta = min( 5, 6) vilket är 5. Värdet på noden B är också 5
Hittills är det så här vårt spelträd ser ut. 9:an är överstruken eftersom den aldrig beräknades.
- B returnerar 5 till A . På A , alpha = max( -INF, 5) vilket är 5. Nu är maximeraren garanterat ett värde på 5 eller högre. A ringer nu C för att se om det kan få ett högre värde än 5.
- På C , alfa = 5 och beta = +INF. C samtal F
- På F , alfa = 5 och beta = +INF. F tittar på sitt vänstra barn som är en 1. alpha = max( 5, 1) som fortfarande är 5. F tittar på sitt högra barn som är en 2. Därför är det bästa värdet på denna nod 2. Alfa förblir fortfarande 5 F returnerar ett värde på 2 till C . På C , beta = min( +INF, 2). Villkoret beta <= alfa blir sant som beta = 2 och alfa = 5. Så det går sönder och det behöver inte ens beräkna hela underträdet av G .
- Intuitionen bakom detta avbrott är att kl C minimeraren garanterades ett värde på 2 eller lägre. Men maximisören var redan garanterad ett värde på 5 om han ville B . Så varför skulle maximeraren någonsin välja C och få ett värde mindre än 2 ? Återigen kan du se att det inte spelade någon roll vilka de två sista värdena var. Vi sparade också en hel del beräkningar genom att hoppa över ett helt underträd. C returnerar nu värdet 2 till A . Därför det bästa värdet på A är max( 5, 2) vilket är en 5.
- Därför är det optimala värdet som maximeraren kan få 5
Så här ser vårt sista spelträd ut. Som du kan se G har stryks över eftersom det aldrig beräknades.
sortera en arraylist i java
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;> }> |
vad är ett linux filsystem
>
>
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.> |
>
>
Python3
java listning
# 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> |
>
>
typskriptuppsättning
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
gimp ersätter färg
> // 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> > |
>
>Produktion
The optimal value is : 5>