Algoritmo di MiniMax
Questa presentazione è un chiaro esempio di come aggiungere i
tagli Alfa-Beta per migliorare l’efficienza dell’algoritmo MiniMax.
La soluzione è stata ottenuta applicando l’algoritmo MiniMax
partendo da sinistra e andando verso destra.
Algoritmo di MiniMax
Nodi AND 
X (a,b)
Massimizzano il valore dei loro successori
Nodi OR  Y (a,b)
Minimizzano il valore dei loro successori
Algoritmo di MiniMax
Ogni nodo è caratterizzato da due soglie:
a e b
I tagli possono essere fatti solo quando
a b
Algoritmo di MiniMax
Visione completa del grafo And-Or.
A
B
E
C
F
G
D
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
7
6
8
5
4
3
0
-2
6
2
5
8
9
2
Algoritmo di MiniMax
L’algoritmo ha inizio assegnando al nodo di partenza
(il nodo radice) i valori a=-e b=
Algoritmo di MiniMax
Il nodo A non è un nodo foglia
 espansione del nodo A.
A
(-,)
Algoritmo di MiniMax
Il nodo B non è un nodo foglia
 espansione del nodo B.
B
(-,)
A
(-,)
Algoritmo di MiniMax
Il nodo E non è un nodo foglia
 espansione del nodo E.
B
E
(-,)
(-,)
A
(-,)
Algoritmo di MiniMax
Il nodo L è un nodo foglia
 valutazione del nodo L.
B
E
L
(-,)
(-,)
A
(-,)
Algoritmo di MiniMax
Il valore del nodo L è ritornato al
nodo padre E che, essendo un nodo
AND, imposterà a come il maggiore A
tra il valore ritornato e il
valore attuale
di a.
B (-,)
E
L
7
(-,)
(-,)
Algoritmo di MiniMax
Nodo E: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di E, lo si genera.
B
E
L
7
(,)
(-,)
A
(-,)
Algoritmo di MiniMax
Il nodo M è un nodo foglia
 valutazione del nodo M.
B
E
L
7
(,)
M
(-,)
A
(-,)
Algoritmo di MiniMax
Il valore del nodo M è ritornato al
nodo padre E che, essendo un nodo
AND, imposterà a come il maggiore A
tra il valore ritornato e il
valore attuale
di a.
B (-,)
E
(,)
L
M
7
6
(-,)
Algoritmo di MiniMax
Nodo E: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di E, lo si genera.
B
E
(,)
L
M
7
6
(-,)
A
(-,)
Algoritmo di MiniMax
Non ci sono più figli da generare
 si ritorna a al nodo padre B che,
essendo un nodo OR, imposterà b
come il minore tra il valore
ritornato e il valore
attuale di b.
B (-,)
E
(,)
L
M
7
6
A
(-,)
Algoritmo di MiniMax
Nodo B: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di B, lo si genera.
B
E
(,)
L
M
7
6
(-,)
A
(-,)
Algoritmo di MiniMax
Il nodo F non è un nodo foglia
 espansione del nodo F.
E
(,)
L
M
7
6
B
(-,)
F
(-,)
A
(-,)
Algoritmo di MiniMax
Il nodo N è un nodo foglia
 valutazione del nodo N.
E
(,)
L
M
7
6
N
B
(-,)
F
(-,)
A
(-,)
Algoritmo di MiniMax
Il valore del nodo N è ritornato al
nodo padre F che, essendo un nodo
AND, imposterà a come il maggiore A
tra il valore ritornato e il
valore attuale
di a.
B (-,)
E
(,)
L
M
N
7
6
8
F
(-,)
(-,)
Algoritmo di MiniMax
Nodo F: si può interrompere la
ricerca (a b)  si ritorna b
al nodo padre B.
E
(,)
L
M
N
7
6
8
B
(-,)
F
(8,)
A
(-,)
Algoritmo di MiniMax
Il nodo B, essendo un nodo OR,
imposterà b come il minore tra
il valore ritornato e il
valore attuale
di b.
E
(,)
L
M
N
7
6
8
B
(-,)
F
(8,)
A
(-,)
Algoritmo di MiniMax
Nodo B: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di B, lo si genera.
E
(,)
L
M
N
7
6
8
B
(-,)
F
(8,)
A
(-,)
Algoritmo di MiniMax
Il nodo G non è un nodo foglia
 espansione del nodo G.
