Inteligenta Artificiala
description
Transcript of 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
Curs nr. 3
Strategii de rezolvare a problemelor Problema satisfacerii restrictiilor Strategii de cautare in jocuri
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
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)
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.
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
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.
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.
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
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
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
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.
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
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)
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
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.
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.
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)
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
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
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
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
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
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
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)
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
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
2.8 Euristici
Ordonarea variabilelor Ordonarea valorilor Ordonarea testelor
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
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
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
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*/
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
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)
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
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.
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.
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
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
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
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)
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
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.
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)
% 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).
% 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]).
% 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.
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).
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
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).
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.
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
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
3.4 Jocuri cu elemente de sansa
Jucatorul nu cunoaste miscarile legale ale oponentului
3 tipuri de noduri: MAX MIN Sansa (chance nodes)
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