Vereisten: Minimax-algoritme in speltheorie , Evaluatiefunctie in speltheorie
Alpha-Beta-snoeien is eigenlijk geen nieuw algoritme, maar eerder een optimalisatietechniek voor het minimax-algoritme. Het vermindert de rekentijd met een enorme factor. Hierdoor kunnen we veel sneller zoeken en zelfs diepere niveaus in de spelboom ingaan. Het snijdt takken in de spelboom af die niet hoeven te worden doorzocht omdat er al een betere zet beschikbaar is. Het wordt Alpha-Beta-snoeien genoemd omdat het 2 extra parameters doorgeeft in de minimax-functie, namelijk alfa en bèta.
0,2 als breuk
Laten we de parameters alfa en bèta definiëren.
Alfa is de beste waarde die de maximalisatie momenteel op dat niveau of hoger kunnen garanderen.
Bèta is de beste waarde die de minimaliseren momenteel op dat niveau of lager kan garanderen.
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)>
Laten we het bovenstaande algoritme duidelijk maken met een voorbeeld.
- Het eerste gesprek begint vanaf A . De waarde van alpha is hier -ONEINDIGHEID en de waarde van bèta is + ONEINDIGHEID . Deze waarden worden doorgegeven aan volgende knooppunten in de boom. Bij A de maximalisator moet max. van kiezen B En C , Dus A oproepen B Eerst
- Bij B Hier moet de minimalisator min van kiezen D En EN en dus gebeld D Eerst.
- Bij D , kijkt het naar zijn linkerkind, dat een bladknooppunt is. Dit knooppunt retourneert een waarde van 3. Nu de waarde van alpha op D is max( -INF, 3), wat 3 is.
- Om te beslissen of het de moeite waard is om naar het juiste knooppunt te kijken of niet, controleert het de voorwaarde beta<=alpha. Dit is niet waar, omdat bèta = +INF en alpha = 3. Het zoeken wordt dus voortgezet. D kijkt nu naar zijn rechterkind, dat een waarde van 5.At retourneert D , alpha = max(3, 5) wat 5 is. Nu de waarde van knooppunt D is 5 D retourneert een waarde van 5 tot B . Bij B , beta = min( +INF, 5) wat 5 is. De minimalizer heeft nu gegarandeerd een waarde van 5 of minder. B belt nu EN om te zien of hij een lagere waarde dan 5 kan krijgen.
- Bij EN de waarden van alfa en bèta zijn niet respectievelijk -INF en +INF maar in plaats daarvan -INF en 5, omdat de waarde van bèta is gewijzigd op B en dat is wat B doorgegeven aan EN
- Nu EN kijkt naar zijn linkerkind, dat is 6. At EN , alpha = max(-INF, 6), wat 6 is. Hier wordt de voorwaarde waar. bèta is 5 en alfa is 6. Dus bèta<=alfa is waar. Daarom breekt het en EN retourneert 6 naar B
- Merk op dat het niet uitmaakte wat de waarde ervan was EN 's rechter kind is. Het had +INF of -INF kunnen zijn, het zou er nog steeds niet toe doen. We hoefden er niet eens naar te kijken omdat de minimalisatie gegarandeerd een waarde van 5 of minder had. Dus zodra de maximalisator de 6 zag, wist hij dat de minimalisator nooit deze kant op zou komen, omdat hij een 5 kan krijgen aan de linkerkant van B . Op deze manier hoefden we niet naar die 9 te kijken en bespaarden we dus rekentijd. E retourneert een waarde van 6 naar B . Bij B , beta = min( 5, 6), wat 5 is. De waarde van het knooppunt B is ook 5
Tot nu toe ziet onze spelboom er zo uit. De 9 is doorgestreept omdat deze nooit is berekend.
- B retourneert 5 naar A . Bij A , alpha = max( -INF, 5) wat 5 is. Nu krijgt de maximalisatie gegarandeerd een waarde van 5 of hoger. A belt nu C om te zien of het een hogere waarde dan 5 kan krijgen.
- Bij C , alfa = 5 en bèta = +INF. C oproepen F
- Bij F , alfa = 5 en bèta = +INF. F kijkt naar het linkerkind, dat een 1 is. alpha = max( 5, 1), wat nog steeds 5 is. F kijkt naar zijn rechterkind, dat een 2 is. Daarom is de beste waarde van dit knooppunt 2. Alfa blijft nog steeds 5 F retourneert een waarde van 2 naar C . Bij C , bèta = min( +INF, 2). De voorwaarde bèta <= alfa wordt waar als bèta = 2 en alfa = 5. Deze vervalt dus en hoeft niet eens de hele subboom van te berekenen G .
- De intuïtie achter deze breuk is dat, op C de minimalisator kreeg gegarandeerd een waarde van 2 of minder. Maar de maximizer kreeg al een gegarandeerde waarde van 5 als hij daarvoor koos B . Dus waarom zou de maximiser ooit kiezen? C en een waarde kleiner dan 2 krijgen? Opnieuw zie je dat het niet uitmaakte wat die laatste 2 waarden waren. We hebben ook veel rekenwerk bespaard door een hele subboom over te slaan. C retourneert nu een waarde van 2 naar A . Daarom de beste waarde bij A is max( 5, 2), wat een 5 is.
- Daarom is de optimale waarde die de maximizer kan krijgen 5
Zo ziet onze uiteindelijke spelboom eruit. Zoals je kan zien G is doorgestreept omdat deze nooit is berekend.
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
pvr volledige vorm
// 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
hashset-java
# 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> |
>
afrekenen in git
>
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> > |
>
>Uitvoer
git rebase
The optimal value is : 5>