StackOverFlow Error when implementing MiniMax Algorithm on Java Connect 4 game

nethsrk 0
Viewed 41

I am trying to create connect 4 game using JavaFX. When I try to implement the minimax algorithm, it gives giving stack overflow error.

enter image description here

When it comes the AI's turn it is invoking the movePiece(-1) . There are 6 Cols, and 5 Rows in the game. It is working fine after I send a random number between 0 - 5 fine, but the issue is on the minimax function. Here is the code I am using on AI Player's class.

package lk.ijse.dep.service;
public class AiPlayer extends Player {

    private final Board board;

    public AiPlayer(Board board) {
        this.board = board;
    }

    @Override
    public void movePiece(int col) {
        col = minimax(5, true);

        board.updateMove(col, Piece.GREEN); //Placing the piece on the selected col.
        board.getBoardUI().update(col, false);

        Winner winner = board.findWinner();
        if (winner.getWinningPiece() == Piece.GREEN) {
            board.getBoardUI().notifyWinner(winner);
        }

        if (!board.existLegalMove()) {
            board.getBoardUI().notifyWinner(new Winner(Piece.EMPTY));
        }
    }

    private int minimax(int depth, boolean maximizingPlayer) {
        if(depth == 0 || !board.existLegalMove()) return 0;

        if (maximizingPlayer) {
            int maxEval = (int) Double.NEGATIVE_INFINITY;
            for (int i = 0; i < this.board.NUM_OF_COLS; i++) {
                System.out.println(i);
                int heuristicVal = minimax(depth + 1, false); //<< Getting StackOverFlow Error
                maxEval = Math.max(heuristicVal, maxEval);
            }
            return maxEval;
        } else {
            int minEval = (int) Double.POSITIVE_INFINITY;
            for (int i = 0; i < this.board.NUM_OF_COLS; i++) {
                System.out.println(i);
                int heuristicVal = minimax(depth + 1, true); //<< Getting StackOverFlow Error
                minEval = Math.min(heuristicVal, minEval);
            }
            return minEval;
        }

    }
}

When the AI's turn came, it is automatically invoking the movePiece(-1); It is a illegal move, so need to modify before sending it to updateMove(int col, boolean isHuman);

Board's existLegalMove function;

public boolean existLegalMove() {
        for (int i = 0; i < NUM_OF_COLS; i++) {
            for (int j = 0; j < NUM_OF_ROWS; j++) {
                if (pieces[i][j].equals(Piece.EMPTY)) {
                    return true;
                }
            }
        }
        return false;
    }
java algorithm
1 Answers

The only condition that might stop the recursive call is

board.existLegalMove()

but you never modify the board before recalling the minimax function, so the recursivity goes as deep as it can till the Stackoverflow.

How to correct the Stackoverflow :

When you call minmax(), you pass depth+1, it should be depth-1.

Correct the algorithm

You need to modify the board before calling the minimax. You will also need to revert it after the call before checking another move. I do not have the implementation of the Board, so you might need to change/create the updateMove and revertMove methods. There are some optimizations that can be done, but I hope this will help you to resolve your issue.

private int estimateHeuristicValue(boolean maximizingPlayer) {
    return 0;// or something more complicated
}

private int minimax(int depth, boolean maximizingPlayer) {
    if (!board.existLegalMove()) return 0;
    if(depth == 0) return estimateHeuristicValue(maximizingPlayer);

    if (maximizingPlayer) {
        int maxEval = (int) Double.NEGATIVE_INFINITY;
        for (int i = 0; i < this.board.NUM_OF_COLS; i++) {
            board.updateMove(i,Piece.GREEN);
            Winner winner = board.findWinner();
            if (winner.getWinningPiece() == Piece.GREEN) {
                maxEval = Integer.MAX_VALUE; // AI is winning, maximal value
            } else {
                //No winner, go deeper
                int heuristicVal = minimax(depth - 1, false); //<< Getting StackOverFlow Error
                maxEval = Math.max(heuristicVal, maxEval);
            }
            board.revertMove(i,Piece.GREEN);
        }
        return maxEval;
    } else {
        int minEval = (int) Double.POSITIVE_INFINITY;
        for (int i = 0; i < this.board.NUM_OF_COLS; i++) {
            board.updateMove(i,Piece.RED);
            Winner winner = board.findWinner();
            if (winner.getWinningPiece() == Piece.RED) {
                minEval = Integer.MIN_VALUE; // AI lost, minimal value
            } else {
                //No winner, go deeper
                int heuristicVal = minimax(depth - 1, true); //<< Getting StackOverFlow Error
                minEval = Math.min(heuristicVal, minEval);
            }
            board.revertMove(i,Piece.RED);
        }
        return minEval;
    }

}
Bastien Aracil0
Related