Connect 4 AI - Ajuda com implementação Alpha Beta

package Jogadores;

import java.util.*;

/**
 * Inteligência Artificial para um jogador de Connect 4.
 *
 * @author Bruno Prado e Edgar Cintho
 */
public class JogadorBEst implements Jogador {

    /**
     * Profundidade atual da árvore.
     */
    private static int recurDepth = 0;
    /**
     * Profundidade máxima que o algorítmo irá percorrer a árvore.
     */
    private static final int MAX_RECURDEPTH = 7;
    /**
     * Largura e Altura do tabuleiro.
     */
    private static int WIDTH, HEIGHT;
    /**
     * Tabuleiro do jogo.
     */
    private int[][] board;
    /**
     * Armazena a quantidade de peças que uma coluna já possui.
     */
    private int[] columnHeight;
    /**
     * Armazena a cor da minha peça.
     */
    private int me;

    /**
     * Construtor vazio chamado pelo gerenciador da competição.
     */
    public JogadorBEst() {
    }

    /**
     * Método chamado pelo gerenciador da competição.
     *
     * Nele é inicializado alguns trechos principais necessários para a busca da melhor jogada
     * e é, também, chamado o método MiniMax que irá realizar a busca.
     *
     * @param tabuleiro Tabuleiro do jogo no momento atual.
     * @param corDaMinhaBola Cor da minha peça
     * @return Coluna que deverá ser jogada a minha peça
     */
    public int jogada(int[][] tabuleiro, int corDaMinhaBola) {
        //Armazena nas variáveis globais qual o tamanho do tabuleiro (Largura e Altura)
        getBoardLength(tabuleiro);
        //Inicializa o vetor com a quantidade de peças que cada coluna já possui no momento.
        getColumnHeight(tabuleiro);

        /**
         * Armazena o tabuleiro de jogo, realizando uma cópia do tabuleiro original.
         * Isto evita que os cálculos alterem o tabuleiro original durante a execução da busca.
         * Além de auxiliar o algoritmo de minimax na colocação de peças com apenas um valor (o da coluna),
         * sem que este precise verificar qual linha irá utilizar, por este fato que o tabuleiro é rotacionado.
         */
        this.board = copyBoard(tabuleiro);
        //Armazena a cor da minha peça
        this.me = corDaMinhaBola;

        //Variável que irá armazenar a coluna que irei jogar na próxima rodada.
        int action = 0;

        //Variável que armazena o valor da melhor jogada.
        int value = 0;

        //Vetor com os movimentos encontrados.
        //Utilizado caso mais de um movimento possua o mesmo valor, assim iremos
        //embaralhar o vetor e sortear um dos movimentos.
        Vector moves = new Vector();

        //Inicializa um valor mínimo que será utilizado para armazenar os valores
        //encontrados, e comperá-los com o melhor valor já encontrado.
        int prevValue = -MAX_RECURDEPTH - 1;

        //Realiza uma busca para cada uma das sete possibilidades de jogo.
        for (int col = 0; col < WIDTH; col++) {
            //Verifica se nesta coluna pode ser colocada uma peça ou se ela já esta cheia.
            if (columnHeight[col] >= HEIGHT) {
                continue; //Caso esteja cheia, ignora a coluna e continua.
            }

            //Verifica o valor deste movimento, jogando a peça nesta coluna.
            value = minimax(this.me, col);

            //Se o valor encontrado for maior que o valor anterior.
            if (value > prevValue) {
                //Remove todos os elementos da lista de movimentos iguais.
                moves.removeAllElements();
                //E armzena este valor atual.
                prevValue = value;
            }

            //Se o valor encontrado for igual ao valor anterior.
            if (value == prevValue) {
                //Então armazena na lista mais um movimento com valor igual.
                moves.add(new Integer(col));
            }
        }

        //Verifica a quantidade de movimentos encontrados.
        //Isto evita, em caso do algoritmo não encontrar um valor de destaque,
        //que o jogo fique sempre repetitivo.
        if (moves.size() > 0) {
            //Embaralha os movimentos encontrados.
            Collections.shuffle(moves);
            //Pega o primeiro da lista, sortenado entre os valores armazenados.
            action = ((Integer) moves.get(0)).intValue();
        }

        //Retorna a coluna escolhida.
        return action;
    }

    /**
     * Armazena a Largura e a Altura do tabuleiro.
     *
     * @param board Tabuleiro a ser analizado.
     */
    private void getBoardLength(int[][] board) {
        WIDTH = board.length;
        HEIGHT = board[0].length;
    }

    /**
     * Armazena a quantidade de peças que uma coluna já possui.
     *
     * @param board Tabuleiro a ser analizado.
     */
    private void getColumnHeight(int[][] board) {
        //Inicializa o vetor de quantidade de peças por coluna com o tamanho correto.
        columnHeight = new int[WIDTH];

        //Analiza o mapa e armazena a quantidade correta.
        int aux = 0;
        for (int col = 0; col < WIDTH; col++) {
            for (int row = 0; row < HEIGHT; row++) {
                //Contabiliza os espaços em branco de cada coluna.
                if (board[row][col] == 0) {
                    aux++;
                }
            }
            //Pega a altura total e subtrai com a quantidade de espaços em branco encontrados
            //na coluna.
            columnHeight[col] = HEIGHT - aux;
            aux = 0;
        }
    }

