10 Probleme rezolvabile prin backtracking q2p24pg
Mecanismul implicit de functionare a limbajului Prolog este bazat pe backtracking. De aceea problemele care se rezolva prin backtracking se implementeaza mai usor in Prolog decat in alte limbaje. Sa studiem cateva probleme rezolvabile prin backtracking.
10.1 Problema taranului
Fie urmatoarea problema: Pe malul unui rau se afla un taran cu un lup, o capra si o varza. Taranul doreste sa traverseze cu ele raul. Taranul poate face traversari inot ale raului impreuna doar cu unul din cele trei personaje de transportat, sau singur. Daca lupul ramane pe acelasi mal impreuna cu capra si taranul este pe celalalt mal, capra va fi mancata de lup. Similar se intampla cu varza si capra. Sa se scrie un program Prolog care sa ii dea taranului toate solutiile de traversare.
Vom prezenta o rezolvare pe baza de backtracking. Definim starea problemei la un moment dat ca fiind: stare(Taran, Lup, Capra, Varza) unde Taran, Lup, Capra si Varza indica pozitia (malul) fiecarui element si pot avea valorile stang sau drept. In acest fel stim exact pe ce mal se afla fiecare dintre personaje. De remarcat ca aceasta este o structura si nu un predicat. De aici rezulta ca starea intiala este (de exemplu): stare(stang, stang, stang, stang) iar starea finala este: stare(drept, drept, drept, drept).
Rezolvarea problemei prin backtracking presupune incercarea unei miscari posibile in starea curenta si apoi reluarea algoritmului. O miscare genereaza o noua stare, din care se vor incerca apoi alte miscari. Daca se ajunge intr o stare finala, s a gasit o solutie. In acest caz trebuie facuta o revenire pentru a incerca gasirea altor solutii. Trebuie specificate, evident, starea initiala si starea sau starile finale.
Daca se ajunge intr o stare ilegala, cum ar fi de exemplu, in cazul acestei probleme, stare(stang, stang, drept, drept), se executa tot o revenire in starea anterioara. Acelasi lucru trebuie sa se intample si daca starea curenta este una in care s a mai ajuns o data. Nu are rost sa trecem de mai multe ori prin aceeasi configuratie deoarece acest lucru nu face decat sa lungeasca numarul de miscari necesare si poate conduce la bucle infinite.
Deci vom avea nevoie de un predicat care, dandu se o stare, sa stie sa execute miscarile posibile din acea stare. Fie acest predicat: miscare(Stare, StareUrmatoare).
Sa vedem cum se defineste predicatul miscare in cazul acestei problemei:
1) Taranul poate lua lupul cu el pe celalat mal: miscare(stare(Taran, Taran, Capra,Varza), stare(Taran1, Taran1, Capra,Varza)) : opus((Taran, Taran1).
2) Taranul poate lua capra cu el pe celalat mal: miscare(stare(Taran, Lup, Taran,Varza), stare(Taran1, Lup, Taran1, Varza)) : opus(Taran, Taran1).
3) Taranul poate lua varza cu el pe celalat mal: miscare(stare(Taran, Lup, Capra, Taran), stare(Taran1, Lup, Capra, Taran1)) : opus(Taran, Taran1).
4) Taranul poate traversa singur raul: miscare(stare(Taran, Lup, Capra, Varza), stare(Taran1, Lup, Capra, Varza)) : opus(Taran, Taran1).
Se observa ca am folosit predicatul opus(Mal1, Mal2), care determina malul opus unui mal dat. Definitia lui este: opus(stang, drept). opus(drept, stang).
Predicatele initiala(S) si finala(S) specifica daca o stare este sau nu initiala, respectiv finala. Definitiile lor sunt: initiala(stare(stang, stang, stang, stang)). finala(stare(drept, drept, drept, drept)).
Predicatul ilegala(Stare) spune daca o stare este ilegala:
1) Daca lupul este pe acelasi mal cu capra si taranul este pe celalalt mal: ilegala(stare(Taran, Lup, Lup, _ )) :- opus(Taran, Lup).
2) Daca varza este pe acelasi mal cu capra si taranul este pe celalalt mal: ilegala(stare(Taran, _ ,Capra, Capra)) :- opus(Taran, Capra).
Se poate scrie acum predicatul de gasire a unei succesiuni de mutari care rezolva problema. Deoarece nu trebuie sa repetam stari, predicatul va primi, pe langa starea curenta, si o lista de stari deja parcurse, intorcand lista de stari (Solutie) care constituie rezolvarea: lcv(+Stare, -Solutie, -Vizitate). unde Stare este starea curenta, Solutie este solutia ce trebuie gasita, iar Vizitate este lista de stari parcurse. Acest predicat se scrie tinand cont de:
1) Daca starea curenta este o stare finala, atunci solutie este lista de stari parcurse impreuna cu starea curenta: lcv(Stare, aStare|Vizitatei, Vizitate) :- finala(Stare).
2) Altfel genereaza o noua mutare, testeaza daca este legala, testeaza daca nu a mai fost parcursa si relanseaza cautarea din noua stare: lcv(Stare, Solutie, Vizitate) : miscare(Stare, StareUrmatoare), % o noua mutare not(ilegala(StareUrmatoare)), % este ilegala? not(member(StareUrmatoare, aStare | Vizitatei)), % este deja parcursa? lcv(StareUrmatoare, Solutie, aStare | Vizitatei). % reia cautarea
Predicatul member testeaza daca un element face parte dintr o lista si a fost detaliat anterior. Predicatul rezolva rezolva problema, intorcand lista starilor parcurse din starea initiala in starea finala, deci solutia problemei. rezolva(Solutie) :- initiala(Stare), lcv(Stare, Solutie, ai ).
10.2 Problema misionarilor si canibalilor
Trei misionari si trei canibali ajung la malul estic al unui rau. Aici se afla o barca cu doua locuri cu care se poate traversa raul (raul nu se poate traversarea inot deoarece in el traiesc pesti piranha). Daca pe unul dintre maluri numarul de canibali este mai mare decat numarul de misionari, atunci misionarii de pe acel mal vor fi mancati de canibali. Problema intreaba cum pot trece toti raul fara ca misionarii sa fie mancati de canibali. Pentru a afla solutia vom parcurge pasii de la problema anterioara:
Structura starii curente este: stare(MalBarca, NMisionariVest, NCanibaliVest, NMisionariEst, NCanibaliEst). rezolva(Solutie) :- initiala(Stare), mc(Stare, Solutie, ai ).

% mc(+Stare, -Solutie, +StariVizitate) mc(Stare, aStare | Vizitatei, Vizitate) :- finala(Stare). mc(Stare,Solutie,Vizitate) : miscare(Stare, StareUrmatoare), not(ilegala(StareUrmatoare)), not(member(StareUrmatoare, aStare | Vizitatei)), mc(StareUrmatoare, Solutie, aStare | Vizitatei).

% miscare(+Stare, -StareUrmatoare) miscare(stare(est, MV,CV, ME, CE), stare(vest, MV1, CV, ME1, CE)) : oameni(N), ME >= N, ME1 is ME - N, MV1 is MV + N. miscare(stare(est, MV, CV, ME, CE), stare(vest, MV, CV1, ME, CE1)) : oameni(N), CE >= N, CE1 is CE - N, CV1 is CV + N. miscare(stare(est, MV, CV, ME, CE), stare(vest, MV1, CV1, ME1, CE1)) : ME >= 1, CE >= 1, ME1 is ME - 1, MV1 is MV + 1,
CE1 is CE - 1, CV1 is CV + 1.

miscare(stare(vest, MV, CV, ME, CE), stare(est, MV1, CV, ME1, CE)) : oameni(N), MV >= N, MV1 is MV - N, ME1 is ME + N. miscare(stare(vest, MV, CV, ME, CE), stare(est, MV, CV1, ME, CE1)) : oameni(N), CV >= N, CV1 is CV - N, CE1 is CE + N. miscare(state(vest, MV, CV, ME, CE), stare(est, MV1, CV1, ME1, CE1)) : MV >= 1, CV >= 1, MV1 is MV - 1, ME1 is ME + 1,
CV1 is CV - 1, CE1 is CE + 1.

oameni(1). oameni(2).
% ilegala(+Stare) ilegala(stare( _ , MV,CV , _ , _ )) :- MV > 0, CV > MV. ilegala(stare( _ , _ , _ , ME, CE)) :- ME > 0, CE > ME.

