6. JocuriMediile multiagent sunt cele in care orice agent dat va trebui sa ia in considerare actiunile altor agenti si modul in care acestia ii afecteaza propria bunastare. Imprevizibilitatea acestor agenti poate introduce multe evenimente neprevazute in procesul agentului de rezolvare a problemelor. Mediile competitive, in care scopurile agentului sunt in conflict, dau nastere problemelor de cautare contradictorie – adesea cunoscute ca si jocuri.6.2. Deciziile optime in jocuriSe vor considera doi jucatori pe care ii vom numi MAX si MIN din motive care vor devein evidente in curand. MAX muta primul si amandoi muta pe rand pana cand jocul se sfarseste. La sfarsitul jocului se dau puncte jucatorului care a castivat si se penalizeaza jucatorul care a pierdut. Un joc poate fi definit formal ca un fel de problema de cautare cu urmatoarele componente:-Starea initiala care include pozitia tablei si identifica jucatorul care trebuie sa mute.-O functie succesor, care returneaza o lista de perechi (mutare, stare), fiecare indicand o mutare legala si starea care rezulta prin ea.-Un test terminal care determina cand jocul se sfarseste. Starile cand jocul s-a terminat se numesc stari terminal.-O functie de utilitate(numita si functie obiectiv) care da o valoare numerica starilor terminale. La sah rezultatul este o victorie, o infrangere sau o remiza, cu valorile +1, -1 sau 0.STRATEGIILE OPTIMEIntr-o problema de cautare normala, solutia optima ar fi o secventa de mutari care conduc la o stare obiectiv - o stare terminala care este o victorie. Intr-un joc pe de alta parte, MIN are ceva de spus despre asta. MAX, prin urmare, trebuie sa gaseasca o strategie intamplatoare, care specifica mutarea lui MAX in starea initiala, apoi mutarile lui MAX din starile care rezulta din fiecare raspuns posibil al lui MIN, apoi mutarile lui MAX in starile care rezulta din fiecare raspuns posibil al lui MIN la aceste mutari, si asa mai departe. General vorbind, o strategie optima duce la rezultate cel putin la fel de bune ca orice alta strategie atunci cand cineva joaca impotriva unui adversar infailibil.6.3 TAIEREA ALPHA-BETA6.4 DECIZII IMPERFECTE IN TIMP REALAlgoritmul minimax genereaza intreg spatial de cautare, in timp ce algoritmul alfa-beta taie parti destul de mari din el. Totusi si alfa-bta trebuie sa caute pana la starile terminale pentru o portiune din spatiu.6.5 JOCURI CARE INCLUDE ELEMENTUL DE NOROCIn viata reala sunt multe evenimente externe imprevizibile care ne pun in situatii neasteptate. Multe jocuri oglindesc aceasta imprevizibilitate prin includerea unor elemente intamplatoare cum ar fi aruncarea zarurilor. Astfel ne aduc la un pas mai aproape de realitate si merita sa vedem cum afecteaza procesul decisional.

