inteligenta artificiala: jocuri. satisfacerea constrangerilor

Click here to load reader

Post on 26-Jun-2015

288 views

Category:

Documents

10 download

Embed Size (px)

DESCRIPTION

InteligenŃă artificială3. Jocuri. Satisfacerea constrângerilorFlorin LeonUniversitatea Tehnică „Gh. Asachi” Iaşi Facultatea de Automatică şi Calculatoare http://florinleon.byethost24.com/curs_ia.htmFlorin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmJocuri. Satisfacerea constrângerilor1. 2. 3. 4. 5. 6. 7. 8. Tipuri de jocuri Algorimul minimax Retezarea alfa-beta Jocuri nedeterministe Formalizarea problemelor de satisfacere a constrângerilor Backtracking Eur

TRANSCRIPT

Inteligen artificial 3. Jocuri. Satisfacerea constrngerilor Florin Leon Universitatea Tehnic Gheorghe Asachi din Iai Facultatea de Automatic i Calculatoare http://florinleon.byethost24.com/curs_ia.htm Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm2 Jocuri. Satisfacerea constrngerilor 1. Tipuri de jocuri 2. Algorimul minimax 3. Retezarea alfa-beta 4. Jocuri nedeterministe 5. Formalizarea problemelor de satisfacere a constrngerilor 6. Backtracking 7. Euristici de optimizare 8. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm3 Jocuri. Satisfacerea constrngerilor 1. Tipuri de jocuri 2. Algorimul minimax 3. Retezarea alfa-beta 4. Jocuri nedeterministe 5. Formalizarea problemelor de satisfacere a constrngerilor 6. Backtracking 7. Euristici de optimizare 8. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm4 Cutarea i jocurile De-a lungul timpului, jocurile care necesit explorarea unor alternative au fost considerate provocri pentru inteligena uman Dame (Mesopotamia, cc. 3000 .Hr.) ah (India, sec. VI d.Hr.) Go (China, sec. VI .Hr.) IA-ul folosete deseori jocurile pentru a proiecta i testa algoritmi Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm5 Jocuri Unul din cele mai vechi subdomenii ale IA-ului(Zuse, Shannon, Wiener, Turing, anii 1950) Forme abstracte i pure de competiie care necesit inteligen Probleme dificile cu o structur iniial minim de cunotine Stri i aciuni uor de reprezentat Puine cunotine necesare despre mediu Jocurile sunt un caz particular al problemelor de cutare Deseori au spaii de cutare foarte mari Sunt interesante Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm6 Jocuri deterministe cu informaii perfecte ah DameGo Othelo X i 0 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm7 Jocuri nedeterministe cu informaii perfecte TableMonopoly Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm8 Jocuri nedeterministe cu informaii imperfecte Bridge Scrabble Poker Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm9 Dificulti Jocurile pot fi probleme de cutare foarte dificile Totui uor de formalizat Gsirea soluiei optime poate fi nefezabil O soluie care nvinge adversarul este acceptabil O soluie inacceptabil nu numai c induce costuri mai mari, ci provoac nfrngerea Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm10 Exemple: dimensiunea spaiului de cutare ah (drosofila IA-ului) Factor de ramificare 35 50 de mutri pe juctor 35100 (10154) noduri 1040 noduri distincte (dimensiunea grafului de cutare) Go Factorul de ramificare ncepe de la 361 (tabl 19 x 19) 200 de mutri pe stare, 300 de niveluri 200300 (10690) noduri n arbore Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm11 Jocurile i cutarea Cutarea clasic: un singur agent, ncearc fr piedici s i ating obiectivul Jocurile: cutare n prezena unui adversar Reprezentarea jocurilor ca probleme de cutare Stri: configuraiile tablei de joc Operatori: mutrile permise Starea iniial: configuraia curent a tablei Starea scop: configuraia ctigtoare Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm12 Noi tehnici necesare (I) Spaiul de cutare este foarte mare Nu cunoatem mutarea adversarului Algoritmii pentru jocuri: Caut numai pn la o anumit adncime n arbore Utilizeaz o funcie de evaluare la adncimea respectiv Propag evalurile n sus spre rdcin Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm13 Noi tehnici necesare (II) Modalitatea de joc: Se consider toate mutrile legale care se pot face Fiecare mutare conduce ctre o nou configuraie (poziie) Se evalueaz fiecare poziie rezultat i se determin care este cea mai bun Se face mutarea respectiv Se ateapt mutarea adversarului i se repet algoritmul Probleme cheie: Reprezentarea tablei Generarea tuturor configuraiilor urmtoare valide Evaluarea unei poziii Considerarea mai multor mutri n avans Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm14 Funcia de evaluare (I) Evalueaz valoarea unei poziii Considernd funciile g i h de la cutarea clasic, aici conteaz numai h; g este irelevant Este o funcie euristic i cuprinde cunotinele expert despre domeniu Inteligena calculatorului depinde n mare msur de funcia de evaluare Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm15 Funcia de evaluare (II) Presupunem c jocul este de sum zero Putem folosi o singur funcie de evaluare pentru ambii juctori f(n) > 0: poziia n este bun pentru calculator i rea pentru adversar (om) f(n) < 0:poziia n este rea pentru calculator i bun pentru adversar Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm16 Exemple X i 0: f(n) = [numrul de direcii de 3 ptrele deschise pentru calculator] [numrul de direcii deschise pentru adversar] Direciile sunt linii, coloane sau diagonale complete ah (funcia lui Alan Turing): f(n) = w(n) / b(n) w(n) = suma punctelor pieselor albe b(n) = suma punctelor pieselor negre Pion = 1 punct, cal/nebun = 3 puncte, turn = 5 puncte, regin = 9 puncte Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm17 Exemple Majoritatea funciilor de evaluare sunt sume ponderate ale trsturilor unei poziii: f(n) = w1 t1(n) + w2 t2(n) + ... + wk tk(n) Trsturi pentru ah sunt numrul de piese, plasarea pe tabl a pieselor, ptrele controlate etc. Deep Blue avea 8000 de trsturi n funcia de evaluare Pot exista combinaii neliniare de trsturi Nebunul valoreaz mai mult spre sfritul jocului dect la nceput 2 nebuni valoreaz mai mult dect dublul valorii unuia singur Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm18 3. Jocuri. Satisfacerea constrngerilor 1. Tipuri de jocuri 2. Algorimul minimax 3. Retezarea alfa-beta 4. Jocuri nedeterministe 5. Formalizarea problemelor de satisfacere a constrngerilor 6. Backtracking 7. Euristici de optimizare 8. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm19 Minimax Restricii: 2 juctori:MAX (calculator) i MIN (adversar) Determinist, informaii perfecte Se selecteaz o limit de adncime (de exemplu 2) i o funcie de evaluare MAX MIN MAX 2531443 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm20 MAX MIN MAX - Se construiete arborelepn la limita de adncime - Se calculeaz funcia deevaluare pentru frunze 2531443 - Se propag evaluarea n sus - innd minimele n MIN 21 3 - innd maximele n MAX 3 Alege mutarea Modul de funcionare Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm21 Initialize depthbound; Minimax (board, depth) = IF depth = depthbound THEN return StaticEvaluation(board); ELSE IF maximizing_level(depth)THEN FOR EACH child c of board compute Minimax(c, depth+1); return maximum over all children; ELSE IF minimizing_level(depth)THEN FOR EACH child c of board compute Minimax(c, depth+1); return minimum over all children; Apel:Minimax(current_board, 0) Pseudocod Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm22 Jocuri cu mai muli juctori Funcia de evaluare este vectorial i red utilitile tuturor juctorilor Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm23 Alianele Alianele pot rezulta din aplicarea strategiilor optime individuale Cooperarea poate rezulta din urmrirea comportamentului raional individual (egoist) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm24 Jocuri. Satisfacerea constrngerilor 1. Tipuri de jocuri 2. Algorimul minimax 3. Retezarea alfa-beta 4. Jocuri nedeterministe 5. Formalizarea problemelor de satisfacere a constrngerilor 6. Backtracking 7. Euristici de optimizare 8. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm25 Retezarea alfa-beta engl. alpha-beta pruning, elagajul alfa-beta Optimizare general aplicat algoritmului minimax Minimax Creeaz mai nti ntregul arbore (pn la limita de adncime) Apoi realizeaz propagarea Retezarea alfa-beta ntreese generarea arborelui cu propagarea valorilor Motivaie Unele valori obinute n arbore furnizeaz informaii privind redundana altor pri, care nu mai trebuie generate Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm26 MIN MAX MAX 2 Ideea alfa-beta Se genereaz arborele n adncime, de la stnga la dreapta Se propag valorile finale ale nodurilor ca estimri iniiale pentru prinii lor 2 5 =2 2 1 1 - Valoarea MIN (1) este deja mai mic dect valoarea MAX a printelui(2) - Valoarea MIN poate doar sdescreasc n continuare - Valoarea MAX poate doars creasc - Nu are sens s mergemmai jos sub acest nod Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm27 Terminologie Valorile (temporare) n nodurile MAX sunt valori ALFA Valorile (temporare) n nodurile MIN sunt valori BETA Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm28 Principiile alfa-beta (I) Dac valoarea alfa este mai mare sau egal dect valoarea beta a unui nod descendent Atunci se oprete generarea fiilor nodului descendent Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm29 Principiile alfa-beta (II) Dac valoarea beta este mai mic sau egal dect valoareaalfa a unui nod descendent Atunci se oprete generarea fiilor nodului descendent Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm30 873916241135392652123972864 Exemplu: minimax cu alfa-beta1 2 8 3 5= 8 4 6 8 7 8 9 911131719 21 24 2628323436 10 2 12 4 14= 4 15= 4 4 16 18 1 20 3 22= 5 30= 5 523 5