Answers.Body: <p>Because you said</p>
  
  <blockquote>
    <p>Without limiting the allowed depth of the Quiescence Search, my program ran for multiple minutes without any result</p>
  </blockquote>
  
  <p>I'm assuming that you haven't implemented any capture ordering in your quiescence search. </p>
  
  <p>When you don't do this, you allow your computer to calculate rather silly situations very deeply. For instance, say I have one capture: my queen takes your (defended) pawn. This is obviously a bad choice, and we want your computer to recognize this quickly. </p>
  
  <p>You could simply recapture (choice A), but you have another capture available (choice B) your bishop takes my pawn. Say for the sake of example that these are the only two available captures. You now have two options for searching these moves:</p>
  
  <p>First B, then A</p>
  
  <p>If you search B first, my queen might have the option to take another piece (now that it has moved to a different square). You'll call the quiescence function again (maybe your bishop can now take another piece) and after that, maybe my queen can take yet another piece. You're calling the quiescence function over and over again. It'll have to end at some point, but when you're doing this for <em>every</em> leaf node, this takes time. </p>
  
  <p>First A, then B</p>
  
  <p>If you search A first, I will no longer have a queen with which to take pieces, meaning I am substantially less likely to have to have more captures available, meaning your quiescence search will likely stop here. Then, when you inevitably search B, you will be much more likely to create a beta cutoff because capturing the queen with a pawn was given a very high value.</p>
  
  <hr>
  
  <p>Hopefully this illustrates the importance of move ordering in quiescence search.</p>
  
  <p>The way we typically do this is with MVV/LVA, which stands for "most valuable victim, least valuable attacker," which does exactly what it sounds like. For each capture, compute the value of the victim minus the value of the attacker, then search the largest captures first. This should massively reduce your qsearch times.</p>
  
  <p>All this being said, limiting your qserach is sometimes a legitimate thing to do, (is it <em>actually</em> useful to see the 10th capture in a row?) but first you should see how the capture ordering shakes out, then make a decision.</p>
  
  <p>Hope it helps.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-10T17:23:57.093Z
Answers.Text: wow this answer is great! Thank you very much. Would this ordering also help in alpha-beta search?
Answers.UserDisplayName: Finn Eggers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-10T17:30:20.813Z
Answers.Text: I just did that and it reduced the amount of checked nodes by a factor of 5.
Answers.UserDisplayName: Finn Eggers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-10T18:13:07.850Z
Answers.Text: Glad I could help! And yes, alpha/beta benefits (quite a lot) from move ordering techniques. In fact, I assumed you were aware of them when writing my answer. As I said, searching A before B makes it more likely to create a beta cutoff. The same principle applies to normal alpha/beta search: if you search the good moves first, alpha/beta will be more efficient. The actual ordering mechanisms are usually more complicated than MVV/LVA, but core idea is the same.
Answers.UserDisplayName: Noah Caplinger
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-10T18:16:35.613Z
Answers.Text: I will also go ahead and implement iterative deepening which should be a huge improvement.
  
  Just one last question on that. Basicaly the last principal variation line is only included in the first called node, right? Basically only for the left-most nodes in the alpha-beta tree.
Answers.UserDisplayName: Finn Eggers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-10T18:41:56.120Z
Answers.Text: I'm not entirely sure what you mean by "the principal variation line is only included in the first called node," but the basic idea of iterative deepening is that after each iteration, you can order the nodes using the previous iteration. This means that the first move of the principal variation of the previous iteration will be searched first, along with the other moves, in descending order of value.
Answers.UserDisplayName: Noah Caplinger
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-10T19:26:17.070Z
Answers.Text: Yeah okay that's what I meant. for me the 'leftmost node' is the one that is traversed first and this equals the principal variation of the previous iteration.
Answers.UserDisplayName: Finn Eggers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-27T21:34:43.440Z
Answers.Text: How does this relate to the killer heuristic? Would you use killer heuristic instead of MVV/LVA, or in addition to it?
Answers.UserDisplayName: user134593
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-10T04:44:44.847Z
Answers.LastActivityDate: 2019-12-10T08:02:54.693Z
Answers.LastEditDate: 2019-12-10T08:02:54.693Z
Answers.UserDisplayName: Noah Caplinger
Answers.Body: <p>The point of a quiescence search(QSearch) is to get a better static evaluation.  By the number of nodes your searching, it seems that your just extending your main search function.  By limiting your QSearch to only captures, promotions and maybe checks, you should greatly reduce the QSearch.</p>
  <p>An interesting observation is that QSearch is the function mainly used to call the evaluation function.  This is the most time consuming function, so the QSearch would account for the most time used.</p>
  <p><a href="https://web.archive.org/web/20201106232751/members.home.nl/matador/Inside%20Rebel.pdf" rel="nofollow noreferrer">https://web.archive.org/web/20201106232751/members.home.nl/matador/Inside%20Rebel.pdf</a> is a useful reference.</p>
  <p>Note:  By providing some code, it would be easier to suggest a better answer.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-10T17:22:31.807Z
