Quiescence Search Explosions

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
xsadar
Posts: 147
Joined: Wed Jun 06, 2007 8:01 am
Location: United States
Full name: Mike Leany
Contact:

Quiescence Search Explosions

Post by xsadar » Fri Apr 18, 2008 6:16 pm

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.

User avatar
hgm
Posts: 25076
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Quiescence Search Explosions

Post by hgm » Fri Apr 18, 2008 7:01 pm

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
Posts: 2212
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Quiescence Search Explosions

Post by Gerd Isenberg » Fri Apr 18, 2008 8:40 pm

xsadar wrote: 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
Posts: 388
Joined: Wed Mar 08, 2006 9:08 pm
Contact:

Re: Quiescence Search Explosions

Post by CThinker » Sat Apr 19, 2008 2:30 am

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

User avatar
hgm
Posts: 25076
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Quiescence Search Explosions

Post by hgm » Sat Apr 19, 2008 9:36 am

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
Posts: 2212
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Quiescence Search Explosions

Post by Gerd Isenberg » Sat Apr 19, 2008 3:23 pm

hgm wrote: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.

User avatar
hgm
Posts: 25076
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Quiescence Search Explosions

Post by hgm » Sat Apr 19, 2008 4:57 pm

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
Posts: 2212
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Quiescence Search Explosions

Post by Gerd Isenberg » Sat Apr 19, 2008 5:49 pm

hgm wrote: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.

User avatar
xsadar
Posts: 147
Joined: Wed Jun 06, 2007 8:01 am
Location: United States
Full name: Mike Leany
Contact:

Re: Quiescence Search Explosions

Post by xsadar » Wed Apr 23, 2008 4:59 am

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 :oops: . 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.

User avatar
xsadar
Posts: 147
Joined: Wed Jun 06, 2007 8:01 am
Location: United States
Full name: Mike Leany
Contact:

Re: Quiescence Search Explosions

Post by xsadar » Thu May 22, 2008 3:46 pm

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.

Post Reply