Determining the right position in minimax tic-tac-toe

Question

I tried to code a simple version of tic-tac-toe in C++ using the minimax algorithm but ran into a problem while trying to determine the position where the score is the best. The minEval (Returns score for min), maxEval(returns score for max) and playMove (determines which position to play and then plays the move) functions are shown below.

int maxEval(int board[9]) {
    if (checkDraw(board)) {
        return 0;
    }
    else if (checkWin(board)) {
        return -1000;
    }
    int finalScore = -1000;
    for (int i = 0; i < 9; i++) {
        if (board[i] == 0) {
            board[i] = 1;
            int score = minEval(board);
            if (score > finalScore) {
                finalScore = score;
            }
            board[i] = 0;
        }
    }
    return finalScore;
}

int minEval(int board[9]) {
    if (checkDraw(board)) {
        return 0;
    }
    else if (checkWin(board)) {
        return 1000;
    }
    int finalScore = 1000;
    for (int i = 0; i < 9; i++) {
        if (board[i] == 0) {
            board[i] = -1;
            int score = maxEval(board);
            if (score < finalScore) {
                finalScore = score;
            }
            board[i] = 0;
        }
    }
    return finalScore;
}

void playMove(int board[9], int player) {
    int finalScore = player * -1000;
    int position;
    for (int i = 0; i < 9; i++) {
        if (board[i] == 0) {
            board[i] = player;
            int score;
            if (player == 1) {
                score = maxEval(board);
            }
            else {
                score = minEval(board);
            }
            if (player == 1 && score >= finalScore) {
                finalScore = score;
                position = i;
            }
            else if (player == -1 && score <= finalScore) {
                finalScore = score;
                position = i;
            }
            board[i] = 0;
        }
    }

    board[position] = player;
}

When I tested different positions to see whether minEval and maxEval correctly evaluate the position, the functions return the correct score (1000 for max win, -1000 for min win and 0 for a draw). However, when I make the AI play by using the playMove function, it plays very dubious moves and almost always makes "incorrect" moves. Here is an example of a game I made the program play (with itself):

I suspect that there is something wrong with the way I set position to i, but I tried to make changes to no avail. Any suggestions as to what is wrong with the evaluate function? Thanks.

Here is the link to the entire code: http://ideone.com/6791d4

Answer 1

I would check up on the variations found not just the scores. Are you finding just any winning variation, or the one where the opponent plays best?

e.g. Modify your min/max Eval code to also add the move chosen to an array.

BTW it may be easier to see what is happening if you combine the min/max Eval routines into one.

WARNING UNTESTED CODE

int minmaxEval(int board[9], int player, int moves[9], int move) {
    if (checkDraw(board)) {
        return 0;
    }
    int finalScore = player * -1000;
    if (checkWin(board)) {
        return finalScore;
    }
    for (int i = 0; i < 9; i++) {
        if (board[i] == 0) {
            board[i] = player;
            int score = minmaxEval(board, -player, moves, move+1);
            if ( (player > 0 && score > finalScore) ||
                (player < 0 && score < finalScore) ) {
                  finalScore = score;
                  moves[move] = i;
            }
            board[i] = 0;
        }
    }
    return finalScore;
}

If you print out moves[] in your toplevel routine you should see the variation which gave that score. A mismatch there will inform your understanding of the algorithm e.g. is it stopping when it finds a win.

In general it is important to have a way to double check your code is doing what you expect. Look into unit testing and test-driven development.