import java.io.*;
/**
 *  class Engine
 *
 *  This class holds static methods for finding the best move
 *  given a certain position.
 *
 *  @author Jonatan Pettersson (mediocrechess@gmail.com)
 *  Date: 2006-12-26
 */

public class Engine implements Definitions
{
	public static int current_depth; // The depth we are currently searching to in the iterative deepening
	public static int nodesSearched; // The number of nodes search, incremented at every alphaBeta()-call
	public static int contemptFactor; // Added to the draw value to avoid easy draws
	public static int[][] historyMoves; // Keeps track of number of times a move has been played for better sorting (history heuristic)
	public static KillerMoves killers; // Keeps track of killer moves 
	public static boolean useFixedDepth; // Are we using a fixed depth
	public static boolean stopSearch; // Set to true if used too much time
	public static long startTime; // The time we started searching at
	public static int timeForThisMove; // Set if we are using a fixed time for every move
	public static int nextTimeCheck; // Keeps track of when to check the time
	public static final int TIME_CHECK_INTERVAL = 2000; // How often we should check if time is up inside alphaBeta
	public static boolean isUci; // Are we using uci or winboard output
	public static int gamePhase; // What phase the game is in (opening, ending etc.)
	public static int[] moves; // The moves array, keeps track of moves at every ply
	public static int[] movesSort; // The ordering values for the moves
	public static int moveMemoryIndex; // Where we currently are in the moves array
	
	/**
	 * Starts the search by doing iterative deepening calls to alphaBeta()
	 * 
	 * @param board The position to search
	 * @param depth If !=0 we will search to this depth and ignore time
	 * @param uci If true we use uci thinking output, else we use winboard output
	 * @param timeLeft The time we have left
	 * @param increment The increment used in the game
	 * @param movetime If !=0 we search every move this amount of time and ignore the timeLeft and increment
	 * @return finalEval The best line and evaluation
	 */
	public static LineEval search(Board board, int depth, boolean uci, int timeLeft, int increment, int movetime) throws IOException
	{
		moves = new int[4096];
		movesSort = new int[4096];
		moveMemoryIndex = 0;


		isUci = uci; // Store wether we are using uci or winboard
	
		
		
		// Decide the contempt factor by looking at the phase the game is in
		gamePhase = Evaluation.getGamePhase(board);
		
		if(gamePhase == PHASE_OPENING) contemptFactor = CONTEMPT_OPENING;
		else if(gamePhase == PHASE_ENDING || gamePhase == PHASE_PAWN_ENDING) contemptFactor = CONTEMPT_ENDING;
		else contemptFactor = CONTEMPT_MIDDLE;
		
		if(depth == 0) useFixedDepth = false;
		else useFixedDepth = true;

		LineEval finalEval = new LineEval(); // Stores the evaluation and principal valuation
		nodesSearched = 0; // Initialize nodes searched

		startTime = System.currentTimeMillis(); // Start the timer

		historyMoves = new int[120][120];
		killers = new KillerMoves(); // Initialize the killer move class
		
		int alpha = -INFINITY; // First iteration will be with ordinary values for alpha and beta
		int beta = INFINITY;

		stopSearch = false; // Initialize the hard stop

		if(movetime == 0) // Not fixed time per move
		{
			timeForThisMove = calculateTime(timeLeft, increment); // Calculate the time for this move
		}
		else // Fixed time per move
		{
			timeForThisMove = movetime;
		}

		for(current_depth = 1;;) // Start the iterative deepening loop
		{	
			nextTimeCheck = TIME_CHECK_INTERVAL; // Reset the time check 

			int eval = alphaBeta(board,current_depth,alpha,beta, false); // Search with the current depth
			
			if(stopSearch) break;
						
			// If we miss the aspiration window, make a new search with full windows
			// Do this check before reporting any lines so we don't get double reports
			// for researchs
			if(eval <= alpha || eval >= beta)
			{
				alpha = -INFINITY;
				beta = INFINITY;
				continue;
			}	
			else // Only get eval and pv if we do not have to recall
			{
				finalEval = new LineEval(Mediocre.transpositionTable.collectPV(board, current_depth), eval); // Record the evaluation and principal variation
			}

			System.out.println(receiveThinking(startTime, finalEval)); // Get a thinking string and send

			alpha = eval -30; // Get ready for a new search, with a new window
			beta = eval +30;  // The current window equas 1/10 of a pawn

			if(useFixedDepth)
			{
				if(current_depth == depth || eval == MATE_VALUE || eval == -MATE_VALUE) break;
			}
			else
			{
				if(System.currentTimeMillis() - startTime > timeForThisMove || eval == MATE_VALUE || eval == -MATE_VALUE) break; // We have reached the allocated time or found a mate, and exit
			}
			current_depth++; // Go to the next depth


		}

		return finalEval;
	}
	// END search()
	
