import java.awt.*;
import java.awt.image.*;
import java.net.*;
import java.applet.*;
import java.util.Vector;
import java.util.Random ;

/* la position du jeu est repré‚senté par un bitmask pour
blanc et noir ! (16 bits)

Il y a 1<<16 -1 positions possibles (2^16 - 1) pour chaque joueur.
L'algorithme de jeu fait jouer le coup qui offre le moins de
possibilités pour l'adversaire de placer des pièces dans l'autre
camp  */

public class LeGrec extends Applet {
    
   int camp_blanc; 
   int camp_noir ; // sud, joueur par défaut

   int cx, cy, cx1, cy1, dim ; // coordonn‚ées du coin de la premièŠre case grandeur case
   int delta, rayon ; // décalage grandeur d'un jeton

   boolean joueur_commence = true ;  // marque qui commence
   boolean en_cours = false ;        // partie en cours
   boolean to_user ;                 // la main est au joueur
   boolean coup_en_cours = false ;   // une première case a été sélectionnée
    
// coup de l'utilisateur
   coup coup_crt = new coup(1,1) ;

// en prévision de choix parmi des coups possibles
   Random rnd = new Random();
 
   Image table1 ; // table 
   Image table2 ;
    
   TextField tf ;

   // initialisation et paint
   public void init() {
	table1  = getImage(getCodeBase(), "images/lg-tabl1.gif");
	table2  = getImage(getCodeBase(), "images/lg-tabl2.gif");

        cx = Integer.valueOf(getParameter("cx")).intValue();
        cy = Integer.valueOf(getParameter("cy")).intValue();
        cx1 = Integer.valueOf(getParameter("cx1")).intValue();
        cy1 = Integer.valueOf(getParameter("cy1")).intValue();
        dim = Integer.valueOf(getParameter("dim")).intValue();
        delta = Integer.valueOf(getParameter("delta")).intValue();
        rayon = Integer.valueOf(getParameter("rayon")).intValue();
  
        initJeu() ;  
 
        setLayout(new BorderLayout());
        Panel cmd = new Panel();
        CheckboxGroup cbg = new CheckboxGroup();
        tf = new TextField("Message",30) ;
        tf.setEditable(false) ;
        add("South",tf);

        cmd.setLayout(new GridLayout(3,1,1,1));
	cmd.add(new Checkbox("Je commence",cbg,true));
	cmd.add(new Checkbox("L'ordinateur commence",cbg,false));
        cmd.add(new Button("Début du jeu"));
        add("East",cmd) ;
   }

   public void paint(Graphics g) {
     if (joueur_commence) { 
        g.drawImage(table1,1,1,this) ;
      } else {
        g.drawImage(table2,1,1,this) ;
        }
      dessin_piece(g) ;  
   }

// dessin des pièces différent selon qui commence
   public void dessin_piece(Graphics g) {
      int li , co , coorx , coory ;
      for(int i = 15; i>=0 ;i--) {
         li = i / 4 ;
         co = i % 4 ;
         if(joueur_commence) {
           coorx = cx+delta+co*dim ;
           coory = cy+delta+(3-li)*dim ;
         } else {
           coorx = cx1+delta+(3-co)*dim ;
           coory = cy1+delta+li*dim ;
         }
         if (caseOccupee(i,camp_noir)) {
            g.fillOval (coorx,coory,rayon,rayon) ;
         } else if (caseOccupee(i,camp_blanc)) {
                g.drawOval(coorx,coory,rayon,rayon) ;
            }
        }
   }

   public void initJeu () {
      camp_noir = 1<<0 | 1<<1 | 1<<2 | 1<<3 | 1<<4 | 1<<5 | 1<< 6 ;
      camp_blanc  = 1<<9 | 1<<10 | 1<<11 | 1<<12 | 1<<13 | 1<<14 | 1<< 15 ;
   }
   
   public boolean action(Event evt, Object arg) {
      en_cours = false;
      if(evt.target instanceof Checkbox) {
         Checkbox chk = (Checkbox)evt.target ;
         if(chk.getLabel() == "Je commence") {
           joueur_commence = true ;
           chk.setState(true);
         } else {
           joueur_commence = false ;
              chk.setState(false);
         } 
         repaint();
      } else {
           debutJeu() ;
           tf.setText("Début du jeu") ;
      }
      return true ;
   }

