Minimax issue- connect four.

Question

I'm struggling with a minimax exercise, I'm just trying to make a connect four ai with it. Mine works when only exploring one node deep but I can't figure out why it messes up once it goes deeper.

private int minimax(Gameboard gameBoard, int alpha, int depth, char color) {
    Gameboard gb = new Gameboard(gameBoard);
    int value = 0;
    int bestChoice = 0;
    int bestValue = alpha;
    // determine which use the value is for
    if (gb.computerColor == color) {
        value = 1;
    } else {
        value = -1;
    }
    if (gb.CheckForWinner(gb.lastSpacePlayed)) {
        if(gb.winner == gb.computerColor){
            bestValue = (1000000000 - depth);
        }else{
            bestValue = (-1000000000 - depth);
        }

    }

    // get the bestValue at our maximum recrusion depth
    else if (depth == maxDepth) {
        int moveWeight = (threatLevel(gb, color));
        if (moveWeight != 0) {
            bestValue = value * (moveWeight - depth);
        } else {
            bestValue = moveWeight;
        }
    } else {
        // Generate moves for each col and find the best score from each of
        // the generated moves.
        for (int c = 0; c < 7; c++) {
            Gameboard game = new Gameboard(gb);
            int selectedPlace = game.PlacePiece(c, color);

            // Recursive call the generated game grid and compare the
            // current value to move value
            // If move is higher, make it the new current value.

            if (selectedPlace != -1) {
                char tempColor;
                // change the user for the child node after a piece is played
                if (color == 'Y') {
                    tempColor = 'R';
                } else {
                    tempColor = 'Y';
                }
                // call the function so we can explore to maximum depth
                if (depth < maxDepth) {
                    int v = minimax(new Gameboard(game), -1000000, depth + 1, tempColor);
                    if (v > bestValue) {
                        bestChoice = c;
                        bestValue = v;
                    }
                    System.out.println(v);
                }
            }
        }
    }
    if (depth == 0) {
        if (threatLevel(gb, gb.lastSpacePlayed.getColor()) == 0) {
            return gb.spaces.get(0).get(3).getColor() == gb.playerColor ? 2
                    : 3;
        } else {
            return bestChoice;
        }
    } else {
        return bestValue;
    }

}

I'm starting it off as so return minimax(gameBoard, -1000000, 0, gameBoard.computerColor);

My understanding is just looping over all children and returning a value a maximum value if the nodes are the same as the parent and a minimum value if the nodes aren't. Any direction would be appreciated.

Answer 1

If your approach isn't working you could try to mimic the basic structure of the pseudocode on wiki or here. In java I have:

    /**
     * initialize MiniMax(0, player1) where player1 is computer
     * @param deg depth
     * @param player either MAX or MIN
     * @return int {score,column}
     */
    int[] MiniMax(int deg, char player) {

        // list of possible columns to place a checker
        List<int[]> moves = nextMoves();
        int v;
        char prev;

        if (player==player1) prev = player2;
        else prev = player1;

        // IF depth = 0 OR there is a connect 4 OR the board is full (draw) THEN
        //      return your static evaluation (heuristic)
        // if the current position has a connect 4, return -inf or inf
        // depending on if player is MIN or MAX respectively
        if (checkPos(prev) || (deg == this.deg) || moves.isEmpty())
            return new int[] {eval(),bestMove};

        //MAX
        else if (player==player1) {
            v = -inf;
            for (int[] move : moves) {  // move = {row,column}

                board[move[0]][move[1]] = player1; // make move
                int score = MiniMax(deg+1,player2)[0];
                board[move[0]][move[1]] = ' '; // undo move

                if (score>v) {
                    v = score;
                    bestMove = move[1];
                }

            }
            return new int[] {v,bestMove};
        }

        //MIN
        else {
            v = inf;
            for (int[] move : moves) {  // move = {row,column}

                board[move[0]][move[1]] = player2; // make move
                int score = MiniMax(deg+1,player1)[0];
                board[move[0]][move[1]] = ' '; // undo move

                if (v>score) {
                    v = score;
                    bestMove = move[1];
                }
            }
            return new int[] {v,bestMove};
        }
    }

It could be useful to use a character array or something, rather than a class, to represent the board. The most efficient way though is to represent the board as a long as you can check if there is a connect four using 4 bit shifts. Here's some sloppy java that shows the above stuff working:

import java.util.ArrayList;
import java.util.List;

public class Connect4 {
    static final int WIDTH = 7;
    static final int HEIGHT = 6;
    private static final int inf = 9999999;
    private static final char player1 = 'X';
    private static final char player2 = 'O';
    char[][] board = new char[WIDTH][HEIGHT];
    private int deg;
    int bestMove;