	/**
	 *  Takes the time left and calculates how much is to be
	 *  used on this move, increment adds a bit to the thinking time
	 *
	 *  @param timeLeft The total time left
	 *  @param increment The games uses increments
	 *  @return timeForThisMoves The time to be used on this move
	 */
	private static int calculateTime(int timeLeft, int increment)
	{
		// Use 2.25% of the time + half of the increment
		int timeForThisMove = timeLeft/40+(increment/2);

		// If the increment puts us above the total time left
		// use the timeleft - 0.5 seconds
		if(timeForThisMove >= timeLeft)
			timeForThisMove = timeLeft -500;

		// If 0.5 seconds puts us below 0
		// use 0 seconds
		if(timeForThisMove < 0)
			timeForThisMove = 100;


		return timeForThisMove;
	}
	// END calculateTime()	
	

	/**
	 *  Returns a thinking line
	 *
	 *  @param time The time the search began
	 *  @param finalEval The evaluation and pv
	 *  @return String The thinking string
	 */
	private static String receiveThinking(long time, LineEval finalEval)
	{
		
		if(isUci) // We are using uci protocol
		{

			// Built the pv line
			String pvString = "";
			for(int i = 0; i < 128; i++)
			{
				if(finalEval.line[i] == 0) break;
				pvString += (Move.inputNotation(finalEval.line[i]) + " ");
			}

			// Calculate the nodes per second, we need decimal values
			// to get the most accurate result.
			// If we have searched less than 1 second return the nodesSearched
			// since the numbers tend to get crazy at lower times

			long splitTime = (System.currentTimeMillis() - time);
			int nps;
			if((splitTime / 1000) < 1) nps = nodesSearched;
			else
			{
				Double decimalTime = new Double(nodesSearched/(splitTime/1000D));
				nps = decimalTime.intValue();
			}

			// Send the info to the uci interface
			return "info score cp " + finalEval.eval + " depth " + current_depth + " nodes " + nodesSearched + " nps " + nps + " time " + splitTime + " pv " + pvString;


		}
		else // We are using winboard protocol
		{
			// Start building the thinking output
			String stringEval = current_depth + " " + finalEval.eval + " " + (System.currentTimeMillis() - time) + " " + nodesSearched + " ";

			// Insert the principal variation into the stringEval
			for(int i = 0; i < 128; i++)
			{
				if(finalEval.line[i] == 0) break;
				stringEval += (Move.notation(finalEval.line[i]) + " ");
			}

			return stringEval; // Send the stringEval to the gui
		}		

	}
	// END receiveThinking()

	/**
	 *  class LineEval
	 *
	 *  Holds a line and evaluation number used to return in search
	 */
	public static class LineEval
	{
		public int[] line;
		public int eval;

		public LineEval()
		{
			this.line = new int[128];
			this.eval = 0;
		}

		public LineEval(int[] line, int eval)
		{
			this.line = line;
			this.eval = eval;
		}
	}
	// END class LineEval
	
	/**
	 *  class KillerMoves
	 *
	 *  Holds killer moves for the alphaBeta search
	 */
	public static class KillerMoves
	{
		public int[] primaryKillers; // The index corresponds to the ply the killer move is located in
		public int[] secondaryKillers;
		public int[][][] everyKiller; // ply, from index, to index

