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 = 10000; // 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
	public static int globalBestMove;
	public static final int ASPIRATION_SIZE = 10;
	
	/**
	 * 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
	 * @param leftOpening This is the first search after the opening book ended, use more time on this move
	 * @return finalEval The best line and evaluation
	 */
	public static LineEval search(Board board, int depth, boolean uci, int timeLeft, int increment, int movetime, boolean leftOpening) 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, leftOpening, board); // Calculate the time for this move
		}
		else // Fixed time per move
		{
			timeForThisMove = movetime;
		}

		for(current_depth = 1; current_depth <= 64;) // Start the iterative deepening loop
		{	
			nextTimeCheck = TIME_CHECK_INTERVAL; // Reset the time check 
			
			int eval = searchRoot(board,alpha,beta);
			
			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
			{
				// If the score dropped by atleast the value of a pawn
				// on the last iteration something dangerous is happening
				// so try use more time on this move
				// Won't be used if we are used fix time per move
				/*if(movetime == 0 && eval+100 < finalEval.eval)
				{
					timeForThisMove = needMoreTime(timeLeft, timeForThisMove, (int)(System.currentTimeMillis() - startTime));
				}*/
				
				// Record the evaluation
				finalEval = new LineEval(Mediocre.transpositionTable.collectPV(board, current_depth), eval); // Record the evaluation and principal variation, flip the eval if it's black to move so black ahead is always negative
			}

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

			alpha = eval -ASPIRATION_SIZE; // Get ready for a new search, with a new window
			beta = eval +ASPIRATION_SIZE;  // The current window equals 3/10 of a pawn
			
			if(alpha <= -INFINITY) alpha = -INFINITY;
			if(beta >= INFINITY) beta = INFINITY;
			
			

			if(useFixedDepth)
			{
				if(current_depth == depth || eval == -(MATE_VALUE +1)) break;
			}
			else if(movetime != 0)
			{
				if(System.currentTimeMillis() - startTime > timeForThisMove || eval == -(MATE_VALUE +1)) break; // We have reached the allocated time or found a mate, and exit
			}
			else
			{
				// If we used 90% of the time so far, we break here
				if(System.currentTimeMillis() - startTime > timeForThisMove*0.9 || eval == -(MATE_VALUE +1)) break; // We have reached the allocated time or found a mate, and exit
			}
			current_depth++; // Go to the next depth


		}
		return finalEval;
	}
	// END search()
	
	/**
	 * Used when evaluation make a big change after an iteration
	 * grants more time to use on the move
	 * 
	 * @param timeLeft Total time left in the game
	 * @param originalTimeForThisMove What was originally granted for the move
	 * @param timeUsed How much time we used so far
	 * @return Either the new time to use, or the same time if we don't grant new time
	 */
	/*private static int needMoreTime(int timeLeft, int originalTimeForThisMove, int timeUsed)
	{
		// Give half the total time for this move + what was left of the originally granted time
		int newTimeForThisMove = (originalTimeForThisMove-timeUsed) + (originalTimeForThisMove/2);
		
		// If we run out of time by doing this, don't grant new time
		if(newTimeForThisMove >= timeLeft)
		{
			return originalTimeForThisMove;
		}
		// Grant more time
		else
		{
			return newTimeForThisMove;
		}		
	}*/
	// END needMoreTime()
	
	/**
	 *  Takes the time left and calculates how much is to be
	 *  used on this move, increment adds to the thinking time
	 *
	 *  @param timeLeft The total time left
	 *  @param increment The games uses increments
	 *  @param leftOpening If true this is the first search after the opening moves so we should use more time
	 *  @param board Board is submitted so we can check for queens and such
	 *  @return timeForThisMoves The time to be used on this move
	 */
	private static int calculateTime(int timeLeft, int increment, boolean leftOpening, Board board)
	{
		int timeForThisMove; // The maximum time we are allowed to use on this move
		int percent; // How many percent of the time we will use; percent=20 -> 5%, percent=40 -> 2.5% etc. (formula is 100/percent, i.e. 100/40 =2.5)
		
		/*if(leftOpening)
		{
			// We left the opening so we should spend some time understanding the position
			percent = 10; // 10% of the time left		
		}
		else if ((gamePhase == PHASE_OPENING || gamePhase == PHASE_MIDDLE) && (board.pieces[30] != -1 || board.pieces[14] != -1))
		{
			// Queens are still on the board along with more pieces, so we need to be careful
			percent = 30; // 3.33% of the time left
		}
		else*/
		{
			// Did not leave opening and no queens, so use the standard amount
			percent = 40; // 2.5% of the time left
		}
		
		// Use the percent + increment for the move
		timeForThisMove = timeLeft/percent+(increment);

		// 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.1 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(i == 0)
				{
					pvString += (Move.inputNotation(globalBestMove) + " ");
				}
				else if(finalEval.line[i] == 0) break;
				else
				{
					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
			if(finalEval.eval >= MATE_BOUND)
			{
				int rest = ((-MATE_VALUE) - finalEval.eval)%2;
				int mateInN = (((-MATE_VALUE)-finalEval.eval)-rest)/2+rest;
				return "info score mate " + mateInN + " depth " + current_depth + " nodes " + nodesSearched + " nps " + nps + " time " + splitTime + " pv " + pvString;				
			}
			else if(finalEval.eval <= -MATE_BOUND)
			{
				int rest = ((-MATE_VALUE) + finalEval.eval)%2;
				int mateInN = (((-MATE_VALUE)+finalEval.eval)-rest)/2+rest;
				return "info score mate " + -mateInN + " depth " + current_depth + " nodes " + nodesSearched + " nps " + nps + " time " + splitTime + " pv " + pvString;				
			}
			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 = "";
			String stringLine = "";

			// Insert the principal variation into the stringEval
			for(int i = 0; i < 128; i++)
			{
				if(i == 0)
				{
					stringLine += (Move.notation(globalBestMove) + " ");
				}
				else if(finalEval.line[i] == 0)
				{
					stringEval = current_depth + " " + finalEval.eval + " " + (System.currentTimeMillis() - time) + " " + nodesSearched + " ";
					break;
				}
				else
				{
					stringLine += (Move.notation(finalEval.line[i]) + " ");
				}

				
			}
			
			stringEval += " " + stringLine;
			

			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()

	/**
	 * Searches the root moves. The search is done slightly differently at the root
	 */
	public static int searchRoot(Board board, int alpha, int beta) throws IOException
	{
		int eval = 0;
		int bestMove = 0;
		int bestEval = -INFINITY;
		int eval_type = HASH_ALPHA;

		int firstMoveIndex = moveMemoryIndex;
		moveMemoryIndex += board.generateMoves(false, moves, firstMoveIndex);
		sortRootMoves(moves, firstMoveIndex, moveMemoryIndex, current_depth, 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, current_depth-1, -alpha -1, -alpha, true, 1);

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

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

			board.unmakeMove(moves[i]); // Reset the board
			
			if(stopSearch)
			{
				break;
			}

			if(eval > bestEval)
			{
				if(eval >= beta) // If the evalatuion is bigger than beta, cutoff
				{
					if(!stopSearch)
						Mediocre.transpositionTable.record(board.zobristKey, current_depth, HASH_BETA, eval, moves[i]);
					//killers.incrementKiller(moves[i], current_depth); // Increment the possible killer
					//killers.addKiller(moves[i], current_depth); // 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, current_depth, eval_type, bestEval, bestMove);
		}
		moveMemoryIndex = firstMoveIndex;
		
		if(bestMove != 0) globalBestMove = bestMove;
		
		return alpha;		
	}
	// END searchRoot()
	
	/**
	 * 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, int depth) 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)
		{
			//Mediocre.transpositionTable.record(board.zobristKey, ply, HASH_EXACT, (DRAW_VALUE + contemptFactor), 0);
			return (DRAW_VALUE + contemptFactor);
			
			// TODO: Contempt factor still not right. Should be - for white and + for black
		}
		
		Mediocre.repTable.recordRep(board.zobristKey);
		
		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)
			{
				Mediocre.repTable.removeRep(board.zobristKey);
				return Mediocre.transpositionTable.getEval(board.zobristKey);
			}
			else if(Mediocre.transpositionTable.getFlag(board.zobristKey) == HASH_ALPHA && Mediocre.transpositionTable.getEval(board.zobristKey) <= alpha)
			{
				Mediocre.repTable.removeRep(board.zobristKey);
				return Mediocre.transpositionTable.getEval(board.zobristKey);
			}
			else if(Mediocre.transpositionTable.getFlag(board.zobristKey) == HASH_BETA && Mediocre.transpositionTable.getEval(board.zobristKey) >= beta)
			{
				Mediocre.repTable.removeRep(board.zobristKey);
				return Mediocre.transpositionTable.getEval(board.zobristKey);
			}
		}

		// If 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 isInCheck = false;
		if(isInCheck(board))
		{
			ply++;
			isInCheck = 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);
			}
			Mediocre.repTable.removeRep(board.zobristKey);
			return eval;
		}

		// 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 && !isInCheck && gamePhase != PHASE_PAWN_ENDING)
		{
			int R = 2;
			board.nullmoveToggle(); // Making a null-move
			eval = -alphaBeta(board, ply-1-R, -beta, -beta+1, false, depth+1);

			board.nullmoveToggle(); // Unmaking the null-move

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

		if(stopSearch)
		{
			Mediocre.repTable.removeRep(board.zobristKey);
			return 0; // Stop the search
		}
		

		// Internal iterative deepening if we don't have a hash move
		int hashMove = Mediocre.transpositionTable.getMove(board.zobristKey);

		int iidDepth = ply/2;
		if(hashMove == 0 && ply > 3 && iidDepth >= Mediocre.transpositionTable.getDepth(board.zobristKey))
		{
			alphaBeta(board, iidDepth, alpha, beta, false, depth+1);
			hashMove = Mediocre.transpositionTable.getMove(board.zobristKey);			
		}

		
		
		int generationState = GEN_HASH;
		int rememberMoveMemoryIndex = moveMemoryIndex;
		int firstMoveIndex = moveMemoryIndex;
		int tempMove;
		int losingCaptureIndexStart = firstMoveIndex; // Keeps track of where the losing captures start, initialized here to make java compiler happy will change below
		int losingCaptureIndexEnd = moveMemoryIndex;
		int startIndex = firstMoveIndex;
		int endIndex = moveMemoryIndex; // Tells the for-loop between what indexes to get moves
		int bestEval = -INFINITY;
		int eval_type = HASH_ALPHA;
		boolean atleastOneLegal = false; // Is set to true if we find atleast one legal move, if left false after all generation is done, there are no legal moves and the positions is mate or stalemate
		
	
		// Outer loop, this loops 6 times, one time for every time of move generation
		while(generationState < GEN_END)
		{		
			// For every generation change, make sure we reset the futility settings
			boolean fprune = false;
			int fmargin = 0;
			int materialEval = 0;
			
			// Generate part of the moves depending on how many times we have looped
			switch(generationState)
			{
			case GEN_HASH:
				// If there is a hash move (which we got before or from iid), record it and give it a very high ordering value
				if(hashMove != 0)
				{
					moves[moveMemoryIndex] = hashMove;
					movesSort[moveMemoryIndex] = 10000;
					moveMemoryIndex++;
				}
				startIndex = firstMoveIndex;
				endIndex = moveMemoryIndex;
				break;
			case GEN_CAPS:
				// Start generating captures
				
				firstMoveIndex = moveMemoryIndex;
				
				// Generate all pseudo legal captures on the board
				moveMemoryIndex += board.gen_caps(moves, firstMoveIndex);

				// Go through the moves and assign the ordering values according to see
				for(int i = firstMoveIndex; i < moveMemoryIndex; i++)
				{
					tempMove = moves[i];

					// If the capture is the same as the hashMove, we have already searched it
					// so give it a very low value, it will be skipped when run into below.
					if(tempMove == hashMove)
					{
						movesSort[i] = -10000;
					}
					else
					{
						// The move is not a duplicate so give it a see value
						movesSort[i] = See.see(board, tempMove);
					}
				}

				// We now have ordering values for all the captures so order them with bubblesort
				losingCaptureIndexStart = sortCaps(firstMoveIndex, moveMemoryIndex);
				losingCaptureIndexEnd = moveMemoryIndex;
				
				startIndex = firstMoveIndex;
				if(losingCaptureIndexStart == -1)
					endIndex = moveMemoryIndex;
				else
					endIndex = losingCaptureIndexStart;
				break;
			case GEN_KILLERS: firstMoveIndex = moveMemoryIndex; break; // TODO: Pick killers here instead of finding them below, need verification code
			case GEN_NONCAPS:				
				// Start generating non captures
				
				firstMoveIndex = moveMemoryIndex;
				
				// Generate all pseudo legal captures on the board
				moveMemoryIndex += board.gen_noncaps(moves, firstMoveIndex);

				// Go through the moves and assign the ordering values according to see
				for(int i = firstMoveIndex; i < moveMemoryIndex; i++)
				{
					tempMove = moves[i];

					if(tempMove == hashMove)
					{
						movesSort[i] = -10000; // Hash move is already searched so skip it
					}
					else if(tempMove == killers.primaryKillers[ply])
					{
						movesSort[i] = 5000;
					}
					else if(tempMove == killers.secondaryKillers[ply])
					{
						movesSort[i] = 2500;
					}
					else
					{
						// Add ordering value from the history
						movesSort[i] = historyMoves[Move.fromIndex(moves[i])][Move.toIndex(moves[i])];
					}
				}

				// Sort the non-captures
				sortNoncaps(firstMoveIndex, moveMemoryIndex);
				
				startIndex = firstMoveIndex;
				endIndex = moveMemoryIndex;
				break;
			case GEN_LOSINGCAPS:
				// Here we go back and use the losing captures generated in GEN_CAPS if there were any				
				if(losingCaptureIndexStart == -1)
				{
					// No losing captures so skip looping
					startIndex = moveMemoryIndex;
					endIndex = moveMemoryIndex;
				}
				else
				{
					// Select the captures that were losing
					startIndex = losingCaptureIndexStart;
					endIndex = losingCaptureIndexEnd;					
				}
				
				break;
				
			}
			
			// Futility pruning, if we're at a frontier node
			// check if the current evaluation + 200 (500 for pre frontier nodes)
			// reaches up to alpha, if it doesn't the node is poor and we
			// do not search it if it's not a checking move (determined below)
			if(ply <= 2 && !isInCheck)
			{
				materialEval = Evaluation.evaluate(board,false);
				if(ply == 1 && (materialEval +200)  <= alpha)
				{
					fmargin = 200;
					fprune = true;
				}
				else if(ply == 2 && materialEval + 500 <= alpha)
				{
					fmargin = 500;
					fprune = true;
				}
			}
			
			
			// Go through the generated moves one by one
			for(int i = startIndex; i < endIndex; i++)
			{

				if(movesSort[i] == -10000) continue;

			
				
				board.makeMove(moves[i]); // Make the move on the board
				
				// Make sure we don't leave the king in check when making this move
				if(board.toMove == BLACK_TO_MOVE && board.isAttacked(board.w_king.pieces[0], BLACK))
				{
					board.unmakeMove(moves[i]);
					continue;
				}
				else if(board.toMove == WHITE_TO_MOVE && board.isAttacked(board.b_king.pieces[0], WHITE))
				{
					board.unmakeMove(moves[i]);
					continue;
				}
				
				atleastOneLegal = true; // The move was legal, so we have atleast one legal move
				
				
				// Futility pruning, if we decided that we could not reach alpha
				// above, see if the move is a checking move, if it isn't just
				// set the score to whatever the eval was and continue with the next move
				if(fprune && !isInCheck(board))
				{
					// If the move was a capture we add the value of the captured piece
					// if the move was not a capture this will add 0 (leaving materialEval unchanged)
					materialEval += Math.abs(PIECE_VALUE_ARRAY[Move.capture(moves[i])+7]);
					if((materialEval+fmargin) <= alpha)
					{
						if(materialEval > bestEval) bestEval = materialEval;
						board.unmakeMove(moves[i]);
						continue;
					}
				}
				
	
				

	
				
				if(eval_type == HASH_EXACT) // We have found a good move, so do the pv search
				{   

					// Late move reduction
					if(generationState >= GEN_NONCAPS && ply >= 3 && Move.capture(moves[i]) == 0 && !isInCheck(board))
					{
						eval = -alphaBeta(board, ply-2, -alpha-1,-alpha, true, depth+1);
					}
					else eval = alpha +1; // If the move was not reduced make sure we enter the ordinary searches below



					if(eval > alpha)
					{
						// Pvs search
						eval = -alphaBeta(board, ply-1, -alpha -1, -alpha, true, depth+1);

						if(eval > alpha && eval < beta)
						{
							// Full depth search
							eval = -alphaBeta(board, ply-1, -beta, -alpha, true, depth+1);

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

				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]);
						if(Move.capture(moves[i]) == 0)
						{
							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 = rememberMoveMemoryIndex;

						Mediocre.repTable.removeRep(board.zobristKey);
						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;
					}
				}
			}// End for loop
			
			generationState++; // We have gone through all the generated moves from the last state so move to the next
		}// End while loop
	
		if(!atleastOneLegal)
		{
			moveMemoryIndex = rememberMoveMemoryIndex;
			Mediocre.repTable.removeRep(board.zobristKey);
			return mateCheck(board, depth); // No legal moves, check for mate/stalemate
		}
		
		moveMemoryIndex = rememberMoveMemoryIndex;
		
		
		
		if(!stopSearch)
		{
			Mediocre.transpositionTable.record(board.zobristKey, ply, eval_type, bestEval, bestMove);
		}
		
		
		Mediocre.repTable.removeRep(board.zobristKey);
		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,false); // 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.gen_caps(moves, firstMoveIndex); // Get captures

		
		// Go through the moves and assign the ordering values according to see
		for(int i = firstMoveIndex; i < moveMemoryIndex; i++)
		{
				movesSort[i] = See.see(board, moves[i]);
		}
		
		int losingCapturesIndexStart = sortCaps(firstMoveIndex, moveMemoryIndex);

		if(losingCapturesIndexStart == -1) losingCapturesIndexStart = moveMemoryIndex;
		
		for(int i = firstMoveIndex; i < losingCapturesIndexStart; i++) // Loop through all the captures
		{
			nodesSearched++;
			board.makeMove(moves[i]); // Make first capture on the board
			
			// Make sure we don't leave the king in check when making this move
			if(board.toMove == BLACK_TO_MOVE && board.isAttacked(board.w_king.pieces[0], BLACK))
			{
				board.unmakeMove(moves[i]);
				continue;
			}
			else if(board.toMove == WHITE_TO_MOVE && board.isAttacked(board.b_king.pieces[0], WHITE))
			{
				board.unmakeMove(moves[i]);
				continue;
			}
			
			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()
	
	/**
	 * Same as sortMoves but includes checking for hash move since it's not automatic at root
	 * 
	 * @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 sortRootMoves(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;
					continue;
				}

				if(Move.capture(moves[i]) != 0)
				{
					int tempSee = See.see(board, moves[i]);
					if(tempSee > 0)
					{
						movesSort[i] = 4000;
						continue;
					}
					else if(tempSee == 0)
					{
						movesSort[i] = 1000;
						continue;
					}
				}
				if(moves[i] == killers.primaryKillers[ply])
				{
					movesSort[i] = 3000;	
					continue;
				}
				else if(moves[i] == killers.secondaryKillers[ply])
				{
					movesSort[i] = 2000;
					continue;
				}

				movesSort[i] += Move.orderingValue(moves[i]) - 31;
				movesSort[i] += historyMoves[Move.fromIndex(moves[i])][Move.toIndex(moves[i])];





			}
			catch(ArrayIndexOutOfBoundsException ex){}

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

	}
	// END sortMoves()

	/**
	 * Used to sort non-captures, simply sorts the moves-array
	 * according to the information in the movesSort-array
	 * 
	 * @param startIndex Where the non-captures begin in the moves array
	 * @param endIndex Where the non-captures end
	 */
	public static void sortNoncaps(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 = moves[j];
					moves[j] = moves[j-1];
					moves[j-1] = temp;
					
					// Switch the sort places
					temp = movesSort[j];
					movesSort[j] = movesSort[j-1];
					movesSort[j-1] = temp;
					
					done = false;
				}
			}
		}
	}
	// END bubbleSortMoves()
	
	/**
	 * Used to sort captures, different from the other sorts since it
	 * returns the index where the captures start having negative ordering
	 * values (i.e. losing captures)
	 * 
	 * @param startIndex Where the captures begin in the moves array
	 * @param endIndex Where the captures end
	 * @return Index where captures start to be losing, or -1 for no losing captures
	 */
	public static int sortCaps(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 = moves[j];
					moves[j] = moves[j-1];
					moves[j-1] = temp;
					
					// Switch the sort places
					temp = movesSort[j];
					movesSort[j] = movesSort[j-1];
					movesSort[j-1] = temp;
					
					done = false;
				}
			}
			
			// Check if we have negative ordering value for the last move
			// If we do we skip sorting the rest of the moves, and return
			// the index where the negative moves start
			if(movesSort[i] < 0)
			{
				return i;
			}
		}
		return -1; // No losing captures
	}
	// END bubbleSortMoves()
	
	/**
	 * 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 depth)
	{
		int king_square;		
		if(board.toMove == WHITE_TO_MOVE) king_square = board.w_king.pieces[0];
		else king_square = board.b_king.pieces[0];

		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))
		{
			board.toMove *= -1; // Switch back side to move	
			return (MATE_VALUE + depth); 
		}
		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.w_king.pieces[0];
		else king_square = board.b_king.pieces[0];
		
		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))
		{
			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()
}
