Jump to content
  • Advertisement
Sign in to follow this  

Connect 4 - MiniMax (Alpha Beta) - HELP

This topic is 3122 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
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!