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

bruno.prado · Novembro 2, 2009, 2:10pm

Pessoal… segue meu código abaixo para inteligência artificial para o jogo Connect 4…

Ele está implementado para um minimax (já esta funcionando perfeitamente) só que agora quero acrescentar poda Alpha Beta… só que estou com dificuldades…

Alguém pode olhar o código e me ajudar na implementação?

Fico extremamente grato!

[code]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;
  }
  }
  [/code]

EDIT: Tentei acrescentar dessa forma… mas não funcionou… ferrou todo o algoritmo e só estou perdendo rs…

[code]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;
}[/code]

bruno.prado · Novembro 3, 2009, 9:18am

Por favor, alguem pode me ajudar?

A entrega do trabalho é para sábado…

system · Dezembro 24, 2015, 5:41am

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

Cursos de Mobile

Cursos de Programação

Cursos de Front-end

Cursos de DevOps

Cursos de Design & UX

Cursos de Business

Cursos de Data & BI