Alfa – beta no es un algoritmo diferente a minimax. Es una mejora que se añade a minimax. Podemos tener minimax puro o minimax con poda alfa – beta.

La poda alfa – beta se describe en esta entrada de Wikipedia y en muchas otras fuentes: https://es.wikipedia.org/wiki/Poda_alfa-beta. No es fácil de entender ni tampoco de explicar. Vamos a intentarlo.

Parámetros alfa y beta:

Recordemos que en minimax hay un jugador, en nuestro caso el ratón, que intenta maximizar la puntuación, y otro jugador, en nuestro caso los gatos, que intenta minimizarla. Pues bien, a esto la poda alfa – beta le añade dos parámetros:

• Alfa: Es la mejor (mayor) puntuación que tiene garantizada hasta el momento el jugador maximizador.
• Beta: Es la mejor (menor) puntuación que tiene garantizada hasta el momento el jugador minimizador.

Inicialmente alfa empieza con un valor muy bajo, en teoría menos infinito. Y beta empieza con un valor muy alto, en teoría más infinito. En la práctica, como estamos usando un byte sin signo para las evaluaciones, el valor más bajo posible es 0 y el más alto posible es 255. Por tanto, empezamos así:

• Alfa inicial = 0.
• Beta inicial = 255.

Ahora vamos desarrollando el árbol de juego en profundidad, es decir, desde la raíz hasta la primera hora. Y vamos pasando los parámetros alfa y beta, primero hacia abajo y luego hacia arriba. Lo mejor es verlo con un ejemplo.

Ejemplo de búsqueda alfa – beta:

El árbol anterior es el resultado final del proceso de búsqueda, en el que se han podado las ramas que están sombreadas. Verlo así es fácil; lo complejo es entender por qué esas ramas sombreadas se pueden podar o, mejor dicho, por qué se puede prescindir directamente de generarlas y evaluarlas.

Proceso paso a paso:

El proceso paso a paso es así:

• Inicialmente, desarrollamos el árbol de juego hasta la primera hoja, pasando los alfa y beta iniciales “hacia abajo”:

• En segundo lugar, y como hemos llegado hasta una hoja, aplicamos la función de evaluación sobre la misma, que nos devuelve un valor de 5. Ese valor 5 se devuelve al padre de la hoja que, al ser un nodo minimizador (turno de los gatos), lo compara con beta = 255 y, al ser 5 menor que 255, toma beta = 5:

• Ahora se desarrolla la segunda hoja, que ya no recibe alfa = 0 y beta = 255, sino alfa = 0 y beta = 5. Al tratarse de una hoja, se evalúa con la función de evaluación, que devuelve un valor de 6:

• Ese valor de 6 se retorna al padre, de forma análoga al caso anterior con 5, y, al ser el padre un nodo minimizador (turno de los gatos), compara 6 con beta = 5 pero, en este caso, al ser 6 mayor que 5, no se actualiza beta. Beta se queda con el valor de 5, que es el valor que se retorna al abuelo:

• Ahora el abuelo es un nodo maximizador (turno del ratón) y, por tanto, compara 5 con alfa = 0. Y como 5 es mayor que 0, toma alfa = 5. Ahora los valores de alfa = 5 y beta = 255 son los que se pasan al siguiente padre:

• Y de ese padre, alfa = 5 y beta = 255 se pasan a la tercera hoja que, al ser hoja, se evalúa con la función de evaluación, que ahora devuelve 7. Y ese 7 se devuelve al padre:

• Y como el padre es un nodo minimizador (turno de los gatos), compara 7 con beta = 255, y, como 7 es menor que 255, se queda con beta = 7. Ahora los valores alfa = 5 y beta = 7 se pasan a la cuarta hoja:

• Y como la cuarta hoja es una hoja, se evalúa con la función de evaluación, que devuelve 4. Y este 4 se pasa al padre que, al ser un nodo minimizador (turno de los gatos), lo compara con beta = 7 y, al ser 4 menor que 7, se queda con beta = 4:

• Por último, y antes de devolver ese 4 al abuelo, se da una situación muy interesante: alfa (5) >= beta (4). Eso significa que, aunque habría un tercer hijo de valor 5 (quinta hoja), no es necesario desarrollarlo ni evaluarlo. Esto es lo que se llama una “poda alfa”, porque se produce en un nodo minimizador, siendo la “poda beta” la situación equivalente cuando se produce en un nodo maximizador:

Y para entender por qué ese tercer hijo no es necesario conviene volver al árbol completo:

En este caso esa quinta hoja hubiera valido 5 según la función de evaluación, pero, en realidad, da igual lo que valga. Por eso se puede podar o, mejor dicho, no es necesario ni generarla ni evaluarla.

Si esa quinta hoja hubiera valido 4 o más (por ejemplo, 5) es evidente que no hubiera afectado al proceso de búsqueda, porque tiene un hermano de 4 y su padre busca el valor mínimo. Y si hubiera valida menos de 4 (por ejemplo, 3), dado que el abuelo busca el valor máximo y tiene garantizado un 5 hacia la rama de la izquierda, nunca hubiera tomado el camino de la derecha.

En definitiva, los valores de alfa y beta que se van pasando hacia abajo y luego hacia arriba determinan que, cuando alfa es mayor o igual que beta, no es necesario desarrollar ni evaluar los siguientes nodos. Esto ocurre en todas las ramas del árbol anterior que están sombreadas.

Simulación de la búsqueda alfa – beta:

Otra forma buena de entender la búsqueda alfa – beta es mediante un simulador, de los cuales hay muchos en Internet. Algunos ejemplos son:

https://raphsilva.github.io/utilities/minimax_simulator/#

http://homepage.ufp.pt/jtorres/ensino/ia/alfabeta.html

El primer simulador usa siempre el mismo ejemplo. El segundo permite configurar el árbol que se quiere analizar (número de nodos, profundidad, evaluaciones de las hojas, etc.). Por ejemplo, con los valores:

• Enter the game tree structure => 3 2 2 2 2 1 2 1 1 2 2 3 1 1 2 1 1 2 1.
• Enter the game tree terminal values => 5 6 7 4 5 3 6 6 9 7 5 9 8 6.

es posible configurar el mismo árbol que en Wikipedia, y simular su búsqueda paso a paso o completa, señalando las ramas que se podan y la variante principal.

Pseudocódigo de la búsqueda alfa – beta:

Por último, una forma condensada de describir la búsqueda alfa – beta es mediante su descripción en pseudocódigo, que es así:

Como se puede observar es una definición recursiva, es decir, en términos de sí misma. Y, sí, en ensamblador se pueden programar rutinas recursivas…