La poda alfa- beta es un algoritmo de búsqueda que busca reducir el número de nodos evaluados en un árbol de búsqueda por el algoritmo minimax . Diseñado para juegos antagónicos y usado para juegos de máquina (en computadora ajedrez , computadora go y otros). El algoritmo se basa en la idea de que la evaluación de una rama del árbol de búsqueda puede finalizar prematuramente (sin calcular todos los valores de la función de evaluación) si se encuentra que el valor de la función de evaluación para esta rama está en en todo caso peor que el calculado para el ramal anterior. La poda alfa-beta es una optimización porque no afecta la corrección del algoritmo.
Allen Newell y Herbert Simon , usando lo que John McCarthy llamó una "aproximación" [1] en 1958, escribieron que la poda alfa-beta " parece haber sido inventada repetidamente " [2] . Arthur Samuel , Richards, Hart, Levin, Edwards propusieron de forma independiente las primeras versiones de este algoritmo [3] . McCarthy también presentó ideas similares en el Seminario de Dartmouth en 1956, y luego, en 1961, propuso a un grupo de sus estudiantes en el MIT , incluido Alan Kotok [4] , para la investigación . Alexander Brudno descubrió el algoritmo de forma independiente y publicó sus resultados en 1963 [5] . En 1975, Donald Knuth y Ronald Moore mejoraron el algoritmo agregando la poda "beta" [6] [7] .
La ventaja de la poda alfa-beta es, de hecho, que algunas de las ramas de subnivel del árbol de búsqueda se pueden excluir después de que al menos una de las ramas de nivel se haya considerado en su totalidad. Dado que el recorte se produce en todos los niveles de anidamiento (excepto en el último), el efecto puede ser bastante significativo. La eficiencia del método se ve significativamente afectada por la clasificación preliminar de opciones (sin enumeración o con enumeración a menor profundidad): al clasificar, cuantas más opciones "buenas" se consideren al principio, más ramas "malas" se pueden cortar sin un análisis exhaustivo.