CODEWITHSUNDEEP
javaminimax
kolijo20
kolijo20

Reputation: 53

Make Minimax return best move instead of score resulted from best move

From all the examples I have seen, minimax algorithm will return an int value that represents that best score or board state that will result from the best move. How can I return the best move associated with this score? Thank you

private Integer minimax(Board board, Integer depth, Color current, Boolean maximizingPlayer, Integer maxPlayerBestVal, Integer minPlayerBestVal) {
    Integer bestValue;
    if (0 == depth)
        return ((current == selfColor) ? 1 : -1) * this.evaluateBoard(board, current);

    Integer val;
    if (maximizingPlayer) {
        bestValue = -INF;
        for (Move m : board.getPossibleMoves(current)) {
            board.apply(m);
            val = minimax(board, depth - 1, Boolean.FALSE, 
                      minPlayerBestVal, maxPlayerBestVal); // swap here 
            bestValue = Math.max(bestValue, val);
            board.revert(m);
            if (bestValue >= minPlayerBestVal) // too good for the minPlayer
                return bestValue;              // so cut here (pruning)
            }
        return bestValue;
    } else {
        [...] min player
    }
}

the evaluate function

private Integer evaluateBoard(Board board, Color player) {
    return board.pawns(player) - board.pawns(player.other());
}

Upvotes: 4

Views: 2191

Answers (2)

average Joe
average Joe

Reputation: 43

One solution is to return an object that stores both best move and best score. Another one is to have a search just for the root that calls the other search function but returns the best move. If the move is in form of an integer you can check if you are on the root and then return the move instead of the score. For example in chess programming usually the moves are integers that store information like which piece the move contains, if the move is a capture.... This is done by bitwise operations. The last solution is not fitted for all problems.

Upvotes: 0

ggorlen
ggorlen

Reputation: 57394

One strategy is to store the best move using a class-scoped instance variable (another approach could be to return a pair of values, the value and the associated move). Set this best move variable whenever you find yourself at the top-level recursive call depth with a new better move (at the initial depth, we're checking every possible move and picking the one that ultimately leads to the node with the best evaluation).

Since we only want our best move to be something reachable from the origin state, we can either keep track of depth and only set the best move if at the first recursive call, or set it whenever we find a best move in a child (it'll be overwritten when that new best returns to the caller, so we'll ultimately get one of the available moves from the origin).

Note that you may never reach depth 0 if paths from the starting board encounter only terminal states before then. For example, the exploration depth might be 8 but all pawns must be captured and the game ends within the next 2 moves, so calls to board.getPossibleMoves() return an empty array. This would leave the best move unset. Adding a check for something like isTerminal(board) would handle this scenario.

I notice that minPlayerBestVal and maxPlayerBestVal (the alpha-beta pruning bounds) don't appear to be updated in the provided implementation. Your recursive call is missing the Color current parameter as well.

There's no need to use the boxed versions of primitive datatypes; use int and boolean.

Lastly, without knowing the game you're programming for (I imagine something like pawns-only chess), the heuristic you've provided for evaluation is likely incomplete and might need to account for positions where no captures occur in the next depth moves (if the game is trivial enough, like hexapawn, that a full search is possible, skip depth-limiting entirely).

Here's an example of the above points. Likely, you'll need to adapt this a bit since I don't have your supporting classes:

private Move bestMove;

public Move getBestMove(Board board) {
    minimax(board, 42, selfColor, true, -INF, INF);
    return bestMove;
}

private int minimax(Board board, int depth, Color current, 
                    boolean maximizing, int alpha, int beta) {
    if (depth == 0/* || isTerminal(board)*/) {
        return ((current == selfColor) ? 1 : -1) * 
                   this.evaluateBoard(board, current);
    }
    else if (maximizing) {
        int best = -INF;

        for (Move m : board.getPossibleMoves(current)) {
            board.apply(m);
            int childVal = minimax(board, depth - 1, current, 
                                   false, alpha, beta);
            board.revert(m);

            if (childVal > best) {
                best = childVal;
                alpha = Math.max(alpha, best);
                this.bestMove = m;

                if (alpha >= beta) {
                    break;
                }
            }
        }

        return best;
    }

    int best = INF;

    for (Move m : board.getPossibleMoves(current)) {
        board.apply(m);
        best = Math.min(best, minimax(board, depth - 1, current, 
                                      true, alpha, beta));
        board.revert(m);
        beta = Math.min(beta, best);

        if (alpha >= beta) {
            break;
        }
    }

    return best;
}

Upvotes: 1

Related Questions