La poda Alfa-Beta se basa en la idea de disponer de dos valores que conforman una ventana a la cual deben pertencer los valores de f_ev(n) para que sean considerados. En los nodos n MAX, según el algoritmo minimax, se debe maximizar el valor de los nodos sucesores. En estos nodos, se utiliza el parámetro a (n) que determina el máximo de los valores de los nodos sucesores encontrado hasta el momento. Así mismo, como los nodos n MIN tratan de minimizar el valor de los nodos, utilizan el parámetro b (n) que va a ser, en cada momento, el mínimo de los valores encontrados de los nodos sucesores de ese nodo.

Existen dos formas de podar, dependiendo del nodo en el que se está estudiando. En los nodos MAX, la condición de poda es: a _p >= b _p-1 es decir, si el a de un nodo MAX de profundidad p es mayor o igual que el b del nodo MIN padre (profundidad p-1) se pueden podar los sucesores del nodo MAX no estudiados todavía. Esto es debido a que, como valor inferior, el nodo MAX va a devolver ese valor de a (a _p). Ya que el nodo superior trata de minimizar, va a calcular:

con lo que siempre va a elegir el b _p-1. Por lo tanto, los nodos no estudiados todavía en el nodo MAX no es necesario estudiarlos, porque no cambian el valor b del nodo padre.

Simétricamente, la condición de poda en los nodos MIN es:b _p <= a _p-1. La explicación es análoga al caso anterior. El algoritmo recursivo del Alfa-Beta podría especificarse de la forma expresada en la tabla adjunta, donde la llamada inicial es de la forma: Alfa-Beta (Situación Inicial Menor-Número Mayor-Número 0)

procedimiento Alfa-Beta (Situación Alfa-Beta Profundidad)

Si situación está considerada como empate, devolver 0

Si Situación es ganadora, devolver mayor-número

Si Situación es perdedora, devolver menor-número

Si profundidad = profundidad-máxima, devolver evaluación (Situación)

Si nivel-max-p

Para todo a_i sucesor de situación y Alfa < Beta

Alfa-Beta=Alfa-Beta (a _i, Alfa, Beta, profundidad + 1)

Alfa = max(Alfa, Alfa-Beta)

Devolver Alfa

Si no

Para todo a _i sucesor de situación y Beta > Alfa

Alfa-Beta=Alfa-Beta (a _i, Alfa, Beta, profundidad + 1)

Beta = min(Beta, Alfa-Beta)

Devolver Beta

Ejemplo:

Con el árbol de la figura, va a realizarse una búsqueda minimax con la poda alfa-beta. En este árbol los nodos círculo son nodos del nivel MAX, y, por tanto, se les denomina nodos MAX, y los nodos cuadrado pertenecen a niveles MIN, y por tanto, se les denomina nodos MIN. Dentro de cada nodo aparecen su identificador y debajo de los nodos hoja aparece el valor que devolvería la función de evaluación si se evaluara dicho nodo.

El algoritmo se inicia con el nodo inicial y los valores para a y b siguientes, teniendo en cuenta que no se puede representar el µ en las computadoras:

a = menor número posible (m); b = mayor número posible (M)

Los valores de m y M dependen del lenguaje de programación, y de la computadora utilizada, normalmente. Como se puede observar en la siguiente figura, se produceuna poda en el nodo 6 ya que el a en ese nodo (6) es mayor que el valor de b (5) en el nodo padre. Después puede observarse cómo se produce una poda para el nodo 3 debido a que el valor de b (5) es igual al de a (5) del nivel superior, con lo que, por mucho que se estudien los hijos del nodo 3 no se va a cambiar el valor del nodo 1. Por último vuelve a producirse una poda debido a que, en el nodo 11 el valor de a (10) es mayor que el valor de b (8) en el nodo padre.

La técnica Alfa-Beta es completamente general, pudiendo utilizarse tanto para árboles de cualquier profundidad finita, como para árboles de profundida irregular. Las interrupciones que se producen en los nodos conjuntivos se llaman "alfa-interrupciones", diciéndose también que existe un "alfa-atajo" en tanto que las interrupciones que se producen en los nodos disyuntivos se llaman "betas-interrupciones", o también se dice que existe un "beta-atajo".