Aprendizaje por refuerzo (RL) — Capítulo 4: Min-Max y Alpha-Beta Pruning — Parte 2: Alpha-Beta Pruning

9 min readDec 7, 2023

En la parte anterior explicamos el algoritmo Min-Max como una estrategia de simular todas las posibles jugadas para seleccionar la que garantiza la victoria o la mejor ventaja. Uno de los problemas que tenía este algoritmo es que requiere explorar todos los estados posibles que, en la mayoría de los casos, resulta imposible de llevar a cabo.

Es esta parte exploraremos el algoritmo Min-Max con Alpha-Beta Pruning, que nos va a permitir “podar el árbol” de decisiones para hacer la búsqueda más rápida sin necesidad de explorar todos los estados.

Pongámonos en marcha!

Introducción

El algoritmo Min-Max presenta un desafío fundamental: requiere explorar todos los posibles estados, lo cual se vuelve impracticable en juegos con un gran número de posiciones posibles. En nuestro ejemplo anterior, resolvimos el juego del TaTeTi utilizando Min-Max, y este juego tiene una complejidad de 4, lo que implica que existen aproximadamente 10⁴ estados posibles en total. Sin embargo, cuando abordamos juegos más complejos como el ajedrez o el GO, con complejidades de 43 y 172 respectivamente, resulta esencialmente imposible, ya que requeriría un tiempo y una memoria infinitos en la práctica.

Una solución para aplicar Min-Max en estas situaciones consiste en no explorar todos los estados posibles hacia adelante, sino solo mirar un número limitado de pasos hacia el futuro, lo que llamaremos “profundidad de búsqueda”. Sin embargo, surge una pregunta importante: dado que solo evaluamos unos pocos pasos hacia adelante y no alcanzamos el estado final del juego, ¿Cómo determinamos el valor de la posición actual?.

Cuando empleamos Min-Max con una exploración completa, llegamos al final del juego, lo que nos permite determinar claramente si una posición es un empate, una derrota o una victoria. Pero si no llegamos al estado final, necesitamos una manera de medir la calidad de la posición actual, lo cual no es una tarea sencilla.

En juegos como el ajedrez, es posible calcular el valor de nuestras piezas y restarle el valor de las piezas del oponente para obtener una estimación aproximada de la ventaja o desventaja en la partida. Sin embargo, el ajedrez es un juego complejo en el cual un jugador puede tener una posición ganadora incluso con menos piezas que su oponente.

Otra solución, que no resuelve por completo el problema de explorar todos los estados pero sí mejora significativamente la eficiencia, es el algoritmo Min-Max con Alpha-Beta Pruning. La palabra Pruning (poda) hace referencia a la eliminación de ciertas ramas del árbol de búsqueda que no tienen sentido explorar, reduciendo así significativamente el espacio de búsqueda.

El algoritmo de Alpha-Beta Pruning, como mencionamos, tiene como objetivo reducir el tamaño del árbol de búsqueda. Para lograrlo, debemos proporcionar al algoritmo Min-Max criterios de detección que le indiquen cuándo debe detener la búsqueda en ciertas regiones del árbol una vez que haya encontrado el mínimo o máximo garantizado en ese nivel.

Vamos a entender este concepto con el mismo ejemplo con el que veníamos trabajando en la parte anterior.

En el ejemplo explotamos el árbol de arriba hacia abajo y de izquierda a derecha. Si exploramos la primer rama completa llegamos a que si ambos jugadores juegan de forma perfecta llegamos a empate que es a lo mismo que llegamos con Min-Max. Ahora vamos a la segunda rama, si exploramos la primer bifurcación llegamos a que perdemos la partida, entonces ¿es necesario explorar la otra bifurcación?. La respuesta es no.

Independientemente de el resultado sabemos que esa rama nunca se va a jugar porque el oponente nunca va a tomar esa decisión porque ya tiene una que le lleva a la victoria. Algo similar sucede con la tercera rama, por lo que el espacio de búsqueda se reduce significativamente.

Búsqueda Min-Max en una partida de TaTeTi con poda.

Algoritmo Alpha-Beta Pruning

La poda alfa-beta o Alpha-Beta Pruning utiliza dos parámetros: alpha (α) y beta (β) para realizar la búsqueda. Estos dos parámetros nos permite hacer seguimiento de la mejor puntación de ambos jugados mientras se recorre el árbol. Alpha es el mejor resultado del jugador Max, por lo que queremos obtener el mayor valor posible de este. Por otro lado, beta es el mejor resultado al que puede aspirar, por el momento, nuestro contrincante (el jugador Min) y por lo tanto queremos el menor valor posible de este. Estos valores se mantienen y actualizan durante toda la búsqueda y es lo que nos va a permitir decidir si se justifica explorar una rama o la podemos “podar’’.

La mejor forma de entender el funcionamiento de este algoritmo es mediante un ejemplo, así que vamos a ello. En este ejemplo tenemos varios estados (que llamamos A, B, C, D, E, F y G), que recordemos que al inicio solo conocemos el estado actual (el A). También se indican los estados finales, con el valor de esos estados, y recordemos al igual que antes que estos estados finales son desconocidos para nosotros hasta que decidamos visitarlos.

Búsqueda Min-Max con Alpha-Beta Pruning: Paso 1.

El algoritmo se desarrolla de la siguiente manera:

