Poda alfa-beta

Erro al crear miniatura:

Eixemple de poda alfa-beta.

La poda alfa beta és una tècnica de busca que reduïx el número de nodos evaluats en un arbre de joc pel algoritme Minimax. Es tracta d'una tècnica molt utilisada en programes de jocs entre adversaris com l'escacs, el tres en ralla o el Go.

Entre els pioners en l'us d'esta tècnica trobem a Arthur Samuel, D.J Edwards i T.P. Hart, Alan Kotok, Alexander Brudno, Donald Knuth i Ronald W. Moore

El problema de la busca Minimax és que el número d'estats a explorar és exponencial al número de moviments. Partint d'este fet, la tècnica de poda alfa-beta tracta d'eliminar parts grans de l'arbre, aplicant-ho a un arbre Minimax estàndart, de manera que es torne el mateix moviment que tornaria est, gràcies a que la poda de dites branques no influïx en la decisió final.

Desenroll de l'algoritme

La busca minimax és primer en profunditat, per això en qualsevol moment només es deuen considerar els nodos a lo llarc d'un camí en l'arbre.

La poda alfa-beta pren dit nom de l'utilisació de dos paràmetros que descriuen els llímits sobre els valors cap a arrere que apareixen a lo llarc de cada camí.

• α és el valor de la millor opció fins al moment a lo llarc del camí per a MAX, açò implicarà per lo tant l'elecció del valor més alt
• β és el valor de la millor opció fins al moment a lo llarc del camí per a MIN, açò implicarà per lo tant l'elecció del valor més baix.

Esta busca alfa-beta va actualisant el valor dels paràmetros segons es recorre l'arbre. El método realisarà la poda de les branques restants quan el valor actual que s'està examinant siga pijor que el valor actual de α o β per a MAX o MIN, respectivament.

El desenroll de l'algoritme en pseudocódigo serà el següent:

funció alfa-beta(nodo //en el nostre cas el tauler, profunditat, α, β, jugador)
    si nodo és un nodo terminal o profunditat = 0
        tornar el valor heurístic del nodo
    si jugador1
        per a cada fill de nodo
            α := max(α, alfa-beta(fill, profunditat-1, α, β, jugador2))
            si β≤α
                trencar (* poda β *)
        tornar α
    si no
        per a cada fill de nodo
            β := min(β, alfa-beta(fill, profunditat-1, α, β, jugador1))
            si β≤α
                trencar (* poda α *)
        tornar β

(* Cridada inicial *)
alfa-beta(orige, profunditat, -infinit, +infinit, jugador_desijat)

Eixemple de poda alfa-beta

Erro al crear miniatura:

La figura mostra un eixemple de la poda alfa-beta. Cada nivell representa la jugada dels jugadors MAX i MIN, que tindran que definir un valor α o β respectivament.

A continuació es presenta un eixemple d'aplicació de l'algoritme per a l'arbre de la figura. En ella els nodos podats en aplicar l'algoritme es presenten sombrejats en gris.

Comencem primer en la busca en profunditat. El pare dels nodos full més a l'esquerra, etiquetats en 5 i 6 respectivament, deurà triar un valor β en tractar-se d'un nivell MIN, açò implica que deurà triar el valor mínim entre dits nodos, és dir 5.

Seguint el desenroll, s'expandiran el restant de successors del pare. En este cas s'expandix el camí que conduïx als nodos full 7 i, buscant un valor β menor, el nodo etiquetat en 4. En este moment el valor momentàneu de β en eixe nivell és 4 (el mínim entre 7 i 4). Açò implica que en este moment en el nivell superior, el pare del nodo que etiquetem anteriorment en β igual a 5, i d'este β igual a 4 momentàneu, deu decidir el millor valor, (el més alt en trobar-se en un nivell MAX), si seguírem expandint fills del nodo MIN pare de 7 i 4, només podríem conseguir valors menors a 4, lo que seguiria implicant una elecció de la jugada esquerra en el nivell MAX, per lo tant, podem podar el restant de fills, tal i com es mostra en la figura.

El restant del desenroll de l'arbre se seguiria utilisant els criteris mencionats en anterioritat.

Eficàcia de la poda alfa-beta

L'eficàcia de la poda alfa-beta depén de l'orde en el que s'examinen els successors, és dir, l'algoritme es comportarà de forma més eficient si examinem primer els successors que provablement seran els millors.

Si açò poguera fer-se, implicaria que alfa-beta només tindria que examinar $O(b^{d/2})$ en lloc dels $O(b^d)$ de Minimax. Açò implica que el factor de ramificació eficaç serà de $\sqrt{b}$ en lloc de $b$. En atres paraules, alfa-beta podria mirar cap a davant aproximadament dos voltes més que Minimax en la mateixa cantitat de temps.

Si es recorre a una ordenació aleatòria en lloc de primer el millor en els successors, el número aproximat de nodos examinats seria de $O(b^{3d/4})$ per a un valor moderat de $b$. En escacs es pot realisar una funció d'ordenació senzilla tenint en conte primer captures de fiches, despuix amenaces, moviments cap a davant i per últim moviments cap a darrere, açò conseguiria aproximadament un factor de dos del resultat $O(b^{d/2})$ del millor cas. L'inclusió d'esquemes dinàmics per a ordenar moviments, basats en experiència podrien acostar-se al llímit teòric.