   public void debutJeu() {
      en_cours = true ;
      coup_en_cours = false ;
      initJeu() ;
      repaint() ;
      if (joueur_commence) {
        to_user = true ;
      } else {
        to_user = false ;
        computerMove() ; 
      }
   }

   boolean caseOccupee(int no, int pos) {
      return ((1<<no) == (pos & (1<<no))) ;
   }

   public void computerMove() {
      to_user = false ;
      tf.setText("Je réfléchis") ;
      coup c = bestMove();
      modifierCoupComputer(c) ;
      tf.setText("J'ai joué") ;
      analyserSituationComputer() ;
      repaint() ;
      to_user = true ;
   }


// Si une partie est en cours et que c'est à l'utilisateur
// de jouer on enregistre deux clics et regarde si
// c'est un coup légal. Si oui, modification de l'état
// du joueur, analyse de l'état et mise à jour du dessin
   public boolean mouseUp(Event evt, int x, int y) {
      int no_case, li, co ;
      if (!en_cours) {
        return false ;
      } else if (!to_user) {
        return false ;
      } else {          
        if (joueur_commence) {
          co = (x-cx)/dim ; 
          li = (y-cy)/dim ;
          no_case = 4*(3-li) + co ;
        } else {
          co = (x-cx1)/dim ; 
          li = (y-cy1)/dim ;      
          no_case = 4*li+ 3-co ;
        }
        tf.setText("case "+no_case); 
        if (no_case >=0 && no_case<16) {
          if (coup_en_cours) {
            coup_crt.arrivee = no_case ;
            coup_en_cours = false ;
            if (verifierCoupUser(coup_crt)) { 
              tf.setText("coup valable");
              modifierCoupUser(coup_crt) ;
              analyserSituationJoueur() ;
              repaint() ;
              if (en_cours) 
                computerMove() ;
            } else {
              tf.setText("coup non valable") ;
            }
          } else {
            coup_crt.depart = no_case ;
            coup_en_cours = true ;
          }
        } else {
            coup_en_cours = false ;          
        }
        return true ;     
      } 
    }
	
   public Vector jouableBlanc(int blanc, int noir) {
      Vector lc = new Vector(5,5) ;
      for (int i = 0 ; i<= 15 ; i++) {
         int imin = i - i%4 ;
         int imax = imin + 3 ;
         int li = i / 4 ;
         int jeu = blanc | noir ;
         if (caseOccupee(i,blanc)) {
           if (imin <= (i-1) && !caseOccupee(i-1,jeu)) {
             lc.addElement(new coup(i,i-1)) ;
           }
           if (imax >= (i+1) && !caseOccupee(i+1,jeu)) {
             lc.addElement(new coup(i,i+1)) ;
           }
           if (imin<= (i-1) && li>0 && !caseOccupee(i-5,jeu)) {
             lc.addElement(new coup(i,i-5)) ;
           }
           if (li>0 && !caseOccupee(i-4,jeu)) {
             lc.addElement(new coup(i,i-4)) ;
           }
           if (imax >= (i+1) && li>0 && !caseOccupee(i-3,jeu)) {
             lc.addElement(new coup(i,i-3)) ;
           }
           if (imin<= (i-2) && !caseOccupee(i-2,jeu) && caseOccupee(i-1,noir)) {
             lc.addElement(new coup(i,i-2)) ;
           }
           if (imax>= (i+2) && !caseOccupee(i+2,jeu) && caseOccupee(i+1,noir)) {
             lc.addElement(new coup(i,i+2)) ;
           }
           if (imin<= (i-2) && li>1 && !caseOccupee(i-10,jeu) && caseOccupee(i-5,noir)) {
             lc.addElement(new coup(i,i-10)) ;
           }
           if (li>1 && !caseOccupee(i-8,jeu) && caseOccupee(i-4,noir)) {
             lc.addElement(new coup(i,i-8)) ;
           }
           if (imax>= (i+2) && li>1 && !caseOccupee(i-6,jeu) && caseOccupee(i-3,noir)) {
             lc.addElement(new coup(i,i-6)) ;
           }
         }
      }
      return lc ;
   } 

