Starting with quiescence search

[Luis Babboni]

Hi people,

I´m starting with the target to add quiescence search to my engine and have my first question:

Suppouse at depth d there are (to simplify) 4 possible positions (p1,p2,p3 and p4) where the odds one (1 and 3) deservs a deeper search (p1d and p3d). The question is about in wich order quiescence search will study the tree?:

a) p1, p2, p3, p4, p1d, p3d.

b) p1, p1d, p2, p3, p3d, p4.

Thanks!

[hgm]

(b)

QS isn't really different from normal search. You always first search all daughter nodes that you want to search, and determine the score of the current node based on the score of these daughters. The difference between the QS part and the full-width part of the tree is that in the QS part you only search captures, and assume all non-captures will not change the score compared towhat it currently is. (I.e. include the static evaluation instead of any non-captures in the set of possible actions from which you take the best. This is usually implemented by trying the static evaluation first, in the hope this will cause a beta cutoff so that you never get to searching any captures.)

[Sven]

See also https://chessprogramming.wikispaces.com ... nce+Search

[Luis Babboni]

See also https://chessprogramming.wikispaces.com ... nce+Search

Thanks Sven, I did, and this was what made me wonder:

"...Most chess programs, at the end of the main search perform a more limited quiescence search..."

[Luis Babboni]

Thanks H.G.!

I´do not understand since this point of your explanation:

(b)
...
and assume all non-captures will not change the score compared towhat it currently is. (I.e. include the static evaluation instead of any non-captures in the set of possible actions from which you take the best. This is usually implemented by trying the static evaluation first, in the hope this will cause a beta cutoff so that you never get to searching any captures.)

I evaluate the positions at the end nodes.
An end-node was for me till now depth=maximumdepth.
What I´m trying to do is to understand a capture as a no-end node and just go one ply further.

What about include checks not just captures?
It seems cause my code is far simplier to me to include just captures than include captures and checks.

[hgm]

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).

[Luis Babboni]

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.

[Sven]

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.

[Luis Babboni]

...
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).

What about promotions?
As first step in quiescence search implement, Is suggested to be included as captures or not as checks?

Thanks!

...
Consider this simple opening position
...

Sorry Sven, I just see it now, I´ll read it and comment, thanks!

[Luis Babboni]

Sven answer read!

Is what I was understood except one thing I understand I´m not sure if it is what you is saying.

You said that if some capture not improve the score (cause for example the value of the piece you captured is less than the score yor lost cause the worst position you reach after did it) you could stop the search as there was not capture to do?
Sounds good no matter actualy for my evaluation that just consider material has not relevance.