import java.awt.*;
import java.applet.Applet;
import java.net.*;
import java.util.*;

public class Slide5b extends Applet{
	// Set up the checkboxes that enable the player to move.
	private CheckboxGroup allmoves;	 
	private Checkbox move[];
	// The playing board.
	private TokenCanvas pic[];
	// Some messages appear at the upper left corner, which we also
	// use to lay out the playing board correctly.
	private TokenCanvas corner;

	Board position;			// The current state of the game.
	int turn;				// Whose turn it is
	int winner;				// Whether we have a winner
	int player1, player2;	// Keep score - games won
	
	int state;				// Game state for correct dispatching of events

	public void init(){
		int i,j;
		turn = 1;
		setBackground(Color.lightGray);
		state = 0;
		setLayout(new GridLayout(6,6));
		allmoves = new CheckboxGroup();
		position = new Board();
		pic = new TokenCanvas[25];
		for(i = 0; i< 25; i++){
			pic[i] = new TokenCanvas();
			pic[i].resize(50,50);
			pic[i].token = 0;
		}
		
		corner = new TokenCanvas();
		corner.resize(50,50);
		corner.token = 9;
		corner.setBackground(Color.cyan);
		player1 = 0; player2 = 0;
		add(corner);
		corner.repaint();
		move = new Checkbox[10];
		for(i = 0; i < 10; i++){
			move[i] = new Checkbox();
		}
		move[0].setLabel("1");
		move[1].setLabel("2");
		move[2].setLabel("3");
		move[3].setLabel("4");
		move[4].setLabel("5");
		move[5].setLabel("6");
		move[6].setLabel("7");
		move[7].setLabel("8");
		move[8].setLabel("9");
		move[9].setLabel("10");
		for(i = 0; i < 10; i++){
			move[i].setCheckboxGroup(allmoves);
		}
		for( i = 0; i < 5; i++){
			add(move[i]);
		}
		for( i = 5; i < 10; i++){
			add(move[i]);
			for(j = 0; j < 5; j++){
				add(pic[(i-5)*5 + j]);
			}
		}
		

		
		
	}
	void startNewGame(){
		int i;
		// It will be the human's move when we return.
		corner.token = 9;
		corner.setBackground( Color.cyan );
		// Clear the game board
		position.reset();
		// If the computer is starting, let it pick a random move.
		if(turn == -1){
			Random r = new Random();
			int move = r.nextInt() % 10 + 1;
			position.push(move, turn);
 			 turn = -turn;
 		}
		corner.repaint();
		state = 0;
		repaint();
	}

	public void paint(Graphics g){
		int i;
		for(i = 0; i< 25; i++){
			pic[i].token = position.token[i];
			pic[i].repaint();
		}

	}

	public boolean action(Event e, Object o){
		 String statline = " ";
		 // State is "human to move". Human has picked a move.
		 if(state == 0 && e.target instanceof Checkbox){
			 String s = ((Checkbox)(e.target)).getLabel();
			 statline = "Human's move was " + s;
			 
			 int move = Integer.parseInt(s);
			 position.push(move, turn);
			 winner = position.wins();
			 // If human has won this game, let the corner say so,
			 // keep track of the score, and change the state to
			 // "start a new game".
			 if((turn == 1) && ((winner == 1) || (winner == 3))){
				 corner.token = 10;
				 turn = -turn;
				 player1++;
	 			 if(winner > 0)corner.setBackground(Color.pink);
				 statline = statline + ". Human: " + player1 + ", Computer: " + player2 + ". Click for new game.";
				 corner.repaint();
				 showStatus(statline);
				 state = 1;
			 }
			 // If human's move produced a win for computer, set the corner
			 // to say so, keep score, and set the state to "start new game".
			 else if(turn == 1 && winner > 1){
				 corner.token = 11;
				 player2++;
	 			 if(winner > 0)corner.setBackground(Color.pink);

				 statline = statline + ". Human: " + player1 + ", Computer: " + player2 + ". Click for new game.";
				 corner.repaint();
  				 showStatus(statline);

				 state = 1;
			 }
			 // Otherwise set the state to "computer's move".
			 else {
	 
			 turn = -turn;
 			 corner.setBackground(turn == 1 ? Color.cyan : Color.white);
			 statline = statline + " Click for computer's move.";
			 state = -1;
			 corner.token = 8;
			 showStatus(statline);

			 corner.repaint();
			 repaint();
			 }
		
		 }
		 // Handle the case where the player clicks anywhere in the
		 // "start new game" state.
		 else if(state == 1){
				 state = 0;
				 startNewGame();
				 statline = (turn == 1 ? "Human" : "Computer") + 
					 ",s move.";
   				 showStatus(statline);

		 }
		 // Handle the case where the player clicks a checkbox in the 
		 // "computer's move" state.
		 else if(state == -1 && e.target instanceof Checkbox){
			 state = 99;
			 computersMove();
		 }
		 
		 repaint();
		 return true;
	}

