QUATTRO

FOGARASI MONICA - 332CB

Cuprins

Regulile jocului
Appletul JAVA
Sursa
Detalii despre algoritm
Alte observatii

Regulile jocului

Quattro este un joc care se disputa intre doi jucatori, pe o tabla dreptunghiulara, avand in general 6 linii si 8 coloane. Fiecare dintre jucatori poseda piese de o anumita culoare. Scopul jocului este acela de a realiza o "formatie" de patru piese, pe verticala, orizontala sau diagonala. Desfasurarea jocului: Cei doi jucatori efectueaza pe rand "mutari". O mutare consta in plasarea unei piese proprii in una dintre coloanele tablei de joc, pe cea mai joasa pozitie posibila. In cazul in care toata tabla este ocupata, se considera ca jocul s-a terminat egal.

Appletul Java

Sursa

<!--  
import java.awt.*;
import java.awt.event.*;
import java.applet.*;

public class Quattro extends Applet 

{   Table  joc = new Table();
  
    public Quattro()
    {   add(joc);
    }

    public static void main(String[] args)
    {   WindowListener l = new WindowAdapter()
        {   public void windowClosing(WindowEvent e) 
            {   System.exit(0);}
        };

        Frame f = new Frame("Quattro");
        f.addWindowListener(l); 
        f.add(new Quattro());
        f.setSize(400, 300);
        f.show();
    }

    public String getAppletInfo() 
    {   return "Quattro (Connect4) by Monica Fogarasi - 332CB. January, 2003";
    }
  
    public String[][] getParameterInfo() 
    {   return null;
    }   

}

class Table extends Component

{   public final static int ROWS = 6;
    public final static int COLS = 8;
    public final static int CONN = 4;
  
    private int[] moves = new int [ROWS*COLS];      //Mutarile efectuate
    private int n = 0;                              //Numarul de mutari 
    private int[][] a = new int [ROWS+1][COLS];     //Tabla de joc
    
    public final static int WIN = CONN*ROWS*COLS+1; //un jucator a castigat
    public final static int DRAW = CONN*ROWS*COLS;  //tabla plina => egalitate
  
    public final static int ILOSE = 0;
    public final static int IWIN = 3;
    public final static int IDRAW = 1;          
    
    public int pres = IDRAW;            
  
    private int res=0;                              //Rezultatul partidei
    private int []move = new int[1];
    
    Table ()                                        //CONSTRUCTORUL CLASEI
    
    {   MouseListener getMove = new MouseAdapter()  //Innerclass pt tratarea evenimentelor de mouse
        {   public void mousePressed(MouseEvent e)
            {   removeMouseListener(this);          
                if (res ==WIN || res==DRAW)         //Daca jocul s-a terminat
                {   while (n > 0) undoMove();       //Goleste tabla de joc
                    res = 0;                        //Rezultatul e indecis
                    repaint();                  
                } 
                else                                //Daca jocul continua   
                {   if (addMove(e.getX()/(getSize().width/COLS))) 
                    {   res = win(lastMove());      //Adauga mutarea si vezi daca s-a terminat jocul    
                        repaint();
                    }   
                    if (res !=WIN && res!=DRAW) 
                    {   pres = bestMove(move,CONN);
                        addMove(move[0]);
                        res = win(lastMove());
                        repaint();
                    }
                }
                addMouseListener(this);
            }
        };
        addMouseListener(getMove);                  
    }
  
    boolean addMove (int y)                         //EFECTUAREA UNEI MUTARI O(1)
    
    {   if (0<=y && y<=COLS)                        //Daca y este o coloana valida
            if (a[ROWS][y]<ROWS)                    //Daca nu s-a completat deja coloana y
            {   moves[n++] = y;                     //Adauga y la lista de mutari si incrementeaza nr de mutari 
                a[a[ROWS][y]++][y] = n%2+1;         //Adauga piesei (1 sau 2) pe tabla de joc si incr nr de piese din col 
                return true;                        //Mutarea s-a putut efectua
            }
        return false;                               //Mutarea nu s-a putut efectua  
    }
    
    int undoMove ()                                 //RETRAGEREA ULTIMEI MUTARI O(1)
    
    {   int y = moves[--n];                         //Decrementarea nr de mutari & det coloana pe care s-a facut ultima mutare
        a[--a[ROWS][y]][y] = 0;                     //Decrementarea nr de piese din col & marcarea pe tabla ca "liber" (0)  
        return y;                                   //Intoarce coloana pe care s-a facut mutarea
    }
  
    int lastMove ()                                 //AFLAREA COLOANEI PE CARE S-A EFECTUAT ULTIMA MUTARE O(1)  
    
    {   return moves[n-1];}
  
    int winMove()                                   //DETERMINA DACA EXISTA MUTARE CASTIGATOARE O(COLS)
    
    {   for (int i = 0; i < COLS; i++)
        {   if(addMove(i))
            {   if (win(i) == WIN) {undoMove();return i;}
                undoMove();
            }
        }
        return -1;
    }
        
    public void paint(Graphics g)                   //AFISAREA TABLEI DE JOC O(ROWS*COLS)
    
