Staged Quiesence

[JoAnnP38]

Via hearsay, I understand that SF uses a a staged quiescence search that seems to productively reduce required search depth in quiescence. My take on this is that I could alter my existing quiescence search to search moves as follows to also have a staged quiescence search:

1. 1st 2-ply of quiescence: Search all checks, promotions, captures + e.p. & check evasions (as-needed)
2. Next 4-ply: Search all captures & check evasions (as-needed)
3. The rest: Only search recaptures until stand-pat

The only little caveat is that in the transition between state 2 and 3 there may still be piece(s) en prise, but maybe that's okay hopefully this will end up reducing my B.F. enough to increase my overall search depth and still give good positional values. Has anyone else experimented with staged quiescence? All comments about my plan are welcome.

[hgm]

I think people have been searching checks in the first two ply for ages. In HaChu I limit the depth of QS to 5 ply, after which it evaluates by SEE. This was needed to prevent search explosion. In the Interactive Diagram, where search explosion is an even greater concern, I use a depth scheme without a clear distinction between QS and full-width, by extending all new captures a fractional ply, and only always search recaptures. Non-captures that are not new get reduced, or pruned when the remaining depth is smaller than the reduction. Pruned moves are replaced by stand-pat.

[JoAnnP38]

I think people have been searching checks in the first two ply for ages. In HaChu I limit the depth of QS to 5 ply, after which it evaluates by SEE. This was needed to prevent search explosion. In the Interactive Diagram, where search explosion is an even greater concern, I use a depth scheme without a clear distinction between QS and full-width, by extending all new captures a fractional ply, and only always search recaptures. Non-captures that are not new get reduced, or pruned when the remaining depth is smaller than the reduction. Pruned moves are replaced by stand-pat.

Interesting! I have thought about using my SEE to enforce a fixed depth limit on my quiescence search, but it currently doesn't consider pins or adjust the material balance of a capture involving a pawn promotion. However, I think I'm going to give that a try after searching recaptures for a few plies. There shouldn't be that many recaptures left after that so my SEE may not pose as big a risk as I imagine.

[JVMerlino]

Via hearsay, I understand that SF uses a a staged quiescence search that seems to productively reduce required search depth in quiescence. My take on this is that I could alter my existing quiescence search to search moves as follows to also have a staged quiescence search:

1. 1st 2-ply of quiescence: Search all checks, promotions, captures + e.p. & check evasions (as-needed)
2. Next 4-ply: Search all captures & check evasions (as-needed)
3. The rest: Only search recaptures until stand-pat

The only little caveat is that in the transition between state 2 and 3 there may still be piece(s) en prise, but maybe that's okay hopefully this will end up reducing my B.F. enough to increase my overall search depth and still give good positional values. Has anyone else experimented with staged quiescence? All comments about my plan are welcome.

Long ago I had some code to limit qsearch to recaptures after ply 4. As HG stated, this was to prevent search explosion in my weak and slow engine. When I converted to bitboards I disabled the code, as the gain was no longer obvious. I re-enabled the code for a test and, while promising, I still need more games to be sure. The current result is +7 elo, but +/- 17 elo.

[expositor]

Expositor has used a staged quiescing search since the beginning; these two comments explain the policy:
https://github.com/expo-dev/expositor/b ... gen.rs#L12
https://github.com/expo-dev/expositor/b ... lve.rs#L40