initiala(stare(est, 0, 0, 3, 3)). finala(stare(vest, 3, 3, 0, 0)).
10.3 Problema galetilor cu apa
Exista doua galeti cu capacitatile de 8 si respectiv 5 litri, fara alte marcaje. Se cere sa se masoare exact 4 litri dintr un vas mare care contine cel putin 20 de litri. Operatiile admise sunt: umplerea unei galeti din vasul mare, golirea unei galeti in vasul mare si transferul continutului unei galeti in alta galeata, pana cand galeata din care se toarna s a golit complet, sau galeata in care se toarna s a umplut pana la refuz.
Pentru rezolvarea problemei vom urmari aceeasi schema de la cele doua problemele anterioare. rezolva(Solutie) :- initiala(Stare), galeti(Stare, ai, Solutie). galeti(Stare, Solutie, Vizitate) :- miscare(Stare, StareUrmatoare), % se genereaza starea urmatoare not(member(StareUrmatoare, aStare | Vizitatei)), % starea a mai fost generata? galeti(StareUrmatoare, Solutie, aStare | Vizitatei).
% daca nu, mergem mai departe
O stare este o structura cu cinci campuri: stare(D1, D2, G1, G2, M), care au urmatoare semnificatie: D1 = cati litri de apa sunt in galeata 1, D2 = cati litri de apa sunt in galeata 2, G1 = capacitatea galetii 1, G2 = capacitatea galetii 2, M = mesajul explicativ asociat tranzitiei in aceasta stare (M spune ce actiune a fost executata cand s-a trecut in aceasta stare).
% miscare(+Stare,-StareUrmatoare)
% Regulile comentate nu sunt necesare, ele generand solutii sau executii mai lungi. miscare(stare(D1, D2, G1, G2, _ ), stare(0, D2, G1, G2, 'Golesc G1 in vas.')). miscare(stare(D1, D2, G1, G2, _ ), stare(D1, 0, G1, G2, 'Golesc G2 in vas.')). miscare(stare(D1, D2, G1, G2, _ ), stare(G1, D2, G1, G2, 'Umplu G1 din vas.')). miscare(stare(D1, D2, G1, G2, _ ), stare(D1, G2, G1, G2, 'Umplu G2 din vas.')). miscare(stare(D1, D2, G1, G2, _ ), stare(0, D22, G1, G2, 'Golesc G1 in G2.')) : D1 > 0, D22 is D1 + D2, D22 =< G2.
% miscare(stare(D1, D2, G1, G2, _ ), stare(D11, 0, G1, G2, 'Golesc G2 in G1.')) : % D2 > 0, D11 is D1 + D2, D11 =< G1. miscare(stare(D1, D2, G1, G2, _ ), stare(D11, G2, G1, G2, M)) : T is G2 - D2, D11 is D1 - T, D11 > 0, string_ term(S, T), concat(a'Torn', S, ' litri din G1 in G2.'i, M).
% miscare(stare(D1, D2, G1, G2, _ ), stare(G1, D22, G1, G2, M)) : % T is G1 - D1, D22 is D2 - (G1 - D1), D22 > 0,
% string_ term(S, T), concat(a'Torn', S, ' litri din G2 in G1.'i, M).

Se observa ca problema a fost rezolvata pentru cazul general, putand varia atat capacitatile galetilor, cat si numarul de litri de apa care trebuie masurat.
% Starea initiala initiala(stare(0, 0, 8, 5, 'Galetile sunt goale.')).
% Starea finala finala(stare(4, _ , _ , _ , _ )). finala(stare( _ , 4, _ , _ , _ )).

Functia member a fost rescrisa deoarece mesajul asociat unei stari nu trebuie sa influenteze procesul de rezolvare a problemei. O stare este data de fapt doar de primii doi parametrii ai structurii stare, urmatorii doi fiind doua valori constante, iar ultimul, mesajul, a fost introdus doar pentru a descrie rezolvarea problemei. Deci putem ajunge in aceeasi stare cu doua mesaje diferite. member(stare(X, Y, _ , _ , _ ), astare(X, Y, _ , _ , _ ) | _ i ). member(X, a _ | Resti ) :- member(X, Rest).

Pentru afisarea frumoasa a solutiilor se adauga predicatele: run :- rezolva(Solutie), scrie_solutie(Solutie).

scrie_solutie(ai) :- nl. scrie_solutie(aS | Resti) :- scrie_solutie(Rest), scrie_stare(S).

scrie_stare(stare(X, Y, _ , _ )) :- write(X), write($ $), write(Y), nl.
Functionarea programului este urmatoarea:
?- run.
0 0 Galetile sunt goale.
8 0 Umplu G1 din vas.
3 5 Torn 5 litri din G1 in G2.
3 0 Golesc G2 in vas.
0 3 Golesc G1 in G2.
8 3 Umplu G1 din vas.
6 5 Torn 2 litri din G1 in G2.
6 0 Golesc G2 in vas.
1 5 Torn 5 litri din G1 in G2.
1 0 Golesc G2 in vas.
0 1 Golesc G1 in G2.
8 1 Umplu G1 din vas.
4 5 Torn 4 litri din G1 in G2. yes
10.4 Exercitii propuse
EP1. Fie un graf neorientat definit de legaturile dintre nodurile sale, exprimate ca fapte Prolog: leg(a, b). leg(b, c). leg(a, c). leg(a, d).
1) Sa se defineasca predicatul drum(N1, N2), care verifica daca exista un drum in graf intre nodurile N1 si N2.
2) Sa se critice urmatoarea implementare a predicatului drum: drum(N, N). drum(N1, N2) :- leg(N1, N), drum(N, N2).
3) Sa se modifice definitia predicatului drum la drum(N1, N2, ListaN) astfel incat sa se obtina in ListaN lista nodurilor parcurse intre N1 si N2, in cazul in care exista un drum in graf intre nodurile N1 si N2, si lista vida in caz contrar.
EP2. Studiind texte vechi, in incercarea de a reconstitui arborele genealogic al unei familii boieresti, un istoric si-a notat pe fise separate, relatiile de rudenie dintre diferitele persoane ale unei singure familii, sub forma a trei tipuri de relatii: x este sotul (sotia) lui y x este fiul (fiica) lui y x este fratele (sora) lui y unde x si y sunt prenumele unor membri din aceeasi familie.
In ipoteza ca nu exista doua persoane cu acelasi prenume, sa se scrie un program care citeste dintr-un fisier relatii de rudenie intre perechi de persoane si care stabileste urmatoarele:
- daca informatiile privind relatiile de rudenie sunt compatibile sau contradictorii, stiind ca in familie nu s-au facut casatorii intre rude. In caz ca informatiile sunt contradictorii se da mesajul 'Informatii incompatibile' si nu se mai fac alte operatii privind familia in cauza;
- daca informatiile nu sunt complete pentru alcatuirea arborelui genealogic, se afiseaza numai mesajul 'Informatii incomplete'. Daca datele permit alcatuirea arborelui genealogic, se afiseaza mai intai relatiile de rudenie deduse in afara celor date initial si se afiseaza arborele genealogic sub o forma sugestiva. (Concurs de Programare UPB 1995, Etapa locala).
11 Strategii de cautare in spatiul starilor
Unul dintre cele mai utilizate modele de rezolvare a problemelor este prin reprezentarea cautarii sub forma unui graf orientat in care nodurile sunt stari succesive in rezolvare iar arcele corespund tranzitiilor sau operatorilor legali ce pot fi aplicati pentru trecerea dintr-o stare in alta aFlo93,LS93i.
11.1 Cautarea solutiilor in spatiul starilor
Pentru a construi o descrierea unei probleme rezolvate prin reprezentare in spatiul starilor trebuie parcurse urmatoarele etape:
1) Se defineste spatiul starilor care contine toate toate configuratiile posibile ale obiectelor relevante (si poate si unele imposibile). Spatiul se poate defini explicit prin indicarea tuturor starilor (acesta fiind un caz particular si rar intalnit in practica) sau implicit prin indicarea transformarilor care genereaza o noua stare dintr-o stare data.
2) Se specifica una sau mai multe stari din spatiu care descriu situatii posibile de la care poate porni procesul de rezolvare a problemei (starea initiala).
3) Se specifica una sau mai multe stari care ar fi acceptabile ca solutii ale problemei. Aceste stari se numesc stari scop (sau stari finale sau scopuri).
4) Se specifica un set de reguli care descriu actiunile (operatorii) disponibile si care definesc tranzitiile sau transformarile intre stari. In aceasta etapa trebuie analizate urmatoarele probleme:
• Ce presupuneri nedeclarate explicit sunt prezente in descrierea informala a problemei?
• Cat de generale trebuie sa fie regulile?
• Cat de mult din calculul necesar rezolvarii problemei ar trebui facut inainte si reprezentat in reguli?
Problema poate fi rezolvata apoi utilizand o strategie de control adecvata, pentru a parcurge o parte din spatiul starilor (eventual tot) pana cand este gasita o cale de la o stare initiala la o stare finala, in cazul in care problema admite solutie. Cautarea este un mecanism general care poate fi utilizat atunci cand o metoda directa (determinista) de rezolvare a problemei nu este cunoscuta. In acelasi timp, ea ofera cadrul in care pot fi incapsulate metode mai directe de rezolvare a anumitor parti ale problemei (subproblemelor).
11.2 Cautare prin backtracking
Rezolvarea unei probleme folosind strategia de backtracking a fost expusa in capitolul 10. In continuare se prezinta schema generala a unei astfel de cautari care poate fi aplicata pentru orice descriere a unei subprobleme in termeni de stari initiale, stari finale si operatori sau tranzitii intre stari. Pentru ilustrare, se defineste explicit un spatiu de cautare finit, ipotetic, prin definirea predicatului succ(stare, stare_urmatoare). O definire a predicatului succ specifica unei probleme particulare cuplata cu schema generala de rezolvare prin backtracking ce este prezentata in continuare rezolva problema.
% Graful care descrie spatiul de cautare complet. succ(a,b). % a stare initiala succ(b,c). succ(c,d). succ(d,g). succ(a,e). succ(e,f). succ(f,g). final(g). % Stare finala

% rez(+Stare, -Sol) rez(Stare, Sol) :- bkt(Stare, ai, Sol). bkt(Stare, Drum, aStare | Drumi) :- final(Stare). bkt(Stare, Drum, Sol) :- succ(Stare, N1), not (member(N1, Drum)), bkt(N1, aStare | Drumi, Sol).

