PODA
ALFA-BETA
- La Poda alfa-beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Para ello, trata de eliminar partes grandes del árbol que se va construyendo de forma que se devuelva el mismo movimiento que devolvería este, podando ramas que se sepa que no van a influir en la decisión final.
La poda alfa-beta toma su nombre por el uso de dos parámetros que fijan ciertas cotas para el proceso de propagación hacia arriba que efectúa el algoritmo.- es el valor de la mejor opción hasta el momento a lo largo del camino para MAX, que representa, por tanto, una cota superior. El valor representa la cota inferior del valor que puede asignarse en último término a un nodo maximizante.
- es el valor de la mejor opción hasta el momento a lo largo del camino para MIN, que representa, por tanto, una cota inferior. El valor representa la cota superior del valor que puede asignarse en último término a un nodo minimizante.
Ejemplo:
Considera el árbol en figura siguiente de un juego de dos personas, donde los círculos son nodos max y los cuadrados son nodos min. Aplica el algoritmo minimax con poda alfa-beta, propaga los valores de evaluación hasta el nodo raíz, marca la mejor jugada para max, y marca todos los subárboles que se podan.
