I have a QS scheme that I like now:
Code: Select all
Search(depth)
{
startDepth = (depth == 10 ? 0 : 10); // IID only in horizon nodes
for(d = startDepth; d <= depth; d++) { // IID
bestScore = (depth > 10 ? -INF : Eval()); // depth 0-10 is all QS, so stand pat
if(bestScore >= beta) return bestScore;
for( ALL_MOVES ) {
if(depth<=10 && !MoveIsCapture(move)) continue; // only captures in QS
replyDepth = d-1;
if(d<=10 && IsObviousGain(move)) replyDepth++; // maybe other depth limit than 10?
if(replyDepth < 0) continue;
MakeMove(move);
score = -Search(replyDepth);
UnMake();
...
}
}
}
The subtlety is in the function IsObviousGain(). Without it (i.e. if it would always return FALSE), this would just be a QS with a depth limit, which is increased from 0 to 10 ply by IID in the horizon nodes (d=10). The idea is now to declare captures 'obvious gains' if the piece captured is worth more than he can recapture (on same or different square) on the next ply as Low x High or hanging piece. And then to extend such captures, so that even at d=0 it would continue to search them to unlimited depth.
The IID is only conceptual, and would in pratice be cut short through the usual depth bootstrapping: a stand-pat result in itself would be immediately valid upto d=10, as would any score where none of the branchess contained a fail low at d=0 (so that it might have been affected by the pruning of the non-obvious captures). Only in the latter case the depth backed-up towards the root would be < 10, and signal to the horizon node that further depth increase is necessary to get the next level of non-obvious tactics within the horizon. As soon as all moves return a 'saturated' depth with their score, no new iterations have to be performed.
The IsObviousGain criterion is inspired by the idea that when I capture something in face of a threat against a higher piece of mine, it is likely to loose material. But I don't want all my captures to be declared non-obvious in the face of a possible Q trade (i.e. he has Q x (protected Q)), so that they would eat one depth unit and would require an extra iteration. So I do not count equal or HxL attacks against a protected piece as threats against that piece. This is consistent with the fact that on the next ply the equal capture Q x (protected Q) would also not be an 'obvious gain', and thus not searched at d=0.
So a capture that qualifies for searching at d=0 will never have a reply searched at d=0 that captures an equal or higher piece. Every next capture after reaching d=0 has to be on a less valuable piece. This ensures you run out of moves pretty quickly, even in positions where plunder raids are possible. You just will not continue the plunder raid at any point where he can make an equal or better capture than you can as stm. This will be saved for the next QS-IID iteration, when (hopefully) more side branches of the plunder raid are resolved, narrowing the search window, and perhaps even alpha-beta pruning the entire plunder raid itself before you wasted time searching it to the end.
A slight refinement can be that you also take captures with the threatened piece into account. E.g. when (at d=0) I am not allowed to search captures of anything less than a Queen, because there is a PxR threat against me, but if one of the captures thus pruned is a BxR capture, a move (threatened R) x (protected B) should be an 'obvious gain', as his recapture of the R is outlawed by my pre-existing BxR.
