Quiescence Search Explosions

[xsadar]

I just implemented a quiescence search for the first time, and it definitely seems to be an improvement early and late in the game. However, during the middle-game it tends to explode. I was wondering if people had suggestions on how to keep it under control.

It does a full-depth alpha-beta search on all promotions and captures. My move ordering could likely contribute to the problem, as it's not the best. They're simply ordered the way I generate them, which is as follows:

Stand Pat (not a move, but I check this first, naturally)
Promotions with captures: (PxQ=Q . . . PxQ=N) . . . (PxN=Q . . . PxN=N)
Other Promotions: P=Q . . . P=N
All other captures in the following order:
PxQ . . . PxP
NxQ . . . NxP
BxQ . . . BxP
RxQ . . . RxP
QxQ . . . QxP
KxQ . . . KxP

I tried hashing the QS nodes, but that seemed to have little impact, if any.
I also wondered if maybe I should use SEE to prune away some losing captures.

[hgm]

It is better to sort by victim as primary sort key, than by attacker. Although your ordering does not seem extremely bad, you might try a regular MVV/LVA ordering to see if that solves your problem.

Next step would be to push High x Low captures of defended piece backwards, or run a SEE on them to decide if they are any good. And then you can even prune them if they are no good.

[Gerd Isenberg]

Other Promotions: P=Q . . . P=N
All other captures in the following order:
PxQ . . . PxP
NxQ . . . NxP
BxQ . . . BxP
RxQ . . . RxP
QxQ . . . QxP
KxQ . . . KxP

Capturing en-prise queen/rook/bishop/knight should be tried before capturing pawns or equal captures.

PxQ, KxQ, NBxQ, RxQ, QxQ (see>0),
PxR, KxR, NBxR, RxR (see>0),
PxNB,KxNB,NBxNB (see>0),
QxR(see>0),RxNB(see>0),
PxP(see>0),...

Of course you should prune, if eval + maxgain is still less/equal alpha.

[CThinker]

One may even get away with not doing SEE for potentially equal captures (QxQ, RxR, BxB, BxN, NxB, NxN).

[hgm]

For equal captures it is indeed better to simply make the highest capture first, even if it has SEE=0, and there are other captures with SEE>0. Almost always you can do the SEE>0 capture anyway, as taking the highest piece keeps the opponent under maximum pressure to recapture. And simplifying first by trading the highest piece will make it less likely he can do something nasty with that piece. (Equal captures are often reciprocal!) First pull the teeth of your prey, before you start eating him!

[Gerd Isenberg]

For equal captures it is indeed better to simply make the highest capture first, even if it has SEE=0, and there are other captures with SEE>0. Almost always you can do the SEE>0 capture anyway, as taking the highest piece keeps the opponent under maximum pressure to recapture. And simplifying first by trading the highest piece will make it less likely he can do something nasty with that piece. (Equal captures are often reciprocal!) First pull the teeth of your prey, before you start eating him!

Agreed. Assuming you have direction-wise attack- and defend-sets handy, let say in an aggregated manner like pawn- (single, double), king-. single, at least double (+battery) attacks/defends - to most often rely on a set-wise SEE - I think capturing a hanging (let say not defended) knight/bishop should be tried before RxR or even QxQ. Also assuming both opponent rooks or queens are mutually defended appropriately.

[hgm]

I am not sure what you are saying here. My statement implied that, even when there is an undefended B or N one can capture, it would be better to try a neutral QxQ or RxR first.

Because if the +3 capture is a cut move, the QxQ (or RxR) and recapture will be in the tree anyway, as the opponent will then initiate that capture in the all-node following our B capture. They will not be futile (or we would have stood pat), and can only end better for the opponent than when we would have initiated them. (Because we don't know if our Q or R was sufficiently defended). And by doing these two captures before we take the hanging Bishop, in stead of after it, all unpleasant surprises will be for the opponent, in stead of for us.

[Gerd Isenberg]

I am not sure what you are saying here. My statement implied that, even when there is an undefended B or N one can capture, it would be better to try a neutral QxQ or RxR first.

Because if the +3 capture is a cut move, the QxQ (or RxR) and recapture will be in the tree anyway, as the opponent will then initiate that capture in the all-node following our B capture. They will not be futile (or we would have stood pat), and can only end better for the opponent than when we would have initiated them. (Because we don't know if our Q or R was sufficiently defended). And by doing these two captures before we take the hanging Bishop, in stead of after it, all unpleasant surprises will be for the opponent, in stead of for us.

Sorry for the confusion. I agreed under the assumption attack and defend sets or lists were not available and you only rely on MVV/LVA without exact see > or == 0 information of equal captures. Or without the information our queen is sufficiently defended or possibly en-prise.

Otherwise the earlier you win a piece, the better imho - otherwise some (quite) saving tactics or zwischenzug is more likely - even if the opponent is able to force the exchange. I think most often it don't cares if you do X x hangingNB or defendedQ x defendedQ first. But there are cases where the defended queen itself has the option for an equal exchange versus grabbing the hanging piece. Also for the QxQ branch the other side may able to recapture with the hanging knight. Of course there are counter examples as well.

[xsadar]

Thank you all for your thoughts. I will definitely have to improve my move ordering. And, as it turns out, I remembered wrong, and my move ordering is worse than I thought. I wrote my move generation code for my new engine six months ago, and didn't really work on my engine since then until a couple weeks ago. When I took a closer look at my code, I realized my moves were only ordered by attacker, and didn't even take the victim into consideration . I'm not sure why I did that, but I'll definitely have to fix that. It shouldn't be too difficult to change it to regular MVV/LVA. Should help with my regular search as well.

[xsadar]

Well, my engine now generates captures in regular MVV/LVA order. I have to tell you, the effect of decent move ordering is simply AMAZING!!! I expect to also try SEE in the future, but probably not until after my first release. Thanks again HGM, Gerd and Lance for your help.