		public KillerMoves()
		{
			primaryKillers = new int[100]; // Assuming we never search over 100 plies deep
			secondaryKillers = new int[100];
			everyKiller = new int[100][120][120]; // Assuming we never search over 100 plies and indexes are on the 0x88 board
		}

		/**
		 *  Inserts a new killer move into either primary or secondary array
		 *
		 *  @param move The killer move
		 *  @param ply The ply the killer move exists in
		 */
		public void addKiller(int move, int ply)
		{
			if(primaryKillers[ply] == 0) primaryKillers[ply] = move; // Spot was empty so take it
			else if(secondaryKillers[ply] == 0) secondaryKillers[ply] = move; // Primary was taken, but secondary empty so take it

			// If the move isn't the same as in primary killers and it has a higher count
			// put it to primaryKillers and move down the primary killer to secondary
			else if(Move.fromIndex(primaryKillers[ply]) != Move.fromIndex(move) && Move.toIndex(primaryKillers[ply]) != Move.toIndex(move) && everyKiller[ply][Move.fromIndex(primaryKillers[ply])][Move.toIndex(primaryKillers[ply])] < everyKiller[ply][Move.fromIndex(move)][Move.toIndex(move)])
			{
				secondaryKillers[ply] = primaryKillers[ply];
				primaryKillers[ply] = move;
			}
			// If the move isn't the same as in secondaryKiller and has a higher count
			else if(Move.fromIndex(secondaryKillers[ply]) != Move.fromIndex(move) && Move.toIndex(secondaryKillers[ply]) != Move.toIndex(move) && everyKiller[ply][Move.fromIndex(secondaryKillers[ply])][Move.toIndex(secondaryKillers[ply])] < everyKiller[ply][Move.fromIndex(move)][Move.toIndex(move)])
			{
				secondaryKillers[ply] = move;
			}
		}
		// END addKiller()

		/**
		 *  Increments the number a certain killer has occured
		 *
		 *  @param move The move
		 *  @param ply The ply the move exists in
		 */
		public void incrementKiller(int move, int ply)
		{
			// Increment the place that corresponds to the ply and from/to index
			everyKiller[ply][Move.fromIndex(move)][Move.toIndex(move)]++;
		}
		// END incrementKiller()
	}
	// END KillerMoves

	
	
	/**
	 *  Checks wether the search should stop or not,
	 *  can be due to out of time, or 'stop'/'?' has been sent
	 *  by the interface (uci-stop winboard-?)
	 *  
	 *  return boolean true for stop, false for not
	 */
	public static boolean shouldWeStop() throws IOException
	{
		
		if(((System.currentTimeMillis() - startTime) > timeForThisMove))
		{
			return true;

		}
		if(Mediocre.reader.ready())
		{
			
			if(isUci)
			{
				if("stop".equals( Mediocre.reader.readLine() ))
				{
					return true;
				}
			}
			else
			{
				if(Mediocre.reader.readLine().startsWith("?"))
				{
					return true;
				}
			}
		}

		return false;
		
	}
	// END shouldWeStop()

