Code: Select all
#define QSdepth 10 /* optimize empirically */
Search(alpha, beta, eval, evalCut, depth)
{
startDepth = (depth == QSdepth ? 0 : depth); // IID only in horizon nodes
for(d = startDepth; d <= depth; d++) { // IID
bestScore = (depth > QSdepth ? -INF : eval); // depth 0-10 is all QS, so stand pat
if(bestScore >= beta) return bestScore;
for( ALL_MOVES ) {
if(depth<=QSdepth && !MoveIsCapture(move)) continue; // only captures in QS
MakeMove(move);
newEval = Eval();
victimValue = newEval - eval;
if(depth <= QSdepth && (victimValue <= value[mover] || !Attacked(TOSQUARE(move)))) {
if(victimValue > evalCut) { // previous ply was unjustly extended / searched
if(d == 0) score = +INF; // force beta cutoff if last two ply were a gain
else {
d--; depth--; evalCut = +INF; // take away extension and prevent this from happening again
score = -Search(-beta, -alpha, newEval, victimValue, d);
}
} else // extend, but set us up to fail low if this happens to opponent on next d=0 ply
score = -Search(-beta, -alpha, newEval, victimValue, d);
} else {
if(d == 0) score = -INF; // non-obvious gains fail low without search at d=0 (pruned)
else // and at other depths they eat one depth unit
score = -Search(-beta, -alpha, newEval, +INF, d-1);
}
UnMake();
...
}
}
}
I have a less cryptic formulation of the IIDing QS, by getting rid of the rather obscure and possibly very complex function IsObviousGain(). This is replaced by tests after MakeMove(). This is a more general approach, and is not assuming any complex infra-structure in the engine that can decide whether pieces are protected or not. (This can be quite hard to figure out when a move can explode neighboring pieces; even an attack map could then give wrong information, because a listed protector could get lost in the explosion, while on the other hand a square listed as unprotected could become protected because you blew up a neighbor that was blocking a slider attacker.)
In the current scheme it is not needed to know whether something is protected, (i.e. capturable by the side not to move after your move), only whether something is attacked by the stm. And even then it can be allowed to err in the direction of reporting pieces unprotected that in fact are protected in a non-obvious way (e.g. by exploding something on a neighboring square). This only means you will miss an early pruning of such bad captures, but eventually it will be discovered on the following ply that a recapture was possible, and abort the search there with a beta cutoff. (Which is the same as when a too-valuable 'hostage' would be executed on a different square).
With MMV sorting it should always be discovered on the first move whether it has a more valuable victim on what was captured on the previous ply. So there is no searching of moves in the sub-tree that will be pruned in this delayed way.
