Potatura alfa-beta

Potatura alfa-beta
Potatura alfa-beta. Si può ignorare il sottoalbero destro, perché sappiamo già che ha valore 1 o meno, e quindi non contiene la soluzione migliore
Classe	Algoritmo di ricerca
Caso peggiore temporalmente	$O(b^{d})$
Caso ottimo temporalmente	$O\left({\sqrt {b^{d}}}\right)$

La potatura alfa-beta è un algoritmo di ricerca che può ridurre drasticamente il numero di nodi da valutare nell'albero di ricerca dell'algoritmo minimax. Viene comunemente usata nei programmi di gioco automatico per computer, per giochi a turni a due o più giocatori (Tris, Go, Scacchi ecc.), e consiste nel terminare la valutazione di una possibile mossa non appena viene dimostrato che è comunque peggiore di una già valutata in precedenza: è una ottimizzazione sicura, che non modifica il risultato finale dell'algoritmo a cui viene applicata.

Funzionamento dell'algoritmo

La potatura alfa-beta si basa su due valori, detti appunto alfa e beta che rappresentano, in ogni punto dell'albero, la posizione migliore e peggiore che è possibile raggiungere. Più precisamente, se A è il giocatore massimizzante e B il giocatore minimizzante:

• α è il punteggio minimo che A può raggiungere, a partire dalla posizione in esame; all'inizio dell'algoritmo viene posto a -∞. Durante il calcolo, α coincide con il valore della migliore mossa possibile attualmente calcolata per A.
• β è il punteggio massimo che B può raggiungere a partire dalla stessa posizione; all'inizio dell'algoritmo viene posto a +∞. Durante il calcolo, β coincide con il valore della migliore mossa possibile attualmente calcolata per B.

La ricerca procede come una normale ricerca minimax, in cui però i valori di α e β per ogni nodo vengono aggiornati man mano che la ricerca si approfondisce. Se durante la ricerca, per un dato nodo α diventa maggiore di β, la ricerca al di sotto di quel nodo cessa e il programma passa ad un altro sottoalbero, perché la posizione di quel nodo non può essere raggiunta durante il gioco normale (cioè da quella posizione in poi, A perderebbe inevitabilmente anche se giocasse per vincere, il che in un gioco competitivo è assurdo, e certamente non è il risultato che vogliamo). Si dice che il sottoalbero corrispondente al nodo con α e β "invertiti" viene potato, da cui il nome dell'algoritmo stesso.

Miglioramenti rispetto al semplice minimax

Il beneficio fondamentale della potatura alfa-beta è l'eliminazione di interi rami dell'albero di ricerca; questo permette di limitare la ricerca alle mosse più promettenti, approfondendo ulteriormente la loro valutazione nel tempo dato. Come i suoi predecessori, anche la potatura alfa-beta è un algoritmo di tipo branch and bound.

Dato un fattore di diramazione (medio o costante) b e una profondità di ricerca di d mosse, il numero massimo di mosse valutate (quando l'ordinamento dell'albero è pessimo) è O(b*b*...*b) = O(b^d) – lo stesso di una semplice ricerca minimax. Se invece l'ordinamento è perfetto (le mosse migliori sono sempre valutate per prime), il numero di posizioni ricercate diventa O(b*1*b*1*...*b) per profondità d pari e O(b*1*b*1*...*1) per d dispari, cioè

$O(b^{d/2})=O({\sqrt {b^{d}}})$.

Quindi, nel caso migliore il fattore di diramazione efficace è ridotto alla sua radice quadrata, ovvero la ricerca può raggiungere una profondità doppia con lo stesso numero di calcoli. Il motivo di b*1*b*1*... è che per il giocatore A devono essere valutate tutte le mosse possibili per trovare la migliore, mentre basta conoscere la miglior mossa di B per scartare tutte le mosse di A meno la migliore; il principio alfa-beta garantisce che non è necessario considerare nessun'altra mossa di B. Nel caso degli scacchi, dove il fattore di diramazione è circa 40, e considerando una profondità di ricerca di 12 turni, il rapporto fra caso migliore e caso peggiore è circa 40⁶, cioè una ricerca alfa-beta ottimale per gli scacchi è 4 miliardi di volte più rapida del semplice minimax.

Perciò, poiché il numero di posizioni da valutare diminuisce esponenzialmente col diminuire della profondità, vale la pena compiere sforzi anche grandi per tenere quanto più possibile ordinato l'albero di ricerca: un ordinamento anche solo parziale può migliorare le prestazioni di milioni di volte. Nella pratica quindi, prima della ricerca vera e propria si effettua una prima "pre-ricerca" molto superficiale per ottenere un primo albero già parzialmente ordinato, che la ricerca vera e propria si occuperà di approfondire e completare fino alla profondità stabilita.

Nei programmi di gioco per i computer questa pre-ricerca non è, generalmente, necessaria: viene infatti adottata una procedura di raffinamento successivo, per cui ad ogni nuova mossa il calcolo riparte approfondendo il sottoalbero scelto dal giocatore di turno, già parzialmente ordinato dalle ricerche precedenti

