import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.Random;

/*
 * Created on May 24, 2007
 */

public class Yelena extends ComputerPlayer {
	
	int maxDepth = 5;
	int alpha_min = -10;
	int beta_max = 10;
	int max_init = 70;
	int max_recur = 70;
	int num_moves, prune;
	
	public Yelena(Game game, PlayerNumber p, String limit )
	{
		super("Yelena", game, p, limit);
	}
	
	public Move findbest(Game g) throws GameException
	{
		MoveIterator iter = g.getMoves();
	    Move mv = null;
	    Move mov = null;
	    int curr = alpha_min;
	    boolean win = false;
	    num_moves=0;
	    prune=0;
	    ArrayList moves = new ArrayList ();

	    ((Isola)g).startEval();

	    while(iter.hasNext()) {
		    try {
		    Isola ng = (Isola) g.copy();
		    mov = iter.next();
	
		    m = mv = mov; /* make sure m && mv are not null. This differs
		                  slightly from the technique used in Medium to make 
		                  sure a null move is not made */
	
		    ng.startEval();
		    ng.make(mov);
	
		    if(ng.gameOver() && ng.winner().equals(getPlayerNumber())){
			    mv = mov;
			    win = true;
			    break;
		    }
		    else{
		    	Piece other = ng.getCurrentPlayer().getPlayerPiece();
		    	//Only add the move if it removes a square which is next to
		    	//the opponent's piece
		    	if(((other.getX()-mov.cell.getX()==1 ||
		    		other.getX()-mov.cell.getX()==-1) &&
		    		other.getY()-mov.cell.getY()<=1 &&
				   	other.getY()-mov.cell.getY()>=-1) ||
				  ((other.getY()-mov.cell.getY()==1 ||
				    other.getY()-mov.cell.getY()==-1) &&
				    other.getX()-mov.cell.getX()<=1 &&
				    other.getX()-mov.cell.getX()>=-1)){
			    	moves.add(mov);
		    	}
		    }
		     
		    }catch(Exception e){e.printStackTrace();}
	    }
	    /* get max_init random moves and perform a recursive evaluation on them */
	    if(!win){
	    	randomize(moves);
	        int count = 0;
			System.out.println("size is " + moves.size());
	        if(moves.size()!=0)
		    	mv = (Move) moves.get(0);
	        /* get max_init random moves and perform a recursive evaluation on them */
	        if(moves.size()<5)
	        	maxDepth=9;
	        else if(moves.size()<8)
	        	maxDepth=8;	
	        else if(moves.size()<12)
	        	maxDepth=7;
	        else if(moves.size()<15)
	        	maxDepth=6;
	        else if(moves.size()<20)
	        	maxDepth=5;
	        else if(moves.size()<25)
	        	maxDepth=4;
	        else if(moves.size()<36)
	        	maxDepth=3;
	        else
	        	maxDepth=2;
	        while (count < max_init && !halt && moves.size()!=0 && count<moves.size()) {
	        	try{
		        Isola ng = (Isola) g.copy();
		        mov = (Move) moves.get(count);
		        ng.startEval();
		        ng.make(mov);
		        int k = -negamax(ng, alpha_min, beta_max);
		        System.out.println(k + " " + curr);
		        if ( k > curr ) {
		        	curr = k;
		        	mv = mov;
		        }
		        if(k==beta_max)
		        	break;
		        count++;
		        }catch (Exception e){}
		    }
	    }
	    ((Isola)g).endEval();
	    System.out.println(num_moves + " " + prune);
	    
	    if(halt)
	    	System.out.println("halt reached");
		System.out.println (mv + " (" + mv.piece.getX() + "," + mv.piece.getY() + ")");
	    return mv;
		}
	
	public void randomize(ArrayList arr){
		Random rd = new Random(); // used to get a random move
		int tempi;
		Move temp;
		for(int i=arr.size()-1; i>=0; i--){
			tempi=rd.nextInt(i+1);
			//System.out.println(arr.size() + " " + tempi + " " + tempc + " " + i);
			temp=(Move)arr.get(i);
			arr.set(i,arr.get(tempi));
			arr.set(tempi,temp);
		}
	}
	