	public boolean mouseUp(Event e, int x, int y){
		// Catch mouse clicks in either the "start new game" state or
		// the "computer's move" state.
		String statline = " ";
		if(state == 1){
			 state = 99;
			 startNewGame();
			 statline = (turn == 1 ? "Human" : "Computer") + 
					 "'s move.";
			 showStatus(statline);
			 repaint();
			 state = 0;
			
		}
		else if(state == -1){
			state = 99;
			computersMove();
			
		}
		return true;
	}

	void computersMove(){
		    String statline = " ";
			Board successor;
			int moveNumber, winsSuccessor;
			// Prepare for usual change of state to "human's move".
			corner.token = 9;
 			state = 0;
			// First check to see if computer has a winning move.
			// Minimax might prune before we find the winning move.
			for (moveNumber = 1; moveNumber <= 10; moveNumber++){
				successor = new Board(position.token);
				successor.push(moveNumber, -1);
				winsSuccessor = successor.wins();
				if(winsSuccessor > 1){
  					 corner.token = 11;
					 corner.setBackground(Color.pink);
					 player2++;
					 statline = statline + ". Human: " + player1 + ", Computer: " + player2 + ". Click for new game.";
					 corner.repaint();
					 position.push(moveNumber, turn);
					 state = 1;
					 turn = -turn;
					 showStatus(statline);
					 repaint();
					 return;
			    }
			}

			// minimax determines value of position and best move.
			int posVal = position.minimax(-100, 100, 0);
			int best = position.bestMove;
			// If there is no good move, just make move #1.
			if(best == 0) best = 1;
			position.push(best, turn);
			winner = position.wins();
			// If computer has won, announce it, keep score, and 
			// switch to "start new game" state.
			if((turn == -1) && ((winner == 2) || (winner == 3))){
				 corner.token = 11;

				 player2++;
				 statline = statline + ". Human: " + player1 + ", Computer: " + player2 + ". Click for new game.";
				 corner.repaint();			 
				 state = 1;
			 }
			 // Possibly computer made a move that was a human win.
			 // Announce the win, keep score, and change to "start new game"
			 // state.
			 else if(turn == -1 && winner == 1){
				 corner.token = 10;
				 player1++;
 				 statline = statline + ". Human: " + player1 + ", Computer: " + player2 + ". Click for new game.";
				 corner.repaint();
				 state = 1;
			 }
 			 turn = -turn;
			 if(winner == 0)
				 statline = "Computer's move was " + best +". Click your move.";
			 
			 corner.setBackground(turn == 1 ? Color.cyan : Color.white);
 			 if(winner > 0)corner.setBackground(Color.pink);
			 showStatus(statline);
			 
			 corner.repaint();
			 repaint();
			 }


}

class TokenCanvas extends Canvas{
	public int token;
	

	public void paint(Graphics g){
		
		g.setColor(Color.black);
		if( token < 2){
			g.drawLine(0,0,0,49);
			g.drawLine(49,0,0,0);
		}

		g.drawLine(0,49,49,49);

		g.drawLine(49,49,49,0);
		

		switch(token){
		case 0:
		break;
		case 1:
			g.setColor(Color.cyan);
			g.fillOval(1,1,47,47);
			g.setColor(Color.black);
			g.drawString("Human",6,28);
		break;
		case -1:
  			g.setColor(Color.white);
			g.fillOval(1,1,47,47);
			g.setColor(Color.black);
			g.drawString("Computer",1,28);
		break;
		case 10:
			
			g.setColor(Color.black);
			g.drawString("Human ", 1,20);
			g.drawString("wins!", 10, 40);
		break;
		case 11:
			
			g.setColor(Color.black);

			g.drawString("Computer", 1,20);
			g.drawString("wins!", 10, 40);
		break;
		case 9:
			g.setColor(Color.black);
			g.drawString("Human's", 1,20);
			g.drawString("turn", 10, 40);
			
		break;
		case 8:
			g.setColor(Color.black);
			g.drawString("Computer", 1,20);
			g.drawString("turn", 10, 40);
			
		break;

		}

			

	}
}