E
(,)
L
M
N
7
6
8
B
(-,)
F
(8,)
G
(-,)
A
(-,)
Algoritmo di MiniMax
Il nodo P è un nodo foglia
 valutazione del nodo P.
E
(,)
L
M
N
7
6
8
B
(-,)
F
(8,)
G
P
A
(-,)
(-,)
Algoritmo di MiniMax
Il valore del nodo P è ritornato al
nodo padre G che, essendo un nodo
AND, imposterà a come il maggiore A
tra il valore ritornato e il
valore attuale
di a.
B (-,)
E
(,)
F
(8,)
G
L
M
N
P
7
6
8
4
(-,)
(-,)
Algoritmo di MiniMax
Nodo G: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di G, lo si genera.
E
(,)
B
(-,)
F
(8,)
G
L
M
N
P
7
6
8
4
(4,)
A
(-,)
Algoritmo di MiniMax
Il nodo Q è un nodo foglia
 valutazione del nodo Q.
E
(,)
B
(-,)
F
(8,)
G
L
M
N
P
7
6
8
4
A
(4,)
Q
(-,)
Algoritmo di MiniMax
Il valore del nodo Q è ritornato al
nodo padre G che, essendo un nodo
AND, imposterà a come il maggiore A
tra il valore ritornato e il
valore attuale
di a.
B (-,)
E
(,)
F
(8,)
G
(4,)
L
M
N
P
Q
7
6
8
4
3
(-,)
Algoritmo di MiniMax
Nodo G: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di G, lo si genera.
E
(,)
B
(-,)
F
(8,)
G
(4,)
L
M
N
P
Q
7
6
8
4
3
A
(-,)
Algoritmo di MiniMax
Non ci sono più figli da generare
 si ritorna a al nodo padre B che,
essendo un nodo OR, imposterà b
come il minore tra il valore
ritornato e il valore
attuale di b.
B (-,)
E
(,)
F
(8,)
G
(4,)
L
M
N
P
Q
7
6
8
4
3
A
(-,)
Algoritmo di MiniMax
Nodo B: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di B, lo si genera.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
L
M
N
P
Q
7
6
8
4
3
A
(-,)
Algoritmo di MiniMax
Non ci sono più figli da generare
 si ritorna b al nodo padre A che,
essendo un nodo AND, imposterà a
come il maggiore tra il valore
ritornato e il valore
attuale di a.
B (-,4)
E
(,)
F
(8,)
G
(4,)
L
M
N
P
Q
7
6
8
4
3
A
(-,)
Algoritmo di MiniMax
Nodo A: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di A, lo si genera.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
L
M
N
P
Q
7
6
8
4
3
A
(4,)
Algoritmo di MiniMax
Il nodo C non è un nodo foglia
 espansione del nodo C.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
L
M
N
P
Q
7
6
8
4
3
A
(4,)
C
(4,)
Algoritmo di MiniMax
Il nodo H non è un nodo foglia
 espansione del nodo H.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
L
M
N
P
Q
7
6
8
4
3
H
A
(4,)
C
(4,)
(4,)
Algoritmo di MiniMax
Il nodo R è un nodo foglia
 valutazione del nodo R.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
L
M
N
P
Q
7
6
8
4
3
H
R
A
(4,)
C
(4,)
(4,)
Algoritmo di MiniMax
Il valore del nodo R è ritornato al
nodo padre H che, essendo un nodo
AND, imposterà a come il maggiore A
tra il valore ritornato e il
valore attuale
di a.
B (-,4)
C
E
(,)
F
(8,)
G
(4,)
H
L
M
N
P
Q
R
7
6
8
4
3
0
(4,)
(4,)
(4,)
Algoritmo di MiniMax
Nodo H: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di H, lo si genera.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
L
M
N
P
Q
R
7
6
8
4
3
0
A
(4,)
C
(4,)
(4,)
Algoritmo di MiniMax
Il nodo S è un nodo foglia
 valutazione del nodo S.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
L
M
N
P
Q
R
7
6
8
4
3
0
A
(4,)
C
(4,)
(4,)
S
Algoritmo di MiniMax
Il valore del nodo S è ritornato al
nodo padre H che, essendo un nodo
AND, imposterà a come il maggiore A
tra il valore ritornato e il
valore attuale
di a.
B (-,4)
C
E
(,)
F
(8,)
G
(4,)
H
(4,)
L
M
N
P
Q
R
S
7
6
8
4
3
0
-2
(4,)
(4,)
Algoritmo di MiniMax
Nodo H: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di H, lo si genera.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,)
(4,)
L
M
N
P
Q
R
S
7
6
8
4
3
0
-2
Algoritmo di MiniMax
Non ci sono più figli da generare
 si ritorna a al nodo padre C che,
