Vom da mai intai cateva definitii:
Definitia 1. La un anumit pas al jocului numim punct folosit un punct care este capatul unui segment deja trasat.
Definitia 2. La un anumit pas al jocului numim punct blocat un punct care nu mai poate fi unit cu nici un alt punct respectand regulile jocului.
Definitia 3. La un anumit pas al jocului numim punct liber un punct pentru care mai exista cel putin un alt punct cu care poate fi unit respectand regulile jocului.
Definitia 4. La un anumit pas al jocului numim zona o multime de puncte libere astfel incat orice punct din multime nu poate fi unit cu nici un alt punct care nu apartine multimii.
Definitia 5. La un anumit pas al jocului numim jocul asociat unei zone jocul care porneste cu zona respectiva ca multime a punctelor. Acest joc se joaca numai in zona respectiva, tinand seama de constrangerile initiale ale zonei. Numim numar posibil de mutari un numar de mutari dupa care jocul asociat zonei se poate termina. In general, exista mai multe numere posibile de mutari. Multimea acestora o vom numi multime de numere posibile de mutari asociate zonei.
Definitia 6. La un anumit pas al jocului numim grupaj nedecis o zona pentru care multimea de numere posibile de mutari asociate are doua elemente si acestea sunt 1 si 2. Practic, grupajul nedecis este acea zona care poate fi jucata intr-una sau doua mutari.
Mai jos, avem 2 zone de cate 4 puncte fiecare. Prima reprezinta un grupaj nedecis, deoarece unind pe 1 cu 3 jocul s-a terminat intr-o singura mutare, iar unind pe 1 cu 2, mai este posibil sa se uneasca 3 cu 4, deci jocul se termina in 2 mutari.
A doua nu reprezinta un grupaj nedecis, deoarece oricum am uni 2 puncte, mai este posbila inca o mutare, deci jocul se va termina in 2 mutari oricum. Aceasta zona este o zona mica.
Grupajele nedecise au o mare importanta, deoarece jucatorul care ataca grupajul castiga jocul asociat grupajului respectiv. Grupajele nedecise trebuie sa aiba cel putin patru puncte; ne vom axa pe cele de patru sau de cinci puncte, deoarece acestea sunt mai usor de observat.
Definitia 7. La un anumit pas al jocului numim zona mica o zona pentru care multimea de numere posibile de mutari asociate are un singur elemente.
S-a ales aceasta denumire, deoarece zonele ce au doua sau trei puncte evident zone mici. Vom tine cont si de zonele mici formate din 4 sau 5 puncte.
Definitia 8. La un anumit pas al jocului numim numar sigur de mutari suma numerelor posibile de mutari asociate fiecarei zone mici.
Numarul sigur de mutari da in fond numarul minim cunoscut de mutari in care se va termina jocul de la pasul respectiv.
Dam in continuare urmatoarea propozitie:
Propozitia 1. Fie urmatoarea situatie la un anumit pas al jocului: toate zonele sunt grupaje nedecise sau zone mici; notam cu A jucatorul care este de mutat, cu B celalt jucator; notam ned numarul grupajelor nedecise si cu mut numarul sigur de mutari. Atunci:
a) Daca ned este par si mut este par, exista o strategie castigatoare pentru jucatorul B.
b) Pentru celelalte situatii exista o strategie castigatoare pentru jucatorul A.
Demonstratie:
Vom demonstra acest rezultat prin inductie dupa numarul grupajelor nedecise.
Cazuri de baza: Pentru zero grupaje nedecise, jocul este deja hotarat, indiferent de mutarile celor 2 jucatori. In acest caz, exista numai zone mici, deci se cunoaste numarul de mutari in care se va termina jocul (care este egal in acest caz cu numarul sigur de mutari). Daca acest numar este impar, va castiga jucatorul care este de mutat (jucatorul A), invers va castiga jucatorul B.
Pentru un singur grupaj nedecis, jucatorul A va avea o strategie de castig. Intr-adevar, dupa ce A muta (presupunand ca va rezolva grupajul nedecis), revenim in situatia cu zero grupaje nedecise, in care jocul este hotarat. Strategia lui A este sa rezolve grupajul astfel incat cand B vine la mutare, numarul de mutari in care se termina jocul (numarul sigur de mutari) sa fie par. Daca numarul sigur de mutari cand A este de mutat este par, atunci A va rezolva grupajul nedecis printr-o mutare; invers, il va rezolva prin 2 mutari.
Ipoteza de inductie: Aratam ca P(2k) implica P(2k+1) si P(2k+2), adica presupunand propozitia adevarata pentru 2k grupaje nedecise, vom arata ca este adevarata pentru 2k+1 si pentru 2k+2 grupaje nedecise.
Aratam P(2k) -> P(2k+1). Pentru 2k+1 grupaje nedecise, jucatorul A are o strategie castigatoare. Intr-adevar, A va rezolva un grupaj nedecis astfel incat cand B vine la mutare numarul sigur de mutari sa fie par. Cum numarul grupajelor nedecise va fi atunci 2k si P(2k) este adevarata, rezulta ca B va pierde, deci A are o strategie castigatoare.
Aratam ca P(2k+2) este adevarata. Observam mai intai ca jucatorul A nu va rezolva nici un grupaj nedecis (deoarece vor ramane 2k+1 grupaje nedecise, P(2k+1) este adevarata, jucatorul B va fi la mutare si deci B va avea o strategie castigatoare), deci A va uni puncte numai din zonele mici. Daca nu exista zone mici, A pierde, B avand o strategie castigatoare. Presupunem ca exista zone mici. Prin mutarea lui A, numarul sigur de mutari s va micsora cu 1, numarul grupajelor nedecise va ramane neschimbat; deci B va fi fortat si el sa uneasca puncte dintr-o zona nedecisa. Situatia se continua pana cand nu vor mai fi zone mici, jucatorul ce trebuie sa mute in acest moment va fi fortat sa rezolve un grupaj nedecis, deci va pierde (deoarece celalt va fi la mutare intr-o situatie cu 2k+1 grupaje nedecise, deci va castiga). In concluzie, daca numarul sigur de mutari este par, A va fi jucatorul ce este fortat in cele din urma sa rezolve un grupaj nedecis si deci B va avea strategie castigatoare; daca numarul sigur de mutari este impar, B va fi jucatorul ce este fortat in cele din urma sa rezolve un grupaj nedecis si deci A va avea strategie castigatoare.
Propozitia este demonstrata.
Strategia de rezolvare pe care am adoptat-o se bazeaza pe impartirea punctelor in zone cat mai mici astfel incat sa ajungem la o situatie in care zonele sunt grupaje nedecise sau zone mici. Vom testa o zona pentru a stabili daca este zona mica sau grupaj nedecis numai daca zona are 4 sau 5 elemente (daca zona are 2 sau 3 puncte, este sigur zona mica; daca are 4 sau 5 puncte nu poate fi decat zona mica sau grupaj nedecis; daca are mai multe puncte poate sa nu fie nici zona mica, nici grupaj nedecis, iar stabilirea acestui fapt se face greu).
Algoritmul
-> La fiecare pas alegem zona cu cele mai multe de puncte;
-> Daca zona are mai mult de 12 puncte, se imparte zona respectiva. Se uneste printr-un segment doua puncte ce se pot uni din zona respectiva. Am ales segmentul potential cu lungimea cea mai mare;
-> Daca zona are cel mult cinci puncte, atunci vedem ce jucator are o strategie castigatoare, conform propozitiei 1. Daca are calculatorul strategia castigatoare, atunci se face mutarea urmatoare conform acestei strategii; altfel, calculatorul muta la intamplare;
-> Daca zona are cel mult 12 puncte si cel putin 6 puncte, se cauta in zonele de acest fel mutarea care va da strategia castigatoare la pasul urmator pentru configuratia "cunoscuta" (adica zonele mici si grupajele nedecise); daca nu exista, se face o mutare la intamplare in zona maxima;
2. Implementarea
S-au folosit urmatoarele clase:
-Proiect2AA pentru interfata grafica;
-Punct ce implementeaza imaginea unui punct pe ecran;
-JucCalc ce implementeaza practic algoritmul -Mutari ce implementeaza mutarile (facute de calculator sau de utilizator);
La fiecare pas al jocului (fiecare "mutare"), se actualizeaza o situatie a jocului. Aceasta situatie a jocului este reprezentata de urmatoarele:
-multimea zonelor punctelor libere, implementata ca un vector de multimi (HashSet) de obiecte de tip Punct, fiecare multime reprezentand o zona in sensul definitiei date mai sus;
-multimea punctelor folosite, implementata ca o multime (HashSet) de obiecte de tip Punct;
-multimea punctelor blocate, implementata ca o multime (HashSet) de obiecte de tip Punct;
-multimea liniilor existente (trasate), implementata ca un vector de obiecte de tip Line2D.Float;
Avem o functie care stabileste daca doua puncte se pot uni, pur si simplu vazand daca segmentul dat de cele 2 puncte nu intersecteaza vreo linie existenta.
Exista o functie care uneste doua puncte prin segmentul corespunzator si actualizeaza situatia jocului dupa aceasta mutare. Astfel, se introduce noul segment in multimea liniilor trasate, se introduc cele 2 puncte in multimea punctelor folosite. Trebuie apoi actualizat vectorul zonelor punctelor libere. Pentru aceasta, se determina mai intai zona din care fac parte cele 2 puncte (evident, ca sa poata fi unite trebuie sa faca parte din aceeasi zona). Se elimina punctele respective din zona. Prin unirea acestor puncte, probabil ca zona respectiva s-a impartit in mai multe zone; de asemenea, pot sa apara noi puncte blocate. Exista o functie ce intoarce un vector de multimi pentru fosta zona, fiecare multime reprezentand sau o zona (caz in care are cel putin 2 puncte) sau o multime formata dintr-un singur punct (atunci nu este zona, punctul respectiv este un punct blocat). In continuare se parcurge acest vector de multimi, eliminandu-se multimile formate dintr-un singur punct (aceste puncte vor fi adaugate punctelor blocate), apoi se scoate fosta zona din vectorul zonelor si se adauga in acest vector zonele noi formate.
Prezentam acum modul in care se imparte fosta zona in noi zone. Pornim cu un vector de multimi de puncte ce contine initial toate multimile formate dintr-un singur punct. Formam o multime de perechi de puncte ce pot fi unite. Parcurgem aceasta multime si la fiecare pas luam punctele din perechea respectiva, vedem daca fac parte din aceeasi multime de puncte (zona potentiala), daca nu reunim cele 2 multimi corespunzatoare celor 2 puncte.
Strategia calculatorului este implementata in clasa JucCalc. Functia muta este cea prin care se realizeaza mutarea calculatorului. In aceasta functie, se determina mai intai configuratia "cunoscuta" (grupaje nedecise + zone mici), de asemenea zona de marime maxima. In functie de marimea acestei zone, se iau urmatoarele decizii:
-Daca zona are cel putin 13 puncte, ea se imparte in zone mai mici, alegand sa se traseze segmentul cu lungimea cea mai mare din ea.
-Daca zona are cel mult 5 puncte, atunci inseamna ca toate zonele au cel mult cinci puncte, deci avem numai zone mici si grupaje nedecise. In acest caz, daca calculatorul are o strategie castigatoare, se aplica aceasta; iar daca nu, va muta la intamplare.
-Daca zona are cel putin 6 puncte si cel mult 12 puncte (zona mijlocie), atunci incepand cu zona maxima vom cauta in toate zonele mijlocii o mutare care sa aduca configuratia "cunoscuta" (zonele mici si grupajele nedecise) intr-o situatie avantajoasa.
Clasa interioara GrupajNedecis gestioneaza zonele de 4 sau 5 puncte. Ea are printre membrii 2 perechi de puncte ce corespund a doua mutari posibile (o mutare duce la rezolvarea grupajului nedecis in 2 mutari, cealata conduce la rezolvarea grupajului nedecis intr-o singura mutare). O functie gaseste aceste doua perechi (daca nu va gasi una dintre ele, atunci zona nu este grupaj nedecis, ci zona mica).
Clasa interioara ZonaMijlocie trateaza zonele de la 6 la 12 puncte. O functie determina mutarea urmatoare, in functie de numarul sigur de mutari si de numarul grupa de grupaje nedecise dorit (de fapt, conteaza doar paritatea acestor numere) prin simularea unei mutari a calculatorului si analiza situatiei create.
3. Exemplu
Comentam in continuare rezultatele obtinute la un joc.
Muta intai calculatorul. Deoarece sunt mai mult de 13 puncte, va trasa segmentul cel mai mare:
Muta utilizatorul. Exista 2 zone mijlocii: (5,6,1,13,12,14,11) si (4,8,9,16,3,10). Nu exista zone mici si nici grupaje nedecise. Calculatorul va lua zona cea mai mare si va incerca sa faca o mutare astfel incat sa se formeze un numar par de grupaje nedecise si un numar sigur de mutari par (nr par poate fi si 0). Face mutarea (1-13), care formeaza 2 zone mici (5,6) si (11,12,14) (deci numarul sigur de mutari va fi 2) si nici un grupaj nedecis.
Utilizatorul face mutarea (5-6). Numarul sigur de mutari devine 1, avem o zona mijlocie, zero grupaje nedecise. Calculatorul va cauta in zona mijlocie o mutare din care sa rezulte un numar sigur de mutari impar (pentru zona respectiva -pe total trebuie sa fie par) si un nr par de grupaje nedecise. Va face mutarea (4-8), obtinand zona mica (16,3,0). In acest moment, singurele zone sunt zone mici, numarul sigur de mutari este 2, deci utilizatorul pierde (jocul e hotarat):
Urmatoarele mutari nu mai conteaza:
