Dipartimento di Ingegneria dell’Informazione
Università degli Studi di Parma
Intelligenza Artificiale
Risoluzione dei Problemi (parte 4)
Agostino Poggi
Stefano Cagnoni
Algoritmi
di Miglioramento Iterativo
 Ci sono dei problemi (es. 8 regine) per cui la descrizione dello stato
contiene tutte le informazioni necessarie per la soluzione
indipendentemente dal percorso che ha condotto a quello stato.
 In questi casi l’idea generale per la soluzione può essere quella di partire
da uno stato iniziale “completo” (es. 8 regine già sulla scacchiera) e poi
modificarlo per raggiungere una soluzione (o una soluzione migliore, se
esiste).
 Questi metodi fanno parte dei cosiddetti algoritmi di ottimizzazione il cui
scopo è massimizzare (minimizzare) il valore di una funzione di
valutazione che misura la bontà (costo) di una soluzione.
 Questo metodo può essere rappresentato come il movimento su una
superficie che rappresenta lo spazio degli stati alla ricerca della vetta più
elevata.
Risoluzione dei Problemi
2
Ricerca in Salita (Hill Climbing)
 L’algoritmo di ricerca in salita è un algoritmo ciclico che, ad ogni passo,
raggiunge una posizione migliore all’interno di un’area di ricerca, se
esiste, seguendo la direzione di massima pendenza.
 Possiamo definire l’algoritmo di ricerca in salita come segue:
function Hill-Climbing(problem) {
current = Make-Node(Initial-State(problem));
while true {
next = ‘a higher valued successor’;
if Value(next) < Value(current)
return current ;
current = next;
}
}
Risoluzione dei Problemi
3
Ricerca in Salita
 Questo algoritmo deve affrontare tre tipi di situazioni che lo
possono “bloccare”.
Nella rappresentazione dello spazio di ricerca come una
superficie, corrispondono al raggiungimento di:
 massimi locali
 pianori
 crinali
 Il metodo per superare questi problemi è fare ripartire la ricerca
da un altro punto scelto a caso
 Questo è ciò che fa una variante dell’algoritmo di ricerca in
salita (Random-restart-hill-climbing).
Risoluzione dei Problemi
4
Ricerca in Salita
 Questa variante ad ogni iterazione mantiene in memoria il risultato
migliore e, periodicamente o al verificarsi di condizioni di “blocco”,
riparte con una nuova iterazione da uno stato scelto in modo random.
Dopo un certo numero fisso di iterazioni o dopo che per un certo numero
di iterazioni questo risultato non viene migliorato, l’algoritmo termina
ritornando il risultato migliore.
 In genere una buona soluzione può essere trovata dopo poche iterazioni.
 Se il problema è NP-completo, la soluzione non può che essere fornita in
un tempo esponenziale poiché, per tale classe di problemi, lo spazio degli
stati ha un numero esponenziale di massimi locali.
Risoluzione dei Problemi
5
Simulated Annealing
 L’algoritmo di simulated annealing ha un comportamento
molto simile all’algoritmo di ricerca in salita.
 La differenza consiste nell’eseguire, ad ogni passo, una mossa
casuale.
 Se la mossa migliora la situazione, allora viene sempre
eseguita, altrimenti viene eseguita con probabilità eE/T dove:
 E è il peggioramento (<0) causato dall’esecuzione della mossa.
 T è un valore che tende a zero con l’aumentare dei cicli e quindi rende
sempre meno probabile l’esecuzione di mosse negative.
Risoluzione dei Problemi
6
Simulated Annealing
 L’algoritmo è così chiamato perché simula l’annealing, cioè il
processo graduale di raffreddamento di una sostanza che passa
dallo stato liquido allo stato solido.
 Se la temperatura viene diminuita abbastanza lentamente,
allora il liquido raggiunge una configurazione a minima
energia.
Risoluzione dei Problemi
7
Simulated Annealing
 Possiamo definire l’algoritmo di simulated annealing come segue:
function Simulated-Annealing(problem) {
current = Make-Node(Initial-State(problem));
for t = 1 to  {
T = schedule[t]; schedule = mappatura tempo/temperatura
if (T = = 0)
return current;
next = ‘a randomly selected successor’;
E = Value(next) - Value(current);
if (E > 0)
current = next;
else ‘current = next with probability eE/T’
}
}
Risoluzione dei Problemi
8
I Giochi
 I giochi sono stati uno dei primi campi in cui è stata applicata