    static char[][] copy(char[][] aArray) {
        char[][] copy = new char[aArray.length][aArray[0].length];
        for (int idy = 0; idy < aArray.length; ++idy) {
            for (int idx = 0; idx < aArray[0].length; ++idx) {
                copy[idy][idx] = aArray[idy][idx];
            }
        }
        return copy;
    }
    void prints() {
        System.out.println();
        for (int i = 0; i < 6; i++) {
            System.out.println("=============================");
            for (int j = 0; j < 7; j++) {
                if (j == (WIDTH - 1)) {
                    if (board[i][j]==' ') {
                        System.out.println("|   |");
                    }
                    else {
                        if(board[i][j]==player1 ) System.out.println("| " +"\u001B[32m"+board[i][j]+"\u001B[0m" + " |");

                        else System.out.println("| " +"\u001B[34m"+board[i][j]+"\u001B[0m" +  " |");
                    }
                }
                else {

                    if (board[i][j]==' ') {
                        System.out.print("|   ");
                    }
                    else {
                        if(board[i][j]==player1 ) System.out.print("| " +"\u001B[32m"+board[i][j]+"\u001B[0m" + " ");

                        else System.out.print("| " +"\u001B[34m"+board[i][j]+"\u001B[0m" + " ");
                    }
                }

            }
        }
        System.out.println("=============================");
    }


    //STATIC EVALUATION
    int eval3(char player) {
        if (checkPos(player)) {
            return inf;
        }

        int count;
        int open;
        int evaluation = 0;

        //evaluation = number of open 3 in rows
        //go through all possible 4in rows and check

        //horz
        for (int i = 0; i < HEIGHT; i++) {
            for (int j = 0; j < 4; j++) {
                count = 0;
                open = 0;
                if (board[i][j]==player) count++;
                else if(board[i][j]==' ') open++;

                if (board[i][j + 1]==player) count++;
                else if(board[i][j + 1]==' ') open++;

                if (board[i][j + 2]==player) count++;
                else if(board[i][j + 2]==' ') open++;

                if (board[i][j + 3]==player) count++;
                else if(board[i][j + 3]==' ') open++;

                if ((count == 3) && (open == 1)) evaluation++;
            }
        }

        //vert
        for (int j = 0; j < WIDTH; j++) {
            for (int i = 0; i < 3; i++) {
                count = 0;
                open = 0;
                if (board[i][j]==player) count++;
                else if (board[i][j]==' ') open++;

                if (board[i + 1][j]==player) count++;
                else if (board[i+1][j]==' ') open++;

                if (board[i + 2][j]==player) count++;
                else if (board[i + 2][j]==' ') open++;

                if (board[i + 3][j]==player) count++;
                else if (board[i + 3][j]==' ') open++;

                if ((count == 3) && (open == 1)) evaluation++;
            }
        }


        // pos slope diag
        for (int j = 0; j < 4; j++) {
            for (int i = 3; i < HEIGHT; i++) {
                count = 0;
                open = 0;
                if (board[i][j]==player) count++;
                else if (board[i][j]==' ') open++;

                if (board[i - 1][j + 1]==player) count++;
                else if (board[i - 1][j + 1]==' ') open++;

                if (board[i - 2][j + 2]==player) count++;
                else if (board[i - 2][j + 2]==' ') open++;

                if (board[i - 3][j + 3]==player) count++;
                else if (board[i - 3][j + 3]==' ') open++;

                if ((count == 3) && (open == 1)) evaluation++;
            }
        }

        // neg slope diag
        for (int j = 0; j < 4; j++) {
            for (int i = 0; i < (3); i++) {
                count = 0;
                open = 0;
                if (board[i][j]==player) count++;
                else if (board[i][j]==' ') open++;

                if (board[i + 1][j + 1]==player) count++;
                else if (board[i + 1][j + 1]==' ') open++;

                if (board[i + 2][j + 2]==player) count++;
                else if (board[i + 2][j + 2]==' ') open++;

                if (board[i + 3][j + 3]==player) count++;
                else if (board[i + 3][j + 3]==' ') open++;

                if ((count == 3) && (open == 1)) evaluation++;

            }
        }
        return evaluation;
    }
    int eval() {return eval3(player1) - eval3(player2);}
    boolean checkPos(char cur) {
        //horz
        for (int i = 0; i < HEIGHT; i++) {
            for (int j = 0; j < 4; j++) {
                if (    board[i][j]==cur &&
                        board[i][j + 1]==cur &&
                        board[i][j + 2]==cur &&
                        board[i][j + 3]==cur) {
                    return true;
                }
            }
        }


        //vert
        for (int j = 0; j < WIDTH; j++) {
            for (int i = 0; i < 3; i++) {
                if (    board[i][j]==cur &&
                        board[i + 1][j]==cur &&
                        board[i + 2][j]==cur &&
                        board[i + 3][j]==cur) {
                    return true;
                }
            }
        }


        // pos slope diag
        for (int j = 0; j < 4; j++) {
            for (int i = 3; i < HEIGHT; i++) {
                if (    board[i][j]==cur &&
                        board[i - 1][j + 1]==cur &&
                        board[i - 2][j + 2]==cur &&
                        board[i - 3][j + 3]==cur) {
                    return true;
                }

            }
        }


        // neg slope diag
        for (int j = 0; j < 4; j++) {
            for (int i = 0; i < 3; i++) {
                if (    board[i][j]==cur &&
                        board[i + 1][j + 1]==cur &&
                        board[i + 2][j + 2]==cur &&
                        board[i + 3][j + 3]==cur) {
                    return true;
                }
            }
        }

        return false;
    }
    List<int[]> nextMoves() {
        List<int[]> result = new ArrayList<>();
        for (int j = 0; j < WIDTH; j++) {
            //if column j isnt full then add
            if (board[0][j]==' ') result.add(new int[] {findY(j),j});
        }
        return result;
    }
    int findY(int col) {
        int i = board.length - 1;
        while (i > -1) {
            if (board[i][col]==' ') break;
            i--;
        }
        return i;
    }


