Una técnica de poda de árboles de búsqueda aplicada a búsquedas adversariales de tipo minimax que mantiene dos cotas (alpha y beta) para eliminar ramas que no pueden influir en la decisión de la raíz, reduciendo así el número de nodos evaluados sin cambiar el resultado minimax óptimo cuando se aplica correctamente.

Principio

Mantener y propagar cotas inferior (alpha) y superior (beta) de los valores alcanzables a lo largo del árbol; podar cualquier subárbol cuya cota no pueda mejorar la mejor opción actual en nodos antecesores.

Demostración

En un árbol de juego de dos jugadores, al explorar un nodo para el jugador maximizador con la mejor valoración actual alpha, si un subárbol hijo del oponente minimizador produce un valor ≤ alpha, ese subárbol puede omitirse porque el maximizador evitará caminos que lleven allí; en la práctica esto puede eliminar grandes porciones del árbol.

Aplicación incorrecta

Poda basada en cotas incorrectas o mal inicializadas, aplicar alpha–beta en problemas no de suma cero o no minimax sin adaptación, o asumir que siempre produce aceleraciones lineales independientemente del orden de jugadas.

Consecuencia

Usada correctamente reduce el tiempo y la memoria de búsqueda—a menudo de forma drástica con buen ordenamiento de movimientos—manteniendo la decisión minimax exacta; sin embargo, la complejidad en el peor caso sigue siendo exponencial si las oportunidades de poda son limitadas.

Inversión

Expandir cada nodo sin poda (minimax completo) invierte la técnica, garantizando la evaluación de todas las hojas y produciendo la misma decisión pero con el coste computacional máximo y sin atajos basados en cotas.

Límite

Se aplica a problemas deterministas, de información perfecta y alternancia de turnos; excluye nodos estocásticos, juegos parcialmente observables y situaciones que requieren criterios no-minimax salvo que se adapten (por ejemplo expectiminimax o evaluaciones heurísticas).

Tensión semántica

A menudo se confunde con heurísticas de ordenación de movimientos y otros métodos de poda (p. ej. poda por movimiento nulo); alpha–beta es específicamente la regla de poda por propagación de cotas dentro de minimax, no una estrategia de ordenación aunque el orden de movimientos afecte mucho su eficacia.

Síntesis

La poda alfa–beta es el uso disciplinado de cotas alpha y beta propagadas para omitir de forma segura partes de un árbol minimax: una regla de poda exacta que sacrifica exploración redundante a cambio de decisiones óptimas idénticas, cuyos ahorros prácticos dependen de la estructura del problema y del orden de movimientos.