Poda alfa-beta

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.

El desarrollo del algoritmo en pseudocódigo será el siguiente:

función alfa-beta(nodo //en nuestro caso el tablero, profundidad, α, β, jugador)
    si nodo es un nodo terminal o profundidad = 0
        devolver el valor heurístico del nodo
    si jugador1
        para cada hijo de nodo
            α := max(α, alfa-beta(hijo, profundidad-1, α, β, jugador2))
            si β≤α
                romper (* poda β *)
        devolver α
    si no
        para cada hijo de nodo
            β := min(β, alfa-beta(hijo, profundidad-1, α, β, jugador1))
            si β≤α
                romper (* poda α *)
        devolver β

(* Llamada inicial *)
alfa-beta(origen, profundidad, -infinito, +infinito, jugador_deseado)

 

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.

Comenzamos primero con la búsqueda en profundidad. 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 caso se expande el camino que conduce a los nodos hoja 7 y, buscando un valor β menor, el nodo etiquetado con 4. 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.

El resto del desarrollo del árbol se seguiría utilizando los criterios mencionados con anterioridad.

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.

Si esto pudiera hacerse, implicaría que alfa-beta sólo tendría que examinar ${\displaystyle O(b^{d/2})}$  en lugar de los ${\displaystyle O(b^{d})}$  de Minimax. Esto implica que el factor de ramificación eficaz será de ${\displaystyle {\sqrt {b}}}$  en lugar de ${\displaystyle b}$ . En otras palabras, alfa-beta podría mirar hacia delante aproximadamente dos veces más que Minimax en la misma cantidad de tiempo.

Si se recurre a una ordenación aleatoria en lugar de primero el mejor en los sucesores, el número aproximado de nodos examinados sería de ${\displaystyle O(b^{3d/4})}$  para un valor moderado de ${\displaystyle b}$ . En ajedrez se puede realizar una función de ordenación sencilla teniendo en cuenta primero capturas de fichas, después amenazas, movimientos hacia delante y por último movimientos hacia detrás, esto conseguiría aproximadamente un factor de dos del resultado ${\displaystyle O(b^{d/2})}$  del mejor caso. La inclusión de esquemas dinámicos para ordenar movimientos, basados en experiencia podrían acercarse al límite teórico.^[5]​