Proiect Analiza Algoritmilor – Jocul logic  FOTBAL

 

Baltoiu Sergiu-Alexandru 334 CA  thewhitewolf@k.ro     

Cirpian Romanasu 332 CA           ciprian_romanasu@k.ro

 

1. Prezentare joc logic

2. Prezentare program

3. Algoritmul jocului

4. Programul JAVA

5. Testare program

 

1. Prezentare joc logic

 

Acest joc este unul foarte popular, dar contrar numelui sau nu are in comun cu jocul fizic decât o asemănare intre reguli.

 

Cei doi adversari (jocul nu permite decât doi adversari simultan) se înfrunta pe o tabla impartita in pătrate egale (dimensiunile fiind de 10 pe 8). Scopul jocului este de a da gol adversarului, castigand astfel partida. O alta metoda de a castiga (in general posibila numai după un timp mai mare de joc) este prin blocarea adversarului. Acest lucru presupune ca acesta sa nu mai aibă nici o latura libera pe care sa „paseze”.

 

Terenul are in capetele diametral opuse doua porţi, iar jocul va începe de la mijloc. Miscarile acceptate sunt cele pe cele patru direcţii paralele cu axele si pe diagonale:

 

 

Cea mai mare corespondenta cu jocul supranumit „sportul rege” este o caracteristica speciala a mutării: pasa. Daca nodul in care se ajunge cu latura este deja „atins” de o pasa anterioara, jucătorul mai are dreptul la o mutare:

 

 

Se pot face in acest fel un număr de mutări limitat doar de poziţie si de numărul de noduri atinse anterior in joc.

 

O alta caracteristica foarte importanta este faptul ca nu se poate trece peste linii deja făcute. In acest fel se creează situaţii din ce in ce mai dificile cu soluţii tot mai puţin evidente.

       

        Scopul fiecarul jucător este sa dea gol in poarta adversarului si sa isi protejeze propria poarta. Un jucător uman poate opta pentru o multitudine de miscari pentru îndeplinirea acestui scop. Castigarea jocului prin blocare este de obicei foarte greoaie deoarece terenul trebuie sa fie aproape complet ocupat.

 

Titlu ~ Joc logic ~ Interfaţa ~ Algoritm ~ Programul ~ Execuţie

 

 

 

2. Prezentare program

 

Programul odată pornit, afiseaza fereastra principala, in care se pot alege opţiunile principale de configurare.

 

 

 

Opţiunile prezentate sunt următoarele :

·        tipul fiecărui jucător (calculator sau om), in stânga fiind jucătorul numărul 1 (care va juca in stânga) iar in dreapta cel cu numărul 2

·        in cazul selectării jucătorului controlat de calculator, se oferă posibilitatea creşterii importantei hazardului in jocul acestuia (in acest fel se evita repetarea la infinit a aceleiaşi strategii in condiţii identice

·        opţiunea Run reprezintă începutul jocului;

·        Exit este ieşirea din program.

 

La apelarea opţiunii Run se începe jocul propriu-zis, afisandu-se suprafaţa de joc (terenul) si fiecare jucător făcând mutările sale in momentul in care celalalt a terminat. Calculatorul va aştepta ca jucătorul uman sa termine (inclusiv mai multe mutări, daca este cazul) si apoi va muta (respectând aceleaşi reguli).

 

 

Jocul poate fi jucat atât intre 2 jucători umani (moment in care calculatorul doar afiseaza terenul si calculează condiţiile de victorie, nelasand posibilitatea unei trisari) cat si intre calculator si om sau 2 jucători AI. Aceasta ultima posibilitate este interesanta prin faptul ca se pot observa diferentele de strategie in funcţie de nivelul random selectat. Mai puteam introduce si o opţiune legata de strategie generala (defensiva sau ofensiva) dar am preferat sa păstram un nivel optim intre cele 2.

 

Titlu ~ Joc logic ~ Interfaţa ~ Algoritm ~ Programul ~ Execuţie

 

 

3. Prezentare algoritm

 

        Problema prezentata de acest joc este cea găsirii mutării cele mai bune in scopul castigarii partidei. Acest scop poate fi atins fie prin înscrierea unui gol fie prin determinarea adversarului sa se auto-blocheze. Am urmărit ambele variante, profitând de capacitatea programului sa calculeze mult mai rapid si mai complex) desfasurarea jocului. Totuşi, funcţia principala de calcul a drumului urmareste in primul rând sa dea gol si ca sub-scop, sa deseneze cat mai multe muchii pentru a tăia drumul adversarului.

 

        Algoritmul pur este reprezentat de un algoritm Dijkstra modificat in scopul propus. Acest algoritm întoarce arborele de acoperire minim, dar având in vedere ca am definit costul muchiilor intre noduri ca 0, algoritmul va putea folosi o infinitate (in sens teoretic) pentru a găsi o soluţie mai buna.

 

        Trebuie explicat mai întâi de ce am ales acest algoritm: soluţia iniţiala la care ne-am gândit a fost (normal) un backtraking. De altfel am si încercat-o, rezultatele fiind cele la care ne-am aşteptat: deşi programul era mai agresiv (soluţiile erau mai apropiate de cele umane) au apărut si neajunsurile: timp de calcul mult mai mare.

 

        Aceasta a doua încercare oferă pe de o flexibilitate mai mare din punct de vedere a stresului la care este supus calculatorul cat si al modelului de care doream sa ne apropiem: un algoritm rapid si eficient.

 