	/**
	 * The alpha-beta search
	 * 
	 * @param board The position we're at
	 * @param ply The current ply we're at (starts at the current depth and goes down to 0)
	 * @param alpha The alpha value
	 * @param beta The beta value
	 * @param allowNull If a null move is allowed
	 * @return int Depending on where in the search we are returns alpha, beta or exact evaluation
	 */
	public static int alphaBeta(Board board, int ply, int alpha, int beta, boolean allowNull) throws IOException
	{
		int bestMove = 0;
		if(ply < 0) ply = 0;
		nodesSearched++; // Add a node searched

		if(!useFixedDepth)
		{
			nextTimeCheck--;
			if(nextTimeCheck == 0) // Time to check the time
			{
				nextTimeCheck = TIME_CHECK_INTERVAL;
				
				if(shouldWeStop())
				{
					stopSearch = true;
					return 0;
				}
			}
		}
		
		if((ply != current_depth && Mediocre.repTable.repExists(board.zobristKey)) || board.movesFifty >= 100)
		{
			//return -DRAW_VALUE;
			return -(DRAW_VALUE + contemptFactor);
		}
		
		if(Mediocre.transpositionTable.entryExists(board.zobristKey) && Mediocre.transpositionTable.getDepth(board.zobristKey) >= ply) // Check if the value in the hashtable was found at same or higher depth search
		{
			if(Mediocre.transpositionTable.getFlag(board.zobristKey) == HASH_EXACT)
			{
				return Mediocre.transpositionTable.getEval(board.zobristKey);
			}
			else if(Mediocre.transpositionTable.getFlag(board.zobristKey) == HASH_ALPHA && Mediocre.transpositionTable.getEval(board.zobristKey) <= alpha)
			{
				return Mediocre.transpositionTable.getEval(board.zobristKey);
			}
			else if(Mediocre.transpositionTable.getFlag(board.zobristKey) == HASH_BETA && Mediocre.transpositionTable.getEval(board.zobristKey) >= beta)
			{
				return Mediocre.transpositionTable.getEval(board.zobristKey);
			}
		}

		// The there is a check in the position, we want to extend the search one
		// ply to see if there is something dangerous with the check
		boolean extend = false;
		/*if(isInCheck(board))
		{
			ply++;
			extend = true;
		}*/
		
		int eval = 0;

	




		if(ply <= 0)
		{
			//eval = Evaluation.evaluate(board);
			eval = quiescentSearch(board, alpha, beta);
			if(eval >= beta)
				Mediocre.transpositionTable.record(board.zobristKey, 0, HASH_BETA, eval, 0);
			else if(eval <= alpha)
				Mediocre.transpositionTable.record(board.zobristKey, 0, HASH_ALPHA, eval, 0);
			else {
				Mediocre.transpositionTable.record(board.zobristKey, 0, HASH_EXACT, eval, 0);
			}
		
			return eval; // Reached the depth, continue with quiescent search
		}

		// Start with trying a null-move if allowed
		// Do not use null moves if he search was extended since that means
		// something interesting might be about to happen
		if(allowNull && !extend && gamePhase != PHASE_PAWN_ENDING)
		{
			if(!isInCheck(board))
			{
				board.nullmoveToggle(); // Making a null-move
				eval = -alphaBeta(board, ply-3, -beta, -beta+1, false);
				
				board.nullmoveToggle(); // Unmaking the null-move

				if(eval >= beta)
				{
					if(!stopSearch)
						Mediocre.transpositionTable.record(board.zobristKey, ply, HASH_BETA, eval, 0);
					return eval; // Cutoff
				}
			}
		}
		
		if(stopSearch) return 0; // Stop the search



		int firstMoveIndex = moveMemoryIndex;
		moveMemoryIndex += board.generateMoves(false, moves, firstMoveIndex);
		 
		
		if(firstMoveIndex == moveMemoryIndex)
		{
			return mateCheck(board, ply); // No legal moves, check for mate/stalemate
		}

		int bestEval = -INFINITY;
		
		int eval_type = HASH_ALPHA;
	


		sortMoves(moves, firstMoveIndex, moveMemoryIndex, ply, board);

		for(int i = firstMoveIndex; i < moveMemoryIndex; i++)
		{			
			
			board.makeMove(moves[i]); // Make the move on the board

			if(eval_type == HASH_EXACT) // We have found a good move, so do the pv search
			{   
				eval = -alphaBeta(board, ply-1, -alpha -1, -alpha, true);

				if(eval > alpha && eval < beta)
				{
					eval = -alphaBeta(board, ply-1, -beta, -alpha, true);

				}
			}
			else // We have not found a good move yet, so do ordinary search.
			{
				eval = -alphaBeta(board, ply-1, -beta, -alpha, true);
			}

			board.unmakeMove(moves[i]); // Reset the board

			if(eval > bestEval)
			{
				if(eval >= beta) // If the evalatuion is bigger than beta, cutoff
				{
					if(!stopSearch)
						Mediocre.transpositionTable.record(board.zobristKey, ply, HASH_BETA, eval, moves[i]);
					killers.incrementKiller(moves[i], ply); // Increment the possible killer
					killers.addKiller(moves[i], ply); // Try to add the killer

					historyMoves[(Move.fromIndex(moves[i]))][Move.toIndex((moves[i]))]++;

					moveMemoryIndex = firstMoveIndex;
					return eval;
				}

				
				bestEval = eval;
				bestMove = moves[i];
				
				if(eval > alpha) // If the evaluation is bigger than alpha (but less than beta) this is our new best move
				{
					eval_type = HASH_EXACT;
					alpha = eval;
				}
			}
		}
	
		
		if(!stopSearch)
			Mediocre.transpositionTable.record(board.zobristKey, ply, eval_type, bestEval, bestMove);
		moveMemoryIndex = firstMoveIndex;
		return alpha;
	}
	//END alphaBeta()
	
