La efectividad del procedimiento alfa-beta depende en gran medida del orden en que se examinen los caminos. Si se examinan primero los peores caminos no se realizará ningún corte. Pero, naturalmente, si de antemano se conociera el mejor camino no necesitaríamos buscarlo.
La efectividad de la técnica de poda en el caso perfecto ofrece una cota superior del rendimiento en otras situaciones. Según Knuth y Moore (1975), si los nodos están perfectamente ordenados, el número de nodos terminales considerados en una búsqueda de profundidad d con alfa-beta es el doble de los nodos terminales considerados en una búsqueda de profundidad d/2 sin alfa-beta. Esto significa que en el caso perfecto, una búsqueda alfa-beta nos da una ganancia sustancial pudiendo explorar con igual costo la mitad de los nodos finales de un árbol de juego del doble de profundidad.
En esta sección se describen otras modificaciones del procedimiento MINIMAX que también mejoran su rendimiento.
2.3.3.1. Poda de inultilidades
La poda de inutilidades es la finalización de la exploración de un subárbol que ofrece pocas posibilidades de mejora sobre otros caminos que ya han sido explorados.
En el ejemplo de la figura 3, después de examinar el nodo B el jugador maximizante se asegura un valor de 3. Al examinar el nodo G se obtiene un valor 3.1 que es sólo algo mejor que 3. Puesto que si se exploran los nodos H e I no lograremos mejorar este valor desde el punto de vista del jugador maximizante, sería mejor podarlos y dedicar más tiempo a explorar otras partes del árbol donde se puedan obtener más ventajas.
No hay comentarios:
Publicar un comentario