s[r]=1;

                  for(i=0;i<99;i++)

                       {

                             d[i]=a[r][i];

                             if(i!=r)

                                   if(d[i]<30000)

                                         t[i]=r;

                       }

                  for(i=0;i<98;i++)

                       {

                             min=30000;

                             for(j=0;j<99;j++)

                                   if(s[j]==0)

                                         if(d[j]<min)

                                               {

                                                     min=d[j];

                                                     poz=j;

                                               }

                             s[poz]=1;

                             for(j=0;j<99;j++)

                                   if(s[j]==0)

                                         {

                                               if(d[j]>d[poz]+a[poz][j])

                                                     {

                                                           d[j]=d[poz]+a[poz][j];

                                                           t[j]=poz;

                                                     }

                                         }

                       }

 

Înainte de a începe cu explicarea codului este necesar sa explicam la ce serveşte fiecare componenta a funcţiei:

·        d – vectorul costurilor de la nodul r la celelalte noduri ale grafului; d[i], i=1..99 este distanta la un moment dat intre nodul r si j;

·        t – drumurile găsite intre nodul r si celelate noduri ale grafului (legăturile sunt descrise pas cu pas, ca intr-o lista dintre indice si nodul corespunzător;

·        s – mulţimea nodurilor selectate ( s[i]=0 nodul este neselectat, s[i]=1 – selectat)

 

Algoritmul se comporta astfel:

·        Nodul r este adăugat mulţimii s (care este iniţial vida < s[r]=1 >);

·        Se scriu costurile drumurilor de la r la fiecare nod al grafului in vectorul d de pe linia r a matricii a;

·        Pentru toate nodurile cu cost finit al drumului de r la ele se initializeaza t[i]=r;

·        Se executa de 98 de ori secvenţa următoare:

·  se caută printre nodurile neselectat cel aflat la distanta minima fata de r si se adaugă mulţimii s;

·  pentru fiecare dintre nodurile neselectat se actualizează in d costul drumurilor de la r la el, utilizând ca nod intermediar nodul selectat, astfel: 

·        se compara distanta existenta in vectorul d cu suma dintre distanta existenta in d pentru nodul selectat si distanta de la nodul selectat la nodul pentru care se face actualizarea distantei (preluate din a)

·        daca suma este mai mica, elementul din d corespunzător nodului pentru care se face actualizarea capta ca valoare aceasta suma si elementul din t corespunzător aceluiaşi nod ia valoarea nodului selectat (drumul trece prin acest nod).

·        se actualizează distanta pentru nodul j si se compara d[k]+a[k][j] cu d[j]

·        se calculează apoi drumurile (algoritmul va obţine drumurile de la nodul r la toate nodurile exceptându-l pe el insusi).

 

O parte foarte importanta a algoritmului este (normal) matrice costurilor de la un nod la celalalt. Am ales o soluţie de mijloc in scopul micsorarii volumului de calcule: am considerat ca o matrice de int este mult mai eficienta (in ciuda mărimii sale) decât referentieri continue de la un obiect la celalalt pentru a obţine diferite date (exista sau nu legătura, nodurile sunt atinse, etc ).

 

Iniţializarea acestei matricii (impresionante ca mărime 99x99 – drum de la fiecare nod la fiecare) se face in următoare structura următoare:

 

        for(i=0;i<99;i++)

       for(j=0;j<99;j++)     

        a[i][j]=30000;

 

       int auxJuc=0;

        if(jucator==1)

            auxJuc=-1;

        if(jucator==2)

            auxJuc=1;             

                            

 for(i=0;i<99;i++)

   for(j=0;j<99;j++)   

     if(Math.abs(i%11-j%11)<=1&&Math.abs(i-j)/11<=1&&!mat.laturi.esteLegatura(mat.Matrice[i%11][i/11],mat.Matrice[j%11][j/11])&&i!=j&&Math.abs(i-j)<=12)

             {

         a[i][j]=Math.abs(10*Math.abs(jucator-2)+auxJuc*(Math.max(i,j)%11))+Math.abs(4-(Math.max(i,j)/11))+(int)Math.floor(Math.random()*2);                          if(mat.Matrice[i%11][i/11].esteAtins()&&mat.Matrice[j%11][j/11].esteAtins())

                  {

                     a[i][j]=0;                                                   

                  }                                       

             }   

                 

         for(i=0;i<10;i++)

            {

              a[i][i+1]=a[i+1][i]=30000;

              a[88+i][88+i+1]=a[88+i+1][88+i]=30000;

            }

         for(i=0;i<8;i++)

            {

              a[11*i][11*(i+1)]=a[11*(i+1)][11*i]=30000;

              a[10+11*i][10+11*(i+1)]=a[10+11*(i+1)][10+11*i]=30000;

            }

 

In partea de început se atribuie tuturor laturilor valoarea ce corespunde „muchie existenta”, făcându-se imposibila selectarea acesteia: se elimina astfel muchiile intre nodurile care fizic nu pot avea muchie cat si cele care sunt unite de o muchie anterioara.

 

Se actualizează situaţia, initializandu-se muchiile dintre doua noduri adiacente si libere (nelegate printr-o muchie) cu o valoare variabila in funcţie de distanta de poarta in care se doreşte sa se dea gol. Aceste valori îndruma algoritmul spre poarta adversarului, costul scăzând odată cu apropierea de poarta, atât pe verticala cat si pe orizontala.

 

Se remarca costul dintre doua noduri atinse, iniţializat cu 0. Astfel programul le va considera întotdeauna cea mai buna alternativa ale oricărei alte mutări. Se realizează astfel o influenta a algoritmului către complicarea cat mai mult a figurii si a realizării de cat mai multe mutări pana la a se alege una ce este cat mai buna din punct de vedere al costului.

 

Am introdus si un element de hazard prin adăugarea aleatoare a 0 sau 1 la costurile laturilor, astfel programul va lua alte decizii in aceeaşi situaţie.

 

        Aceasta metode de iniţializare a costurilor face ca algoritmul sa aleagă întotdeauna un drum cat mai departe de propria poarta si cat mai orientat spre cea a adversarului.

 

        Algoritmul Dijkstra este unul de tip Greedy, ceea ce conduce la timpi de execuţie mici si la puţine operaţii necesare. In general algoritmii Greedy nu dau soluţii optime, in schimb acest algoritm particular conduce intr-adevăr la drumul minim. Numărul de operaţii este dat de numărul de comparaţii si atribuiri care se fac in scopul obţinerii drumului minim.

        Formula este următoarea:

                N=99+98*(99*2+99*2)=99+39204=39303

        Aceasta formula este totuşi una artificiala, trebuie ţinut cont de faptul ca multe operaţii sunt eliminate de condiţiile ca drumul sa fie minim (daca se urmareste ca la fiecare pas sa se obtina un drum minim, din 99 de noduri nu raman decât 30 – cazul mediu - ) ceea ce imbunatateste considerabil calculul:

                N=99+98*(2*30+30*2)=11760+99=11859

       

In acelaşi timp, cu cat calculatorul se apropie de poarta aversa, volumul de calcule scade. Este de observat următorul aspect: cu cat terenul este mai complex ocupat, calculatorul are doua avantaje: volumul de calcule scade si felul sau de găsire al soluţiei îl avantajează in fata jucătorului uman. Totuşi, deoarece algoritmul furnizează strict soluţia perfecta din punctul sau de vedere, el nu caută in acelaşi timp si o soluţie care sa pună jucătorul uman intr-o situaţie cat mai proasta. Un algoritm de acest tip (asemănător cu cel MINMAX) s-ar fi putut obţine prin introducerea următoarei inovaţii (după găsirea unor soluţii SI de la nodul iniţial către poarta sa se recalculeze si o soluţie SJ din fiecare punct către poarta adversarului < simulând punctul celuilalt de vedere >, alegându-se soluţia SI de cost minim ii corespunde soluţia SJ de cost maxim).

 

Titlu ~ Joc logic ~ Interfaţa ~ Algoritm ~ Programul ~ Execuţie

 

 

 

4. Programul JAVA

       

Pentru a vizualiza sursa programului, selectaţi aceste link-uri.

 

        Sursa:                       Versiune_13_2.EXE - format ACE Versiune 13.ace Versiune_13.EXE - format ZIP

        Proiectul proiectului:   Proiect.doc

       

Programul a fost realizat cu JCreatorLite (ocazie cu care dorim sa mulţumim companiei Xinox Software pentru amabilitatea de a oferi versiuni gratuite) si compilat cu JAVA SDK 1.4.1. Realizarea sa a urmărit ca produsul final sa poată fi vizualizat cu un browser  HTTP (am verificat corectitudinea afisarii cu Internet Explorer 6.0 si Netscape Navigator 6.0).

 

Titlu ~ Joc logic ~ Interfaţa ~ Algoritm ~ Programul ~ Execuţie

 

 

 

5. Testare program

 

Acest fişier html a fost realizat cu ajutorul Microsoft Word. Am dorit sa subliniez acest lucru pentru a lamuri orice întrebări privind dimensiune impresionanta a codului html rezultat cat si eficienta sa J.

 

 

Titlu ~ Joc logic ~ Interfaţa ~ Algoritm ~ Programul ~ Execuţie