	/**
	 *  Quiescent search, looks at captures passed the search depth
	 *
	 *  @param board The board to search
	 *  @param alpha alpha value
	 *  @param beta beta value
	 *  @return int The expected evaluation
	 */
	private static int quiescentSearch(Board board, int alpha, int beta)
	{
		int eval = Evaluation.evaluate(board); // Start with evaluating the current position

		if(eval >= beta)
		{ // Check if we get a cutoff, the move is too good
			return beta;
		}


		if(eval > alpha)
		{
			
			alpha = eval;
		}
		
		
		int firstMoveIndex = moveMemoryIndex;
		moveMemoryIndex += board.generateMoves(true, moves, firstMoveIndex); // Get captures

		
		
		bubbleSortQuis(moves, firstMoveIndex, moveMemoryIndex); // Sort the captures according to MVA/LVV

		for(int i = firstMoveIndex; i < moveMemoryIndex; i++) // Loop through all the captures
		{
			board.makeMove(moves[i]); // Make first capture on the board
			eval = -quiescentSearch(board, -beta, -alpha); // Call recursively just like in alphabeta
			board.unmakeMove(moves[i]); // Reset the board


			if(eval >= beta)// The move is too good
			{
				moveMemoryIndex = firstMoveIndex;
				return beta;
			}

			if(eval > alpha)// Best move so far
			{
				alpha = eval;
							

			}
		}			
		
		moveMemoryIndex = firstMoveIndex;
		return alpha;
	}
	// END quiescentSearch()
	
	/**
	 * Sets 
	 *
	 *  @param moves Moves to be sorted
	 *  @param ply The depth the search is currently at
	 */
	/**
	 * Gives the moves an ordering value, from being a hash move, killer move etc.
	 * 
	 * The ordering values are stored in a separate array
	 * 
	 * @param moves The moves we want to order
	 * @param startIndex Where the moves we want start
	 * @param endIndex Where the moves we want end
	 * @param ply What ply in the search are we at, used to find killer moves
	 * @param board The current position, used to find the transposition table entry
	 */
	private static void sortMoves(int[] moves, int startIndex, int endIndex, int ply, Board board) 
	{
		// TODO: See if we can move the 'sortMoves' into the generate moves algorithms,
		// this method doesn't really sort the moves it only puts values on them which
		// could be done when generating instead
		
		if(ply <0) ply = 0;
		
		//TranspositionTable.Hashentry hashentry = Mediocre.transpositionTable.getEntry(board.zobristKey);

		// Go through the moves and add orderingValues according to the type of move
		for(int i = startIndex; i < endIndex; i++)
		{
			movesSort[i] = 0;
			try{
				
			
			if(moves[i] == Mediocre.transpositionTable.getMove(board.zobristKey))
			{
				
				movesSort[i] += 5000;
			}
			if(moves[i] == killers.primaryKillers[ply])
			{
				movesSort[i] += 3000;			
			}
			else if(moves[i] == killers.secondaryKillers[ply])
			{
				movesSort[i] += 2000;
			}

			movesSort[i] += historyMoves[Move.fromIndex(moves[i])][Move.toIndex(moves[i])];
			
			movesSort[i] += Move.orderingValue(moves[i]);
			
			
			}
			catch(ArrayIndexOutOfBoundsException ex){}

		}		
		 bubbleSortMoves(moves, startIndex, endIndex); // Order the moves according to their ordering values
	}
	// END sortMoves()

