Futility Pruning and its Relation to Quiescence Search

[Jakob Progsch]

So I'm reading the wiki page on futility pruning and I feel I must be missing something. To me it reads like the following:

1. at d=1 if eval is below alpha-theshold don't bother and end the main search (aka. go into QS)
2. however you should still search the following moves: <list of everything QS is going to search anyway>

The first makes sense to me but the second just confuses me again. How is searching "captures and moves that give check" different from dropping into QS right there and then?

In general I feel I don't get the justification of futility pruning under presence of QS. Since I can't actually know that there is only one move left to search. For all I know QS will find some devastating sequence of captures that give check such as a back rank mate situation where all the opponent can do is throw their "superior" material in the way to delay a mate.

[hgm]

This sounds like an incorrect description. Futility pruning is done at d<=1 (or in general wherever you get a QS reply) prunes moves with a score estimate so far below alpha that you can be certain the child node will fail high through stand pat. If the current eval is sufficiently below alpha, this obviously includes all non-captures, as these hardly raise the eval. It can include a lot on captures too, though. If you are a Rook below alpha, you won't have to bother with capturing Pawns or minors.

But that also is an issue in QS itself. In designs that use a separate search routine for QS, calling that is a simple kludge to bulk-prune all non-captures, though. Most designs don't have a similar trick for pruning all captures of Pawns, or of Pawns + minors. So these are then always generated and sorted, and then tested for futility on a per-move basis. But when you search them in MVV order, as soon as you encounter a futile one, you can be sure all remaining moves will be futile as well, and fail low immediately.

Note that you can get a similar situation at d=1, when initially eval is not much below or even above alpha, but a capture raises alpha to far above current eval. Then all non-captures have become futile as well. (But since you are already searchin captures, it makes no sense to switch to QS doing it again).

[Gerd Isenberg]

With classical FP à la Heinz at frontier nodes (depth==1), you don't go into qsearch (this is matter of some razoring techniques) but you skip none tactical moves inside the move loop. See Ernst A. Heinz' Search with Extended Futility Pruning and Limited Razoring Code, futility pruning at frontier nodes near the end. While it sounds similar to going into qsearch, there are subtle differences, concerning standing pat and not pruning check giving moves.

[Jakob Progsch]

I guess there is a chance I'm just overinterpreting the wiki. The wiki has separate pages for "futility pruning" and "delta pruning". The second is described as a special case of futility pruning in QS so I assumed the futility pruning page would specifically apply to the non-quiescence search.

Reading the replies makes me think I maybe try to reason about this in the wrong place? My assumption was I'd do this at the "node level".

As in:

Code: Select all

search(..., depth) {
	futility_margin = <most valuable piece left + safety margin or so>;
	
	if(depth == 0 || (depth == 1 && eval + futility_margin < alpha)) {
	 	return qs(..., depth); 
	}
	 
	 // do the rest as normal
}

I do have delta pruning in QS. I do movegen by first populating some masks with all the moves and then list them out by category. So I never actually sort all the moves I just extract them in the "right" order. In QS I just stop that process once I have gone through all the promotions, "sufficiently winning" captures and maybe checks. So for my implementation the above may indeed be a reasonable futility pruning implementation?

I guess the other way would be something like the following?

Code: Select all

search(..., depth) {
	if(depth == 0) {
	 	return qs(..., depth); 
	}
	 
	//... movegen etc.
	
	for(moves) {
		futility_margin = <max gain from this move>;
		if(depth = 1 && eval + futility_margin < alpha) {
			break;
		}
		// search move
	}
}

Which would mean at the first move that doesn't stand a chance to raise alpha it just exits hard (without even doing QS on the remaining moves)?