Inteligenta Artificiala

(Deadline: -)

Daca nu sunteti logati exercitiile nu se mai afiseaza.

Tema 2 - jocuri

Barem

Rezolvati problema urmatoare folosind algoritmii:

Toate cerintele se rezolva intr-un singur fisier python.


Barem (punctajul e dat in procentaje din punctajul maxim al temei; procentajul maxim este 100%):

Tema nu se puncteaza fara prezentare. Se va da o nota pe prezentare de la 1 la 10 in functie de cat de bine a stiut studentul sa explice ce a facut. Punctajul temei se va inmulti cu nota_prezentare/10. Astfel, daca cineva stie sa explice doar jumatate din ce a facut, primeste jumatate din punctaj; daca nu stie nimic primeste 0.

Temele copiate duc la anularea notei atat pentru cel care a dat tema cat si pentru cel care a copiat, iar numele studentilor cu aceasta problema vor fi comunicate profesorului titular de curs.




Reversi

Se va implementa jocul reversi. Conform wikipedia (linkul anterior), regulile jocului sunt urmatoarele:

Exemplu de afisare a gridului (puteti alege un alt mod de afisare atat timp cat se poate intelege usor configuratia tablei din afisare). Simbolul # este folosit pentru locatii libere, a si n pentru piesele albe si negre

   a b c d e f g h
   ---------------
0 |# # # # # # # #
1 |# # # # # # # #
2 |# # # # # # # #
3 |# # # a n # # #
4 |# # # n a # # #
5 |# # # # # # # #
6 |# # # # # # # #
7 |# # # # # # # #

Utilizatorul ar raspunde cu un numar de la 0 la 7 si o litera de la a la h (linia si coloana) pentru fiecare mutare.

Lamuriri/ raspunsuri la intrebarile studentilor

Aveti si un exemplu de reversi online.




Omu' cu bombe

Descrierea jocului

Se va implementa un joc asemanator cu Atomic Bomberman dar mult simplificat.

Se porneste de la harta de mai jos (desi puteti pe langa aceasta harta sa va faceti propriile voastre harti):

######################
#1    #       #      #             
# #   ###   #### #####              
# #                  #             
#    p #  p  #  ### ##             
##########           #             
# #     #   ####    ##             
#             p      #             
# #######   #######  #             
#    #  #   #p       #             
# ####  #   ### ###  #             
#    #    #         2#            
######################

simbolurile de pe harta

Jucatorii sunt notati cu 1 si 2. Jucatorul este intrebat daca doreste sa joace cu 1 sau cu 2.

Fiecare jucator se poate deplasa doar in spatiile libere marcate cu spatiu sau intr-un loc in care se afla o "protectie", locul fiind marcat cu "p". Astfel, obstacolele (locatii in care jucatorul nu poate intra) sunt zidurile, marcate cu "#" si bombele, marcate cu "b".

Desfasurarea jocului

Jocul este turn based. Fiecare jucator la randul sau este obligat sa faca o deplasare si optional o plasare de bomba.

Fiecare jucator se poate deplasa doar in directiile sus, jos, stanga,dreapta si numai daca nu exista un obstacol (zid sau bomba) in sensul deplasarii. Protectiile sunt luate automat de jucatori cand acestia ajung intr-o locatie cu protectie. Dupa ce un jucator a lut protectia, rezista la strict o explozie de bomba. Jucatorul poate aduna mai multe protectii de pe harta (deci poate avea un numar np>1 de protectii).

In momentul deplasarii un jucator poate plasa si o bomba care va ramane in urma lui (adica in pozitia in care era inainte de deplasare). Bomba este inactiva pana o activeaza jucatorul. Jucatorul nu poate plasa inca o bomba daca are deja o bomba inactiva.