Primero inicializamos los valores de alpha y beta en -∞ y +∞ que son los valores extremos para ambos parámetros (recordemos que queremos que α sea lo mas grande posible y β lo mas chico posible).
En el siguiente paso propagamos esos valores al nodo B y posteriormente al nodo D. Luego el nodo D llega a los dos estados finales y dado que es la jugada del jugador Max, elegiremos el máximo de todos los valores, que es 3. Este valor también se propaga al valor de α del nodo D, ya que 3 > -∞.
Ahora el algoritmo propaga los valores al nodo B. Como en el nodo B es el turno del jugador Min, el valor se propaga al valor β, y como queremos minimizar este valor y 3 < ∞, entonces β = 3 y α conserva el valor de -∞, ya que el jugador Min intenta minimizar este valor.

Búsqueda Min-Max con Alpha-Beta Pruning: Paso 2.

En el segundo paso recorremos el nodo E. El cual hereda los valores de α = -∞ y β = 3 del nodo B.
El nodo E explora el primer estado final que tiene un valor de 5, y como 5 > -∞, α toma ese valor.
Ahora se cumple una condición esencial en el algoritmo de Alpha-Beta Pruning. Como ahora los valores del nodo E son α = 5 y β = 3 y se cumple la condición α > β, no es necesario explorar el resto de nodos de E.

Entendamos porque pasa esto en mas detalle. En el nodo E es el turno del jugador Max, mientras que en su nodo superior (B) es el turno Min que va a tomar el menor de los valores. Como el nodo E ya asegura que seguro como mínimo ese nodo va a tener un valor de 5 ya sabemos que este nunca se va a explorar, ya que en el turno del nodo B va siempre a intentar minimizar el valor y esa elección es ir por el camino del nodo D, que tiene un valor de 3.

Búsqueda Min-Max con Alpha-Beta Pruning: Paso 3.

En el tercer paso se devuelven los valores hasta el nodo A. Primero en el nodo B se mantienen los valores de α = -∞ y β = 3 ya que 3 < 5.
Luego se propagan al nodo A, y como es el turno del jugador Max, va a tomar el máximo entre su valor actual de α, que es -∞ y el valor del nodo hijo B, que es 3, por lo que los valores de α y β del nodo A terminan siendo 3 y +∞ respectivamente.
Finalmente le pasa estos valores al nodo C.

Búsqueda Min-Max con Alpha-Beta Pruning: Paso 4.

En el cuarto paso los valores del nodo C se pasan al nodo hijo F.
Luego el nodo F compara su valor actual de α con el 0 y con el 1 y como α = 3 es mayor que 0 y 1 este valor se mantiene igual. Pero, el valor del nodo si es 1 que es el máximo entre 0 y 1.
Acá F debió explorar los dos nodos finales porque en ningún momento se cumplió la condición α > β.

Búsqueda Min-Max con Alpha-Beta Pruning: Paso 5.

Finalmente, en el quinto paso, el nodo C hereda de F el valor 1 como su valor β ya que este es el tuno del jugador Min y 1 < +∞.
Ahora se cumple nuevamente la condición en el nodo C de que α > β, por lo que el hijo derecho de C será podado y el algoritmo no atravesará todo el subárbol G.

Hasta acá toda la búsqueda y por lo tanto en el estado actual A estamos en condiciones de tomar nuestra acción. Como nosotros queremos maximizar las recompensas debemos tomar el máximo entre sus dos nodos hijos que son 3 y 1. Por tanto, el valor óptimo para el maximizador es 3 que, para este ejemplo, es tomar la acción que nos lleva al nodo B.

Y hasta aquí todo el proceso de Alpha-Beta Pruning, que si bien requirió de cierto esfuerzo de nuestra parte para poder hacer todo el seguimiento, podemos ver que no es mas que ir propagando los valores de α y β y tomando los máximos y mínimos según corresponda. Esto al igual que el algoritmo Min-Max se puede resolver mediante una función recurrente haciendo unas pocas modificaciones:

Y con estas modificaciones ya tenemos implementado nuestro algoritmo.

Min-Max vs Alpha-Beta Pruning

Ahora veamos como actúa Min-Max con y sin poda en una partida de TaTeTi, ¿realmente mejora la velocidad estas modificaciones que realizamos?, veamos.

Una partida de TaTeTi con dos jugadores Min-Max sin poda toma 492 segundos, mientras que el mismo algoritmo pero con poda tarda 35 segundos. Obviamente estos valores depende de la computadora que esté realizando el procesamiento, pero lo que importa son los valores relativos que nos dice que el algoritmo con poda tarda unas 14 veces menos que el Min-Max sin poda!.

La poda realmente tuvo un impacto en la velocidad, pero seamos sinceros, 35 segundos sigue siendo mucho tiempo para una partida de un juego tan simple, imagínese una partida de ajedrez, tardaríamos años (y cuando digo años me refiero a AÑOS, con mayúsculas).

El algoritmo Min-Max y Alpha-Beta Pruning son muy potentes ya que nos permiten encontrar la acción perfecta para obtener el máximo retorno de una partida, pero esto lo hace a expensas de recorrer todos o casi todos los estados y eso es inviable en la mayoría de situaciones.

Si solo existiera una forma mas “inteligente’’ de realizar la poda… eso lo veremos mas adelante. Mientras tanto mantenga en su memoria la imagen del principio de este capítulo donde podemos ver a Garry Kasparov contra Deep Blue porque, unos capítulos mas adelante de esta serie sobre aprendizaje por refuerzo o 19 años después de esa partida, nos vamos a encontrar con una situación similar.

Y hasta aquí la teoría sobre los modelos de Min-Max y Alpha-Beta Pruning. En la próxima parte veremos como implementar estos dos algoritmos en Python, asi que no te lo pierdas!. Y si estás ansioso puedes ir consultado las notebooks con las implementaciones de estos algoritmos en el repositorio de Git: