CODEWITHSUNDEEP
calgorithmtic-tac-toeminimax
Colin Harrison
Colin Harrison

Reputation: 194

Minimax not scoring branches correctly in tic-tac-toe

I'm trying to create a perfect tic-tac-toe game in C. I'm using a 2D array to keep track of the board.

I have narrowed the issue down to the way my minimax function is scoring each potential move, but I am having trouble debugging it because the error happens around the second move usually, and I cannot keep track of all the potential game states from that point.

The computer goes first, and is always 'X'. minimax is being called from within a computerMove function which tries each available move and then minimaxes them. It takes the value returned for the potential game state from minimax as a temporary score and compares it to the current top score. I am confident that part of the program is working. The problem lies in the minimax function itself

Here is the important parts of my code:

int minimax(char board[][3], char maxPlayer) // +10 -> X wins 
{                                            // -10 -> O wins
    char minPlayer;                          //   0 -> draw
    int scores[3][3];
    if (maxPlayer == 'X') minPlayer = 'O';
    else minPlayer = 'X';
    int topScore = 0;

    // initializing scores to ensure a move is selected
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            scores[i][j] = -11;
        }
    }

    // check for terminal state
    if (isWinning(board,'X') || isWinning(board,'O') || 
    !moveAvailable(board)) {
        if (isWinning(board,'X')) return 10;
        else if (isWinning(board,'O')) return -10;
        else return 0;
    }

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i][j] == 'U') { 
                board[i][j] = maxPlayer;                // try the move
                scores[i][j] = minimax(board,minPlayer);// minimax it
                board[i][j] = 'U';                      // undo the move
            }
        }
    }  

    // if calling minimax for computer, maximize the score
    if (maxPlayer == 'X') {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (scores[i][j] > topScore && scores[i][j] != -11) 
                    topScore = scores[i][j];
            }
        }
    }

    // if calling minimax for human, minimize the score
    else if (maxPlayer == 'O') {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (scores[i][j] < topScore && scores[i][j] != -11) 
                    topScore = scores[i][j];
            }
        }
    }
    return topScore;
}

Upvotes: 0

Views: 178

Answers (1)

gdelab
gdelab

Reputation: 6220

The problem is with topScore initialization:

  • You should initialise topScore at 11 or -11 depending on who plays, not 0, otherwise both players will believe they can always reach at least a draw (which is not the case), starting at depth 2.

  • in terms of good practices (imho), I think that the last two loops should be grouped into one, with the if (maxPlayer == 'X') condition inside of it, just before updating topScore. Also, you should skip all positions where board[i][j]!='U', it's easier to understand than lookinf for -11 in scores (which is good though).

Upvotes: 1

Related Questions