Bug in minimax for tic_tac_toe AI

Question

I have been trying to implement an AI for the computer using minimax with alpha-beta pruning, but I m facing an unidentifiable bug. The algorithm should calculate all the possible moves of its own and the other player too, but it isn't playing back the way it should.

Here is my minimax code :

public int minimax(int[] board, char symbol, int alpha, int beta, int depth = 2)
{
    int win = util.checkwin(board);
    int nsymbol = (symbol == 'X' ? 1 : 2);
    int mult = (symbol == compside ? 1 : -1);

    if (win != -1)
    {
        if (win == nsymbol)
            return mult;
        else if (win != 0)
            return (mult * -1);
        else
            return 0;
    }

    if (depth == 0)
        return 0;

    int[] newboard = new int[9];
    Array.Copy(board, newboard, 9);
    int score, i, pos = -1;
    ArrayList emptyboard = new ArrayList();
    emptyboard = util.filterboard(newboard);

    for (i = 0; i < emptyboard.Count; i++)
    {
        if (i > 0)
            newboard[(int)emptyboard[i - 1]] = 0;

        newboard[(int)emptyboard[i]] = nsymbol;
        score = minimax(newboard, util.changeside(symbol), alpha, beta, depth - 1);

        if (mult == 1)
        {
            if (score > alpha)
            {
                alpha = score;
                pos = (int)emptyboard[i];
            }

            if (alpha >= beta)
                break;
        }
        else
        {
            if (score < beta)
                beta = score;

            if (alpha >= beta)
                break;
        }
    }

    if (depth == origdepth)
        return pos;

    if (mult == 1)
        return alpha;
    else
        return beta;
}

The details of undefined functions:

util.checkwin(int[] board) = checks the board for a possible won or drawn outboard or an incomplete board, and returns the winner as 1 or 2 (player X or O), 0 for a draw, and -1 for an incomplete board.

util.filterboard(int[] newboard) = returns an arraylist containing all the positions of empty locations in board given.

util.changeside(char symbol) = simply flips X to O and O to X and returns the result.

I have tried with the depth as 2 which means it will calculate the next 2 moves (if it is winning and if the opponent can win). But the results weren't what I expected. and it is also trying to play on a filled location occasionally.

Here is an output(depth = 2):

 Turn: X
  |   |
1 | 2 | 3
__|___|__
  |   |
4 | 5 | 6
__|___|__
  |   |
7 | 8 | 9
  |   |
Enter Your Choice:

 Turn: O
  |   |
1 | 2 | 3
__|___|__
  |   |
X | 5 | 6
__|___|__
  |   |
7 | 8 | 9
  |   |
Enter Your Choice: 5


 Turn: X
  |   |
1 | 2 | 3
__|___|__
  |   |
X | O | 6
__|___|__
  |   |
7 | 8 | 9
  |   |
Enter Your Choice:

 Turn: O
  |   |
1 | X | 3
__|___|__
  |   |
X | O | 6
__|___|__
  |   |
7 | 8 | 9
  |   |
Enter Your Choice: 1


 Turn: X
  |   |
O | X | 3
__|___|__
  |   |
X | O | 6
__|___|__
  |   |
7 | 8 | 9
  |   |
Enter Your Choice:

 Turn: O
  |   |
O | X | 3
__|___|__
  |   |
X | O | 6
__|___|__
  |   |
7 | X | 9
  |   |
Enter Your Choice: 9


  |   |
O | X | 3
__|___|__
  |   |
X | O | 6
__|___|__
  |   |
7 | X | O
  |   |
O Wins

But it still fails to recognize my winning move.

All the other functions have been tested when played user against a user and they are all working fine. I would appreciate some help.

I am happy to provide my full code, if necessary and anything else required.

Answer 1

A couple of observations.

1) The if (depth == 0) return 0; should be changed to something like

if (depth == 0) return EvaluatePosition();,

because currently your algorithm will return 0 (score, corresponding to a draw) whenever it reaches depth zero (while the actual position at zero depth might not be equal - for instance, one of the sides can have huge advantage). EvaluatePosition() function should reflect the current board position (it should say something like "X has an advantage", "O is losing", "The position is more or less equal" etc, represented as a number). Note, that this will matter only if depth == 0 condition is triggered, otherwise it is irrelevant.

2) Do you really need this emptyboard stuff? You can iterate over all squares of the newboard and once you find an empty square, copy the original board, make the move on this empty square and call minimax with the copied and updated board. In pseudocode it will look something like this:

for square in board.squares: if square is empty: board_copy = Copy(board) board_copy.MakeMove(square) score = minimax(board_copy, /*other arguments*/) /*the rest of minimax function*/

3) The if (alpha >= beta) break; piece is present in both branches (for mult == 1 and mult != 1), so you can put it after the if-else block to reduce code repetition.

4) Check if your algorithm is correct without alpha-beta pruning. The outcomes of plain minimax and alpha-beta pruning minimax should be the same, but plain minimax is easier to understand, code and debug. After your plain minimax is working properly, add enhancements like alpha-beta pruning and others.