Algoritmo di MiniMax Questa presentazione è un chiaro esempio di come aggiungere i tagli Alfa-Beta...

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.

XNodi AND

Nodi OR Y

Massimizzano il valore dei loro successori

Minimizzano il valore dei loro successori


Ogni nodo è caratterizzato da due soglie:

e

I tagli possono essere fatti solo quando



A

N O

CB

L M P Q R S T U V W X Y

D

Visione completa del grafo And-Or.

E KJIHGF

7 6 8 5 4 3 0 -2 6 2 5 8 9 2


L’algoritmo ha inizio assegnando al nodo di partenza (il nodo radice) i valori e


A

Il nodo A non è un nodo foglia espansione del nodo A.


B

Il nodo B non è un nodo foglia espansione del nodo B.

A


B

Il nodo E non è un nodo foglia espansione del nodo E.

A

E


B

Il nodo L è un nodo foglia valutazione del nodo L.

A

E

L


B

Il valore del nodo L è ritornato alnodo padre E che, essendo un nodoAND, imposterà come il maggioretra il valore ritornato e ilvalore attualedi .

A

E

L

7


B

A

E

L

7

Nodo E: non si può interrompere la ricerca (< ) se esiste un altro figlio di E, lo si genera.


B

A

E

L

7

Il nodo M è un nodo foglia valutazione del nodo M.

M


B

A

E

L

7 6

Il valore del nodo M è ritornato alnodo padre E che, essendo un nodoAND, imposterà come il maggioretra il valore ritornato e ilvalore attualedi .

M


B

A

E

L

7 6

Nodo E: non si può interrompere la ricerca (< ) se esiste un altro figlio di E, lo si genera.

M


B

A

E

L

7 6

Non ci sono più figli da generare si ritorna al nodo padre B che,essendo un nodo OR, imposterà come il minore tra il valore ritornato e il valore attuale di .

M


B

A

E

L

7 6

Nodo B: non si può interrompere la ricerca (< ) se esiste un altro figlio di B, lo si genera.

M


B

A

E

L

7 6

Il nodo F non è un nodo foglia espansione del nodo F.

M

F


B

A

E

L

7 6

Il nodo N è un nodo foglia valutazione del nodo N.

M

F

N


B

A

E

L

7 6 8

Il valore del nodo N è ritornato alnodo padre F che, essendo un nodoAND, imposterà come il maggioretra il valore ritornato e ilvalore attualedi .

M

F

N


B

A

E

L

7 6 8

Nodo F: si può interrompere la ricerca ( ) si ritorna al nodo padre B.

M

F

N


B

A

E

L

7 6 8

Il nodo B, essendo un nodo OR, imposterà come il minore tra il valore ritornato e il valore attuale di .

M

F

N


B

A

E

L

7 6 8


M

F

N


B

A

E

L

7 6 8

Il nodo G non è un nodo foglia espansione del nodo G.

M

F

N

G


B

A

E

L

7 6 8

Il nodo P è un nodo foglia valutazione del nodo P.

M

F

N

G

P


B

A

E

L

7 6 8 4

Il valore del nodo P è ritornato alnodo padre G che, essendo un nodoAND, imposterà come il maggioretra il valore ritornato e ilvalore attualedi .

M

F

N

G

P


B

A

E

L

7 6 8 4

Nodo G: non si può interrompere la ricerca (< ) se esiste un altro figlio di G, lo si genera.

M

F

N

G

P


B

A

E

L

7 6 8 4

Il nodo Q è un nodo foglia valutazione del nodo Q.

M

F

N

G

P Q


B

A

E

L

7 6 8 4 3

Il valore del nodo Q è ritornato alnodo padre G che, essendo un nodoAND, imposterà come il maggioretra il valore ritornato e ilvalore attualedi .

M

F

N

G

P Q


B

A

E

L

7 6 8 4 3

M

F

N

G

P Q

Nodo G: non si può interrompere la ricerca (< ) se esiste un altro figlio di G, lo si genera.


B

A

E

L

7 6 8 4 3

