In a Minimax algorithm, what happens if an AI doesn't reach a terminal state before hitting dep-CodePudding

I have been coding a simple Minimax algorithm and stumbled upon a problem I'm not able to solve. The algorithm first determines if the game is over (either via a draw or win of either player) OR if the depth hits == 0 (depth decreases by 1 in each recursive call).

The problem I'm having is the algorithm usually hits depth 0 really quickly (as the initial depths are low). However, as pointed out by the pseudocode I have been given, if that happens, the algorithm should return a static evaluation of the current board. In my case, that board is in a state of CONTINUE (meaning there are no game over conditions met).

I have my evaluation algorithm set so it returns -1 if circle wins, 0 for a draw and 1 for cross win. What should I return if the game isn't over yet at depth==0 to not mess up the maximizing/minimizing of the algorithm?

The evaluation code:

int getGameResult() {
    //check for possible win
    //check vertical lines
    for (int i = 0; i <= BOARD_SIZE - 4; i  ) {
        for (int j = 0; j < BOARD_SIZE; j  ) {
            //if circle has 4 verticals
            if (board[i][j] == FieldStatus::CIRCLE
                && board[i   1][j] == FieldStatus::CIRCLE
                && board[i   2][j] == FieldStatus::CIRCLE
                && board[i   3][j] == FieldStatus::CIRCLE) {
                return -1;
            }
            //if cross has 4 verticals
            else if (board[i][j] == FieldStatus::CROSS
                && board[i   1][j] == FieldStatus::CROSS
                && board[i   2][j] == FieldStatus::CROSS
                && board[i   3][j] == FieldStatus::CROSS) {
                return 1;
            }
        }
    }

    //check horizontal lines
    for (int i = 0; i < BOARD_SIZE; i  ) {
        for (int j = 0; j <= BOARD_SIZE - 4; j  ) {
            //if circle has 4 horizontals
            if (board[i][j] == FieldStatus::CIRCLE
                && board[i][j   1] == FieldStatus::CIRCLE
                && board[i][j   2] == FieldStatus::CIRCLE
                && board[i][j   3] == FieldStatus::CIRCLE) {
                return -1;
            }
            //if cross has 4 horizontals
            else if (board[i][j] == FieldStatus::CROSS
                && board[i][j   1] == FieldStatus::CROSS
                && board[i][j   2] == FieldStatus::CROSS
                && board[i][j   3] == FieldStatus::CROSS) {
                return 1;
            }
        }
    }

    //check diagonals
    //right diagonals
    for (int i = 0; i < BOARD_SIZE - 3; i  ) {
        for (int j = 0; j < BOARD_SIZE - 3; j  ) {
            if (board[i][j] == FieldStatus::CIRCLE
                && board[i   1][j   1] == FieldStatus::CIRCLE
                && board[i   2][j   2] == FieldStatus::CIRCLE
                && board[i   3][j   3] == FieldStatus::CIRCLE) {
                return -1;
            }

            if (board[i][j] == FieldStatus::CROSS
                && board[i   1][j   1] == FieldStatus::CROSS
                && board[i   2][j   2] == FieldStatus::CROSS
                && board[i   3][j   3] == FieldStatus::CROSS) {
                return 1;
            }
        }
    }

    //left diagonals
    for (int i = BOARD_SIZE - 1; i > BOARD_SIZE - 2; i--) {
        for (int j = 0; j < BOARD_SIZE - 3; j  ) {
            if (board[i][j] == FieldStatus::CIRCLE
                && board[i - 1][j   1] == FieldStatus::CIRCLE
                && board[i - 2][j   2] == FieldStatus::CIRCLE
                && board[i - 3][j   3] == FieldStatus::CIRCLE) {
                return -1;
            }

            if (board[i][j] == FieldStatus::CROSS
                && board[i - 1][j   1] == FieldStatus::CROSS
                && board[i - 2][j   2] == FieldStatus::CROSS
                && board[i - 3][j   3] == FieldStatus::CROSS) {
                return 1;
            }
        }
    }

    //check for draw
    for (int i = 0; i < BOARD_SIZE; i  ) {
    

        for (int j = 0; j < BOARD_SIZE; j  ) {
            if (board[i][j] != FieldStatus::EMPTY) {
                return -5; //!! This is the part that confuses me
            }
        }
    }

    return 0;
}

The minimax code (isCross basically means isMaximizer):

