Transcript
Page 1: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

Inteligenţă artificială

3. Jocuri. Satisfacerea constrângerilor Florin Leon

Universitatea Tehnică „Gheorghe Asachi” din Iaşi

Facultatea de Automatică şi Calculatoare

http://florinleon.byethost24.com/curs_ia.htm

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 2: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

2

Jocuri. Satisfacerea constrângerilor

1. Tipuri de jocuri

2. Algorimul minimax

3. Retezarea alfa-beta

4. Jocuri nedeterministe

5. Formalizarea problemelor de satisfacere a constrângerilor

6. Backtracking

7. Euristici de optimizare

8. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 3: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

3

Jocuri. Satisfacerea constrângerilor

1. Tipuri de jocuri

2. Algorimul minimax

3. Retezarea alfa-beta

4. Jocuri nedeterministe

5. Formalizarea problemelor de satisfacere a constrângerilor

6. Backtracking

7. Euristici de optimizare

8. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 4: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

4

Căutarea şi jocurile

De-a lungul timpului, jocurile care necesită explorarea unor alternative au fost considerate provocări pentru inteligenţa umană

Dame (Mesopotamia, cc. 3000 î.Hr.)

Şah (India, sec. VI d.Hr.)

Go (China, sec. VI î.Hr.)

IA-ul foloseşte deseori jocurile pentru a proiecta şi testa algoritmi

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 5: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

5

Jocuri

Unul din cele mai vechi subdomenii ale IA-ului (Zuse, Shannon, Wiener, Turing, anii 1950)

Forme abstracte şi pure de competiţie care necesită inteligenţă

Probleme dificile cu o structură iniţială minimă de cunoştinţe

Stări şi acţiuni uşor de reprezentat

Puţine cunoştinţe necesare despre mediu

Jocurile sunt un caz particular al problemelor de căutare

Deseori au spaţii de căutare foarte mari

Sunt interesante

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 6: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

6

Jocuri deterministe cu informaţii perfecte

Şah Dame Go

Othelo X şi 0 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 7: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

7

Jocuri nedeterministe cu informaţii perfecte

Table Monopoly

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 8: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

8

Jocuri nedeterministe cu informaţii imperfecte

Bridge

Scrabble

Poker

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 9: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

9

Dificultăţi

Jocurile pot fi probleme de căutare foarte dificile

Totuşi uşor de formalizat

Găsirea soluţiei optime poate fi nefezabilă

O soluţie care învinge adversarul este acceptabilă

O soluţie „inacceptabilă” nu numai că induce costuri mai mari, ci provoacă înfrângerea

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 10: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

10

Exemple: dimensiunea spaţiului de căutare

Şah („drosofila IA-ului”)

Factor de ramificare ≈ 35

≈ 50 de mutări pe jucător

≈ 35100 (10154) noduri

1040 noduri distincte (dimensiunea grafului de căutare)

Go

Factorul de ramificare începe de la 361 (tablă 19 x 19)

≈ 200 de mutări pe stare, 300 de niveluri 200300 (10690) noduri în arbore

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 11: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

11

Jocurile şi căutarea

Căutarea clasică: un singur agent, încearcă fără piedici să îşi atingă obiectivul

Jocurile: căutare în prezenţa unui adversar

Reprezentarea jocurilor ca probleme de căutare

Stări: configuraţiile tablei de joc

Operatori: mutările permise

Starea iniţială: configuraţia curentă a tablei

Starea scop: configuraţia câştigătoare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 12: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

12

Noi tehnici necesare (I)

Spaţiul de căutare este foarte mare

Nu cunoaştem mutarea adversarului

Algoritmii pentru jocuri:

Caută numai până la o anumită adâncime în arbore

Utilizează o funcţie de evaluare la adâncimea respectivă

Propagă evaluările în sus spre rădăcină

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 13: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

13

Noi tehnici necesare (II)

Modalitatea de joc:

Se consideră toate mutările legale care se pot face

Fiecare mutare conduce către o nouă configuraţie (poziţie)

Se evaluează fiecare poziţie rezultată şi se determină care este cea mai bună

Se face mutarea respectivă

Se aşteaptă mutarea adversarului şi se repetă algoritmul

Probleme cheie:

Reprezentarea tablei

