Teoria jocurilor

7x puncte

categorie: Informatica

nota: 9.00

nivel: Facultate

Referat despre Teoria jocurilor
3. Algoritmul Minimax
Algoritmul MiniMax e un algoritm de cautare intr-un arbore. Acest algoritm urmareste selectarea celei mai bune mutari pentru calculator intr-un joc cu doi jucatori. Algoritmul construieste un arbore cu toate mutarile posibile pentru ambii jucatori. Acest algoritm este denumit Minimax deoarece pur si simplu calculatorul face mutare[...]
DOWNLOAD REFERAT

Preview referat: Teoria jocurilor

Referat despre Teoria jocurilor
3. Algoritmul Minimax
Algoritmul MiniMax e un algoritm de cautare intr-un arbore. Acest algoritm urmareste selectarea celei mai bune mutari pentru calculator intr-un joc cu doi jucatori. Algoritmul construieste un arbore cu toate mutarile posibile pentru ambii jucatori. Acest algoritm este denumit Minimax deoarece pur si simplu calculatorul face mutarea care-i ofera castigul maxim, in acelasi timp asigurandu-se ca oponentul face mutarea cea mai defavorabila calculatorului.

Deoarece mutarile alterneaza, algoritmul alterneaza minimizand si maximizand nivelele arborelui de cautare in mod recursiv. Intrucat, chiar si in cazul unui joc simplu, numarul mutarilor posibile creste exponential, si deoarece in general memoria unui calculator este limitata, acest algoritm face cautarea numai pe o adancime fixa. In continuare vom considera un arbore de cautare ipotetic, ca sa studiem cum algoritmul Minimax selecteaza mutarea cea mai buna. Acest exemplu este pentru un joc in care sunt posibile exact doua mutari, iar adancimea maxima de cautare e 4. Observam ca si in acest caz cu putine mutari posibile, trebuiesc generate 30 situatii posibile.

In figura de mai sus nodurile maximizante sunt reprezentate printr-un patrat iar cele minimizante printr-un cerc. Sa presupunem ca urmatorul jucator este calculatorul si ca in acest moment al jocului arborele de cautare este cel din figura 1. Radacina arborelui ( cel mai de sus nod) este nodul curent si reprezinta pozitia actuala in joc. Observam ca din aceasta pozitie, calculatorul are numai doua mutari posibile A si B. Momentan ignoram numerele din interiorul nodurilor, le vom calcula mai tarziu.

Pentru inceput observam ca nodul curent este un nod maximizant, altfel spus, dintre mutarile A si B o vom alege pe cea care ne furnizeaza valoarea maxima. Urmatorul nivel din arborele de cautare este corespunzator mutarilor posibile celui de-al doilea jucator, sa presupunem omul. Pentru a nu complica lucrurile vom urma numai ramura A a arborelui de cautare. Omul va trebui sa aleaga acum intre mutarile C si D. Observam ca nodurile sunt reprezentate prin cercuri, asadar sunt noduri minimizante.

Asadar, vom presupune ca omul va alege mutarea care va lasa calculatorului cea mai mica valoare posibila. Si asa se va continua mai departe in mod recursiv. Cel mai simplu algoritm MiniMax e posibil ca sa evalueze recursiv toate cele 16 "frunze" ale arborelui de cautare, apoi va merge inapoi, minimizand valoarea pentru mutarile omului si maximizand mutarile calculatorului. Dupa cum observam, in exemplul nostru cea mai buna mutare pentru calculator este A deoarece valoarea din A este mai mare decat cea din B. Nodul A la randul lui este un nod minimizant, asadar va reflecta minimul dintre 10 si 14. Nodul C maximizeaza, luand valoarea cea mai mare dintre 9 si 10. Nodul G minimizeaza valorile 10 si 11, samd.

Conform celor de mai sus, nodul din coltul din stanga, evaluat la 10, este cea mai buna pozitie pe care calculatorul o poate obtine, Astfel incat daca o luam in sens invers pe arbore, de jos in sus, prin G si C si in final A care e mutarea cea mai buna pe care calculatorul o poate face in final. Valorile din interiorul nodurilor reprezinta cat de buna e pozitia actuala in cadrul jocului din punctul de vedere a calculatorului. Acest lucru pare foarte usor daca beneficiem de luxul de a cauta pana la finalul jocului, in acest caz o victorie fiind foarte buna, iar o infrangere fiind foarte rea.

Dar, de cele mai multe ori, in realitate, cautarea in adancime e limitata, iar in acest caz e se utilizeaza o functie statica de evaluare a pozitie in cadrul jocului care returneaza o valoare ce indica cat de buna e aceasta pozitie. In terminologia inteligentei artificiale, acest numar e numit euristic. In caz ca dorim sa implememtam o astfel de euristica, trebuiesc luate in considerate urmatoarele lucruri: Care sunt elementele interesante ale jocului si cum trebuie evaluate astfel incat sa determinam daca o pozitie e mai buna decat alta? Care sunt valorile relative care trebuie asignate fiecarui element? Acest lucru de multe ori necesita o sofisticat analiza a jocului in cauza si nu intotdeauna acest lucru e usor.

4. Aloritmul MinimMax cu reducere Alfa-Beta
Dupa cum am mai precizat, arborele de cautare in cazul algoritmului MiniMax poate creste foarte mult, astfel incat se utilizeaza tehnici avansate care sa limiteze timpul si resursele necesare algoritmului de cautare MiniMax. Cea mai usoara tehnica de acest gen este limitarea adancimii de cautare. O alta tehnica este asa-zisa reducere Alfa-Beta Reducerea Ala-Beta permite realizarea aceleeasi analize, dar mai eficient, fara pierdere de informatii.

In primul rand, arborele de cautare trebuie parcurs intr-o ordine predefinita, sa zicem de la stanga spre dreapta, de sus in jos, mai intai in adincime, sarind (reducand) peste toate nodurile ce nu pot influenta determinarea celei mai bune valori. Exemplificarea o vom face tot pe arborele de cautare din figura 2. Pentru inceput vom sari peste nodul J si fiii sai, nodurile tip frunza 13 si 14. Scopul explorarii parintelui nodului J este acela de a daca valoarea nodului A poate fi redusa sub 10, care este valoarea deja stabilita de fiul stang al nodului A, C. Pornind cautarea de la nodul D, mai intai vom evalua nodul I, in care vom avea valoarea 14. Acest lucru va determina ca nodul D sa aiba cel putin valoarea 14, indiferent de valoarea posibila din J.
DOWNLOAD REFERAT
« mai multe referate din Informatica

CAUTA REFERAT

TRIMITE REFERAT CERE REFERAT
Referatele si lucrarile oferite de E-referate.ro au scop educativ si orientativ pentru cercetare academica.
Confidentialitatea ta este importanta pentru noi

E-referate.ro utilizeaza fisiere de tip cookie pentru a personaliza si imbunatati experienta ta pe Website-ul nostru. Te informam ca ne-am actualizat termenii si conditiile de utilizare pentru a integra cele mai recente modificari privind protectia persoanelor fizice in ceea ce priveste prelucrarea datelor cu caracter personal. Inainte de a continua navigarea pe Website-ul nostru te rugam sa aloci timpul necesar pentru a citi si intelege continutul Politicii de Cookie. Prin continuarea navigarii pe Website-ul nostru confirmi acceptarea utilizarii fisierelor de tip cookie conform Politicii de Cookie. Nu uita totusi ca poti modifica in orice moment setarile acestor fisiere cookie urmarind instructiunile din Politica de Cookie.


Politica de Cookie
Am inteles