import java.util.*;

public class Player {
    int mainPlayer;
    int maxDepth = -1;

    public GameState play(final GameState pState, final Deadline pDue) {
        Vector<GameState> lNextStates = new Vector<GameState>();
        pState.findPossibleMoves(lNextStates);

        mainPlayer = pState.getNextPlayer();

        if (lNextStates.size() == 0)
            return new GameState(pState, new Move());

        if (lNextStates.size() == 1)
            return lNextStates.elementAt(0);

        int bestIndex = 0;
        for (int depth = 1; depth < 11; depth++) {
            this.maxDepth = depth;
            int score = Integer.MIN_VALUE;
            int index = 0;

            for (int i = 0; i < lNextStates.size(); i++) {
                int tempScore = alphaBeta(lNextStates.elementAt(i), 0, Integer.MIN_VALUE, Integer.MAX_VALUE, 2, pDue);
                if (tempScore == -9999) {
                    return lNextStates.elementAt(bestIndex);
                }

                if (tempScore > score) {
                    score = tempScore;
                    index = i;
                }
            }
            bestIndex = index;
        }

        return lNextStates.elementAt(bestIndex);
    }

    public int eval(GameState gameState, int depth) {
        int redValue = 0;
        int whiteValue = 0;

        for (int cell = 0; cell < GameState.NUMBER_OF_SQUARES; cell++) {
            int row = GameState.cellToRow(cell);
            int col = GameState.cellToCol(cell);
            int cellValue = gameState.get(row, col);

            if (cellValue == Constants.CELL_RED) {
                redValue += 1;
            } else if (cellValue == Constants.CELL_RED + Constants.CELL_KING) {
                redValue += 4;
            } else if (cellValue == Constants.CELL_WHITE) {
                whiteValue += 1;
            } else if (cellValue == Constants.CELL_WHITE + Constants.CELL_KING) {
                whiteValue += 4;
            }
        }

        if (gameState.isRedWin()) {
            redValue += 40 - depth;
        }
        if (gameState.isWhiteWin()) {
            whiteValue += 40 - depth;
        }

        int extra = 0;
        if (gameState.isDraw()) {
            extra = 15 - depth;
        }

        int value;

        if (mainPlayer == 1) {
            value = redValue - whiteValue;
        } else {
            value = whiteValue - redValue;
        }
        return value + extra;
    }

    public int alphaBeta(GameState gameState, int depth, int alpha, int beta, int player, Deadline pDue) {
        if (pDue.timeUntil() < 100000000 / 10) {
            return -9999;
        }

        Vector<GameState> nextStates = new Vector<GameState>();
        gameState.findPossibleMoves(nextStates);

        int value;
        if (depth == maxDepth || nextStates.size() == 0) {
            value = eval(gameState, depth);
            return value;
        }

        else if (player == 1) {
            value = Integer.MIN_VALUE;
            for (GameState nextState : nextStates) {
                value = Math.max(value, alphaBeta(nextState, depth + 1, alpha, beta, 2, pDue));
                alpha = Math.max(alpha, value);
                if (beta <= alpha) {
                    break;
                }
            }
        }

        else {
            value = Integer.MAX_VALUE;
            for (GameState nextState : nextStates) {
                value = Math.min(value, alphaBeta(nextState, depth + 1, alpha, beta, 1, pDue));
                beta = Math.min(beta, value);
                if (beta <= alpha) {
                    break;
                }
            }
        }

        if (pDue.timeUntil() < 100000000 / 10) {
            return -9999;
        }

        return value;
    }

}