Cautarea si teoria jocurilor.pdf

8/18/2019 Cautarea si teoria jocurilor.pdf

1/15

31.03.201

Căutarea şi teoria jocurilor

Buzic Ioana-Adriana

Frona Alina

Necula Dan

Jocurile şi inteligenţa artificială

John von Neumann şi Oskar Morgenstern au definit jocul(1944) ca “orice interacţiune între diverşi agenţi,guvernată de un set de reguli specifice care stabilesc mutările

posibile ale fiecărui participant şi câştigurile pentru fiecare

combinaţie de mutări ”. Jocurile sunt primele domenii deaplicare a IA(performanţa uşor de măsurat, reguli simple şi

precise).Teoria jocurilor abordează problema comportamentului

optim în jocurile cu două sau mai multe persoane, într-uncadru descris de un ansamblu de reguli precise care stabilescposibilităţile de acţiune ale fiecarui jucaător, precum şimodul cum li se acorda acestora, în final, anumite valori.

Teoria jocurilor utilizează trei ipoteze fundamentale:

● jucătorii se comportă raţional ;


2/15


3/15

31.03.201

Jocuri în formă extinsă şi jocuri înformă normalizată

Există jocuri care implică elemente aleatoare numite şi şansă, care intervinatunci când se aruncă zarurile sau se extrage o carte. Toate aceste mutărisunt atribuite unui jucător „Şansă” – un jucător fictiv folosit doar pentru obună abstractizare a jocului.

Spunem ca un joc este în forma extinsă, atunci când acesta este specificatde o listă de reguli. Pentru rezolvarea matematică a unui joc, avem însănevoie de jocuri în formă normalizată. Pentru aceasta este nevoie săcunoaştem o listă completă cu toate combinaţiile de mutări legale posibile,pe care un jucător poate să le facă pentru fiecare situaţie care apare peparcursul unui joc.

Pentru jocurile de 2 jucători, cea mai simplă metodă de stocare a acestoraeste folosind matrice bidimensionale .

Dilema prizonierilor

Doi prizonieri sunt chestionaţi de poliţie. Poliţia ştie ceva dedespre ce au făcut, dar nu are toate informaţiile. Ca să afle, îibagă în doua celule separate şi îi interoghează.

Prizonierii au două opţiuni: pot spune toată povestea (adicăsă trădeze) sau pot să nu spună nimic (cooperare). Niciunprizonier nu ştie ce va spune celalalt.

• Dacă amândoi cooperează (adică tac), ambii iau sentinţăuşoară (1 an).• Dacă unul trădează şi celălalt cooperează, trădătorul e

liber, iar cel trădat primeşte 10 ani de închisoare.• Dacă ambii trădează, fiecare ia 5 ani de detenţie.


4/15

31.03.201

Vânătoarea de cerbi/iepuri

• Doi indivizi merg la vânătoare. Fiecare poatealege individual să vâneze un cerb sau uniepure şi trebuie să facă alegerea fără să ştiece a ales celalalt.

• Dacă unul alege un cerb, are nevoie de

cooperarea celuilalt ca să reuşească.• Fiecare poate vâna un iepure de unul singur,

dar un iepure valorează mai puţin decât uncerb.


5/15

31.03.201

Aplicabilitate• Economie : Dacă două companii aleg să facă reclam în o anumită

perioadă, ambele se anulează reciproc, dar costurile rămân. Cantitateade reclamă a uneia depinde direct de cantitatea de reclamă pe care oface cealaltă.

Membrii unui cartel sunt implicaţi într-un astfel de joc cu maimulti jucători. Cooperare in acest caz înseamnă să ţină preţurile la unminim prestabilit. Trădarea vine de la vânzarea sub minimul prestabilit.

• Sport : Doi ciclişti aflaţi în faţa plutonului (grupului masiv) poartă

consecutiv trena (cooperează) pentru a nu fi ajunşi din urmă. De multeori, doar unul duce trena (cooperează), iar la linia de sosire este trădat deadversar.

• Sociologie : Când cunoaştem o noua persoană, tindem să fim foarteatenţi pentru a avea o poziţie de sigurantă (competiţie). Ambii potsemnala dorinţa de a se muta de la poziţiile defensive către interacţiunesş recunoaşterea unei intenţii comune.

• Corporaţii

• Război


6/15

31.03.201

Jocul ca problemă de căutare•