    /**
     * Copia o tabuleiro realizando uma rotação no mesmo para a direita.
     *
     * Isto é feito pois facilida o algoritmo de minimax na construção dos sucessores de um
     * estado, sendo que este apenas utiliza o valor da coluna, sem precisar buscar pelo
     * valor da linha, evitando cálculos desnecessários e diminuindo o tempo de execução do
     * mesmo.
     *
     * @param board Tabuleiro a ser copiado e rotacionado.
     * @return A cópia do tabuleiro.
     */
    private int[][] copyBoard(int[][] board) {
        int[][] copia = new int[WIDTH][HEIGHT];

        int aux = 0;
        for (int row = WIDTH - 1; row >= 0; row--) {
            for (int col = 0; col < HEIGHT; col++) {
                //Rotaciona o tabuleiro para a direita.
                copia[col][aux] = board[row][col];
            }
            aux++;
        }
        return copia;
    }

    /**
     * Método MiniMax implementado de forma recursiva (evitando a criação de dois métodos
     * Max e Min, e o gasto de tempo na criação de sucessores antes do tempo necessário).
     *
     * Ele sempre retorna o valor máximo para o meu jogador e o valor mínimo para o
     * meu oponente.
     *
     * @param player Número do jogador a ser utilizado na jogada atual.
     * @param column Coluna a ser jogada.
     * @return Valor desta jogada.
     */
    int minimax(int player, int column) {
        //Verifica se nesta coluna é possível colocar uma peça
        if (columnHeight[column] >= HEIGHT) {
            //Retorna valor 0 caso não seja possível (Indica que é uma folha e este movimento tem valor nulo).
            return 0;
        }

        //Inicializa a variável que armazenará o valor do movimento.
        //Ele irá depender do valor de seus filhos.
        int value = 0;

        /**
         * Trecho no qual iremos simular a movimentação.
         */
        recurDepth++; //Aumenta a profuncidade atual.
        this.board[column][columnHeight[column]] = player; //Coloca o jogador.
        columnHeight[column]++; //Aumenta a quantidade de peças que tem na coluna.
        /**
         * Movimentação Simulada.
         */

        //Verifica se neste estado simulado houve uma vitória de um dos jogadores.
        int victory = fourInARow();
        //Se for o meu jogador define um valor máximo ao movimento subtraindo à profundidade atual.
        //(Isto irá fazer com que meu algorítimo sempre procure pela vitória mais rápida).
        //Senão, define um valor mínimo para o movimento somando à profundidade atual.
        //(Isto irá fazer com que meu algorítimo evite movimentos que torne a vitória do oponente
        //mais próxima).
        if (victory == this.me) {
            value = MAX_RECURDEPTH + 1 - recurDepth;
        } else if (victory == 3 - this.me) {
            value = -MAX_RECURDEPTH - 1 + recurDepth;
        }

        //Irá prosseguir na árvore se a profundidade ainda não atingiu a profundidade máxima definida ou
        //se o valor continua igual a zero, ou seja, nenhum jogador está vencendo neste estado.
        //(Isto realiza uma pequena poda, pois não precisa continuar a busca nestes casos).
        if (recurDepth < MAX_RECURDEPTH && value == 0) {
            //Define um valor alto como padrão para o estado.
            value = MAX_RECURDEPTH + 1;

            //Realiza o mesmo procedimento para os filhos deste estado.
            for (int col = 0; col < WIDTH; col++) {
                //Verifica se é possível colocar uma peça nesta coluna.
                //Isso verifica se nesta determinada coluna ele possui um filho ou não.
                if (columnHeight[col] >= HEIGHT) {
                    continue; //Caso não seja possível, simplesmente continua na busca de outros filhos.
                }

                //Chama o método novamente para este filho passando o próximo jogador e a coluna definida.
                //E armazena o valor encontrado referente a uma relação completa de todos seus filhos, netos.....
                int sucValue = minimax(3 - player, col);

                /* Após a análise de todos os filhos iremos verificar o valor de cada um até que
                 * chegue no primeiro nó */

                //Se for a folha, ou seja, nenhum valor foi definido ainda (ele está com o valor padrão).
                if (value == (MAX_RECURDEPTH + 1)) {
                    value = sucValue; //Então define o valor atual como o valor encontrado
                } else if (player == this.me) { //Caso o jogador atual deste estado seja o meu.
                    if (value > sucValue) { //Se o valor atualmente armazenado for maior que o valor dos meus filhos.
                        //Atualiza este valor pois este tem uma relação direta com o valor dos filhos
                        //Ja que o jogo continua, e o valor dos filhos é relevante.
                        value = sucValue;
                    }
                } else if (sucValue > value) { //Caso seja meu oponente e o valor dos filhos for maior que o valor atualmente armazenado
                    //Então modifica atualiza este valor pois como é meu oponente e os filhos tem um valor
                    //alto referente ao meu jogador, então este movimento é mais valioso para mim, portanto
                    //eu maximizo este valor para minimizar as chances dele.
                    value = sucValue;
                }
            }
        }

        /**
         * Trecho no qual iremos remover a simulação da movimentação.
         * Iremos voltar na árvore.
         */
        recurDepth--; //Diminui a profundidade atual
        columnHeight[column]--; //Diminui o valor de peças na coluna
        this.board[column][columnHeight[column]] = 0; //Remove a peça colocada.

        //Retorna o valor total deste movimento. (Calculado juntamente com o valor de todos seus filhos).
        return value;
    }

