Prolog: Metro Board Game

• Responsabil: 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 vmchecker
• Data tester-ului: 15.05.2017
• Forum temă
• changelog

• 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 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 acest link.

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 8×8:

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):

Cartea #1: +0, +0, +0, +0	Cartea #2: +0, +0, +1, +3	Cartea #3: +0, +1, +1, +2
Cartea #4: +0, +2, +0, +2	Cartea #5: +0, +2, +3, +3	Cartea #6: +1, +1, +1, +1
Cartea #7: +1, +2, +2, +3	Cartea #8: +1, +3, +1, +3	Cartea #9: +2, +2, +2, +2
	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ă.

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.

Î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).

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

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.

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.

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.

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.

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.

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

• 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ă.

• Arhiva de pornire

Descriere și implementare a jocului Metro

• 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 ''play_game''.
• 15.05 – Actualizare tester, configurare vmchecker.
• 20.05 – Testele de bonus și în arhiva de pe wiki, cu scuze.