	/**
	 * Sorts the moves in the array according to their ordering values
	 * using the bubbleSort algorithm
	 * 
	 * The ordering values are in a separate array, but both arrays
	 * has to be sorted
	 * 
	 * TODO: We probably won't have to send the toSort array since it is the
	 * global moves[] array anyway
	 * 
	 * @param toSort The array to sort
	 * @param startIndex Where to start
	 * @param endIndex Where to stop
	 */
	public static void bubbleSortMoves(int[] toSort, int startIndex, int endIndex)
	{
		boolean done = false;
		for(int i = startIndex; i < endIndex; i++)
		{
			if(done) break;
			done = true;

			for(int j = endIndex - 1; j > i; j--)
			{
				if(movesSort[j] > movesSort[j-1])
				{
					// Switch the moves' places
					int temp = toSort[j];
					toSort[j] = toSort[j-1];
					toSort[j-1] = temp;
					
					// Switch the sort places
					temp = movesSort[j];
					movesSort[j] = movesSort[j-1];
					movesSort[j-1] = temp;
					
					done = false;
				}
			}
		}
	}
	// END bubbleSortMoves()
	
	/**
	 *  Same as bubbleSortMoves but only uses the ordering value located in the move
	 *  and not the movesSort array
	 *
	 *  @param toSort The moves to sort
	 *  @param startIndex Where to start
	 *  @param endIndex Where to end
	 */
	public static void bubbleSortQuis(int[] toSort, int startIndex, int endIndex)
	{
		boolean done = false;
		for(int i = startIndex; i < endIndex; i++)
		{
			if(done) break;
			done = true;

			for(int j = endIndex - 1; j > i; j--)
			{
				if(Move.orderingValue(toSort[j]) > Move.orderingValue(toSort[j-1]))
				{
					int temp = toSort[j];
					toSort[j] = toSort[j-1];
					toSort[j-1] = temp;
					done = false;
				}
			}
		}
	}
	// END bubbleSortMoves()
	
	/**
	 *  Takes a board and checks for mate/stalemate, this method assumes
	 *  that there are no legal moves for the side on the move
	 *
	 *  @param board The board to check
	 *  @param ply What ply the mate is found on
	 *  @return int The evaluation
	 */
	public static int mateCheck(Board board, int ply)
	{
		int king_square;		
		if(board.toMove == WHITE_TO_MOVE) king_square = board.wking_index;
		else king_square = board.bking_index;

		board.toMove *= -1; // Switch side to move on the board to get the other side's pieces to be the attacker
		if(board.isAttacked(king_square))
		{
			board.toMove *= -1; // Switch back side to move	
			return -(MATE_VALUE + ply); // Return the negative mate value + ply, negative since the 
		}
		else
		{
			board.toMove *= -1; // Switch back side to move
			return -DRAW_VALUE;
		}	



	}
	//END mateCheck()
	
	/**
	 *  Similar to mateCheck but only reports if the king of the side moving
	 *  is in check or not
	 *
	 *  @param board The board to check
	 *  @return boolean true if the king of the side moving is in check, false if is not
	 */
	public static boolean isInCheck(Board board)
	{
		int king_square;		
		if(board.toMove == WHITE_TO_MOVE) king_square = board.wking_index;
		else king_square = board.bking_index;

		board.toMove *= -1; // Switch side to move on the board to get the other side's pieces to be the attacker
		if(board.isAttacked(king_square))
		{
			board.toMove *= -1; // Switch back side to move	
			return true; // The king is in check
		}		
		board.toMove *= -1; // Switch back side to move	
		return false; // The king is not in check
	}
	//END isInCheck()
}
