Alpha-Beta

INTRODUCCIÓN 

El algoritmo poda alfa-beta es una técnica mejorada del algoritmo minimax, que consiste en dividirlo en la mitad. La jugada es que es posible calcular la decisión mínima correcta sin mirar todos los nodos en el árbol de juego. La poda alfa-beta puede aplicarse a árboles de cualquier profundidad y también subárboles enteros. 

MARCO TEÓRICO PODA ALPHA-BETA 

Este algoritmo es el más utilizado en las aplicaciones referidas a juegos, dada su excepcional utilidad en el aumento de la velocidad de la búsqueda sin producir pérdida de la información. Es una extensión en particular del algoritmoo de Búsqueda Minimax en juegos de dos contrincantes. Cada vez que se evalúa un nodo, el algoritmo determina los nuevos hijos generados, pueden generar una mejor utilidad de la que ya posee el nodo estudiado y si afecta al nodo padre. De no ser así, eso significa que seguir analizando esa rama es desperdiciara recursos como tiempo y espacio, por lo cual no se sigue generando y simplemente se le poda, de allí el nombre.

DESARROLLO DEL ALGORITMO 

La búsqueda minimax es primero en profundidad, por ello en cualquier momento sólo se deben considerar los nodos a lo largo de un camino en el árbol. La poda alfa-beta toma dicho nombre de la utilización de dos parámetros que describen los límites sobre los valores hacia atrás que aparecen a lo largo de cada camino. α es el valor de la mejor opción hasta el momento a lo largo del camino para MAX, esto implicará por lo tanto la elección del valor más alto  β es el valor de la mejor opción hasta el momento a lo largo del camino para MIN, esto implicará por lo tanto la elección del valor más bajo. Esta búsqueda alfa-beta va actualizando el valor de los parámetros según se recorre el árbol. El método realizará la poda de las ramas restantes cuando el valor actual que se está examinando sea peor que el valor actual de α o β para MAX o MIN, respectivamente.