?- rez(a,Sol).
Sol=ag,d,c,b,ai
Cautarea prin backtracking poate fi cuplata cu impunerea unei adancimi maxime de cautare, necesara in special in cazul spatiilor de cautare infinite in care solutia poate sa nu se afle pe ramura curenta pe care a inceput cautarea. Stabilirea unei adancimi maxime de cautare se poate face astfel:
% rez1(Stare, Sol) impune o adancimea maxima Max = 10 rez1(Stare, Sol) :- bkt1(Stare, Sol,10). bkt1(Stare, aStarei, _ ) :- final(Stare). bkt1(Stare, aStare | Soli, Max) :-
Max > 0, succ(Stare, N1),
Max1 is Max-1, bkt1(N1, Sol, Max1).
In acest caz, s-a eliminat testul de stari anterior parcurse deoarece, existand o adancime maxima de cautare se elimina buclele dar cu penalizarea eventuala a reparcurgerii unor stari. Exercitiul propus 1 al acestui capitol va cere o combinare a acestor doua solutii.
11.3 Cautare pe nivel si in adancime
Pentru implementarea acestor doua strategii de cautare de baza se folosesc doua liste: lista OPEN a nodurilor explorate in cautare (sau FRONTIERA portiunii cunoscute a spatiului de cautarea la un moment dat cu partea necunoscuta inca a acestui spatiu) si lista CLOSED a nodurilor expandate (sau TERITORIUL portiunii cunoscute din spatiul de cautare). Detalii suplimentare asupra acestor strategii de cautare se pot gasi in aFlo93i. Pentru a putea obtine calea de la starea initiala la starea finala, odata ce s-a gasit starea finala, ambele liste vor contine perechi aStare, Predecesori, unde Predecesor este starea predecesoare a starii Stare. Pentru starea initiala se va introduce in OPEN perechea aStareInitiala, nili, cu nil o constanta arbitrar fixata.
Implementarea foloseste doua tipuri de date, stiva si coada, pentru exploatarea listei OPEN, respectiv stiva in cazul cautarii in adancime si coada in cazul cautarii pe nivel. Definirea operatiilor tipice asociate acestor structuri de date abstracte in Prolog este pusa in evidenta de implementarea ce urmeaza.
% Cautare pe nivel si in adancime
% Se folosesc tipurile de date abstracte Stack and Queue.

% TDA Stack
% emptys(+S) - testeaza daca stiva este vida
% emptys(-S) - initializeaza stiva emptyst(ai).
% stack(-Top, -SNou, +S) - are efect de pop
% stack(+Top, +S, -SNoua) - are efect de push
% stack(-Top, _, +S) - are efect de top stack(Top, Stack, aTop | Stacki).

% TDA Queue
% empty(+Q) - testeaza daca coada este vida
% empty(-Q) - initializeaza coada emptyq(ai).
% enqueue(+El, +Q, -QNoua) introduce un element in coada enqueue(El, ai, aEli). enqueue(El, aX | Resti, aX | R1i) :- enqueue(El, Rest, R1).
% dequeue(-El, +Q, -QNoua) elimina un element din coada dequeue(El, aEl | Ri, R).

% Spatiul de cautare succ(a, b). succ(b, c). succ(c, d). succ(d, g). succ(a, e). succ(e, f). succ(f, g). final(g).

% Rezolvare cu parcurgere pe nivel
% rezbreadth(+StareInitiala) rezbreadth(Si) :- emptyq(Open), emptyq(Closed), enqueue(aSi, nili, Open, Open1), breadth(Open1, Closed). breadth(Open, _) :- emptyq(Open), !, write('Nu exista solutie'), nl. breadth(Open, Closed) :- dequeue(aStare | Predeci, Open, _), final(Stare),
write('S-a gasit o solutie'), nl, scriecale(aStare | Predeci, Closed). breadth(Open, Closed) : dequeue(aStare| Predeci, Open, _), final(Stare),
write('S-a gasit o solutie'),nl, showpath(aStare| Predeci, Closed). breadth(Open, Closed) : dequeue(aStare, Predi, Open, RestOpen), enqueue(aStare, Predi, Closed, Closed1), listsucc(Stare, RestOpen, Closed1, LSucc), append(RestOpen, Lsucc, Open1), breadth(Open1, Closed1). listsucc(Stare, RestOpen, Closed, Lsucc) : bagof(aS, Starei, (succ(Stare, S), not member(aS,_i, RestOpen), not member(aS, _i, Closed) ), LSucc). listsucc(Stare, RestOpen, Closed, ai).

% Rezolvare cu parcurgere pe in adancime
% rezdepth(+StareInitiala) rezdepth(Si) :- emptyst(Open), emptyst(Closed), stack(aSi, nili, Open, Open1), depth(Open1, Closed). depth(Open, _) :- emptyst(Open), write('Nu exista solutie'), nl. depth(Open, Closed) :- stack(aStare | Predeci, RestOpen, Open), final(Stare),

write('S-a gasit o solutie'), nl, scriecale(aStare | Predeci, Closed). depth(Open, Closed) :- stack(aStare, Predi, RestOpen, Open), stack(aStare, Predi, Closed, Closed1), listsucc(Stare, RestOpen, Closed1, LSucc), append(LSucc, RestOpen, Open1), depth(Open1, Closed1).
% Afiseaza calea de la Si la Sf
% scriecale(+Cale, +Closed) scriecale(aS, nili, _) :- scrie(S), nl. scriecale(aS, Predeci, Closed) :- member(aPredec, Pi, Closed), scriecale(aPredec, Pi, Closed), scrie(S), nl. scrie(S) :- write(S). member(El, aEl | _i). member(El ,a_ | Resti) :- member(El, Rest). append(ai, L, L). append(aX | L1i, L2, aX | L3i) :- append(L1, L2, L3).

?- rezbreadth(a). a e f g
?- rezdepth(a). a b c d g
Strategia de cautare pe nivel este o strategie completa care, in plus, gaseste calea de la starea initiala la starea finala cu numarul minim de tranzitii de stari. Strategia de cautare in adancime nu este completa pentru orice spatii de cautare dar consuma mai putina memorie decat cea in adancime.
Pentru a pune in evidenta diferenta intre strategia de cautare in adancime si cea de backtracking, se va rescrie schema generala de backtracking din sectiunea precedenta pe acelasi sablon cu cel de la strategiile precedente. rezbkt(Si) :-emptyst(Open), stack(Si, Open, NewOpen), bkt(NewOpen). bkt(Open) :- stack(S, _, Open), final(S), write('S-a gasit o solutie'), afis(Open). bkt(Open) :- stack(S, _, Open), succ(S, S1), not member(S1, Open), stack(S1, Open, NewOpen), bkt(NewOpen). afis(ai) :- nl. afis(aS | Resti) :- afis(Rest), scrie(S).
Se observa ca, deoarece strategia de backtracking pastreaza numai starile de pe calea curenta de cautare si face testul pentru stari anterior parcurse numai pe aceasta cale, este suficient mentinerea numai a listei OPEN. In plus, aceasta lista nu mai trebuie sa fie o lista de perechi aStare, Predecesori ci numai o lista de stari parcurse, la detectia starii finale continutul lui OPEN fiind chiar calea spre solutie. Implementarea de mai sus este echivalenta cu cea din sectiunea precedenta. Predicatul afis permite afisarea starilor parcurse in ordinea de la starea initiala la cea finala.
11.4 Algoritmul A*
A* este un algoritm de cautare in spatiul starilor a solutiei de cost minim (solutia optima) ce utilizeaza o functie euristica de estimare a distantei starii curent parcurse fata de starea finala. Pe parcursul cautarii, starile sunt considerate in ordinea crescatoare a valorii functiei f(S)=g(S)+h(S), unde g(S) este functia de cost a portiunii parcurse pana in starea S iar h(S) este functia euristica de estimare a distantei din S la starea finala. Functia euristica trebuie sa fie admisibila (mai mica sau cel mult egala cu distanta reala) pentru a garanta optimalitatea solutiei. O prezentare sistematica si detalii suplimentare asupra algoritmului A* pot fi gasite in aFlo93i. Desi are o complexitate timp tot exponentiala, ca orice procedura de cautare, algoritmul este mai eficient, in general, decat stategiile neinformate datorita componentei euristice care ghideaza cautarea.
Trebuie observat ca algoritmul A* poate fi aplicat si in cazul in care intr-o problema nu exista costuri, considerand implicit toate costurile tranzitiilor de stari egale cu 1. In acest caz, rezultatele algoritmului sunt similare cu cele ale parcurgerii pe nivel, in sensul gasirii drumului de la starea initiala la starea finala cu un numar minim de tranzitii de stari, dar cautarea este, in general, mai rapida. Programul Prolog ce urmeaza presupune, implicit, costurile tranzitiilor de stari egale cu 1.
Implementarea algoritmului A* se va face pe baza schemelor anterioare de cautare, cu urmatoarele modificari. In loc de a exploata lista OPEN ca o stiva sau ca o coada, acesta lista va fi tratata ca o lista de prioritati in functie de f(S). Fiecarei tranzitii de stari i se va asocia un cost, in functie de problema, si fiecarei stari i se va asocia o valoare pentru functia euristica h(S). Lista OPEN va fi o lista de liste de patru elemente de forma aStare, Predecesor, G, H, Fi. La fel ca in cazurile precedente, programul va fi exemplificat pe un spatiu de cautare ipotetic pentru ca in capitolul urmatoar schema generala de cautare sa fie aplicata pe probleme reale.
% Spatiul de cautare succ(a, b). succ(b, c). succ(c, d). succ(d, g). succ(a, e). succ(e, f). succ(f, g). final(g).

