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 possiblePositions = getAllPossiblePositions(board, Team.Black);
          List 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 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 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. 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.
  
  
  ---
  
  