Analiza
Algoritmilor
Proiect
Jocul
cu pătrate
Student: Richea Irina
Grupa: 331CA
E-mail : irinuca@k.ro
4. Jocul
5. Surse
6. Bibliografie
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.
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.
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 ).
Aici puteți testa jocul. Distracție plăcuta!
·
"Jocuri si probleme
distractive" - Petre Constantinescu
·
"Introducere in
algoritmi" - Thomas Cormen, Charles Leisserson, Ronald Rivest