3. Programul Fotbal

Programul a fost scris in Java si programat pentru a fi rulat intr-un browser HTTP care suporta integrarea cu masina virtuala Java (JRE). Este format din 3 clase:

4. Algoritmul Fotbal

In applet-ul fotbal sunt folositi doi algoritmi, implementati in clasa back. Primul algoritm face cautarea posibilitatilor de mutare, iar al doilea algoritm alege dintre posibilitatile generate de primul cea mai buna mutare, cautand maximul unei functii care atribuie fiecarei solutii gasite cate un punctaj.

Algoritmul de generare a mutarilor este un algoritm Backtracking, cu structura urmatoare

   void CautSolutie(int adancime){
        int i,sv;
        teren t1;
        for(i=0;i<=7;i++){ //pentru fiecare directie
            if (posibil(adancime, i)){ //daca directia este posibila
                t1=new teren(intoarcere[adancime-1]); //facem un backup
                sv=t1.status;
                t1.muta(i); //si mutam in directia aleasa
                if(t1.status!=sv){ //daca se schimba starea terenului (i.e. se schimba jucatorul)
                    if(t1.status!=teren.ST_BL1&&t1.status!=teren.ST_BL2){ //daca nu se blocheaza
                         if((adancime > punctajSolutie[t1.mingex][t1.mingey])&&((((int)Math.random()*nivelRandomAdancime)==0)||(punctajSolutie[t1.mingex][t1.mingey])==0)) {
                            if(t1.status == teren.ST_GOL2 && cautare==1) gasitGol=true;
                            if(t1.status == teren.ST_GOL1 && cautare==2) gasitGol=true; 
                            solutii[t1.mingex][t1.mingey]=new teren(t1); //salveaza solutia
                            punctajSolutie[t1.mingex][t1.mingey] = adancime; //precum si punctajul ei
                        }
                    toateSolutiile++; //am mai gasit o solutie
                    }
                }
                else{ //daca nu s-a ajuns intr-o pozitie finala
                    intoarcere[adancime]=new teren(t1);
                     CautSolutie(adancime+1); //se continua cautarea din punctul in care am ajuns
                   }
            }
        }      
    }

Functia nu intoarce toate solutiile posibile, ci pentru fiecare punct de pe teren in care se poate ajunge se pastreaza o singura solutie, solutia cu cel mai bun punctaj. La nivelul cautarii, punctajul inseamna adancimea la care a fost gasita solutia respectiva (adica numarul de linii duse de la pozitia initiala pana la pozitia curenta). Cu cat o mutare este mai lunga, cu atat se ocupa mai mult din teren, iar sansele ca oponentul sa se intoarca pe acelasi drum scad.

Pentru fiecare pozitie in care se ajunge, pentru fiecare directie in care se poate merge, se muta si se evalueaza noua stare a terenului; daca starea nu s-a modificat, inseamna ca s-a mutat intr-un punct folosit si se continua cautarea, adica se apeleaza recursiv functia de cautare pentru noua configuratie. Daca starea terenului s-a modificat inseamna ca este o mutare finala si se evalueaza starea. Daca starea nu este de blocare, se compara punctajul solutiei curente (adancimea la care ne aflam) cu punctajul solutiei precedente din acelasi punct. Daca punctajul este mai mare, atunci solutia noua o inlocuieste pe cea veche. Exista totusi o sansa ca o solutie de adancime mai mare sa nu o inlocuiasca pe alta de adancime mai mica; sansa se poate modifica prin variabila nivelRandomAdancime, probabilitatea fiind 1 la nivelRandomAdancime.

Complexitatea algoritmului de cautare este teoretic 8ⁿ, unde n este adancimea la care se poate ajunge. In program, adancimea este limitata la 15, 8¹⁵=35.184.372.088.832. De fapt, pentru a se putea trece printr-un punct, acesta trebuie sa fi fost deja parcurs, deci trebuie sa existe cel putin doua linii duse deja din acel punct, si mai exista si o a treia linie, cea prin care se ajunge la punct prin mutarea curenta, rezultand doar 5¹⁵=30.517.578.125 posibilitati. In practica lucrurile stau mult mai bine, deoarece adancimea este strict limitata de liniile care au fost duse deja, numarul maxim de posibilitati atins de mine intr-un joc ilogic (cu mutari aleatoare) este de 200.000, iar intr-un joc logic (cu mutari care corespund scopului jocului) numarul de mutari nu creste decat rar peste 50.000, la adancimea 15.

