Analiza Algoritmilor

Proiect

Jocul cu pătrate

 

Student: Richea Irina

Grupa: 331CA

E-mail : irinuca@k.ro

1.      Descrierea jocului

2.      Prezentare grafica

3.      Algoritmul jocului

4.      Jocul

5.      Surse

6.      Bibliografie

 

1. Descrierea jocului:

        

Jocul este foarte răspândit si este de asemenea cunoscut sub numele “Biscuitul” sau ‘Unește punctele” (“Connect-the-dots”).

Se joaca pe o suprafața poligonala , a cărei dimensiune si forma poate fi variata. Eu am considerat o suprafața dreptunghiulara ale cărei dimensiuni se pot seta de către utilizator. La joc participa 2 jucători.

Reguli: cei 2 jucători trasează, pe rând, cate o latura a patratelelor interioare ( aceste laturi sunt desenate inițial cu gri) . Laturile care construiesc conturul suprafertei de joc se considera deja trasate la începutul jocului.

In momentul in care un jucător trasează o linie cu care închide un patratel, acest patratel devine al lui. Jucătorul respectiv castiga dreptul de a mai trasa o linie. El nu poate sa renunțe la acest drept.

După ce s-a terminat tabla ( au fost trasate toate liniile interioare), se declara castigator jucătorul care are mai multe pătrate in posesia lui.

  

2. Prezentare grafica:

         Jocul oferă posibilitatea de a alege dimensiunea tablei si de asemenea de a opta pentru a fi primul sau al doilea la mutare.

Pe tabla liniile trasate deja sunt colorate n negru, iar cele netrașate, in cyan. Selectarea liniei care se dorește trasata (mutarea dorita), se face prin click pe linia respectiva. Daca mutarea e permisa (linia nu e deja trasata), cursorul se schimba indicând faptul ca linia poate fi selectata.

In momentul in care un pătrat se completează si intra in posesia unuia dintre jucători, el se colorează in culoarea acelui jucător (albastru pentru primul jucător, roșu pentru al doilea).

Când s-a terminat jocul, apare o fereastra care anunța castigatorul.

 

3. Algoritmul jocului:

Algoritmul costa in alegerea mutării pe care calculatorul trebuie sa o facă la un moment dat in anumite condiții, adică alegerea linia care trebuie trasata. Pentru acest lucru, am clasificat liniile care au rămas netrașate la un moment dat, in 3 categorii.

Prima categorie o reprezintă liniile care completează un patratel. Acestea reprezintă liniile avantajoase. Daca exista astfel de linii la o mutare, ele trebuie mutate, ele sunt cele alese (pana sunt epuizate, deoarece fiecare oferă posibilitatea de a mai muta o data).

A doua categorie sunt liniile dezavantajoase, care lasă un patratel cu o singura linie netrașata, oferind adversarului posibilitatea de a-l castiga si de a continua. Calculatorul alege o astfel de linie decât atunci când nu mai are alta soluție. Aceste linii, le-am reținut intr-o coada de prioritati (realizata folosind heapsort), fiecare având drept cheie, număr de pătrate pe care îl poate completa adversarul dc se alege aceasta linie. Astfel, dc e necesar sa se aleagă o astfel de linie, va fi aleasa cea cu cheia cea mai mica (cea mai puțin dezavantajoasa).

A treia categorie sunt liniile care nu constituie decât prima sau a doua linie pentru patratelele adiacente. Acestea sunt linii neutre, din cadrul cărora calc va selecta mutarea, după ce s-a epuizat prima categorie. Pentru suprafețe de joc cu număr mic de pătratele se poate face o selecție intre liniile din aceasta categorie, dar când numărul de pătratele creste teoria matematica a jocului, devine foarte complicata, bazata pe probabilitati. Factorul ”întâmplare” are un rol important si o mutare care poate fi buna pe o suprafața mica a jocului la un moment dat, se poate dovedi dezavantajoasa mai târziu pe o suprafața mai mare de joc. De aceea, nu am făcut o diferențiere intre aceste linii, calculatorul selectând la întâmplare una din ele pentru a o trasa la un moment dat.

Mulțimile care rețin aceste categorii de linii, trebuie actualizate după fiecare mutare. Linia care este mutata, se scoate definitiv din aceste mulțimi, iar celelalte linii ale pătratelor adiacente ei s-ar putea sa necesite sa fie mutate dintr-o mulțime in alta. Trebuie verificat de asemenea căror linii din categoria a 2-a li se schimba prioritatile, trebuie recalculate aceste prioritati si modificate in interiorul mutimii.

      Am prezentat mai jos funcțiile mai importante din cadrul algoritmului:

o        funcția care efectuează mutarea returneaza true dc jucătorul mai are dreptul la o mutare:

§       activează linia la fiecare dintre cele 2 pătrate adiacente

§       le modifica pe amândouă;

o        funcția care modifica un pătrat:

§       dc are 4 linii, el este trecut in posesia jucătorului;

§       dc are 3 linii, linia libera este introdusa in prima categorie si scoasa din a doua, dc nu făcea deja parte din prima

§       dc are 2 linii, liniile libere trebuie introduse in categoria a doua (dc nu fac parte din prima), si trebuie calculata prioritatea (număr de pătrate pe care le cedează adversarului). Asta se face intr-o funcție de modificare a liniei. Daca linia făcea parte din categoria a treia, ea trebuie scoasa din aceasta mulțime;

o        funcția care modifica linia :

§       se parcurg pătratele adiacente atâta timp cat ele au 2 linii si se incrementează numărul de pătrate. Liniile parcurse se rețin intr-o mulțime întrucât vor avea toate aceeași prioritate si vor trebui modificate.

  Întrucât pentru reținere muchiilor din categoria a doua(cele cu prioritati) am folosit o structura de tip coada de prioritati, orice operație de adăugare, modificare sau scoatere a unui element din coada se poate face intr-un timp O(lg n), unde n este numărul de elemente prezent la un moment dat in coada. Numărul de linii din coada nu poate depasi jumătate din numărul de linii existente pe tabla. Aceste operații , cat si operațiile cu celelalte 2 mulțimi (care sunt de tip Vector) sunt determinante in cadrul funcțiilor de alegere a mutării si a celei de mutare. In cadrul funcției mutare se poate ajunge sa se apeleze (de max 2 ori) funcția de modificare a unei linii. Timpul de execuție al acestei funcții depinde de structura tablei la un moment dat ( de număr de pătrate la care se poate ajunge - adică, de fapt, de prioritatea liniei respective ).

 

4. Jocul:

Aici puteți testa jocul. Distracție plăcuta!

 

5. Surse:

Surse

 

6.     Bibliografie:

·         "Jocuri si probleme distractive" - Petre Constantinescu

·         "Introducere in algoritmi" - Thomas Cormen, Charles Leisserson, Ronald Rivest