import java.util.Vector;
import java.util.Stack;

/**
 *  class Engine
 *
 *  This class holds static methods for finding the best move
 *  give a certain position.
 *
 *  @author Jonatan Pettersson (zlaire@gmail.com)
 *  Date: 2006-12-26
 */

public class Engine implements Definitions
{
	public static int current_depth;
	public static Vector pv = new Vector();
	public static Vector prevpv = new Vector();
	public static boolean usingPreviousLine;
	public static int nodesSearched;
	public static KillerMoves killers;

	/**
	 *  Calls the alpha beta and returns
	 *  the principal variation
	 *
	 *  @param board The board on which to find the moves
	 *  @return Vector The principal variation
	 */
	public static LineEval search(Board board)
	{
		LineEval finalEval; // Stores the evaluation and principal valuation
		nodesSearched = 0; // Initialize nodes searched
		String stringEval; // Used to output thinking
		long time = System.currentTimeMillis();

		usingPreviousLine = false; // Start with not using a previous line since we don't have one yet

		killers = new KillerMoves();
		
		int alpha = -200000;
		int beta = 200000;
		for(current_depth = 1;;) // Start the iterative deepening loop
		{	
			int eval = alphaBeta(board,current_depth,alpha,beta, pv); // Search with the current depth
			finalEval = new LineEval(pv, eval); // Record the evaluation and principal variation
			usingPreviousLine = true; // We now have a previous line and can use it in our next search

			stringEval = current_depth + " " + eval + " " + (System.currentTimeMillis() - time) + " " + nodesSearched + " ";
			
			// Insert the principal variation into the stringEval
			for(int i = 0; i < finalEval.line.size(); i++)
			{
				stringEval += ((Move)finalEval.line.get(i)).notation() + " ";
			}

			System.out.println(stringEval); // Send the stringEval to the gui


			if(eval <= alpha || eval >= beta)
			{
				alpha = -200000;
				beta = 200000;
				pv = new Vector();
				continue;
			}

			alpha = eval -10; // Get ready for a new search, with a new window
			beta = eval +10;  // The current window equas 1/10 of a pawn
			prevpv = pv; // Remember the last pv, for move ordering in the next search
			pv = new Vector(); // Clear the pv to prepare for a fresh search
			if(System.currentTimeMillis() - time > 2000 || 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()
	
	/**
	 *  class LineEval
	 *
	 *  Holds a line and evaluation number used to return in search
	 */
	public static class LineEval
	{
		public Vector line;
		public int eval;

		public LineEval()
		{
			this.line = new Vector();
			this.eval = 0;
		}

		public LineEval(Vector 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 Move[] primaryKillers; // The index corresponds to the ply the killer move is located in
		public Move[] secondaryKillers;

		public KillerMoves()
		{
			primaryKillers = new Move[100]; // Assuming we never search over 100 plies deep
			secondaryKillers = new Move[100];
		}

		/**
		 *  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(Move move, int ply)
		{
			if(primaryKillers[ply] != null) // If a move already exists at the ply
			{
				if(!primaryKillers[ply].equals(move)) // If the move is new to primaryKillers
				{
					secondaryKillers[ply] = primaryKillers[ply]; // Move the previous primary killer down to secondary
					primaryKillers[ply] = move; // Insert the move into primary killer
				}
			}
			else primaryKillers[ply] = move; // If no move existed in primary killers, add this move

		}
	}
	// END KillerMoves
	

	/**
	 *  The alpha-beta search.
	 *
	 *  @param board The position we're at
	 *  @param ply The current ply we're at
	 *  @param alpha The alpha value
	 *  @param beta The beta value
	 *  @param pv Passing the principal variation through the trees
	 *  @return int Depending on where in the search we are
	 *              it returns alpha, beta (cutoff) or the
	 *              final evaluation
	 */
	public static int alphaBeta(Board board, int ply, int alpha, int beta, Vector pv)
	{
		boolean foundPV = false;
		nodesSearched++; // Add a node searched
		int eval = 0;
		Vector localpv = new Vector(); // Holds this ply's pv
		Vector moves = sortMoves(board.generateMoves(), ply); // Get the moves to search in the right order
				
		if (moves.size() == 0) return mateCheck(board, ply);
		//else if(ply == 0) return Evaluation.evaluate(board); // No quiescent search

		else if(ply <= 0) return quiescentSearch(board, alpha, beta); // Quiescent search

		else // We're not at the wanted depth and continue with the search
		{
			for(int i = 0; i < moves.size(); i++) // Loop through all the moves
			{
				
				int times_repeated = 0;
				board.makeMove((Move)moves.get(i)); // Make the move on the board

				// Repetition detection
				// We check after the first move is played, i.e. first time alphaBeta is called recursively
				// since this is the time the first move has been played on the board and we can
				// check if the position gets repeated.
				if(ply >= current_depth - 2)
				{
					String this_position = board.getShortFEN(); // Get fen for the position
					for(int j = 0; j < Mediocre.history.size(); j++) // Go through the history
					{
						// Repeated twice, remember it
						if(times_repeated == 0 && this_position.equals((String)Mediocre.history.get(j)))
						{
							times_repeated++;
						}
						// Repeated three times (with this move included), the game is drawn
						else if(times_repeated == 1 && this_position.equals((String)Mediocre.history.get(j)))
						{
							times_repeated++;
							eval = -DRAW_VALUE;
							j = Mediocre.history.size();
						}
					}
				}	

				// Call the method again with the updated board, one less ply and
				// swapped alpha and beta. This will return the evaluation after
				// all recursive calls are done.
				if(times_repeated != 2)
				{
					if(foundPV)
					{
						eval = -alphaBeta(board, ply-1, -alpha -1, -alpha, localpv);
						if(eval > alpha && eval < beta)
						{
							localpv = (Vector)localpv.clone();
							eval = -alphaBeta(board, ply-1, -beta, -alpha, localpv);
						}
					}
					else
						eval = -alphaBeta(board, ply-1, -beta, -alpha, localpv);
				}

				board.unmakeMove((Move)moves.get(i)); // Reset the board


				if(eval >= beta) // If the evalatuion is bigger than beta, cutoff
				{
					killers.addKiller((Move)moves.get(i), ply);

					usingPreviousLine = false; // Since we are using aspiration windows we could get a beta cutoff even if we are searching the previous pv, so to make sure set it to false here as well
					return beta;
				}

				if(eval > alpha) // If the evaluation is bigger than alpha (but less than beta) this is our new best move
				{
					foundPV = true;

					usingPreviousLine = false; // We have received our first evaluation based on the previous line and now stop using it

					// Extract the principal variation
					//
					// If there is nothing in the pv so far, add a new move
					if(pv.size() == 0)
						pv.add(moves.get(i));
					else // Else replace the old move
						pv.set(0, moves.get(i)); // Add the move at first index

					// Append the localpv to the pv
					for(int j = 0; j < localpv.size(); j++)
					{
						// Check if we have a spot ready in the pv or if
						// we need to add a new one.
						if(pv.size() -2 < j)
							pv.add(j+1, localpv.get(j));
						else
							pv.set(j+1, localpv.get(j));
					}

					// Remember the new best value
					alpha = eval;


				}
			}

			
		}

		
		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
	 *  @param pv The principal variation
	 *  @return int The expected evaluation
	 */
	private static int quiescentSearch(Board board, int alpha, int beta)
	{


		Vector captures = new Vector();

		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;
		}

		captures = quisSort(board.generateMoves()); // Get the sorted captures

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


			if(eval >= beta) // The move is too good
				return beta;

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

			}
		}			


		return alpha;
	}
	// END quiescentSearch()
	
	/**
	 *  Sorts the moves in the following order:
	 *
	 *  Previous search, captures, pawn moves
	 *
	 *  @param moves Moves to be sorted
	 *  @param ply The depth the search is currently at
	 *  @return Vector The sorted moves
	 */
	private static Vector sortMoves(Vector moves, int ply)
	{
		Vector sortedMoves = new Vector();

		// If we're searching deeper than 1 ply we search the last evaluation first
		if(usingPreviousLine && current_depth - ply < current_depth - 1)
		{
			sortedMoves.add((Move)prevpv.get(current_depth - ply)); // Start with adding the best move from the previous iteration
		}

		Vector primaryKiller = new Vector();
		Vector secondaryKiller = new Vector();

		Vector captures = new Vector();
		Vector rest = new Vector();

		// Go through the rest of the moves and find captures to evaluate them first
		for(int i = 0; i < moves.size(); i++)
		{
			if(sortedMoves.isEmpty() || (!sortedMoves.isEmpty() && !((Move)moves.get(i)).equals((Move)sortedMoves.get(0)))) // Make sure we don't add the move from the principal variation again
			{
				if(killers.primaryKillers[ply] != null && ((Move)moves.get(i)).equals(killers.primaryKillers[ply]))
				{
					primaryKiller.add(moves.get(i));			
				}
				else if(killers.secondaryKillers[ply] != null && ((Move)moves.get(i)).equals(killers.secondaryKillers[ply]))
					secondaryKiller.add((Move)moves.get(i));
				else if(((Move)moves.get(i)).capture != 0) // The move is a capture
					captures.add(moves.get(i));
				else
					rest.add(moves.get(i));
			}
		}

		sortedMoves.addAll(primaryKiller);
		sortedMoves.addAll(secondaryKiller);
		sortedMoves.addAll(captures); // Add the captures
		sortedMoves.addAll(rest); // Add the rest


		return sortedMoves;

	}
	
	/**
	 *  Takes vector with Moves and sort the captures
	 *  into a new vector and returns it
	 *
	 *  @param moves Ordinary moves
	 *  @return Vector Sorted captures
	 */
	public static Vector quisSort(Vector moves)
	{
		Vector sortedCaptures = new Vector();

		Vector PxQ = new Vector(); Vector PxR = new Vector(); Vector PxB = new Vector();
		Vector NxQ = new Vector(); Vector NxR = new Vector(); Vector NxB = new Vector();
		Vector BxQ = new Vector(); Vector BxR = new Vector(); Vector BxB = new Vector();
		Vector RxQ = new Vector(); Vector RxR = new Vector(); Vector RxB = new Vector();
		Vector QxQ = new Vector(); Vector QxR = new Vector(); Vector QxB = new Vector();
		Vector KxQ = new Vector(); Vector KxR = new Vector(); Vector KxB = new Vector();

		Vector PxN = new Vector(); Vector PxP = new Vector();
		Vector NxN = new Vector(); Vector NxP = new Vector();
		Vector BxN = new Vector(); Vector BxP = new Vector();
		Vector RxN = new Vector(); Vector RxP = new Vector();
		Vector QxN = new Vector(); Vector QxP = new Vector();
		Vector KxN = new Vector(); Vector KxP = new Vector();

	        // Go through the moves and add it to the right vector
		for(int i = 0; i < moves.size(); i++)
		{
			if(((Move)moves.get(i)).capture != 0) // If the move is a capture
			{
				switch(Math.abs(((Move)moves.get(i)).capture))
				{
					case W_QUEEN:
					{
						switch(Math.abs(((Move)moves.get(i)).pieceMoving))
						{
							case W_PAWN: PxQ.add(moves.get(i)); break;
							case W_KNIGHT: NxQ.add(moves.get(i)); break;
							case W_BISHOP: BxQ.add(moves.get(i)); break;
							case W_ROOK: RxQ.add(moves.get(i)); break;
							case W_QUEEN: QxQ.add(moves.get(i)); break;
							case W_KING: KxQ.add(moves.get(i)); break;
						}
						break;
					}
					case W_ROOK:
					{
						switch(Math.abs(((Move)moves.get(i)).pieceMoving))
						{
							case W_PAWN: PxR.add(moves.get(i)); break;
							case W_KNIGHT: NxR.add(moves.get(i)); break;
							case W_BISHOP: BxR.add(moves.get(i)); break;
							case W_ROOK: RxR.add(moves.get(i)); break;
							case W_QUEEN: QxR.add(moves.get(i)); break;
							case W_KING: KxR.add(moves.get(i)); break;
						}
						break;
					}
					case W_BISHOP:
					{
						switch(Math.abs(((Move)moves.get(i)).pieceMoving))
						{
							case W_PAWN: PxB.add(moves.get(i)); break;
							case W_KNIGHT: NxB.add(moves.get(i)); break;
							case W_BISHOP: BxB.add(moves.get(i)); break;
							case W_ROOK: RxB.add(moves.get(i)); break;
							case W_QUEEN: QxB.add(moves.get(i)); break;
							case W_KING: KxB.add(moves.get(i)); break;
						}
						break;
					}
					case W_KNIGHT:
					{
						switch(Math.abs(((Move)moves.get(i)).pieceMoving))
						{
							case W_PAWN: PxN.add(moves.get(i)); break;
							case W_KNIGHT: NxN.add(moves.get(i)); break;
							case W_BISHOP: BxN.add(moves.get(i)); break;
							case W_ROOK: RxN.add(moves.get(i)); break;
							case W_QUEEN: QxN.add(moves.get(i)); break;
							case W_KING: KxN.add(moves.get(i)); break;
						}
						break;
					}
					case W_PAWN:
					{
						switch(Math.abs(((Move)moves.get(i)).pieceMoving))
						{
							case W_PAWN: PxP.add(moves.get(i)); break;
							case W_KNIGHT: NxP.add(moves.get(i)); break;
							case W_BISHOP: BxP.add(moves.get(i)); break;
							case W_ROOK: RxP.add(moves.get(i)); break;
							case W_QUEEN: QxP.add(moves.get(i)); break;
							case W_KING: KxP.add(moves.get(i)); break;
						}
						break;
					}					
				}
			}


		}

		sortedCaptures.addAll(PxQ);
		sortedCaptures.addAll(NxQ);
		sortedCaptures.addAll(BxQ);
		sortedCaptures.addAll(RxQ);
		sortedCaptures.addAll(QxQ);
		sortedCaptures.addAll(KxQ);

		sortedCaptures.addAll(PxR);
		sortedCaptures.addAll(NxR);
		sortedCaptures.addAll(BxR);
		sortedCaptures.addAll(RxR);
		sortedCaptures.addAll(QxR);
		sortedCaptures.addAll(KxR);

		sortedCaptures.addAll(PxB);
		sortedCaptures.addAll(NxB);
		sortedCaptures.addAll(BxB);
		sortedCaptures.addAll(RxB);
		sortedCaptures.addAll(QxB);
		sortedCaptures.addAll(KxB);

		sortedCaptures.addAll(PxN);
		sortedCaptures.addAll(NxN);
		sortedCaptures.addAll(BxN);
		sortedCaptures.addAll(RxN);
		sortedCaptures.addAll(QxN);
		sortedCaptures.addAll(KxN);

		sortedCaptures.addAll(PxP);
		sortedCaptures.addAll(NxP);
		sortedCaptures.addAll(BxP);
		sortedCaptures.addAll(RxP);
		sortedCaptures.addAll(QxP);
		sortedCaptures.addAll(KxP);

		return sortedCaptures;
	}
	// END quisSort()



	
	/**
	 *  Takes a board and checks for mate/stalemate
	 *
	 *  @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)
	{

		// Start with finding the king
		int king_square = -1;		
		for(int index = 0; index < 120; index++)
		{
			if((index & 0x88) == 0)
			{
				if(board.boardArray[index]*board.toMove == W_KING)
				{
					king_square = index; // Remember the king's index
					index = 120; // End the loop
				}
			}
			else index += 7;
		}

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