Cum rezolvăm o problemă de căutare?

1. Observăm care sunt datele de intrare și le introducem în totalitate într-un fișier.
2. Decidem cum abstractizăm problema la un graf (cine vor fi nodurile și muchiile). De obicei nodurile conțin o reprezentare a starii problemei (o configurație) iar muchiile reprezintă tranziții de la o stare la alta (de exemplu, mutarea unei entități în cadrul configurației).
3. Decidem cum memorăm o stare. De exemplu: dacă avem o colecție de date putem folosi o listă sau un tuplu. Dacă datele sunt ca un fel de proprietăți ale configurătiei, putem folosi un dicționar sau o instanță a unei clase definite pentru a ilustra o configurație.
4. Folosim șabloanele date la laborator pentru algoritmi și integrăm codul nostru în ele
5. Parsăm fișierul de input si memoram starea inițială, și, eventual, stările finale.
6. Ne gândim dacă există moduri de a determina dacă problema nu are soluții încă din starea inițială. De exemplu în starea finală apare un item care nu era în cea inițială și nici nu are cum să apară printr-o mutare. Sau nu sunt suficiente locuri valide pentru a realiza mutările necesare. etc.
7. Scriem codul pentru generarea succesorilor unei stări, gândindu-ne la toate mutările posibile pe acea stare inițială și făcâând o listă cu rezultatele acestor mutări. Atenție pentru fiecare mutare ilustrată repornim de la starea pentru care generăm succesorii, deci ar fi bine sa facem câte o copie înainte de mutare, ca să nu stricăm informațiile inițiale și să avem date greșite când generăm a doua mutare
8. Scriem o funcție care testează dacă o configurație e nod scop, conform cerințelor
9. Căutăm idei de euristici. Pentru a găsi euristici, luăm câteva exemple de stări nefinale și câteva exemple de stări finale și le observăm. Ne punem întrebarile:
   • Ce elemente se schimbă pentru a ajunge într-o stare finală ?
   • Câte elemente se schimbă? (în special când avem colecții de elemente: vectori sau matrici)
   • Schimbarea unui element influențează schimbarea altor elemente? Dacă da, atunci trebuie să împărțim euristica la câte elemente se schimbă, deoarece dacă o mutare schimbă de exemplu 2 elemente dar o numărăm pentru fiecare element, ne iese o estimare mai mare decât costul real (neadmisibilă)
   • În câți pași se schimbăun element șî de ce factori depinde? Pentru această întrebare putem încerca simplificări ale contextului, dar de care știm sigur că nu măresc numărul de pași ci doar eventual îl micșorează. De exemplu dacă vrem să vedem în câte mutări e parcursă o hartă reprezentată printr-o matrice, în care sunt și obstacole (celule în care nu putem intra). O simplificare bună e ignorarea obstacolelor (un obstacol înseamnă un ocol, deci mai mulți pași, astfel, ignorarea lor, nu poate decât să scadă numărul de pași estimat).
10. Scriem o funcție de afișare care pornește de la informația unui nod și scrie în mod ușor de înțeles această informație. Apelăm funcția pentru fiecare nod dintr-un drum-soluție.
11. Aplicăm eventuale diverse analize cerute în enunț abia după ce am verificat că programul merge. De exemplu, rularea cu timeout sau afișarea timpului de rulare, adăugarea unor contoare pentru numărul de noduri generate (nu trebuie să faceți aceste lucruri decât dacă e specificat clar în enunțul problemei voastre).

Cum implementăm un joc (cu jucător automat, folosind algoritmii studiați?

1. Observăm care sunt parametri ceruți de joc (diverse setări necesare generării tablei și stării inițiale, precum dimensiunea tablei, sau cine mută primul).
2. Folosim șabloanele date la laborator pentru algoritmi și integrăm codul nostru în ele
3. Ne gândim la o structură care să memoreze tabla de joc (cel mai adesea e o matrice sau un graf). Generăm tabla inițială folosind structura cerută.
4. Ne gândim la informațiile necesare unei mutări. Scriem bucla jocului în care repetitiv cerem aceste informații jucătorului, lăsând apoi calculatorul să genereze o mutare.
5. În cazul jocurilor cu scor sau alte date în plus pe lângă tabla de joc, memorăm acele date în instanța clasei Joc, sub formă de noi proprietăți
6. Scriem o funcție de afișare a tablei de joc cu toate informațiile necesare (cum arată tabla, care este scorul (în caz că jocul are scor), cine urmează să mute etc.)
7. Scriem funcția de generare a mutărilor. Funcția trebuie să genereze toate mutările posibile. De obicei presupune parcurgerea întregii table de joc și selecționarea simbolurilor care pot fi mutate, sau, după caz, a locurilor libere în care putem plasa un simbol nou.
8. Ne gândim la toate cazurile în care jocul se poate finaliza (de obicei cu remiză sau când câștigă un jucător). Scriem funcția care tstează daca tabla îndeplinește condiția de finalizare a jocului.
9. Căutăm idei de evaluare a stării pentru a obține numărul corespunzător pentru arborele minimax (în cazul în care starea respectivă este o frunză). Vom pune numere foarte mari (care nu pot fi obținute prin funcția de evaluare a unei stări nefinale) pentru cazul în care câștigă MAX, numere foarte mici pentru cazul în care câștigă MIN și 0 pentru remiză. Pentru a găsi funcția de estimare a scorului, luăm căteva exemple de configurații (de obicei cu o tablă mai plină, ca să ne dăm seama ușor de caracteristicile jocului) și incercăm întâi intuitiv să decidem pentru care dintre jucători este starea respectivă mai favorabilă, gândindu-ne la ce mutări sunt posibil șî cine câștigă în ce situație. Incercăm apoi să ne dăm seama pe ce se bazează acea intuiție: sunt mai multe simboluri într-o anumită zona a tablei, e mai aproape un jucător de a face o configurație câștigătoare, un jucător mai are un pic șie blocat (rămâne fără mutări), sunt simboluri în locuri mai favorabile pe tablă etc. Atunci când avem mai mulți factori care influențează cât de favorabilă e o stare, putem să le dăm și niște ponderi în evaluare. Nu uităm să adunăm factorii care influențează pozitiv și să-i scădem pe cei care influențează negativ (în general, dacă jocul e simetric, adunăm factorii pentru MAX și scădem aceiași factori, în același format pentru MIN)
10. Si apoi.... ne jucam cu jocul nou creat :) și verificăm dacă "ne bate" sau nu.