import java.applet.*;import java.awt.*;import java.awt.event.*;

public class Tictactoe2 extends Applet 
implements ActionListener {
               
   Button squares[];
   int squaresRemaining;
   Button resetBtn;
   Button easyBtn;
   Button hardBtn;
   Button expertBtn;
   Button perfectBtn;
   int strategy;
   static final int RANDOM = 0;
   static final int HARD = 1;
   static final int EXPERT = 2;
   static final int PERFECT = 3;
   boolean[] levelsEnabled = new boolean[4];
	static	 final int O = 1;
	static	 final int X = -1;
	int caddyCorner = -1;
	int borderedCorner = -1;
	
		                   
   public void init() {
      
      strategy = RANDOM;
               
      // set layout and size
      Panel controlPanel = new Panel();
      Panel buttonPanel1 = new Panel();
      Panel buttonPanel2 = new Panel();
      Panel buttonPanel3 = new Panel();
      controlPanel.setLayout(new GridLayout(1,5));
      buttonPanel1.setLayout(new GridLayout(1,3));
      buttonPanel2.setLayout(new GridLayout(1,3));
      buttonPanel3.setLayout(new GridLayout(1,3));
      setLayout(new GridLayout(5,1));
      setSize(350,350);
      
      easyBtn = new Button();
      easyBtn.addActionListener(this);
      easyBtn.setFont(new Font("Serif",Font.BOLD,20));
      easyBtn.setLabel("Easy"); 
      
      hardBtn = new Button();
      hardBtn.addActionListener(this);
      hardBtn.setFont(new Font("Serif",Font.PLAIN,10));
      hardBtn.setLabel("Hard"); 
 
      expertBtn = new Button();
      expertBtn.addActionListener(this);
      expertBtn.setFont(new Font("Serif",Font.PLAIN,10));
      expertBtn.setLabel("Expert"); 

      perfectBtn = new Button();
      perfectBtn.addActionListener(this);
      perfectBtn.setFont(new Font("Serif",Font.PLAIN,10));
      perfectBtn.setLabel("Perfect"); 
           
           
		// disable non-random strats at first. they need to be unlocked
		levelsEnabled[RANDOM] = true;
		      hardBtn.setEnabled(false);
		      expertBtn.setEnabled(false);
					perfectBtn.setEnabled(false);
           
      resetBtn = new Button();
      resetBtn.addActionListener(this);
      resetBtn.setFont(new Font("Serif",Font.BOLD,13));
      resetBtn.setLabel("Reset"); 

      
      controlPanel.add(resetBtn);
      controlPanel.add(easyBtn);
      controlPanel.add(hardBtn);
      controlPanel.add(expertBtn);
      controlPanel.add(perfectBtn);
      
      Label myLbl = new Label("A Tic-Tac-Toe Game", Label.CENTER);
      add(myLbl);
      add(controlPanel);
      
      squaresRemaining = 9;

      // add buttons
      squares = new Button[9];
      for ( int i = 0; i < 9; i++ ) {
         squares[i] = new Button();
         squares[i].addActionListener(this);
         squares[i].setFont(new Font("Serif",Font.BOLD,20));
         squares[i].setBackground(Color.gray);
         if (i== 0 || i== 1 || i== 2)
         	buttonPanel1.add(squares[i]);
	if (i== 3 || i== 4 || i== 5)         	
         	buttonPanel2.add(squares[i]);
         if (i== 6 || i== 7 || i== 8)
         	buttonPanel3.add(squares[i]);
      }
      
      add(controlPanel);
      add(buttonPanel1);
      add(buttonPanel2);
      add(buttonPanel3);
               
   } // end init
               
   public void actionPerformed(ActionEvent e) {               
      // main logic is here when user clicks a square
      if (e.getSource() == resetBtn){
      		reset();
      		return;
      	}else if (e.getSource() == easyBtn){
      		setStrat(RANDOM);
      		return;
      	} else if (e.getSource() == hardBtn){
      		setStrat(HARD);
      		return;
      	} else if (e.getSource() == expertBtn){
      		setStrat(EXPERT);
      		return;
      	} else if (e.getSource() == perfectBtn){
      		setStrat(PERFECT);
      		return;
      	}
      	else {

      // traverse each square to see which was clicked
      for ( int i=0; i<9; i++ ) {
         if ( e.getSource() == squares[i] ) {
            // main logic is here when user clicks a square 
               
            // if square is already occupied, do nothing
            if ( squares[i].getLabel().equals("X") || 
                 squares[i].getLabel().equals("O") ) {
               return;
            }
               
            // user takes a square
            squares[i].setLabel("X"); 
            squaresRemaining--;
               
            // detect for win
            String winner = "";
            winner = detectWin();
               
            if ( winner.equals("X") || winner.equals("O")) {
               endGame();
            } else {
               if ( squaresRemaining <= 0 ) {
                  tieGame(); // Tie Game
                  endGame(); // Tie Game
               } else {
                  // computer makes a move
                  computerMove();
                  squaresRemaining--;
                  winner = detectWin();
                  if ( winner.equals("X") || winner.equals("O") 
                       || squaresRemaining <= 0 ) 
                  {
                     endGame(); // if winner or tie
                  } 
               }
            } 
         }
         }
      }

}         

	public String detectWin(){  // returns "X", "O", or "NO WINNER FOUND!"
       		if ( !(squares[1].getLabel().equals("")) && squares[0].getLabel().equals(squares[1].getLabel()) && squares[1].getLabel().equals(squares[2].getLabel()) ) {
               		markWinner(0,1,2);
               		return squares[1].getLabel();  // top row
            	}
       		if (  !(squares[4].getLabel().equals("")) && squares[3].getLabel().equals(squares[4].getLabel()) && squares[4].getLabel().equals(squares[5].getLabel()) ) {
			markWinner(3,4,5);
               		return squares[4].getLabel();  // mid row
            	}
            	if (  !(squares[7].getLabel().equals("")) && squares[6].getLabel().equals(squares[7].getLabel()) && squares[7].getLabel().equals(squares[8].getLabel()) ) {
               		markWinner(6,7,8);               		
               		return squares[7].getLabel();  // bottom row
            	}     
       		if (  !(squares[3].getLabel().equals("")) && squares[0].getLabel().equals(squares[3].getLabel()) && squares[3].getLabel().equals(squares[6].getLabel()) ) {
               		markWinner(0,3,6);
               		return squares[3].getLabel();  // left col
            	}
       		if (  !(squares[4].getLabel().equals("")) && squares[1].getLabel().equals(squares[4].getLabel()) && squares[4].getLabel().equals(squares[7].getLabel()) ) {
			markWinner(1,4,7);
               		return squares[4].getLabel();  // mid col
            	}
            	if (  !(squares[5].getLabel().equals("")) && squares[2].getLabel().equals(squares[5].getLabel()) && squares[5].getLabel().equals(squares[8].getLabel()) ) {
               		markWinner(2,5,8);   
               		return squares[5].getLabel();  // right col
            	}                      
       		if (  !(squares[4].getLabel().equals("")) && squares[0].getLabel().equals(squares[4].getLabel()) && squares[4].getLabel().equals(squares[8].getLabel()) ) {
			markWinner(0,4,8);
              		return squares[4].getLabel();  // top left to bot right
            	}
            	if (  !(squares[4].getLabel().equals("")) && squares[2].getLabel().equals(squares[4].getLabel()) && squares[4].getLabel().equals(squares[6].getLabel()) ) {
               		markWinner(2,4,6);               		
               		return squares[4].getLabel();  // top right to bot left
            	}      
            	
            	return "NO WINNER FOUND!";               		
		
	}


	public void markWinner(int a, int b, int c){
	      // mark line red if user (X) wins
      		// mark line blue if computer (O) wins
	      if ( squares[a].getLabel().equals("X") ) {
         	squares[a].setBackground(Color.red);
         	squares[b].setBackground(Color.red);
         	squares[c].setBackground(Color.red); 
         	// if X (the user) wins, enable next level of difficulty
         	// unless already perfect
         	if (strategy == RANDOM){
         		levelsEnabled[strategy+1] = true;
         	} else if (strategy == HARD){
         		levelsEnabled[strategy+1] = true;
         	} else if (strategy == EXPERT){
         		levelsEnabled[strategy+1] = true;
         	}
         		
       } else {
         	squares[a].setBackground(Color.blue);
         	squares[b].setBackground(Color.blue);
         	squares[c].setBackground(Color.blue);
      	}
   }


	public void tieGame(){
		//color black x
		String tempLbl;
		for ( int i=0; i<9; i+=2) {
	      		tempLbl = squares[i].getLabel();
	      		squares[i].setBackground(Color.black);
	      		squares[i].setForeground(Color.red);
	      		squares[i].setLabel(tempLbl);
	      		squares[i].setForeground(Color.black);
	      	}
	}
		
	public void endGame(){
		// disable all squares      
		for ( int i=0; i<9; i++)         
		      squares[i].setEnabled(false);
		      
		//enable strategy buttons
		if (levelsEnabled[RANDOM])
			easyBtn.setEnabled(true);
		if (levelsEnabled[HARD])
			hardBtn.setEnabled(true);
		if (levelsEnabled[EXPERT])
			expertBtn.setEnabled(true);
		if (levelsEnabled[PERFECT])
			perfectBtn.setEnabled(true);

	}
  
  	public void computerMove(){
		if (strategy == RANDOM)
			moveRandom();
		else if (strategy == HARD)
			moveHard();
		else if (strategy == EXPERT)
			moveExpert();		
		else if (strategy == PERFECT)
			movePerfect();		
	}

	public void moveRandom(){
		boolean foundMove = false;
		int pickedSquare;
		while (!foundMove){
			pickedSquare = (int) (Math.random() * 9 );  // 0 to 8         	
			if (squares[pickedSquare].getLabel().equals("")){
				squares[pickedSquare].setLabel("O");
				foundMove = true;
			}
		}
	}


	public void moveHard(){
		boolean foundMove = false;
		 
		foundMove = findMove(O);  // that is, find a win for O
	
		if (!foundMove)
			foundMove = findMove(X); // that is, find a win for X, or block for O
		
		if (!foundMove)
			moveRandom();
	}

	// opposite corner exploit discovered by Brian Ziebart
	public void moveExpert(){
		boolean foundMove = false;
		 
		foundMove = findMove(O);  // that is, find a win for O
	
		if (!foundMove)
			foundMove = findMove(X); // that is, find a win for X, or block for O
		if (!foundMove)
			foundMove = moveCenter();
		if (!foundMove)
			foundMove = moveUnborderedCorner();			
		if (!foundMove)
			foundMove = moveCorner();
		if (!foundMove)
			moveRandom();	
			
	}

	// strategy derived from:
	// http://www.chessandpoker.com/tic_tac_toe_strategy.html
	public void movePerfect(){
		boolean foundMove = false;
		 
		foundMove = findMove(O);  // that is, find a win for O
	
		if (!foundMove)
			foundMove = findMove(X); // that is, find a win for X, or block for O
		if (!foundMove)
			foundMove = moveCenter();
		
		// if we can't win, block, or go center, check these conditions:
		
		// condition 1: if X is on a corner and an edge:
		if (!foundMove)
			if (condition1())
					//move to the oppossite corner 
					foundMove = moveCaddy();

		// condition 2a: if both X's are on edges and border a corner
		if (!foundMove)
			if (condition2a())
					//move to the bordered corner 
					foundMove = moveBorderd();

		// condition 2b: if both X's are on edges and don't border a corner
		if (!foundMove)
			if (condition2b())
					//move to any edge
					foundMove = moveEdge();			

		// condition 3: if both X's are on corners
		if (!foundMove)
			if (condition3())
					//move to any edge
					foundMove = moveEdge();					
		
			
		
		if (!foundMove)
			foundMove = moveUnborderedCorner();
		if (!foundMove)
			foundMove = moveCorner();			
		if (!foundMove)
			moveRandom();	
			
	}

	public boolean moveCenter(){
		if (squares[4].getLabel().equals("")){
			squares[4].setLabel("O");
			return true;
		} else
			return false;
	}

	public boolean moveCorner(){
		if (squares[0].getLabel().equals("")){
			squares[0].setLabel("O");
			return true;
		} else if (squares[2].getLabel().equals("")){
			squares[2].setLabel("O");
			return true;
		} else	if (squares[6].getLabel().equals("")){
			squares[6].setLabel("O");
			return true;
		} else	if (squares[8].getLabel().equals("")){
			squares[8].setLabel("O");
			return true;
		} else
			return false;
	}

	public boolean moveUnborderedCorner(){
			if (squares[1].getLabel().equals("X") && squares[3].getLabel().equals("X")){
				if (squares[2].getLabel().equals("")){
					squares[2].setLabel("O");
					return true;
				}			
				if (squares[6].getLabel().equals("")){
					squares[6].setLabel("O");
					return true;
				}	
				if (squares[8].getLabel().equals("")){
					squares[8].setLabel("O");
					return true;
				}									
			}
			if (squares[1].getLabel().equals("X") && squares[5].getLabel().equals("X")){
				if (squares[0].getLabel().equals("")){
					squares[0].setLabel("O");
					return true;
				}			
				if (squares[6].getLabel().equals("")){
					squares[6].setLabel("O");
					return true;
				}	
				if (squares[8].getLabel().equals("")){
					squares[8].setLabel("O");
					return true;
				}				
			}			
			if (squares[3].getLabel().equals("X") && squares[7].getLabel().equals("X")){
				if (squares[2].getLabel().equals("")){
					squares[2].setLabel("O");
					return true;
				}			
				if (squares[0].getLabel().equals("")){
					squares[0].setLabel("O");
					return true;
				}	
				if (squares[8].getLabel().equals("")){
					squares[8].setLabel("O");
					return true;
				}				
			}	
			if (squares[5].getLabel().equals("X") && squares[7].getLabel().equals("X")){
					if (squares[2].getLabel().equals("")){
					squares[2].setLabel("O");
					return true;
				}			
				if (squares[6].getLabel().equals("")){
					squares[6].setLabel("O");
					return true;
				}	
				if (squares[0].getLabel().equals("")){
					squares[0].setLabel("O");
					return true;
				}	
			} 
				
			return false;
	}

	public boolean moveCaddy(){		
		if (squares[caddyCorner].getLabel().equals("")){
			squares[caddyCorner].setLabel("O");
			return true;
		} else
			return false;
	}
	
	public boolean moveBorderd(){
		if (squares[borderedCorner].getLabel().equals("")){
			squares[borderedCorner].setLabel("O");
			return true;
		} else
			return false;
	}	

	public boolean moveEdge(){
		if (squares[1].getLabel().equals("")){
			squares[1].setLabel("O");
			return true;
		} else if (squares[3].getLabel().equals("")){
			squares[3].setLabel("O");
			return true;
		} else	if (squares[5].getLabel().equals("")){
			squares[5].setLabel("O");
			return true;
		} else	if (squares[7].getLabel().equals("")){
			squares[7].setLabel("O");
			return true;
		} else
			return false;
	}

	// condition 1: if X is on a corner and an edge:
	public boolean condition1(){
		int corners = 0;
		int edges = 0;
		int hits = 0;
		
		for (int i = 0; i <9; i++){
			if(squares[i].getLabel().equals("X")){
				hits++;
				if (i == 0 || i == 2 || i == 6 || i == 8 ){
					corners++;	
					if (i == 0)
						caddyCorner = 8;
					if (i == 2)
						caddyCorner = 6;						
					if (i == 8)
						caddyCorner = 0;
					if (i == 6)
						caddyCorner = 2;												
				}
				if (i == 1 || i == 3 || i == 5 || i == 7 ){
					edges++;	
				}				
			}
		}
		
		// only use strat if x has played twice and on an edge and a corner
		if (corners == 1 && edges == 1 && hits == 2){
			return true;
		} else {
			return false;
		}		
	}

	// condition 2b: if both X's are on edges and don't border a corner
	public boolean condition2b(){
		int edges = 0;
		int hits = 0;
		
		for (int i = 0; i <9; i++){
			if(squares[i].getLabel().equals("X")){
				hits++;
				if (i == 1 || i == 3 || i == 5 || i == 7 ){
					edges++;	
				}				
			}
		}
		
		// only use strat if x has played twice and on 2 edges
		if (edges == 2 && hits == 2){
			// opposite edges
			if ((squares[1].getLabel().equals("X") && squares[7].getLabel().equals("X")) ||
					(squares[3].getLabel().equals("X") && squares[5].getLabel().equals("X")) )
				return true;				
		} 
		return false;
	}


// condition 2a: if both X's are on edges and border a corner
	public boolean condition2a(){
		int edges = 0;
		int hits = 0;
		
		for (int i = 0; i <9; i++){
			if(squares[i].getLabel().equals("X")){
				hits++;
				if (i == 1 || i == 3 || i == 5 || i == 7 ){
					edges++;	
				}				
			}
		}
		
		// only use strat if x has played twice and on 2 edges
		if (edges == 2 && hits == 2){
			// adjacent edges
			if (squares[1].getLabel().equals("X") && squares[3].getLabel().equals("X")){
					borderedCorner = 0;
					return true;				
			}
			if (squares[1].getLabel().equals("X") && squares[5].getLabel().equals("X")){
					borderedCorner = 2;
					return true;				
			}			
			if (squares[3].getLabel().equals("X") && squares[7].getLabel().equals("X")){
					borderedCorner = 6;
					return true;				
			}	
			if (squares[5].getLabel().equals("X") && squares[7].getLabel().equals("X")){
					borderedCorner = 8;
					return true;				
			}	
		}
		
			return false;
	}


	// condition 3: if both X's are on corners
	public boolean condition3(){
		int corners = 0;
		int hits = 0;
		
		for (int i = 0; i <9; i++){
			if(squares[i].getLabel().equals("X")){
				hits++;
				if (i == 0 || i == 2 || i == 6 || i == 8 ){
					corners++;	
				}
			}
		}
		
		// only use strat if x has played twice and on 2 corners
		if (corners == 2 && hits == 2){
			return true;
		} else {
			return false;
		}
		
	}


	public boolean findMove(int team){
		// look for rows with two entires.
		// we will use the summing trick, with
		// x = -1
		// o = 1
		// and empty = 0
		//thus, a sum of 2 indicates win for o
		// and a sum of -2 indicates a win for x
		
		int bits[] = new int[9];
		int target = -999;
		int move = -999;
		boolean foundMove = false;
		
		for (int i = 0; i <9; i++){
			if (squares[i].getLabel().equals("X")){
				bits[i] = -1;
				//squares[i].setLabel("-1");
			} else if (squares[i].getLabel().equals("O")){
				bits[i] = 1;
				//squares[i].setLabel("1");
			}else {
				bits[i] = 0;
				//squares[i].setLabel("0");
			}
		}
		
		// we search based on the param, team.
		if (team == X)
			target = -2;
		if (team == O)			
			target = 2;
			
		if (bits[0] + bits [1] + bits[2] == target) {
			if (bits[0] == 0)
				move = 0;
			if (bits[1] == 0)
				move = 1;
			if (bits[2] == 0)
				move = 2;							
			foundMove = true;
		} else 	if (bits[3] + bits [4] + bits[5] == target) {
			if (bits[3] == 0)
				move = 3;
			if (bits[4] == 0)
				move = 4;
			if (bits[5] == 0)
				move = 5;							
			foundMove = true;
		} else 	if (bits[6] + bits [7] + bits[8] == target) {
			if (bits[6] == 0)
				move = 6;
			if (bits[7] == 0)
				move = 7;
			if (bits[8] == 0)
				move = 8;							
			foundMove = true;
		} else 	if (bits[0] + bits [3] + bits[6] == target) {
			if (bits[0] == 0)
				move = 0;
			if (bits[3] == 0)
				move = 3;
			if (bits[6] == 0)
				move = 6;							
			foundMove = true;
		} else 	if (bits[1] + bits [4] + bits[7] == target) {
			if (bits[1] == 0)
				move = 1;
			if (bits[4] == 0)
				move = 4;
			if (bits[7] == 0)
				move = 7;							
			foundMove = true;
		} else 	if (bits[2] + bits [5] + bits[8] == target) {
			if (bits[2] == 0)
				move = 2;
			if (bits[5] == 0)
				move = 5;
			if (bits[8] == 0)
				move = 8;							
			foundMove = true;
		} else 	if (bits[0] + bits [4] + bits[8] == target) {
			if (bits[0] == 0)
				move = 0;
			if (bits[4] == 0)
				move = 4;
			if (bits[8] == 0)
				move = 8;							
			foundMove = true;
		} else 	if (bits[2] + bits [4] + bits[6] == target) {
			if (bits[2] == 0)
				move = 2;
			if (bits[4] == 0)
				move = 4;
			if (bits[6] == 0)
				move = 6;							
			foundMove = true;
		}															
		
		if (foundMove){	
			squares[move].setLabel("O");
			return true;
		} else
			return false;
	}


	public void setStrat(int strat){
		strategy = strat;
		if (strategy == HARD){
      			hardBtn.setFont(new Font("Serif",Font.BOLD,20));
      			hardBtn.setLabel("Hard"); 			
      			easyBtn.setFont(new Font("Serif",Font.PLAIN,10));
      			easyBtn.setLabel("Easy"); 		
      			expertBtn.setFont(new Font("Serif",Font.PLAIN,10));
      			expertBtn.setLabel("Expert"); 
      			perfectBtn.setFont(new Font("Serif",Font.PLAIN,10));
      			perfectBtn.setLabel("Perfect");       			
		} else if (strategy == RANDOM){
      			easyBtn.setFont(new Font("Serif",Font.BOLD,20));
      			easyBtn.setLabel("Easy"); 			
      			hardBtn.setFont(new Font("Serif",Font.PLAIN,10));
      			hardBtn.setLabel("Hard"); 				
      			expertBtn.setFont(new Font("Serif",Font.PLAIN,10));
      			expertBtn.setLabel("Expert");       	
      			perfectBtn.setFont(new Font("Serif",Font.PLAIN,10));
      			perfectBtn.setLabel("Perfect");       			      			
		}  else if (strategy == EXPERT){
			expertBtn.setFont(new Font("Serif",Font.BOLD,20));
      			expertBtn.setLabel("Expert");       	
      			easyBtn.setFont(new Font("Serif",Font.PLAIN,10));
      			easyBtn.setLabel("Easy"); 			
      			hardBtn.setFont(new Font("Serif",Font.PLAIN,10));
      			hardBtn.setLabel("Hard"); 				
      			perfectBtn.setFont(new Font("Serif",Font.PLAIN,10));
      			perfectBtn.setLabel("Perfect");       			      			
		}  else if (strategy == PERFECT){
						expertBtn.setFont(new Font("Serif",Font.PLAIN,10));
      			expertBtn.setLabel("Expert");       	
      			easyBtn.setFont(new Font("Serif",Font.PLAIN,10));
      			easyBtn.setLabel("Easy"); 			
      			hardBtn.setFont(new Font("Serif",Font.PLAIN,10));
      			hardBtn.setLabel("Hard"); 				
      			perfectBtn.setFont(new Font("Serif",Font.BOLD,20));
      			perfectBtn.setLabel("Perfect");       			      			
		}
	}

	public void reset(){
      		squaresRemaining = 9;

      		// reset buttons
      		for ( int i = 0; i < 9; i++ ) {
      			squares[i].setBackground(Color.gray);
         		squares[i].setFont(new Font("Serif",Font.BOLD,20));
         		squares[i].setLabel("");
         		squares[i].setEnabled(true);
      		}
      		// disable difficulty buttons
      		easyBtn.setEnabled(false);
      		hardBtn.setEnabled(false);
		      expertBtn.setEnabled(false);
					perfectBtn.setEnabled(false);
	
	}

}