I'm not sure how it compares with any other engines' staged quiescing (in fact, until this post, I didn't realize anyone else did something similar).

Unfortunately, I can't tell you whether this gains or loses Elo – I never bothered to measure. I thought it was interesting and would've kept it regardless, but perhaps one day I'll revisit it and change my mind ^_^'

I did tune the length* numbers a bit that determine the selectivity by looking at the mean absolute error** and number of expanded nodes for a smallish corpus of positions. I adjusted them to decrease the node count until the error started creeping up.


*My term for "distance from the leaf node of the main search tree" (the root of the quiescing search), whereas height is distance from the root of the (main) search tree.

**Between the result of the quiescing search and an actual search, after mapping both through a sigmoid.

[JoAnnP38]

Expositor has used a staged quiescing search since the beginning; these two comments explain the policy:
https://github.com/expo-dev/expositor/b ... gen.rs#L12
https://github.com/expo-dev/expositor/b ... lve.rs#L40

I'm not sure how it compares with any other engines' staged quiescing (in fact, until this post, I didn't realize anyone else did something similar).

Unfortunately, I can't tell you whether this gains or loses Elo – I never bothered to measure. I thought it was interesting and would've kept it regardless, but perhaps one day I'll revisit it and change my mind ^_^'

I did tune the length* numbers a bit that determine the selectivity by looking at the mean absolute error** and number of expanded nodes for a smallish corpus of positions. I adjusted them to decrease the node count until the error started creeping up.


*My term for "distance from the leaf node of the main search tree" (the root of the quiescing search), whereas height is distance from the root of the (main) search tree.

**Between the result of the quiescing search and an actual search, after mapping both through a sigmoid.

I am currently testing for Elo gain now based on the implementation I described above. If nothing else I'm coming out of this with a method for generating check-evasion moves which I didn't have before. It's looking like this might provide ~ 10 Elo gain, but will need to let the test finish and I'll post the results.

[JoAnnP38]

Long ago I had some code to limit qsearch to recaptures after ply 4. As HG stated, this was to prevent search explosion in my weak and slow engine. When I converted to bitboards I disabled the code, as the gain was no longer obvious. I re-enabled the code for a test and, while promising, I still need more games to be sure. The current result is +7 elo, but +/- 17 elo.

I just finished a test that had about the same results. It was a little different that I had initially laid out. It doesn't now generate checking moves in the first two ply as I had planned. However, I extend the main search one full ply for every safe check so maybe I need this until I switch to fractional extensions. My initial test results are:

Code: Select all

Score of Pedantic 0.3A vs Pedantic 0.3B: 465 - 424 - 1111  [0.510] 2000
...      Pedantic 0.3A playing White: 267 - 176 - 557  [0.545] 1000
...      Pedantic 0.3A playing Black: 198 - 248 - 554  [0.475] 1000
...      White vs Black: 515 - 374 - 1111  [0.535] 2000
Elo difference: 7.1 +/- 10.1, LOS: 91.5 %, DrawRatio: 55.5 %

I'm going to commit this change and run a sprt test to verify. But 7 elo would be fine if it hangs around there.

[JVMerlino]

Long ago I had some code to limit qsearch to recaptures after ply 4. As HG stated, this was to prevent search explosion in my weak and slow engine. When I converted to bitboards I disabled the code, as the gain was no longer obvious. I re-enabled the code for a test and, while promising, I still need more games to be sure. The current result is +7 elo, but +/- 17 elo.

I just finished a test that had about the same results. It was a little different that I had initially laid out. It doesn't now generate checking moves in the first two ply as I had planned. However, I extend the main search one full ply for every safe check so maybe I need this until I switch to fractional extensions. My initial test results are:

Code: Select all

Score of Pedantic 0.3A vs Pedantic 0.3B: 465 - 424 - 1111  [0.510] 2000
...      Pedantic 0.3A playing White: 267 - 176 - 557  [0.545] 1000
...      Pedantic 0.3A playing Black: 198 - 248 - 554  [0.475] 1000
...      White vs Black: 515 - 374 - 1111  [0.535] 2000
Elo difference: 7.1 +/- 10.1, LOS: 91.5 %, DrawRatio: 55.5 %

I'm going to commit this change and run a sprt test to verify. But 7 elo would be fine if it hangs around there.

No such luck here. Further testing brought it down to +3.8 +/- 12.5.

[rdhoffmann]

I simply use a "pyramid" starting with a bunch of moves on the first ply then gradually narrowing towards zero. At the end of the day it is similar to what you are doing. I don't get the capture-recapture idea though, isn't it worse than just making the best MVV capture?

[JoAnnP38]

The recapture is sort of like an advanced SEE because it can account for pins, material changes due to promotions, e.p. etc. Because I only consider recaptures on the square of the prior move it drastically limits how deep the search can go which in one sense is what I was trying to accomplish.