Inteligenta Artificiala

55
Inteligenta Inteligenta Artificiala Artificiala Universitatea Politehnica Bucuresti Anul universitar 2008-2009 Adina Magda Florea http:// turing . cs .pub. ro / ia _08 si curs.cs.pub.ro

description

Inteligenta Artificiala. Universitatea Politehnica Bucuresti Anul universitar 2008-2009 Adina Magda Florea http://turing.cs.pub.ro/ia_08 si curs.cs.pub.ro. Curs nr. 3. Strategii de rezolvare a problemelor Problema satisfacerii restrictiilor Strategii de cautare in jocuri. - PowerPoint PPT Presentation

Transcript of Inteligenta Artificiala

Page 1: Inteligenta Artificiala

Inteligenta ArtificialaInteligenta Artificiala

Universitatea Politehnica BucurestiAnul universitar 2008-2009

Adina Magda Floreahttp://turing.cs.pub.ro/ia_08 si

curs.cs.pub.ro

Page 2: Inteligenta Artificiala

Curs nr. 3

Strategii de rezolvare a problemelor Problema satisfacerii restrictiilor Strategii de cautare in jocuri

Page 3: Inteligenta Artificiala

1. Problema satisfacerii restrictiilor

Gradul unei variabile Aritatea unei restrictii Gradul problemei Aritatea problemei

{X ,...,X }1 n

{D ,...,D }1 n

{R R }1,..., k

R D ... Dj i1 i j X ,...,Xi1 i j

{(X ,x ),...,(X ,x )}1 j1 n jn

Page 4: Inteligenta Artificiala

2.1 Instante ale CSP

Determinarea unei solutii sau a tuturor solutiilor

CSP totala CSP partiala CSP binara – graf de restrictiiCSP – problema de cautare, in NP Sub-clase de probleme cu timp polinomial Reducerea timpului (reducerea sp. de

cautare)

Page 5: Inteligenta Artificiala

Algoritm: Backtracking nerecursiv

1. Initializeaza FRONTiERA cu {Si} /* Si este starea initiala */2. daca FRONTIERA = { }

atunci intoarce INSUCCES /* nu exista solutie /*3. Fie S prima stare din FRONTIERA4. daca toate starile succesoare ale lui S au fost deja generate

atunci4.1. Elimina S din FRONTIERA4.2. repeta de la 2

5. altfel5.1. Genereaza S', noua stare succesoare a lui S5.2. Introduce S' la începutul listei FRONTIERA 5.3. Stabileste legatura S’ S5.4. Marcheaza în S faptul ca starea succesoare S' a fost generata5.5. daca S' este stare finala

atunci5.5.1. Afiseaza calea spre solutie urmarind legaturile S’ S ..5.5.2. întoarce SUCCES /* s-a gasit o solutie */

5.6. repeta de la 2sfarsit.

Page 6: Inteligenta Artificiala

2.2 Notatii

X1, …, XN variabilele problemei, N fiind numarul de variabile ale problemei,

U - intreg care reprezinta indicele variabilei curent selectate pentru a i se atribui o valoare

F - vector indexat dupa indicii variabilelor, in care sunt memorate selectiile de valori facute de la prima variabila si pana la variabila curenta

contrar cazin fals

