Alfabeta: El árbol podado

Aquí tenemos un árbol de búsqueda completo. Hemos desarrollado el minimax en su totalidad calculando el árbol de variantes completo sin aplicar ninguna técnica de poda. Este ejemplo de búsqueda completa con minimax nos servirá de base para explicar el algoritmo alfabeta.

A continuación vamos a ver si es posible aplicar alguna técnica que nos ahorre algo de trabajo.

Para esto seguiremos con detalle el camino que sigue el algoritmo de búsqueda mientras va construyendo el árbol de variantes.

Siguiendo de cerca la búsqueda

NIVEL 0: Partiendo de la posición de partida, el primer trabajo es generar su lista de jugadas. Una vez generada consideramos la primera jugada de la lista y la aplicamos sobre el tablero. Como resultado tenemos una posición nueva en el nivel 1.

NIVEL 1: Generamos la lista de jugadas para esta nueva posición. Otra vez nos quedamos con la primera de la lista y la realizamos en el tablero, así llegamos a una nueva posición en el nivel 2.

NIVEL 2: Repetimos el proceso: generamos la lista de jugadas y realizamos la primera en el tablero. El resultado es una posición en el siguiente nivel, el 3.

NIVEL 3: Estamos en el final del árbol, los nodos de este nivel serán enviados a la función de evaluación y etiquetados con un valor numérico. El resultado de este primer nodo terminal evaluado es 4.

Subiendo y bajando

NIVEL 3: El algoritmo de búsqueda ha tocado fondo: es hora de iniciar su camino de regreso. El primer escalón de subida es ascender al nivel 2 con el resultado del primer nodo terminal evaluado. Este valor se anota como valor provisional del nodo padre.

NIVEL 2: Este nodo toma como valor provisional 4. Ahora el algoritmo desciende de nuevo para examinar el siguiente nodo terminal en la lista de jugadas de esa rama.

NIVEL 3: Enviamos la posición a la función de evaluación y resulta que este otro nodo vale 2. El flujo del programa asciende de nuevo para informar al nodo padre del nuevo valor terminal.

NIVEL 2: Recordemos que aquí tenemos un valor provisional de 4. El nuevo valor que se le propone es 2. Como estamos en un nivel maximizador, el nodo conserva el valor anterior más alto, con lo que el valor definitivo de este nodo es 4.

El flujo de trabajo del minimax

Vamos a hacer una pequeña escala en el nivel 2. Nos detenemos un momento para observar el flujo de trabajo del minimax: el árbol se va formando expandiéndose hacia abajo hasta encontrar un nodo con valor final.

Cuando se asigna valor de forma definitiva a un nodo el algoritmo sube para informar al padre del valor recién obtenido.

Estos valores definitivos se pueden obtener como resultado del juicio directo de la función de evaluación (nodos terminales) o porque todos los nodos hijos ya tienen valor definitivo.

En este punto estamos ahora: el nodo del nivel 2 tiene valor final porque ya se han valorado todos sus hijos. Por tanto la función de búsqueda sube de nivel para informar al nodo padre (minimizador) del valor de su primer hijo. Anotamos por tanto un valor provisional 4 en este nodo del nivel 1.

Identificando límites

A continuación el flujo del programa se dirige otra vez hacia abajo para expandir el siguiente nodo de nivel 2.

Pero esta vez hay una diferencia, tenemos un límite: el valor final del nodo hermano, es decir 4.

¿Qué significa que tenemos un límite = 4? El padre del nivel 2 es minimizador, elegirá el menor de sus nodos hijos en cada rama. O dicho de otra forma: entre todos los nodos hermanos del nivel 2 será escogido el menor. Luego como el primer nodo examinado tiene un valor 4, es seguro que ningún nodo con valor superior a 4 será elegido en esta rama.

Por tanto en cuanto detectemos que un nodo va a tener un valor menor de esta cifra podemos ahorrarnos esa parte de la búsqueda sin miedo a perder nada: fuese cual fuese el resultado de esas posiciones que no vamos a generar ni evaluar no importa porque nunca hubieran sido escogidas.

Aplicando los límites

Ahora volvamos al ejemplo del diagrama. El algoritmo de búsqueda empieza a desarrollar el nodo del nivel 2 (el hermano del que vale 4). Desciende y valora el primer nodo terminal, que es puntuado con un valor de 10. Luego sube y se anota ese valor como provisional del nodo padre.

¿Podemos podar el árbol en esta rama?

Tenemos un valor provisional de 10. Imaginemos que seguimos con la búsqueda, descendemos y le pedimos el siguiente valor a la función de evaluación, puede ser alguno de estos casos:

Resultado de la poda

Generalizando: los valores de los nodos ya evaluados son utilizados como límites para los nodos hermanos de ese nivel.
Si el nivel es maximizador podremos podar si obtenemos un valor provisional superior a los ya obtenidos. Si estamos en un nivel minimizador podaremos si detectamos un valor provisional inferior a límite de sus hermanos.

En el diagrama podemos ver como quedaría el árbol de variantes tras aplicar la poda alfa beta.

Además de aplicar los límites que va encontrando, el algoritmo debe ir actualizándolos.

En el algoritmo de búsqueda clásico de los programas de ajedrez se utilizan normalmente dos límites de este tipo, uno representa el límite para los niveles maximizadores y otro para los minimizadores. Se les suele llamar alfa y beta, y de ahí recibe el nombre el algoritmo.

Un buen alfabeta acelera muchísimo el proceso de búsqueda. Sin estas técnicas de poda los más modernos ordenadores apenas conseguirían profundizar unas pocas jugadas en un tiempo razonable.

Para conseguir una buena poda alfabeta es imprescindible ordenar la lista de jugadas: No es indiferente el orden en que se coloquen las jugadas en la lista, es muy importante que los mejores movimientos estén en el principio.