Non ci sono più figli da generare si ritorna al nodo padre B che,essendo un nodo OR, imposterà come il minore tra il valore ritornato e il valore attuale di .

M

F

N

G

P Q


B

A

E

L

7 6 8 4 3


M

F

N

G

P Q


B

A

E

L

7 6 8 4 3

Non ci sono più figli da generare si ritorna al nodo padre A che,essendo un nodo AND, imposterà come il maggiore tra il valore ritornato e il valore attuale di .

M

F

N

G

P Q


B

A

E

L

7 6 8 4 3

Nodo A: non si può interrompere la ricerca (< ) se esiste un altro figlio di A, lo si genera.

M

F

N

G

P Q


B

A

E

L

7 6 8 4 3

Il nodo C non è un nodo foglia espansione del nodo C.

M

F

N

G

P Q

C


B

A

E

L

7 6 8 4 3

Il nodo H non è un nodo foglia espansione del nodo H.

M

F

N

G

P Q

C

H


B

A

E

L

7 6 8 4 3

Il nodo R è un nodo foglia valutazione del nodo R.

M

F

N

G

P Q

C

H

R


B

A

E

L

7 6 8 4 3 0

Il valore del nodo R è ritornato alnodo padre H che, essendo un nodoAND, imposterà come il maggioretra il valore ritornato e ilvalore attualedi .

M

F

N

G

P Q

C

H

R


B

A

E

L

7 6 8 4 3 0

Nodo H: non si può interrompere la ricerca (< ) se esiste un altro figlio di H, lo si genera.

M

F

N

G

P Q

C

H

R


B

A

E

L

7 6 8 4 3 0

Il nodo S è un nodo foglia valutazione del nodo S.

M

F

N

G

P Q

C

H

R S


B

A

E

L

7 6 8 4 3 0 -2

Il valore del nodo S è ritornato alnodo padre H che, essendo un nodoAND, imposterà come il maggioretra il valore ritornato e ilvalore attualedi .

M

F

N

G

P Q

C

H

R S


B

A

E

L

7 6 8 4 3 0 -2

Nodo H: non si può interrompere la ricerca (< ) se esiste un altro figlio di H, lo si genera.

M

F

N

G

P Q

C

H

R S


B

A

E

L

7 6 8 4 3 0 -2

Non ci sono più figli da generare si ritorna al nodo padre C che,essendo un nodo OR, imposterà come il minore tra il valore ritornato e il valore attuale di .

M

F

N

G

P Q

C

H

R S


B

A

E

L

7 6 8 4 3 0 -2

Nodo C: si può interrompere la ricerca ( ) si ritorna alnodo padre A.

M

F

N

G

P Q

C

H

R S


B

A

E

L

7 6 8 4 3 0 -2

Il nodo A, essendo un nodo AND, imposterà come il minore tra il valore ritornato e il valore attuale di .

M

F

N

G

P Q

C

H

R S


B

A

E

L

7 6 8 4 3 0 -2


M

F

N

G

P Q

C

H

R S


B

A

E

L

7 6 8 4 3 0 -2

Il nodo D non è un nodo foglia espansione del nodo D.

M

F

N

G

P Q

C

H

R S

D


B

A

E

L

7 6 8 4 3 0 -2

Il nodo J non è un nodo foglia espansione del nodo J.

M

F

N

G

P Q

C

H

R S

D

J


B

A

E

L

7 6 8 4 3 0 -2

Il nodo V è un nodo foglia valutazione del nodo V.

M

F

N

G

P Q

C

H

R S

D

J

V


B

A

E

L

7 6 8 4 3 0 -2 5

Il valore del nodo V è ritornato alnodo padre J che, essendo un nodoAND, imposterà come il maggioretra il valore ritornato e ilvalore attualedi .

M

F

N

G

P Q

C

H

R S

D

J

V


B

A

E

L

7 6 8 4 3 0 -2 5

Nodo J: non si può interrompere la ricerca (< ) se esiste un altro figlio di J, lo si genera.

M

F

N

G

P Q

C

H

R S

D

J

V


B

A

E

L

7 6 8 4 3 0 -2 5

