import java.util.*;

public class Player {
    public final int PLAYER_A = 1;
    public final int PLAYER_B = 2;
    public final int MAXDEPTH = 2;
    private static int[][] winningStates = getWinningStates();
    private HashMap<Integer[], Integer> visitedStates = new HashMap<Integer[], Integer>();
    private HashMap<GameState, Integer> state2val = new HashMap<GameState, Integer>();
    /**
     * Performs a move
     *
     * @param gameState
     *            the current state of the board
     * @param deadline
     *            time before which we must have returned
     * @return the next state the board is in after our move
     */
    public GameState play(final GameState gameState, final Deadline deadline) {
        Vector<GameState> nextStates = new Vector<GameState>();
        gameState.findPossibleMoves(nextStates);
        long roundStartTime = Deadline.getCpuTime();
        //System.err.println("TIME AT START: " + roundStartTime);
        if (nextStates.size() == 0) {
            // Must play "pass" move if there are no other moves possible.
            return new GameState(gameState, new Move());
        }

        /**
         * Here you should write your algorithms to get the best next move, i.e.
         * the best next state. This skeleton returns a random move instead.
         */
        GameState maxMove = new GameState();
        int max = Integer.MIN_VALUE;
        for (GameState child : nextStates) {
            int value = miniMax(child, 0, Integer.MIN_VALUE, Integer.MAX_VALUE, PLAYER_B, deadline, deadline.timeUntil());
            if (value > max) {
                max = value;
                maxMove = child;
            }
            long timePassed = Deadline.getCpuTime() - roundStartTime;
            //if (timePassed >= 6000000) {System.err.println("\nBREAKING!!\n");break;}
            //if (Deadline.getCpuTime() - roundStartTime >= 590000) break;
        }
        long timePassed = Deadline.getCpuTime() - roundStartTime;
        //System.err.println("time passed: " + timePassed / 1000000);
        //Random random = new Random();
        //return nextStates.elementAt(random.nextInt(nextStates.size()));
        //System.err.println("TIME AT END: " + Deadline.getCpuTime() + " time passed = " + (Deadline.getCpuTime() - roundStartTime));
        return maxMove;
    }

    int heuristic(GameState S, int player) {

        //We check the diagonal
        if (S.isEOG()) {
            if (S.isXWin()) return Integer.MAX_VALUE;
            if (S.isOWin()) return Integer.MIN_VALUE;
            return 0; // if tie
        }

        int score = 0;
        for (int i = 0; i < winningStates.length; i++) {
            int countPlayerA = 0;
            int countPlayerB = 0;
            for (int j = 0; j < GameState.BOARD_SIZE; j++) {
                if (S.at(winningStates[i][j]) == Constants.CELL_X) countPlayerA++;
                if (S.at(winningStates[i][j]) == Constants.CELL_O) countPlayerB++;
            }
            if (countPlayerB == 0) {
                score += countPlayerA == 0 ? 0 : Math.pow(10, countPlayerA);
            }
            if (countPlayerA == 0) {
                score -= countPlayerB == 0 ? 0 : Math.pow(10, countPlayerB);
            }
        }
        return score;
    }

    int miniMax(GameState S, int depth, int alpha, int beta, int player, Deadline deadline, long timeLeft) {
        // state: the current state we are analyzing
        // alpha: the current best value achievable by A
        // beta: the current best value achievable by B
        // player: the current player
        // returns the minimax value of the state
        Vector<GameState> nextStates = new Vector<GameState>();
        S.findPossibleMoves(nextStates);
        //System.err.println("depth: " + depth + ", alpha = " + alpha + ", beta = " + beta + ", children: " + nextStates.size());
        int value = 0;
        long ttot = deadline.timeUntil();
        double keepGoing = ttot - (ttot / (Math.pow(timeLeft, depth))); // this must be less than time left

        if (depth >= MAXDEPTH || nextStates.size() == 0 || keepGoing < deadline.timeUntil()) {
            // terminal state
            //System.err.println("reached terminal state with depth = " + depth + ", possible states: " + nextStates.size());
            value = heuristic(S, player); // gamma
            //return value;
        } else if (player == PLAYER_A) {
            value = Integer.MIN_VALUE;
            for (GameState child : nextStates) {
                value = Math.max(value, miniMax(child, depth + 1, alpha, beta, PLAYER_B, deadline, deadline.timeUntil()));
                alpha = Math.max(alpha, value);
                if (beta <= alpha) break;
            }

        } else if (player == PLAYER_B) {
            value = Integer.MAX_VALUE;
            for (GameState child : nextStates) {
                value = Math.min(value, miniMax(child, depth + 1, alpha, beta, PLAYER_A, deadline, deadline.timeUntil()));
                beta = Math.min(beta, value);
                if (beta <= alpha) break;
            }
        }

        return value;
    }