Implementarea: Codificarea jocului astfel încat să fie pe înțelesul caculatorului

• Structura: jocul gândit ca un arbore ce conținetoate stările viitoare ale jocului

• Exemplu: jocul de șah cu stări ce reprezintă modul dearanjare a pieselor pe tablă, precum și cine faceurmătoarea mutare

• Stare inițială: rădăcina arborelui

• Fii arborelui: fiecare mutare posibilă executată de un

jucător, reprezentând starea jocului• Stare finală: reprezentată prin frunzele arborelui din

care nu se va mai face nici o mutare -> un jucator acastigat sau remiza

Componentele unei probleme decăutare

• Jocul privit ca o problemă de cautare ce va aveaurmătoarele componente:

• Starea iniţială, include poziţiile pe tabla de joc şi cine este lamutare.

• Mulţime de acţiuni, care definesc mutările admise pe carele poate efectua un jucător.

• Stare terminală, care determină când se sfârşeşte jocul.Stările în care jocul se încheie se numesc stări terminale.

• Funcţie de utilitate, care întoarce o valoare numericăpentru rezultatul jocului. De ex. în şah posibilităţile sunt 1pentru victorie, 0 pentru egalitate şi -1 pentru înfrângere.


7/15

31.03.201

Decizii perfecte în jocuri de douăpersoane

• Caz general două persoane MIN și MAX

• MAX este primul jucător ce va face mutareaiar apoi mutările se vor face pe rând până lasfârșitul jocului

• La sfârșit, pierzătorul este penalizat iarpunctele se atribuie jucătorului care câștigă

Descrierea formală a unui joc

• Un joc poate fi definit formal ca o problemă de căutarecu următoarele componente: – Starea initiala include pozițiile de pe tablă și cine este cel

care este la mutare.

– O mulțime de acțiuni care definesc mutările admise pecare le poate face un jucător.

– O stare terminală care determină când se sfârșeste jocul.Stările în care jocul se încheie se numesc stări terminale.

– O funcție de utilitate care întoarce o valoare numericăpentru rezultatul jocului.

– În general, posibilitățile sunt victorie, egal sau înfrângerecare pot fi reprezentate ca 1, 0 sau -1.


8/15

31.03.201

Decizii perfecte în jocuri de douăpersoane

• MAX trebuie să găsească o strategie care să îlducă la o stare terminală în care el estecâștigătorul, indiferent de ce mutări face MIN

• Strategia presupune că MAX face mutărilecorecte, indiferent de mutările lui MIN

• Ideea este de a arăta cum se găsește o

strategie optimă, chiar dacă în mod normal nueste timp suficient să o găsim.

Aplicaţia „X – O”

• Importanță – Managementul sistemelor informatice

– Abilitatea de a asocia situații spre acțiuni care săconducă la maximizarea unei recompensenumerice

– Precum în cele mai multe forme de instruire amașinilor, nu știm ce acțiuni trebuie făcute dar

încercându-le pe toate, trebuie să descoperimacțiunile ce aduc cea mai mare recompensă


9/15

31.03.201

Aplicaţia „X – O”

• Doi jucători mută pe rând folosind o tabla de joc de dimensiune 3 x 3. Unul dintre ei joacăcu „X”, iar celălalt cu „O”, până când unuldintre ei câştigă, reuşind să plaseze trei semnede-ale sale pe o linie, coloană sau diagonală.Dacă nici un jucător nu reuşeşte aceasta şitoată tabla este completată, jocul se încheie laegalitate

X și 0, reprezentarea jocului sub formăde arbore


10/15

31.03.201

1

X și 0 - reprezentare

• De la starea inițială, MAX are posibilitatea de a alege din 9stări posibile

• Jucătorii alternează punând X și 0 până când se ajunge la ostare terminală – stare în care un jucător are trei elementepe o linie, coloană sau diagonală ori toate casuțele suntcompletate

• Numărul atașat la fiecare nod frunză se referă la utilitateastării terminale pentru jucatorul MAX

• Valorile mari sunt considerate bune pentru MAX și proastepentru MIN (și invers), de aici și numele celor doi jucători

• Sarcina lui MAX este să folosească arborele de căutarepentru a determina cele mai bune mutări, ținând cont deutilitățile stărilor terminale

Definirea jocului

• Un joc poate fi definit prin:

– Starea inițială (cum sunt elementele aranjateinițial)

