Note de curs, clasele 9-10, 22 martie 2013

From Algopedia
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Am petrecut o lecție vorbind mai puțin despre algoritmi și mai mult despre importanța de a lucra la proiecte „reale”. Notele de curs adaugă lucruri noi (marcate cu „NOU”), fiindcă nu vreau să mai petrecem încă o lecție pe acest subiect.

Motivație

De ce vă tot îndemn să lucrați la proiecte mai mari?

  • Veți avea utilizatori. :-) Un program de olimpiadă nu este propriu-zis „folosit”. Un program real este folosit de oameni care vă pot da sugestii, semnala buguri, vor iubi sau vor urî programul vostru.
  • Veți lua singuri decizii de design. Un program de olimpiadă nu necesită mari decizii, dincolo de numele identificatorilor și mici detalii de implementare (Kruskal vs. Prim, să zicem). Un program real poate evolua într-o infinitate de direcții, pe care voi le prioritizați cum vreți. De exemplu, îmi îmbunătățesc programul de șah prin adăugarea unei tabele de deschideri sau prin optimizarea algoritmului alpha-beta?
  • Vă veți obișnui cu programe mai complexe. Veți avea nevoie de unit testing, de unelte pentru controlul versiunilor (chiar și când lucrați solo).
  • Pe termen lung, bunele practici inginerești contează la fel de mult ca algoritmii.
  • Conexiunea la Internet este un lucru fascinant. Utilizatorii voștri vor vota feature-uri noi pe care le vor, sau jocul vostru logic poate juca împotriva oamenilor de pretutindeni și a altor calculatoare.
  • Câștigați reputație, posibil și bani. „Am un site folosit de 1.000.000 de oameni pe lună” este un motiv de mândrie în orice CV.

Trăsături generale

Dincolo de subiectul programului în sine (joc, utilitar, site web), există niște trăsături comune:

  • salvarea pe disc, în fișiere în format propriu, în formate publice sau într-o bază de date
  • conexiunea la internet (pentru actualizări, pentru comunicarea cu alte copii ale programului etc.)
  • componentă grafică (mai evoluată sau mai rudimentară, dar trebuie să existe o interfață)
  • pentru jocuri, niveluri de dificultate, generarea nivelurilor și a campaniilor etc.
  • un proiect suficient de mare trebuie să aibă o listă de email, o pagină de buguri, o pagină wiki

Variante de grafică

  • niciuna. Folosim modul text, cu afișarea datelor pe ecran. Se pretează la programe utilitare.
  • modul text „deștept” (cu afișare la orice coordonate). Se pretează la jocuri și programe unde grafica nu este factorul principal. Poate fi ulterior înlocuit cu o grafică mai performantă.
  • în browser. Primim de-a gata tabele, imagini, rudimente de animație, biblioteci puternice de JavaScript. Se pretează la programe unde viteza nu este esențială.
  • GTK / QT. Sunt modalități ușoare de a construi interfețe grafice (butoane, cutii de text etc.).
    • un moment bun pentru a învăța concepte de programare orientată pe obiect: clase, proprietăți, metode, evenimente.
  • OpenGL -- acolo unde grafica e totul!

Mastermind

Am folosit acest joc simplu pentru a evidenția că nu mai există o singură cale de a scrie un program. Există nenumărate strategii de joc, unele mai bune ca altele.

  • Cum ghicește calculatorul un număr ascuns de noi?
    • într-o primă variantă, stochează toate numerele compatibile cu răspunsurile primite anterior, și alege una la întâmplare.
    • într-o variantă mai deșteaptă, alege întrebarea astfel încât, indiferent de răspunsul primit, noua listă de numere compatibile să fie cât mai mică.
  • Cum ascunde calculatorul un număr pentru ca omul să-l ghicească?
    • într-o variantă simplă, calculatorul alege un număr la început, apoi răspunde la întrebări
    • într-o variantă mai deșteaptă (și mai perfidă), calculatorul nu alege de la început un număr. El menține o listă de numere compatibile cu toate răspunsurile date anterior. La întrebarea prezentă, dă acel răspuns care să ducă la o nouă listă cât mai mare.
    • *acesta este un punct de plecare pentru nivelul de joc: la niveluri mici, calculatorul „ne ajută” prin răspunsuri care triază rapid lista de posibilități.

Șah (ca exemplu de minimax / alpha-beta)

Nu vă încurajez neapărat să implementați un program de șah. Are avantaje și dezavantaje:

  • avantaj: comunitatea este uriașă. Există nenumărate documentații și tutoriale specializate în programarea unui joc de șah
  • avantaj: există servere de șah unde puteți conecta programul vostru ca să vedeți cât de bun este (freechess.org)
  • avantaj: sunt nenumărate componente care fac un program puternic și toate sunt interesante din punct de vedere algoritmic
  • dezavantaj: regulile jocului sunt complexe și necesită atenție la implementare
  • dezavantaj: este puțin probabil să fiți „cei mai buni” sau să vă atrageți o bază fidelă de utilizatori. Există programe fantastic de puternice, de bine cizelate.