Normalmente, nel corso dell'algoritmo, i sottoalberi sono temporaneamente dominati dal vantaggio di uno dei due giocatori; questo accade tipicamente quando un giocatore può fare molte buone mosse e ad ogni iterazione le prime mosse controllate sono già buone, mentre tutte le mosse dell'altro richiedono una analisi più approfondita per poter essere giudicate). Può anche accadere che questo vantaggio apparente passi spesso dall'uno all'altro giocatore, nel caso l'albero di ricerca del gioco sia poco ordinato.

Miglioramenti euristici

Si possono migliorare le prestazioni senza sacrificare l'accuratezza dei risultati usando euristiche di ordinamento per ricercare subito le parti dell'albero che più probabilmente forzeranno subito dei tagli alfa-beta: per esempio negli scacchi si esaminano per prime le mosse che prendono dei pezzi, o che hanno raggiunto dei punteggi molto alti nella prima ricerca superficiale. Un'altra ottimizzazione euristica molto comune ed economica è l'euristica killer, per cui l'ultima mossa che ha provocato un taglio beta allo stesso livello nell'albero viene sempre ricercata per prima; questa ottimizzazione si può generalizzare in un insieme di tabelle di confutazione.

La ricerca alfa-beta può essere ulteriormente accelerata considerando una finestra di ricerca (la differenza α - β) molto stretta, di solito con un valore ipotizzato in base all'esperienza; questa tecnica è nota come aspiration search. Nel caso estremo, si compie la ricerca con α = β, ottenendo la tecnica nota come zero-window search, null-window search, o scout search. Questa tecnica è particolarmente efficace nei finali di partita, quando si cerca lo scaccomatto. Se una aspiration search fallisce, è immediato sapere se l'intervallo scelto era troppo alto o troppo basso, ottenendo una nuova ipotesi di intervallo alfa-beta per una eventuale nuova ricerca sulla stessa posizione.

Altri algoritmi di ricerca

Sono noti in letteratura algoritmi di ricerca simili più veloci e avanzati, altrettanto capaci di calcolare il valore minimo esatto, come il Negascout e l'MTD-f. Poiché l'algoritmo minimax e le sue varianti sono intrinsecamente a ricerca di profondità, insieme alla potatura alfa-beta viene di solito adottata una strategia ad approfondimento iterativo, che permette alla ricerca di fornire una mossa ragionevolmente buona anche se la ricerca viene interrotta prima del termine. Un altro vantaggio dell'approfondimento iterativo è che permette di ordinare parzialmente l'albero di ricerca, il che permette di potare più in fretta i rami inutili, risparmiando tempo.

D'altra parte esistono anche algoritmi come l'SSS*, che invece analizzano l'albero delle mosse possibili a partire dalle migliori. Questo può renderli computazionalmente più efficienti, ma ha un costo molto pesante in termini di spazio di memoria occupato.

Pseudocodice

Ecco una forma in Pseudocodice dell'algoritmo di potatura alfa-beta. Viene chiamato dalla funzione "minimax" come esempio.

01 FUNZIONE alfa_beta(nodo, profondità, α, β, chi_gioca)
02      SE profondità = 0 O nodo è terminale
03          RESTITUISCI valore euristico del nodo
04      SE chi_gioca = MAX
05          v := -∞
06          PER OGNI figlio del nodo
07              v := max(v, alfa_beta(figlio, profondità - 1, α, β, MIN))
08              α := max(α, v)
09              SE β ≤ α
10                  INTERROMPI IL CICLO (* taglio secondo β *)
11          RESTITUISCI v
12      ALTRIMENTI SE chi_gioca = MIN
13          v := +∞
14          PER OGNI figlio del nodo
15              v := min(v, alfa_beta(figlio, profondità - 1, α, β, MAX))
16              β := min(β, v)
17              SE β ≤ α
18                  INTERROMPI IL CICLO (* taglio secondo α *)
19          RESTITUISCI v

(* richiamo iniziale *)
alfa_beta(origine, profondità, -∞, +∞, MAX)

Voci correlate

• Branch and bound
• Minimax
• Ottimizzazione combinatoria
• Negamax
• Tabella di trasposizione
• MTD(f)
• Negascout
• Euristica killer

Collegamenti esterni

• (EN) http://sern.ucalgary.ca/courses/CPSC/533/W99/presentations/L1_5B_McCullough_Melnyk/
• (EN) http://sern.ucalgary.ca/courses/CPSC/533/W99/presentations/L2_5B_Lima_Neitz/search.html
• (EN) https://web.archive.org/web/20021223103359/http://www.maths.nott.ac.uk/personal/anw/G13GAM/alphabet.html
• (EN) https://web.archive.org/web/20041123061044/http://chess.verhelst.org/search.html
• (EN) http://www.frayn.net/beowulf/index.html Beowulf