l’IA.
 La presenza di un avversario rende più complicato il problema
della ricerca dato che l’avversario introduce incertezza.
 La caratteristica che spesso li distingue è il grandissimo spazio
di ricerca.
Risoluzione dei Problemi
9
I Giochi
 Un gioco per due persone può essere definito come un
problema di ricerca con le seguenti componenti:
 Lo stato iniziale.
 Gli operatori, le mosse legali.
 Un test di terminazione.
 Una funzione di utilità (utility or payoff function) indicante il risultato
della partita.
Risoluzione dei Problemi
10
Il Gioco del Filetto
Risoluzione dei Problemi
1
2
3
4
5
6
7
8
9
11
Soluzione 1
 Struttura dati
 int Quadro[9]
 dove:
– Quadro[i] = 0 se vuoto
– Quadro[i] = 1 se riempito con X
– Quadro[i] = 2 se riempito con O
 Quadro Mosse[19683]
 Algoritmo
 Si considera il vettore Quadro come se fosse un numero in base 3 e si
converte in decimale.
 Si usa questo numero per accedere ad un elemento del vettore Mosse.
 I valore dell’elemento è il nuovo valore di Quadro.
Risoluzione dei Problemi
12
Soluzione 2
 Strutture dati
 int Quadro[9]
 dove:
– Quadro[i] = 2 se vuoto
– Quadro[i] = 3 se riempito con X
– Quadro[i] = 5 se riempito con O
 int Turno
 Funzioni
 Vai(n)
 Esegue Quadro[n] = 3 se Turno è dispari
 Esegue Quadro[n] = 5 se Turno è pari
 Fai2()
 Ritorna il primo quadro vuoto tra i quadri: 5,2,4,6,8
 Vincente(p)
 Ritorna 0 se il giocatore p non può vincere alla prossima mossa
 Altrimenti ritorna il quadro vincente
Risoluzione dei Problemi
13
Soluzione 2
 Algoritmo
se Turno = 1 allora Vai(1)
se Turno = 2 e Quadro[5] = 2 allora Vai(5) altrimenti Vai(1)
se Turno = 3 e Quadro[9] = 2 allora Vai(9) altrimenti Vai(3)
se Turno = 4 e Vincente(x) > 0 allora Vai(Vincente(x)) altrimenti Vai(Fai2())
se Turno = 5 e Vincente(x) > 0 allora Vai(Vincente(x)) altrimenti
se Vincente(o) > 0 allora Vai(Vincente(o)) altrimenti
se quadro[7] = 2 allora Vai(7) altrimenti Vai(3)
se Turno = 6 e Vincente(o) > 0 allora Vai(Vincente(o)) altrimenti
se Vincente(x) > 0 allora Vai(Vincente(x)) altrimenti Vai(Fai2())
se Turno = 7 e Vincente(x) > 0 allora Vai(Vincente(x)) altrimenti
se Vincente(o) > 0 allora Vai(Vincente(o)) altrimenti Vai(i) tale che Quadro[i] = 2
se Turno = 8 e Vincente(o) > 0 allora Vai(Vincente(o)) altrimenti
se Vincente(x) > 0 allora Vai(Vincente(x)) altrimenti Vai(i) tale che Quadro[i] = 2
se Turno = 9 e Vincente(x) > 0 allora Vai(Vincente(x)) altrimenti
se Vincente(o) > 0 allora Vai(Vincente(o)) altrimenti Vai(i) tale che Quadro[i] = 2
Risoluzione dei Problemi
14
Soluzione 3
 Strutture Dati
 Struct PosizioneQuadro {
int Quadro[9]
PosizioneQuadro ProssimaPosizione[]
int Valore
}
 Algoritmo
 Si generano tutte le configurazioni raggiungibili in una mossa e si sceglie la
migliore:
 Se una configurazione è vincente allora è la migliore.
 Altrimenti si considerano tutte le mosse che l’avversario può compiere da quella
configurazione.
 Si determina la peggiore posizione e si assegna il suo valore alla configurazione che
stiamo considerando.
 La configurazione migliore ha il valore più alto.
Risoluzione dei Problemi
15
Soluzione 1
 Pregi
 Efficiente in termini di tempo.
 Capace di giocare in modo ottimale.
 Difetti




