[114] [Circolino] Il Gran Consiglio degli Spammer of Death

[DT84]

Di cosa, dittì? Io ho fisica 2 giovedì mattina

Intelligenza Artificiale... sto dannando la potatura alfa beta.

[Bl@ck]

La potatura alfa-beta è un algoritmo di ricerca che riduce drasticamente il numero di nodi da valutare nell'albero di ricerca dell'algorimo 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 peggiore 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 miglior 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 minore 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(bd) – lo stesso di una semplice ricerca minimax. Se invece l'ordinamento è perfetto (le mosse migliori sono sempre valutate per prime), il numero di posizione ricercate diventa O(b*1*b*1*...*b) per profondità d pari e O(b*1*b*1*...*1) per d dispari, cioè
.
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. [1]. 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 406, 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.

[Ero-Senin]

matematica


inoltre ricordo a tutti che la fisica è una cosa che non esiste, una finizione (sigislove docet)

[ilfuso]

inoltre ricordo a tutti che la fica è una cosa che non esiste, una finizione (sigislove docet)

fix'd

[Bl@ck]

finizione

[Ero-Senin]

fix'd

no dai quella l'ho vista esiste davvero


la visione delle fibra da vicino


e finizione m'è scappato

[ilfuso]

no dai quella l'ho vista esiste davvero


la visione delle fibra da vicino


e finizione m'è scappato

lo so bene che esiste davvero, ma ultimamente ho dei dubbi

[Ero-Senin]

lo so bene che esiste davvero, ma ultimamente ho dei dubbi

vabbè, dopo aver assaggiato l'amaro apprezzerai il miele ancor di più



ah, dannato ottimismo

[Bl@ck]

[ilfuso]

vabbè, dopo aver assaggiato l'amaro apprezzerai il miele ancor di più



ah, dannato ottimismo

son della stessa opinione, ma in questo periodo permettimi di mantenere una media di bestemmie giornaliere superiore alle 600

[Ero-Senin]

son della stessa opinione, ma in questo periodo permettimi di mantenere una media di bestemmie giornaliere superiore alle 600

claro che è consentito in questi momenti

[Alle]

Sabato il destino ha voluto che non andassi a scommettere.. devo ringraziarlo

Però gioco oggi o domani invece

[ilfuso]

che scommetti? :V

[Alle]

che scommetti? :V

Serie A sto guardando oggi

L'altra volta avevo puntato anche su premier e liga

Edit: volevi sapere su quali partite?

[ilfuso]

[Bl@ck]

son della stessa opinione, ma in questo periodo permettimi di mantenere una media di bestemmie giornaliere superiore alle 600

io non posso :( a lavoro poi mi rompono, quindi mi limito solo alla sera e devo dire che riesco a mantenere una buona media

[Alle]

Mah adesso sto guardano un po' in generale.. vedendo su quali puntare

Ad esempio mi ispirano:

Catania - Inter
Sampdoria - Lazio
Cagliari - Siena

Poi vedrò come puntare e se puntare anche su altre

[Bl@ck]

ma io scommetterei su CAMPIONI DEL MONDO!!

[Alle]

Ottima idea

[ilfuso]

ma io scommetterei su CAMPIONI DEL MONDO!!

[Stanislao]

po po poo

[DT84]

ma io scommetterei su CAMPIONI DEL MONDO!!

[Ero-Senin]

buon giorno gente

[Bl@ck]

ossssssssssssssssssssss

sto forum fa cahare!

[Ero-Senin]

'giorno