Poda alfa-beta
Entre los pioneros en el uso de esta técnica encontramos a Arthur Samuel, D.J Edwards y T.P.
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.
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.
El desarrollo del algoritmo en pseudocódigo será el siguiente: A continuación se presenta un ejemplo de aplicación del algoritmo para el árbol de la figura.
En ella los nodos podados al aplicar el algoritmo se presentan sombreados en gris.
El padre de los nodos hoja más a la izquierda, etiquetados con 5 y 6 respectivamente, deberá escoger un valor β al tratarse de un nivel MIN, esto implica que deberá escoger el valor mínimo entre dichos nodos, es decir 5.
Siguiendo el desarrollo, se expandirán el resto de sucesores del padre.
En este momento el valor momentáneo de β en ese nivel es 4 (el mínimo entre 7 y 4).
Esto implica que en este momento en el nivel superior, el padre del nodo que etiquetamos anteriormente con β igual a 5, y de este β igual a 4 momentáneo, debe decidir el mejor valor, (el más alto al encontrarse en un nivel MAX), si siguiéramos expandiendo hijos del nodo MIN padre de 7 y 4, sólo podríamos conseguir valores menores a 4, lo que seguiría implicando una elección de la jugada izquierda en el nivel MAX, por lo tanto, podemos podar el resto de hijos, tal y como se muestra en la figura.
La eficacia de la poda alfabeta depende del orden en el que se examinan los sucesores, es decir, el algoritmo se comportará de forma más eficiente si examinamos primero los sucesores que probablemente serán los mejores.
En otras palabras, alfa-beta podría mirar hacia delante aproximadamente dos veces más que Minimax en la misma cantidad de tiempo.
La inclusión de esquemas dinámicos para ordenar movimientos, basados en experiencia podrían acercarse al límite teórico.
