Lecture on Constraint Satisfaction Problems (CSPs)

Inteligent, ă Artificială Problema satisfacerii restrict, iilor Slides: Andrei Olaru, Adina Florea Problema satisfacerii restrict, iilor | 0 / 22 Satisfacerea restrict, iilor Backtracking Propa...

Inteligent, ă Artificială Problema satisfacerii restrict, iilor Slides: Andrei Olaru, Adina Florea Problema satisfacerii restrict, iilor | 0 / 22 Satisfacerea restrict, iilor Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Problema satisfacerii restrict, iilor (Constraint Satisfaction Problem – CSP) problema colorării hărt, ilor WA, NT , Q, SA, NSW , V , T ∈ Colors WA ̸= NT , WA ̸= SA, NT ̸= SA,... Problema satisfacerii restrict, iilor | 1 / 22 Satisfacerea restrict, iilor Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Problema satisfacerii restrict, iilor (Constraint Satisfaction Problem – CSP) problema colorării hărt, ilor sudoku a, b,... , i ∈ {1, 2, 3, 4} a∈ / {1, 2, 4, d, i} b∈ / {2, 4, c, e, h} c∈ / {2, 4, b, c, f } d∈ / {1, 3, 4, a, g}... Problema satisfacerii restrict, iilor | 1 / 22 Satisfacerea restrict, iilor Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Problema satisfacerii restrict, iilor (Constraint Satisfaction Problem – CSP) problema colorării hărt, ilor sudoku orarul Problema satisfacerii restrict, iilor | 1 / 22 Satisfacerea restrict, iilor Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Problema satisfacerii restrict, iilor (Constraint Satisfaction Problem – CSP) problema colorării hărt, ilor sudoku orarul problema lui Einstein (Zebra puzzle) Problema satisfacerii restrict, iilor | 1 / 22 Satisfacerea restrict, iilor Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP T W O Problema satisfacerii restrict, iilor + T W O (Constraint Satisfaction Problem – CSP) F O U R problema colorării hărt, ilor W , O, U, R ∈ 0... 9 sudoku T,F ∈ 1...9 orarul 2 · O % 10 = R problema lui Einstein (Zebra puzzle) 2 · W % 10 + 2 · O ÷ 10 = U puzzle-uri matematice 2 · T % 10 + 2 · W ÷ 10 = O 2 · T ÷ 10 = F Problema satisfacerii restrict, iilor | 1 / 22 Satisfacerea restrict, iilor Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Problema satisfacerii restrict, iilor (Constraint Satisfaction Problem – CSP) problema colorării hărt, ilor sudoku orarul problema lui Einstein (Zebra puzzle) puzzle-uri matematice... Problema satisfacerii restrict, iilor | 1 / 22 Satisfacerea restrict, iilor : Terminologie Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP {X1... XN } = V – Variable {D1... DN } – Domenii {R1... Rk } = R – Restrict, ii, Rj = ⟨tj , rj ⟩, tj ⊆ V , rj : ×Xi ∈tj Di → − {True, False} {⟨X1 , x1 ⟩... ⟨XN , xN ⟩} – Atribuire la valori, cu xi ∈ Di ∪ {⊥} (⊥ ≡ neatribuit la o valoare) o atribuire este solut, ie dacă xi ∈ Di , i = 1, N, i.e. toate variabilele au atribuită o valoare (atribuire completă) ∀Rj ∈ R, rj (vals) = True, cu vals valorile variabilelor din tj (solut, ie validă) Problema satisfacerii restrict, iilor | 2 / 22 Satisfacerea restrict, iilor : Terminologie Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP CSP totală – solut, ia este completă s, i nu încalcă nicio restrict, ie Problema satisfacerii restrict, iilor | 3 / 22 Satisfacerea restrict, iilor : Terminologie Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP CSP totală – solut, ia este completă s, i nu încalcă nicio restrict, ie CSP part, ială – solut, ia este completă dar încalcă unele restrict, ii Rj = ⟨tj , rj , cj ⟩, cu cj costul restrict, iei Rj P costul solut, iei c = cj Rj ∈R,rj (vals(tj ))=False Problema satisfacerii restrict, iilor | 3 / 22 Satisfacerea restrict, iilor : Terminologie Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP CSP totală – solut, ia este completă s, i nu încalcă nicio restrict, ie CSP part, ială – solut, ia este completă dar încalcă unele restrict, ii Rj = ⟨tj , rj , cj ⟩, cu cj costul restrict, iei Rj P costul solut, iei c = cj Rj ∈R,rj (vals(tj ))=False CSP binară – toate restrict, iile sunt binare ∀Rj ∈ R, tj ∈ V × V Problema satisfacerii restrict, iilor | 3 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Backtracking Problema satisfacerii restrict, iilor | 4 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP CSP este o problemă NP, apropiată de problema SAT ⇒ CSP trebuie rezolvat prin backtracking ce putem face este să încercăm să reducem spat, iul de căutare s, i factorul de ramificare îmbunătăt, irea consistent, ei căutării reducerea spat, iului de căutare Problema satisfacerii restrict, iilor | 5 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP CSP-BKT Intrări: Vars – variabile rămase de atribuit, init, ial X ; Sol – solut, ia (atribuirea) part, ială, init, ial ∅ Ies, ire: O atribuire completă sau E S, EC 1. dacă Vars = ∅ atunci întoarce Sol 2. Xi ← − alege_variabila(Vars) 3. pentru fiecare x ∈ Di 4. dacă consistent(Sol ∪ ⟨Xi , x⟩, R) atunci 5. res ← − CSP-BKT (Vars \ {Xi }, Sol ∪ ⟨Xi , x⟩) 6. dacă res ̸= E S, EC atunci întoarce res 7. întoarce E S, EC Problema satisfacerii restrict, iilor | 6 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Propagarea locală a restrict, iilor Problema satisfacerii restrict, iilor | 7 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Intuitiv: init, ial, după aplicarea restrict, iilor unare, avem a ∈ {3} d ∈ {2} b, c, e, f ∈ {1, 3} h ∈ {1, 2} g ∈ {4} i ∈ {1} a 1. a poate fi doar 3; a se învecinează cu d, i; ambele au domenii compatibile cu valoarea lui a b c d e f g h i Problema satisfacerii restrict, iilor | 8 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Intuitiv: init, ial, după aplicarea restrict, iilor unare, avem a ∈ {3} d ∈ {2} b, c, e, f ∈ {1, 3} h ∈ {1, 2} g ∈ {4} i ∈ {1} a 1. a poate fi doar 3; a se învecinează cu d, i; ambele au domenii compatibile cu valoarea lui a b c d 2. d poate fi doar 2, se învecinează cu b, c, g; sunt compatibile e f g h i Problema satisfacerii restrict, iilor | 8 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Intuitiv: init, ial, după aplicarea restrict, iilor unare, avem a ∈ {3} d ∈ {2} b, c, e, f ∈ {1, 3} h ∈ {1, 2} g ∈ {4} i ∈ {1} a 1. a poate fi doar 3; a se învecinează cu d, i; ambele au domenii compatibile cu valoarea lui a b c d 2. d poate fi doar 2, se învecinează cu b, c, g; sunt compatibile e f g 3. i poate fi doar 1, se învecinează cu h, deci h nu poate fi 1 ⇒ restrict, ionăm domeniul lui h la {2} h i Problema satisfacerii restrict, iilor | 8 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Intuitiv: init, ial, după aplicarea restrict, iilor unare, avem a ∈ {3} d ∈ {2} b, c, e, f ∈ {1, 3} h ∈ {1, 2} g ∈ {4} i ∈ {1} a 1. a poate fi doar 3; a se învecinează cu d, i; ambele au domenii compatibile cu valoarea lui a b c d 2. d poate fi doar 2, se învecinează cu b, c, g; sunt compatibile e f g 3. i poate fi doar 1, se învecinează cu h, deci h nu poate fi 1 ⇒ restrict, ionăm domeniul lui h la {2} h i 4. restrict, ionarea nu afectează pe b, e, f Problema satisfacerii restrict, iilor | 8 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Intuitiv: init, ial, după aplicarea restrict, iilor unare, avem a ∈ {3} d ∈ {2} b, c, e, f ∈ {1, 3} h ∈ {1, 2} g ∈ {4} i ∈ {1} a 1. a poate fi doar 3; a se învecinează cu d, i; ambele au domenii compatibile cu valoarea lui a b c d 2. d poate fi doar 2, se învecinează cu b, c, g; sunt compatibile e f g 3. i poate fi doar 1, se învecinează cu h, deci h nu poate fi 1 ⇒ restrict, ionăm domeniul lui h la {2} h i 4. restrict, ionarea nu afectează pe b, e, f 5. rămân b, c, e, f cu domeniul {1, 3} Problema satisfacerii restrict, iilor | 8 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Pe cazul general, dacă o variabilă i poate avea doar valorile Di′ , ajustăm domeniile tuturor variabilelor vecine (care au restrict, ii binare cu variabila i), în as, a fel încât să cont, ină doar valori compatibile cu valorile din Di′. Dacă un domeniu Dk , al variabilei k vecină cu i, a fost ajustat, trebuie verificate din nou toate variabilele vecine cu variabila k , mai put, in variabila i. Problema satisfacerii restrict, iilor | 9 / 22 CSP Backtracking Propagarea locală a restrict, iilor : AC-3 Îmbunătăt, iri BKT PCSP Algoritmul AC-3 (Arc Consistency 3) trebuie ca toate restrict, iile să fie unare sau binare putem forma un graf de restrict, ii în care nodurile corespund variabilelor arcele corespund restrict, iilor binare. Considerăm pentru fiecare restrict, ie două arce orientate. un arc (Xi , Xj ) corespunzător unei restrict, ii Rij este arc-consistent dacă ∀xi ∈ Di , ∃xj ∈ Dj , rij (xi , xj ) = True dacă toate arcele din graf sunt arc-consistente, graful este arc-consistent s, i nu putem reduce mai mult (prin acest mecanism) spat, iul de căutare Problema satisfacerii restrict, iilor | 10 / 22 CSP Backtracking Propagarea locală a restrict, iilor : AC-3 Îmbunătăt, iri BKT PCSP AC-3 1. reduce toate domeniile conform cu restrict, iile unare 2. Q← − {(Xi , Xj ) | Rij ∈ R sau Rji ∈ R} 3. cât timp Q ̸= ∅ 4. (Xi , Xj ) ← − Q.pop() 5. dacă check (Xi , Xj ) atunci domeniul lui Xi s-a modificat 6. dacă Di = ∅ atunci întoarce E S, EC 7. Q = Q ∪ {(Xk , Xi ) | Rki ∈ R, k ̸= j} 8. întoarce S UCCES check (Xi , Xj ) 1. pentru xi ∈ Di 2. dacă ∄xj ∈ Dj. rij (xi , xj ) = True 3. atunci Di ← − Di \ {xi } 4. întoarce True dacă Di s-a modificat, altfel False Problema satisfacerii restrict, iilor | 11 / 22 CSP Backtracking Propagarea locală a restrict, iilor : AC-3 Îmbunătăt, iri BKT PCSP complexitatea temporală pentru AC-3 este O(e · d 3 ), unde e = |R| – numărul de restrict, ii (muchii) d = maxi=1,N |Di | – cardinalitatea maximă a domeniilor complexitatea spat, ială este O(e) algoritmi mai noi – dar mai complicat, i – pot fi mai buni. E.g., AC-4 are complexitate O(e · d 2 ) Problema satisfacerii restrict, iilor | 12 / 22 CSP Backtracking Propagarea locală a restrict, iilor : AC-3 Îmbunătăt, iri BKT PCSP dacă AC-3 întoarce E S, EC atunci înseamnă că problema nu are solut, ie dacă după realizarea AC-3, toate domeniile au cardinalitate 1 (spunem că lăt, imea grafului de restrict, ii este 1), atunci nu mai este necesar backtracking dacă lăt, imea grafului de restrict, ii este mai mare de 1, atunci nu este garantat că problema are solut, ie, s, i trebuie făcut backtracking pe variabilele cu domenii de cardinalitate > 1 Problema satisfacerii restrict, iilor | 13 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Îmbunătăt, iri BKT Problema satisfacerii restrict, iilor | 14 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT : MAC PCSP Reducerea spat, iului de căutare prin detectarea timpurie a inconsistent, elor: combinăm backtracking cu arc consistent, a, ment, inând arc-consistent, a pe măsură ce avansăm în recursivitate. (Maintaining arc-consistency – MAC) verificăm arc-consistent, a după ce atribuim o valoare în solut, ia part, ială Problema satisfacerii restrict, iilor | 15 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT : MAC PCSP BKT-MAC 1. dacă Vars = ∅ atunci întoarce Sol 2. Xi ←− alege_variabila(Vars) 3. pentru fiecare x ∈ Di 4. Dcopy ← −D copiem toate domeniile arcs_out întoarce toate arcele care pornesc din Xi 5. −AC-3′ (arcs_out(Xi )) r← AC-3’ este AC-3 începând de la pasul 3., cu Q pornind de la valoarea din argument 6. dacă r s, i consistent(Sol ∪ ⟨Xi , x⟩, R) atunci 7. res ← − BKT -MAC(Vars \ {Xi }, Sol ∪ ⟨Xi , x⟩) 8. dacă res ̸= E S, EC atunci întoarce res 9. D← − Dcopy 10. întoarce E S, EC refacem domeniile Problema satisfacerii restrict, iilor | 16 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT : Ordonarea variabilelor PCSP Putem ordona variabilele (funct, ia alege_variabila): aleator alegând variabila cea mai restrict, ionată (cu domeniul cel mai redus) – Minimum remaining value – MRV util atunci când ne dorim o singură solut, ie s, i vrem să fort, ăm, dacă e cazul, un es, ec mai rapid alegând variabila cea mai put, in restrict, ionată util atunci când ne dorim aflarea tuturor solut, iilor s, i ne dorim un arbore de BKT mai lat s, i mai put, in adânc alegând variabila implicată în cele mai multe restrict, ii cu variabile încă ne-atribuite – Degree heuristic Problema satisfacerii restrict, iilor | 17 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT : Ordonarea valorilor PCSP Putem parcurge valorile din domeniu într-o anumită ordine: selectăm întâi valoarea care elimină cele mai put, ine valori din variabilele vecine la ment, inerea arc-consistent, ei util atunci când ne dorim o singură solut, ie s, i vrem să ajungem la o solut, ie mai repede selectăm întâi valoarea care elimină cele mai multe valori din variabilele vecine la ment, inerea arc-consistent, ei util atunci când ne dorim toate solut, ile s, i preferăm un graf mai put, in adânc Problema satisfacerii restrict, iilor | 18 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT CSP Part, ială CSP Part, ială Problema satisfacerii restrict, iilor | 19 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT CSP Part, ială Pentru o problemă de tip CSP cu multe restrict, ii, este posibil ca nu toate restrict, iile să fie la fel de importante (vezi, de exemplu, problema orarului) ⇒ CSP Part, ială (Flexible CSP). asociem un cost cu fiecare restrict, ie: Rj = ⟨tj , rj , cj ⟩,cu cj > 0 P stabilim o limită suficientă S – considerăm o solut, ie Sol ca validă dacă cj ≤ S j,rj (Sol)=False optimizare: dacă în parcurgere costul total al restrict, iilor încălcate de atribuirea part, ială curentă depăs, es, te S, sau depăs, es, te costul restrict, iilor pentru cea mai bună solut, ie găsită până acum, nu are sens să mai continuăm pe aceast cale Problema satisfacerii restrict, iilor | 20 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT CSP Part, ială PCSP – găses, te prima solut, ie acceptabilă Intrări: Vars – variabile rămase de atribuit, init, ial X ; Sol – solut, ia (atribuirea) part, ială, init, ial ∅ cost – costul solut, iei part, iale Sol, cu S – limita suficientă Ies, ire: O atribuire completă de cost ≤ S sau E S, EC 1. dacă Vars = ∅ atunci întoarce Sol 2. Xi ← − alege_variabila(Vars) 3. pentru fiecare x ∈ Di 4. Sol ′ ←− Sol ∪ ⟨Xi , x⟩ P 5. c = cost + cj Xi ∈tj ,rj (Sol ′ )=False 6. dacă c ≤ S 7. − PCSP(Vars \ {Xi }, Sol ′ , c) res ← 8. dacă res ̸= E S, EC atunci întoarce res 9. întoarce E S, EC Problema satisfacerii restrict, iilor | 21 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT CSP Part, ială PCSP – găses, te cea mai bună solut, ie acceptabilă Intrări: Vars – variabile rămase de atribuit, init, ial X ; Sol – solut, ia (atribuirea) part, ială, init, ial ∅ cost – costul solut, iei part, iale Sol, cu S – limita suficientă Global: sols – toate solut, iile complete acceptabile găsite până acum best_cost – costul minim al unei solut, ii din sols Ies, ire: O mult, ime de atribuiri complete de cost ≤ S, sau E S, EC 1. dacă Vars = ∅ atunci 2. sols ←− sols ∪ {Sol} 3. dacă cost < best_cost atunci best_cost ← − cost 4. Xi ←− alege_variabila(Vars) 5. pentru fiecare x ∈ Di 6. Sol ′ ← − Sol ∪ ⟨Xi , x⟩ P 7. c = cost + cj Xi ∈tj ,rj (Sol ′ )=False 8. dacă c ≤ S s, i c < best_cost 9. PCSP(Vars \ {Xi }, Sol ′ , c) va actualiza sols dacă este cazul Problema satisfacerii restrict, iilor | 22 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Mult, umesc! https://forms.gle/DJUdkejstkvyNRF5A Feedbackul este binevenit! Problema satisfacerii restrict, iilor | 22 / 22  Inteligent, ă Artificială Căutare în jocuri Căutare în jocuri | 0 / 28 2 jucători 3+ jucători MCTS vedem un joc ca o problemă de căutare – are un spat, iu de stări, o stare init, ială, s, i stări finale în care jocul se termină s, i în care jucătorii primesc o recompensă. Căutare în jocuri | 1 / 28 2 jucători 3+ jucători MCTS x x x x o o o o x x x o o xo xo x x x x o o xo xo xo xx x o o o x ooo xo xo xx xx xo o xo xxo o xo xxo x o Căutare în jocuri | 2 / 28 2 jucători 3+ jucători MCTS jocuri cooperative – Pandemic non-cooperative – Poker cu sumă 0 – X s, i 0, S, ah, Go jocuri cu informat, ie perfectă – S, ah, X s, i 0, Go imperfectă – Poker, Bridge cu elemente de s, ansă – Table, Poker jocuri secvent, iale – X s, i 0, S, ah, Poker cu mis, cări simultane – Rock-paper-scissors Căutare în jocuri | 3 / 28 Jocuri cu 2 adversari 3+ jucători MCTS ne referim mai ales la jocuri cu sumă 0 – un jucător pierde s, i altul câs, tigă cu informat, ie perfectă – toate elementele sunt cunoscute ambilor jucători secvent, iale – jucătorii joacă pe rând Căutare în jocuri | 4 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS pe bazele teoretice puse de von Neumann în 1928 s, i descris în 1944 poate alege cea mai bună mutare pentru orice stare a jocului, dacă avem informat, ie perfectă jucătorul (“eu”) caută să îs, i maximizeze câs, tigul adversarul caută să minimizeze câs, tigul jucătorului ⇒ calculăm pentru fiecare nod din arborele de joc recompensa bazat pe cele 2 idei de mai sus. Căutare în jocuri | 5 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN x x x o o MAX o o x x x o xo MIN xo x x x x x o o xo MAX xo xo x x o o o x o o xo MIN xo +1 xx xx xo o ooo xo MAX xx xxo o xo MIN xxo x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN x x x o o MAX o o x x x o xo MIN xo x x x x x o o xo MAX xo xo +1 x x o o o x o o xo MIN xo +1 xx xx xo o ooo xo MAX xx xxo o xo MIN xxo x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN x x x o o MAX o o x x x o xo MIN xo x x x x x o o xo MAX xo 0 xo +1 x x o o o x o o xo MIN xo +1 xx xx xo o ooo xo MAX xx xxo o xo MIN xxo x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN x x x o o MAX o o x x x o xo MIN xo 0 x x x x x o o xo MAX xo 0 xo +1 x x o o o x o o xo MIN xo +1 xx xx xo o ooo xo MAX xx xxo o xo MIN xxo x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN x x x o o MAX o 0 o x x x o xo MIN xo 0 x x x x x o o xo MAX xo 0 xo +1 x x o o o x o o xo MIN xo +1 xx xx xo o ooo xo MAX xx xxo o xo MIN xxo x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN x x x o o MAX o 0 o 0 x x x o xo MIN xo 0 x x x x x o o xo MAX xo 0 xo +1 x x o o o x o o xo MIN xo +1 xx xx xo o ooo xo MAX xx xxo o xo MIN xxo x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x x x o o MAX o 0 o 0 x x x o xo MIN xo 0 x x x x x o o xo MAX xo 0 xo +1 x x o o o x o o xo MIN xo +1 xx xx xo o ooo xo MAX xx xxo o xo MIN xxo x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x x x o o MAX o 0 o 0 x x x o xo MIN xo 0 x x x x x o o xo MAX xo 0 xo +1 x x o o o x o o xo MIN xo +1 xx xx xo o ooo xo MAX xx -1 xxo o xo MIN xxo x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x x x o o MAX o 0 o 0 x x x o xo MIN xo 0 x x x x x o o xo MAX xo 0 xo +1 x x o o o x o o xo MIN xo +1 xx -1 xx xo o ooo xo MAX xx -1 xxo o xo MIN xxo x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x x x o o MAX o 0 o 0 x x x o xo MIN xo 0 x x x x x o o xo MAX xo 0 xo +1 x 0 x o o o x o o xo MIN xo +1 xx -1 xx xo o ooo xo MAX xx -1 xxo o xo MIN xxo x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x x x o o MAX o 0 o 0 x x x o xo MIN xo 0 x 0 x x x x o o xo MAX xo 0 xo +1 x 0 x o o o x o o xo MIN xo +1 xx -1 xx xo o ooo xo MAX xx -1 xxo o xo MIN xxo x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x x x o o MAX o 0 o 0 x 0 x x o xo MIN xo 0 x 0 x x x x o o xo MAX xo 0 xo +1 x 0 x o o o x o o xo MIN xo +1 xx -1 xx xo o ooo xo MAX xx -1 xxo o xo MIN xxo x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x x x o o MAX o 0 o 0 x 0 x x o xo MIN xo 0 x 0 x x x x o o xo MAX xo 0 xo +1 x 0 x o o o x o o xo MIN xo +1 xx -1 xx xo o ooo xo MAX xx -1 xxo o xo MIN xxo +1 x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x x x o o MAX o 0 o 0 x 0 x x o xo MIN xo 0 x 0 x x x x o o xo MAX xo 0 xo +1 x 0 x o o o x o o xo MIN xo +1 xx -1 xx xo o ooo xo MAX xx -1 xxo +1 o xo MIN xxo +1 x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x x x o o MAX o 0 o 0 x 0 x x o xo MIN xo 0 x 0 x x x x o o xo MAX xo 0 xo +1 x 0 x o o o x o o xo MIN xo +1 xx -1 xx +1 xo o ooo xo MAX xx -1 xxo +1 o xo MIN xxo +1 x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x x x o o MAX o 0 o 0 x 0 x x o xo MIN xo 0 x 0 x x x x o o xo MAX xo 0 xo +1 x 0 x +1 o o o x o o xo MIN xo +1 xx -1 xx +1 xo o ooo xo MAX xx -1 xxo +1 o xo MIN xxo +1 x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x x x o o MAX o 0 o 0 x 0 x x o xo MIN xo 0 x 0 x +1 x x x o o xo MAX xo 0 xo +1 x 0 x +1 o o o x o o xo MIN xo +1 xx -1 xx +1 xo o ooo xo MAX xx -1 xxo +1 o xo MIN xxo +1 x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x x x o o MAX o 0 o 0 x 0 x +1 x o xo MIN xo 0 x 0 x +1 x x x o o xo MAX xo 0 xo +1 x 0 x +1 o o o x o o xo MIN xo +1 xx -1 xx +1 xo o ooo xo MAX xx -1 xxo +1 o xo MIN xxo +1 x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX x MIN 0 x 0 x x o o MAX o 0 o 0 x 0 x +1 x o xo MIN xo 0 x 0 x +1 x x x o o xo MAX xo 0 xo +1 x 0 x +1 o o o x o o xo MIN xo +1 xx -1 xx +1 xo o ooo xo MAX xx -1 xxo +1 o xo MIN xxo +1 x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS MAX 0 x MIN 0 x 0 x x o o MAX o 0 o 0 x 0 x +1 x o xo MIN xo 0 x 0 x +1 x x x o o xo MAX xo 0 xo +1 x 0 x +1 o o o x o o xo MIN xo +1 xx -1 xx +1 xo o ooo xo MAX xx -1 xxo +1 o xo MIN xxo +1 x o Căutare în jocuri | 6 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS spat, iul de căutare poate fi foarte mare s, i parcurgerea completă nepractică ⇒ putem construi arborele doar până la o adâncime n mai departe de adâncimea n, evaluăm nodurile folosind o funct, ie de evaluare e.g., pentru X s, i 0, numărul de linii pe care MAX (mai) poate câs, tiga, minus numărul de linii pe care MIN (mai) poate câs, tiga dacă un jucător poate câs, tiga la următoarea mutare, evaluarea va da un rezultat semnificativ mai mare / mai mic Căutare în jocuri | 7 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS spat, iul de căutare poate fi foarte mare s, i parcurgerea completă nepractică ⇒ putem construi arborele doar până la o adâncime n mai departe de adâncimea n, evaluăm nodurile folosind o funct, ie de evaluare e.g., pentru X s, i 0, numărul de linii pe care MAX (mai) poate câs, tiga, minus numărul de linii pe care MIN (mai) poate câs, tiga dacă un jucător poate câs, tiga la următoarea mutare, evaluarea va da un rezultat semnificativ mai mare / mai mic dar asta se poate aplica s, i dacă un jucător câs, tigă inevitabil în următoarele 2 mutări... s, i as, a mai departe efectul de orizont (horizon effect) – este posibil ca foarte curând după adâncimea n progresul jocului să se schimbe semnificativ →− aici intervine MCTS (mai jos) Căutare în jocuri | 7 / 28 Jocuri cu 2 adversari : Minimax 3+ jucători MCTS Minimax Intrări: S – starea curentă a jocului, e.g. cea init, ială; P – jucătorul care urmează, init, ial MAX n – adâncimea maximă Ies, ire: scorul maxim care poate fi obt, inut de jucătorul MAX 1. dacă S este stare finală, atunci întoarce scor (S) relativ la jucătorul MAX 2. dacă nivel(S) = n atunci întoarce eval(S) 3. dacă P = max atunci v = −∞ altfel v = ∞ 4. pentru fiecare Sj ∈ succ(S) 5. dacă P = max 6. atunci v ←− max(v , minimax(Sj , next_player (P))) 7. altfel v ← − min(v , minimax(Sj , next_player (P))) 8. întoarce v Căutare în jocuri | 8 / 28 Jocuri cu 2 adversari : Tăiere alfa-beta 3+ jucători MCTS nu este neapărat nevoie să construim întreg arborele de joc putem elimina (prune) anumite ramuri pentru că nu au cum să ofere o solut, ie mai bună → − Alpha-beta pruning (Knuth & Moore, 1975) Căutare în jocuri | 9 / 28 Jocuri cu 2 adversari : Tăiere alfa-beta 3+ jucători MCTS nu este neapărat nevoie să construim întreg arborele de joc putem elimina (prune) anumite ramuri pentru că nu au cum să ofere o solut, ie mai bună → − Alpha-beta pruning (Knuth & Moore, 1975) considerăm α cea mai bună valoare găsită pentru jucătorul MAX β cea mai bună valoare găsită pentru jucătorul MIN α-tăiere – nu construim un subarbore copil al unui nod MIN cu v < α β-tăiere – nu construim un subarbore copil al unui nod MAX cu v > β Căutare în jocuri | 9 / 28 Jocuri cu 2 adversari : Tăiere alfa-beta 3+ jucători MCTS Căutare în jocuri | 10 / 28 Jocuri cu 2 adversari : Tăiere alfa-beta 3+ jucători MCTS Căutare în jocuri | 10 / 28 Jocuri cu 2 adversari : Tăiere alfa-beta 3+ jucători MCTS Căutare în jocuri | 10 / 28 Jocuri cu 2 adversari : Tăiere alfa-beta 3+ jucători MCTS Căutare în jocuri | 10 / 28 Jocuri cu 2 adversari : Tăiere alfa-beta 3+ jucători MCTS Căutare în jocuri | 10 / 28 Jocuri cu 2 adversari : Tăiere alfa-beta 3+ jucători MCTS Căutare în jocuri | 10 / 28 Jocuri cu 2 adversari : Tăiere alfa-beta 3+ jucători MCTS Căutare în jocuri | 10 / 28 Jocuri cu 2 adversari : Tăiere alfa-beta 3+ jucători MCTS Căutare în jocuri | 10 / 28 Jocuri cu 2 adversari : Tăiere alfa-beta 3+ jucători MCTS Alfa-beta Intrări: S – starea curentă; P – următorul jucător; α, init, ial −∞; β, init, ial ∞ Ies, ire: scorul maxim care poate fi obt, inut de jucătorul MAX 1. dacă S este stare finală, atunci întoarce scor (S) relativ la jucătorul MAX 2. pentru fiecare Sj ∈ succ(S) 3. dacă P = max atunci 4. α← − max(α, alfa-beta(Sj , next_player (P), α, β)) 5. dacă α > β atunci întoarce β β cutoff 6. altfel 7. β← − min(β, alfa-beta(Sj , next_player (P), α, β)) 8. dacă α > β atunci întoarce α α cutoff 9. dacă P = max atunci întoarce α altfel β Căutare în jocuri | 11 / 28 Jocuri cu 2 adversari : Tăiere alfa-beta 3+ jucători MCTS putem ordona (euristic) succesorii în as, a fel încât să construim întâi cei mai buni succesori Căutare în jocuri | 12 / 28 2 jucători Jocuri cu mai mult, i jucători MCTS Chinese checkers variat, ie germană a jocului american Halma, inventat de George H. Monks în 1880. joc cu informat, ie perfectă pentru 2-6 jucători fiecare jucător deplasează 10 piese dintr-o pozit, ie de start într-o pozit, ie finală pisele se mută în pozit, ia vecină sau sărind peste una sau o serie de piese alăturate Căutare în jocuri | 13 / 28 2 jucători Jocuri cu mai mult, i jucători MCTS Jocuri cu mai mult, i jucători Nu există algoritmi buni consacrat, i. avem 2 strategii: MAXn – generalizare a Minimax pentru n jucători Paranoic – reduce la joc cu 2 jucători în care se presupune că tot, i ceilalt, i colaborează împotriva jucătorului MAX Căutare în jocuri | 14 / 28 2 jucători Jocuri cu mai mult, i jucători : Maxn MCTS Generalizarea Minimax pentru n jucători Nodurile arborelui de joc sunt n-tuple, în care elementul pe pozit, ia i este scorul jucătorului i. Pentru non-frunze, valoarea Max n a unui nod în care jucătorul i mută este valoarea Max n a succesorului pentru care a i-a componentă din vector este maximă. Căutare în jocuri | 15 / 28 2 jucători Jocuri cu mai mult, i jucători : Maxn MCTS Maxn Intrări: N – starea curentă; P – jucătorul care urmează să mute; n – adâncime maximă Ies, ire: scorul maxim care poate fi obt, inut de jucătorul MAX 1. dacă N este stare finală atunci întoarce N[P] 2. dacă nivel(N) = n atunci întoarce eval(N, P) 3. next ← − {} 4. pentru fiecare sj ∈ succ(N) 5. − next ∪ Max n (sj , next_player (P)) next ← 6. best ← − tuple ∈ next, cu tuple[P] maxim 7. întoarce best Căutare în jocuri | 16 / 28 2 jucători Jocuri cu mai mult, i jucători : Maxn MCTS Atent, ie! Pot exista mai multe valori egale Maxn într-un arbore Rezultatul poate depinde drastic de felul în care se face alegerea – e.g. (2, 3, 3) vs. (2, 1, 7) Alfa-beta în adâncime (deep pruning) nu poate fi aplicat Maxn -shallow pruning, Korf, 1991 (analog cu alfa-beta dar cu performante proaste) Căutare în jocuri | 17 / 28 2 jucători Jocuri cu mai mult, i jucători : Paranoic MCTS Paranoic – reduce jocul la 2 jucători – MAX s, i tot, i ceilalt, i jucători ca un adversar colectiv este o strategie paranoică – consideră că tot, i ceilalt, i jucători se aliază împotriva lui MAX în fiecare nod scorul este scorul jucătorului MAX minus scorul tutoror celorlalt, i jucători fiind la fel ca Minimax: există o unică valoare în fiecare nod se poate utiliza tăiere alfa-beta, dar pe măsură ce numărul jucătorilor cres, te beneficiul adus de tăiere scade. pentru jocuri cu 3-6 jucători, adâncimea este cu 20-50% mai mare decât la Maxn. Căutare în jocuri | 18 / 28 2 jucători Jocuri cu mai mult, i jucători : Paranoic MCTS Căutare în jocuri | 19 / 28 2 jucători 3+ jucători Monte Carlo Tree Search MCTS – algoritm probabilistic care utilizează o serie de simulări aleatoare pentru a expanda selectiv arborele de joc. metodă bună pentru luarea deciziilor în probleme cu un spat, iu de căutare mare. best-first search care înlocuies, te euristica cu rezultatele unor simulări Monte-Carlo. metodele de tip Monte Carlo folosesc es, antionare aleatoare repetată pentru a obt, ine informat, ii despre procese determinsite. se bazează pe 2 ipoteze: 1. adevărata valoare a unei act, iuni (mutare în joc) poate fi aproximată utilizând simulări aleatoare. 2. valorile astfel obt, inute pot fi utilizate pentru a ajusta politica de select, ie spre o cea mai bună strategie. Căutare în jocuri | 20 / 28 2 jucători 3+ jucători Monte Carlo Tree Search baza metodei este utilizarea unei unde de joc / simulări (playout). Playout – un joc jucat cu mutări aleatoare dintr-o anumită stare până la starea finală, obt, inându-se un scor. nu utilizează spat, iu suplimentar pentru că nu construies, te noduri în arbore – în urma simulării se ret, ine doar scorul final. fiecărui nod construit i se asociază un merit (sau calitate – quality), bazat pe rezultatul simulărilor. se construies, te un arbore de joc part, ial, format din stările cele mai promit, ătoare. algoritm de tip stop-anytime – ne putem opri oricând s, i avem o solut, ie, care este cu atât mai bună cu cât am explorat mai mult. Căutare în jocuri | 21 / 28 2 jucători 3+ jucători Monte Carlo Tree Search : Etapele algoritmului La fiecare iterat, ie a algoritmului avem 4 pas, i: select, ie | construct, ie(expandare) | simulare | propagare (backpropagation) Căutăm un nod care nu este încă (complet) expandat – pornim de la rădăcină s, i aplicăm recursiv o politică de select, ie a copiilor pentru a găsi cel mai potrivit nod căruia să îi construim un copil. Căutare în jocuri | 22 / 28 2 jucători 3+ jucători Monte Carlo Tree Search : Etapele algoritmului La fiecare iterat, ie a algoritmului avem 4 pas, i: select, ie | construct, ie(expandare) | simulare | propagare (backpropagation) Construim unul sau mai multe noduri noi, corespunzătoare unor act, iuni încă neexplorate. Căutare în jocuri | 22 / 28 2 jucători 3+ jucători Monte Carlo Tree Search : Etapele algoritmului La fiecare iterat, ie a algoritmului avem 4 pas, i: select, ie | construct, ie(expandare) | simulare | propagare (backpropagation) Realizăm o simulare pornind din nodul/nodurile noi. Căutare în jocuri | 22 / 28 2 jucători 3+ jucători Monte Carlo Tree Search : Etapele algoritmului La fiecare iterat, ie a algoritmului avem 4 pas, i: select, ie | construct, ie(expandare) | simulare | propagare (backpropagation) Propagăm către rădăcină rezultatul obt, inut. Căutare în jocuri | 22 / 28 2 jucători 3+ jucători Monte Carlo Tree Search : Algoritm MCTS(rădăcină) 1. (v , s) ← − nodul rădăcină, corespunzător stării s0 , parinte(v ) ← −⊥ 2. pentru fiecare unitate de buget repetă 3. cât timp s nu este stare finală 4. dacă v este complet expandat atunci (v , s) ← − select(v ) altfel break 5. a← − alege_actiune(s) am ajuns la nodul care trebuie expandat 6. construies, te (v ′ , s′ ), cu s′ ← − next(s, a) s, i parinte(v ′ ) ← − (v ′ , s′ ) − v ; (v , s) ← 7. cât timp s nu este stare finală 8. a← − act, iune disponibilă în s, aleasă aleator 9. s←− next(s, a) 10. r← − recompensa(s′ ) 11. cât timp v ̸= ⊥ 12. N(v ) ← − N(v ) + 1 13. Q(v ) ← − actualizare_Q(v , r ) 14. v← − parinte(v ) 15. (v , s) ← − select(radacina) 16. întoarce a, cu s = next(s0 , a) cea mai bună act, iune Căutare în jocuri | 23 / 28 2 jucători 3+ jucători Monte Carlo Tree Search : Discut, ie Ce strategii se folosesc pentru select, ie? Exploatare: Selectăm stări din care s-a câs, tigat des s, i au fost parcurse de multe ori Explorare: Selectam stări cu put, ine simulări anterioare Căutare în jocuri | 24 / 28 2 jucători 3+ jucători Monte Carlo Tree Search : Discut, ie Select, ie folosind UCT – Upper Confidence Bound 1 applied to trees s ! Q(s′ ) 2 · ln(N(s)) select(s) ← − argmaxs′ ∈succ(s) +C· N(s′ ) N(s′ ) Echilibrează calitatea unui nod copil cu gradul de explorare al părintelui în raport cu copilul. Căutare în jocuri | 25 / 28 2 jucători 3+ jucători Monte Carlo Tree Search : Discut, ie Backpropagation poate folosi, pentru propagarea de la s′ la părintele s: Vmed · Wmed + Vr · Nr V (s) ← − Wmed · Nr Vmed — media valorilor nodurilor copii Wmed — ponderea acestei medii Vr — mutarea cu cel mai mare număr de simulări Nr — numărul de ori de care s-a jucat Vr Căutare în jocuri | 26 / 28 2 jucători 3+ jucători Monte Carlo Tree Search : Discut, ie MCTS converge lent spre valorile Minimax, dar este mai eficient decât tăierea alfa-beta. nu găses, te întotdeauna cea mai bună mutare, dar are, în general, un succes rezonabil în cazul alegerii mutărilor care duc la s, anse mari de câs, tig. poate să nu detecteze ramuri care, folosind o anumită line de joc, duc la un rezultat semnificativ diferit Light playouts — playout complet aleator Heavy playouts — euristici/politici pentru selectarea mis, cării următoare în timpul simulării Căutare în jocuri | 27 / 28 2 jucători 3+ jucători Monte Carlo Tree Search : Discut, ie MoGo – A participat în 30 de turnee între 2006 s, i 2010 (9 x 9 GO) A câs, tigat contra profesionis, tilor MoGo învinge pe campionul Myungwan Kim, august 2008, utilizand MCTS FUEGO – a învins mai mult, i campioni la 9 x 9 GO în 2009 MoHex – devine campion la jocul Hex în 2009 Căutare în jocuri | 28 / 28 2 jucători 3+ jucători MCTS Mult, umesc! https://forms.gle/DJUdkejstkvyNRF5A Feedbackul este binevenit! Căutare în jocuri | 28 / 28