Differences

This shows you the differences between two versions of the page.

--- chess:programming:search:quiescence_search [2021/10/11 22:48] – created peter
+++ chess:programming:search:quiescence_search [2021/10/11 23:05] (current) – peter
@@ Line 1: / Line 1: @@
 ====== Chess - Programming - Search - Quiescence Search ======
+At the end of the main search a more limited quiescence search should be performed.
+  * The purpose of this search is to only evaluate "quiet" positions, or positions where there are no winning tactical moves to be made.
+  * This search is needed to avoid the __horizon effect__.
+  * Simply stopping a search when the desired depth is reached and then evaluated, is very dangerous.
+  * Consider the situation where the last move you consider is QxP.
+    * If the search is stopped there and evaluated, it might think that a pawn has been won.
+    * But what if the search was made one move deeper; and found that the next move is PxQ?
+    * A pawn has not really been won; instead a queen has been lost.
+    * Hence the need to make sure that only quiescent (quiet) positions are evaluated.
+Despite the fact that quiescence searches are typically very short, about 50%-90% nodes are spent there, so it is worthwhile to apply some pruning there.
+<code>
+int Quiesce( int alpha, int beta ) {
+    int stand_pat = Evaluate();
+    if( stand_pat >= beta )
+        return beta;
+    if( alpha < stand_pat )
+        alpha = stand_pat;
+    until( every_capture_has_been_examined )  {
+        MakeCapture();
+        score = -Quiesce( -beta, -alpha );
+        TakeBackMove();
+        if( score >= beta )
+            return beta;
+        if( score > alpha )
+           alpha = score;
+    }
+    return alpha;
+}
+</code>
+----
+===== References =====
+http://web.archive.org/web/20120427185347/http://chessprogramming.wikispaces.com/Quiescence+Search
+http://web.archive.org/web/20120420061736/http://chessprogramming.wikispaces.com/Pruning