% Valorile functiei euristice folosite in algoritmul A* euristic(a, g, 3). euristic(b, g, 3). euristic(c, g, 2). euristic(d, g, 1). euristic(g, g, 0). euristic(e, g, 2). euristic(f, g, 1). euristic(_, _, 0).

% Coada de prioritati (coada este sortata crescator in functie de cheia F1). inspq(El, ai, aEli). inspq(El, aX | Resti, aEl, X | Resti) :- precedes(El, X), !. inspq(El, aX | Resti, aX | R1i) :- inspq(El, Rest, R1). precedes(a_, _, _, _, F1i, a_, _, _, _, F2i) :- F1<F2.

rezastar(Si, Scop) :- emptyq(Open), emptyq(Closed), euristic(Si, Scop, H), inspq(aSi, nil, 0, H, Hi, Open, Open1), astar(Open1, Closed, Scop).

astar(Open, _, _) :- emptyq(Open), !, write('Nu exista solutie'), nl. astar(Open, Closed, Scop) :- dequeue(aS, Pred, _, _, _i, Open, _),
S=Scop,
write('S-a gasit o solutie'), nl, scriecale1(aS, Pred, _, _, _i, Closed). astar(Open, Closed, Scop) :- dequeue(aS, Pred, G, H, Fi, Open, RestOpen), inspq(aS, Pred, G, H, Fi, Closed, Closed1),
(bagof(aUrmator, H1i, (succ(S, Urmator), euristic(Urmator, Scop, H1)), LSucc),!,
G1 is G+1, actual_toti(S, G1, LSucc, RestOpen, Closed1, OpenR, ClosedR);
OpenR=RestOpen, ClosedR=Closed1), astar(OpenR, ClosedR, Scop).

actual_toti(_, _, ai, Open, Closed, Open, Closed) :- !. actual_toti(Stare, G, aaS, Hi | Resti, Open, Closed, OpenR, ClosedR) :- actual(Stare, G, aS, Hi, Open, Closed, Open1, Closed1), actual_toti(Stare, G, Rest, Open1, Closed1, OpenR, ClosedR). actual(Stare, G, aS, Hi, Open, Closed, OpenR, Closed) :- member(aS, Pred, G1, _, _i, Open), !,
( G1=<G, OpenR=Open, !;
F is G+H, elim(aS, Pred, G1, _, _i, Open, Open1), inspq(aS, Stare, G, H, Fi, Open1, OpenR)).

actual(Stare, G, aS, Hi, Open, Closed, OpenR, ClosedR) :- member(aS, Pred, G1, _, _i, Closed), !,
( G1=<G, ClosedR=Closed, OpenR=Open, !;
F is G+H, elim(aS, Pred, G1, _, _i, Closed, ClosedR), inspq(aS, Stare, G, H, Fi, Open, OpenR)).

actual(Stare, G, aS, Hi, Open, Closed, OpenR, Closed) :-
F is G+H, inspq(aS, Stare, G, H, Fi, Open, OpenR).

scriecale1(aS, nil, _, _, _i, _) :- scrie(S), nl. scriecale1(aS, Pred, _, _, _i, Closed) :- member(aPred, P, _, _, _i, Closed), scriecale1(aPred, P, _, _, _i, Closed), scrie(S), nl. scrie(S) :- write(S). elim(_, ai, ai). elim(X, aX | Resti, Rest) :- !. elim(X, aY | Resti, aY | Rest1i) :- elim(X, Rest, Rest1).
?- rezastar(a). a e f g

11.5 Exercitii propuse
EP1. Sa se rescrie schema de cautare cu backtracking combinand varianta care memoreaza lista starilor parcurse cu cea care impune o adancime maxima de cautare.
EP2. Adancimea maxima de cautare trebuie impusa, in anumite cazuri (spatii de cautare infinite) si pentru cautarea in adancime. Sa se modifice schema cautarii in adancime prin includerea unei adancimi maxime de cautare.
EP3. Strategiile de cautare backtracking, in adancime si pe nivel prezentate determina prima solutie, in cazul in care problema admite solutie. Sa se modifice programele corespunzatoare acestor strategii astfel incat sa determine si sa afiseze toate solutiile problemei, daca problema admite mai multe solutii.
EP4. Sa se modifice algoritmul A* din sectiunea 11.4 prin adaugarea unui cost explicit, diferit de 1, tranzitiilor de stari.
12 Utilizarea cautarii in rezolvarea problemelor
In acest capitol se aplica schemele de strategii de cautare dezvoltate in capitolul precedent pentru rezolvarea unor probleme "clasice" in inteligenta artificiala. In acest scop, pentru fiecare problema, se indica reprezentarea starilor cu identificarea starii initiale si a starii finale, se definesc tranzitiile legale de stari si, acolo unde este cazul, costuri si functii euristice de ghidare a cautarii.
12.1 Problema misionarilor si canibalilor
Reluam problema misionarilor si canibalilor din sectiunea 10.2 si aratam cum se poate rezolva acesta problema pe baza schemelor de cautare prezentate in capitolul 11. Spre deosebire de rezolvarea din sectiunea 10.2, se modifica reprezentarea unei stari a problemei din stare(MalBarca, NMisionariVest, NCanibaliVest, NMisionariEst, NCanibaliEst)
in stare(MalBarca, NMisMalBarca, NCanMalbarca, NMisMalOpus, NCanMalOpus) unde MalBarca poate fi, la fel ca inainte, est sau vest. Implementarea care urmeaza pune in evidenta avantajele acestei noi reprezentari din punct de vedere al simplificarii prelucrarilor necesare.
Se considera starea initiala in care cei trei misionari si canibali sunt pe malul de est, ei dorind sa ajunga pe malul de vest fara ca misionarii sa fie mancati de canibali.
% Stare initiala initial(st(est, 3, 3, 0, 0)).
% Starea finala final(st(vest, 3, 3, 0, 0)).

% Malurile opuse opus(est, vest). opus(vest, est).

% sigur(+NrMisionari, +NrCanibali) - stare sigura sigur(0, _ ). sigur(X, Y) :- X > 0, X >= Y.

% Tranzitii intre stari, succ(+StareCurenta, - StareUrmatoare)
% muta doi misionari succ(st(X, MX, CX, MY, CY), st(Y, MY1, CY, MX1, CX)) :- opus(X, Y), modifica(2, MX, MY, MX1, MY1), sigur(MX1, CX), sigur(MY1, CY).
% muta doi canibali succ(st(X, MX, CX, MY, CY), st(Y, MY, CY1, MX, CX1)) : opus(X, Y), modifica(2, CX, CY, CX1, CY1), sigur(MX, CX1), sigur(MY, CY1).
% muta un misionar si un canibal succ(st(X, MX, CX, MY, CY), st(Y, MY1, CY1, MX1, CX1)) :- opus(X, Y), modifica(1, MX, MY, MX1, MY1), modifica(1, CX, CY, CX1, CY1), sigur(MX1, CX1), sigur(MY1, CY1).
% muta un misionar succ(st(X, MX, CX, MY, CY), st(Y, MY1, CY, MX1, CX)) :- opus(X, Y), modifica(1, MX, MY, MX1, MY1), sigur(MX1, CX), sigur(MY1, CY).
% muta un canibal succ(st(X, MX, CX, MY, CY), st(Y, MY, CY1, MX, CX1)) :- opus(X, Y), modifica(1, CX, CY, CX1, CY1), sigur(MX, CX1), sigur(MY, CY1).

% modifica(+Cati, +NrInit1, +NrInit2, -NrRez1, -NrRez2) modifica(N, NX, NY, NX1, NY1) :- NX >= N, NX1 is NX - N, NY1 is NY + N.

