Why is my minimax algorithm for Tic-Tac-Toe so slow?

  alpha-beta-pruning, c++, minimax

The algorithm figures out its move on an empty grid in around 180ms which is obviously playable, but way too slow for its purpose. I’m also planning on implementing the algorithm for chess and I don’t want it to take so much time on a much simpler game. In this video the algorithm moves pretty much instantly even though it was written in JavaScript.

My code:

AI.cpp:

AI::AI(int AI_ID, int AI_depth) {
    ID = AI_ID;
    myDepth = AI_depth;
}

int AI::min(Board* board, int alpha, int beta, int depth) {
    int boardScore = evaluate(board);
    if (boardScore != 2) {
        return boardScore;
    }

    if (depth == 0) {
        return 0;
    }

    int bestScore = beta;

    for (int x = 0; x < 3; x++) {
        for (int y = 0; y < 3; y++) {
            if (!board->isTaken(x, y)) {
                board->replace(3 - ID, x, y);
                int score = max(board, alpha, bestScore, depth - 1);
                board->replace(0, x, y);

                if (score < bestScore) {
                    bestScore = score;
                    if (bestScore <= alpha) {
                        break;
                    }
                }
            }
        }
    }

    return bestScore;
}

int AI::max(Board* board, int alpha, int beta, int depth) {
    int boardScore = evaluate(board);
    if (boardScore != 2) {
        return boardScore;
    }

    if (depth == 0) {
        return 0;
    }

    int bestScore = alpha;

    for (int x = 0; x < 3; x++) {
        for (int y = 0; y < 3; y++) {
            if (!board->isTaken(x, y)) {
                board->replace(ID, x, y);
                int score = min(board, bestScore, beta, depth - 1);
                board->replace(0, x, y);

                if (score > bestScore) {
                    bestScore = score;
                    if (depth == myDepth) {
                        bestMove = {x, y};
                    }
                    if (bestScore >= beta) {
                        break;
                    }
                }
            }
        }
    }

    return bestScore;
}

int AI::evaluate(Board* board) {
    int win = board->checkWin(false);
    if (win == 0) {
        return board->isDraw() ? 0 : 2;
    } else {
        return win == ID ? 1 : -1;
    }
}

Move AI::getBestMove(Board* board) {
    max(board, -2, 2, myDepth);
    return bestMove;
}

Board.cpp:

void Board::replace(int id, int x, int y) {
    grid[x][y] = id;
}

bool Board::isTaken(int x, int y) {
    return grid[x][y] != 0;
}

int Board::checkWin(bool save) {
    int winner = 0;

    for (int j = 0; j < 3; j++) {
        if (grid[j][0] == grid[j][1] && grid[j][1] == grid[j][2] && grid[j][0] > 0) {
            if (save) {
                winRow = j;
                winPosition = VERTICAL;
            }

            return grid[j][0];
        }
        if (grid[0][j] == grid[1][j] && grid[1][j] == grid[2][j] && grid[0][j] > 0) {
            if (save) {
                winRow = j;
                winPosition = HORIZONTAL;
            }

            return grid[0][j];
        }
    }

    if (grid[0][0] == grid[1][1] && grid[1][1] == grid[2][2] && grid[0][0] > 0) {
        if (save) {
            winRow = 0;
            winPosition = DIAGONAL;
        }

        return grid[0][0];
    }

    if (grid[0][2] == grid[1][1] && grid[1][1] == grid[2][0] && grid[0][2] > 0) {
        if (save) {
            winRow = 1;
            winPosition = DIAGONAL;
        }

        return grid[0][2];
    }

    return 0;
}

bool Board::isDraw() {
    for (int x = 0; x < 3; x++) {
        for (int y = 0; y < 3; y++) {
            if (grid[x][y] == 0) {
                return false;
            }
        }
    }

    return true;
}

Source: Windows Questions C++

LEAVE A COMMENT