DDR

])F[U],(F[UR restrictia exista dacaadevarat

=])F[U,U],F[U,(U Relatie2121

21

UU UU

21 UU

2211

Page 7: Inteligenta Artificiala

Algoritm: Backtracking recursiv

BKT (U, F)

pentru fiecare valoare V a lui XU executa1. F[U] V2. daca Verifica (U,F) = adevarat

atunci2.1. daca U < N

atunci BKT(U+1, F) 2.2. altfel

2.2.1. Afiseaza valorile din vectorul F/* F reprezinta solutia

problemei */2.2.2. intrerupe ciclul

sfarsit.

Page 8: Inteligenta Artificiala

Verifica (U,F)

1. test adevarat

2. I U - 1

3. cat timp I > 0 executa

3.1. test Relatie(I, F[I], U, F[U])

3.2. I I - 1

3.3. daca test = fals

atunci intrerupe ciclul

4. intoarce test

sfarsit.

Page 9: Inteligenta Artificiala

2.3 Imbunatatirea performantelor BKT Algoritmi de imbunatatire a consistentei reprezentarii

Consistenta locala a arcelor sau a cailor in graful de restrictii

Algoritmi hibrizi Imbunatatesc performantele rezolvarii prin reducerea numarului

de teste. Tehnici prospective:

- Algoritmul de cautare cu predictie completa- Algoritmul de cautare cu predictie partiala- Algoritmul de cautare cu verificare predictiva

Tehnici retrospective:- Algoritmul de backtracking cu salt- Algoritmul de backtracking cu marcare- Algoritmul de backtracking cu multime conflictuala

Utilizarea euristicilor

Page 10: Inteligenta Artificiala

Algoritmi de imbunatatire a consistentei reprezentarii

Propagarea restrictiilor

X

X XR = {(a,b)}1 2

3

12

R = {(a,c)}13

X

X XR = {(a,b),(b,c)}1 2

3

12

R = {(a,c),(c,b)}13 R = {b,c)}

23

(a) (b)

D = D = D = {a,b,c}X X X1 2 3

Page 11: Inteligenta Artificiala

2.4 Propagarea locala a restrictiilor

Combinatia de valori x si y pentru variabilele Xi si Xj este permisa de restrictia explicita Rij(x,y).

Un arc (Xi, Xj) intr-un graf de restrictii orientat se numeste arc-consistent daca si numai daca pentru orice valoare x Di, domeniul variabilei Xi, exista o valoare y Dj, domeniul variabilei Xj, astfel incat Rij(x,y).

Graf de restrictii orientat arc-consistent

Page 12: Inteligenta Artificiala

Algoritm: AC-3: Realizarea arc-consistentei pentru un graf de restrictii.

1. Creeaza o coada Q { (Xi, Xj) | (Xi, Xj) Multime arce, ij}

2. cat timp Q nu este vida executa

2.1. Elimina din Q un arc (Xk, Xm)

2.2. Verifica(Xk, Xm)

2.3. daca subprogramul Verifica a facut schimbari in domeniul variabilei Xk

atunci

Q Q { (Xi, Xk) | (Xi, Xk)Multime arce, ik,m}

sfarsit.

Verifica (Xk, Xm)

pentru fiecare x Dk executa

1. daca nu exista nici o valoare y Dm astfel incat Rkm(x,y)

atunci elimina x din Dk

sfarsit.

Page 13: Inteligenta Artificiala

Cale-consistenta

O cale de lungime m prin nodurile i0,…,im ale unui graf de restrictii orientat se numeste m-cale-consistenta daca si numai daca pentru orice valoare x Di0, domeniul variabilei i0 si o valoare y Djm, domeniul variabilei im, pentru care Ri0im(x,y), exista o secventa de valori z1 Di1 … zm-1 Dim-1 astfel incat Ri0i1(x,z1), …, Rim-1im(zm-1,y)

Graf de restrictii orientat m-arc-consistent Graf minim de restrictii n-cale-consistenta Comentarii

Page 14: Inteligenta Artificiala

Complexitate N - numarul de variabile a - cardinalitatea maxima a domeniilor de valori ale

variabilelor e - numarul de restrictii. Algoritmului de realizare a arc-consistentei - AC-3:

complexitate timp este O(e*a3); complexitate spatiu: O(e+N*a)

S-a gasit si un algoritm de complexitate timp O(e*a2) – AC-4

Algoritmul de realizare a 2-cale-consistentei - PC-4: complexitatea timp O(N3*a3)

Page 15: Inteligenta Artificiala

2.5 CSP fara bkt - conditii

Graf de restrictii ordonat Latimea unui nod Latimea unei ordonari a nodurilor Latimea unui graf de restrictii

A C

B

RAC

RCB

A

A

A

B B

BC

C

C

Page 16: Inteligenta Artificiala

Teoreme

Daca un graf de restrictii arc-consistent are latimea egala cu unu (i.e. este un arbore), atunci problema asociata grafului admite o solutie fara backtracking.

Daca un graf de restrictii 2-cale-consistent are latimea egala cu doi, atunci problema asociata grafului admite o solutie fara backtracking.

Page 17: Inteligenta Artificiala

d-consistenta

Fiind data o ordonare d a variabilelor unui graf de restrictii R, graful R este d-arc-consistent daca toate arcele avand directia d sint arc-consistente.

Fie un graf de restrictii R, avind ordonarea variabilelor d cu latimea egala cu unu. Daca R este d-arc-consistent atunci cautarea dupa directia d este fara backtracking.

Page 18: Inteligenta Artificiala

d-consistenta

Algoritm: Realizarea d-arc-consistentei unui graf de restrictii cu ordonarea variabilelor (X1,…,XN)

pentru I N la 1 executa

1. pentru fiecare arc (Xj, Xi) cu j < i executa

1.1. Verifica(Xj, Xi)

sfarsit.

Complexitatea timp: O(e*a2)

Page 19: Inteligenta Artificiala

2.6 Tehnici prospective

Conventii Notatii: U, N, F (F[U]), T (T[U] … XU), TNOU, LINIE_VIDA

Verifica_Inainte Verifica_Viitoare

Predictie completa Predictie partiala Verificare predictiva

contrar cazîn fals

)L,(LR dacaadevarat=L2)U2,L1,,Relatie(U1 21 UU 21

Page 20: Inteligenta Artificiala

Algoritm: Backtracking cu predictie completa

Predictie(U, F, T)pentru fiecare element L din T[U] executa 1. F[U] L 2. daca U < N atunci //verifica consistenta atribuirii

2.1 TNOU Verifica_Inainte (U, F[U], T)2.2 daca TNOU LINIE_VIDA atunci TNOU Verifica _Viitoare (U, TNOU)2.3 daca TNOU LINIE_VIDA atunci Predictie (U+1, F, TNOU)

3. altfel afiseaza atribuirile din Fsfarsit

Page 21: Inteligenta Artificiala

Verifica_Inainte (U, L, T)

1. TNOU tabela vida

2. pentru U2 U+1 pana la N executa

2.1 pentru fiecare element L2 din T[U2] executa

2.1.1 daca Relatie(U, L, U2, L2) = adevarat

atunci introduce L2 in TNOU[U2]

2.2 daca TNOU[U2] este vida

atunci intoarce LINIE_VIDA

3. intoarce TNOU

sfarsit

Page 22: Inteligenta Artificiala

Verifica_Viitoare (U, TNOU)daca U+1 < N atunci1. pentru U1 U+1 pana la N executa

1.1 pentru fiecare element L1 din TNOU[U1] executa1.1.1 pentru U2 U+1 pana la N, U2U1 executa

i. pentru fiecare element L2 din TNOU[U2] executa

- daca Relatie (U1, L1, U2, L2) = adevarat atunci intrerupe ciclul //dupa L2

ii. daca nu s-a gasit o valoare consistenta pentru U2 atunci

- elimina L1 din TNOU[U1]- intrerupe ciclul // dupa U2

1.2 daca TNOU[U1] este vida atunci intoarce LINIE_VIDA

2. intoarce TNOUsfarsit

Page 23: Inteligenta Artificiala

BKT cu predictie partiala Se modifica Verifica_Viitoare pasii marcati cu rosu

Verifica_Viitoare (U, TNOU)daca U+1 < N atunci1. pentru U1 U+1 pana la N - 1 executa

1.1 pentru fiecare element L1 din TNOU[U1] executa1.1.1 pentru U2 U1+1 pana la N executa

i. pentru fiecare element L2 din TNOU[U2] executa- daca Relatie (U1, L1, U2, L2) = adevarat atunci intrerupe ciclul //dupa L2

ii. daca nu s-a gasit o valoare consistenta pentru U2 atunci

- elimina L1 din TNOU[U1]- intrerupe ciclul // dupa U2

1.2 daca TNOU[U1] este vida atunci intoarce LINIE_VIDA

2. intoarce TNOUsfarsit

Page 24: Inteligenta Artificiala

BKT cu verificare predictiva Se elimina apelul Verifica_Viitoare(U, TNOU) in

subprogramul Predictie

Algoritm: Backtracking cu verificare predictiva

Predictie(U, F, T)pentru fiecare element L din T[U] executa 1. F[U] L 2. daca U < N atunci //verifica consistenta atribuirii

2.1 TNOU Verifica_Inainte (U, F[U], T)2.2 daca TNOU LINIE_VIDA atunci TNOU Verifica _Viitoare (U, TNOU)2.2 daca TNOU LINIE_VIDA atunci Predictie (U+1, F, TNOU)

3. altfel afiseaza atribuirile din Fsfarsit

Page 25: Inteligenta Artificiala

2.7 Tehnici retrospective Backtracking cu salt

(a)

Pantofi

Cãmãºi Pantaloni

D ={escarpeni, pantofi de tenis}

D ={gri, bleu, jeans}D ={verde, albã}

Pf

C Pt

{(escarpeni, gri), (pantofi de tenis, jeans)}{(escarpeni, albã)}

{(verde, gri), (verde, jeans), (albã, jeans), (albã, bleu)}

Pantofi escarpeni pantofi de tenis

jeans

verde albã

Pantaloni

Cãmãºi

jeansbleu

gri

verde albã2

1

1

1

(b)

gris bleu

verde alba

verde alba

(pantofi de tens, gris) (pantofi tenis, bleu)

Page 26: Inteligenta Artificiala

Algoritm: Backtracking cu saltBacktrackingCuSalt(U, F) /* intoarce Nivel – blocare */

/* NrBlocari, NivelVec, I, test– var locale */1. NrBlocari 0, I 0, Nivel U2 pentru fiecare element V a lui XU executa

2.1 F[U] V2.2 test, NivelVec[I] Verifica1 (U, F)2.3 daca test = adevarat atunci

2.3.1 daca U < N atuncii. Nivel BacktrackingCuSalt (U+1, F)ii. daca Nivel < U atunci salt la pasul 4

2.3.2 altfel afiseaza valorile vectorului F // solutia2.4 altfel NrBlocari NrBlocari + 12.5 I I + 1

3. daca NrBlocari = numar valori ale lui X[U] sitoate elementele din NivelVec sunt egale

atunci Nivel NivelVec[1]4. intoarce Nivelsfarsit

Page 27: Inteligenta Artificiala

Verifica1 (U, F)

/* intoarce test si nivelul la care s-a produs blocarea sau 0 */

1. test adevarat

2. I U-1

3. cat timp I>0 executa

3.1 test Relatie(I, F[I], U, F[U])

3.2 daca test = fals

atunci intrerupe ciclul

3.3 I I –1

4. NivelAflat I

5. intoarce test, NivelAflat

sfarsit

Page 28: Inteligenta Artificiala

2.8 Euristici

Ordonarea variabilelor Ordonarea valorilor Ordonarea testelor

Page 29: Inteligenta Artificiala

2.9 CSP partiala

Memoreaza cea mai buna solutie gasita pana la un anumit moment (gen IDA*) – distanta d fata de solutia perfecta

Abandoneaza calea de cautare curenta in momentul in care se constata ca acea cale de cautare nu poate duce la o solutie mai buna

NI - numarul de inconsistente gasite in "cea mai buna solutie" depistata pana la un moment dat – limita necesara

Page 30: Inteligenta Artificiala

CSP partiala

Pantofi

escarpeni pantofi de tenis

jeansbleu gri

verde albã

Pantaloni

Cãmãºi

jeans

bleugri

verde albã verde albã

d=0 d=0

d=1

d=1d=0 d=0

d=1 d=1

15 t.c.6 t.c.

14 t.c.d=3 d=1 d=1 d=1 d=1NI=3 NI=1 NI=1 NI=1 NI=13 t.c. 5 t.c. 8 t.c. 10 t.c. 12 t.c.

d=0NI=113 t.c.

* * *NI=1 NI=1

Page 31: Inteligenta Artificiala

CSP partiala

S - limita suficienta - specifica faptul ca o solutie care violeaza un numar de S restrictii (sau mai putine), este acceptabila.

PBKT(Cale, Distanta,Variablie,Valori) Semnificatie argumente Rezultat: GATA sau CONTINUA

variabile globale: CeaMaiBuna, NI, S

Page 32: Inteligenta Artificiala

Algoritm: CSP PartialaPBKT(Cale, Dsitanta, Variabile, Valori)

/* intoarce GATA sau CONTINUA */1. daca Variabile = {}

atunci1.1 CeaMaiBuna Cale1.2 NI Distanta1.3 daca NI S atunci intoarce GATA

altfel intoarce CONTINUA2. altfel

2.1 daca Valori = {} atunci CONTINUA/* s-au incercat toate valorile si se revine la var ant. */

2.2 altfel2.2.1 daca Distanta NI

atunci intoarce CONTINUA/* revine la var ant pentru gasirea unei solutii mai bune*/

Page 33: Inteligenta Artificiala

2.2.2 altfeli. Var first(Variabile)ii. Val first(Valori)iii. DistNoua Distantaiv. Cale1 Calev. cat timp Cale1 <> {} si DistNoua < NI executa

- (VarC, ValC) first(Cale1)- daca Rel(Var,Val,VarC,ValC) = fals- atunci DistNoua DistNoua + 1- Cale1 rest(Cale1)

vi. daca DistNoua < NI si PBKT(Cale+(Val,Var),DistNoua,Rest(Variabile),ValoriNoi)

= GATA/* ValoriNoi - domeniul de valori asociat primei variabile din Rest(Variabile) */

atunci intoarce GATA altfel intoarce

PBKT(Cale,Distanta,variabile,rest(Valori)

sfarsit

Page 34: Inteligenta Artificiala

2.10 Cautari locale

Multime de stari S, Operatori: S S Cost(Utilitate): S R Reprezentare stari Operatori de modificare a starilor Minime/maxime locale Exemplu: cautare tip SA (simulated

annealing)

Page 35: Inteligenta Artificiala

Algoritm: Cautare SA

1. T temperatira initiala2. s stare initiala3. v Energie(s)2. cat timp T > temp finala executa

2.1 pentru i=1,n executa s' operator(s) v' Energie(s')daca v' < v atunci s s'altfel s s' cu prob. exp(-(v'-v)/kT)

2.2 T 0.95 * Tsfarsit

Page 36: Inteligenta Artificiala

3. Strategii de cautare in jocuri

Jocuri ce implică doi adversari jucator adversar

Jocuri in care spatiul de cautare poate fi investigat exhaustiv

Jocuri in care spatiul de cautare nu poate fi investigat complet deoarece este prea mare.

Page 37: Inteligenta Artificiala

3.1 Minimax pentru spatii de cautare investigate exhaustiv Jucator – MAX Adversar – MIN Principiu Minimax Etichetez fiecare nivel din AJ cu MAX (jucator) si

MIN (adversar) Etichetez frunzele cu scorul jucatorului Parcurg AJ

daca nodul parinte este MAX atunci i se atribuie valoarea maxima a succesorilor sai;

daca nodul parinte este MIN atunci i se atribuie valoarea minima a succesorilor sai.

Page 38: Inteligenta Artificiala

Spatiu de cautare Minimax (AJ)

MIN

A / 3

B / 3

MAX

C / 2 D / 2

MAX F / 12E / 3 G / 8 H / 2 I / 4 J / 6 K / 14 L / 5 M / 2

Page 39: Inteligenta Artificiala

Spatiu de cautare Minimax (AJ)

MIN

MAX

MIN

MAX

MIN

MAX

7 / 1

6 - 1 / 1 5 - 2 / 1 4 - 3 / 1

5 - 1 - 1 / 0 4 - 2 - 1 / 1 3 - 2 - 2 / 0 3 - 3 - 1 / 1

4 - 1 - 1 - 1 / 0 3 - 2 - 1 - 1 / 1 2 - 2 - 2 - 1 / 0

3 - 1 - 1 - 1 - 1 / 0 2 - 2 - 1 - 1 - 1 / 1

2 - 1 - 1 - 1 - 1 - 1 / 0

Nim cu 7 bete

Page 40: Inteligenta Artificiala

Algoritm: Minimax cu investigare exhaustiva Minimax( S )

1. pentru fiecare succesor Sj al lui S (obtinut printr-o mutare opj) executa

val( Sj ) Minimax( Sj )

2. aplica opj pentru care val( Sj ) este maximasfarsit

Minimax( S )1. daca S este nod final atunci intoarce scor( S )2. altfel

2.1 daca MAX muta in S atunci

2.1.1 pentru fiecare succesor Sj al lui S executa

val( Sj ) Minimax( Sj )

2.1.2 intoarce max( val( Sj ), j )2.2 altfel { MIN muta in S }

2.2.1 pentru fiecare succesor Sj al lui S executa

val( Sj ) Minimax( Sj )

2.2.2 intoarce min( val( Sj ), j )sfarsit

Page 41: Inteligenta Artificiala

3.2 Minimax pentru spatii de cautare investigate pana la o adancime n

Principiu Minimax Algoritmul Minimax pana la o adancime n nivel(S) O functie euristica de evaluare a unui nod

eval(S)

Page 42: Inteligenta Artificiala

Algoritm: Minimax cu adancime finita n Minimax( S )1. pentru fiecare succesor Sj al lui S (obtinut printr-o mutare opj) executa

val( Sj ) Minimax( Sj )2. aplica opj pentru care val( Sj ) este maximasfarsit

Minimax( S ) { intoarce o estimare a starii S }0. daca S este nod final atunci intoarce scor( S )1. daca nivel( S ) = n atunci intoarce eval( S )2. altfel

2.1 daca MAX muta in S atunci2.1.1 pentru fiecare succesor Sj al lui S executa

val( Sj ) Minimax( Sj )2.1.2 intoarce max( val( Sj ), j )

2.2 altfel { MIN muta in S }2.2.1 pentru fiecare succesor Sj al lui S executa

val( Sj ) Minimax( Sj )2.2.2 intoarce min( val( Sj ), j )

sfarsit

Page 43: Inteligenta Artificiala

Implementare Prolog play:- initialize(Position,Player), display_game(Position,Player), play(Position,Player,Result).

% play(+Position,+Player,-Result)play(Position, Player, Result) :- game_over(Position,Player,Result), !, write(Result),nl.

play(Position, Player, Result) :- choose_move(Position,Player,Move), move(Move,Position,Position1), next_player(Player,Player1), display_game(Position1,Player1), !, play(Position1,Player1,Result).

% apel ?-play.

Page 44: Inteligenta Artificiala

move(a1,a,b).move(a2,a,c).move(a3,a,d).move(b1,b,e).move(b2,b,f).move(b3,b,g).move(c1,c,h).move(c2,c,i).move(c3,c,j).move(d1,d,k).move(d2,d,l).move(d3,d,m).

next_player(max,min).next_player(min,max).

initialize(a,max).display_game(Position,Player):-

write(Position),nl,write(Player),nl.

game_over(e,max,3).game_over(f,max,12).game_over(g,max,8).game_over(h,max,2).game_over(i,max,4).game_over(j,max,6).game_over(k,max,14).game_over(l,max,5).game_over(m,max,2).

% move(+Move,+Position,-Position1)

% game_over(+Position,+Player,-

Result).

% next_player(+Player, - Player1)

Page 45: Inteligenta Artificiala

% choose_move(+Position, +Player, -BestMove)choose_move(Position, Player, BestMove):- get_moves(Position,Player,Moves), evaluate_and_choose(Moves,Position,10,Player,Record,[BestMove,_]).

% get_moves(+Position, +Player, -Moves)get_moves(Position, Player, Moves):- findall(M,move(M,Position,_),Moves).

% evaluate_and_choose(+Moves, +Position,+D,+MaxMin,+Record,-BestRecord).

evaluate_and_choose([Move|Moves],Position,D,MaxMin,Record,BestRecord) :-

move(Move,Position,Position1), next_player(MaxMin, MinMax), minimax(D,Position1,MinMax,Value), update(MaxMin,Move,Value,Record,Record1), evaluate_and_choose(Moves,Position,D,MaxMin,Record1,BestRecord).

evaluate_and_choose([], Position, D, MaxMin, BestRecord, BestRecord).

Page 46: Inteligenta Artificiala

% minimax(+Depth,+Position,+MaxMin,-Value)

minimax(_, Position, MaxMin, Value) :- game_over(Position,MaxMin,Value),!.

minimax(0, Position, MaxMin, Value) :- eval(Position,Value),!.

minimax(D, Position, MaxMin, Value) :- D > 0, D1 is D-1, get_moves(Position,MaxMin,Moves), evaluate_and_choose(Moves, Position, D1, MaxMin, Record,

[BestMove,Value]).

Page 47: Inteligenta Artificiala

% update(+MaxMin, +Move, +Value, +Record, -Record1)

update(_, Move, Value, Record, [Move,Value]) :- var(Record),!.

update(max, Move, Value, [Move1,Value1], [Move1,Value1]) :- Value =< Value1.update(max, Move, Value, [Move1,Value1], [Move,Value]) :- Value > Value1.

update(min, Move, Value, [Move1,Value1], [Move1,Value1]) :- Value > Value1.update(min, Move, Value, [Move1,Value1], [Move,Value]) :- Value =< Value1.

Page 48: Inteligenta Artificiala

Exemplu de functie de evaluare

Jocul de Tic‑Tac‑Toe (X si O) Functie de estimare euristica eval( S ) - conflictul

existent in starea S. eval( S ) = numarul total posibil de linii castigatoare

ale lui MAX in starea S - numarul total posibil de linii castigatoare ale lui MIN in starea S.

Daca S este o stare din care MAX poate face o miacare cu care castiga, atunci eval( S ) =  (o valoare foarte mare)

Daca S este o stare din care MIN poate castiga cu o singura mutare, atunci eval( S ) = - (o valoare foarte mica).

Page 49: Inteligenta Artificiala

eval(S) in Tic-Tac-Toe

  X are 6 linii castigatoare posibile

  O are 5 linii castigatoare posibile

  eval( S ) = 6 - 5 = 1

X    

     

  O  

Page 50: Inteligenta Artificiala

3.3 Algoritmul taierii alfa‑beta

Este posibil sa se obtină decizia corecta a algoritmului Minimax fara a mai inspecta toate nodurile din spatiului de cautare pana la un anumit nivel.

Procesul de eliminare a unei ramuri din arborele de cautare se numeste taierea arborelui de cautare (pruning).

Page 51: Inteligenta Artificiala

Algoritmul taierii alfa‑beta

Fie cea mai buna valoare (cea mai mare) gasita pentru MAX si cea mai buna valoare (cea mai mica) gasita pentru MIN.

Algoritmul alfa‑beta actualizeaza si pe parcursul parcurgerii arborelui si elimina investigarile subarborilor pentru care sau sunt mai proaste.

Terminarea cautarii (taierea unei ramuri) se face dupa doua reguli:

Cautarea se opreste sub orice nod MIN cu o valoare mai mica sau egala cu valoarea a oricaruia dintre nodurile MAX predecesoare nodului MIN in cauza.

Cautarea se opreste sub orice nod MAX cu o valoare mai mare sau egala cu valoarea a oricaruia dintre nodurile MIN predecesoare nodului MAX in cauza.

Page 52: Inteligenta Artificiala

Tăierea alfa-beta a spaţiului de căutare

MIN

A / 3

B / 3

MAX

C / 2 D / 2

MAX F / 12E / 3 G / 8 H / 2 I / 4 J / 6 K / 14 L / 5 M / 2

Page 53: Inteligenta Artificiala

Algoritm: Alfa-betaMAX(S, , ) { intoarce valoarea maxima a unei stari. }0. daca S este nod final atunci intoarce scor( S )1. daca nivel( S ) = n atunci intoarce eval( S )2. altfel

2.1 pentru fiecare succesor Sj al lui S executa2.1.1 max(, MIN(Sj, , ))2.1.2 daca atunci intoarce

2.2 intoarce sfarsit

MIN(S, , ) { intoarce valoarea minima a unei stari. }0. daca S este nod final atunci intoarce scor( S )1. daca nivel( S ) = n atunci intoarce eval( S )2. altfel

2.1 pentru fiecare succesor Sj al lui S executa2.1.1 min(, MAX(Sj, , ))2.1.2 daca atunci intoarce

2.2 intoarce sfarsit

Page 54: Inteligenta Artificiala

3.4 Jocuri cu elemente de sansa

Jucatorul nu cunoaste miscarile legale ale oponentului

3 tipuri de noduri: MAX MIN Sansa (chance nodes)

Page 55: Inteligenta Artificiala

55

MAX

MIN

MAX

Zar

Noduri sansa

Noduri de decizieNoduri de decizie

• 36 rez pt 2 zaruri• 21 noduri distincte• Zaruri egale - > 1/36• Zaruri diferite -> 1/18

1/361,1

1/181,2

Zar

1/361,1

1/181,2

• Valoarea estimata pt noduri sansa• SumaSj suc S[ P(Sj)*EMinimax(Sj)]

• Functia de evaluare•scor – nod terminal•max din EMinimax succesori - MAX•min din EMinimax succesori - MIN•Suma P(Sj)*EMinimax(Sj)] succesori

- SANSA