Forutsetninger: Minimax-algoritme i spillteori , Evalueringsfunksjon i spillteori
Alpha-Beta-beskjæring er egentlig ikke en ny algoritme, men snarere en optimaliseringsteknikk for minimaksalgoritmen. Det reduserer beregningstiden med en enorm faktor. Dette lar oss søke mye raskere og til og med gå inn på dypere nivåer i spilltreet. Den kutter av grener i vilttreet som ikke trenger å søkes i fordi det allerede finnes et bedre trekk tilgjengelig. Det kalles Alpha-Beta pruning fordi det passerer 2 ekstra parametere i minimax-funksjonen, nemlig alfa og beta.
La oss definere parametrene alfa og beta.
Alfa er den beste verdien som maksimerer for øyeblikket kan garantere på det nivået eller høyere.
Beta er den beste verdien som minimer for øyeblikket kan garantere på det nivået eller under.
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)>
La oss gjøre algoritmen ovenfor tydelig med et eksempel.
- Den første samtalen starter kl EN . Verdien av alfa her er -EVIGHET og verdien av beta er +INFINITY . Disse verdiene overføres til påfølgende noder i treet. På EN maksimereren må velge maks av B og C , så EN samtaler B først
- På B det må minimeren velge min av D og OG og dermed samtaler D først.
- På D , ser den på det venstre barnet som er en bladnode. Denne noden returnerer en verdi på 3. Nå verdien av alfa at D er maks( -INF, 3) som er 3.
- For å avgjøre om det er verdt å se på dens høyre node eller ikke, sjekker den tilstanden beta<=alpha. Dette er usant siden beta = +INF og alfa = 3. Så det fortsetter søket. D ser nå på det høyre barnet som returnerer en verdi på 5.At D , alpha = max(3, 5) som er 5. Nå verdien av node D er 5 D returnerer en verdi på 5 til B . På B , beta = min( +INF, 5) som er 5. Minimereren er nå garantert en verdi på 5 eller mindre. B ringer nå OG for å se om han kan få en lavere verdi enn 5.
- På OG verdiene til alfa og beta er ikke -INF og +INF, men i stedet -INF og henholdsvis 5, fordi verdien av beta ble endret kl. B og det er det B gått ned til OG
- Nå OG ser på det venstre barnet som er 6. Kl OG , alpha = max(-INF, 6) som er 6. Her blir betingelsen sann. beta er 5 og alfa er 6. Så beta<=alfa er sant. Derfor går den i stykker og OG returnerer 6 til B
- Legg merke til hvordan det ikke spilte noen rolle hva verdien av OG sitt rette barn er. Det kunne ha vært +INF eller -INF, det ville fortsatt ikke ha noe å si, vi måtte aldri se på det fordi minimeren var garantert en verdi på 5 eller mindre. Så snart maksimereren så 6-eren, visste han at minimiseringen aldri ville komme på denne måten fordi han kan få en 5-er på venstre side av B . På denne måten trengte vi ikke å se på den 9 og sparte dermed beregningstid. E returnerer en verdi på 6 til B . På B , beta = min( 5, 6) som er 5. Verdien av node B er også 5
Så langt er dette hvordan spilltreet vårt ser ut. 9-tallet er krysset ut fordi det aldri ble beregnet.
- B returnerer 5 til EN . På EN , alpha = max( -INF, 5) som er 5. Nå er maksimeringsverdien garantert en verdi på 5 eller høyere. EN ringer nå C for å se om den kan få en høyere verdi enn 5.
- På C , alfa = 5 og beta = +INF. C samtaler F
- På F , alfa = 5 og beta = +INF. F ser på det venstre barnet som er en 1. alpha = max( 5, 1) som fortsatt er 5. F ser på det høyre barnet som er en 2. Derfor er den beste verdien av denne noden 2. Alfa forblir fortsatt 5 F returnerer en verdi på 2 til C . På C , beta = min( +INF, 2). Betingelsen beta <= alpha blir sann som beta = 2 og alfa = 5. Så den bryter og den trenger ikke engang å beregne hele undertreet til G .
- Intuisjonen bak dette bruddet er at kl C minimeren var garantert en verdi på 2 eller mindre. Men maksimeren var allerede garantert en verdi på 5 hvis han ville B . Så hvorfor skulle maksimeren noen gang velge C og få en verdi mindre enn 2 ? Igjen kan du se at det ikke spilte noen rolle hva de siste 2 verdiene var. Vi sparte også mye beregning ved å hoppe over et helt undertre. C returnerer nå en verdi på 2 til EN . Derfor den beste verdien på EN er max( 5, 2) som er en 5.
- Derfor er den optimale verdien som maksimering kan få 5
Slik ser vårt siste spilltre ut. Som du kan se G er krysset ut da den aldri ble beregnet.
CPP
gjø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.> |
>
sortert tuppelpyton
>
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
>
>Produksjon
The optimal value is : 5>