   public Vector jouableNoir(int noir, int blanc) {
      Vector lc = new Vector(5,5) ;
      for (int i = 0 ; i<= 15 ; i++) {
         int imin = i - i%4 ;
         int imax = imin + 3 ;
         int li = i / 4 ;
         int jeu = noir | blanc ; 
         if (caseOccupee(i,noir)) {
           if (imin <= (i-1) && !caseOccupee(i-1,jeu)) {
             lc.addElement(new coup(i,i-1)) ;
           }
           if (imax >= (i+1) && !caseOccupee(i+1,jeu)) {
             lc.addElement(new coup(i,i+1)) ;
           }
           if (imin<= (i-1) && li<3 && !caseOccupee(i+3,jeu)) {
             lc.addElement(new coup(i,i+3)) ;
           }
           if (li<3 && !caseOccupee(i+4,jeu)) {
             lc.addElement(new coup(i,i+4)) ;
           }
           if (imax >= (i+1) && li<3 && !caseOccupee(i+5,jeu)) {
             lc.addElement(new coup(i,i+5)) ;
           }
           if (imin<= (i-2) && !caseOccupee(i-2,jeu) && caseOccupee(i-1,blanc)) {
             lc.addElement(new coup(i,i-2)) ;
           }
           if (imax>= (i+2) && !caseOccupee(i+2,jeu) && caseOccupee(i+1,blanc)) {
             lc.addElement(new coup(i,i+2)) ;
           }
           if (imin<= (i-2) && li<2 && !caseOccupee(i+6,jeu) && caseOccupee(i+3,blanc)) {
             lc.addElement(new coup(i,i+6)) ;
           }
           if (li<2 && !caseOccupee(i+8,jeu) && caseOccupee(i+4,blanc)) {
             lc.addElement(new coup(i,i+8)) ;
           }
           if (imax>= (i+2) && li<2 && !caseOccupee(i+10,jeu) && caseOccupee(i+5,blanc)) {
             lc.addElement(new coup(i,i+10)) ;
           }
         }
      }
      return lc ;
   } 

   public void modifierCoupUser(coup c) {
        if(joueur_commence) {
           camp_noir = modifierPosition(c,camp_noir) ;
         } else {
           camp_blanc = modifierPosition(c,camp_blanc);
         }
   }

   public void modifierCoupComputer(coup c) {
        if(!joueur_commence) {
           camp_noir = modifierPosition(c,camp_noir);
         } else {
           camp_blanc = modifierPosition(c,camp_blanc) ;
         }
   }

   public int modifierPosition(coup c, int pos) {
        return (pos | (1 << c.arrivee)) & ~(1<<c.depart) ; 
   }   

   public boolean verifierCoupUser(coup c) {
      Vector l = new Vector() ;
      if (joueur_commence) {
         l = jouableNoir (camp_noir,camp_blanc) ;      
         return c.memberp(l) ; 
      } else {
         l = jouableBlanc(camp_blanc,camp_noir) ;
         return c.memberp(l) ;
      }
   }

   public void analyserSituationComputer () {
      if (camp_blanc < 1<<8) { 
         tf.setText("blanc a gagné") ;
         en_cours = false ;
      }
      if (0 == (camp_noir & ((1<<8)-1)) ) {
         tf.setText("noir a gagné") ;
         en_cours = false ;
      } ;
      if(!joueur_commence) {
         if(jouableBlanc(camp_blanc, camp_noir).isEmpty()) {
           tf.setText("noir a gagné en étouffant blanc"); 
           en_cours = false ;
         }
      } else {
         if(jouableNoir(camp_noir, camp_blanc).isEmpty()) {
           tf.setText("blanc a gagné en étouffant noir"); 
           en_cours = false ;
         }
      }
    }
 
    public void analyserSituationJoueur () {
      if (camp_blanc < 1<<8) { 
         tf.setText("blanc a gagné") ;
         en_cours = false ;
      }
      if (0 == (camp_noir & ((1<<8)-1)) ) {
         tf.setText("noir a gagné") ;
         en_cours = false ;
      } ;
      if(joueur_commence) {
         if(jouableBlanc(camp_blanc, camp_noir).isEmpty()) {
           tf.setText("noir a gagné en étouffant blanc"); 
           en_cours = false ;
         }
      } else {
         if(jouableNoir(camp_noir, camp_blanc).isEmpty()) {
           tf.setText("blanc a gagné en étouffant noir"); 
           en_cours = false ;
         }
      }
    }
   