Bonus. Daca jocul pare un pic plictisitor - de exemplu, ambii jucatori refuza sa puna bombe (de exemplu pe cazul calculator vs calculator), puteti considera ca la fiecare k mutari in care nu a pus bomba, jucatorul sa fie obligat sa puna o bomba (pur si simplu lasa bomba in urma lui). Ca sa reseteze contorul de mutari, poate pune el o bomba, pana ajunge la k mutari fara bomba.

Jucatorul pierde jocul daca moare

Detaliile unei mutari

Cand vine randul jucatorului, va fi intrebat:

  1. directia in care vrea sa se mute (sus/jos/stanga/dreapta) - incercati sa ii cereti un singur caracter, de exemplu: w,a,s,d.
  2. Actiuni posibile (numai atunci cand e cazul): activare bomba(daca exista), plasare bomba(daca e vreo bomba inactiva de-a jucatorului, se activeaza automat), nimic. Incercati si aici sa faceti optiuni doar de un caracter.

O bomba activa se declanseaza cand un jucator trece prin dreptul ei (pe linie sau pe coloana fara sa existe obstacole intre ea si jucator). Explozia se intinde pe toata linia si coloana pe care se afla bomba.

O protectie inseamna ca il protejeaza pe jucator de o explozie.




Hares and hounds

Se va implementa jocul hare and hounds (trad: iepure si catelusi). Conform wikipedia (linkul anterior), regulile jocului sunt urmatoarele:

Exemplu de afisare partiala a jocului (puteti alege un alt mod de afisare atat timp cat se poate intelege usor configuratia tablei din afisare):

...[eventual alte afisari si inputuri date de utilizator]...
Vrei sa fii catelus sau iepure? (raspunde c sau i)
c
Unde vrei sa faci mutarea (alege un nr)?
  1-4-7  
 /|\|/|\
0-2-5-8-10
 \|/|\|/
  3-6-9

Starea curenta:
  c-*-*  
 /|\|/|\
c-*-*-*-i
 \|/|\|/
  c-*-*  
Pozitie catel de mutat:

Utilizatorul ar raspunde cu un numar de la 1 la 10. La fiecare mutare se reafiseaza tabla de joc. De fiecare data cand e intrebat utiliatorul unde o sa mute se reafiseaza configuratia cu numerele ca sa nu fie nevoit sa se uite mereu la inceput.

Observatie: puteti nota nodurile 0 si 10 cu -1 si 11, pentru a gasi o formula mai simpla pentru deplasarea cainilor.




Dame

Se va implementa jocul dame. Conform wikipedia (linkul anterior), regulile jocului sunt urmatoarele:

Exemplu de afisare a gridului (puteti alege un alt mod de afisare atat timp cat se poate intelege usor configuratia tablei din afisare). Simbolul # este folosit pentru locatii libere, a si n pentru piesele albe si negre

   a b c d e f g h
   ---------------
0 |# a # a # a # a
1 |a # a # a # a #
2 |# a # a # a # a
3 |a # a # a # a #
4 |# # # # # # # #
5 |n # n # n # n #
6 |# n # n # n # n
7 |n # n # n # n #

Utilizatorul ar raspunde cu un numar de la 0 la 7 si o litera de la a la h (linia si coloana) pentru fiecare mutare.

Lamuriri/ raspunsuri la intrebarile studentilor




Jocul Obstruction

Se va implementa jocul Obstruction. Conform site-ului dat ca exemplu, regulile jocului sunt urmatoarele:

  • Sunt doi jucatori (x si 0). Jocul foloseste un grid (pot fi n linii si m coloane, nu neaparat 6x6 cum e in exemplul de pe site-ul din bibliografie). Numarul de linii si coloane va fi dat in constructorul jocului (puteti sa le hardcodati sau sa le cititi dintr-un fisier de setari), insa cerinta e ca unul dintre numere sa fie par. Jocul este bazat pe ture.
  • Cand ii vine randul, un jucator poate plasa un simbol doar intr-o zona libera care nu este in imediata vecinatate (pe linie, coloana sau diagonala) a altui simbol de pe grid.
  • Pierde jucatorul care nu mai are mutari posibile (si, evident, castiga adversarul sau).