% Afiseaza solutia
% Predicatul scrie din capitolul precedent se redefineste astfel: scrie(st(B, MX, CX, MY, CY)) :- nl, scrielista(aB, ' ', MX, ' ', CX, ' ', MY, ' ', CYi). scrielista(ai). scrielista(aX | Resti) :- write(X), scrielista(Rest).
Rezolvarea problemei este acum imediata folosind schemele de cautare din capitolul precedent. Selectia predicatului rezbkt conduce la o rezolvare echivalenta cu cea prezentata in sectiunea 10.2.
% Se alege strategia dorita (nivel, adancime sau backtracking) solutie :- nl, initial(Si), rezbreadth(Si).
% rezdepth(st(est, 3, 3, 0, 0)).
% rezbkt(Si).
Pentru a aplica o strategie A* se fixeaza implicit costuri de 1 pentru fiecare tranzitie intre doua stari si trebuie definita o functie euristica admisibila. Se noteaza cu Ne numarul persoanelor de pe un anumit mal (misionari plus canibali) in starea S si se definesc urmatoarele trei functii euristice : h1(S) = nE(S), numarul de persoane de pe malul de est in starea S h2(S) = nE(S) ? 2 nE(S) + 1, daca barca este la vest si nE(S) ? 0 h3(S) = nE(S) - 1, daca barca este la est si nE(S) ? 0
0 daca nE(S) = 0
Functia h1 nu este admisibila, functiile h2 si h3 sunt admisibile si monotone, cu h3 functie euristica mai informata decat h2. Pentru a rezolva problema cu algoritmul A* se defineste, de exemplu, functia h3 in Prolog, se pastreza specificatiile anterioare ale problemei si se foloseste strategia de cautare informata definita in sectiunea 11.4. Solutia obtinuta este minima (optima) in termeni de numar de tranzitii de stare.
% Functia euristica h3 euristic(st(est, MX, CX, _ , _ ), Sfin, H) : - final(Sfin), Ne is MX + CX, (Ne \= 0, !, H is Ne - 1; H = 0). euristic(st(vest, _ , _ , MY, CY), Sfin, H) : - final(Sfin), Ne is MY + CY, (Ne \= 0, !, H is Ne + 1; H=0).
% Rezolvare solutie :- nl, initial(Si), final(Sfin), rezastar(Si, Sfin).
12.2 Problema mozaicului cu opt cifre
Problema mozaicului cu opt cifre consta in gasirea mutarilor de executat pentru a ajunge dintr o configuratie initiala a mozaicului intr-o configuratie finala. O configuratie finala poate fi cea prezentata in figura 11.
1 2 3
8 4
7 6 5
Figura 11. O configuratie finala a mozaicului cu opt cifre
Aceasta problema, desi aparent simpla, are un spatiu de cautare foarte mare in cazul general si este un bun exemplu ce pune in evidenta utilitatea folosirii functiilor euristice de ghidare a cautarii. In sectiunile ce urmeaza vom arata cum se rezolva problema cu diverse strategii si vom pune in evidenta incapacitatea strategiilor de cautare neinformate de a gasi solutia pentru multe din configuratiile initiale propuse. Va sugeram sa testati, pentru diverse pozitii initiale, care metode reusesc si care nu. Proprietatile importante care determina esuarea unor metode si reusita altora sunt numarul de stari generate, numarul de apeluri recursive si numarul de mutari care rezolva problema.
Problema nu contine costuri dar, daca ne intereseaza rezolvarea mozaicului printr-un numar minim de miscari (tranzitii de stare) se poate considera costul tuturor tranzitiilor egal cu 1. Pentru rezolvarea problemei printr-un algoritm A* se pot defini urmatoarele functii euristice alternative aBra88i:
1) h1(S) = numarul de cifre care nu sunt la locul lor in starea S fata de starea finala;
2) h2(S) = suma distantelor, pe orizontala si verticala, la care se afla cifrele in starea S fata de pozitia lor finala (distanta Manhattan);
3) h3(S) = h2(S) + 3 ? D(S), unde D(S) este suma din d(c) pentru fiecare cifra c, mai putin ultima, in starea S. Functia d(c) se calculeaza astfel:
• Daca c este pe pozitia in care se va afla in final spatiul liber, atunci d(c) = 1;
• Daca c este pe pozitia p, iar c + 1 se afla pe pozitia p + 1, atunci d(c) = 0;
• Daca c este pe pozitia p, iar c + 1 nu se afla pe pozitia p + 1, atunci d(c) = 2.

Functiile h1 si h2 sunt admisibile, h2 fiind mai informata decat h1 deoarece incearca sa surprinda si dificultatea structurala a configuratiei initiale. Functia h3 nu este admisibila deoarece in unele situatii este mai mare decat h* (distanta reala). Ea este utila deoarece este mai informata decat h2 si ajunge mult mai repede la o solutie buna, chiar daca solutia nu este optima (solutia este destul de aproape de solutia optima). Asa cum se va vedea mai departe, h3 este singura functie care poate rezolva problema pentru anumite configuratii initiale.
In continuare se va prezenta rezolvarea acestei probleme prin trei metode neinformate, backtracking, parcurgere in adancime, parcurgere pe nivel, apoi rezolvarea pe baza algoritmului A*, utilizand functiile h1, h2 si h3.
Se va vedea ca o cautare in adancime functioneaza pana la maxim 2 3 mutari necesare pentru rezolvarea problemei, cautarea pe nivel poate ajunge pana la 5 6 mutari si A* cu h1 pana la 8 9 mutari, cu h2 pana la 18 20 de mutari, iar cu h3 chiar pana la 25 de mutari.
12.3 Rezolvarea problemei mozaicului prin cautari neinformate
O prima posibilitate de reprezentare a starilor problemei ar fi printr-o lista de perechi, o pereche fiind de forma apozitie, cifrai, unde pozitie este pozitia pe tabla (de exemplu p1,...p9) iar cifra este cifra existenta intr-o anumita stare pe acea pozitie. Astfel, starea finala s-ar specifica in Prolog prin: final(aap1,1i,ap2,2i,ap3,3i,ap4,8i,ap5,bli,ap6,4i,ap7,7i,ap8,6i,ap9,5ii)
O astfel de reprezentare este mai intuitiva si mai convenabila pentru o afisare frumoasa a solutiei dar este ineficienta pentru prelucrare. Din acest motiv vom folosi o reprezentare diferita, respectiv o lista ordonata de tipul:
apozitie_blanc, pozitie_cifra1, ..., pozitie_cifra9i de exemplu, pentru starea finala, avem definitia: final(a5, 1, 2, 3, 6, 9, 8, 7, 4i).
Pentru a putea testa problema pe mai multe stari initiale, predicatul initial va avea un paramentru suplimentar, respectiv numarul unei stari initiale. In continuare se definesc starile initiale alternative, starea finala, tranzitiile de stari si un predicat de afisare "frumoasa" a mozaicului.
% Definirea problemei mozaicului cu 8 cifre
% Stare initiala 1 - merge cu orice strategie initial(s1, a1, 4, 2, 3, 6, 9, 8, 7, 5i).
% Stare initiala 2 - merge cu orice strategie initial(s2, a3, 4, 1, 2, 6, 9, 8, 7, 5i).
% Stare initiala 3 - merge cu parcurgere pe nivel si in adancime, dar nu cu bkt initial(s3, a5, 1, 6, 2, 3, 9, 8, 7, 4i).
% Stare initiala 4 - merge cu parcurgere pe nivel, nu merge cu adancime si bkt initial(s4, a8, 4, 1, 3, 6, 9, 5, 7, 2i).
% Stare initiala 4.1 - merge cu nivel si adancime, dar nu cu bkt initial(s5, a5, 1, 6, 2, 3, 9, 8, 7, 4i).
% Stare initiala 6 - nu merge cu nici o strategie neinformata initial(s6, a9, 4, 2, 6, 8, 5, 1, 3, 7i).
% Stare initiala 7 - nu merge cu nici o strategie neinformata initial(s7, a2, 4, 5, 6, 3, 9, 8, 7, 1i).
% Stare finala final(a5, 1, 2, 3, 6, 9, 8, 7, 4i).

% muta(+Tabla, -TablaNoua, +Sens) - muta cifra care se poate muta in sensul Sens muta(Tabla, TablaN, Sens) :-
Tabla = aPoz | Resti, detlist(Sens, L), not member(Poz, L), calc(Poz, Poz1, Sens), repl(Poz1, Poz, Rest, Rest1),
TablaN = aPoz1 | Rest1i, !.

% succ(+Tabla, -TablaNoua) - determina urmatoarea stare a tablei succ(S, S1) :- (muta(S, S1, stg); muta(S, S1, dr); muta(S, S1, sus); muta(S, S1, jos)).

% detlist determina pozitiile din care nu se poate muta in Sens detlist(stg, a1, 4, 7i) :- !. detlist(dr, a3, 6, 9i) :- !. detlist(sus, a1, 2, 3i) :- !. detlist(jos, a7, 8, 9i).

% calc(+Poz, -Poz1, +Sens) - calculeaza noua pozitie dupa mutare in Sens calc(Poz, Poz1, stg) :- !, Poz1 is Poz-1. calc(Poz, Poz1, dr) :- !, Poz1 is Poz+1. calc(Poz, Poz1, sus) :- !, Poz1 is Poz-3. calc(Poz, Poz1, jos) :- !, Poz1 is Poz+3.

% repl - actualizeaza pozitia pe tabla repl(Poz1, Poz, aPoz1 | Resti, aPoz | Resti) :- !. repl(X, X1, aY | Resti, aY | Rest1i) :- repl(X, X1, Rest, Rest1).

% Afisare poza(I) :- pozitie(1, I, V1), pozitie(2, I, V2), pozitie(3, I, V3), pozitie(4, I, V4), pozitie(5, I, V5), pozitie(6, I, V6), pozitie(7, I, V7), pozitie(8, I, V8), pozitie(9, I, V9), nl, tab(10), write(V1), write(' '), write(V2), write(' '), write(V3), nl, tab(10), write(V4), write(' '), write(V5), write(' '), write(V6), nl, tab(10), write(V7), write(' '), write(V8), write(' '), write(V9), nl. pozitie(X, I, V) :- poz(X, I, 0, N), (N = 0, !, V = ' '; V = N). poz(X, aX | _ i, N, N) :- !. poz(X, aY | Resti, N, NR) :- N1 is N+1, poz(X, Rest, N1, NR).