    /**
     * Verifica se algum dos jogadores vence o jogo neste estado atual.
     *
     * @return O número do jogador que vence no estado atual.
     */
    int fourInARow() {
        int num, player;

        for (int y = 0; y < HEIGHT; y++) {
            num = 0;
            player = 0;
            for (int x = 0; x < WIDTH; x++) {
                if (this.board[x][y] == player) {
                    num++;
                } else {
                    num = 1;
                    player = this.board[x][y];
                }
                if (num == 4 && player > 0) {
                    return player;
                }
            }
        }

        for (int x = 0; x < WIDTH; x++) {
            num = 0;
            player = 0;
            for (int y = 0; y < HEIGHT; y++) {
                if (this.board[x][y] == player) {
                    num++;
                } else {
                    num = 1;
                    player = this.board[x][y];
                }
                if (num == 4 && player > 0) {
                    return player;
                }
            }
        }

        for (int xStart = 0, yStart = 2; xStart < 4;) {
            num = 0;
            player = 0;
            for (int x = xStart, y = yStart; x < WIDTH && y < HEIGHT; x++, y++) {
                if (this.board[x][y] == player) {
                    num++;
                } else {
                    num = 1;
                    player = this.board[x][y];
                }
                if (num == 4 && player > 0) {
                    return player;
                }
            }
            if (yStart == 0) {
                xStart++;
            } else {
                yStart--;
            }
        }

        for (int xStart = 0, yStart = 3; xStart < 4;) {
            num = 0;
            player = 0;
            for (int x = xStart, y = yStart; x < WIDTH && y >= 0; x++, y--) {
                if (this.board[x][y] == player) {
                    num++;
                } else {
                    num = 1;
                    player = this.board[x][y];
                }
                if (num == 4 && player > 0) {
                    return player;
                }
            }
            if (yStart == HEIGHT - 1) {
                xStart++;
            } else {
                yStart++;
            }
        }

        //Neste estado atual nenhum dos jogadores obtém uma vitória.
        return 0;
    }

    /**
     * Retorna o nome do nosso jogador para o gerenciador da
     * competição.
     *
     * @return O nome do nosso jogador.
     */
    public String getNome() {
        return "Jogador BEst";
    }

    /**
     * Método utilizado para DEBUG, onde imprime o estado atual
     * do tabuleiro.
     *
     * OBS.: Copiado do Algoritmo JogadorMinMax do professor
     * Fabrício.
     *
     * @return String com a representação do tabuleiro.
     */
    public String printTabuleiro() {
        String resultado = "";
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                resultado = resultado + " | " + this.board[i][j];
            }
            resultado = resultado + " | " + "\n";
        }
        return resultado;
    }
}

int minimax(int player, int column, int alpha, int beta) {

        if (columnHeight[column] >= HEIGHT) {
            return 0;
        }

        int value = 0;

        recurDepth++;
        this.board[column][columnHeight[column]] = player;
        columnHeight[column]++;

        if (fourInARow() > 0) {
            if (player == this.me) {
                value = MAX_RECURDEPTH + 1 - recurDepth;
            } else {
                value = -MAX_RECURDEPTH - 1 + recurDepth;
            }
        }

        if (recurDepth < MAX_RECURDEPTH && value == 0) {
            if (player == this.me) {
                value = alpha;
            } else {
                value = beta;
            }

            for (int col = 0; col < WIDTH; col++) {

                if (columnHeight[col] >= HEIGHT) {
                    continue;
                }

                if (player == this.me) {
                    value = Math.max(value, minimax(3 - player, col, alpha, beta));
                    alpha = value;

                } else {
                    value = Math.min(value, minimax(3 - player, col, alpha, beta));
                    beta = value;
                }

                if (alpha >= beta) {
                    recurDepth--;
                    columnHeight[column]--;
                    this.board[column][columnHeight[column]] = 0;
                    return value;
                }
            }
        }

        recurDepth--;
        columnHeight[column]--;
        this.board[column][columnHeight[column]] = 0;

        return value;
    }