Consumul de memorie este limitat, applet-ul lucrand intr-un spatiu de memorie de 3 MB, din care ocupa cam 1.5-2 MB. Limitarea este facuta prin folosirea unei memorari a terenului care ocupa aproximativ 1000 de biti, adica 125 Bytes, dar care permite accesul rapid la elementele terenului. Pentru fiecare linie de pe teren se pastreaza 2 biti, unul da existenta liniei (true daca este linie dintr-un punct intr-o anumita directie), iar celalalt da culoarea liniei (jucator 1/jucator 2). In algoritmul de cautare, limitarea se face pastrand o singura solutie pentru fiecare punct din teren.

Performanta algoritmului pe un sistem Intel Celeron II 1.3 GHz este de 5000 de solutii pe secunda

Algoritmul de alegere a solutiei optime are complexitate liniara, facand doar o cautare in solutiile date de functia de cautare

    public teren ceaBuna(){
        int i,j,max=0,p;
        teren best=new teren();
        boolean gasit=false; //rezolva bugul resetarii
        for(i=0;i<13;i++){
            for(j=0;j<10;j++){
                if(punctajSolutie[i][j]!=0){
                    p=punctaj(i,j,punctajSolutie[i][j],solutii[i][j]);
                    if(p==max){ //daca au acelasi punctaj, exista 50% sanse ca a doua sa fie aleasa
                         if(Math.random()<0.5f){ best=new teren(solutii[i][j]); gasit=true;}
                    }
                    else if(p>max){
                         best=new teren(solutii[i][j]);
                         gasit=true;
                         max=p;
                    }
                }
            }            
        }
        if(gasit) return best;
        else{
            t.status=teren.ST_BL1; //finalitate
            return t; //bug-ul blocarii este rezolvat
        }
    }

Functia ia fiecare solutie posibila si ii aplica o functie de punctaj. Daca doua solutii au acelasi punctaj, exista sansa de 50% ca solutia noua sa o inlocuiasca pe cea veche. Punctajul poate depinde de pozitia punctului final, lungimea drumului pana in acel punct si configuratia terenului. In aceasta versiune am optat pentru o functie care foloseste numai pozitia punctului final.

    public int punctaj(int x,int y,int adancime,teren t1){
        //x este vertical si y orizontal!
        return sgn(x-6)*x*(Math.abs(y-5)+1)+(12-x)*43 + (int)(Math.random()*nivelRandom) + ((x==6)?-2:0);
    }

Functia atribuie punctelor de pe teren urmatoarele punctaje:

          516  516  516

469  470  471  472  471  470  469

422  424  426  428  426  424  422

375  378  381  384  381  378  375

328  332  336  340  336  332  328

281  286  291  296  291  286  281

280  274  268  262  268  274  280

243  236  229  222  229  236  243

204  196  188  180  188  196  204

165  156  147  138  147  156  165

126  116  106   96  106  116  126

 87   76   65   54   65   76   87

           24   12   24

Se observa ca aceasta formula de punctaj corespunde destul de bine scopului jocului, adica indreapta calculatorul catre poarta adversarului si apara poarta proprie. Cu cat pozitia verticala este mai aproape de poarta adversa, punctajul creste pe pozitia de mijloc orizontala. Calculatorul se va apropia de poarta adversa pe mijlocul terenului. Cu cat pozitia verticala se apropie de poarta calculatorului, punctajul orizontal creste spre marginea terenului, permitand astfel departarea de poarta, adica apararea ei.

Si in functia de punctaj apare un element random, pentru a varia raspunsul calculatorului atunci cand jocul ajunge in aceeasi pozitie.

Deoarece uneori timpul de calcul este mare, nu am putut implementa un algoritm MinMax, deoarece timpul de calcul al fiecarei mutari ar fi crescut de cel putin 6-7 ori. Din pacate, nu am gasit nici o euristica suficient de buna pentru a reduce arborele de cautare fara a pierde uneori solutii importante. Singura optimizare din cautarea solutiilor este descoperirea unui gol din partea calculatorului, moment in care algoritmul de cautare este intrerupt.

5. Rularea Fotbal

Prezenta versiune a fost compilata cu Java SDK 1.4.1_01 si testata cu aceeasi veriune de masina virtuala. Teoretic functioneaza si cu alte versiuni ale JVM.