essendo un nodo OR, imposterà b
come il minore tra il valore
ritornato e il valore
attuale di b.
B (-,4)
E
(,)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,)
(4,)
L
M
N
P
Q
R
S
7
6
8
4
3
0
-2
Algoritmo di MiniMax
Nodo C: si può interrompere la
ricerca (a b)  si ritorna a al
nodo padre A.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
(4,)
L
M
N
P
Q
R
S
7
6
8
4
3
0
-2
Algoritmo di MiniMax
Il nodo A, essendo un nodo AND,
imposterà a come il minore tra
il valore ritornato e il
valore attuale
di a.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
(4,)
L
M
N
P
Q
R
S
7
6
8
4
3
0
-2
Algoritmo di MiniMax
Nodo A: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di A, lo si genera.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
(4,)
L
M
N
P
Q
R
S
7
6
8
4
3
0
-2
Algoritmo di MiniMax
Il nodo D non è un nodo foglia
 espansione del nodo D.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
(4,)
L
M
N
P
Q
R
S
7
6
8
4
3
0
-2
D
(4,)
Algoritmo di MiniMax
Il nodo J non è un nodo foglia
 espansione del nodo J.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
(4,)
L
M
N
P
Q
R
S
7
6
8
4
3
0
-2
D
J
(4,)
(4,)
Algoritmo di MiniMax
Il nodo V è un nodo foglia
 valutazione del nodo V.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
D
(4,)
L
M
N
P
Q
R
S
7
6
8
4
3
0
-2
J
V
(4,)
(4,)
Algoritmo di MiniMax
Il valore del nodo V è ritornato al
nodo padre J che, essendo un nodo
AND, imposterà a come il maggiore A
tra il valore ritornato e il
valore attuale
di a.
B (-,4)
C
E
(,)
F
(8,)
G
(4,)
H
(4,)
(4,4)
D
(4,)
J
L
M
N
P
Q
R
S
V
7
6
8
4
3
0
-2
5
(4,)
(4,)
Algoritmo di MiniMax
Nodo J: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di J, lo si genera.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
D
(4,)
J
L
M
N
P
Q
R
S
V
7
6
8
4
3
0
-2
5
(,)
(4,)
Algoritmo di MiniMax
Il nodo W è un nodo foglia
 valutazione del nodo W.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
D
(4,)
J
L
M
N
P
Q
R
S
V
7
6
8
4
3
0
-2
5
(,)
W
(4,)
Algoritmo di MiniMax
Il valore del nodo W è ritornato al
nodo padre J che, essendo un nodo
AND, imposterà a come il maggiore A
tra il valore ritornato e il
valore attuale
di a.
B (-,4)
C
E
(,)
F
(8,)
G
(4,)
H
(4,)
(4,4)
D
(4,)
J
(,)
L
M
N
P
Q
R
S
V
W
7
6
8
4
3
0
-2
5
8
(4,)
Algoritmo di MiniMax
Nodo J: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di J, lo si genera.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
D
(4,)
J
(8,)
L
M
N
P
Q
R
S
V
W
7
6
8
4
3
0
-2
5
8
(4,)
Algoritmo di MiniMax
Non ci sono più figli da generare
 si ritorna a al nodo padre D che,
essendo un nodo OR, imposterà b
come il minore tra il valore
ritornato e il valore
attuale di b.
B (-,4)
E
(,)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
D
(4,)
J
(8,)
L
M
N
P
Q
R
S
V
W
7
6
8
4
3
0
-2
5
8
(4,)
Algoritmo di MiniMax
Nodo D: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di D, lo si genera.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
D
(4,)
J
(8,)
L
M
N
P
Q
R
S
V
W
7
6
8
4
3
0
-2
5
8
(4,8)
Algoritmo di MiniMax
Il nodo K non è un nodo foglia
 espansione del nodo K.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
(4,)
J
D
(4,8)
(8,)
K
L
M
N
P
Q
R
S
V
W
7
6
8
4
3
0
-2
5
8
(4,8)
Algoritmo di MiniMax
Il nodo X è un nodo foglia
 valutazione del nodo X.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
