Requisitos previos: Algoritmo Minimax en teoría de juegos , Función de evaluación en teoría de juegos.
La poda Alfa-Beta no es en realidad un algoritmo nuevo, sino más bien una técnica de optimización para el algoritmo minimax. Reduce el tiempo de cálculo en un factor enorme. Esto nos permite buscar mucho más rápido e incluso adentrarnos en niveles más profundos en el árbol del juego. Corta ramas en el árbol del juego que no es necesario buscar porque ya existe un movimiento mejor disponible. Se llama poda Alfa-Beta porque pasa 2 parámetros adicionales en la función minimax, a saber, alfa y beta.
Definamos los parámetros alfa y beta.
Alfa es el mejor valor que el maximizador actualmente podemos garantizar a ese nivel o superior.
Beta es el mejor valor que el minimizador Actualmente podemos garantizar a ese nivel o menos.
Pseudocódigo:
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)>
Aclaremos el algoritmo anterior con un ejemplo.
- La llamada inicial comienza desde A . El valor de alfa aquí es -INFINIDAD y el valor de beta es +INFINITO . Estos valores se transmiten a los nodos posteriores del árbol. En A el maximizador debe elegir max de B y C , entonces A llamadas B primero
- En B el minimizador debe elegir min de D y Y y por eso llama D primero.
- En D , mira a su hijo izquierdo, que es un nodo hoja. Este nodo devuelve un valor de 3. Ahora el valor de alfa en D es max(-INF, 3) que es 3.
- Para decidir si vale la pena mirar su nodo derecho o no, verifica la condición beta<=alfa. Esto es falso ya que beta = +INF y alfa = 3. Entonces continúa la búsqueda. D ahora mira a su hijo derecho que devuelve un valor de 5. D , alfa = max(3, 5) que es 5. Ahora el valor del nodo D es 5 D devuelve un valor de 5 a B . En B , beta = min( +INF, 5) que es 5. Ahora se garantiza al minimizador un valor de 5 o menos. B ahora llama Y para ver si puede obtener un valor inferior a 5.
- En Y los valores de alfa y beta no son -INF y +INF sino -INF y 5 respectivamente, porque el valor de beta se cambió en B y eso es lo que B transmitido a Y
- Ahora Y mira a su hijo izquierdo que tiene 6 años. Y , alfa = max(-INF, 6) que es 6. Aquí la condición se vuelve verdadera. beta es 5 y alfa es 6. Entonces beta<=alfa es verdadero. Por eso se rompe y Y devuelve 6 a B
- Observe cómo no importaba cuál era el valor de Y El hijo correcto es. Podría haber sido +INF o -INF, aún así no importaría. Ni siquiera tuvimos que mirarlo porque al minimizador se le garantizaba un valor de 5 o menos. Entonces, tan pronto como el maximizador vio el 6, supo que el minimizador nunca vendría de esta manera porque puede obtener un 5 en el lado izquierdo de B . De esta manera no tuvimos que mirar ese 9 y, por lo tanto, ahorramos tiempo de cálculo. E devuelve un valor de 6 a B . En B , beta = min( 5, 6) que es 5. El valor del nodo B también es 5
Hasta ahora así es como se ve nuestro árbol de juegos. El 9 está tachado porque nunca fue computado.
- B devuelve 5 a A . En A , alfa = max( -INF, 5) que es 5. Ahora el maximizador tiene garantizado un valor de 5 o mayor. A ahora llama C para ver si puede obtener un valor superior a 5.
- En C , alfa = 5 y beta = +INF. C llamadas F
- En F , alfa = 5 y beta = +INF. F mira a su hijo izquierdo que es 1. alpha = max( 5, 1) que sigue siendo 5. F mira a su hijo derecho, que es un 2. Por lo tanto, el mejor valor de este nodo es 2. Alfa sigue siendo 5. F devuelve un valor de 2 a C . En C , beta = mín( +INF, 2). La condición beta <= alfa se vuelve verdadera cuando beta = 2 y alfa = 5. Entonces se rompe y ni siquiera tiene que calcular el subárbol completo de GRAMO .
- La intuición detrás de esta ruptura es que, al menos C al minimizador se le garantizaba un valor de 2 o menos. Pero el maximizador ya tenía garantizado un valor de 5 si elegía B . Entonces, ¿por qué el maximizador alguna vez elegiría C y obtener un valor menor que 2? Nuevamente puedes ver que no importaba cuáles fueran esos 2 últimos valores. También ahorramos muchos cálculos al omitir un subárbol completo. C ahora devuelve un valor de 2 a A . Por lo tanto, el mejor valor en A es max(5, 2) que es un 5.
- Por tanto el valor óptimo que puede obtener el maximizador es 5
Así es como luce nuestro árbol de juego final. Como se puede ver GRAMO ha sido tachado porque nunca fue calculado.
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.> |
ejemplos de modelos e r
>
>
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> > |
>
>Producción
The optimal value is : 5>