|
LaMoSca v0.08L'Alpha-Beta pruning |
ObiettivoIn questa versione del programma, il numero di nodi da analizzare durante la ricerca nell'albero delle mosse è ridotto tramite l'algoritmo "Alpha-Beta pruning". Il codiceL'Alpha-Beta pruning serve per non eseguire la ricerca esaustiva sull'intero albero delle mosse, che cresce esponenzialmente all'aumentare del livello di analisi. Il nome deriva dalle due variabili principali dell'algoritmo, dove Alpha rappresenta il minimo dei valori delle posizioni analizzate, mentre Beta il massimo. Teoricamente Alpha dovrebbe essere aggiornata dai nodi corrispondenti a mosse del programma (detti "Max node"). E' inizializzata a "- Infinito" e rappresenta il valore massimo delle posizioni ottenibili per un certo livello: l'obiettivo è quello di tenere traccia della mossa che porta alla posizione migliore. Beta, invece, dovrebbe essere aggiornata dai nodi corrispondenti a mosse dell'avversario (detti "min node"). E' inizializzata a "+ Infinito" e rappresenta il valore minimo delle posizioni ottenibili per un certo livello: l'obiettivo è quello di tenere traccia della risposta che da al programma il vantaggio minore..
Analogamente a quanto fatto nel passaggio da MiniMax a NegaMax, però, si evita di lavorare in maniera distinta su i nodi Max e Min. In ciascun livello si aggiorna solo la variabile Alpha, usandola per memorizzare il massimo. Nel tornare poi il risultato alla istanza chiamante, questo viene cambiato di segno. In questo modo la massimizzazione di Alpha al livello superiore costituisce, in realtà, la ricerca della posizione meno favorevole per il livello inferiore. In questo modo, se un lato al livello inferiore ha già trovato una posizione con un certo valore, l'avversario al livello superiore proseguirà la ricerca di una mossa che porti ad una situazione meno favorevole di questa. Nella generazione di istanze della funzione a livello inferiore, le variabili Alpha e Beta, oltre che essere cambiate di segno, vengono anche scambiate tra loro. In questo modo, il valore di Alpha del livello chiamante diventa il limite superiore Beta (sempre cambiandolo di segno) del livello chiamato. Infatti, il crescere di Alpha del livello chiamante rappresenta un progressivo abbassamento del limite superiore Beta del livello chiamato: in altre parole, il miglioramento della situazione del livello chiamante si traduce in un peggioramento del massimo raggiungibile per il livello chiamato. D'altra parte, Beta è passato come Alpha (sempre cambiandolo di segno) al livello inferiore. Infatti, Beta rappresenta il risultato migliore dell'avversario e, chiamando il lato avversario, questo scarterà tutte quelle mosse che portano a posizioni peggiori di quella già trovata. Se aggiornando Alpha durante la navigazione nell'albero si arriva ad una condizione nella quale Alpha supera Beta, la ricerca per quel ramo può essere interrotta dato che il livello superiore non giocherà mosse che portano l'avversario su posizioni migliori di quelle che ha già dovuto concedere. Il vantaggio dell'algoritmo è proprio in questa interruzione della ricerca (definita in genere "taglio"). Infatti, è inutile continuare ad analizzare le varianti del livello inferiore quando la mossa che porta a queste varianti non verrà giocata dato che risulta sfavorevole al livello superiore. Un esempio di pseudocodice per la funzione AlphaBeta è il seguente: AlphaBeta(Livello, Alpha, Beta) {
if (Livello == FOGLIA) return Valutazione();
GeneraMosse();
for (tutte le mosse) {
FaiUnaMossa();
Valore = -AlphaBeta(Livello + 1, -Beta, -Alpha);
TornaIndietro();
if (Valore > Alpha)
// questa ?la mossa migliore
Alpha = Valore;
if (Valore >= Beta)
// la mossa ?tanto buona che l'avversario non la lascer?fare
return Beta;
}
}
return Alpha;
}
Arrivati al livello inferiore, corrispondenti a mosse del programma, la scelta dell'algoritmo per il primo gruppo di mosse (trattandosi di "Max node") sarà dato dal loro massimo, pari ad 8. Questo valore rappresenterà il punto di partenza per l'avversario, sperando di trovare una situazione meno favorevole per il programma. Per l'algoritmo, il valore "8" rappresenta il Beta del quale cercare il valore minimo. Per facilità di rappresentazione questo viene riportato al livello superiore con segno invertito permettendo anche a questo livello di procedere con la ricerca del massimo: si procede, cioè, in maniera analoga a quanto visto per l'algoritmo NegaMax. Continuando per le altre sequenze di livello più basso, si ottiene la seguente situazione:
Chiamando per la seconda volta la funzione, il limite massimo accettabile per l'avversario, cioè Beta, non viene superato dai nuovi valori, che raggiungono un massimo Alpha pari a 3. Il nuovo Alpha, essendo inferiore al Beta corrente, sarà la nuova scelta dell'avversario e rappresenterà il nuovo Beta.
Consideriamo ora di risalire fino al primo livello, assegnando alla mossa il valore ottenuto di "1". Questo valore rappresenta il nuovo limite inferiore per il programma, cioè l'Alpha per il livello 1 e 3. In altre parole, nuove mosse possono essere scelte dal programma al livello 1 solo se i valori delle posizioni raggiunte al livello 3 risulteranno migliori di questa, tenendo conto che l'avversario farà le proprie mosse scegliendo mosse che portano alle posizioni meno favorevoli per il programma.
Ci sono due osservazioni generali da fare sul funzionamento dell'algoritmo:
L'esecuzione del programmaAnalizziamo la solita apertura considerando tre livelli di analisi. Il livello 1 e due corrisponderanno a mosse del programma e, quindi, tenderanno a massimizzare il valore della posizione ottenibile, mentre il livello 2 corrisponde a mosse dell'avversario, che tenderà a minimizzare questo valore. Le prime tre chiamate alla funzione Alpha-Beta per la mosse "a2a3", la risposta "b8a6" e l'analisi di tutte le conseguenti posizioni possibili propagheranno verso il basso i valori di Alpha = -infinito e Beta = +infinito: nel programma l'infinito è approssimato con il massimo intero pari a "2147483647" o, in esadecimale, "0x7FFFFFFF". Mosse livello 1 (Alpha=-2147483647, Beta=2147483647): Il valore "8" trovato per il livello 3 rappresenta il massimo valore per le posizioni del programma e sarà visto con segno negativo dal livello 2, corrispondente alle mosse dell'avversario. Richiamando il livello 3, si passerà questo valore come limite superiore per la mossa "b8c6", dato che se tra le posizioni ce ne sarà una migliore per il programma, la "b8c6" non sarà giocata dall'avversario. Mosse livello 3 (Alpha=-2147483647, Beta=8): L3a3a4=-8
L3b2b3=-7 L3b2b4=-5 L3c2c3=-6 L3c2c4=-3 L3d2d3=-1 L3d2d4=3 L3e2e3=-1
L3e2e4=3 L3f2f3=-6 L3f2f4=-3 L3g2g3=-7 L3g2g4=-5 L3h2h3=-8 L3h2h4=-7
L3a1a2=-9 L3b1c3=1 L3g1f3=1 L3g1h3=-4 Questa volta l'analisi delle mosse di livello 3 ha riportato un valore meno svantaggioso per l'avversario (=-3) che quindi preferirà giocare la "b8c6" al posto della "b8a6". Terza chiamata alla funzione per la mossa "g8f6", che ha come risultato: Mosse livello 3 (Alpha=-2147483647, Beta=3): L3a3a4=-8
L3b2b3=-7 L3b2b4=-5 L3c2c3=-6 L3c2c4=-3 L3d2d3=-1 L3d2d4=3 /Cut Questa volta l'analisi di livello 3 trova subito una mossa di valore pari a tre ed interrompe l'ulteriore analisi, dato che si potrebbero trovare valori anche superiori a questo, per cui l'avversario non giocherà la "g8f6". |
DownloadDa completare
Da fare
|
Link |
| Indietro | Indice | Avanti |
Consideriamo,
ad esempio, l'albero su tre livelli riportato in figura. Se consideriamo
le fasi iniziali dell'Alpha-Beta, le prime istanze della funzione saranno
chiamate propagando verso il basso i valori impostati di default
all'infinito per le due variabili.
Questo
nuovo valore di Beta causerà un taglio nella nuova chiamata della
funzione. Infatti, mentre si analizzano i valori delle nuove posizioni, si
trova un valore (il "4") che è maggiore del Beta. Questo vuol
dire che se l'avversario esegue la mossa che porta a queste nuove
posizioni per il programma, quest'ultimo potrebbe avere una posizione
migliore di quelle finora possibili. E' quindi inutile continuare ad
analizzare i valori delle altre posizioni, dato che l'avversario non
eseguirà questa mossa, risparmiando in questo modo tempo di calcolo.