Popescu Mircea-Andrei 333 CC

Avioane v1.0

Proiect Analiza Algoritmilor 2004-2005





Avioane. Cum se joaca ?


Avioane este un joc de strategie care se poate juca intre doua persoane, sau asha cum am facut eu in acest proiect, se poate juca impotriva calculatorului, adica o mica inteligenta artificiala. Fiecare participant la joc detine o tabla de joc, de forma patratica, care este impartita in patratele. La inceput se porneste prin desenarea pe propria tabla de joc a avioanelor, in acest caz eu am ales 3. Structura avionului este foarte simpla, lungime cap-coada=4 patratele, o aripa de 5 patratele si o coada formata din 3 patratele. La desenare, avioanele nu trebuii suprapuse sub nici o forma, si nici nu pot depasi tabla de joc !

Dupa ce ambii participanti la joc au desenat pe tabla de joc cele 3 avioane, jocul propriu-zis poate incepe. Este un joc de tip “turn by turn”, adica dupa ce lovesti iti trece randul, si va lovi adversarul tau. Scopul jocului este de a distruge avioanele inamice. La fiecare lovitura, persoana a carui rand este, transmite adversarului pozitia pe care doreste sa o loveasca, dupa care adversarul transmite inapoi ce fel de lovitura a fost.

Exista trei tipuri de lovituri:

  1. Lovitura care nu atinge nici unul din avioanele inamice, pe care adversarul o transmite ca “lovitura pe langa”, adica in aer.

  2. Lovitura care nimereste unul dintre avioanele inamice, dar nu loveste acel avion in cap, se transmite de catre adversar ca “lovitura ochit”, adica lovit.

  3. Lovitura care nimereste unul dintre avioanele inamice exact in cap, se transmite de catre adversar ca “lovitura cap”, adica in cap.




Modalitatea de a distruge avioanele inamice este de a le lovi in cap. Loviturile in corpul avioanelor inamice, precum si loviturile “pe langa”, au scopul de a ajuta in descoperirea capului avioanelor, si astfel la distrugerea lor.

Jocul se sfarseste cand unul dintre participanti nu mai are nici un avion ramas din cele initiale, toate fiind distruse. Castigatorul este acela care mai ramane cu avioane pe tabla de joc.



Modalitatea de joc Avioane v1.0


La inceput apar pe ecran doua table de joc, impartite in patratele. In Avioane v1.0 se joaca impotriva calculatorului. Se incepe prin plasarea avioanelor pe tabla de joc din stanga, tabla jucatorului. Avioanele se deseneaza prin pozitionarea prin click de mouse pe una din patratele de joc a capului, si apoi inca un click intr-o alta patratica in directia cozii avionului, adica directia cap-coada. Dupa ce au fost pozitionate toate avioanele, jocul propriu-zis poate incepe. La inceput prima lovitura o da jucatorul. Loviturile in tabla de joc a computerului se efectueaza in tabla de joc din partea dreapta. Dupa fiecare lovitura a jucatorului, calculatorul va lovi in tabla de joc, iar nr de avioane ramase pentru fiecare este afisat in partea de sus a fiecarei table de joc. Jocul se incheie cand unul dintre participanti ramane fara avioane. Succes !!!




Structura programului si a functiilor


Jocul este facut in Java, ca un applet. De aceea programul are doua parti, partea grafica, care se ocupa de interfata si partea de algoritm, unde are loc gandirea artificiala.

Class Patratel

obiect tip patratel, fiecare celula a tablei de joc si contine culoarea ei si statusul (0, 1 sau 2) 0=liber, 1=ocupat 2=lovit

Class Avion

obiect tip avion, care contine capul si directia pe care este construit avioanul

Class punct

se foloseste in matricile de lovire, punct are cele doua coordonate x si y si o variabila rezolvat (=1 sau 0)

Class ZonaJoc

reprezinta fiecare tabla de joc, si extinde Canvas, aici sunt toate metodele de desenare

Functia avion_contine_puncte(int xi,int yi,int dir,Punct [] pun,int nic)

testeaza daca avionul situat cu capul in (xi,yi) si pe directia dir, contine punctele din vectorul de puncte pun de dimesiune nic

Functia se_poate_avion_mapom(int xi,int yi,int dir)

Verifica daca in matricea de lovituri in avioanele omului se poate pune un avion cu capul in (xi,yi) pe directia dir

Functia se_poate_avion(int xi,int yi,int dir)

Verifica daca in momentul desenarii alegerea capului (xi,yi) cu directia dir este posibila

Functia desen_avion(int xi,int yi,int dir)

Deseneaza pe tabla de joc un avion cu capul in (xi,yi) pe directia dir

Functia kill_avion(int xi,int yi)

Functia scoate in evidenta intreg avionul care are capul in (xi,yi) de pe matricea omului

Functia int nu_contine_punct(Punct x1,Punct x2,Punct x3)

Se verifica daca punctul x2 este intre x1 si x3

Functia Punct gaura_maxima()

Cauta atunci cand loveste calculatorul gaura de dimensiune maxima si loveste in centrul ei

Functia next_hit(Punct pct)

Functia de tip Greedy care cauta capul avionului in momentul cand acesta a fost lovit

Functia void ai()

Este functia principala a programului care testeaza diferite situatii de joc si apeleaza functii precum next_hit

Functia void avioane_ai()

Este functia care face pozitionarea avioanelor calculatorului

Functia void init()

Functia de initializare a variabilelor de sistem si de afisare a componentelor



Algoritmul de structura a A.I.