Predicatul poza(I) permite afisarea sub forma de mozaic a unei stari. El poate fi folosit in afisarea solutiei definind predicatul scrie(S) astfel: scrie(S) :- poza(S).
La cautarea in adancime se fac foarte multe mutari pana la starea finala. Din aceasta cauza nu se poate folosi pentru orice configuratie initiala afisarea cu predicatul poza (este generata eroarea Not enough stack) si este necesara pastrarea variantei initiale de definire a lui scrie in care afisarea starilor se va face sub forma de lista, cu semnificatia definita in sectiunea precedenta.
Solutia problemei, pentru o stare initiala, NrS, fixata dintre cele definite (s1, s2,...), se obtine astfel: solutie(NrS) :- initial(NrS, Si), poza(Si), rezbreadth(Si).
% rezdepth(Si).
% rezbkt(Si).
12.4 Rezolvarea problemei mozaicului cu A*
Se pastreaza reprezentarea starilor problemei descrisa in sectiunea precedenta, se utilizeaza schema de rezolvare cu algoritmul A* prezentata in capitolul 11 si se definesc trei variante de predicate pentru calculul functiei euristice, conform celor trei functii euristice discutate in sectiunea 12.2. Functia euristica h1 se calculeaza astfel:
% euristic(+S, -H) - corespunzatoare functiei h1 euristic(S, H) :- final(Sf), calc(S, Sf, 0, H). calc(ai, _ , HR, HR) :- !. calc(S, Sf, H, HR) :- S = aPoz | Resti, Sf = aPoz1 | Rest1i,
(Poz = Poz1, N = 0; Poz\ = Poz1, N = 1),
H1 is H+N, calc(Rest, Rest1, H1, HR).
Functia euristica h2, distanta Manhattan, se calculeaza astfel:
% euristic(+S, +H) - corespunzatoare functiei h2 euristic(S, H) :- final(Sf), S = a _ | Resti, Sf = a _ | Rest1i, calc(Rest, Rest1, 0, H).
% calc(+R, +R1, +ValInit, -H) calc(ai, _ , H, H) :- !. calc(S, Sf, H, HR) :- S = aPoz | Resti, Sf = aPoz1 | Rest1i, lincol(Poz, L, C), lincol(Poz1, L1, C1),
(L> = L1, !, D1 is L-L1; D1 is L1-L),
(C> = C1, !, D2 is C-C1; D2 is C1-C),
Manh is D1+D2, H1 is H+Manh, calc(Rest, Rest1, H1, HR).

Pentru calculul functiei h3 se aduga la h2 valoarea 3 * D(S), cu D calculata de predicatul dep(S,D).
% Daca se adauga la h2 si 3*D se obtine h3 e-adimisibila
% euristic(+S, +H) - corespunzatoare functiei h3 euristic(S,H): final(Sf), S = a _ | Resti, Sf = a _ | Rest1i, calc(Rest, Rest1, 0, H1), dep(Rest,D), H is H1+ (3 * D).

calc(ai, _ , H, H) :- !. calc(S, Sf, H, HR) :- S = aPoz | Resti, Sf = aPoz1 | Rest1i, lincol(Poz, L, C), lincol(Poz1, L1, C1),
(L> = L1, !, D1 is L-L1; D1 is L1-L),
(C> = C1, !, D2 is C-C1; D2 is C1-C),
Manh is D1+D2, H1 is H+Manh, calc(Rest, Rest1, H1, HR).

dep(S, D) :- dep(S, 0, D). dep(aPi, D, D). dep(aP, P1 | Resti, D, DR) :-
(P = 5, !, D1 = 1; urm(P, U), (P1 = U, !, D1 = 0;D1 = 2)),
D2 is D+D1, dep(aP1 | Resti, D2, DR).

% functii ajutatoare div(X, Y, R) :- div(X, Y, 0, R). div(X, Y, N, N) :- (X = 0; X < Y), !. div(X, Y, N, NR) :- X > = Y, X1 is X-Y, N1 is N+1, div(X1, Y, N1, NR).
% P mod 3 = 0 atunci Coloana = 3, Linie = P div 3
% P mod 3 \= 0 atunci Coloana = P mod 3, Linie = P div 3+1 lincol(P, L, C) :- T is P mod 3,
(T = 0, !, C = 3, div(P, 3, L);
C = T, div(P, 3, L1), L is L1+1).

urm(1, 2). urm(2, 3). urm(3, 6). urm(4, 1). urm(6, 9). urm(9, 8). urm(8, 7). urm(7, 4).
%% Stare initiala 1 initial(s1,a1,4,2,3,6,9,8,7,5i).
%% Stare initiala 2 initial(s2,a3,4,1,2,6,9,8,7,5i).
%% Stare initiala 3 initial(s3,a5,1,6,2,3,9,8,7,4i).
%% Stare initiala 4 - merge cu h1, h2, h3 initial(s4,a8,4,1,3,6,9,5,7,2i).
%% Stare initiala 5 - merge cu h2, h3, nu merge cu h1 initial(s5,a5,2,1,9,4,8,3,7,6i).
%% Stare initiala 6 - merge numai cu h3 initial(s6,a9,4,2,6,8,5,1,3,7i).
%% Stare initiala 7 - merge numai cu h3 initial(s7,a2,4,5,6,3,9,8,7,1i).
Rezolvarea problemei se obtine astfel (atentie ! se alege numai una dintre cele trei definitii posibile pentru predicatul euristic, corespunzatoare lui h1 sau h2 sau h3): solutie(NrS): initial(NrS,Si), poza(Si), rezastar(Si).
Pentru exemplificarea performantelor strategiilor de cautare (neinformate si informate) discutate in acest capitol se prezinta rezultatele obtinute pentru sapte stari initiale in problema mozaicului cu opt cifre (D. s. inseamna depasirea stivei), in figura 12.
Si Poza Strategii de cautare neinformate Cautare informata cu A*
Nivel Adancime BKT A* - h1 A* - h2 A* - h3

Si 1 2 3 2 mutari 30 mutari 30 mutari 2 mutari 2 mutari 2 mutari
1 8 4 5 apeluri 28 apeluri 28 apeluri 2 apeluri 2 apeluri 2 apeluri
7 6 5

Si 2 2 3 4 mutari 4 mutari 4 mutari 4 mutari 4 mutari 4 mutari
1 8 4 15 apeluri 4 apeluri 4 apeluri 5 apeluri 4 apeluri 4 apeluri
7 5 5

Si 3 1 3 4 4 mutari 30 mutari Nu merge. 4 mutari 4 mutari 4 mutari
8 2 26 apeluri D. s. 5 apeluri 4 apeluri 4 apeluri
7 6 5

Si 4 2 8 3 5 mutari D.s. D. s. 5 mutari 5 mutari 5 mutari
1 6 4 57 apeluri 163 apeluri 338 apeluri 6 apeluri 5 apeluri 5 apeluri
7 5

Si 5 2 1 6 D. s. D. s. D. s. D. s. 18 mutari 18 mutari
4 8
7 5 3

Si 6 6 2 7 D. s. D. s. D. s. D. s. D. s. 23 mutari
1 5 3 74 apeluri 163 apeluri 124 apeluri
8 4

Si 7 8 4 D. s. D. s. D. s. D. s. D. s. 22 mutari
1 2 3 74 apeluri 163 apeluri 84 apeluri
7 6 5

Figura 12. Performantele strategiilor de cautare in problema mozaicului
12.5 Exercitii propuse
EP1. Sa se implementeze problema misionarilor si canibalilor folosind un algoritm A* bazat pe functia euristica h2.
EP2. Sa se extinda problema misionarilor si a canibalilor pentru N misionari, N canibali si capacitatea barcii de M persoane. Sa se rezolve aceasta problema prin strategii de cautare neinformate si informate si sa se faca o analiza comparativa a performantelor metodelor, de tipul celei din figura 12.
EP3. Sa se foloseasca schemele generale de cautare pentru rezolvarea problemei maimutei si a bananei prezentata in capitolul 4.
EP4. Sa se foloseasca cautari informate si neinformate pentru rezolvarea problemei taranului (10.1); se va defini o functie euristica adecvata. Se va propune, de asemenea, o reprezentare a starilor problemei alternativa celei din sectiunea 10.1.
EP5. Sa se modifice implementarile rezolvarii problemei mozaicului astfel incat sa se afiseze statisticile prezentate in figura 12.
EP6. Sa se aplice algoritmul A* cu costuri explicite (dezvoltat in cadrul exercitiului propus 4 din capitolul 11) pentru rezolvarea problemei comis-voiajorului.
13 Strategii de cautare aplicate la jocuri
In aceasta sectiune se discuta strategii de cautare specifice unui joc ce implica doi adversari. Strategia de cautare necesara in acest caz este mai complicata datorita existentei adversarului ostil si imprevizibil in mutari. Exista doua tipuri de jocuri: jocuri in care spatiul de cautare poate fi investigat exhaustiv si jocuri in care spatiul de cautare nu poate fi investigat complet deoarece este prea mare.
13.1 Algoritmul Minimax pentru spatii de cautare investigate exhaustiv
In procesul de cautare trebuie luate in considerare miscarile posibile ale adversarului. Se presupune ca oponentul are acelasi cunostinte despre spatiul de cautare ca si jucatorul si ca foloseste aceste cunostinte pentru a castiga. Algoritmul minimax implementeaza o strategie de cautare bazata pe aceasta presupunere. In prezentarea algoritmului, ne vom situa pe pozitia unuia din cei doi participanti, ales arbitrar si numit jucator, celalat participant fiind numit adversar sau oponent.
Jucatorul este referit ca MAX iar adversarul sau ca MIN. MAX incearca sa castige maximizandu si avantajul, iar MIN incearca sa castige minimizand avantajul lui MAX. Se presupune ca MIN va muta intotdeauna in configuratia care este cea mai defavorabila pentru MAX in acel moment.
Pe parcursul jocului se genereaza spatiul de cautare ce contine ca noduri configuratiile posibile ale jocului iar ca tranzitii intre acestea mutarile posibil de executat. Pentru implementarea cautarii se eticheteaza fiecare nivel din spatiul de cautare cu MAX sau cu MIN, dupa cum miscarea este facuta de jucator sau de adversar. Se genereaza tot spatiul de cautare si fiecare nod terminal este evaluat la scorul configuratiei terminale corespunzatoare; de exemplu 1 daca este o configuratie castigatoare pentru MAX si 0 daca este necastigatoare (este castigatoare pentru MIN). Se pot asocia si valori (pozitive) de castig pentru jucator in fiecare nod terminal, corespunzatoare punctajului obtinut de acesta la sfarsitul jocului. Apoi se propaga aceste valori in sus in graf, la nodurile parinti, dupa urmatoarele reguli:
1. daca nodul parinte este MAX atunci i se atribuie valoarea maxima a succesorilor sai;
2. daca nodul parinte este MIN atunci i se atribuie valoarea minima a succesorilor sai.
Valoarea asociata astfel fiecarei stari descrie cea mai buna valoare pe care jucatorul poate spera sa o atinga (presupunand ca oponentul joaca conform algoritmului minimax). Valorile obtinute sunt folosite pentru a alege intre diverse mutari posibile. Un exemplu de spatiu de cautare Minimax este prezentat in figura 13.

