Algoritmul Alpha-beta

Alpha-Beta este o implementare eficientă a algoritmului Minimax.

Tehnica pe care o vom examina, în cele ce urmează, este numită în literatura de specialitate alpha-beta prunning (“alpha-beta retezare”). Atunci când este aplicată unui arbore de tip minimax standard, ea va întoarce aceeaşi mutare pe care ar furniza-o şi Algoritmul Minimax, dar într-un timp mai scurt, întrucât realizează o retezare a unor ramuri ale arborelui care nu pot influenţa decizia finală.

Principiul general al acestei tehnici constă în a considera un nod oarecare n al arborelui, astfel încât jucătorul poate alege să facă o mutare la acel nod. Dacă acelaşi jucător dispune de o alegere mai avantajoasă, m, fie la nivelul nodului părinte al lui n, fie în orice punct de decizie aflat mai sus în arbore, atunci n nu va fi niciodată atins în timpul jocului. Prin urmare, de îndată ce, în urma examinării unora dintre descendenţii nodului n, ajungem să deţinem suficientă informaţie relativ la acesta, îl putem înlătura.

Ideea tehnicii de alpha-beta retezare este aceea de a găsi o mutare “suficient de bună”, nu neapărat cea mai bună, dar suficient de bună pentru a se lua decizia corectă. Această idee poate fi formalizată prin introducerea a două limite, alpha şi beta, reprezentând limitări ale valorii de tip minimax corespunzătoare unui nod intern.

Semnificaţia acestor limite este următoarea: alpha este valoarea minimă pe care este deja garantat că o va obţine MAX, iar beta este valoarea maximă pe care MAX poate spera să o atingă. Din punctul de vedere al jucătorului MIN, beta este valoarea cea mai nefavorabilă pentru MIN pe care acesta o va atinge. Prin urmare, valoarea efectivă care va fi găsită se află între alpha şi beta.

Valoarea alpha, asociată nodurilor de tip MAX, nu poate niciodată să descrească, iar valoarea beta, asociată nodurilor de tip MIN, nu poate niciodată să crească.

Cele două reguli pentru încheierea căutării, bazată pe valori alpha şi beta, pot fi formulate după cum urmează:

• Căutarea poate fi oprită dedesubtul oricărui nod de tip MIN care are o valoare beta mai mică sau egală cu valoarea alpha a oricăruia dintre strămoşii săi de tip MAX.
• Cautarea poate fi oprită dedesubtul oricărui nod de tip MAX care are o valoare alpha mai mare sau egală cu valoarea beta a oricăruia dintre strămoşii săi de tip MIN.

Dacă, referitor la o poziţie, se arată că valoarea corespunzătoare ei se află în afara intervalului alpha-beta, atunci această informaţie este suficientă pentru a şti că poziţia respectivă nu se află de-a lungul variaţiei principale, chiar dacă nu este cunoscută valoarea exactă corespunzătoare ei. Cunoaşterea valorii exacte a unei poziţii este necesară numai atunci când această valoare se află între alpha şi beta.

Din punct de vedere formal, putem defini o valoare de tip minimax a unui nod intern, P, V( P, alpha, beta ), ca fiind “suficient de bună” dacă satisface următoarele cerinţe:

• V( P, alpha, beta ) < alpha, dacă V( P ) < alpha
• V( P, alpha, beta ) = V( P ), dacă alpha ≤ V( P ) ≤ beta
• V( P, alpha, beta ) > beta, dacă V ( P ) > beta, unde prin V( P ) am notat valoarea de tip minimax corespunzătoare unui nod intern.

Valoarea exactă a unui nod-rădăcină P poate fi întotdeauna calculată prin setarea limitelor după cum urmează: V( P, -∞, +∞ ) = V( P ).

Exemplu de arbore de cautare pt alg Alpha-Beta:

Aşa cum se vede în figură, unele dintre valorile de tip minimax ale nodurilor interne sunt aproximative. Totuşi, aceste aproximări sunt suficiente pentru a se determina în mod exact valoarea rădăcinii. Se observă că Algoritmul Alpha-Beta reduce complexitatea căutării de la 8 evaluări statice la numai 5 evaluări de acest tip.

Pași

Începe din poziţia a. 2. Mutare la b. 3. Mutare la d. 4. Alege valoarea maximă a succesorilor lui d, ceea ce conduce la V( d ) = 4. 5. Întoarce-te în nodul b şi execută o mutare de aici la e. 6. Ia în consideraţie primul succesor al lui e a cărui valoare este 5. În acest moment, MAX, a cărui mutare urmează, are garantată, aflându-se în poziţia e, cel puţin valoarea 5, indiferent care ar fi celelalte alternative plecând din e. Această informaţie este suficientă pentru ca MIN să realizeze că, la nodul b, alternativa e este inferioară alternativei d. Această concluzie poate fi trasă fără a cunoaşte valoarea exactă a lui e. Pe această bază, cel de-al doilea succesor al lui e poate fi neglijat, iar nodului e i se poate atribui valoarea aproximativă 5.

Căutarea de tip alpha-beta retează nodurile figurate în mod discontinuu. Ca rezultat, câteva dintre valorile intermediare nu sunt exacte (nodurile c, e), dar aproximările făcute sunt suficiente pentru a determina atât valoarea corespunzătoare rădăcinii, cât şi variaţia principală, în mod exact.

Eficienţa Algoritmului Alpha-Beta depinde de ordinea în care sunt examinaţi succesorii. Este preferabil să fie examinaţi mai întâi succesorii despre care se crede că ar putea fi cei mai buni.

Pseudocod

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if α ≥ β then
                break (* β cut-off *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if α ≥ β then
                break (* α cut-off *)
        return value


(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)