Answers.Text: I added my code. Thank you for the link! It looks promising allthough there are some aspects that I did not include in my program like checkmate etc. the game ends if the king is taken. this is much simpler to implement. I could implement that those moves are forbidden when actually playing but they are allowed when searching
Answers.UserDisplayName: Finn Eggers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-10T05:22:05.933Z
Answers.LastActivityDate: 2022-09-02T20:03:05.477Z
Answers.LastEditDate: 2022-09-02T20:03:05.477Z
Answers.UserDisplayName: Mike Jones
Answers.Body: <p>I am speculating that you have too many quiet positions to continue with the quiescence checking, especially at that extra depth.   You will have to limit the number of extra quiescent moves you check or get a faster computer; or be willing to wait longer for an answer.    </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T19:03:49.800Z
Answers.Text: So I got a pretty good result when limiting it to a depth of 2. Is this allowed?
Answers.UserDisplayName: Finn Eggers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T19:06:40.067Z
Answers.Text: @FinnEggers -  if you are happy with the results you may certain do that without anyone elses approval.
Answers.UserDisplayName: yobamamama
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T19:07:32.763Z
Answers.Text: Okay thank you! Should I include things like move-ordering and hashing also for the Quiescence Search?
Answers.UserDisplayName: Finn Eggers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T19:09:20.480Z
Answers.Text: @FinnEggers -- Now you are getting past my experience with this sort of programming.  I would expect that the Quiescent search would be more of the normal search method just to verify no funny surprises could happen.  On a philosophical bent,  why don't programmers then do a quiescent search on the results of the quiescent search just done .... ad infinitum.    At some point  you have to say this is what I can do and just stop.
Answers.UserDisplayName: yobamamama
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T19:10:12.057Z
Answers.Text: Okay so basically it is a normal search but only for moves that will capture. Thank you very much!
Answers.UserDisplayName: Finn Eggers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T19:11:57.337Z
Answers.Text: Yes and no.  Captures may occur.  mate could happen.  It is ensure there are no oddball surprises that undo the tentative evaluation of that path.
Answers.UserDisplayName: yobamamama
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T19:12:49.963Z
Answers.Text: according to: https://www.chessprogramming.org/Quiescence_Search
  only captures are checked
Answers.UserDisplayName: Finn Eggers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T19:16:04.097Z
Answers.Text: That is your call.  It would simplify and speed up that part of the search.  I would think you still need to look at checks.  Be embarassing to have a mate in one and not check because it was not a capture.
Answers.UserDisplayName: yobamamama
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T19:17:53.220Z
Answers.Text: yes that is correct. problem with that is that it would rise the complexity. my code is very simple. no bitboards, no castling, no en passent and no mate checking. even moves where the king places himself into checkmate are kinda allowed allthough the game will end after that.
  
  So I will probably stick with only captures :)
  Thank you for your help!