Figura 13. Un posibil spatiu de cautare Minimax
Fie urmatorul joc (NIM): Mai multe bete se pun pe masa intr o gramada initiala. Fiecare participant trebuie sa imparta cate o gramada in doua gramezi cu un numar diferit de bete. De exemplu, daca initial sunt 6 bete, acestea pot fi impartite 5 1 sau 4 2, dar nu 3 3. Primul jucator care nu mai poate face nici o miscare pierde. Spatiul de cautare pentru configuratia initiala de 7 bete este prezentat in figura 14.

Figura 14. Spatiul de cautare Minimax pentru Nim cu 7 bete
Se observa ca daca incepe MIN, jucatorul MAX poate castiga intotdeauna jocul, deoarece orice miscare initiala a lui MIN duce intr o stare din care MAX poate castiga daca joaca bine.
13.2 Algoritmul Minimax cu adancime de cautare finita
Daca nu se poate investiga exhaustiv spatiul de cautare, se aplica algoritmul minimax. pana la o adancime finita, arbitrar prestabilita. Configuratiile aflate la aceasta adancime sunt considerate stari terminale. Deoarece ele nu sunt (de cele mai multe ori) stari terminale, deci de sfarsit de joc, punctajul asociat acestora se estimeaza pe baza unei functii euristice care indica cat de promitatoare este o astfel de stare pentru castigul jucatorului.
De pe fiecare nivel curent se cauta pe urmatoarele n nivele ale spatiului. Valoarea care se atribuie unui nod in urma investigarii a n nivele sub el si folosind functia euristica nu este o indicatie daca se castiga sau se pierde, ci o estimare euristica a celei mai bune stari la care se poate ajunge in n miscari de la nodul dat. Descrierea algoritmului in aceasta abordare este:
Descriere Minimax( S ) pentru fiecare succesor Sj al lui S (obtinut printr-o mutare opj) executa val( Sj ) ? Minimax( Sj ) aplica opj pentru care val( Sj ) este maxima sfarsit
Minimax( S ) A intoarce o estimare a starii S S daca nivel( S ) = n atunci intoarce eval( S ) altfel daca MAX muta in S atunci pentru fiecare succesor Sj al lui S executa val( Sj ) ? Minimax( Sj )
intoarce max( val( Sj ), ?j ) altfel A MIN muta in S S pentru fiecare succesor Sj al lui S executa val( Sj ) ? Minimax( Sj )
intoarce min( val( Sj ), ?j ) sfarsit
Pentru a da un exemplu de functie de estimare, sa consideram jocul de Tic Tac Toe (X si O). Alegem o functie de estimare euristica eval( S ) ce incearca sa masoare conflictul existent in joc in starea S. Valorea eval( S ) este numarul total posibil de linii castigatoare ale lui MAX in starea S din care se scade numarul total posibil de linii castigatoare ale lui MIN in starea S. Prin linie castigatoare se intelege o linie orizontala, verticala sau diagonala care a fost, este doar partial sau poate fi completata numai cu X sau numai cu O. Daca S este o stare din care MAX poate face o miscare cu care castiga, atunci eval( S ) = ? (o valoare foarte mare), iar daca S este o stare din care MIN poate castiga cu o singura mutare, atunci eval( S ) = -? (o valoare foarte mica). Un exemplu este prezentat in figura 15.
X X are 6 linii castigatoare posibile
O are 5 linii castigatoare posibile
O eval( S ) = 6 - 5 = 1
Figura 15. Functia euristica de evaluare a unei stari in jocul Tic Tac Toe
Dezavantajul abordarii cu adancime de cautare finita egala cu n este acela ca poate sa apara efectul de orizont, adica la nivelul n se neglijeaza cai care la nivelul (n + 1) ar putea fi mai bune. Efectul de orizont poate fi partial inlaturat daca se investigheaza inainte anumite stari care par a fi foarte promitatoare. Astfel, anumite stari cheie (de exemplu captura unei piese) se investigheaza la nivele suplimentare. De obicei se pune o limita de timp si se investigheaza iterativ nivele din ce in ce mai mari pana cand se atinge limita de timp impusa.
Prezentam in continuare implementarea in Prolog a acestui algoritm si aplicarea lui la jocul de Tic Tac Toe (X si O):
% Implementarea algoritmului Minimax
% Partea independenta de jocul particular

% Predicatul minimax: minimax(+Poz, -CelMaiBun, -Val)
% Poz este pozitia considerata, Val este valoarea sa minimax.
% Cea mai buna mutare este intoarsa in CelMaiBun

minimax(Poz, CelMaiBun, Val) :-
% PozList = lista mutarilor posibile din pozitia Poz mutari(Poz, aPrim | PozListi), !, minimax(Prim, _ , VPrim), bun(Poz, PozList, Prim, VPrim, CelMaiBun, Val). minimax(Poz, _ , Val) :- valstatic(Poz, Val). % Poz nu are succesori

bun(Curenta, ai, Poz, Val, Poz, Val) :- !. bun(Curenta, aPoz | PozListi, PozCurenta, ValCurenta, PozBuna, ValBuna) :- minimax(Poz, _ , Val), bun_dela(Curenta, Poz, Val, PozCurenta, ValCurenta, PozNoua, ValNoua), bun(Curenta, PozList, PozNoua, ValNoua, PozBuna, ValBuna).

bun_dela(Curenta, Poz0, Val0, Poz1, Val1, Poz0, Val0) :- muta_min(Curenta), Val0 < Val1, !. bun_dela(Curenta, Poz0, Val0, Poz1, Val1, Poz0, Val0) :- muta_max(Curenta), Val0 > Val1, !. bun_dela(Curenta, Poz0, Val0, Poz1, Val1, Poz1, Val1).

% Jocul X si 0
% O pozitie se memoreaza astfel: pos(x, ax, b, 0, b....i, 3) unde
% x = jucatorul care muta curent
% a...i este ceea ce se gaseste in tabla, pe linii
% 3 reprezinta cate mutari se mai fac in adancime, maxim, in minimax

% Generatorul de mutari posibile mutari(Poz, PozList) :- bagof(P, mutare(Poz, P), PozList). mutare(pos(P, Tabla, N), pos(O, Tabla1, N1)) :-
N > 0, not(final(Tabla, _ )), opus(P, O), N1 is N - 1, subst(Tabla, P, Tabla1).

opus(x, 0). opus(0, x). subst(ab | Resti, P, aP | Resti). subst(aX | Resti, P, aX | Rest1i) :- subst(Rest, P, Rest1).

% Evaluarea statica valstatic(pos( _ , B, N), Val) :- final(B, P), !, castigator(P, N, Val). valstatic(pos( _ , Tabla, _ ), Val) :- lin1(Tabla, L1), lin2(Tabla, L2), lin3(Tabla, L3), col1(Tabla, C1), col2(Tabla, C2), col3(Tabla, C3), dia1(Tabla, D1), dia2(Tabla, D2),
Val is L1 + L2 + L3 + C1 + C2 + C3 + D1 + D2.

final(aP, P, P | _ i, P) :- P \= b, !. final(a _ , _ , _ , P, P, P | _ i, P) :- P \= b, !. final(a _ , _ , _ , _ , _ , _ , P, P, Pi, P) :- P \= b, !. final(a P, _ , _ , P, _ , _ , P | _ i, P) :- P \= b, !. final(a _ , P, _ , _ , P, _ , _ , P | _ i, P) :- P \= b, !. final(a _ , _ , P, _ , _ , P, _ , _ , Pi, P) :- P \= b, !. final(aP, _ , _ , _ , P, _ , _ , _ , Pi, P) :- P \= b, !. final(a _ , _ , P, _ , P, _ , P | _ i, P) :- P \= b, !. final(Tabla, b) :- not(member(b, Tabla)).