    {   super.paint(g);
        int cx = getSize().width/COLS,              //Dimensiunea unei celule pe orizontala 
            cy = getSize().height/ROWS;             //Dimensiunea unei celule pe verticala
        int i, j;
        g.setColor(Color.lightGray);                //Fondul
        g.fillRect(0, 0, getSize().width, getSize().height);
        g.setColor(Color.black);                    //Trasarea liniilor
        for (i = 1; i < COLS; i++)
        {   g.drawLine(i*cx, 0, i*cx, getSize().height);}
        for (j = 1; j < ROWS; j++)
        {   g.drawLine(0, j*cy, getSize().width, j*cy);}
        for (i = 0; i < ROWS; i++)                  //Desenarea pieselor
            for (j = 0; j < COLS; j++)     
            {   if (a[i][j]!=0)
                {   if (a[i][j] == 2) g.setColor(Color.red); else g.setColor(Color.blue);
                    g.fillOval(j*cx,(ROWS - i - 1)*cy, cx, cy);
                }
            }
        if (res == WIN)                             //Afisarea rezultatului, daca e cazul
        {   g.setColor(Color.black);
            g.setFont(new Font(g.getFont().getName(),Font.BOLD,cy));
            g.drawString("Winner!!!",2*cx,3*cy);
        }
        if (res == DRAW) 
        {   g.setColor(Color.black);
            g.setFont(new Font(g.getFont().getName(),Font.BOLD,cy));
            g.drawString("Draw!!!",2*cx,3*cy);
        }
        if (pres == IWIN) 
        {   g.setColor(Color.black);
            g.setFont(new Font(g.getFont().getName(),Font.BOLD,cy/2));
            g.drawString("I'm gonna win!!!",1*cx,1*cy);
        }
        if (pres == IDRAW) 
        {   g.setColor(Color.black);
            g.setFont(new Font(g.getFont().getName(),Font.BOLD,cy/2));
            g.drawString("Undecided!!!",1*cx,1*cy);
        }
        if (pres == ILOSE) 
        {   g.setColor(Color.black);
            g.setFont(new Font(g.getFont().getName(),Font.BOLD,cy/2));
            g.drawString("You might win!!!",1*cx,1*cy);
        }
    }
  
    int win (int y)                                 //DETERMINA REZULTATUL, PORNIND DE LA ULTIMA MUTARE O(MAX(ROWS,COLS))
    
    {   int i,j, x = a[ROWS][y]-1, k, k1, k2, sum = 0;
        int player, rival;
        /*  k - numarul de piese de aceeasi culoare alaturate
            k1 - cat de mult se poate extinde (lungimea formatiei)
            k2 - cate piese sunt deja in formatie
        */
        //Egalitate
        if (n==ROWS*COLS+1) return DRAW;
        player = a[x][y]; 
        rival = (player == 1) ? 2 :1; 
        //Vertical
        i = x; j = y; k = 0;
        while (i>=0 && a[i][j] == player) {k++;i--;}
        if (k>=CONN) return WIN;
        k2 = k; k1 = ROWS - a[ROWS][y];
        if (k1+k2 >= CONN) sum+= (CONN+1)*k2+k1;
        //Orizontal
        i = x; j = y; k = -1; k2 = 0; k1 = 0;
        while (j>=0 && a[i][j]==player) {k++;j--;}
        while (j>=0 && a[i][j]!=rival)
        {   if (a[i][j] == player) k2++; else k1++; j--;}
        i = x; j = y;
        while (j<COLS && a[i][j]==player) {k++;j++;}
        while (j<COLS && a[i][j]!=player)
        {   if (a[i][j] == player) k2++; else k1++; j++;}
        if (k>=CONN) return WIN;
        k2 += k;
        if (k1+k2 >= CONN) sum+= (CONN+1)*k2+k1;
        //Diagonal 1
        i = x; j = y; k = -1; k2 = 0; k1 =0;
        while (j>=0 && i<ROWS && a[i][j]==player) {k++;j--;i++;}
        while (j>=0 && i<ROWS && a[i][j]!=rival) 
        {   if (a[i][j] == player) k2++; else k1++; j--; i++;}
        i = x; j = y;
        while (j<COLS && i>=0 && a[i][j]==player) {k++;j++;i--;}
        while (j<COLS && i>=0 && a[i][j]!=rival)
        {   if (a[i][j] == player) k2++; else k1++; j++; i--;}
        if (k>=CONN) return WIN;
        k2+=k;
        if (k1+k2 >= CONN) sum+= (CONN+1)*k2+k1;
        //Diagonal 2
        i = x; j = y; k = -1; k2 = 0; k1 = 0;
        while (j>=0 && i>=0 && a[i][j]==player) {k++;j--;i--;}
        while (j>=0 && i>=0 && a[i][j]!=rival) 
        {   if (a[i][j] == player) k2++; else k1++; j--; i--;}
        i = x; j = y;
        while (j<COLS && i<ROWS && a[i][j]==player) {k++;j++;i++;}
        while (j<COLS && i<ROWS && a[i][j]!=rival)
        {   if (a[i][j] == player) k2++; else k1++; j++; i++;}
        if (k>=CONN) return WIN;
        k2+=k; 
        if (k1+k2 >= CONN) sum+= (CONN+1)*k2+k1;
        return sum;
    }       
  