Algoritmul are la baza mai multe situatii de joc. Partea principala a sa este formata dintr-un algoritm tip Greedy combinat cu un A*. La prima lovitura se foloseste un random, dar nu pentru toata suprafata a tablei, deoarece in acest moment al jocului nu ne intereseaza direct sa lovim un cap de avion, ci doar sa gasim informatii.

Dupa ce s-a facu prima lovitura intra in actiune o functie care depinzand de cum a fost prima lovitura decide unde va avea loc cea de-a doua lovitura, si tot asha pana se va lovi un avion. Aici are loc adevaratul algoritm, pentru gasirea capului avionului atins.

Metoda Greedy se poate aplica unor probleme de optimizare cu solutie vectoriala, ca alternativa mai eficienta la o cautare exahaustiva (de tip “backtracking”). Complexitatea unui algoritm Greedy este polinomiala. Un algoritm Greedy este un algoritm iterativ (nerecursiv) care determina in fiecare pas k o componenta x[k] a vectorului solutie si nu mai revine ulterior la aceasta alegere.

Numele metrodei (“Greedy”=lacomie) sugereaza modul de lucru: la stabilirea valorii lui x[k] – se alege dintre candidatii posibili pe acela care este optim l pasul k, deci un optim local. In general , aceasta alegere precipitata, grabita si care nu tine seama de valorile ce vor fii stabilite in pasii urmatori pentru x[k+1].......x[n] nu poate garanta solutia optima a problemei. In functie de specifiul problemei, un algoritm Greedy poate conduce la solutia optima sau la o solutie destul de buna, desi suboptimala. Rezultatul unui algoritm Greedy pentru o problema data poate depinde de datele concrete ale problemei.

De exemplu, in problema exprimarii unei sume de bani printr-un numar minim de monede de valori date rezultatul (optim sau suboptim) depinde de valorile monedelor si de valoarea sumei. Algoritmul Greedy foloseste monedele in ordinea descrescatoare a valorilor lor, deci “se repede” la monedele de valoare maxima, care vor fii in numar mai mic pentru aceeasi suma. Fie monedele de 11,5 si1. Pentru suma 12 rezultatul algoritmului Greedy va fi optim (doua monede de valori 11 si 1), dar pentru suma 15, algoritmul Greedy nu va fii optim (5 monede de valori 11,1,1,1,1 in loc de 3 monede de valori 5,5,5).

Simplificand, putem spune ca metoda Greedy conduce la solutia optima pentru problemele care au proprietatea de selectie Greedy si o structura optimala: alegerile optime la fiecare pas conduc la un optim global si solutia optima a problemei initiale contine optime la subprobleme de dimensiuni mai mici. Metoda Greedy se aplica si pentru probleme care nu satisfac aceasta conditie, pentru ca ea produce o solutie buna, destul de apropiata de solutia optima intr-un timp mult mai scurt decat o metoda “backtracking”. In aceste cazuri metoda Greedy este considerata ca o metoda euristica, adica o metoda care “ghiceste” sau intuieste solutia buna fara sa se bazeze pe un algoritm determinist, demonstrabilm sau sa faca o analiza exhaustiva a tuturor solutiilor posibile.

Incercarea de a folosi o schema generala de algoritm Greedy, care apopi sa fie adaptata fiecarei probleme specifice, are avantajul ca pune in evidenta strategia comuna tuturor programelor bazate pe algoritmi greedy, dar si dezavantajul unor programe neoptimizate. De aceea, in literatura programele de tip Greedy apar in forme foarte diferite si exploateaza particularitatile problemei rezolvate pentru un cod sursa minim si un timp de executie. O procedura Greedy generala contine un ciclu principal in care, la fiecare pas, se alege o valoare pentru o componenta a solutie x[k]. Alegerea se face dintr-o lista de candidati, lista care poate fii unica pentru toti pasii, sau se modifica (se genereaza din nou) la fiecare pas. Vom considera o functie “genCand” care genereaza aceasta lista de candidati si care este apelata la fiecare pas, desi uneori poate fi scoasa in afara ciclului (lista se genereaza o singura data). Functia “optim” va selecta candidatul din lista de candidati “cand”.

Lista de candidati este, ca tip abstract de date, o coada cu prioritati, pentru a permite extragerea rapida a candidatului optim (maxim sau minim) dintr-o colectie dinamica, la care se pot adauga noi candidati. Teoretic, cea mai buna implementare a unei cozi cu prioritati este un vector “heap”, dar din motive de simplitate se foloseste deseori un vector ordonat sau neordonat. Un vector ordonat este suficient atunci cand lista initiala de candidati nu se mai modifica prin adaugarea altor candidati.

Selectarea unui candidat ca valoare pentru x[k] antreneaza dupa sine si alte operatii, specifice problemei, care vor fii reunite in functia “include”. Functia “posibil” verifica anumite conditii specifice probl emei in functie de care candidatul optim este acceptat sau nu in solutie. Functia generala “Greedy” presupune ca elementele vectorului solutie se determina in ordinea x[1],x[2],.........x[n], deci exista cazuri in care ordinea determinarii acestor componente este diferita.



//variabile globale

int n; \\lungime vector solutie

int x[NX]; \\vector solutie

//algoritm Greedy general

void greedy(){

int k,opt,m; //m=numar de candidati

int cand[NC]; //lista de candidati

init(); //initializari

for(k=1;k<=n&&!solutie(k-1);k++){

genCand(m,cand); //lista de candidati pentru x[k]

kopt=optim (cand,m); //candidatul optim

if (posibil(x[kopt]))

include(x[kopt]);

}

}

Aceasta functie poate fi folosita ca atare si completata cu functiile dependente de aplicatie: genCand, init, posibil, include, optim, solutie. Eventual, mai intervine o secventa care determina valoarea lui x[k] in functie de candidatul optim selectat.