castigator(x, N, Val) :- !, Val is -10 * (N + 1). castigator(0, N, Val) :- !, Val is 10 * (N + 1). castigator( _ , _ , 0).

lin1(ab, b, b | _ i, 1) :- !. lin1( _ , 0). lin2(a_ , _ , _ , b, b, b | _ i, 1) :- !. lin2( _ , 0). lin3(a _ , _ , _ , _ , _ , _ , b, b, bi, 1) :- !. lin3( _ , 0).

col1(a b, _ , _ , b, _ , _ , b | _ i, 1) :- !. col1( _ , 0). col2(a _ , b, _ , _ , b, _ , _ , b | _ i, 1) :- !. col2( _ , 0). col3(a _ , _ , b, _ , _ , b, _ , _ , bi, 1) :- !. col3( _ , 0).

dia1(a b, _ , _ , _ , b, _ , _ , _ , bi, 1) :- !. dia1( _ , 0). dia2(a _ , _ , b, _ , b, _ , b | _ i, 1) :- !. dia2( _ , 0).

%Tipul nodului (min sau max) muta_min(pos(x, _ , _ )). muta_max(pos(0, _ , _ )).

% Jocul efectiv run :- primul(P), adancime(N), initial(Tabla), scrie_tabla(Tabla), joc(pos(P, Tabla, N)).

primul(P) :-
write($Incepe un nou joc...$), nl, write($Eu sunt cu 0, tu esti cu x$), nl,
write($Cine incepe (x/0)? $), read(P).

adancime(N) :- write($Numarul de semi-mutari adancime? $), read(N).

initial(ab, b, b, b, b, b, b, b, bi).

joc(pos(P, Tabla, _ )) :- final(Tabla, P1), !, scrie_castig(P1). joc(pos(x, Tabla, N)) :- !, det_mutare(Tabla, Succ), scrie_tabla(Succ), joc(pos(0, Succ, N)). joc(pos(0, Tabla, N)) :- minimax(pos(0, Tabla, N), pos(x, Succ, _ ), Val), scrie_mutare(Succ, Val), joc(pos(x, Succ, N)).

scrie_castig(b) :- !, write($Remiza.$), nl. scrie_castig(x) :- !, write($Ai castigat.$), nl. scrie_castig(_ ) :- write($Ai pierdut.$), nl.

det_mutare(Tabla, Succ) :- repeat, det_coord(L, C), N is L * 3 + C, verifica(N, Tabla, Succ), !.

scrie_mutare(Tabla, Val) :-
write($Mutarea mea este: $), nl, scrie_tabla(Tabla), write($Punctaj: $), write(Val), nl, anunta(Val).

anunta(10) :- !, write($Acum sunt sigur ca voi castiga.$), nl. anunta(_ ).

det_coord(L, C) :-
write($Linia si coloana? $), read(L1), read(C1), L is L1 - 1, C is C1 - 1.

verifica(0, ab | Resti, ax | Resti) :- !. verifica(N, aX | Tablai, aX | Succi) :- N1 is N - 1, verifica(N1, Tabla, Succ).

scrie_tabla(Tabla) :- repl(Tabla, ' ', aE1, E2, E3, E4, E5, E6, E7, E8, E9i),
write($ 1 2 3$), nl,
write($1 $), write(E1), write($ $), write(E2), write($ $), write(E3), nl,
write($2 $), write(E4), write($ $), write(E5), write($ $), write(E6), nl,
write($3 $), write(E7), write($ $), write(E8), write($ $), write(E9), nl.

% Predicate de uz general repeat. repeat :- repeat.

member(X, aX | _ i). member(X, a_ | Resti) :- member(X, Rest).

repl(ai, _ , ai) :- !. repl(ab | Resti, X, aX | Rest1i) :- !, repl(Rest, X, Rest1). repl(aE | Resti, X, aE | Rest1i) :- repl(Rest, X, Rest1).
13.3 Algoritmul taierii alfa beta
Este posibil sa se obtina 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 taiere (pruning).
Pentru a ilustra ideea acestui algoritm, se considera spatiul de cautare din figura 13, redesenat in figura 16.

Figura 16. Taierea alfa-beta a spatiului de cautare
Se observa ca, odata gasit succesorul H cu valoarea 2 al nodului C, nu mai este necesara inspectarea celorlati succesori ai nodului C, deoarece:
? Nodul C este pe un nivel de MIN si va primi o valoare mai mica sau egala cu 2;
? Pentru nodul A, care este pe un nivel de MAX, am gasit anterior succesorul B cu valoarea 3, deci A va avea o valoare mai mare sau egala cu 3, ceea ce inseamna ca nodul C devine un succesor neinteresant A (valoarea lui C este mai mica decat 3).
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:
1. 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.
2. 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.
Deci algoritmul exprima o relatie intre nodurile de pe nivelul n si nodurile de pe nivelul (n + 2). Daca jucatorul MAX are posibilitatea sa ajunga la un nod m care este mai bun decat nodul curent de pe nivelul n, atunci intr un joc real, nodul de pe nivelul n nu poate fi niciodata considerat, asa cum se vede din figura 17. Se observa ca
A are ? = 3 (A este pe un nivel MIN, deci val( A ) nu poate fi mai mare ca 3)
B este ? taiat deoarece 5 > 3
C are ? = 3 (C este pe un nivel MAX, deci val( C ) nu va fi mai mica decat 3)
D este ? taiat deoarece O < 3
E este ? taiat deoarece 2 < 3, deci val( C ) este 3.

Figura 17. Eliminarea investigarii unor noduri in algoritmul alfa-beta
Algoritmul alfa beta consta in doua proceduri: MIN si MAX. Algoritmul incepe fie prin apelarea procedurii MAX, daca jucatorul muta primul, fie prin apelarea procedurii MIN, daca adversarul muta primul, initial ? fiind foarte mic (0) si ? foarte mare (?).
MAX(S, ?, ?) A Intoarce valoarea maxima a unei stari. S daca nivel( S ) = n atunci intoarce eval( S ) altfel pentru fiecare succesor Sj al lui S executa
? ? max(?, MIN(Sj, ?, ?)) daca ? ? ? atunci intoarce ?
intoarce ? sfarsit
MIN(S, ?, ?) A Intoarce valoarea minima a unei stari. S daca nivel( S ) = n atunci intoarce eval( S ) altfel pentru fiecare succesor Sj al lui S executa
? ? min(?, MAX(Sj, ?, ?)) daca ? ? ? atunci intoarce ?
intoarce ? sfarsit
Algoritmul alfa beta nu elimina limitarile de la Minimax, cum ar fi efectul de orizont. Avantajul sau este insa acela ca reduce numarul de noduri inspectate, permitand o crestere a nivelului de adancime in investigarea nodurilor urmatoare, n. Algoritmul devine eficient daca se face o ordonare a succesorilor in inspectare: cele mai bune miscari ale lui MAX, respectiv ale lui MIN, din punctul de vedere al lui MAX intai. De exemplu, pentru jocul de sah, unde factorul de ramificare este aproximativ egal cu 35, utilizarea algoritmului alfa-beta si o ordonare adecvata a starilor inspectate poate reduce factorul de ramificare la 6, ceea ce permite dublarea adancimii de cautare, permitand trecerea de la un nivel de novice la un nivel de expert.
Prezentam in continuare implementarea algoritmului alfa beta in Prolog si aplicarea lui in jocul de Tic Tac Toe (X si O):
% Implementarea algoritmului alfa beta
% Partea independenta de jocul particular jucat

alfabeta(Poz, Alfa, Beta, SucBun, Val) :- mutari(Poz, aP1 | LPozi), !, alfabeta(P1, Alfa, Beta, _ , V1), nou(Alfa, Beta, P1, V1, NAlfa, NBeta), bunsucc(LPoz, NAlfa, NBeta, P1, V1, SucBun, Val). alfabeta(Poz, Alfa, Beta, SucBun, Val) :- valstatic(Poz, Val).

bunsucc(ai, _ , _ , P1, V1, P1, V1) :- !. bunsucc(aPoz | LPozi, Alfa, Beta, Poz1, Val1, PozBuna, ValBuna) :- alfabeta(Poz, Alfa, Beta, _ , Val), bun_dela(Poz, Val, Poz1, Val1, Poz2, Val2), destuldebun(LPoz, Alfa, Beta, Poz2, Val2, PozBuna, ValBuna).

destuldebun(_ , Alfa, Beta, Poz, Val, Poz, Val) :- muta_min(Poz), Val > Beta, !; muta_max(Poz), Val < Alfa, !. destuldebun(LPoz, Alfa, Beta, P, Val, PozBuna, ValBuna) :- nou(Alfa, Beta, P, Val, NAlfa, NBeta), bunsucc(LPoz, NAlfa, NBeta, P, Val, PozBuna, ValBuna).

nou(Alfa, Beta, Poz, Val, Val, Beta) :- muta_min(Poz), Val > Alfa, !. nou(Alfa, Beta, Poz, Val, Alfa, Val) :- muta_max(Poz), Val < Beta, !. nou(Alfa, Beta, _ , _ , Alfa, Beta).

bun_dela(Poz, Val, Poz1, Val1, Poz, Val) :- muta_min(Poz), Val > Val1, !; muta_max(Poz), Val < Val1, !. bun_dela(_ , _ , Poz1, Val1, Poz1, Val1).

Pentru a aplica algoritmul alfa-beta la jocul Tic-Tac-Toe, singura modificare fata de implementarea prezentata in