Il nodo W è un nodo foglia valutazione del nodo W.

M

F

N

G

P Q

C

H

R S

D

J

V W


B

A

E

L

7 6 8 4 3 0 -2 5 8

Il valore del nodo W è ritornato alnodo padre J che, essendo un nodoAND, imposterà come il maggioretra il valore ritornato e ilvalore attualedi .

M

F

N

G

P Q

C

H

R S

D

J

V W


B

A

E

L

7 6 8 4 3 0 -2 5 8

Nodo J: non si può interrompere la ricerca (< ) se esiste un altro figlio di J, lo si genera.

M

F

N

G

P Q

C

H

R S

D

J

V W


B

A

E

L

7 6 8 4 3 0 -2 5 8

Non ci sono più figli da generare si ritorna al nodo padre D che,essendo un nodo OR, imposterà come il minore tra il valore ritornato e il valore attuale di .

M

F

N

G

P Q

C

H

R S

D

J

V W


B

A

E

L

7 6 8 4 3 0 -2 5 8

Nodo D: non si può interrompere la ricerca (< ) se esiste un altro figlio di D, lo si genera.

M

F

N

G

P Q

C

H

R S

D

J

V W


B

A

E

L

7 6 8 4 3 0 -2 5 8

Il nodo K non è un nodo foglia espansione del nodo K.

M

F

N

G

P Q

C

H

R S

D

J

V W

K


B

A

E

L

7 6 8 4 3 0 -2 5 8

Il nodo X è un nodo foglia valutazione del nodo X.

M

F

N

G

P Q

C

H

R S

D

J

V W

K

X


B

A

E

L

7 6 8 4 3 0 -2 5 8 9

Il valore del nodo X è ritornato alnodo padre K che, essendo un nodoAND, imposterà come il maggioretra il valore ritornato e ilvalore attualedi .

M

F

N

G

P Q

C

H

R S

D

J

V W

K

X


B

A

E

L

7 6 8 4 3 0 -2 5 8 9

Nodo K: si può interrompere la ricerca ( ) si ritorna alnodo padre D.

M

F

N

G

P Q

C

H

R S

D

J

V W

K

X


B

A

E

L

7 6 8 4 3 0 -2 5 8 9

Il nodo D, essendo un nodo OR, imposterà come il minore tra il valore ritornato e il valore attuale di .

M

F

N

G

P Q

C

H

R S

D

J

V W

K

X


B

A

E

L

7 6 8 4 3 0 -2 5 8 9

Nodo D: non si può interrompere la ricerca (< ) se esiste un altro figlio di D, lo si genera.

M

F

N

G

P Q

C

H

R S

D

J

V W

K

X


B

A

E

L

7 6 8 4 3 0 -2 5 8 9

Non ci sono più figli da generare si ritorna al nodo padre A che,essendo un nodo AND, imposterà come il maggiore tra il valore ritornato e il valore attuale di .

M

F

N

G

P Q

C

H

R S

D

J

V W

K

X


B

A

E

L

7 6 8 4 3 0 -2 5 8 9


M

F

N

G

P Q

C

H

R S

D

J

V W

K

X


B

A

E

L

7 6 8 4 3 0 -2 5 8 9

Non ci sono più figli da generare si ritorna . La procedura hatermine.

M

F

N

G

P Q

C

H

R S

D

J

V W

K

X


B

A

E

L

7 6 8 4 3 0 -2 5 8 9

Il valore ritornato dalla procedura (8),indica il nodo finale corrispondente al percorso migliore trovatonell’albero di ricerca.

M

F

N

G

P Q

C

H

R S

D

J

V W

K

X


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.


A

CB

P Q T U V W X Y

D

KJIG

4 3 6 2 5 8 9 2

Situazione finale nel caso in cui l’albero è espanso da destra a sinistra.

Algoritmo di MiniMax Questa presentazione è un chiaro esempio di come aggiungere i tagli Alfa-Beta...

Documents

Transcript of Algoritmo di MiniMax Questa presentazione è un chiaro esempio di come aggiungere i tagli Alfa-Beta...