Answers.Body: <p>I don't have time to read your code in detail, but the main thing that sticks out to me is the following line:</p>
  <pre><code>Piece[,] newBoard = (Piece[,])board.Clone();
  newBoard = move(newBoard, .... blablabla
  </code></pre>
  <p>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.</p>
  <p>Usually this is done by creating <em>one</em> board object, then when you loop over each move you 1. make the move 2. do whatever calculation/recursion you want and 3. <em>undo</em> the move. This avoids all Dynamic memory allocation and cloning.</p>
  <p>These problems can also appear when creating new move objects.</p>
  <hr />
  <p>If you plan on making further modifications to this engine, you should really use <a href="https://en.wikipedia.org/wiki/Negamax#:%7E:text=Negamax%20search%20is%20a%20variant,the%20value%20to%20player%20B." rel="noreferrer">negamax</a>. 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 &gt; should be a &lt; 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-19T17:15:19.723Z
Answers.LastActivityDate: 2022-02-19T17:15:19.723Z
Answers.UserDisplayName: Noah Caplinger
Body: <p>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:</p>
  <pre><code>private void makeAIMove(Piece[,] board)
      {
          Move bestMove;
          int score;
  
          List&lt;Piece[,]&gt; possiblePositions = getAllPossiblePositions(board, Team.Black);
          List&lt;Move&gt; possibleMoves = getAllPossibleMoves(board, Team.Black);
  
          bestMove = possibleMoves[0];
          score = evaluatePosition(possiblePositions[0], int.MinValue, int.MaxValue, DEPTH, Team.White);
          if (numTurns &gt; 0)
          {
              for (int i = 1; i &lt; possiblePositions.Count; i++)
              {
                  int pos = evaluatePosition(possiblePositions[i], int.MinValue, int.MaxValue, DEPTH, Team.White);
                  if (pos &gt;= 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&lt;Move&gt; 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 &lt;= alpha) break;
              }
              return newBeta;
          }
          else
          {
              List&lt;Move&gt; 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 &lt;= 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 &lt; 8; ++i)
          {
              for (int j = 0; j &lt; 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;
      }
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-16T15:35:50.853Z
Comments.Text: This question could be improved by providing a test position or two (using FEN) along with your output and times.
Comments.UserDisplayName: SecretAgentMan
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-16T16:45:22.740Z
Comments.Text: This is likely better asked on https://cs.stackexchange.com/ or stackoverflow
Comments.UserDisplayName: Ian Ringrose
Tags: <engines><programming><minimax>
Title: Why is my chess engine that uses minimax with alpha-beta pruning so slow, even at depth 3?
ThreadText: # Why is my chess engine that uses minimax with alpha-beta pruning so slow, even at depth 3?
  
  (Asked by: username_0 on 2022-02-16)
  
  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;
      }
  
  ```
  
  **Tags:** engines, programming, minimax
  
  > **Comments:**
  > **username_1**: This question could be improved by providing a test position or two (using FEN) along with your output and times.  
  > **username_2**: This is likely better asked on https://cs.stackexchange.com/ or stackoverflow  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2022-02-19. Score: 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](https://en.wikipedia.org/wiki/Negamax#:%7E:text=Negamax%20search%20is%20a%20variant,the%20value%20to%20player%20B.). 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.
  
  
  ---
  
  