    public Dimension getPreferredSize()
    {   return new Dimension(200, 150);
    }
   
    int analyze (int [] hisMove, int i, int depth)  
    {   if (depth<0) return IDRAW;
        int res = bestMove (hisMove,depth);
        if (res == ILOSE) return IWIN;
        if (res == IDRAW) return IDRAW;
        return ILOSE;
    }     

    int bestMove(int [] move, int depth)
    {   int result = ILOSE;
        int i, j, val, max = -1;
        int[] hisMove = new int[1];
        depth--;
        move[0] = i = winMove();
        if (i >= 0) return IWIN;
        else 
        {   i = 7;
            while (!addMove(i)) i--;
            move[0] = i;
            hisMove[0] = winMove();
            undoMove();
            if (hisMove[0]>=0)
                if (hisMove[0] < i)
                {   move[0] = hisMove[0];
                    addMove(move[0]);
                    j = analyze(hisMove, i, depth);
                    undoMove();
                    return j;
                }
                else 
                    if (hisMove[0]==i) i--; 
                    else return ILOSE;
            else 
            {   while (i > 0)
                {   if (addMove(i))
                    {   j = analyze(hisMove, i, depth);
                        val = win(i);
                        undoMove();
                        switch (j)
                        {   case IWIN: 
                            {   move[0] = i;                            
                                return(IWIN);
                            }
                            case IDRAW: 
                            {   if (result==ILOSE || (result==IDRAW && val>max))  
                                {   move[0] = i; max = val; result = IDRAW;} 
                                break;
                            }
                            case ILOSE: 
                            {   if (result==ILOSE && val>max) move[0] = i;
                            }   
                        }
                    }
                    i--;
                }
            }
        }
        return result;
    }   
}
-->

Detalii despre algoritm:

Algoritmul se bazeaza pe o rutina de tip backtracking, implementata recursiv, cu limitare a cautarii in adancime.

Functia principala este:

int bestMove(int [] move, int depth)

Functia va intoarce una din varibilele intregi predefinite IWIN, IDRAW, ILOSE, avand semnificatia: cel mai prost rezultat posibil, in cazul in care ambii jucatori aleg cele mai bune mutari. Ideea de functionare a acestei functii este:

daca adancime==0 atunci intoarce IDRAW
result = ILOSE; 
pentru fiecare mutare posibila
    daca castig atunci intoarce IWIN
    altfel
        x = bestMove(adancime - 1) //mutarea adversarului
        daca x == ILOSE atunci x = IWIN
        daca x == IWIN atunci x = ILOSE
        daca result mai slab decat x atunci result = x
intoarce result

Acest algoritm are o complexitate exponentiala, de forma COLS^adancime, unde COLS este o constanta intreaga, reprezentand numarul de coloane, si implicit, numarul de mutari posibile. Evident, se realizeaza optimizari, si anume: (a) se cauta mai intai o eventuala mutare castigatoare (se evita astfel un numar mare de cautari in adancime nejustificate) (b) se "fura" mutarea castigatoare a adversarului, evitandu-se astfel COLS-1 cautari care vor avea ca rezultat ILOSE si (c) se foloseste o functie care "evalueaza" pozitia curenta de pe tabla, facand posibila alegerea unei mutari dintre mai multe care au acelasi rezultat.

Se mai definesc functii pentru: adaugarea unei mutari O(1) si retragerea ultimei mutari efectuate O(1)

O alta functie importanta este:

int win (int y)

Aceasta determina, pornind de la ultima mutare efectuata, daca jocul s-a incheiat (ultima mutare a fost castigatoare sau s-a ajuns la situatia de egalitate - toata tabla este completata) sau nu. In cazul in care jocul nu s-a terminat, intoarce o evaluare a situatiei de pe tabla, din punctul de vedere al jucatorului care a efectuat ultima mutare. Aceasta evaluare depinde de numarul de piese cu care este "legata" piesa curenta si de posibilitatea de dezvoltare a acestei "formatii". Complexitatea acestei functii este egala cu maximul dintre inaltimea si latimea tablei de joc.

Observatii

Pentru retinerea datelor s-au folosit urmatoarele structuri:

public final static int ROWS = 6;               //Numarul de linii
public final static int COLS = 8;               //Numarul de coloane
public final static int CONN = 4;               //Numarul de piese pt. victorie

private int[] moves = new int [ROWS*COLS];      //Mutarile efectuate
private int n = 0;                              //Numarul de mutari 
private int[][] a = new int [ROWS+1][COLS];     //Tabla de joc

Se observa ca jocul se poate modifica usor prin simpla modificare a constantelor COLS, ROWS si CONN. O imbunatatire evidenta ar fi introducerea unei componente in cadrul appletului care sa permita setarea acestor valori, precum si a adancimii de cautare. Pentru cazul general, adancimea s-a considerat egala cu CONN, o adancime de 4 in acest caz facand din calculator un jucator putin peste medie si cu un timp de raspuns bun (adica instant).