Poda alfa-beta de la búsqueda Minimax

Poda alfa-beta de la búsqueda Minimax

Los procedimientos de búsqueda en profundidad (DFS) pueden mejorar su eficiencia usando una técnica de branch and bound (ramificación y acotación), con la cual una solución parcial se abandona cuando se comprueba que es peor que otra solución conocida o umbral.

La estrategia de poda del algoritmo Minimax es llamada poda alfa-beta, puesto que dado que existen dos jugadores maximizador y minimizador, existen dos valores umbral alfa y beta para acotar la búsqueda de cada uno respectivamente.


El valor alfa representa la cota inferior del valor que puede asignarse en último término a un nodo maximizante.
El valor beta representa la cota superior del valor que puede asignarse en último término a un nodo minimizante.

La figura 2 muestra la aplicación de la poda alfa-beta al ejemplo de la figura 1. La evaluación del nodo E asegura al oponente (jugador minimizante) una cota superior con valor 7, es decir, el oponente obtendrá 7 o un valor menor en la evaluación de B (dado que los valores están en relación al jugador maximizante, los valores menores a 7 son mejores para el oponente). En este caso, 7 representa el valor beta. A continuación, cuando se examina el nodo N cuyo valor es 8, dado que es mayor que beta (7), los nodos hermanos de N (en este caso el nodo O) pueden podarse (dado que nos hallamos en un nivel maximizante, el nodo F tendrá un valor igual o superior a 8, y por lo tanto no podrá competir con la cota asegurada beta en el nivel minimizante anterior).

Luego de evaluar los sucesores de B, se concluye que este nodo asegura al jugador maximizante una cota inferior con valor 3, es decir, obtendrá 3 o un valor mayor en la evaluación de A. En este caso, 3 representa el valor de alfa. A continuación, cuando se examina el nodo H cuyo valor es 0, dado que es menor que alfa (3), los nodos hermanos de H (en este caso el nodo I) pueden podarse (dado que nos hallamos en un nivel minimizante, el nodo C tendrá un valor menor o igual a 0, y por lo tanto no podrá competir con la cota asegurada alfa en el nivel maximizante anterior).
FIGURA 2

En un nivel dado, el valor de umbral alfa o beta según corresponda, debe actualizarse cuando se encuentra un umbral mejor. En el ejemplo anterior, al obtenerse el valor 8 del nodo D se puede actualizar el valor de alfa (3) a alfa (8). Esto tendría sentido en el caso de que existieran otros nodos hermanos de D que pudieran ser podados utilizando este valor de alfa. Análogamente, al obtenerse un valor de 3 en el nodo G se puede actualizar el valor de beta (7) a beta (3). Esto tendría sentido en el caso de que existieran otros nodos hermanos G que pudieran ser podados utilizando este valor de beta.

El algoritmo MINIMAX_ALFABETA evita esta diferenciación utilizando dos valores de umbral, uno que usa efectivamente como umbral (umbralUSO) y otro que debe pasar al nivel siguiente para ser usado (umbralPASO). En un nivel dado, uno de los valores es usado para realizar posibles podas de nodos hijos (umbralUSO), y mientras tanto se va actualizando el valor de umbral del nivel anterior (umbralPASO).

La primera llamada a la función recursiva será:

MINIMAX_ALFABETA (posiciónactual, 0, JUGADOR-UNO, MAXINT, MININT)

El algoritmo MINIMAX con poda ALFABETA es el siguiente:

MINIMAX_ALFABETA( posición, profundidad, jugador, umbralUSO, umbralPASO)
comienzo

Si SUFICIENTE (posición, profundidad) entonces
resultado.VALOR := ESTATICA (posición, jugador);
resultado.CAMINO := NULO;
return resultado; sino
Sucesores := GENMOV (posición, jugador);
Si EstaVacia (Sucesores) entonces
resultado.VALOR := ESTATICA (posición, jugador);
resultado.CAMINO := NULO;
return resultado; sino
por cada sucesor de Sucesores
resultadoSucesor := MINIMAX_ALFABETA (sucesor, profundidad+1, CONTRARIO(jugador), -umbralPASO, -umbralUSO);

// el mejor resultado se va guadando en umbralPASO
Si umbralPASO < - resultadoSucesor.VALOR entonces umbralPASO := - resultadoSucesor.VALOR; resultadoMejor.CAMINO := sucesor + resultadoSucesor.CAMINO; fin si; // umbralUSO se usa para podar los hermanos Si umbralPASO >= umbralUSO entonces
resultadoMejor.VALOR := umbralPASO;
return resultadoMejor; finsi; fin por;
resultadoMejor.VALOR := umbralPASO;
return resultadoMejor; fin sino; fin sino;

fin MINIMAX_ALFABETA;