(4,)
J
D
(4,8)
(8,)
K
L
M
N
P
Q
R
S
V
W
7
6
8
4
3
0
-2
5
8
X
(4,8)
Algoritmo di MiniMax
Il valore del nodo X è ritornato al
nodo padre K che, essendo un nodo
AND, imposterà a come il maggiore A
tra il valore ritornato e il
valore attuale
di a.
B (-,4)
C
E
(,)
F
(8,)
G
(4,)
H
(4,)
D
(4,8)
(8,)
K
(4,4)
(4,)
J
L
M
N
P
Q
R
S
V
W
X
7
6
8
4
3
0
-2
5
8
9
(4,8)
Algoritmo di MiniMax
Nodo K: si può interrompere la
ricerca (a b)  si ritorna b al
nodo padre D.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
(4,)
J
D
(4,8)
(8,)
K
L
M
N
P
Q
R
S
V
W
X
7
6
8
4
3
0
-2
5
8
9
(9,8)
Algoritmo di MiniMax
Il nodo D, essendo un nodo OR,
imposterà b come il minore tra
il valore ritornato e il
valore attuale
di b.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
(4,)
J
D
(4,8)
(8,)
K
L
M
N
P
Q
R
S
V
W
X
7
6
8
4
3
0
-2
5
8
9
(9,8)
Algoritmo di MiniMax
Nodo D: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di D, lo si genera.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
(4,)
J
D
(4,8)
(8,)
K
L
M
N
P
Q
R
S
V
W
X
7
6
8
4
3
0
-2
5
8
9
(9,8)
Algoritmo di MiniMax
Non ci sono più figli da generare
 si ritorna b al nodo padre A che,
essendo un nodo AND, imposterà a
come il maggiore tra il valore
ritornato e il valore
attuale di a.
B (-,4)
E
(,)
F
(8,)
G
(4,)
H
A
(4,)
C
(4,4)
(4,)
J
D
(4,8)
(8,)
K
L
M
N
P
Q
R
S
V
W
X
7
6
8
4
3
0
-2
5
8
9
(9,8)
Algoritmo di MiniMax
Nodo A: non si può interrompere la
ricerca (a< b)  se esiste un altro
figlio di A, lo si genera.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(8,)
C
(4,4)
(4,)
J
D
(4,8)
(8,)
K
L
M
N
P
Q
R
S
V
W
X
7
6
8
4
3
0
-2
5
8
9
(9,8)
Algoritmo di MiniMax
Non ci sono più figli da generare
 si ritorna a. La procedura ha
termine.
E
(,)
B
(-,4)
F
(8,)
G
(4,)
H
A
(8,)
C
(4,4)
(4,)
J
D
(4,8)
(8,)
K
L
M
N
P
Q
R
S
V
W
X
7
6
8
4
3
0
-2
5
8
9
(9,8)
Algoritmo di MiniMax
Il valore ritornato dalla procedura (8),
indica il nodo finale corrispondente
A
al percorso migliore trovato
nell’albero di ricerca.
E
(,)
B
(-,4)
F
(8,)
C
G
(4,)
H
(8,)
D
(4,8)
(8,)
K
(4,4)
(4,)
J
L
M
N
P
Q
R
S
V
W
X
7
6
8
4
3
0
-2
5
8
9
(9,8)
Algoritmo di MiniMax
Analisi dei risultati:
L’applicazione di questa tecnica ha ridotto il numero dei nodi
analizzati che sono passati da 25, ottenuti con l’applicazione del
solo algoritmo di MiniMax, a 20.
Anche se in questo esempio la riduzione del numero dei nodi
analizzati è stata minima, l’algoritmo risulta molto efficiente nel
caso di ricerca in grafi AND-OR molto più complessi.
E’ da notare che anche l’ordine in cui viene effettuata la ricerca
influisce sull’efficienza dell’algoritmo: in questo caso infatti lo
stesso algoritmo se applicato da destra verso sinistra porta
all’analisi di soli 16 nodi anziché 20.
Algoritmo di MiniMax
Situazione finale nel caso in cui l’albero è espanso da destra a sinistra.
B
(8,8)
G
A
(8,)
C
(8,8)
(8,)
I
(8,)
J
D
(-,8)
(8,)
K
(9,)
P
Q
T
U
V
W
X
Y
4
3
6
2
5
8
9
2