Poco efficiente in termini di spazio.
Occorre molto tempo per definire i valori del vettore Mosse.
Sono probabili errori nell’inserimento dei valori del vettore Mosse.
La soluzione è difficilmente estensibile ad altri giochi.
 Non soddisfa nessun requisito di una buona tecnica di IA.
Risoluzione dei Problemi
16
Soluzione 2
 Pregi
 Efficiente in termini di spazio.
 Capace di giocare in modo ottimale.
 La strategia di gioco è più comprensibile.
 Difetti
 Meno efficiente in termini di tempo.
 La soluzione è difficilmente estensibile ad altri giochi.
 Non soddisfa nessun requisito di una buona tecnica di IA.
Risoluzione dei Problemi
17
Soluzione 3
 Pregi
 Capace di essere efficiente in termini di spazio.
 Capace di giocare in modo ottimale.
 La soluzione è estensibile ad altri giochi.
 Difetti
 Poco efficiente in termini di tempo.
 È un buon esempio di tecnica di IA.
Risoluzione dei Problemi
18
Gli scacchi
 Ad esempio gli scacchi hanno un fattore di ramificazione circa
uguale a 35 e le partite spesso arrivano a 50 mosse per
giocatore.
 Quindi per il gioco degli scacchi abbiamo uno spazio di ricerca
di 35100 (in realtà le posizioni legali sono solo 1040).
 Occorre quindi una funzione di valutazione. Ad esempio, si
potrà dare un peso a ciascun pezzo, ma questo non è
sufficiente.
Risoluzione dei Problemi
19
Funzione di Valutazione
 Una funzione di valutazione in genere si basa sull’importanza
dei pezzi, ma l’importanza di un pezzo non è costante, ma varia
in base alla posizione e alla fase della partita.
 Ad esempio per un cavallo:





Le posizioni centrali pesano di più di quelle agli angoli.
Le posizioni a distanza due da un pezzo nemico pesano di più.
La posizione favorevoli rispetto ai pedoni nemici pesano di più.
La distanza dal re pesa in modo negativo.
Il peso del cavallo diminuisce con l’avanzamento della partita.
Risoluzione dei Problemi
20
Deep Blue
 Il 10/5/1997, a New York, una macchina, Deep Blue, ha battuto in un
match di sei partite (2-1 e tre patte) il campione del mondo Kasparov.
 In particolare, Deep Blue utilizza una macchina parallela general-purpose
a 32 processori più 512 chip specializzati per la generazione di mosse e
valutazione.
 Deep Blue arriva a esplorare alberi profondi 12/14 semimosse (~ 1011
posizioni) in circa 3 minuti.
 Deep Blue consulta anche librerie di aperture (ci sono un centinaio di
aperture ormai completamente esplorate e che possono condizionare tutta
la partita).
Risoluzione dei Problemi
21
L’Algoritmo Minimax
 L’algoritmo Minimax calcola la mossa ottima per il primo
giocatore (Max) supponendo che l’avversario (Min) giochi una
partita perfetta.
 L’algoritmo è composto da 4 passi:
 Genera l’albero completo del gioco.
 Applica la funzione di utilità a tutti gli stati terminali (foglie).
 Partendo dalle foglie assegna ricorsivamente agli stati intermedi:
 Il massimo della funzione di utilità degli stati figli se i figli corrispondono a una
mossa di Max.
 Il minimo della funzione di utilità degli stati figli se i figli corrispondono a una
mossa di Min.
 L’algoritmo termina con l’assegnazione a Max della prima mossa, che
corrisponde al massimo della funzione di utilità al primo livello.
Risoluzione dei Problemi
22
L’Algoritmo Minimax
1
-1
1
1
-1
1
1
Risoluzione dei Problemi
Max
-1
Min
1
1
1
Max
1
-1
Min
23
L’Algoritmo Minimax
 Possiamo definire l’algoritmo Minimax come segue:
function Minimax(game) {
for each op in operator
Value[op] = Minimax-value(apply(op, game), game);
return ‘the op with highest Value’;
}
function Minimax-Value(state, game) {
if Terminal-Test[game](state) return Utility[game](state);
else if ‘Max is to move’
return ‘the highest Minimax-Value of state’s successors’
else return ‘the lowest Minimax-Value of state’s successors’
}
Risoluzione dei Problemi
24
L’Algoritmo Minimax
 L’algoritmo Minimax si basa sull’ipotesi che sia possibile
