Othello Minimax Algorithm

Question

I am trying to implement an artificial intelligence player for Othello using the Minimax algorithm. The computer plays decently, but its not great. Did I implement it correctly in my following code?

Coordinate bestCoordinate = null;
public int minimax(MyButton[][] gameBoard, int depth, boolean maximizingPlayer) {
    if (depth == 0) {
        return evaluateBoard(gameBoard);
    }

    if (maximizingPlayer) {
        int bestValue = Integer.MIN_VALUE;
        LinkedList<Coordinate> moves = generateMoves(gameBoard);
        for (Coordinate move : moves) {
            MyButton[][] newBoard = cloneBoard(gameBoard);
            processMove(newBoard, newBoard[move.getxCoordinate()][move.getyCoordinate()]);
            int v = minimax(newBoard, depth - 1, !maximizingPlayer);
            if (v > bestValue) {
                bestValue = v;
                bestCoordinate = move;
            }
        }
        return bestValue;
    }
    else {
        int bestValue = Integer.MAX_VALUE;
        LinkedList<Coordinate> moves = generateMoves(gameBoard);
        for (Coordinate move : moves) {
            MyButton[][] newBoard = cloneBoard(gameBoard);
            processMove(newBoard, newBoard[move.getxCoordinate()][move.getyCoordinate()]);
            int v = minimax(newBoard, depth - 1, !maximizingPlayer);
            if (v < bestValue) {
                bestValue = v;
                bestCoordinate = move;
            }
        }
        return bestValue;
    }
}

Also, here is my evaluation function:

public int evaluateBoard(MyButton[][] gameBoard) {

    int blackPieces = 0;
    int whitePiecess = 0;

    for (MyButton[] array : gameBoard) {
        for (MyButton button : array) {
            if (button.getBackground().equals(Color.black)) {
                blackPieces++;
            } else if (button.getBackground().equals(Color.WHITE)) {
                whitePiecess++;
            }
        }
    }

    int cornerBonus = 10;
    if (gameBoard[0][0].getBackground().equals(Color.BLACK)) {
        blackPieces += cornerBonus;
    }
    if (gameBoard[0][getBoardWidth() - 1].getBackground().equals(Color.BLACK)) {
        blackPieces += cornerBonus;
    }
    if (gameBoard[getBoardHeight() - 1][0].getBackground().equals(Color.BLACK)) {
        blackPieces += cornerBonus;
    }
    if (gameBoard[getBoardHeight() - 1][getBoardWidth() - 1].getBackground().equals(Color.BLACK)) {
        blackPieces += cornerBonus;
    }
    if (gameBoard[0][0].getBackground().equals(Color.WHITE)) {
        whitePiecess += cornerBonus;
    }
    if (gameBoard[0][getBoardWidth() - 1].getBackground().equals(Color.WHITE)) {
        whitePiecess += cornerBonus;
    }
    if (gameBoard[getBoardHeight() - 1][0].getBackground().equals(Color.WHITE)) {
        whitePiecess += cornerBonus;
    }
    if (gameBoard[getBoardHeight() - 1][getBoardWidth() - 1].getBackground().equals(Color.WHITE)) {
        whitePiecess += cornerBonus;
    }
    return whitePiecess - blackPieces;
}

(The computer always plays white, and the human is black). I'm mainly unsure because the computer doesn't seem to protect corners, despite the bonus points that they give. Is there anything wrong with my code/logic?

Answer 1

You are updating your best move at each depth. Make a constant called SEARCH_DEPTH outside of your function that you use every time you call the function and do an if check:

if(depth == SEARCH_DEPTH) {
    bestCoordinate = move;
}

Also, assuming you are the maximizing player, you only want to set the move in the if(maximizingPlayer) block.

Answer 2

I did not test your code out myself, but that is the minimax algorithm, and it appears to be written correctly (assuming your helper functions are implemented correctly). I have some points that might give you insight as to why your agent is not acting optimally:

1. I see your objective function is the number of pieces your agent has minus the number the opponent has, plus a bonus for corner pieces. This might seem like the best strategy, but I would read up on how good Othello players make their moves. Often, they try to flip only one piece if they can until late game, as they have more opportunities that way.
2. Minimax won't necessarily return the moves that will lead to capturing corners, even if you weigh them highly, because it might be undermined by the opponent's choice of moves. For example, lets say your algorithm looks three turns ahead on the computer's turn, so it first looks at a state where it capture a corner with a high objective function. However, your opponent will be choosing the route that will minimize your objective function, and as such the computer will not view moves moving towards capturing a corner piece as optimal because of the risk. I don't know how easy this will be, but if you can somehow visualize the tree, you might be able to figure out if this is the case.