Tema

Poda alfa beta

IA clásica
Nivel avanzado

La poda alfa beta descarta ramas que no pueden cambiar el valor minimax de la raíz, manteniendo alfa como el mejor valor asegurado para MAX y beta como el mejor valor asegurado para MIN a lo largo del camino actual.

Nombre en inglés

Alpha beta pruning

Intuición

Conviene pensar que MAX ya tiene una oferta en la mano por valor alfa. Al explorar una jugada del rival, en cuanto aparece una respuesta que deja el resultado por debajo de alfa, el resto de esa rama sobra, porque el rival elegirá esa respuesta o algo todavía peor. El valor devuelto por la raíz es exactamente el mismo que sin podar, de modo que la poda ahorra tiempo sin cambiar la decisión.

Fórmula

se poda cuando alfa >= beta.  Con orden perfecto de hijos el coste baja de O(b^d) a O(b^{d/2})

Ejemplo resuelto

Se retoma el árbol con hojas 3, 12, 8 en la primera rama, 2, 4, 6 en la segunda y 14, 5, 2 en la tercera. La primera rama se explora entera y da 3, de modo que alfa = 3 en la raíz. En la segunda rama la primera hoja vale 2, con lo que ese nodo MIN ya no puede superar 2, que es menor o igual que alfa, y las hojas 4 y 6 se podan. En la tercera rama las hojas 14 y 5 no permiten podar, pero al ver el 2 el nodo queda en 2 y la raíz sigue valiendo 3. Se ahorran 2 hojas de 9.

Errores frecuentes

Creer que la poda puede cambiar la jugada elegida, cuando devuelve siempre el mismo valor de raíz y solo evita trabajo inútil.
Actualizar alfa en los nodos MIN y beta en los nodos MAX, confusión que poda ramas buenas y produce un valor de raíz equivocado.
Despreciar el orden de los hijos, ya que con el peor orden posible la poda no ahorra nada y con un orden razonable, por ejemplo el que da una búsqueda somera previa, el ahorro se acerca al caso ideal.

Ejercicio

Una raíz MAX tiene dos hijos MIN. El primer hijo tiene hojas 6 y 4 y el segundo tiene hojas 3, 9 y 7, exploradas de izquierda a derecha. Indica qué hojas se podan.

Ver la solución

El primer nodo MIN explora 6 y luego 4, con lo que vale 4 y la raíz fija alfa = 4. En el segundo nodo MIN la primera hoja vale 3, de modo que ese nodo ya no podrá superar 3 y se cumple beta = 3, que es menor o igual que alfa = 4. La condición de poda se activa y las hojas 9 y 7 no se evalúan. La raíz vale 4 y la mejor jugada es la primera.

Respuesta: Se podan las hojas 9 y 7.