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.

• 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.

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.

CPP

Java

Python 3

C#

Javascript

The optimal value is : 5