import java.util.*;

public class Search
{
        private int defaultply;
        private int node = 0;
        private Board myboard;
        private Move bestmove;
        private int val;
        private int score;  // We'll use this to determine if it was a checkmate or stalemate.
                            // Checkmate is infinity. Stalemate is zero.

        
        public Search(int ply) {
            defaultply = ply;
        }
        
        public int getLastScore() {
            return score;
        }

        public Move getMove(Board theboard, boolean whiteTurn) {
            myboard = theboard;
            long before = System.currentTimeMillis();
            bestmove = null;
            score = AlphaBeta(defaultply, Integer.MIN_VALUE + 1, Integer.MAX_VALUE - 1, whiteTurn);
            long difference = System.currentTimeMillis() - before;
            ChessEngine.outWriter.println("Nodes: " + node + ", Seconds: " + difference/1000 + "\n" +
                                          (int)(node/((double)difference/1000)) + " nodes/second" +
                                        "\nScore: " + score);
            node = 0;

	    return bestmove;
        }

    //this is the main search function, it is recursive in nature. it will exit a line of search at the end of
    //ply or if beta is exceeded(i.e)the enemy can put it in checkmate
        public int AlphaBeta(int depth, int alpha, int beta, boolean whiteTurn) {
	        node++;

                if (depth <= 0) {
                        return myboard.evaluate(whiteTurn);
	        }

                Stack s = new Stack();
                myboard.generateMoves(s, whiteTurn);//this method pushes all legal moves onto the stack at the 
		                                    //current board position
                Collections.sort(s);
                
                if (s.isEmpty()) {
                    //There are no legal moves
                    // We should check to see if we are in check so that we know that this is
                    // not a stalemate instead of a checkmate.
		    int kingr = 0;
		    int kingc = 0;
		    //find king of side under consideration
		    for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
			    if(myboard.getPiece(i,j) != null)
			    if(myboard.getPiece(i,j).type() == ChessPiece.TYPE_KING && myboard.getPiece(i,j).isWhite() == whiteTurn)

				{
				    kingr = i;
				    kingc = j;
				}
			}
		    }
                    if (myboard.attacked(whiteTurn,kingr,kingc)) { // This is a checkmate for the other side.
                        return -ChessPiece.VALUE_KING;
                    } else { // This is a stalemate
                        return 0;
                    }
                }

                while (!s.isEmpty()) {

		    Move curmove = (Move)s.pop();

		    myboard.movePiece(curmove);
		    val = -AlphaBeta(depth - 1, -beta, -alpha, !whiteTurn);
		    myboard.unmakeMove();

		    if (val >= beta)
			return beta;

		    if (val > alpha) {
			alpha = val;
			// If this is the root ply then this is the best move so far.
			if(depth == defaultply) {
			    bestmove = curmove;
			}
		    }
                }
                return alpha;
        }
}