    /**
     * @param deg depth
     * @param player either MAX or MIN
     * @return int {score,column}
     */
    int[] MiniMax(int deg, char player) {

        // list of possible columns to place a checker
        List<int[]> moves = nextMoves();
        int v;
        char prev;

        if (player==player1) prev = player2;
        else prev = player1;

        // IF depth = 0 OR there is a connect 4 OR the board is full (draw) THEN
        //      return your static evaluation (heuristic)
        // if the current position has a connect 4, return -inf or inf
        // depending on if player is MIN or MAX respectively
        if (checkPos(prev) || (deg == this.deg) || moves.isEmpty())
            return new int[] {eval(),bestMove};



        //MAX
        else if (player==player1) {
            v = -inf;
            for (int[] move : moves) {  // move = {row,column}

                board[move[0]][move[1]] = player1; // make move
                int score = MiniMax(deg+1,player2)[0];
                board[move[0]][move[1]] = ' '; // undo move

                if (score>v) {
                    v = score;
                    bestMove = move[1];
                }

            }
            return new int[] {v,bestMove};
        }

        //MIN
        else {
            v = inf;
            for (int[] move : moves) {  // move = {row,column}

                board[move[0]][move[1]] = player2; // make move
                int score = MiniMax(deg+1,player1)[0];
                board[move[0]][move[1]] = ' '; // undo move

                if (v>score) {
                    v = score;
                    bestMove = move[1];
                }

            }
            return new int[] {v,bestMove};
        }

    }

    public static void main(String[] args) {
        Connect4 c = new Connect4();
        c.deg = 5;

        char[][] b = {
                {' ',' ',' ',' ',' ',' ',' '},
                {' ',' ',' ',' ',' ',' ',' '},
                {' ',' ',' ',' ',' ',' ',' '},
                {' ',' ',' ',' ',' ',' ',' '},
                {' ','X','X','X',' ',' ',' '},
                {' ','O','X','X','X',' ',' '}
        };

        c.board = copy(b);
        c.prints();
        System.out.println("best value = " + c.MiniMax(0, player1)[1]);

    }
}

Answer 2

private int minimax(Gameboard gameBoard, int depth, char color) {
    Gameboard gb = new Gameboard(gameBoard);
    int bestChoice = 0;
    int bestValue = 0;

    //If we've won, return highest possible value. If we've lost, return lowest.
    if (gb.CheckForWinner(gb.lastSpacePlayed)) {
        if(gb.winner == color){
            return Integer.MAX_VALUE
        }else{
            return Integer.MIN_VALUE
        }

    }
    //if we hit maximum depth, resort to our heuristic method.
    else if (depth == maxDepth) {
        return threatLevel(gb, color);
    } else {
        // Generate moves for each col and find the best score from each of
        // the generated moves. Keep track of the worst one.
        int worstBestResponse = Integer.MAX_INT
        boolean tie = true;
        for (int c = 0; c < 7; c++) {
            Gameboard game = new Gameboard(gb);
            int selectedPlace = game.PlacePiece(c, color);

            // Recursive call the generated game grid and compare the
            // current value to move value
            // If move is higher, make it the new current value.

            if (selectedPlace != -1) {
                tie = false;
                char tempColor;
                // change the user for the child node after a piece is played
                if (color == 'Y') {
                    tempColor = 'R';
                } else {
                    tempColor = 'Y';
                }
                // call the function so we can explore to maximum depth
                if (depth < maxDepth) {
                    int v = minimax(new Gameboard(game), depth + 1, tempColor);
                    if (v < worstBestResponse) {
                        worstBestResponse = v;
                    }
                }
            }
        }

        if(tie) {
            //if game is a tie, we return 0, to show no favour.
            return 0;
        } else {
            //After determining the value of the opponents best response, we return the negative value of it. That is, what's bad for them is good for us and visa versa.
            return -worstBestResponse;
        }
    }
}

I believe something like this is more what you're looking for. This is assuming that threatLevel is a heuristic method for determining approximately who is winning in a given game.

I've taken out any knowledge the method may have about who it's rooting for. It should only be rooting for whoever "color" is. I've also cleaned up your arbitrarily large integers to show winning and losing. MAX_VALUE and MIN_VALUE is much more elegant.

Anyway, try this out, and call it with depth of 0. Let me know if you have questions