	public int negamax(Isola g, int alpha, int beta){

		if(g.board.ply > maxDepth || halt){
			if(halt)
				System.out.println("Halt reached");
			return beta_max;
		}
		if(g.gameOver()){//Check to see if the game is over and which player has won
			if(g.getCurrentPlayer().getPlayerNumber().equals(g.winner()))
				return beta_max;
			else
				return alpha_min;
		}
		//Check to see if we've reached the maximum depth
		if(g.board.ply == maxDepth){
			num_moves++;
			return evaluate(g);
		}
		MoveIterator iter = g.getMoves();
	    Move mov = null;
	    ArrayList moves = new ArrayList ();

	    while(iter.hasNext()) {
		    try {
		    mov = iter.next();
		    Piece other;
		    if(g.getCurrentPlayer().playerNumber.equals(PlayerNumber.ONE))
		    	other = g.players[1].getPlayerPiece();
		    else
		    	other = g.players[0].getPlayerPiece();
		    
		    //Only add the move if it removes a square which is next to
		    //the opponent's piece
		    if(((other.getX()-mov.cell.getX()==1 ||
		    	other.getX()-mov.cell.getX()==-1) &&
		    	other.getY()-mov.cell.getY()<=1 &&
				other.getY()-mov.cell.getY()>=-1) ||
			  ((other.getY()-mov.cell.getY()==1 ||
			    other.getY()-mov.cell.getY()==-1) &&
			    other.getX()-mov.cell.getX()<=1 &&
			    other.getX()-mov.cell.getX()>=-1)){
		    		moves.add(mov);
		    	}
		    } catch(Exception e){e.printStackTrace();}
	    }
	    
	    int count = 0;
	    randomize(moves);
	    
	    while (count < max_recur && !halt && moves.size()!=0 && count<moves.size()){
		    try{
		    Isola ng = (Isola) g.copy();
		    mov = (Move) moves.get(count);
		    
		    int ply = ng.board.ply; //added
	
		    ng.startEval(); //very important
	
		    ng.board.ply = ply; //added
	
		    ng.make(mov);
	
		    int newval = -negamax(ng, -beta, -alpha);
	
		    if(newval > alpha){
		    	alpha = newval;
		    }
		    if(alpha>=beta){
		    	prune++;
		    	return beta;
		    }
		    }catch(Exception e){System.out.println(e.getMessage());}
	    	count++;
	    }
	    return alpha;
	}

	public int evaluate(Isola g){
		int value =0, value1 = 0, value2 = 0;//Starts from the perspective of player 1 to move
		Collection c = g.board.members.values();
	    Iterator iter = c.iterator();
		int x1=g.players[0].playerPiece.getX(),
			y1=g.players[0].playerPiece.getY(),
			x2=g.players[1].playerPiece.getX(),
			y2=g.players[1].playerPiece.getY();
		int count = 0;
		while(iter.hasNext()){
			BoardCell cell = (BoardCell)iter.next();
			int i = cell.getX(), j = cell.getY();
			if(((x1-i==1 || x1-i==-1) && y1-j<=1 && y1-j>=-1) ||
			   ((y1-j==1 || y1-j==-1) && x1-i<=1 && x1-i>=-1)){
					value1++;
				}
			if(((x2-i==1 || x2-i==-1) && y2-j<=1 && y2-j>=-1) ||
				((y2-j==1 || y2-j==-1) && x2-i<=1 && x2-i>=-1)){
					value2--;
				}
		}
		if(value1==0)
			return alpha_min;
		if(value2==0)
			return beta_max;
		value = value1 + value2;
		//If it's really player two's turn to move, value then is negative of what was
		//calculated
		if(g.turn.playerNumber.equals(PlayerNumber.TWO))
			value = - value;
		return value;
	}
	
}