Luis Babboni wrote:hgm wrote:To implement QS you can evaluate the postion when depth >= maximumdepth, and then see if any captures do better than that. (And if not, stick with the evaluation score.) So it is simply a matter of (in case depth >= maximumdepth) not returning the evaluation, but using it as a start value for determining the best score (so that in the end it gets returned if nothing was better). And then skip (i.e. prune) all non-captures.
You have to be very careful doing checks in QS, as this easily leads to search explosion. You will always run out of captures, but you might never run out of checks. So you have to put some artificial limit to checks, e.g.only doing them in the first (few) levels of QS. Better leave that for later, as it is only of minor importance (compatred to having QS).
Thanks for the 2nd answer, still need to think about the first.
Consider this simple opening position that you reach while doing a 4-ply search from the starting position.
[D]r1bqkbnr/pppp1ppp/2n5/4p3/4P3/5N2/PPPP1PPP/RNBQKB1R w KQkq - 0 3
Speaking in the terminology that was used above you have maximumdepth = 4 and depth = 4, so depth >= maximumdepth. (More common is to use "depth" for the remaining full-width depth so you start QS at depth = 0, but that is another topic.)
So this is a terminal node of the full-width search and you start a quiescence search (QS) to find out whether the side to move (here White) can improve its score by capturing (or promoting a pawn), where all replies of the opponent and of the moving side itself are limited to captures and promotions as well. Let's ignore the topics "check extension" (i.e. extend full-width search when being in check) and "checks in QS" (i.e. try also quiet moves giving check within the first N plies of QS) at this point.
The basic assumption of QS is: we strongly believe that none of the "quiet" moves (those that we will not try during QS) would lose material or otherwise lower the evaluation from the viewpoint of the moving side. So the current evaluation is "safe" under this assumption, and we try whether any capture (or promotion) improves the score. If none of the captures improves the score then we stick with the static evaluation, which looks the same as if we "do nothing". Therefore we use the term "stand pat".
This assumption can fail in some situations. Apart from being in check (which is usually not a situation where it makes sense to do QS) typical cases include hanging pieces, mate threats, or zugzwang. Resolving those kinds of tactics correctly is not the task of QS, and since QS only occurs deep down in the tree the impact of missing such tactics during QS on the final root score is statistically quite low with high search depths.
Now let's return to the example position above. Initially I want to ignore alpha-beta for simplicity. Let's say your static evaluation uses 100 for a pawn and 300 for a knight. It returns a score of 0 for that position.
Now you try whether White can improve on that by capturing. Move generation in QS only covers captures and promotions (but promotions are far away here), so there is just one move to consider: 1.Nxe5.
[D]r1bqkbnr/pppp1ppp/2n5/4N3/4P3/8/PPPP1PPP/RNBQKB1R b KQkq - 0 3
After making the move it is Black's turn, and the same QS algorithm repeats from viewpoint of Black (recursive call).
Evaluation returns -100 (one pawn down, scores always relative to moving side), and you try whether any capture improves on that. Only capture to consider for Black is 1...Nxe5.
[D]r1bqkbnr/pppp1ppp/8/4n3/4P3/8/PPPP1PPP/RNBQKB1R w KQkq - 0 4
Recursive QS call again, it's White's turn. Static evaluation returns -200 from White viewpoint (only a pawn for a knight). Try whether captures improve on that - there are none. So you return -200 to the level above where Black sees this as +200 ("score = -QS(...)"). This is the score for the move 1...Nxe5 by Black, and since +200 > -100 it certainly improves the score, so the new best score for Black is +200. Since there is no other capture we return +200 to the level above. White sees this as -200, so the conclusion is that 1.Nxe5 does not improve the score for White (it would actually lose a knight) so the best score remains 0 as returned initially by the static evaluation. Since there is no other capture for White we are done, QS returns 0. White accepts the static evaluation score since any captures would lose.
The example is (hopefully) simple enough to understand without introducing alpha-beta. However, in reality chess positions are much more complex on average, allowing many more captures, so the QS tree would explode heavily without alpha-beta. In QS you use alpha-beta basically in the same way as in full-width search, by checking whether the score returned from a subtree causes a beta cutoff. Additionally you also check whether the stand-pat score (static eval) is already >= beta so that you can skip trying any captures at all and return immediately.
Once you understood these basics it will be fairly easy to implement it.