Body: <p>I'm currently making a chess engine in Java and my search function is extremely slow to the point that it's slower than my perft function. My search function is currently a negamax search that uses transposition tables, quiescence, and iterative deepening. For reference, I can run perft(depth = 6) with my move generator in 30-40 seconds, but running negamax takes a few minutes with the same depth.</p>
  <p>In terms of the rest of my engine, I'm using bitboards for move generation. For my evaluation function, I currently only have basic piece-square tables from the chess programming wiki because I want to focus on improving my search function first. I think it may be due to my quiescence function making the search slower but I don't know exactly how or why. I have attached my negamax and quiescence implementation below:
  <br/>btb = instance of bitboard class, tt = instance of transposition table. Both are instantiated once when the program is run.</p>
  <pre><code>    public int negamaxFunction(bitboard btb, int currentDepthSearched, int alpha, int beta) {
          if (btb.plyCount_50Move == 100) {
              return 0;
          }
          if (currentDepthSearched == currentMaxSearchDepth) {
              return quiescenceSearch(btb, alpha, beta, currentDepthSearched);
          }
          ArrayList&lt;Integer&gt; allMoves = new ArrayList&lt;&gt;();
          ArrayList&lt;Integer&gt; captures = new ArrayList&lt;&gt;();
          ArrayList&lt;Integer&gt; quietMoves = new ArrayList&lt;&gt;();
          ArrayList&lt;Integer&gt; checks = new ArrayList&lt;&gt;();
          mover.generateAllLegalMoves(btb.wp, btb.wn, btb.wb, btb.wr, btb.wq, btb.wk, btb.bp, btb.bn,
                  btb.bb, btb.br, btb.bq, btb.bk, btb.turn, btb.wCastle, btb.bCastle, btb.lastPawnJump,
                  captures, quietMoves, checks);
          allMoves.addAll(captures); allMoves.addAll(checks); allMoves.addAll(quietMoves);
          if (allMoves.isEmpty()) {
              switch (btb.turn) {
                  case (1) -&gt; {
                      if (mover.squareInCheck(Long.numberOfTrailingZeros(btb.wk), btb.bp, btb.bn, btb.bb, btb.br, btb.bq, btb.bk, btb.turn)) {
                          return MATE_SCORE + currentDepthSearched * 10; //encourages engine to go for longer forced mates
                      } else {
                          return 0;
                      }
                  }
                  case (-1) -&gt; {
                      if (mover.squareInCheck(Long.numberOfTrailingZeros(btb.bk), btb.wp, btb.wn, btb.wb, btb.wr, btb.wq, btb.wk, btb.turn)) {
                          return MATE_SCORE + currentDepthSearched * 10;
                      } else {
                          return 0;
                      }
                  }
              }
          }
  
          for (int m : allMoves) {
              boolean drawByRep = btb.makeMove(m);
              if (drawByRep) {return 0;}
              int score = tt.returnPastEval(btb.currentZobrist, currentDepthSearched, currentMaxSearchDepth - currentDepthSearched,
                      alpha, beta);
              if (score != tt.lookupFailed) {nodesFromTT++;}
              if (score == tt.lookupFailed) {
                  nodesSearched++;
                  score = -negamaxFunction(btb, currentDepthSearched + 1, -beta, -alpha);
              }
              //int score = -negamaxFunction(depth + 1, -beta, -alpha);
              tt.addEval(btb.currentZobrist, score, alpha, beta, m, (currentMaxSearchDepth - currentDepthSearched));
              if (score &gt;= beta) {
                  btb.unmakeMove1Ply();
                  return beta;
              }
              btb.unmakeMove1Ply();
              if (score &gt; alpha) {
                  alpha = score;
                  if (currentDepthSearched == 0) {
                      bestMoveCurrentDepth = m;
                      bestEvalCurrentDepth = score * btb.turn;
                  }
              }
              /*if (currentDepthSearched == currentMaxSearchDepth - 1) {
                  if (score + 350 &lt; alpha) {
                      return alpha; //edit to return modified quiescence search
                  }
              }*/
          }
          return alpha;
      }
  
      public int quiescenceSearch(bitboard btb, int alpha, int beta, int quiescentStartDepth){
          //simple quiescent search
          //preQuiescentEval = evaluation before quiescent search began, in case captures/checks make position worse
          ArrayList&lt;Integer&gt; captures = new ArrayList&lt;&gt;();
          ArrayList&lt;Integer&gt; quietMoves = new ArrayList&lt;&gt;();
          ArrayList&lt;Integer&gt; checks = new ArrayList&lt;&gt;();
          mover.generateAllLegalMoves(btb.wp, btb.wn, btb.wb, btb.wr, btb.wq, btb.wk, btb.bp, btb.bn,
                  btb.bb, btb.br, btb.bq, btb.bk, btb.turn, btb.wCastle, btb.bCastle, btb.lastPawnJump,
                  captures, quietMoves, checks);
          if (captures.isEmpty() &amp;&amp; checks.isEmpty() &amp;&amp; quietMoves.isEmpty()) {
              switch (btb.turn) {
                  case (1) -&gt; {
                      if (mover.squareInCheck(Long.numberOfTrailingZeros(btb.wk), btb.bp, btb.bn, btb.bb, btb.br, btb.bq, btb.bk, btb.turn)) {
                          return MATE_SCORE + quiescentStartDepth * 10; //encourages engine to go for longer forced mates
                      } else {
                          return 0;
                      }
                  }
                  case (-1) -&gt; {
                      if (mover.squareInCheck(Long.numberOfTrailingZeros(btb.bk), btb.wp, btb.wn, btb.wb, btb.wr, btb.wq, btb.wk, btb.turn)) {
                          return MATE_SCORE + quiescentStartDepth * 10;
                      } else {
                          return 0;
                      }
                  }
              }
          }
          /*evaluate current position first. If not capturing is better than capturing, then alpha = currentpositioneval
          after looking for capture moves
           */
          int currentPosEval = evaluation.totalEval(btb); //stand pat evaluation
          if (currentPosEval &gt;= beta) { return beta;}
          if (currentPosEval &gt; alpha) {alpha = currentPosEval;}
          for (int m : captures) {
              btb.makeMove(m);
              int score = - quiescenceSearch(btb, -beta, -alpha, quiescentStartDepth + 1);
              btb.unmakeMove1Ply();
              if (score &gt;= beta) {
                  return beta;
              }
              if (score &gt; alpha) {
                  alpha = score;
              }
          }
          return alpha;
      }
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-27T02:56:29.527Z
Comments.Text: What is the output of a profiler?
Comments.UserDisplayName: qwr
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-27T18:50:15.923Z
Comments.Text: I may take a closer look later, but for now do you have node counts, both for total searched nodes and for qnodes? It might also simplify things to for now disable the transposition table to rule that out as a confounding factor for now.
Comments.UserDisplayName: koedem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-30T18:37:11.103Z
Comments.Text: @koedem sorry for the late reply, I do have node counts, but what are qnodes?
Comments.UserDisplayName: wdk23
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-31T09:08:18.300Z
Comments.Text: qnodes is how many nodes happen in the qsearch. You'd expect to have a number in the same ballpark as nodes outside of the qsearch. However, if you for example have 100 times as many qnodes as nodes outside of the qsearch then that would tell you that the qsearch is indeed the problem.
Comments.UserDisplayName: koedem
Tags: <engines><programming><chess-algorithms><minimax>
Title: Why is my negamax/quiescence search slow?
ThreadText: # Why is my negamax/quiescence search slow?
  
  (Asked by: username_0 on 2023-12-26)
  
  I'm currently making a chess engine in Java and my search function is extremely slow to the point that it's slower than my perft function. My search function is currently a negamax search that uses transposition tables, quiescence, and iterative deepening. For reference, I can run perft(depth = 6) with my move generator in 30-40 seconds, but running negamax takes a few minutes with the same depth.
  
  In terms of the rest of my engine, I'm using bitboards for move generation. For my evaluation function, I currently only have basic piece-square tables from the chess programming wiki because I want to focus on improving my search function first. I think it may be due to my quiescence function making the search slower but I don't know exactly how or why. I have attached my negamax and quiescence implementation below:
    
  btb = instance of bitboard class, tt = instance of transposition table. Both are instantiated once when the program is run.
  
  ```
      public int negamaxFunction(bitboard btb, int currentDepthSearched, int alpha, int beta) {
          if (btb.plyCount_50Move == 100) {
              return 0;
          }
          if (currentDepthSearched == currentMaxSearchDepth) {
              return quiescenceSearch(btb, alpha, beta, currentDepthSearched);
          }
          ArrayList<Integer> allMoves = new ArrayList<>();
          ArrayList<Integer> captures = new ArrayList<>();
          ArrayList<Integer> quietMoves = new ArrayList<>();
          ArrayList<Integer> checks = new ArrayList<>();
          mover.generateAllLegalMoves(btb.wp, btb.wn, btb.wb, btb.wr, btb.wq, btb.wk, btb.bp, btb.bn,
                  btb.bb, btb.br, btb.bq, btb.bk, btb.turn, btb.wCastle, btb.bCastle, btb.lastPawnJump,
                  captures, quietMoves, checks);
          allMoves.addAll(captures); allMoves.addAll(checks); allMoves.addAll(quietMoves);
          if (allMoves.isEmpty()) {
              switch (btb.turn) {
                  case (1) -> {
                      if (mover.squareInCheck(Long.numberOfTrailingZeros(btb.wk), btb.bp, btb.bn, btb.bb, btb.br, btb.bq, btb.bk, btb.turn)) {
                          return MATE_SCORE + currentDepthSearched * 10; //encourages engine to go for longer forced mates
                      } else {
                          return 0;
                      }
                  }
                  case (-1) -> {
                      if (mover.squareInCheck(Long.numberOfTrailingZeros(btb.bk), btb.wp, btb.wn, btb.wb, btb.wr, btb.wq, btb.wk, btb.turn)) {
                          return MATE_SCORE + currentDepthSearched * 10;
                      } else {
                          return 0;
                      }
                  }
              }
          }
  
          for (int m : allMoves) {
              boolean drawByRep = btb.makeMove(m);
              if (drawByRep) {return 0;}
              int score = tt.returnPastEval(btb.currentZobrist, currentDepthSearched, currentMaxSearchDepth - currentDepthSearched,
                      alpha, beta);
              if (score != tt.lookupFailed) {nodesFromTT++;}
              if (score == tt.lookupFailed) {
                  nodesSearched++;
                  score = -negamaxFunction(btb, currentDepthSearched + 1, -beta, -alpha);
              }
              //int score = -negamaxFunction(depth + 1, -beta, -alpha);
              tt.addEval(btb.currentZobrist, score, alpha, beta, m, (currentMaxSearchDepth - currentDepthSearched));
              if (score >= beta) {
                  btb.unmakeMove1Ply();
                  return beta;
              }
              btb.unmakeMove1Ply();
              if (score > alpha) {
                  alpha = score;
                  if (currentDepthSearched == 0) {
                      bestMoveCurrentDepth = m;
                      bestEvalCurrentDepth = score * btb.turn;
                  }
              }
              /*if (currentDepthSearched == currentMaxSearchDepth - 1) {
                  if (score + 350 < alpha) {
                      return alpha; //edit to return modified quiescence search
                  }
              }*/
          }
          return alpha;
      }
  
      public int quiescenceSearch(bitboard btb, int alpha, int beta, int quiescentStartDepth){
          //simple quiescent search
          //preQuiescentEval = evaluation before quiescent search began, in case captures/checks make position worse
          ArrayList<Integer> captures = new ArrayList<>();
          ArrayList<Integer> quietMoves = new ArrayList<>();
          ArrayList<Integer> checks = new ArrayList<>();
          mover.generateAllLegalMoves(btb.wp, btb.wn, btb.wb, btb.wr, btb.wq, btb.wk, btb.bp, btb.bn,
                  btb.bb, btb.br, btb.bq, btb.bk, btb.turn, btb.wCastle, btb.bCastle, btb.lastPawnJump,
                  captures, quietMoves, checks);
          if (captures.isEmpty() && checks.isEmpty() && quietMoves.isEmpty()) {
              switch (btb.turn) {
                  case (1) -> {
                      if (mover.squareInCheck(Long.numberOfTrailingZeros(btb.wk), btb.bp, btb.bn, btb.bb, btb.br, btb.bq, btb.bk, btb.turn)) {
                          return MATE_SCORE + quiescentStartDepth * 10; //encourages engine to go for longer forced mates
                      } else {
                          return 0;
                      }
                  }
                  case (-1) -> {
                      if (mover.squareInCheck(Long.numberOfTrailingZeros(btb.bk), btb.wp, btb.wn, btb.wb, btb.wr, btb.wq, btb.wk, btb.turn)) {
                          return MATE_SCORE + quiescentStartDepth * 10;
                      } else {
                          return 0;
                      }
                  }
              }
          }
          /*evaluate current position first. If not capturing is better than capturing, then alpha = currentpositioneval
          after looking for capture moves
           */
          int currentPosEval = evaluation.totalEval(btb); //stand pat evaluation
          if (currentPosEval >= beta) { return beta;}
          if (currentPosEval > alpha) {alpha = currentPosEval;}
          for (int m : captures) {
              btb.makeMove(m);
              int score = - quiescenceSearch(btb, -beta, -alpha, quiescentStartDepth + 1);
              btb.unmakeMove1Ply();
              if (score >= beta) {
                  return beta;
              }
              if (score > alpha) {
                  alpha = score;
              }
          }
          return alpha;
      }
  
  ```
  
  **Tags:** engines, programming, chess-algorithms, minimax
  
  > **Comments:**
  > **username_1**: What is the output of a profiler?  
  > **username_2**: I may take a closer look later, but for now do you have node counts, both for total searched nodes and for qnodes? It might also simplify things to for now disable the transposition table to rule that out as a confounding factor for now.  
  > **username_0**: @username_2 sorry for the late reply, I do have node counts, but what are qnodes?  
  > **username_2**: qnodes is how many nodes happen in the qsearch. You'd expect to have a number in the same ballpark as nodes outside of the qsearch. However, if you for example have 100 times as many qnodes as nodes outside of the qsearch then that would tell you that the qsearch is indeed the problem.  
  
  ---
  
  ## 0 answers
  
  