Generarea tuturor configuraţiilor următoare valide

Evaluarea unei poziţii

Considerarea mai multor mutări în avans

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 14: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

14

Funcţia de evaluare (I)

Evaluează valoarea unei poziţii

Considerând funcţiile g şi h de la căutarea clasică, aici contează numai h; g este irelevant

Este o funcţie euristică şi cuprinde cunoştinţele expert despre domeniu

„Inteligenţa” calculatorului depinde în mare măsură de funcţia de evaluare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 15: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

15

Funcţia de evaluare (II)

Presupunem că jocul este de sumă zero

Putem folosi o singură funcţie de evaluare pentru ambii jucători

f(n) > 0: poziţia n este bună pentru calculator şi rea pentru adversar (om)

f(n) < 0: poziţia n este rea pentru calculator şi bună pentru adversar

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 16: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

16

Exemple

X şi 0:

f(n) = [numărul de direcţii de 3 pătrăţele deschise pentru calculator] – [numărul de direcţii deschise pentru adversar]

Direcţiile sunt linii, coloane sau diagonale complete

Şah (funcţia 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.htm

Page 17: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

17

Exemple

Majoritatea funcţiilor de evaluare sunt sume ponderate ale trăsăturilor unei poziţii:

f(n) = w1 ∙ t1(n) + w2 ∙ t2(n) + ... + wk ∙ tk(n)

Trăsături pentru şah sunt numărul de piese, plasarea pe tablă a pieselor, pătrăţele controlate etc.

Deep Blue avea 8000 de trăsături în funcţia de evaluare

Pot exista combinaţii neliniare de trăsături

Nebunul valorează mai mult spre sfârşitul jocului decât la început

2 nebuni valorează mai mult decât dublul valorii unuia singur

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 18: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

18

3. Jocuri. Satisfacerea constrângerilor

1. Tipuri de jocuri

2. Algorimul minimax

3. Retezarea alfa-beta

4. Jocuri nedeterministe

5. Formalizarea problemelor de satisfacere a constrângerilor

6. Backtracking

7. Euristici de optimizare

8. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 19: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

19

Minimax

Restricţii: 2 jucători: MAX

(calculator) şi MIN (adversar)

Determinist, informaţii perfecte

Se selectează o limită de adâncime (de exemplu 2) şi o funcţie de evaluare

MAX

MIN

MAX

2 5 3 1 4 4 3

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 20: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

20

MAX

MIN

MAX

- Se construieşte arborele până la limita de adâncime

- Se calculează funcţia de evaluare pentru frunze

2 5 3 1 4 4 3

- Se propagă evaluarea în sus - ţinând minimele în MIN

2 1 3

- ţinând maximele în MAX

3 Alege mutarea

Modul de funcţionare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 21: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

21

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.htm

Page 22: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

22

Jocuri cu mai mulţi jucători

Funcţia de evaluare este vectorială şi redă utilităţile tuturor jucătorilor

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 23: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

23

Alianţele

Alianţele pot rezulta din aplicarea strategiilor optime individuale

Cooperarea poate rezulta din urmărirea comportamentului raţional individual (egoist)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 24: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

24

Jocuri. Satisfacerea constrângerilor

1. Tipuri de jocuri

2. Algorimul minimax

3. Retezarea alfa-beta

4. Jocuri nedeterministe

5. Formalizarea problemelor de satisfacere a constrângerilor

6. Backtracking

7. Euristici de optimizare

8. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 25: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

25

Retezarea alfa-beta

engl. “alpha-beta pruning”, elagajul alfa-beta

Optimizare general aplicată algoritmului minimax

Minimax Creează mai întâi întregul arbore (până la limita de

adâncime)

Apoi realizează propagarea

Retezarea alfa-beta Întreţese generarea arborelui cu propagarea valorilor

Motivaţie Unele valori obţinute în arbore furnizează informaţii privind

redundanţa altor părţi, care nu mai trebuie generate

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 26: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

26

MIN

MAX

MAX

2

Ideea alfa-beta Se generează arborele în adâncime, de la stânga la dreapta

Se propagă valorile finale ale nodurilor ca estimări iniţiale pentru părinţii lor

2

5

=2

2

1

1

- Valoarea MIN (1) este deja mai mică decât valoarea MAX a părintelui (2)

- Valoarea MIN poate doar să descrească în continuare

- Valoarea MAX poate doar să crească

- Nu are sens să mergem mai jos sub acest nod

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 27: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

27

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.htm

Page 28: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

28

Principiile alfa-beta (I)

Dacă valoarea alfa este mai mare sau egală decât valoarea beta a unui nod descendent

Atunci se opreşte generarea fiilor nodului descendent

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 29: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

29

Principiile alfa-beta (II)

Dacă valoarea beta este mai mică sau egală decât valoarea alfa a unui nod descendent

Atunci se opreşte generarea fiilor nodului descendent

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 30: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

30

8 7 3 9 1 6 2 4 1 1 3 5 3 9 2 6 5 2 1 2 3 9 7 2 8 6 4

Exemplu: minimax cu alfa-beta

1

2 8

3

5 = 8

4

6 8

7

8 9

9 11 13 17 19 21 24 26 28 32 34 36

10 2 12 4 14 = 4

15 = 4

4 16

18 1 20 3 22 = 5

30 = 5 5 23

5 31

25 3 27 9 29 6

33 1 35 2 37 = 3

3 38

39 = 5 MAX

MIN

MAX

11 evaluări evitate Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 31: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

31

Retezare în adâncime

Pentru arbori cu cel puţin 4 niveluri min/max, retezarea alfa-beta se aplică şi pentru niveluri mai adânci

4

4

4

4

4

2

2

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 32: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

32

Cazul cel mai favorabil: arbore perfect ordonat

MAX

MIN

MAX

21 20 19 24 23 22 27 26 25 12 11 10 15 14 13 18 17 16 3 2 1 6 5 4 9 8 7

21 24 27 12 15 18 3 6 9

21 12 3

21

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 33: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

33

Cazul cel mai favorabil

MAX

MIN

MAX

- Când pe fiecare nivel cel mai bun nod este primul din stânga

Doar ramurile îngroşate sunt explorate Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 34: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

34

Cazul cel mai favorabil

Numărul de evaluări statice:

nes = 2 bd/2 – 1, dacă d este par

nes = b(d+1)/2 + b(d–1)/2 – 1, dacă d este impar

În exemplul anterior:

d = 3, b = 3 nes = 9 + 3 – 1 = 11

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 35: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

35

Comparaţie între minimax şi alfa-beta

Graficul are scară logaritmică Retezarea alfa-beta are tot complexitate exponenţială

Cazul cel mai defavorabil Pentru unii arbori retezarea alfa-beta nu are niciun efect

Pentru unii arbori este imposibilă reordonarea pentru a permite retezarea

Cazul cel mai favorabil

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 36: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

36

Performanţele retezării alfa-beta

Alfa-beta garantează calcularea aceleiaşi valori pentru rădăcină ca şi minimax, cu o complexitate mai mică sau egală

Cazul cel mai defavorabil: nu se face nicio retezare, se examinează O(bd) noduri

Cazul mediu:

Cazul cel mai favorabil: O(bd/2)

Poate căuta pe o adâncime de două ori mai mare decât minimax

Când cea mai bună mutare este şi prima alternativă generată

În cazul Deep Blue, s-a descoperit empiric că retezarea alfa-beta a redus factorul mediu de ramificare de la 35 la 6

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 37: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

37

Efectul orizontului

Datorită limitei de adâncime, se preferă întârzierea dezastrelor, deşi acestea nu se previn

Soluţia: continuarea euristică

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 38: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

38

Continuarea euristică

În situaţii strategice cruciale (regele în pericol, pierdere iminentă de piese, pion transformat în regină etc.), se extinde căutarea dincolo de limita de adâncime

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 39: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

39

Căutarea secundară

Uneori este utilă verificarea unei mutări

De exemplu, dacă se face căutarea pe 6 niveluri (engl. “ply”) şi s-a găsit cea mai bună mutare, se poate expanda numai acea poziţie pentru încă 2 niveluri pentru a verifica dacă rămâne bună în continuare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 40: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

40

Retezarea înainte

engl. “forward pruning”

Un jucător uman nu ia în calcul toate mutările posibile, ci doar pe cele care i se par utile

Se renunţă la un sub-arbore Când există mai multe mutări simetrice sau

echivalente

Pentru mutări care par iraţionale (care conduc în situaţii aparent defavorbile) Numai la adâncimi mari în arbore

Nerecomandate în apropierea rădăcinii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 41: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

41

Limite de timp

Chiar şi când există limite de adâncime, timpii pot varia mult

Soluţie: căutarea iterativă în adâncime

La orice moment este disponibilă o mutare

Calitatea mutării creşte în timp

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 42: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

42

Efectul euristicilor: şahul

Cu minimax putem căuta pe aproximativ 5 niveluri

Un jucător mediu analizează 6-8 niveluri

Cu reducerea alfa-beta putem căuta pe aproximativ 10 niveluri (reducerea alfa-beta face diferenţa)

Deep Blue Căutare în medie pe 14 niveluri, maxim 40

Evaluarea a 30 de miliarde de poziţii pe mutare

Bază de date cu 700.000 de jocuri

4000 de strategii de deschidere

Toate rezolvările pentru poziţiile cu 5 piese şi multe pentru poziţiile cu 6 piese

Metodele euristice recente pot scădea factorul de ramificare de la 35 la aproximativ 3 De exemplu: “null move” – oponentul mută de 2 ori la început

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 43: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

43

Jocuri. Satisfacerea constrângerilor

1. Tipuri de jocuri

2. Algorimul minimax

3. Retezarea alfa-beta

4. Jocuri nedeterministe

5. Formalizarea problemelor de satisfacere a constrângerilor

6. Backtracking

7. Euristici de optimizare

8. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 44: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

44

Jocuri nedeterministe

Includ elemente probabilistice

Zaruri, cărţi de joc

De exemplu: table

Albul a dat 6-5 şi are 4 mutări valide:

5-10, 5-11

5-11, 19-24

5-10, apoi 10-16

5-11, apoi 11-16

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 45: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

45

Arbori de joc cu noduri-şansă

Nodurile şansă (cercurile) reprezintă evenimente aleatorii

Pentru un eveniment aleatoriu cu n rezultate posibile, fiecare nod-şansă are n fii distincţi; fiecare are asociată o probabilitate

Pentru 2 zaruri, sunt posibile 21 de rezultate

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 46: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

46

Arbori de joc cu noduri-şansă

Se foloseşte minimax pentru a calcula valorile nodurilor MAX şi MIN

Se folosesc valorile aşteptate pentru nodurile-şansă

Pentru nodurile-şansă la un nod MAX (de exemplu C):

expectimax(C) = Σi(P(di) * maxvalue(i))

Pentru nodurile-şansă la un nod MIN:

expectimin(X) = Σi(P(di) * minvalue(i))

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 47: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

47

Exemplu

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 48: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

48

Performanţe

Complexitate: O(bmnm)

n = numărul de posibilităţi distincte (de exemplu, pentru un zar, n = 6)

Pentru jocul de table, căutarea se poate face probabil pe maximum 3 niveluri

Se poate aplica reducerea alfa-beta estimând limitele superioare şi inferioare ale valorilor

Pentru aproximarea valorilor se poate folosi simularea Monte Carlo

Valoarea stării este probabilitatea de a câştiga din acea stare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 49: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

Stadiul actual al programelor de jocuri

Dame (Chinook), Othello (Logistello): programele sunt mai bune decât oamenii

Table (TD-Gammon): învăţare cu întărire şi reţele neuronale, top 3 mondial

Şah – Elo rating : Hydra 2850-3000, Kasparov (cel mai bun înregistrat): 2851

Go (Goemate, Go4++): nivel master pentru tablă 9 x 9, începător pentru 19 x 19

Bridge (GIB): campion mondial

49 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 50: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

50

Jocuri. Satisfacerea constrângerilor

1. Tipuri de jocuri

2. Algorimul minimax

3. Retezarea alfa-beta

4. Jocuri nedeterministe

5. Formalizarea problemelor de satisfacere a constrângerilor

6. Backtracking

7. Euristici de optimizare

8. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 51: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

51

Satisfacerea constrângerilor

engl. “Constraint Satisfaction Problems” (CSP)

O mulţime de variabile {X1, X2, …, Xn}

Fiecare variabilă Xi are un domeniu Di de valori posibile De obicei, Di este finit

O mulţime de constrângeri {C1, C2, …, Cp}

Fiecare constrângere este definită pe o submulţime de variabile şi arată combinaţiile valide ale valorilor acestora

Scopul: atribuirea unei valori fiecărei variabile astfel încât toate constrângerile să fie satisfăcute

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 52: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

52

Variabile: WA, NT, Q, NSW, V, SA, T Domenii: Di = { roşu, verde, albastru } Constrângeri: regiunile adiacente trebuie să aibă culori diferite De ex. WA ≠ NT, sau (WA,NT) {(roşu,verde), (roşu,albastru),

(verde,roşu), (verde,albastru),(albastru,roşu),(albastru,verde)}

Exemplu: colorarea unei hărţi

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 53: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

53

Soluţiile sunt atribuiri complete şi consistente

De exemplu: WA = roşu, NT = verde, Q = roşu, NSW = verde, V = roşu, SA = albastru, T = verde

Soluţie

respectă toate constrângerile

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 54: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

54

Graful constrângerilor

Probleme binare: fiecare constrângere este definită pe 2 variabile

Graful constrângerilor: nodurile sunt variabile, arcele sunt constrângeri

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 55: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

55

Tipuri de PSC

Variabile discrete Domenii finite

“Boolean satisfiability” (NP-completă): problema determinării dacă variabilele unei formule booleene date pot lua valori astfel încât formula să fie adevărată

Domenii infinite Planificarea sarcinilor de lucru (“job shop scheduling”):

variabilele sunt momentele de început/sfârşit ale fiecărei sarcini

Variabile continue Momentele de început/sfârşit pentru observaţiile telescopului

Hubble

Constrângeri liniare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 56: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

56

Tipuri de constrângeri

Constrângerile unare implică o singură variabilă SA ≠ verde

Constrângerile binare implică perechi de variabile SA ≠ WA

Constrângerile de nivel înalt implică 3 sau mai multe variabile Probleme criptaritmetice

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 57: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

57

Probleme criptaritmetice

Variabile: F T U W R O X1 X2 X3

Domenii: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Constrângeri: DiferiteToate (F, T, U, W, R, O) O + O = R + 10 · X1

X1 + W + W = U + 10 · X2

X2 + T + T = O + 10 · X3

X3 = F, T ≠ 0, F ≠ 0

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 58: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

58

Probleme reale

Probleme de atribuire

Cine predă ce obiect la ce clasă

Problema orarului

Ce curs este predat când şi unde

Planificarea transporturilor

Planificarea în mediul industrial

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 59: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

59

Căutarea incrementală standard

Stările sunt definite de valorile atribuite până în prezent

Starea iniţială: atribuirea vidă { }

Operatori: atribuirea unei valori unei variabile neatribuite care nu intră în conflict cu atribuirea curentă

Eşec dacă nu există atribuiri valide

Scop: atribuirea curentă să fie completă

Aceeaşi procedură pentru toate problemele de satisfacere a constrângerilor

Fiecare soluţie apare la adâncimea n cu n variabile

Se foloseşte căutarea în adâncime

Calea este irelevantă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 60: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

60

Jocuri. Satisfacerea constrângerilor

1. Tipuri de jocuri

2. Algorimul minimax

3. Retezarea alfa-beta

4. Jocuri nedeterministe

5. Formalizarea problemelor de satisfacere a constrângerilor

6. Backtracking

7. Euristici de optimizare

8. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 61: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

61

Rezolvarea PSC

Căutare clasică: n variabile, d valori

Arbore cu n! ∙ dn frunze Factorul de ramificare pe primul nivel este n ∙ d, pe al doilea (n - 1) ∙ d etc.

Există doar dn atribuiri complete posibile

În multe probleme, aceleaşi stări pot fi atinse independent de ordinea în care se iau deciziile

Acţiuni comutative

În problemele de satisfacerea constrângerilor, stările au o structură standard iar algoritmii pot profita de aceasta

Se pot aplica algoritmi generali, nu doar euristici specifice unei probleme

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 62: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

62

Căutarea backtracking

Comutativitatea atribuirilor (WA = roşu apoi NT = verde) este la fel cu

(NT = verde apoi WA = roşu)

Căutarea backtracking este: Căutare în adâncime cu

Atribuirea unei singure variabile într-un nod

Poate rezolva problema reginelor cu n ≈ 25

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 63: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

63

Exemplu de backtracking

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 64: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

64

Exemplu de backtracking

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 65: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

65

Exemplu de backtracking

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 66: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

66

Exemplu de backtracking

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 67: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

67

Căutarea neinformată şi backtracking-ul

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 68: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

68

Jocuri. Satisfacerea constrângerilor

1. Tipuri de jocuri

2. Algorimul minimax

3. Retezarea alfa-beta

4. Jocuri nedeterministe

5. Formalizarea problemelor de satisfacere a constrângerilor

6. Backtracking

7. Euristici de optimizare

8. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 69: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

69

Creşterea eficienţei algoritmului backtracking

Metodele de optimizare dau creşteri spectaculoase de viteză

Ce variabilă să fie atribuită în pasul următor?

În ce ordine să se încerce valorile?

Se poate detecta eşecul mai devreme?

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 70: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

70

Cea mai constrângătoare variabilă

Se alege variabila cu cele mai multe constrângeri asupra variabilelor rămase

Utilă pentru decizii în caz de egalitate, de exemplu în starea iniţială

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 71: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

71

Cea mai constrânsă variabilă

Se alege variabila cu cele mai puţine valori permise

Se mai numeşte euristica celor mai puţine valori rămase

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 72: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

72

Cea mai puţin constrângătoare valoare

Pentru o variabilă se alege valoarea care elimină cele mai puţine valori în variabilele rămase

Combinarea acestor euristici face posibilă rezolvarea problemei reginelor cu n ≈ 1000

Permite 1 valoare pentru SA

Permite 0 valori pentru SA

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 73: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

73

Verificarea înainte

engl. “forward checking”

La început, pentru fiecare variabilă se memorează mulţimea curentă de valori permise

Când se atribuie o valoare în procesul de căutare, se actualizează mulţimile de valori permise pentru toate variabilele

Dacă o mulţime devine vidă, se revine (se face backtracking)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 74: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

74

Backtracking şi Verificarea înainte

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 75: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

75

Propagarea constrângerilor

engl. “constraint propagation”

Verificarea înainte calculează domeniul fiecărei variabile independent la început şi actualizează un domeniu numai când se fac atribuiri ce influenţează direct variabila respectivă

Propagarea constrângerilor duce verificarea mai departe:

Când se şterge o valoare din domeniul variabilei X, se verifică toate variabilele conectate la X

Dacă aceste variabile se modifică, se şterg toate valorile inconsistente conectate la ele ş.a.m.d.

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 76: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

76

Propagarea constrângerilor

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 77: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

77

Verificarea înainte şi Propagarea constrângerilor

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 78: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

78

Propagarea constrângerilor cu euristici

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 79: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

79

Complexitatea de timp

Trebuie realizat un compromis între calculele necesare rezolvării problemei propriu-zise şi calculele necesitate de euristici

Propagarea constrângerilor reduce foarte mult factorul de ramificare (uneori rezolvarea este aproape liniară), însă calculele suplimentare sunt laborioase

Pentru majoritatea problemelor uzuale, este suficientă verificarea înainte cu euristicile de ordonare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 80: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

80

Min-Conflicts

Este o metodă de căutare locală

Poate rezolva problema reginelor cu 1 milion de regine în aproximativ 50 de paşi

A redus timpul de planificare al telescopului Hubble pentru o săptămână de observaţii de la 3 săptămâni la 10 minute

Funcţionează bine mai ales când soluţiile sunt dens distribuite în spaţiul stărilor

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 81: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

81

Min-Conflicts

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 82: Inteligenta artificiala: Jocuri. Satisfacerea constrangerilor

82

Concluzii

Jocurile ilustrează faptul că perfecţiunea este deseori de neatins, însă aproximările sunt suficiente

Nu avem nevoie întotdeauna de soluţii optime din punct de vedere teoretic, ci de soluţii prin care câştigăm

Tehnicile de satisfacere a constrângerilor sunt utile când:

Problema poate fi exprimată printr-o mulţime de variabile cu constrângeri asupra valorilor lor

Constrângerile sunt relativ simple (de exemplu binare)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm


Top Related