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

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] == grid[j] && grid[j] == grid[j] && grid[j] > 0) {
if (save) {
winRow = j;
winPosition = VERTICAL;
}

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

return grid[j];
}
}

if (grid == grid && grid == grid && grid > 0) {
if (save) {
winRow = 0;
winPosition = DIAGONAL;
}

return grid;
}

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

return grid;
}

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++