La procedura del taglio Alfa-Beta
si applica alla valutazione Neg-Max degli alberi da
gioco; in maniera assai semplificata può essere così riassunta:
-
Siano Uno e Due
i giocatori; la mossa tocca a Uno che dispone
di N scelte.
-
Uno valuta la prima mossa assegnandole un punteggio V;
nel valutare il secondo ramo, comunica a Due il
valore trovato V (cambiato di segno).
-
Due inizia a valutare le sue contromosse, cercando la
migliore: non appena trova una mossa che supera -V,
interrompe la valutazione poiché ha scoperto che quel ramo consente a Uno
un punteggio inferiore a V, e dunque Uno NON lo
sceglierà: ogni altra operazione su quel ramo è inutile.
L'ottimizzazione esposta si applica a tutti i livelli
sottostanti, utilizzando due valori di Taglio, detti Alfa e Beta: la riduzione
che si ottiene ha un fattore esponenziale.
La pseudocodifica della subroutine è la seguente:
integer Valutazione
(Tavola, Alfa, Beta)
inizio
integer Punto, Max
determina le possibili mosse M1, M2, . . . .Mn
ordinate in base a una valutazione preliminare
Max = Alfa
i = 1
mentre (i <= n and Max < Beta)
inizio
esegui mossa M1
Punto = - Valutazione (Tavola, -Beta,
-Max)
se Punto > Max allora
Max = Punto
fine
ritorna Max
fine
Da adattare caso per caso,
secondo la valutazione e secondo il gioco.
Bibliografia:
* Knuth e Moore (1975);
* Rich e Knight, Intelligenza artificiale, McGraw Hill;
* Nillson, Metodi per la risoluzione dei problemi nell'I.A., Ed. Franco Angeli.
|