Probleme interesante:

  • algoritmul alpha-beta este punctul de pornire
  • NOU optimizări de alpha-beta (pot crește adâncimea arborelui cu 2-3-4 mutări)
  • NOU cum stocăm tabla de joc? Cel mai mare consumator de timp este algoritmul de generare a mutărilor legale dintr-o poziție. De aceea, structura de date folosită pentru tablă este importantă.
  • NOU euristica statică: cum determin valoarea unui lanț sănătos de pioni? Dar a unui rege expus în centrul tablei?
  • carte de deschideri: niciun algoritm nu se descurcă bine în poziția inițială
  • tabele precalculată de finaluri: niciun alpha-beta nu vede destul de multe mutări înainte ca să știe să dea mat cu cal și nebun
  • gestiunea timpului: câte secunde să-mi aloc pentru mutarea următoare?
  • pondering: ce analizez în timp ce aștept să mute adversarul?
  • transpoziții / repetări
  • când accept o remiză? când am opțiunea să închid partida prin șah etern, o aleg sau nu?

NOU Alte jocuri tratabile cu alpha-beta

Majoritatea acestor jocuri au reguli mult mai simplu de implementat decât cele de șah:

Jocuri unde alpha-beta nu se comportă bine

La unele jocuri, factorul de ramificare al arborelui de joc este mult prea mare pentru a mai putea folosi alpha-beta. Bunăoară, la table, ca să evaluez toate mutările posibile dintr-o poziție, trebuie să iau în calcul toate cele 21 de zaruri posibile (unele mai probabile ca altele) și toate modurile de a efectua mutarea pentru un zar. Rezultă un factor de ramificare de circa 400 (comparat cu șahul, unde este cam 35).

La aceste jocuri, implementarea pornește de obicei de la principii strategice.

NOU Jocuri demonstrabile

Cu algoritmi deștepți și suficientă răbdare, unele jocuri pot fi demonstrate. De exemplu, în cazul în care amândoi jucătorii joacă atent, X și 0 este remiză.

Cu timpul, multe jocuri au fost demonstrate: dame, țintar, unele variante mai mici de hex, unele linii din antișah. Altele așteaptă oameni dedicați care să le analizeze!

Un algoritm util în rezolvarea jocurilor este Proof Number Search.

NOU Jocuri de o singură persoană

Deși programul poate fi doar un executor al mutărilor omului, este loc de algoritmi deștepți:

  • Minesweeper
    • Generarea tablei nu este banală. Ea trebuie făcută după primul click, pentru ca jucătorul să nu dea click pe o mină din prima (voi nu v-ați enerva?)
    • Opțional, este și mai util ca primul pătrat deschis să fie un 0, altfel problema este doar amânată pentru a doua mutare.
    • Când utilizatorul dă click pe un 0, toate pătratele din jur trebuie deschise recursiv
    • Are soluție unică? Sau riscăm să enervăm utilizatorul la sfârșit, când trebuie să ghicească? Putem scrie un motor de rezolvare a unei table generate, imediat după prima mutare.
    • „Hints”: îi putem arăta unui începător un pătrat pe care l-ar fi putut deduce singur.
  • pasiențe: FreeCell, Spider solitaire, altele
    • Acolo unde informația este totală (nu există cărți pe dos), este util un motor de rezolvare, ca să putem da indicii
    • Dar rezolvarea nu este simplă, sau uneori nici nu s-a descoperit una
    • A existat o conjectură că orice poziție inițială de FreeCell poate fi câștigată. Ulterior, au fost găsite poziții nerezolvabile.

NOU Jocuri de aventuri text

Genul de jocuri „text adventure” sau „text RPG” pare să dispară încet-încet, dar are o bază de fani fideli. Aceste jocuri se joacă în linia de comandă, cu comenzi în limbaj natural ("take sword"; "enter castle"). Uneori pot exista și elemente grafice (deși singurele imagini cu adevărat frumoase sunt ASCII art). :-)

Provocarea în scrierea unui joc de aventuri text este un interpretor (parser) de limbaj natural. Programul trebuie să înțeleagă fraze simple sau complexe: "go north"; "kill orc"; "kill orc with sword"; "pick up book n table").

Limba română este dificil de implementat pentru că are „forme flexionare”: un verb are 30 de forme în funcție de timp, număr și persoană. Limba engleză are propriile ei probleme din cauza conciziei, care duce la raporturi de omonimie adesea caraghioase:

  • Time flies like an arrow. = Timpul zboară ca săgeata.
  • Time flies like an arrow. = Muștele timpului iubesc o săgeată. :-)