    static int[][] getWinningStates() {

        ArrayList<int[]> arr = new ArrayList<int[]>();
        int[][] winningStates = new int[76][GameState.BOARD_SIZE];
        int index = 0;
        for (int row = 0; row < GameState.BOARD_SIZE; row++) {
            for (int col = 0; col < GameState.BOARD_SIZE; col++) {
                int[] winLayer = new int[GameState.BOARD_SIZE];
                for (int layer = 0; layer < GameState.BOARD_SIZE; layer++) {
                    winLayer[layer] = GameState.rowColumnLayerToCell(row, col, layer);
                }
                winningStates[index++] = winLayer;

                arr.add(winLayer);

            }
        }

        for (int row = 0; row < GameState.BOARD_SIZE; row++) {
            for (int layer = 0; layer < GameState.BOARD_SIZE; layer++) {
                int[] winCol = new int[GameState.BOARD_SIZE];
                for (int col = 0; col < GameState.BOARD_SIZE; col++) {
                    winCol[col] = GameState.rowColumnLayerToCell(row, col, layer);
                }
                winningStates[index++] = winCol;
                arr.add(winCol);
            }
        }

        for (int layer = 0; layer < GameState.BOARD_SIZE; layer++) {
            for (int col = 0; col < GameState.BOARD_SIZE; col++) {
                int[] winLayer = new int[GameState.BOARD_SIZE];
                for (int row = 0; row < GameState.BOARD_SIZE; row++) {
                    winLayer[row] = GameState.rowColumnLayerToCell(row, col, layer);
                }
                winningStates[index++] = winLayer;

            }
        }

        // Diagonals along the row-dimension

        for (int row = 0; row < GameState.BOARD_SIZE; row++) {
            int[] rowDiag = new int[GameState.BOARD_SIZE];
            //System.err.println("row diagonals: ");
            for (int diag = 0; diag < GameState.BOARD_SIZE; diag++) {
                rowDiag[diag] = GameState.rowColumnLayerToCell(row, diag, diag);
                //System.err.print(rowDiag[diag] + " ");
            }
            //System.err.println();
            winningStates[index++] = rowDiag;
        }

        // Row diagonal opposite

        for (int row = 0; row < GameState.BOARD_SIZE; row++) {
            //int colIdx = GameState.BOARD_SIZE - 1;
            int colIdx = 0;
            //System.err.println("opp row diagonals: ");
            int[] rowDiag = new int[GameState.BOARD_SIZE];
            int layerIdx = GameState.BOARD_SIZE - 1;
            for (int i = 0; i < GameState.BOARD_SIZE; i++) {
                rowDiag[i] = GameState.rowColumnLayerToCell(row, colIdx++, layerIdx--);
                //System.err.print(rowDiag[i] + " ");
            }
            //System.err.println();
            winningStates[index++] = rowDiag;
        }

        // Col diagonal

        for (int col = 0; col < GameState.BOARD_SIZE; col++) {
            int[] colDiag = new int[GameState.BOARD_SIZE];
            //System.err.println("col diagonals: ");
            int rowidx = 0;//GameState.BOARD_SIZE - 1;
            int layeridx = 0;//GameState.BOARD_SIZE - 1;
            for (int i = 0; i < GameState.BOARD_SIZE; i++) {
                colDiag[i] = GameState.rowColumnLayerToCell(rowidx++, col, layeridx++);
                //System.err.print(colDiag[i] + " ");
            }
            //System.err.println();
            winningStates[index++] = colDiag;
        }

        // Col diagonal opposite
        for (int col = 0; col < GameState.BOARD_SIZE; col++) {
            int[] colDiag = new int[GameState.BOARD_SIZE];
            int rowidx = 0;//GameState.BOARD_SIZE - 1;
            int layeridx = GameState.BOARD_SIZE - 1;
            //System.err.println("opp col diagoals: ");
            for (int i = 0; i < GameState.BOARD_SIZE; i++) {
                colDiag[i] = GameState.rowColumnLayerToCell(rowidx++, col, layeridx--);
                //System.err.print(colDiag[i] + " ");
            }
            winningStates[index++] = colDiag;
            //System.err.println();
        }

        // layer diagonal
        for (int layer = 0; layer < GameState.BOARD_SIZE; layer++) {
            int[] layerDiag = new int[GameState.BOARD_SIZE];
            //System.err.println("Layer diagonals:");
            for (int diag = 0; diag < GameState.BOARD_SIZE; diag++) {
                layerDiag[diag] = GameState.rowColumnLayerToCell(diag, diag, layer);
                //System.err.print(layerDiag[diag] + " ");
            }
            //System.err.println();
            winningStates[index++] = layerDiag;
        }

        // Layer diagonal opposite

        for (int layer = 0; layer < GameState.BOARD_SIZE; layer++) {
            int[] layerDiag = new int[GameState.BOARD_SIZE];
            //System.err.println("opp layer diags: ");
            int rowidx = 0;
            int colidx = GameState.BOARD_SIZE - 1;
            for (int i = 0; i < GameState.BOARD_SIZE; i++) {
                layerDiag[i] = GameState.rowColumnLayerToCell(rowidx++, colidx--, layer);
                //System.err.print(layerDiag[i] + " ");
            }
            //System.err.println();
            winningStates[index++] = layerDiag;
        }

        //System.err.println("Before final 4: " + index);
        // Finally the, 4 last solutions

        // Cross diagonal
        int[] crossDiag0 = new int[GameState.BOARD_SIZE];
        for (int diag = 0; diag < GameState.BOARD_SIZE; diag++) {
            crossDiag0[diag] = GameState.rowColumnLayerToCell(diag, diag, diag);
        }

        // cross diagonal opposite
        int[] crossDiag1 = new int[GameState.BOARD_SIZE];
        int idx = 0;
        int col = GameState.BOARD_SIZE - 1;
        int layer = 0;

        for (int row = 0; row < GameState.BOARD_SIZE; row++) {
            crossDiag1[idx++] = GameState.rowColumnLayerToCell(row, col--, layer++);
        }


        col = 0;
        int row = 0;
        layer = GameState.BOARD_SIZE - 1;
        int[] crossDiag2 = new int[GameState.BOARD_SIZE];

        for (int i = 0; i < GameState.BOARD_SIZE; i++) {
            crossDiag2[i] = GameState.rowColumnLayerToCell(row++, col++, layer--);
        }


        col = 0;
        row = GameState.BOARD_SIZE - 1;
        layer = 0;
        int[] crossDiag3 = new int[GameState.BOARD_SIZE];
        for (int i = 0; i < GameState.BOARD_SIZE; i++) {
            crossDiag3[i] = GameState.rowColumnLayerToCell(row--, col++, layer++);
        }
        winningStates[index++] = crossDiag0;
        winningStates[index++] = crossDiag1;
        winningStates[index++] = crossDiag2;
        winningStates[index++] = crossDiag3;

        //for (int i = 0; i < 4; i++) {
            //System.err.println("diag0 = " + crossDiag0[i] + ", diag1: " + crossDiag1[i] + ", diag2: " + crossDiag2[i] + ", diag4: " + crossDiag3[i]);
        //}
        /*
        HashMap<int[], Integer> wins = new HashMap<int[], Integer>();
        for (int i = 0; i < index; i++) {

            if (wins.containsKey(winningStates[i])) {
                System.err.print("double: idx = " + i);
                for (int x = 0; x < 4; x++) {
                    System.err.print(winningStates[i][x] + " ");
                }
                System.err.println();
            } else {
                wins.put(winningStates[i], 1);
            }
        }

        idx = 0;
        System.err.println(" final index: " + index);
        */
        return winningStates;
    }
}