1

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;
    }
3
  • 4
    This question could be improved by providing a test position or two (using FEN) along with your output and times. Feb 16 at 15:35
  • This is likely better asked on cs.stackexchange.com or stackoverflow Feb 16 at 16:45
  • 1
    This kind of question is usually best answered by profiling the code to see where it spends most time during execution. How to do that is, however, a question best asked in a forum that focuses on the particular programming language that you use, as well as the development platform, if any, that you use, and possibly even the execution platform. If you provide that information, you may get a better reply.
    – user30536
    Feb 17 at 9:00

1 Answer 1

5

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.