javaartificial-intelligencealpha-beta-pruningminmax

How to receive position that lead to the highest evaluated branch, when using minmax


Right now I am programming a simple game (Capture the Flag) in Java. For creating my AiBots I decided to use minmax with alpha beta pruning. What is the best way to access the position that lead to the branch with the best evaluation determined by running my function. That position would represent the move the Aibot chooses to do ( which is the branch that leads to my functions return when visualizing in a tree) Based ont his strucutre I try to achieve it:

public int minmax(String[][] position,int depth, int alpha, int beta, boolean maximizingPlayer){
        //TODO recursion ends with game over
        if(depth == 0){
            return AssessGame.assess(position, maximizingPlayer);
        }
        if(maximizingPlayer){
            int maxEval = Integer.MIN_VALUE;
            for(String[][] child: generateChildren(position)){
                int eval = minmax(child, depth -1, alpha,beta,false);
                maxEval = Integer.max(maxEval,eval);
                alpha = Integer.max(alpha,eval);
                if( beta <= alpha){
                    break;
                }
            }
            return maxEval;
        }
        else{
            int minEval = Integer.MAX_VALUE;
            for(String[][] child: generateChildren(position)){
                int eval = minmax(child, depth -1, alpha,beta,true);
                minEval = Integer.min(minEval,eval);
                beta = Integer.min(beta,eval);
                if( beta <= alpha){
                    break;
                }
            }
            return minEval;
        }
    }

I tried creating a Evaluation Class which also saves the childs position but I cant seem to figure out where to return what to get the right position.

public class BestMove {
    public int value;
    public String[][] position;

    public BestMove(int value, String[][] position) {
        this.value = value;
        this.position = position;
    }
}

public BestMove minmax(String[][] position, int depth, int alpha, int beta, boolean maximizingPlayer) {
    // TODO recursion ends with game over
    if (depth == 0) {
        return new BestMove(AssessGame.assess(position, maximizingPlayer), position);
    }

    if (maximizingPlayer) {
        int maxEval = Integer.MIN_VALUE;
        String[][] bestPosition = null;
        for (String[][] child : generateChildren(position)) {
            BestMove move = minmax(child, depth - 1, alpha, beta, false);
            int eval = move.value;
            if (eval > maxEval) {
                maxEval = eval;
                bestPosition = child;
            }
            alpha = Integer.max(alpha, eval);
            if (beta <= alpha) {
                break;
            }
        }
        return new BestMove(maxEval, bestPosition);
    } else {
        int minEval = Integer.MAX_VALUE;
        String[][] bestPosition = null;
        for (String[][] child : generateChildren(position)) {
            BestMove move = minmax(child, depth - 1, alpha, beta, true);
            int eval = move.value;
            if (eval < minEval) {
                minEval = eval;
                bestPosition = child;
            }
            beta = Integer.min(beta, eval);
            if (beta <= alpha) {
                break;
            }
        }
        return new BestMove(minEval, bestPosition);
    }
}

Solution

  • After some experimenting, this is the approach that worked for me:

    public BestMove minmax(String[][] position, int depth, int alpha, int beta,
        boolean maximizingPlayer) {
        if (depth == 0 || noPiecesLeft(position)) {
            return new BestMove(AssessGame.assess(position, teamID, depth), position);
        }
    
        if (maximizingPlayer) {
            int maxEval = Integer.MIN_VALUE;
            String[][] bestPosition = null;
            for (String[][] child : generateChildren(position, true)) {
                BestMove move = minmax(child, depth - 1, alpha, beta, false);
                int eval = move.value;
                if (eval > maxEval) {
                    maxEval = eval;
                    bestPosition = child;
                }
                alpha = Integer.max(alpha, eval);
                if (beta <= alpha) {
                    break;
                }
            }
            return new BestMove(maxEval, bestPosition);
        } else {
            int minEval = Integer.MAX_VALUE;
            String[][] bestPosition = null;
            for (String[][] child : generateChildren(position, false)) {
                BestMove move = minmax(child, depth - 1, alpha, beta, true);
                int eval = move.value;
                if (eval < minEval) {
                    minEval = eval;
                    bestPosition = child;
                }
                beta = Integer.min(beta, eval);
                if (beta <= alpha) {
                    break;
                }
            }
            return new BestMove(minEval, bestPosition);
        }
    }