Why is my chess engine that uses minimax with alpha-beta pruning so slow, even at depth 3?

Question

I have little experience with any sort of chess AI and am at a complete loss as to why it still takes a couple of seconds to calculate a decent move even at just depth 3. Here is the code:

private void makeAIMove(Piece[,] board)
    {
        Move bestMove;
        int score;

        List<Piece[,]> possiblePositions = getAllPossiblePositions(board, Team.Black);
        List<Move> possibleMoves = getAllPossibleMoves(board, Team.Black);

        bestMove = possibleMoves[0];
        score = evaluatePosition(possiblePositions[0], int.MinValue, int.MaxValue, DEPTH, Team.White);
        if (numTurns > 0)
        {
            for (int i = 1; i < possiblePositions.Count; i++)
            {
                int pos = evaluatePosition(possiblePositions[i], int.MinValue, int.MaxValue, DEPTH, Team.White);
                if (pos >= score)
                {
                    bestMove = possibleMoves[i];
                    score = pos;
                }
            }
        }
        else
        {
            bestMove = possibleMoves[Random.Range(0, possibleMoves.Count)];
        }
        numTurns += 1;
        updateBoard(bestMove);
    }

    private int evaluatePosition(Piece[,] board, int alpha, int beta, int depth, int team)
    {
        if (depth == 0)
        {
            return evaluate(board);
        }
        if (team == Team.White)
        {
            List<Move> moves = getAllPossibleMoves(board, team);
            int newBeta = beta;
            foreach (Move moveName in moves)
            {
                Piece[,] newBoard = (Piece[,])board.Clone();
                newBoard = move(newBoard, newBoard[moveName.start.y, moveName.start.x], moveName.start, moveName.end);
                newBeta = Mathf.Min(newBeta, evaluatePosition(newBoard, alpha, beta, depth - 1, oppositeTeam(team)));
                if (newBeta <= alpha) break;
            }
            return newBeta;
        }
        else
        {
            List<Move> moves = getAllPossibleMoves(board, team);
            int newAlpha = alpha;
            foreach (Move moveName in moves)
            {
                Piece[,] newBoard = (Piece[,])board.Clone();
                newBoard = move(newBoard, newBoard[moveName.start.y, moveName.start.x], moveName.start, moveName.end);
                newAlpha = Mathf.Max(newAlpha, evaluatePosition(newBoard, alpha, beta, depth - 1, oppositeTeam(team)));
                if (beta <= newAlpha) break;
            }
            return newAlpha;
        }
    }

    int[] scoreTable = new int[]
        {
            1, 3, 3, 5, 9, 999 // Value of each piece
        };
    private int evaluate(Piece[,] board)
    {
        int blackScore = 0;
        int whiteScore = 0;
        for (int i = 0; i < 8; ++i)
        {
            for (int j = 0; j < 8; ++j)
            {
                if (board[i, j].team != Team.None)
                {
                    if (board[i, j].team == Team.White)
                    {
                        whiteScore += scoreTable[board[i, j].name];
                    }
                    else
                    {
                        blackScore += scoreTable[board[i, j].name];
                    }
                }
            }
        }
        return blackScore - whiteScore;
    }

Answer 1

I don't have time to read your code in detail, but the main thing that sticks out to me is the following line:

Piece[,] newBoard = (Piece[,])board.Clone();
newBoard = move(newBoard, .... blablabla

So for each move, you're creating a new board then making your move on that new board. This is breathtakingly slow. There are two main problems: 1. Dynamic memory allocation (that is, creating new objects on the fly) is usually a no-no if you care about performance (). 2. How exactly is the board being cloned? (do you know?) Looping over ever square? Slow.

Usually this is done by creating one board object, then when you loop over each move you 1. make the move 2. do whatever calculation/recursion you want and 3. undo the move. This avoids all Dynamic memory allocation and cloning.

These problems can also appear when creating new move objects.

---

If you plan on making further modifications to this engine, you should really use negamax. Eventually your search function will grow to 200+ lines, and you really don't want to make each change twice (once for white and black) and have to think about whether the > should be a < or whatever. This may seem superficial, but it's basically required if you want to have manageable code and not spend all your time squashing bugs.