generare tutti gli stati terminali.
 Questo è di solito impraticabile, anche per giochi non molto
complicati.
 E’ necessario un criterio che faccia generare una mossa
all’algoritmo Minimax senza dover esplorare tutto l’albero di
ricerca.
 Questo si può ottenere introducendo una funzione euristica di
valutazione, che valuterà la bontà anche di stati non terminali, e
un test di terminazione (Cutoff-Test) per decidere a che livello
di mosse terminare la ricerca.
Risoluzione dei Problemi
25
L’Algoritmo Minimax
 La funzione di valutazione dà una stima della bontà della
mossa.
 Ad esempio negli scacchi la stima può essere data in base al
valore dei pezzi in possesso dei due giocatori.
 Il test di terminazione cerca di interrompere la ricerca ad un
livello d tale che sia rispettato il limite di tempo fissato per il
gioco.
 Tuttavia un test di terminazione così semplice può fornire
pessimi risultati se associato a una funzione di valutazione non
molto sofisticata.
Risoluzione dei Problemi
26
L’algoritmo Minimax
 Per superare questi problemi bisogna arrestare la ricerca in
configurazioni quiescenti, cioè in cui le prime mosse
successive (quelle entro l’orizzonte di valutazione) non
cambiano sensibilmente il valore della funzione di valutazione.
 Un problema difficilmente superabile è il problema
dell’orizzonte, cioè la previsione di mosse avversarie di grande
rilevanza che per il limite spaziale dello spazio di ricerca non
sono raggiungibili e quindi sono invisibili all’algoritmo.
Risoluzione dei Problemi
27
Alpha-Beta Pruning
 L’associazione di una buona funzione di valutazione e un buon
test per decidere dove interrompere l’espansione dell’albero di
ricerca può non essere sufficiente a realizzare un programma
Minimax che possa giocare entro limiti temporali accettabili.
 È tuttavia possibile decidere una mossa corretta senza dover
controllare tutti i nodi che l’algoritmo Minimax controlla.
Questo viene fatto usando la tecnica della potatura alpha-beta:
 se un giocatore può muoversi in un nodo n, ma ha una migliore scelta
m in un nodo di livello più elevato nell’albero, allora il nodo n non
sarà mai raggiunto.
Risoluzione dei Problemi
28
Alpha-Beta Pruning
Max
0,8
0,8
0,9
0,8
0,1
0,8
0,7
0,5
0,6
Risoluzione dei Problemi
Min
0,7
0,8
0,1
0,1
0,7
0,8
0,8
Max
0,7
Min
Max
29
Alpha-Beta Pruning
 Possiamo definire l’algoritmo di ricerca alpha-beta con le funzioni MaxValue e Min-Value.
 Max-Value ha la forma:
function Max-Value(state, game, alpha, beta) {
if Cutoff-test(state)
return Eval(state);
for each s in Successor(state) {
alpha = Max(alpha, Min-Value(s, game, alpha, beta));
if (alpha >= beta)
return beta; }
return alpha;
}
 Se si trova un alpha maggiore o uguale a beta si può uscire perché
sicuramente Min potrà eseguire almeno una mossa di valore beta.
Risoluzione dei Problemi
30
Alpha-Beta Pruning
 Min-Value ha la forma:
function Min-Value(state, game, alpha, beta) {
if Cutoff-Test(state)
return Eval(state);
for each s in Successor(state) {
beta = Min(beta, Max-Value(s, game, alpha, beta));
if (beta <= alpha)
return alpha;
}
return beta;
}
 Se si trova un beta minore di alpha si può uscire perché sicuramente Max
potrà eseguire almeno una mossa di valore alpha.
Risoluzione dei Problemi
31
Alpha-Beta Pruning
 L’efficienza della potatura alpha-beta dipende fortemente
dall’ordine in cui i nodi sono esaminati.
 Se i nodi fossero bene ordinati il numero di nodi da esaminare
sarebbe O(bd/2) invece di O(bd).
 Questa riduzione di nodi corrisponde a passare da una
complessità d alla sua radice quadrata. Questo, in giochi simili
agli scacchi, permette ad esempio di esplorare sequenze di
mosse lunghe il doppio.
Risoluzione dei Problemi
32