int minimax(int depth, bool isCross) {
    //cross maximizes, circle minimizes
    //check if game is done
    if (depth == 0 && isGameOver()) {
        int result = getGameResult();
        
        if (result == -5 && isCross) {
            return 1;
        }
        else if (result == -5) {
            result = -1;
        }

        return result;
    }

    //if maximizing
    if (isCross) {
        int bestMoveScore = INT_MIN;
        for (int i = 0; i < BOARD_SIZE; i  ) {
            for (int j = 0; j < BOARD_SIZE; j  ) {
                if (board[i][j] == FieldStatus::EMPTY) {
                    board[i][j] = FieldStatus::CROSS;

                    int fieldScore = minimax(depth - 1, false);

                    board[i][j] = FieldStatus::EMPTY;
                    if (fieldScore > bestMoveScore) {
                        bestMoveScore = fieldScore;
                    }
                }
            }
        }
        return bestMoveScore;
    }
    else { //minimize
        int bestMoveScore = INT_MAX;
        for (int i = 0; i < BOARD_SIZE; i  ) {
            for (int j = 0; j < BOARD_SIZE; j  ) {
                if (board[i][j] == FieldStatus::EMPTY) {
                    board[i][j] = FieldStatus::CIRCLE;

                    int fieldScore = minimax(depth - 1, true);

                    board[i][j] = FieldStatus::EMPTY;

                    if (fieldScore < bestMoveScore) {
                        bestMoveScore = fieldScore;
                    }
                }
            }
        }
        return bestMoveScore;
    }
}

CodePudding user response：

First there are some issues in your code:

You write (correctly) that a draw is evaluated as 0, but the code doesn't do that. The relevant code is:
```
//check for draw
for (int i = 0; i < BOARD_SIZE; i  ) {    
    for (int j = 0; j < BOARD_SIZE; j  ) {
        if (board[i][j] != FieldStatus::EMPTY) {
            return -5; //!! This is the part that confuses me
        }
    }
}
return 0;
```
The final return 0 can only be executed when the if condition is never true, which -- if we look closely -- would mean all cells are empty! This is obviously wrong. The if condition should be:
```
    if (board[i][j] == FieldStatus::EMPTY) {
```
and now -5 will be the return value whenever getGameResult is called in a state where the game is not over yet. It signifies something like "I have no idea what the value is".
As you have a getGameResult function, which will correctly identify whether the game is over or not, you don't really need gameOver as a separate function. If getGameResult returns -5, then the game is not over, and in all other cases (-1, 0, or 1) it is over.

Your code does not always check whether the game is over

int minimax(int depth, bool isCross) {
    //cross maximizes, circle minimizes
    //check if game is done
    if (depth == 0 && isGameOver()) {
        int result = getGameResult();

This code will only detect whether the game is over when depth is 0, but it could well be that the game ends earlier. So the condition depth == 0 should not be placed here, but be put as a separate case after having dealt with the game-over situation:

int result = getGameResult();
if (result != -5) { // Game is over!
    return result;
}
// Game is not over yet... check if we should search deeper
if (depth == 0) { // We should stop searching.
    return evaluate(); // Use some heuristic to give an estimated value
}

So now we get to your core question: how to implement evaluate (used in above code block)

For the game at hand, you could use the following characteristics to get an estimated value for the game:

Count the number of 4-in-a-row that are potentially still possible for a player. For a line of 4 cells to count in that sum, it should not contain any moves of the opponent. So they should either be empty or have the player's own symbol(s). If that is true for a line of 4 cells, it should contribute as 1 to a total sum that is calculated for all lines of 4 cells. Calculate this sum from the viewpoint of each player separately.
To improve, if among those potential 4-in-a-rows there are some that have 3 occupied by the player, then give them more weight (like count them as 3 instead of just as 1 in the sum). Similarly apply a coefficient for those that have 2 cells occupied.
Given the two sums that are calculated like that, calculate the difference. If positive, that means it is good for the X-player, else it is good for the O-player.
Finally convert this number (e.g. by dividing by 1000) so it is guaranteed to be between (-1, 1) and distinct from the values for a win/loss. It may be better to work with integers, so then use the values 1000 and -1000 for win and loss, instead of 1 and -1.

CodePudding user response：

If you cannot evaluate the tree far enough to get to the end of the game, then you need to have some function which can produce an approximate score for an incomplete gamestate. So if 1 means cross wins, then numbers between 0 and 1 would indicate they're increasingly likely to win, and numbers between 0 and -1 indicate they're likely to lose. The details of this evaluation function entirely depends on the game you're playing, and it may not be obvious what the "right" function to do this is.

In chess for example, here's some functions you could write to try to approximate who's winning:

Add up the number of pieces player A has, and subtract the number of pieces player B has
Same as #1, but weight the pieces relative to how good they generally are (queens worth more than pawns, for example)
Same as #2, but write some complicated logic which looks at the arrangement of the pieces to try to guess whether that arrangement is good or not. Maybe it would give a bonus to pieces that have many moves available to them as opposed to being trapped behind other pieces, or would add a bonus when pawns are arranged diagonally to support eachother.
Same as #3, but use a neural network and billions of training games to generate the complicated logic for you.

What's a good evaluation function for your game? I'm afraid I don't really have a good answer for you. Figuring that out requires some expertise in the game, and very likely some experimentation. To start, maybe you could do something which figures out which pieces are "dead" (ie, they're surrounded such that they can not contribute to making a line of 4), and then sums up the remaining pieces.