În plus, un proiect interesant este un meta-joc: o unealtă care să permită crearea de jocuri de aventuri, prin specificarea scenariului:

  • camerele de pe hartă, cu legăturile între ele
  • obiectele din fiecare cameră, cu atribute (poate fi luat, poate fi folosit cu alte obiecte, descrierea lui când jucătorul îl examinează etc.)
  • personajele din joc, cu algoritmul de comportament al fiecăruia

Există site-uri care permit crearea și jucarea de jocuri: http://www.textadventures.co.uk/, http://www.web-adventures.org/

NOU Grafică 2D / 3D

Tetris

  • Chiar și executarea oarbă a comenzilor jucătorului este un proiect interesant.
  • Multe implementări de Tetris au eșuat pentru că nu răspund bine la comenzi.
  • Este nevoie de temporizare pentru diferite niveluri de dificultate.
  • Este interesant un algoritm pentru calculator: Unde pun următoarea piesă? Dar dacă am acces la preview și văd ce urmează?
    • Cum măsor valoarea unei strategii? Măsor scorul maxim pe care este în stare să îl obțină programul.
  • O variantă extraordinar de atractivă este cea colaborativă: doi oameni (sau un om și un calculator) în același pahar

Alte jocuri 2D implementabile în modul text deștept

Labirinturi 2D

  • Cum generăm un labirint? Arborii parțiali minimi ne ajută!
  • Detectarea coliziunilor (presupunând că mișcarea nu este discretă, ci personajul poate sta între două căsuțe în matrice)
  • Temporizare
  • Sunet, imagini drăguțe, împușcături, bombe, comori de cules, orice poate face jocul mai atractiv.
  • Exemplu: Dyna Blaster

Jocuri 3D

  • Grafica este un subiect în sine despre care s-au scris cărți fără număr.
  • OpenGL oferă primitive avansate pentru grafică
  • Este instructiv și să faceți unele lucruri de la zero (folosind doar primitive de punct, linie și cerc).
  • Exemplu: NetWars
  • FPS (First-person shooter): sunt greu de scris, este recomandat să citiți cărți de specialitate

Site-uri web („chestii serioase”)

Jocurile sunt amuzant de programat, dar și un program „serios” poate fi distractiv. În plus, utilizatorii vă apreciază mai mult dacă programul vostru chiar le rezolvă o nevoie reală, decât dacă este doar o distracție de moment.

Pe Internetul românesc sunt enorm de multe lucruri de făcut. Nu sunt neapărat lucruri simple (altfel ar fi fost deja făcute), dar merită efortul. Dacă vi se pare prea complicat să începeți de la zero, există mormane de proiecte care au nevoie de ajutor. Vă puteți alătura unuia dintre ele.

Generalități

Înainte de a vă apuca de treabă, încercați să înțelegeți principiile dezvoltării de site-uri web:

  • structura unei pagini web: HTML, CSS, Javascript, PHP (sau alt limbaj din „backend”).
  • cum funcționează serverul web folosit (Apache, nginx etc.)
  • cum căutați într-un log ca să vedeți ce probleme apar
  • ce înseamnă DNS resolution
  • ce este un cookie, cum puteți citi sau scrie unul în limbajul folosit
  • care este diferența dintre o pagină statică și una dinamică
  • care este diferența dintre o cerere GET și una POST
  • rudimente de baze de date (MySQL sau altceva)
  • principii de uzabilitate: fără <blink> tag! :-)

Există sisteme la cheie:

  • Mediawiki -- softul pe care rulează Wikipedia
  • Drupal, Joomla -- sisteme la cheie pentru crearea de conținut
  • WordPress -- gândit mai ales pentru bloguri
  • CakePHP -- cadru de dezvoltare PHP (creează automat paginile, legăturile între ele, schema bazei de date etc.)

Totuși, orice site serios are nevoie de atât de multe particularizări, încât mai bine vă scrieți totul de la zero.

Idei de site-uri

  • site de evaluări, modelat după Yelp
    • Permite evaluarea de restaurante, baruri, magazine, doctori, școli...
    • În România nu există nimic notabil în acest domeniu.
    • Probabil, parte din explicație este și apatia populației de a-și dedica timp pentru a evalua locurile în care au fost.
    • Alegerile bazate pe recomandarea a 1-2 prieteni sunt periculoase. Alegerile bazate pe sute de voturi sunt mai bine informate.
  • site de votat online
  • site pentru traduceri colaborative de subtitrări
    • de investigat dacă există așa ceva. http://addic7ed.com are așa ceva, dar comunitatea de limbă română pare mică.
  • site pentru înregistrarea de informații personale
    • programul de somn, dietă, greutate, exerciții fizice făcute
    • Probabil nu are valoare fără o aplicație pentru mobil.
  • site pentru oferirea și găsirea de muncă voluntară
    • „plec la munte o săptămână, cine poate sta cu câinele meu”?
  • îmbunătățiri la vianuarena
    • reminder către autor pentru probleme pe care nu le-a etichetat
    • monitorizarea evaluatorului