7.2 Lumea WumpusLumea Wumpus este o pestera compusa din camere conectate prin pasaje. Ascuns undeva in pestera este wumpus, o bestie care mananca pe oricine intra in camera ei. Wumpus poate fi impuscat de catre un agent, dar agentul are o singura sageata. Unele camere contin gropi fara fund, care vor prinde pe oricine calatoreste prin aceste camere (cu exceptia lui wumpus, care este prea mare pentru a cadea in acestea). Singura trasatura atenuanta de a trai in acest mediu este posibilitatea de a gasi o gramada de aur. Desi lumea lui wumpus este destul de blanda dupa standardele locurilor pe calculator moderne, reprezinta un mediu excelent pentru testarea agentilor inteligenti. Michael Genesereth a fost primul care a sugerat acest lucru.Un model pentru lumea lui wumpus este aratat in figura 7.2. Este data definitia precisa a mediului de atribuire prin descriere PEAS.-Masura performantei: +1000 pentru luarea aurului, -1000 pentru caderea intr-o groapa sau a fi mancat dewumpus, -1 pentru fiecare actiune savarsita si -10 pentru folosirea sagetii.-Mediul: O retea 4x4 de camere. Agentul porneste intotdeauna din patratul etichetat [i,j] cu fata spre dreapta. Locatiile aurului si a wumpusului sunt alese aleator, cu distributie uniforma, dintre patratele distinct de cel de start.-Actiuni: agentul se poate misca inainte, sa se intoarca la stanga sau la dreapta cu 90 . Mersul inainte nu are effect daca in fata agentului⁰ se afla un zid. Actiunea “Grab” poate fi folosita pentru a ridica un obiect care se afla in aceeasi casuta cu agentul. Actiunea “Shoot” poate fi folosita pentru a trage o sageata in directia in care este agentul indreptat.-Senzori: Agentul are 5 senzori, fiecare dand un singur bit de informatie:--In casuta cu wumpusul si in casutele direct adiacente acesteia(nu diagonale) agentul va simti un miros urat.--In casutele direct adiacente unei gropi agentul va percepe o briza.--In casuta unde este aurul agentul va percepe o stralucire.--Cand agentul intra intr-un zid va percepe o lovitura.--Cand wumpusul este ucis emite un strigat lamentabil care se percepe in orice punct din pestera.Perceptele vor fi date agentului in forma unei liste de 5 simboluri; de exemplu daca este un miros urat si o briza dar nu si sclipire, lovitura sau tipat, agentul va primi perceptual [Stench, Breeze,None,None,None].Sintaxa logicii propozitionale defineste propozitiile acceptabile. Propozitiile atomice – elementele nedivizibile syntactic – constau intr-un singur symbol propozitional. Fiecare astfel de symbol tine locul unei propozitii care poate fi adevarata sau falsa.Propozitiile complexe sunt construite din propozitii mai simple folosind conexiuni logice. Sunt folosite 5 conexiuni comune:¬ (negare)-A (si). V (sau) => (implica). (daca si numai daca).6.5 Modele de rationament in logica propozitionalaAceasta sectiune se refera la modelele standard de deducere care pot fi aplicate pentru a obtine lanturi de concluzii care sa conduca la obiectivul dorit. Aceste modele de deducere sunt numite reguli de deductie. Regula cea mai cunoscuta este numita Modus Ponens si

este scrisa dupa cum urmeaza:α=¿ β ,α

βNotatia inseamna ca, ori de cate ori orice propozitii de forma α=>β si α sunt date, propozitia β poate fi dedusa. De exemplu, in cazul in care (WumpusAcap A WumpusAviata) => Trage si (WumpusAcap A WumpusAviata) sunt date, tunci Trage se poate deduce.O alta regula de deductie utila este SI-ELIMINAREA (And-Elimination) care spune ca, dintr-o conjunctie, oricare dintre

conjuncti se poate deduce:α∧β

αDe exemplu, de la (WumpusAcap A WumpusAviata), WumpusAviata se poate deduce.

