IID in QS (again)

[hgm]

I am still working on making Quiescence Search more robust against search explosion, and I have arrived at a scheme that I start to like. The basic idea is to turn of the temperamental depth-first search into a much more robust breadth-first search, by imposing an artificial depth limit, and increasing that step by step. In QS, however, limiting to a fixed depth gives highly unstable scores for the tree branches (trying to capture a fat piece on the last ply where the refuting recapture is beyond the horizon). So you have to extend such captures. But if you extend all captures, you are back to depth-first.

So what I try to do is not extend moves that seem to lead nowhere. Not extending in QS means you might not search them because you ran out of depth, but if they really lead nowhere, pruning them should not upset the stability of the tree much.

If I capture something, and on the next move my opponent gains more than I captured, this usually leads nowhere; it means I am just burning material. So I don't extend a move that seems to gain more than was captured on the previous ply (and which is passed to the next level as a parameter 'threshold' to Searc()). The gain is estimated as victim value (for unprotected victims) or as victim value minus attacker value (if it is protected). If there is no depth left to search such a move unextended, it is assumed to fail high (auto-fail-high). Otherwise it is searched at depth-1.

That some captures take depth, means that it will take some depth to do a reasonable-quality QS. So in stead of just having depth=0 as the QS level, there are now multiple levels. (Which was exactly what we are striving for; simple tactics will be already found at the lowest depth, but complex tactics, e.g. where capturing a hanging piece unexpectedly turns sour because you were pinned on something higher, or would in general be confronted with a recapture on a different square, would require a larger depth. But if the simple tactics does the job, the complex tactics would become irrelevant, so it will only be searched if it is indeed essential.)

Note that a branch RxB - NxR - QxN would count as simple tactics, because the NxR (protected by Q) only has an estimated gain of the exchange (+2), which is lower than the B value (3) in previous RxB, so it would be extended. Even the QxN would be extended, assuming the N was the only protector of the B, because N < R.

With 5 levels of QS (0-4), you would get something like this:

Code: Select all

#define QS 4

int Search(int alpha, int beta, int depth, threshold)
{
  if&#40;depth < 0&#41; return -INF; // abort branch
  if&#40;depth <= QS&#41; &#123; // in QS, try stand pat
    score = Evaluate&#40;);
    if&#40;score > alpha&#41; alpha = score;
  &#125;
  if&#40;alpha >= beta&#41; return beta; // stand-pat cutoff
  for&#40;ALL_MOVES&#41; &#123;
    if&#40;iterDepth <= QS ! IsCapture&#40;move&#41;) continue; // in QS skip non-captures
    int gain = value&#91;victim&#93;;
    if&#40; IsProtected&#40;toSqr&#41; ) gain -= value&#91;piece&#93;;
    int extend = 0;
    if&#40;iterDepth <= QS && gain <= threshold&#41; extend = 1;
    MakeMove&#40;move&#41;;
    score = -Search&#40;-beta, -alpha, depth - 1 + extend, depth <= QS ? value&#91;victim&#93; &#58; INF&#41;;
    UnMake&#40;move&#41;;
    if&#40;score > alpha&#41; &#123;
      alpha = score;
      if&#40;score >= beta&#41; return beta; // beta cutoff
    &#125;
  &#125;
  return alpha;
&#125;

The initial 'return -INF' is a kludge to do the auto-fail-high on the previous level when you run out of depth; a more careful (but more complex) implementation could of course do this without doing Make(), UnMake(). (A sort of inverse futility pruning.) In QS the threshold is set to the captured piece's value; in full-width search it stays at +INF to make sure every test on it fails.

Note that equal captures do have zero 'gain', always <= threshold, so they are always extended, and thus part of simple tactics.

The pseudo-code example doesn't pay any attention to move sorting; it is essential, however, that the search of all non-extended captures (or their auto-fail-high) would be done before the search of all extended captures: they are reduced and expected to fail high. If you generate the captures in MVV order, they can only be non-extended as long as the victim value is above 'threshold'. For protected victims the estimated gain can then still below threshold (so the capture would be extended), and such moves in this stage would have to be postponed, while captures of unprotected victims can always be searched immediately. The postponed captures can be searched before you get to any captures with victim value below 'threshold'.

Also essential (and not shown) is to do depth bootstrapping, as sub-trees that did not run into any auto-fail-highs (a simple stand-pat being the simplest example) are immediately valid to depth = QS = 4, even if they were obtained in a depth=0 search, so that it would be pointless to re-search them at depth = 1, 2, 3, 4.