= Prolog: Metro Board Game = * Responsabil: [[cs@andreiolaru.ro|Andrei Olaru]] * Deadline soft: **22.05.2017**, apoi depunctare 0.5p/ zi * Deadline hard: __24.05.2017 ora 23.59__ * Data publicării: 06.05.2017 * Data ultimei modificări: 06.05.2017 * Tema se va încărca pe [[http://vmchecker.cs.pub.ro|vmchecker]] * Data tester-ului: 15.05.2017 * [[http://cs.curs.pub.ro/2016/mod/forum/view.php?id=5772|Forum temă]] * [[#changelog]] == Obiective == * utilizarea predicatelor în limbajul Prolog pentru a exprima relații între concepte. * înțelegerea procesului de unificare în Prolog. * înțelegerea și utilizarea mecanismelor oferite de Prolog pentru găsirea automată de soluții prin backtracking. == Jocul Metro == Jocul [[http://www.bluering.nl/sieuwert/games/metro/|Metro]] este un board game de 1 sau mai mulți jucători, în care fiecare jucător dorește să câștige un număr cât mai mare de puncte. O implementare a jocului (în Java) se poate observa la [[http://www.bluering.nl/sieuwert/games/metro/|acest link]]. === Harta === Jocul se desfășoară pe o tablă pătrată (//harta//) în care se pot plasa cărți (//tiles//) pătrate, conform cu un caroiaj de dimensiune ''d x d''. Harta reprezintă un spațiu unde se vor forma //trasee// de metrou. Fiecare carte (//tile//) conține 4 conexiuni între puncte de pe marginile cărții, conexiuni care formează, împreună cu celelalte cărți, traseele de metrou de pe hartă. Notăm spațiile de pe hartă cu perechi ''(X, Y)'', cu X ∈ [1, d] și Y ∈ [1, d], unde X este coordonata de pe orizontală, cu 1 fiind coloana cea mai din stânga, iar Y este coordonata de pe verticală, cu 1 fiind linia cea mai de sus. Descrierea hărții este dată în fișierul ''T3base.pl'' prin predicatele ''width/1'', ''height/1'', și ''limits/4''. Pe fiecare latură a hărții se află ''d'' puncte de intrare în hartă și ''d'' puncte de ieșire din hartă, numite în joc //trenuri//, respectiv //gări//. Obiectivul unui jucător este de a conecta, folosind conexiunile de pe cărțile plasate în joc, trenuri cu gări, obținând //trasee// în așa fel încât traseele obținute să fie **cât mai lungi**. Un traseu primește un număr de puncte egale cu numărul de cărți prin care trece (poate trece prin unele cărți de mai multe ori). În centrul hărții se află 4 spații care nu sunt disponibile pentru a pune cărți, care conțin gări (nu și trenuri). Un traseu care ajunge în una dintre cele 8 gări din centrul hărții primește un număr de puncte dublu față de lungimea sa în număr de cărți parcurse. Spațiile din centrul hărții sunt descrise în fișierul ''T3base.pl'' prin predicatul ''center_space/2''. Descrierea punctelor de intrare și ieșire este dată în fișierul ''T3base.pl'' prin predicatele ''entry_point/3'' și ''exit_point/3''. Mai jos se găsește o tablă de joc de dimensiune 8x8: {{ .:board.png?direct&500 | Tablă de joc 8x8}} === Cărțile din joc === Există în joc 10 cărți diferite. Vom nota aceste cărți ''#​1''​ ... ''#​10'' ​-- aceștia vor fi **identificatorii** cărților. Fiecare care conține 4 puncte de intrare și 4 puncte de ieșire, câte unul pe fiecare latură. Fiecare carte conține 4 conexiuni între câte un punct de intrare și un punct de ieșire. Vom reprezenta fiecare carte ca fiind o listă de 4 numere din mulțimea ''​+0'',​ ''​+1'',​ ''​+2'',​ ''​+3'',​ fiecare număr reprezentând pe a câta latură ajunge conexiunea față de latura de unde a pornit, în sens trigonometric,​ latura de unde a pornit fiind latura 0. Conexiunile sunt date în sensul trigonometric al laturilor din care pornesc. Avem următoarele cărți (în aceste imagini conexiunile încep cu conexiunea care pornește de pe latura din stânga): | {{.:1.png?nolink&100|Cartea #1}} | {{.:2.png?nolink&100|Cartea #2}} | {{.:3.png?nolink&100|Cartea #3}} | | Cartea ''#1'': ''+0, +0, +0, +0'' | Cartea ''#2'': ''+0, +0, +1, +3'' | Cartea ''#3'': ''+0, +1, +1, +2'' | | {{.:4.png?nolink&100|Cartea #4}} | {{.:5.png?nolink&100|Cartea #5}} | {{.:6.png?nolink&100|Cartea #6}} | | Cartea ''#4'': ''+0, +2, +0, +2'' | Cartea ''#5'': ''+0, +2, +3, +3'' | Cartea ''#6'': ''+1, +1, +1, +1'' | | {{.:7.png?nolink&100|Cartea #7}} | {{.:8.png?nolink&100|Cartea #8}} | {{.:9.png?nolink&100|Cartea #9}} | | Cartea ''#7'': ''+1, +2, +2, +3'' | Cartea ''#8'': ''+1, +3, +1, +3'' | Cartea ''#9'': ''+2, +2, +2, +2'' | | | {{.:10.png?nolink&100|Cartea #10}} | | | | Cartea ''#10'': ''+3, +3, +3, +3'' | | Toate cele 10 cărți sunt descrise în fișierul ''T3base.pl'' prin predicatul ''tile/5''. Când sunt plasate în spațiul de joc, cărțile pot fi rotite așa cum dorește jucătorul. Există 4 rotații: * ''R0'' -- cartea este în poziția originală, așa cum apare în tabelul de mai sus; * ''R1'' -- cartea este rotită 90° în sens trigonometric față de poziția originală; * ''R2'' -- cartea este rotită 180°; * ''R3'' -- cartea este rotită 270° în sens trigonometric față de poziția originală. Rotațiile sunt descrise în fișierul ''T3base.pl'' prin predicatul ''rotation/2''. Cărțile ''#1'', ''#6'', ''#9'' și ''#10'' nu are sens să fie rotite (au doar rotația ''R0''); cărțile ''#4'' și ''#8'' au două rotații diferite (''R0'' și ''R1''); iar celelalte cărți au 4 rotații posibile diferite: ''R0'', ''R1'', ''R2'' și ''R3''. O rotație a unei cărți se reflectă într-o deplasare circulară a listei de conexiuni care o reprezintă. De exemplu, cartea ''#3'', reprezentată de lista ''+0, +1, +1, +2'', rotită o dată în sens trigonometric (deci cu rotația ''R1'') va fi reprezentată prin lista ''+2, +0, +1, +1''. Vom numi ''​R0''​..''​R3''​ **identificatorii** pentru rotația unei cărți. Vom numi perechea dintre identificatorul unei cărți și identificatorul ​rotației sale //carte rotită//. === Exemplu === Mai jos aveți un exemplu de stare de joc. În aceasta, avem două trasee //complete// (sau //închise//), marcate cu verde și cu albastru. Avem de asemenea un traseu care pornește de la un tren (un punct de intrare), dar nu ajunge la o gară, și este deci un traseu //deschis// (traseul marcat cu roșu). Cele două trasee închise din exemplu aduc jucătorului punte după cum urmează: 5 puncte pentru traseul albastru, care trece de două ori printr-o carte; și 5 puncte pentru traseul verde. În total, 10 puncte. {{ .:game.png?direct&500 |Exemplu de stare a jocului}} În acest exemplu, avem 6 cărți plasate pe hartă, având în spațiile ''(2, 1)'', ''(3, 1)'', ''(2, 2)'', ''(3, 2)'', ''(1, 3)'' și ''(2, 3)'' cărțile rotite ''(#5, R0)'', ''(#6, R0)'', ''(#7, R2)'', ''(#2, R1)'', ''(#9, R0)'' și respectiv ''(#3, R2)''. === Trasee === Un traseu va fi reprezentat prin punctul său de intrare și o listă de cărți rotite care compun calea. Punctul de intrare este coordonata spațiului din afara hărții de unde vine trenul, înainte să intre în hartă. Similar cu punctul de intrare putem defini punctul de ieșire al traseului. Astfel, în exemplul de mai sus traseul albastru are punctul de intrare ''(2, 0)'' și lista de cărți rotite ''(#5, R0)'', ''(#6, R0)'', ''(#2, R1)'', ''(#7, R2)'', ''(#5, R0)''. Punctul de ieșire al traseului este tot ''(2, 0)''. Similar, traseul verde are punctul de intrare ''(3, 0)'' și lista de cărți rotite ''(#6, R0)'', ''(#5, R0)'', ''(#7, R2)'', ''(#3, R2)'', ''(#9, R0)''. Punctul său de ieșire este ''(0, 3)''. === Desfășurarea jocului === Jocul de 1 jucător se desfășoară astfel: Jucătorul va lua din teancul de cărți câte o carte (deci cărțile vin aleator) și o plasează (rotită așa cum dorește) într-un spațiu liber de pe hartă. Condițiile pentru plasarea unei cărți sunt următoarele: * cartea trebuie plasată lângă o margine a hărții sau lângă o altă carte (latură comună); * plasarea cărții nu trebuie să ducă la crearea unui traseu care nu trece decât prin cartea respectivă. Astfel, anumite cărți, cu anumite rotații, nu vor putea fi plasate lângă margine. De exemplu, cartea ''#1'' nu poate fi plasată niciodată lângă margine. Jocul se termină atunci când jucătorul nu poate plasa în spațiul de joc cartea care este la rând, fie pentru că nu mai sunt spații libere pe hartă, fie pentru că plasarea cărții ar crea trasee de lungime 1. == Cerințe de implementare == Pentru rezolvarea completă a temei este necesară implementarea tuturor predicatelor din fișierul ''T3.pl'' din arhiva de pornire. Toate predicatele sunt documentate în detaliu în codul sursă oferit. Sunt date de asemenea câteva **predicate utile** în fișierul sursă **''T3base.pl''.** === Reprezentarea stării jocului === Creați o reprezentare a unei stări a jocului Metro. Starea jocului poate conține orice informații doriți, dar este necesar să conțină cel puțin informații despre cărțile puse în joc. Este de asemenea necesar să se poată obține informații despre traseele existente în starea curentă, fie că ele sunt extrase la momentul interogării sau că sunt reținute în reprezentarea stării. * starea inițială a jocului va fi obținută folosind predicatul ''initial_game_state''. * pentru obținerea informațiilor despre starea jocului trebuie implementate predicatele: * ''get_game_tiles'' -- obține o listă cu câte un triplet pentru fiecare carte plasată în joc, tripletul conținând coordonatele spațiului (ca pereche ''(X, Y)''), identificatorul cărții și identificatorul rotației cu care a fost plasată cartea în spațiul respectiv. __Atenție!__ Rotațiile trebuie să fie doar din cele disponibile, e.g. cartea ''#1'' are doar rotația ''R0''. * ''get_open_paths'' -- obține lista traseelor deschise din starea curentă -- trasee care încep de la un punct de intrare dar nu ajung la un punct de ieșire. * ''get_closed_paths'' -- obține lista traseelor închise din starea curentă -- trasee care încep de la un punct de intrare și ajung la un punct de ieșire. **Reprezentarea traseelor** este la alegerea voastră, dar pentru un traseu trebuie să fie disponibile următoarele predicate: * ''get_path_entry'' -- obține perechea ''(X, Y)'' de coordonate ale punctului de intrare în traseu. Aceste coordonate sunt în mod necesar în afara hărții. Vedeți și predicatul ''entry_point'' din ''T3base''. * ''get_path_tiles'' -- obține lista de cărți prin care trece traseul, fiecare carte fiind reprezentată de o pereche între identificatorul cărții și identificatorul rotației. === Mutările disponibile === O mutare înseamnă plasarea unei cărți, cu o anumită rotație, într-un anumit spațiu de pe hartă. Reprezentarea unei mutări este la alegerea voastră. Pentru accesul la informațiile despre o mutare, dar și pentru **construcția mutărilor**, se vor implementa următoarele predicate: * ''get_move_space'', pentru relația dintre mutare și spațiul de pe hartă în care s-a realizat mutarea (descris ca o pereche ''(X, Y)''). * ''get_move_tile_id'', pentru relația dintre mutare și identificatorul cărții care a fost plasată prin mutare. * ''get_move_rotation_id'', pentru relația dintre mutare și identificatorul rotației cu care a fost plasată cartea. **Atenție!** Cele 3 predicate de mai sus trebuie să funcționeze astfel încât, dacă variabilele ''Space'', ''TID'' și ''RotID'' sunt legate la valori corecte, și variabila ''M'' este neinstanțiată, satisfacerea conjuncției get_move_space(M, Space), get_move_tile_id(M, TID), get_move_rotation_id(M, RotID) să lege variabila ''M'' la o reprezentare corectă a mutării descrise. Predicatul **''available_move''** va fi folosit atât pentru a verifica dacă o mutare dată este disponibilă în starea curentă a jocului, cât și pentru a obține toate mutările valide posibile în starea dată a jocului. **Atenție!** Dacă ''available_move'' este apelat cu al doilea argument neinstanțiat, acesta trebuie să ofere pentru al doilea parametru, ca soluții succesive, câte o legare pentru fiecare mutare disponibilă, fără duplicate. Predicatul ''apply_move'' va fi folosit pentru a obține starea jocului în care se ajunge după aplicarea unei mutări într-o stare dată a jocului. Se va presupune că mutarea dată a fost deja obținută sau verificată folosind ''available_move''. === Desfășurarea jocului === Pentru a putea desfășura un joc integral de un singur jucător, se vor implementa următoarele 2 predicate: * ''pick_move'' -- va alege o mutare dintre mutările disponibile care implică o carte dată. **Pentru bonus** predicatul va alege mutarea conform cu o euristică, în ideea obținerii unui scor cât mai mare (trasee cât mai lungi). * ''play_game'' -- desfășoară un joc complet, pornind de la starea inițială a jocului. Pentru a obține o carte care să fie plasată, se va folosi obligatoriu predicatul ''next_tile(+Time, -TID)'', în apelul căruia primul argument va fi legat la numărul de mutări realizate până la momentul curent (pentru obținerea primei cărți va fi 0, pentru obținerea celei de-a doua va fi 1, etc). * ''next_tile'' poate fi apelat doar pentru momentul de timp la care s-a ajuns; de exemplu, inițial se va putea apela ''next_tile(0, T0)'', apoi pentru următoarea carte din teancul de cărți se va apela ''next_tile(1, T1)'', etc; * pentru ajutor la testare, folosiți predicatele ''tt_reset_stack/0'' pentru a reseta teancul de cărți și ''tt_set_tile_range/1'' pentru a da lista de identificatori de cărți din care ''next_tile'' va întoarce cărți; * ''play_game'' trebuie să reușească întotdeauna; dacă nu se mai poate realiza nicio mișcare, ''play_game'' se va întoarce, obținând starea jocului la care s-a ajuns. == Precizări == * pentru a evita conflictul de nume cu predicatele de testare, nu creați predicate al căror nume începe cu ''tt'' * realizați o implementare elegantă, în care să nu aveți multiple definiții pentru cazuri foarte similare. Utilizați, acolo unde aveți nevoie, predicatele ''between'', ''nth0'' sau ''nth1'', findall. == Resurse == * **Atenție!** Lucrați doar în fișierul ''T3.pl'' * Imediat după descărcarea arhivei, editați fișierul și scrieți-vă pe prima linie numele, prenumele și grupa. * În versiunea trimisă de fișier, nu lăsați variabile de tip singleton (Prolog vă dă warning pentru ele). * Pentru debugging, puteți include trace / notrace și în fișierul de testare, pentru a vă fi mai ușor să porniți trace-ul exact acolo unde este util. Însă când trimiteți nu uitați că * la testare se va folosi fișierul de testare original; * trebuie să eliminați orice element de debugging (trace, debug) din fișierul sursă. * {{:17:teme:metro-start.zip|Arhiva de pornire}} == Referințe == [[http://www.bluering.nl/sieuwert/games/metro/|Descriere și implementare a jocului Metro]] == Changelog == * 6.05 -- Publicare temă. * 9.05 (noaptea) -- Adăugare tester pentru primele 80 de puncte * 12.05 11:00 -- Actualizare tester, pentru primele 100 de puncte * corecția numărului corect de mutări disponibile în testele 41/1 și 41/2. * adăugarea de câteva [[#precizări]]. * adăugarea observațiilor legate de predicatul [[#desfasurarea-jocului1|''play_game'']]. * 15.05 -- Actualizare tester, configurare vmchecker. * 20.05 -- Testele de bonus și în arhiva de pe wiki, cu scuze.