8. LOGICA DE ORDINUL INTAIlogica de ordinul intai este suficient de expresiva pentru a reprezenta o parte buna a cunostintelor noastre comune.8.1 Reprezentarea revizuitaLimbajele de programare (ca si C++ sau Java sau Lisp) sint de departe cea mai mare clasa de limbaje formale folosite in mod curent. Programele in sine reprezinta, in mod direct, doar procese operationale. Structurile de date din cadrul programelor pot deprezenta adevaruri; de exemplu, un program poate folosi o dispunere 4x4 pentru a reprezenta continutul lumii Wumpus. Astfel, enuntul limbajului de programare World[2,2]←Pit este un mod destul de natural de a arata ca este o groapa (pit) in casuta [2,2]. Astfel de reprezentari ar putea fi considerate ad-hoc.Ce le lipseste limbajelor de programare este un mecanism general pentru derivarea faptelor din alte fapte; fiecare actualizare a unei structuri de date se face printr-o procedura specifica domeniului ale carei detalii sunt obtinute de programator din propriile cunostintele despre domeniu. Aceasta abordare procedurala poate fi contrastata cu caracterul declarativ al logicii propozitionale, in care cunostintele si deducerea sunt separate si deducerea este in intregime independenta de domeniu.Un al doilea dezavantaj al structurilor de date in cadrul programelor (si de bazelor de date) este lipsa unei modalitati usoare de a spune, de exemplu, "exista o groapa in [2,2] sau [3,1]" sau "Daca wumpus este in [1,1], atunci el nu este in [2,2]".Logica propozitionala este un limbaj declarativ, deoarece semantica sa se bazeaza pe o relatie de adevar intre propozitii si lumi posibile. Ea are de asemenea suficienta putere expresiva pentru a face fata informatiilor partiale, folosind disjunctia si negatia. Logica propozitionala are o a treia proprietate care este de dorit in limbile de reprezentare, si anume compozitionalitate. Intr-un limbaj compozitional, sensul unei propozitii este o fuinctie su sensul partilor sale componente. De exemplu, "S1,4A S1,2" este legata de semnificatiile lui „S1, 4” si „S1,2”. Ar fi foarte ciudat daca "S1, 4" ar insemna ca exista un miros urat in patratul [1,4] si "S1, 2" ar insemna ca exista un miros urat in patratul [1,2], dar "S1,4 A S1,2" ar insemna ca Franta si Polonia au remizat 1-1 in meciul de hochei de calificare de saptamana trecuta. In mod evident, ne-compozitionalitatea face viata mult mai dificila pentru sistemul de rationament.Logicii propozitionale ii lipseste puterea expresiva de a descrie concis un mediu cu mai multe obiecte. De exemplu, am fost nevoiti sa scriem o regula separata pentru brize si gropi pentru fiecare casuta. In limba engleza in schimb, pare simplu sa spunem odata si sigur „patratele adiacente gropilor au o adiere”. Sintaxa si semantica limbii engleze face posibila descrierea concisa a mediului.Principala diferenta intre logica propozitionala si cea de ordin intai consta in angajamentul ontologic al fiecarui limbaj – adica ce presupune despre natura realitatii.De exemplu, logica propozitionala presupune ca exista fapte care fie tin sau nu tin in lume. Fiecare fapt poate fi in una din cele doua stari: adevarat sau fals. Logica de ordinul intai presupune mai mult, și anume, faptul ca lumea este formata din obiecte cu anumite relatii intre ele care tin sau nu tin.8.2 Sintaxa si semantica logicii de ordinul intaiObiectele din model pot fi legate in diferite moduri. In figura, Richard si John sunt frati. Formal vorbind, o relatie este doar setul de tupluri al obiectelor care sunt legate. (Un tuplu este o colectie de obiecte aranjate intr-o ordine fixa si este scris cu paranteze unghiulare in jurul obiectelor.) Astfel, relatia de fratie in acest model este setul {(Richard Inima de Leu, regele John), (Regele John, Richard Inima de Leu)}. Coroana este pe capul regelui John, deci relatia „pe cap” contine un singur tuplu (coroana, Regele John). Relatiile „frate” si „pe capul” sunt relatii binare – adica stabilesc relatii intre perechi de obiecte.Unele tipuri de relatii sunt cel mai bine considerate ca functii in care obiecte date trebuie sa fie legate de un obiect specific. De exemplu fiecare persoana are un picior stang:(Richard inima de leu)→Piciorul stang al lui RichardUn termen este o expresie logica, care se refera la un obiect. Simbolurile constante sunt, prin urmare, termeni, dar nu este intotdeauna convenabil sa avem un simbol distinct pentru a numi fiecare obiect. De exemplu, in limba engleza am putea folosi expresia "piciorul stang al regelui John", mai degraba decat sa dam un nume piciorului. Pentru asta sunt simbolurile de functii: in loc sa folosim un simbol constant, vom folosi LeftLeg(John). In general, un termen complex este format dintr-un simbol functie urmat de o lista de termeni in paranteze ca argumente pentru simbolul functie. Este important sa ne amintim ca un termen complex este doar un fel de nume complicat. Nu este un "apel subrutina", care "returnează o valoare". Nu exista nici o subrutina LeftLeg care sa ia o persoana ca intrare si returneaza un picior.Propozitii atomice Acum, ca avem atat termeni de referire la obiecte cat si simboluri pentru referire la relatii, le putem pune impreuna pentru a forma propozitii atomice. O propozitie atomica este formata dintr-un simbol predicat, urmat de o list de termeni in paranteze: Frate(Richard, John). Prop atomice pot avea termeni complecsi ca argumente: Married(Father(Richard),Mother(John))Cuantificatori. Logica de ordinul intai contine doi cuantificatori standard, numiti universal si existentialEgalitate. Ex: Father(John)=Henry inseamna ca tatal lui John si Henry sunt 2 termeni care se refera la acelasi obiect.8.3. Folosirea logicii de ordinul intaiAcum ca am definit un limbaj logic expresiv, este timpul sa invatam cum sa il folosim. Cel mai bun mod de a face acest lucru este prin exemple. Am vazut unele propozitii simple care ilustreaza diferitele aspecte ale sintaxei logice; in aceasta sectiune, vom oferi reprezentari mai sistematice ale unor domenii simple. In reprezentarea cunostintelor, un domeniu este doar o parte a lumii despre care dorim sa exprimam anumite cunostinte.Afirmatiile si cerintele in logica de ordinul intaiPropozitiile sunt adaugate unei baze de cunostinte folosind TELL, exact ca in logica propozitionala. Astfel de propozitii sunt numite afirmatii. De ex,: TELL(KB,King(John)).Putem pune intrebari despre baza de cunostinte folosind ASK. De ex, ASK(KB,King(John)) va returna valoarea adrvarat (TRUE).