Mai jos aveti un exemplu de joc. A fost marcata zona ocupata de ultima mutare cu roz, iar zonele ocupate din mutari trecute, cu albastru deschis. In final castiga 0 fiind ultimul care a mai putut plasa un simbol.

mutare obstruction
mutare obstruction
mutare obstruction
mutare obstruction
mutare obstruction
mutare obstruction
mutare obstruction
mutare obstruction
mutare obstruction
mutare obstruction



Jocul Dots & boxes

Se va implementa jocul https://en.wikipedia.org/wiki/Dots_and_Boxes. Conform wikipedia, regulile jocului sunt urmatoarele:

  • Sunt doi jucatori (x si 0). Jocul foloseste un grid de puncte, de n randuri si m coloane. Numarul de randuri si coloane va fi dat in constructorul jocului (puteti sa le hardcodati sau sa le cititi dintr-un fisier de setari). Jocul este bazat pe ture. Gridul initial arata asa (pentru un exemplu de 5 linii si 6 coloane).
    tabla initiala dots
  • Atunci cand e momentul sa actioneze unui jucator, jucatorul uneste doua puncte adiacente cu un segment, orientat pe rand sau pe coloana. Daca segmentul desenat, formeaza impreuna cu alte 3 segmente un patratel (patratelul poate fi doar de latura 1, deci sa nu contina niciun punct pe parcursul laturii, ci sa cuprinda doar punctele din capetele fiecarei laturi). Pe fiecare patratel astfel format se va trece simbolul jucatorului care a adaugat ultimul segment din patratel. De exemplu, in imaginile de mai jos am considerat mutarile lui x marcate cu rosu si mutarile lui 0 marcate cu albastru (mutarea e marcat doar in momentul imediat realizarii ei, deoarece, pentru o linie aflata pe grid nu mai influenteaza mai tarziu cu nimic cine a pus-o.
    mutare dots
    mutare dots
    mutare dots
    mutare dots
    mutare dots
    mutare dots
  • Dintr-o linie se pot cuceri doua patratele in acelasi timp. Asa cum se vede mai jos, jucatorul 0 reuseste sa ia doua patratele dintr-o mutare (pentru ca jucatorul x a binevoit sa faca mutari aiurea de dragul exemplului si chiar jura cu naduf ca nu joaca asa de prost de obicei). Apoi 0 ar mai avea voie sa faca o mutare fiindca a cucerit patratele
    mutare dots
    mutare dots
    mutare dots
    mutare dots
    mutare dots
  • Jocul se termina cand nu se mai pot face mutari. Castiga jucatorul cu mai multe patratele cucerite.



    Jocul Adugo (cainii si jaguarul)

    Se va implementa jocul https://en.wikipedia.org/wiki/Adugo. Conform wikipedia, regulile jocului sunt urmatoarele:

    • Sunt doi jucatori (unul controleaza cainii si celalalt jaguarul). Jocul foloseste o tabla de joc de forma celei din imaginea de mai jos. Jocul este bazat pe ture. Jaguarul are o singura piesa si cainii 14:
      tabla initiala adugo
    • Jaguarul muta primul
    • Cainii si jaguarul se pot deplasa doar pe liniile marcate pe tabla, cate un singur pas (adica se muta dintr-o intersectie de linii in alta intersectie de linii, fara a trece printr-o a treia intersectie de linii). Intersectiile de linii sunt singurele locuri valide pe care se poate gasi o piesa. Iata mai jos un exemplu de mutari succesive:
    • Jaguarul are o mutare in plus: poate captura caini. Pentru asta trebuie sa aiba un caine in imediata vecinatate a lui. Jaguarul poate sari peste caine, capturandu-l, dar asta numai daca:
      • cainele e pe o pozitie vecina cu pozitia jaguarului
      • pe directia cainelui, imediat dupa caine exista un loc valid liber, in care jaguarul va ajunge sarind peste caine
      Mai jos vedeti un exemplu de captura posibila. E marcat prin piesa neagra transparenta locul in care ar putea sari jaguarul.
      captura adugo
    • Se pot captura mai multi caini, in lant, daca conditiile de capturare sunt indeplinite dupa fiecare salt anterior din lant. Un lant de capturi reprezinta o singura mutare din partea jaguarului. Exemplu:
      captura multipla adugo
    • Cainii castiga daca au inconjurat jaguarul (acesta nu mai are mutari posibile). Iata 2 exemple de incoltire mai jos:
      jaguar incoltit
      jaguar incoltit
    • Jaguarul castiga dupa ce a capturat cel putin 5 caini (deoarece, din acel moment cainii nu mai au cum sa inconjoare jaguarul si sa castige).



    Jocul Hex

    Se va implementa jocul https://en.wikipedia.org/wiki/Hex_(board_game). Conform wikipedia, regulile jocului sunt urmatoarele:

    • Sunt doi jucatori (in imagini notati cu rosu si albastru). Jocul foloseste o grila de hexagoane, in forma de romb, cu numar egal de randuri si elemente pe un rand (de obicei e de 11 randuri fiecare de lungime 11). Numarul de randuri si de elemente pe rand va fi dat in constructorul jocului (puteti sa le hardcodati sau sa le cititi dintr-un fisier de setari). Jocul este bazat pe ture. Gridul initial arata asa:
      tabla initiala hex
    • Unul din jucatori va avea alocata directia stanga-dreapta, si celalalt directia sus-jos.
    • Atunci cand e momentul sa actioneze unui jucator, jucatorul plaseaza o piesa pe un spatiu gol de pe tabla de joc (vom ilustra acest lucru in desen, colorand spatiul respectiv cu culoarea jucatorului). In imaginile de mai jos presupunem ca albastru are directia stanga-dreapta si rosu directia sus-jos.
    • Jocul se termina cand unul dintre jucatori a realizat o punte de piese de culoarea lui unind capetele tablei de joc pe directia alocata lui. Exemplu de configuratie castigatoare (sirul castigator de piese e marcat cu contur ingrosat):
      tabla initiala hex
    • Toate cele 4 colturi apartin ambilor jucatori (adica oricare jucator isi poate termina puntea in oricare dintre colturi.

    Observatie: se poate implementa si cu urmatoarea variatie: jucatorii pornesc dintr-un capat al directiei alocate, si nu pot plasa decat piese conectate intre ele (nu se poate pozitiona o piesa pe o anumita pozitie daca nu exista o piesa de aceeasi culoare pe o pozitie vecina).




    Jocul Hap! (Chomp!)

    Pentru cei iubitori de ciocolata...

    Se va implementa jocul http://www.papg.com/show?3AEA cu regulile scrise mai jos. Observatie: Vom discuta o varianta generalizata. Pot fi mai multe patratele otravite. In plus, patratelele "otravite" pot fi oriunde pe grid si jucatorii pot lua o bucata dreptunghiulara orientata oricum (pe linie sau coloana), astfel incat sa nu lase patratele in aer (care sa nu mai fie conectate de bucata initiala, in urma ruperii dreptunghiului).

    Conform site-ului oferit, regulile jocului sunt urmatoarele:

    • Sunt doi jucatori (in imagini notati cu rosu si albastru). Jocul foloseste o grila dreptunghiulara de n randuri si m coloane. Grila reprezinta o bucata de ciocolata (impartita in patratele din care cateva sunt otravite) din care doi jucatori flamanzi rup bucati dreptunghiulare. Numarul de randuri si de coloane va fi dat in constructorul jocului (puteti sa le hardcodati sau sa le cititi dintr-un fisier de setari). Jocul este bazat pe ture. Gridul initial arata asa (in cazul de fata avem doua patratele otravite marcate cu X). :
      tabla initiala chomp
    • La fiecare pas un jucator rupe o bucata dreptunghiulara astfel incat sa nu lase nicio patratica in aer (neconectata), dar nici sa nu ia vreo bucatica otravita. De exemplu, mutarea de mai jos e invalida deoarece raman patratele albe neconectate intre ele (partile din stanga si dreapta bandei rosii):
      mutare ilegala chomp
    • Pierde jucatorul care nu mai poate decupa o bucata dreptunghiulara fara sa desparta placa de ciocolata in doua, ori sa ia o bucatica otravita
    • Aveti mai jos o succesiune de mutari. In final rosu castiga fiind ultimul care a mutat, iar albastru nemaiavand mutari valide fara a lua patratica otravita:



    Jocul Quoridor

    Se va implementa jocul https://en.wikipedia.org/wiki/Quoridor cu regulile scrise mai jos:

    • Vom implementa cazul cu doi jucatori (in imagini notati cu rosu si albastru). Jocul foloseste o grila patratica de dimensiune 9x9. Jocul este bazat pe ture. In cazul a doi jucatori, jucatorii sunt plasati pe laturi opuse ale grilei, avand cate un pion in mijlocul primului rand dinspre latura jucatorului. Gridul initial arata asa:
      tabla initiala quoridor
    • Jucatorii pot realiza o actiune la alegere dintre urmatoarele doua (nu se pot face ambele tipuri de actiuni, la o singura tura):
      • Mutarea unui pion. Pionii pot fi mutati pe rand sau pe coloana, insa nu si pe diagonala, si doar in casute vecine (mutarea va fie doar de un pas). In plus un pion nu poate fi mutat intr-o casuta vecina, daca un perete il separa de acea casuta. Un pion in caz ca e blocat de alt pion, il poate sari (tot doar pe rand si coloana) ajungand in casuta imediat urmatoare de dupa pionul adversar, pe directia de deplasare. Totusi saritura nu paote avea loc daca in calea respectiva exista un perete. De asemenea (pe cazul cu mai multi jucatori), nu se poate sari peste mai mult de un pion. In cazul in care saltul in linie dreapta este blocat, saltul se poate face pe orice alta casuta adicenta pionului peste care dorim sa sarim, asa cum se vede in imaginile de mai jos:
        Saritura peste pionul adversar in linie dreapta se poate face in orice situatie.
        saritura quoridor
        Saritura peste pionul adversar in casutele vecine pionului, in afara de cea in linie dreapta se fac doar in cazul unui obstacol.
        saritura quoridor cu obstacol
      • Plasarea unui perete (peretii sunt marcati cu verde in desene). Peretii sunt de lungime 2 (unde unitatea de masura este egala cu latura unui patratel din grila). Peretii se plaseaza intre celule de asa natura incat sa se intinda exact intre doua perechi de celule (astfel incat zidul sa inceapa si sa se termine la un capat de latura de celula, nu pe parcursul laturii ei). De asemenea, un perete nu poate fi plasat daca taie orice clae ramasa a celuilalt jucator de a ajunge in latura opusa laturii de unde a pornit (deci nu e voie sa fie blocat jucatorul, scopul e sa i se lungeasca drumul cat mai mult). Peretii odata ce sunt plasati, nu mai pot fi mutati.
      • Numarul de pereti este limitat. Pentru 2 jucatori, numarul de pereti disbonibili fiecarui jucator este egal cu 10
    • Castiga jucatorul care a ajuns primul pe latura opusa celei de pe care a pornit.

    Aveti si un exemplu de implementare online




    Jocul Sprouts - oferit ca exemplu, nu se alege

    https://en.wikipedia.org/wiki/Sprouts_(game)

    Insa vom discuta o varianta generalizata. Patratelul "otravit" poate fi oriunde pe grid si jucatorii pot lua o bucata dreptunghiulara orientata oricum (pe linie sau coloana), astfel incat sa nu lase patratele in aer (care sa nu mai fie conectate de bucata initiala, in urma ruperii dreptunghiului).