class Board{
	public int token[];
	int positionValue;
	int bestMove;

	Board(){
		token = new int[25];
		int i;
		for(i = 0; i<24; i++){
			token[i] = 0;
		}
	}

	Board(int a[]){
 		// Constructor copies position from another board.

		token = new int[25];
		int i;
		for(i = 0; i<24; i++){
			token[i] = a[i];
		}
	}

	void reset(){
		// Clear a playing board.
		int i;
		for(i = 0; i<25; i++){
			token[i] = 0;
		}
	}


	int diff(){
		// Number of human tokens - number of computer tokens.
		int htoc = 0;
		int i;
		for(i=0; i<24; i++){
			htoc += token[i];
		}
		return htoc;
	}

	void pushcol(int i, int newtok){
		// Push a token into a column.
		int j = i - 1;
		int k = j;
		
		// push into a column
		while(token[k] != 0 && k < 20)
			k +=5;
		for(; k > j; k -=5)
			token[k] = token[k-5];
		token[j] = newtok;
		
	}

	void pushrow(int i, int newtok){
		// Push a token into a row.
		int j = (i - 6)*5;
		int k = j;
		while(token[k] != 0 && k < j+4)
			k++;
		for(; k > j; k--)
			token[k] = token[k-1];
		token[j] = newtok;
	}

	void push(int i, int newtok){
		// Push a token into a row or column.
		if(i < 6)
			pushcol(i,newtok);
		else
			pushrow(i,newtok);
	}

	int wins(){
		// Return is 1 if the position is a win for the human, 2 if it is a win
		// for the computer, 3 if it is a win for both.
		boolean humanWins = false, computerWins = false;
		int insummary = 0;
		int row, sum, col, rowbase;
		// Check the rows.
		for(row = 0; row < 5; row++){
			sum = 0;
			rowbase = row * 5;
			for(col = 0; col < 5; col++)
				sum += token[rowbase + col];
			if(sum == 5)humanWins = true;
			if(sum == -5)computerWins = true;
		}
		// Check the columns
		for(col = 0; col < 5; col++){
			sum = 0;
			for(row = 0; row < 5; row++)
				sum += token[5*row + col];
			if(sum == 5)humanWins = true;
			if(sum == -5)computerWins = true;
		}
		// Major diagonal
		sum = 0;
		for(row = 0; row < 5; row++)
			sum += token[6*row];
		if(sum == 5)humanWins = true;
		if(sum == -5)computerWins = true;
		// Minor diagonal
		sum = 0;
		for(row = 0; row < 5; row++)
			sum += token[4*row + 4];
		if(sum == 5)humanWins = true;
		if(sum == -5)computerWins = true;
		if(humanWins) insummary = 1;
		if(computerWins) insummary += 2;
		return insummary;
	}

	public int minimax(int alpha, int beta, int level){
		// Minimax with alpha-beta pruning.
		int moveNumber = 1;
		Board successor;
		int winsSuccessor;
		int nextValue;
		bestMove = 0;
		if( level == 4)
			return -this.diff();
		if( level % 2 == 0){
			for (moveNumber = 1; moveNumber <= 10; moveNumber++){
				successor = new Board(token);
				successor.push(moveNumber, -1);
				winsSuccessor = successor.wins();
				if(winsSuccessor > 1){
					bestMove = moveNumber;
					positionValue = 100; // infinity
					return positionValue;
				}
				if(winsSuccessor != 1){
					nextValue = successor.minimax(alpha, beta, level+1);
					if(nextValue != -100){
						if(nextValue > alpha){
							alpha = nextValue;
							bestMove = moveNumber;
						}
						if(alpha >= beta){
							positionValue = alpha;
							return alpha;
						}
					}
				}
			}
			return alpha;
		}
		else{
			for (moveNumber = 1; moveNumber <= 10; moveNumber++){
				successor = new Board(token);
				successor.push(moveNumber, 1);
				winsSuccessor = successor.wins();
				if(winsSuccessor == 1 || winsSuccessor == 3){
					bestMove = moveNumber;
					positionValue = -100; // -infinity
					return positionValue;
				}
				if(winsSuccessor != 2){
					nextValue = successor.minimax(alpha, beta, level+1);
					if(nextValue != 100){
						if(nextValue < beta){
							beta = nextValue;
							bestMove = moveNumber;
						}
						if(alpha >= beta){
							positionValue = beta;
							return beta;
						}
					}
				}
			}
			return beta;


		}
	}


}