Poda alfa-beta

Ejemplo de poda alfa-beta.

La poda alfa beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en programas de juegos entre adversarios como el ajedrez, el tres en raya o el Go.

Entre los pioneros en el uso de esta técnica encontramos a Arthur Samuel, D.J Edwards y T.P. Hart,​ Alan Kotok,​ Alexander Brudno,​ Donald Knuth y Ronald W. Moore​

El problema de la búsqueda Minimax es que el número de estados a explorar es exponencial al número de movimientos. Partiendo de este hecho, la técnica de poda alfa-beta trata de eliminar partes grandes del árbol, aplicándolo a un árbol Minimax estándar, de forma que se devuelva el mismo movimiento que devolvería este, gracias a que la poda de dichas ramas no influye en la decisión final.

Desarrollo del algoritmo

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)

Ejemplo de poda alfa-beta

La figura muestra un ejemplo de la poda alfa-beta. Cada nivel representa la jugada de los jugadores MAX y MIN, que tendrán que definir un valor α o β respectivamente.

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.

Eficacia de la poda alfa-beta

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 $O(b^{d/2})$ en lugar de los $O(b^{d})$ de Minimax. Esto implica que el factor de ramificación eficaz será de ${\sqrt {b}}$ en lugar de $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 $O(b^{3d/4})$ para un valor moderado de $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 $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.​

Referencias

• Datos: Q570496