In first instance I will not be doing any futility pruning in d >= 2 nodes. This because there isn't really a useful limit to the damage Fire Demons can do in a single move, so that a non-capture at d=2 that creates a burn threat could easily gain 6 Queens in the first ply of QS. Moves that do not top alpha at d <= 1, however, will be met with stand pat, no matter how much they threaten.
QS vs 1-ply
There is an interesting iteraction between futility pruning and the effective depth of a search. Searching any move is by definition at least a d=1 search on that move, as you have to play the move itself in order to earch it. So QS is really doing d=1 searches. But what distinguishes it from a 1-ply search is that it doesn't do them on all moves. It prunes the captures, and substitutes a stand-pat score for them. But 1-ply searches also prune moves, if they are futile. And non-captures are the most futile of all. So a QS search under conditions where non-captures would have been futile (because currentEval < alpha - MARGIN) is the same as a 1-ply search for that window, as the stand-pat score (currentEval) will have been ignored. When a capture in QS produces a beta cutoff, it also does not matter whether you intended to search the non-captures or not.
This is relevant for our IID scheme, to distinguish the QS from the 1-ply iteration. If the minimum requested search depth is >= 1 ply, then we don't have to bother with QS, and can start IID with a 1-ply search. If the maximum requested depth is QS, we never have to search non-captures. But if the miimum depth is QS, and we might have to deepen when this fails low, we somehow need to make a conditional transition from QS to 1-ply after we are done with the captures.
This will be implemented as follows:
Before any iteration starts we will calculate the futility threshold, (alpha - currentEval - MARGIN) translated to units used in the MVV/LVA scoring. This will be passed to the staged move generator MoreMoves(), so that this can stop its victim-by-victim move generation when it gets down to the futile victims. In this case it will return a negative "out-of-moves code" early. (Normally it returns the number of generated captures.) The QS / 1-ply iteration would be terminated by this; when the iteration depth reaches 2 ply the futility threshold would be reset to 0, so that future calls to MoreMoves() when the current (partial) move list runs out will continue generating captures on low-valued victims, and non-captures.
A negative value for the futility threshold will be used as a kludge to tell MoreMoves() that it should refrain from generating non-captures even when these are not futile. This will cause an early end to the QS / 1-ply iteration, making it a QS iteration. To handle the case where conditional deepening was requested based on whether QS failed low, we have to recognize this situation (from the futility threshold value), and if alpha <= startAlpha (fail low) and maxDepth > QSDEPTH reset the futility threshold to 0, and call MoreMoves() again (which now will generate non-captures), to finish the iteration we already did the captures for as a 1-ply iteration.
Code: Select all
// before IID loop
int futile = SCALED(alpha - currentEval - MARGIN);
if(futile < 0) futile = -(minDepth <= QSDEPTH); // when non-captures not futile, QS must be requested explicitly
// at top of IID loop
if(iterDepth > QSDEPTH+1) futile = 0; // switch off futility pruning after 1-ply search
// pick next move to search
if(currentMove >= msp) { // out of generated moves, generate next batch
sort = MoreMoves(currentMove, &stash, areaMaps, futile); // generates moves and returns how many need sorting
if(sort < 0) { // all (non-futile) moves exhausted
if(futile < 0) { // kludge to indicate we are doing QS
if(maxDepth <= QSDEPTH) { // QS was all that is requested
if(resultDeph > QSDEPTH) resultDepth = QSDEPTH; // so we won't search captures, making this a QS result
break;
} else if(alpha > startAlpha) break; // deepening requests are only serviced on fail lows
sort = MoreMoves(currentMove, &stash, areaMaps, 0); // generate non-captures after all
futile = 0; // and flag we are now at 1 ply
if(sort < 0) break; // still no moves (can this happen?)
} else break; // termiates non-QS iteration
}
}
A remaining problem is that QS will not search all captures, but prune the bad ones. In Tenjiku Shogi, which is very prone to QS search explosion, I will expand the concept of 'bad capture' to anything that is not obviously gaining material. Only captures of higher or unprotected victims will be considered good. So when we finish a search of captures at QS level, and then continue searching non-captures, the 'bad captures' will still not have been searched. There seems little harm in pruning bad captures at 1-ply as well as in QS, however, and only start searching them from 2-ply on. (This might want to make me reconsider searching equal captures in QS, though, as it does seem bad to leave those out at 1 ply.)
Bad captures will have to be generated even in IID iterations that would prune them, however, because later iterations will want to search them. This will be implemeted by generating bad captures with the lowest possible sort key (which for good captures would hold the MVV/LVA value). After MoreMoves() has placed the next batch of captures (all on the next 'victim group', i.e. a set of victims with the same exchange value) on the move stack, the move loop will extract the one with the lowest sort key from it to search. As all moves have the same victim, this is the one with the LVA. But if it gets to key 1, it will just skip the remaining moves of the batch if the depth is 1-ply or less.
. Surprisingly enough this only degraded performance, and I noticed it because during backward analysis it never seemed to be able to get exact hits on just analyzed positions.