– Acțiunile posibile (unde sunt definite mutărilepermise)

– Un test terminal (care spune dacă jocul s-aterminat)

– O funcție de utilitate (care spune cine a caștigat șicu ce scor)


11/15

31.03.201

1

Minimax

Minimax este considerat la scară largă ca fiind algoritmulde bază în rezolvarea jocurilor, însă vom vedea că aremulte deficienţe.

În primul rând complexitatea lui este una exponenţialăceea ce-l face greu de adaptat unui joc cu multe stări cumar fi şahul sau tablele.

Un alt dezavantaj este acela că Minimax pleacă mereu dela premisa că adversarul său face cea mai bună mutareposibilă, ceea ce în multe cazuri nu se întâmplă.

Minimax (2)

Alternativa pe care o propunem acestei abordăritradiţionale este învăţarea prin întărire bazată pe diferenţa

între estimările unor sări ale jocului în diferite momente.Vom încerca să proiectăm un agent inteligent carecunoscând doar regulile de bază ale jocului, să înveţe să

joace la un nivel expert, fără a fi supravegheat de un om.Ne-am oprit la jocul Tic-Tac-Toe, unul tipic pentruabordarea Minimax, şi vom încerca să arătăm că învăţareaeste intr-adevăr o alternativă viabilă, cu cerinţe minime.


12/15

31.03.201

1

Algoritmul Minimax

Algoritmul Minimax este un algoritm de căutare într-unarbore. Acest algoritm urmăreşte selectarea celei mai bunemutări pentru calculator, într-un joc cu doi jucători. Mai întâise construieşte arborele de joc cu toate mutările posibilepentru ambii jucători.

Acest algoritm este denumit Minimax, deoarece calculatorulface mutarea care-i oferă câştigul maxim, în acelaşi timpasigurându-se că oponentul face mutarea cea mai

defavorabilă calculatorului. Deoarece mutările alternează, şialgoritmul alternează maximizând şi minimizând nivelelearborelui în mod recursiv.

Minimax

În continuare vom considera cazul unui joc simplu cudouă persoane, pe care le vom numi sugestiv MAX şiMIN. Primul care mută primul este MAX, apoi mută perând, până la sfârşitul jocului, când unul este “premiat”iar celălalt penalizat. MAX trebuie să găsească o strategiecare să îl aducă la o stare terminală în care el este

câştigătorul, indiferent de mutările pe care le face MIN.Strategia presupune că MAX face mutările corecte,indiferent de mutările lui MIN. Ideea este de a arăta cumse găseşte o strategie optimă, chiar dacă nu este timpsuficient să o găsim


13/15

31.03.201

1

Arborele de cautare

Paşii algoritmului Minimax

Algoritmul Minimax, care determină strategia optimă pentru jucătorul MAX, constă în 5 paşi:

1. Generează arborele de joc până la stările terminale

2. Aplică funcţia de utilitate pentru fiecare stare terminală,

pentru a îi determina valoarea.3. Foloseşte utilitatea stărilor terminale pentru a determina

utilitatea stărilor de la un nivel superior al arborelui.

4. Continuă evaluarea utilităţii nodurilor până ajunge larădăcină.


14/15

31.03.201

1

Paşii algoritmului Minimax (2)

5. Când se ajunge la rădăcină, MAX alegenodul de pe nivelul inferior cu valoarea ceamai mare.

Invatarea prin intarire

Idee de bază a învăţării prin întărire este următoarea: agentulcare învaţă observă nişte date sau un model de intrare, şiproduce un semnal de ieşire (numit şi acţiune sau semnal decontrol). Imediat, agentul primeşte de la mediu o recompensăsau un feed-back de întărire, care îi arată cât de bun sau cât de

rău a fost semnalul de ieşire. Scopul învăţării este de a generacele mai bune acţiuni care duc la un câştig maxim. De multe oriaceastă recompensă este întârziată, ea vine la sfârşitul uneilungi secvenţe de intrări şi ieşiri. Astfel cel care învaţă, trebuiesă figureze 33 modul în care distribuie câştigul şi penalizărilepentru diferitele intrări, ieşirile conducând spre semnalul finalde recompensă.


15/15

31.03.201

Interacţiunea dintre agent şi

mediu

Cautarea si teoria jocurilor.pdf

Documents

Transcript of Cautarea si teoria jocurilor.pdf