• Advertisement
Sign in to follow this  

Connect 4 - MiniMax (Alpha Beta) - HELP

This topic is 3034 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi! This is my code to AI of Connect 4 game. I wrote a minimax (it´s working very well) but i have to implement a Alpha Beta pruning... and i need help. Can you see the code and help me? Thanks for the help, and sorry by the poor english (I´m Brazilian and don't talk very well)...
package Jogadores;   
  
import java.util.*;   
  
public class JogadorBEst implements Jogador {   
  
    private static int recurDepth = 0;   
    private static final int MAX_RECURDEPTH = 7;   
    private static int WIDTH, HEIGHT;   
    private int[][] board;   
    private int[] columnHeight;   
    private int me;   
  
    public JogadorBEst() {   
    }   
  
    public int jogada(int[][] tabuleiro, int corDaMinhaBola) {   
        getBoardLength(tabuleiro);   
        getColumnHeight(tabuleiro);   
  
        this.board = copyBoard(tabuleiro);   
        this.me = corDaMinhaBola;   
  
        int action = 0;   
        int value = 0;   
  
        Vector moves = new Vector();   
  
        moves.removeAllElements();   
        int prevValue = -MAX_RECURDEPTH - 1;   
  
        for (int col = 0; col < WIDTH; col++) {   
            if (columnHeight[col] >= HEIGHT) {   
                continue;   
            }   
  
            value = minimax(this.me, col);   
  
            if (value > prevValue) {   
                moves.removeAllElements();   
                prevValue = value;   
            }   
  
            if (value == prevValue) {   
                moves.add(new Integer(col));   
            }   
        }   
  
        if (moves.size() > 0) {   
            Collections.shuffle(moves);   
            action = ((Integer) moves.get(0)).intValue();   
        }   
  
        return action;   
    }   
  
    private void getBoardLength(int[][] board) {   
        WIDTH = board.length;   
        HEIGHT = board[0].length;   
    }   
  
    private void getColumnHeight(int[][] board) {   
        columnHeight = new int[WIDTH];   
  
        int aux = 0;   
        for (int col = 0; col < WIDTH; col++) {   
            for (int row = 0; row < HEIGHT; row++) {   
                if (board[row][col] == 0) {   
                    aux++;   
                }   
            }   
            columnHeight[col] = HEIGHT - aux;   
            aux = 0;   
        }   
    }   
  
    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++) {   
                copia[col][aux] = board[row][col];   
            }   
            aux++;   
        }   
        return copia;   
    }   
  
    int minimax(int player, int column) {   
  
        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) {   
            value = MAX_RECURDEPTH + 1;   
  
            for (int col = 0; col < WIDTH; col++) {   
  
                if (columnHeight[col] >= HEIGHT) {   
                    continue;   
                }   
                int v = minimax(3 - player, col);   
  
                if (value == (MAX_RECURDEPTH + 1)) {   
                    value = v;   
                } else if (player == this.me) {   
                    if (value > v) {   
                        value = v;   
                    }   
                } else if (v > value) {   
                    value = v;   
                }   
            }   
        }   
  
        recurDepth--;   
        columnHeight[column]--;   
        this.board[column][columnHeight[column]] = 0;   
  
        return value;   
    }   
  
    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++;   
            }   
        }   
        // Ninguem está ganhando   
        return 0;   
    }   
  
    public String getNome() {   
        return "Jogador BE";   
    }   
  
    public String printTabuleiro() {   
        String resultado = "";   
        for (int i = 0; i < 7; i++) {   
            for (int j = 0; j < 7; j++) {   
                resultado = resultado + " | " + this.board[j];   
            }   
            resultado = resultado + " | " + "\n";   
        }   
        return resultado;   
    }   
}  
I have tried this:
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;   
    }  
But still no working...

Share this post


Link to post
Share on other sites
Advertisement
What seems to be wrong?

EDIT: Actually, I see what's wrong already. You are implementing minimax without the negamax convention, but you wrote the beta-cut condition using it.

I would recommend that you implement negamax first and then add alpha-beta pruning.

O seu inglês não é perfeito, mas da pra entender.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement