logo

TechCodeview

Algoritme Minimax en teoria de jocs | Set 4 (poda alfa-beta)

Requisits previs: Algorisme Minimax en teoria de jocs , Funció d'avaluació en teoria de jocs
La poda alfa-beta no és en realitat un algorisme nou, sinó una tècnica d'optimització per a l'algoritme minimax. Redueix el temps de càlcul en un factor enorme. Això ens permet cercar molt més ràpidament i fins i tot entrar a nivells més profunds de l'arbre del joc. Talla les branques de l'arbre del joc que no cal cercar perquè ja hi ha un millor moviment disponible. S'anomena poda Alpha-Beta perquè passa 2 paràmetres addicionals a la funció minimax, és a dir, alfa i beta.

Definim els paràmetres alfa i beta.

Alfa és el millor valor que el maximitzador actualment es pot garantir a aquest nivell o superior.
Beta és el millor valor que el minimitzador actualment es pot garantir en aquest nivell o per sota.



Pseudocodi:

 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)>

Deixem clar l'algorisme anterior amb un exemple.

Poda Alfa Beta

  • La trucada inicial comença des A . El valor d'alfa aquí és -INFINIT i el valor de beta és +INFINIT . Aquests valors es transmeten als nodes posteriors de l'arbre. A les A el maximitzador ha de triar un màxim de B i C , tan A trucades B primer
  • A les B el minimitzador ha de triar min de D i I i per tant les trucades D primer.
  • A les D , mira el seu fill esquerre que és un node fulla. Aquest node retorna un valor de 3. Ara el valor d'alfa a D és màxim (-INF, 3), que és 3.
  • Per decidir si val la pena mirar el seu node dret o no, verifica la condició beta<=alpha. Això és fals ja que beta = +INF i alfa = 3. Així que continua la cerca.
    • D ara mira el seu fill dret que retorna un valor de 5.At D , alfa = max(3, 5) que és 5. Ara el valor de node D és 5 D retorna un valor de 5 a B . A les B , beta = min( +INF, 5) que és 5. Ara el minimitzador té garantit un valor de 5 o menys. B ara truca I per veure si pot obtenir un valor inferior a 5.
  • A les I els valors d'alfa i beta no són -INF i +INF sinó -INF i 5 respectivament, perquè el valor de beta es va canviar a B i això és el que B transmès a I
  • Ara I mira el seu fill esquerre que fa 6. At I , alfa = max(-INF, 6) que és 6. Aquí la condició esdevé certa. beta és 5 i alfa és 6. Per tant, beta<=alfa és cert. Per tant es trenca i I torna 6 a B
  • Tingueu en compte com no importava quin sigui el valor I el fill correcte és. Podria haver estat +INF o -INF, encara no importaria, ni tan sols ho havíem de mirar perquè el minimitzador tenia garantit un valor de 5 o menys. Així, tan aviat com el maximitzador va veure el 6, va saber que el minimitzador mai no arribaria d'aquesta manera perquè pot obtenir un 5 al costat esquerre de B . D'aquesta manera no vam haver de mirar aquest 9 i, per tant, vam estalviar temps de càlcul.
    • E retorna un valor de 6 a B . A les B , beta = min( 5, 6) que és 5. El valor del node B també és 5

Fins ara, així es veu el nostre arbre de jocs. El 9 està ratllat perquè mai es va calcular.

Poda Alpha Beta 2

    B torna 5 a A . A les A , alfa = max( -INF, 5) que és 5. Ara el maximitzador té garantit un valor de 5 o més. A ara truca C per veure si pot obtenir un valor superior a 5.
  • A les C , alfa = 5 i beta = +INF. C trucades F
  • A les F , alfa = 5 i beta = +INF. F mira el seu fill esquerre que és un 1. alfa = max( 5, 1) que encara és 5.
    • F mira el seu fill dret, que és un 2. Per tant, el millor valor d'aquest node és 2. Alfa segueix sent 5 F retorna un valor de 2 a C . A les C , beta = min(+INF, 2). La condició beta <= alfa esdevé certa com a beta = 2 i alfa = 5. Així que es trenca i ni tan sols ha de calcular tot el subarbre de G .
  • La intuïció darrere d'aquesta ruptura és que, a C el minimitzador es va garantir un valor de 2 o menys. Però el maximitzador ja tenia garantit un valor de 5 si ho volia B . Aleshores, per què escolliria el maximitzador C i obtenir un valor inferior a 2 ? Una vegada més, podeu veure que no importava quins eren aquests dos últims valors. També hem estalviat molts càlculs saltant un subarbre sencer.
    • C ara retorna un valor de 2 a A . Per tant, el millor valor a A és màxim (5, 2), que és un 5.
  • Per tant, el valor òptim que pot obtenir el maximitzador és 5

Així és el nostre arbre de joc final. Com pots veure G s'ha ratllat perquè mai s'ha calculat.

Poda Alpha Beta 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.> 

>

>

Python 3




# 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


string.valueof



> // 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> > 

>

>

Sortida 

The optimal value is : 5>