Answers.UserDisplayName: Finn Eggers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T21:26:06.667Z
Answers.Text: You are certainly welcome for any help I provided.
Answers.UserDisplayName: yobamamama
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T19:02:44.907Z
Answers.LastActivityDate: 2019-12-09T19:02:44.907Z
Answers.UserDisplayName: yobamamama
Body: <p>I am currently trying to implement a basic chess engine and got to the following point:</p>
  
  <p>I have got Alpha-Beta Pruning implemented and extended it with a transposition table. To further increase stability I implemented Quiescence Search and this is where I ran into problems.</p>
  
  <p>The result clearly looked better but the required time for this was out of this world.</p>
  
  <p>I was using Alpha-Beta pruning with a depth of 6 half-moves. Each evaluation was carried out by Quiescence Search. Without limiting the allowed depth of the Quiescence Search, my program ran for multiple minutes without any result. I limited the depth of the Quiescence Search 10 half-moves and got to the following result for the second move:</p>
  
  <pre><code>visited nodes:   6915527     
  quiescent nodes:   104313894    
  &gt;&gt;&gt; 79502 ms &lt;&lt;&lt;
  </code></pre>
  
  <p>Without Quiescence Search (the listed quiescent nodes are the leafs of the main tree)</p>
  
  <pre><code>visited nodes:   8472808    
  quiescent nodes:   4978606    
  &gt;&gt;&gt; 9227 ms &lt;&lt;&lt;
  </code></pre>
  
  <p>You can see that the Quiescence Search takes up most of the time. </p>
  
  <p>What could I do to improve the time my engine needs?</p>
  
  <hr>
  
  <pre><code>private double alphaBetaSearch(double alpha, double beta, int currentDepth) {
      _visitedNodes ++;
      long zobrist = _board.zobrist();
      double transposition = transpositionLookUp(zobrist, currentDepth);
      if(!Double.isNaN(transposition)){
          return transposition;
      }
  
      List&lt;Move&gt; allMoves = _board.getAvailableMoves();
      if(currentDepth == _depth || allMoves.size() == 0 || _board.isGameOver()){
          double val = Quiesce(alpha, beta,quiesce_depth );
          transpositionPlacement(zobrist, currentDepth, val);
          return val;
      }
  
      orderer.sort(allMoves,currentDepth,zobrist,_transpositionTable_pv);
  
      for (Move m : allMoves) {
          _board.move(m);
          double score = -alphaBetaSearch(-beta, -alpha, currentDepth + 1);
          _board.undoMove();
          if (score &gt;= beta) {
              transpositionPlacement(zobrist, m);
              return beta;
          }
          if (score &gt; alpha) {
              transpositionPlacement(zobrist, m);
              alpha = score;
              if (currentDepth == 0) {
                  _bestMove = m;
              }
          }
      }
  
      transpositionPlacement(zobrist, currentDepth, alpha);
  
      return alpha;
  }
  
  
  private double Quiesce(double alpha, double beta, int depth_left) {
      _quiesceNodes ++;
      _evaluatedNodes ++;
      double stand_pat = evaluator.evaluate(_board) * _board.getActivePlayer();
      if(depth_left == 0){
          return stand_pat;
      }
      if( stand_pat &gt;= beta)
          return beta;
      if( alpha &lt; stand_pat )
          alpha = stand_pat;
  
  
      List&lt;Move&gt; allMoves = _board.getAvailableMoves();
  
      for(Move m:allMoves){
          if(m.getPieceTo() * m.getPieceFrom() &lt; 0){
  
              _board.move(m);
              double score = -Quiesce( -beta, -alpha, depth_left-1);
              _board.undoMove();
  
              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: 2019-12-10T15:27:33.683Z
Comments.Text: This seems like a case of (quiescence) search explosion (check also the links provided):
  
  https://www.chessprogramming.org/Quiescence_Search
  
  https://www.chessprogramming.org/Search_Explosion
Comments.UserDisplayName: emdio
Tags: <engines><time-management>
Title: Chess engine: Quiescence Search increases required time by a factor of 20
ThreadText: # Chess engine: Quiescence Search increases required time by a factor of 20
  
  (Asked by: username_0 on 2019-12-09)
  
  I am currently trying to implement a basic chess engine and got to the following point:
  
  I have got Alpha-Beta Pruning implemented and extended it with a transposition table. To further increase stability I implemented Quiescence Search and this is where I ran into problems.
  
  The result clearly looked better but the required time for this was out of this world.
  
  I was using Alpha-Beta pruning with a depth of 6 half-moves. Each evaluation was carried out by Quiescence Search. Without limiting the allowed depth of the Quiescence Search, my program ran for multiple minutes without any result. I limited the depth of the Quiescence Search 10 half-moves and got to the following result for the second move:
  
  ```
  visited nodes:   6915527     
  quiescent nodes:   104313894    
  >>> 79502 ms <<<
  
  ```
  
  Without Quiescence Search (the listed quiescent nodes are the leafs of the main tree)
  
  ```
  visited nodes:   8472808    
  quiescent nodes:   4978606    
  >>> 9227 ms <<<
  
  ```
  
  You can see that the Quiescence Search takes up most of the time.
  
  What could I do to improve the time my engine needs?
  
  ---
  
  ```
  private double alphaBetaSearch(double alpha, double beta, int currentDepth) {
      _visitedNodes ++;
      long zobrist = _board.zobrist();
      double transposition = transpositionLookUp(zobrist, currentDepth);
      if(!Double.isNaN(transposition)){
          return transposition;
      }
  
      List<Move> allMoves = _board.getAvailableMoves();
      if(currentDepth == _depth || allMoves.size() == 0 || _board.isGameOver()){
          double val = Quiesce(alpha, beta,quiesce_depth );
          transpositionPlacement(zobrist, currentDepth, val);
          return val;
      }
  
      orderer.sort(allMoves,currentDepth,zobrist,_transpositionTable_pv);
  
      for (Move m : allMoves) {
          _board.move(m);
          double score = -alphaBetaSearch(-beta, -alpha, currentDepth + 1);
          _board.undoMove();
          if (score >= beta) {
              transpositionPlacement(zobrist, m);
              return beta;
          }
          if (score > alpha) {
              transpositionPlacement(zobrist, m);
              alpha = score;
              if (currentDepth == 0) {
                  _bestMove = m;
              }
          }
      }
  
      transpositionPlacement(zobrist, currentDepth, alpha);
  
      return alpha;
  }
  
  private double Quiesce(double alpha, double beta, int depth_left) {
      _quiesceNodes ++;
      _evaluatedNodes ++;
      double stand_pat = evaluator.evaluate(_board) * _board.getActivePlayer();
      if(depth_left == 0){
          return stand_pat;
      }
      if( stand_pat >= beta)
          return beta;
      if( alpha < stand_pat )
          alpha = stand_pat;
  
      List<Move> allMoves = _board.getAvailableMoves();
  
      for(Move m:allMoves){
          if(m.getPieceTo() * m.getPieceFrom() < 0){
  
              _board.move(m);
              double score = -Quiesce( -beta, -alpha, depth_left-1);
              _board.undoMove();
  
              if( score >= beta )
                  return beta;
              if( score > alpha )
                  alpha = score;
          }
      }
  
      return alpha;
  }
  
  ```
  
  **Tags:** engines, time-management
  
  > **Comments:**
  > **username_1**: This seems like a case of (quiescence) search explosion (check also the links provided):  https://www.chessprogramming.org/Quiescence_Search  https://www.chessprogramming.org/Search_Explosion  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2019-12-10. Score: 7 | Accepted answer
  
  Because you said
  
  > Without limiting the allowed depth of the Quiescence Search, my program ran for multiple minutes without any result
  
  I'm assuming that you haven't implemented any capture ordering in your quiescence search.
  
  When you don't do this, you allow your computer to calculate rather silly situations very deeply. For instance, say I have one capture: my queen takes your (defended) pawn. This is obviously a bad choice, and we want your computer to recognize this quickly.
  
  You could simply recapture (choice A), but you have another capture available (choice B) your bishop takes my pawn. Say for the sake of example that these are the only two available captures. You now have two options for searching these moves:
  
  First B, then A
  
  If you search B first, my queen might have the option to take another piece (now that it has moved to a different square). You'll call the quiescence function again (maybe your bishop can now take another piece) and after that, maybe my queen can take yet another piece. You're calling the quiescence function over and over again. It'll have to end at some point, but when you're doing this for *every* leaf node, this takes time.
  
  First A, then B
  
  If you search A first, I will no longer have a queen with which to take pieces, meaning I am substantially less likely to have to have more captures available, meaning your quiescence search will likely stop here. Then, when you inevitably search B, you will be much more likely to create a beta cutoff because capturing the queen with a pawn was given a very high value.
  
  ---
  
  Hopefully this illustrates the importance of move ordering in quiescence search.
  
  The way we typically do this is with MVV/LVA, which stands for "most valuable victim, least valuable attacker," which does exactly what it sounds like. For each capture, compute the value of the victim minus the value of the attacker, then search the largest captures first. This should massively reduce your qsearch times.
  
  All this being said, limiting your qserach is sometimes a legitimate thing to do, (is it *actually* useful to see the 10th capture in a row?) but first you should see how the capture ordering shakes out, then make a decision.
  
  Hope it helps.
  
  > **Comments:**
  > **username_0**: wow this answer is great! Thank you very much. Would this ordering also help in alpha-beta search?  
  > **username_0**: I just did that and it reduced the amount of checked nodes by a factor of 5.  
  > **username_2**: Glad I could help! And yes, alpha/beta benefits (quite a lot) from move ordering techniques. In fact, I assumed you were aware of them when writing my answer. As I said, searching A before B makes it more likely to create a beta cutoff. The same principle applies to normal alpha/beta search: if you search the good moves first, alpha/beta will be more efficient. The actual ordering mechanisms are usually more complicated than MVV/LVA, but core idea is the same.  
  > **username_0**: I will also go ahead and implement iterative deepening which should be a huge improvement.  Just one last question on that. Basicaly the last principal variation line is only included in the first called node, right? Basically only for the left-most nodes in the alpha-beta tree.  
  > **username_2**: I'm not entirely sure what you mean by "the principal variation line is only included in the first called node," but the basic idea of iterative deepening is that after each iteration, you can order the nodes using the previous iteration. This means that the first move of the principal variation of the previous iteration will be searched first, along with the other moves, in descending order of value.  
  > **username_0**: Yeah okay that's what I meant. for me the 'leftmost node' is the one that is traversed first and this equals the principal variation of the previous iteration.  
  > **username_3**: How does this relate to the killer heuristic? Would you use killer heuristic instead of MVV/LVA, or in addition to it?  
  
  ---
  
  ### Answer by username_4 on 2019-12-10. Score: 2
  
  The point of a quiescence search(QSearch) is to get a better static evaluation. By the number of nodes your searching, it seems that your just extending your main search function. By limiting your QSearch to only captures, promotions and maybe checks, you should greatly reduce the QSearch.
  
  An interesting observation is that QSearch is the function mainly used to call the evaluation function. This is the most time consuming function, so the QSearch would account for the most time used.
  
  <https://web.archive.org/web/20201106232751/members.home.nl/matador/Inside%20Rebel.pdf> is a useful reference.
  
  Note: By providing some code, it would be easier to suggest a better answer.
  
  > **Comments:**
  > **username_0**: I added my code. Thank you for the link! It looks promising allthough there are some aspects that I did not include in my program like checkmate etc. the game ends if the king is taken. this is much simpler to implement. I could implement that those moves are forbidden when actually playing but they are allowed when searching  
  
  ---
  
  ### Answer by username_5 on 2019-12-09. Score: 2
  
  I am speculating that you have too many quiet positions to continue with the quiescence checking, especially at that extra depth. You will have to limit the number of extra quiescent moves you check or get a faster computer; or be willing to wait longer for an answer.
  
  > **Comments:**
  > **username_0**: So I got a pretty good result when limiting it to a depth of 2. Is this allowed?  
  > **username_5**: @username_0 -  if you are happy with the results you may certain do that without anyone elses approval.  
  > **username_0**: Okay thank you! Should I include things like move-ordering and hashing also for the Quiescence Search?  
  > **username_5**: @username_0 -- Now you are getting past my experience with this sort of programming.  I would expect that the Quiescent search would be more of the normal search method just to verify no funny surprises could happen.  On a philosophical bent,  why don't programmers then do a quiescent search on the results of the quiescent search just done .... ad infinitum.    At some point  you have to say this is what I can do and just stop.  
  > **username_0**: Okay so basically it is a normal search but only for moves that will capture. Thank you very much!  
  > **username_5**: Yes and no.  Captures may occur.  mate could happen.  It is ensure there are no oddball surprises that undo the tentative evaluation of that path.  
  > **username_0**: according to: https://www.chessprogramming.org/Quiescence_Search only captures are checked  
  > **username_5**: That is your call.  It would simplify and speed up that part of the search.  I would think you still need to look at checks.  Be embarassing to have a mate in one and not check because it was not a capture.  
  > **username_0**: yes that is correct. problem with that is that it would rise the complexity. my code is very simple. no bitboards, no castling, no en passent and no mate checking. even moves where the king places himself into checkmate are kinda allowed allthough the game will end after that.  So I will probably stick with only captures :) Thank you for your help!  
  > **username_5**: You are certainly welcome for any help I provided.  
  
  ---
  
  