    public coup bestMove() {
      Vector l ; // = new Vector() ;
      int pos_joueur, pos_computer ;
      if(joueur_commence) {
         l = jouableBlanc(camp_blanc,camp_noir) ;
         pos_joueur = camp_noir ;
         pos_computer = camp_blanc ;
      } else {
         l = jouableNoir(camp_noir,camp_blanc);
         pos_joueur = camp_blanc ;
         pos_computer = camp_noir ;
      } 
      return alphaBeta(l,pos_computer,pos_joueur,7) ;
    }

// le meilleur coup de l'ordinateur est celui qui permet
// le moins de mouvement à son adversaire
    public coup alphaBeta (Vector l, int pos_c, int pos_j, int beta) {
      Vector lmin = new Vector() ;
      Vector dl;
      int min = beta ;
      int newnew_pos ;
      int aux_min ;
      for(int j=0;j<l.size();j++) {
         int new_pos = modifierPosition((coup)l.elementAt(j),pos_c) ;
         if (!joueur_commence) {
           if(7== piecesDansBlanc(new_pos)) { 
             return (coup)l.elementAt(j) ;
           } else {
             dl = jouableBlanc(pos_j,new_pos) ;
             for(int p =0; p<dl.size(); p++) {
                newnew_pos = modifierPosition((coup)dl.elementAt(p),pos_j) ;
                aux_min = evaluationNoir(newnew_pos) ;
                if(aux_min == min) {
                   lmin.addElement((coup)dl.elementAt(p)) ;
                } else if (aux_min<min) {
                   lmin.removeAllElements() ;
                   lmin.addElement((coup)dl.elementAt(p)) ;
                   min = aux_min ;
                }
             }
           }
         } else {
           if(7== piecesDansNoir(new_pos)) {
             return (coup)l.elementAt(j) ;
           } else {
             dl = jouableNoir(new_pos,pos_j) ;
             for(int p=0; p<dl.size(); p++) {
                newnew_pos = modifierPosition((coup)dl.elementAt(p),pos_j) ;
                aux_min = evaluationBlanc(newnew_pos) ;
                if(aux_min == min) {
                   lmin.addElement((coup)dl.elementAt(p)) ;
                } else if (aux_min<min) {
                   lmin.removeAllElements() ;
                   lmin.addElement((coup)dl.elementAt(p)) ;
                   min = aux_min ;
                }
             }           
           }
        }        
      } 
      int index = Math.abs(rnd.nextInt()) % l.size() ;
      return (coup)l.elementAt(index) ;
    }

    public int piecesDansNoir(int pos) {
      int total = 0 ;
      int pos1 = (pos & ((1<<8) - 1)) ;
      while(pos1 > 0) {
        total = total+ (pos1 % 2);
        pos1 = pos1 / 2 ;
      }
      return total ;
    }

    public int piecesDansBlanc(int pos) {
       return (7 - piecesDansNoir(pos)); 
    }

    public int evaluationBlanc(int pos_blanc) {
       return piecesDansNoir(pos_blanc) ;
    }

    public int evaluationNoir(int pos_noir) {
       return piecesDansBlanc(pos_noir) ;
    }

    public String getAppletInfo() {
	return "Le Grec (Cré‚ation: D. Huguenin & Yves Ché‚del \nProgrammation: L.-O. Pochon";
    }

}

class coup {
   int depart, arrivee ;

   coup(int d, int a) {
     depart = d ;
     arrivee = a ;
   }

   public boolean memberp(Vector v) {
      coup c ;
      for (int i=0; i<v.size(); i++) {
      c = (coup)v.elementAt(i) ;
      if ( this.depart == c.depart &&
           this.arrivee == c.arrivee)
         return true ;
      }
      return false ; 
   }
}
   
/*class listeCoup {
   coup  first ;
   listeCoup bf ;

   public listeCoup cons (coup c) {
      listeCoup l = new listeCoup() ;
      l.first = c ;
      l.bf = this ;
      return l ;
   }

   public coup car () {
      return this.first ;
   }

   public listeCoup cdr () {
      return this.bf ;
   }

   public int length () {
      if (this == null) { 
        return 0 ;
      } else {
        return 1+ this.bf.length() ;
      }
   }

   public boolean memberp (coup c) {
      if (this == null) {
        return false ;
      }
      if(c.equal(this.first)) {
        return true ;
      } else {
        return (this.bf).memberp(c) ;
      }
   }
} */