Verification of pruning techniques

[Michel]

It is well-known that d=1 or even d=2 nodes and QS nodes are often the same. It seems very strange, though, to subject that notion to a ridiculously large margin of 800. How much do you have to be below alpha to be sure that non-captures are not going to cut it?

The value was never tuned. But 800 is about the value of a bishop. So it is not really "ridiculously large".

[hgm]

Oh, that is pretty unusual. Normally one would expect scores to be posted without warning to be in centi-Pawns.

A Bishop still seems a pretty large margin to me. Which fraction of the non-captures would increase the eval by more than a Bishop? Would it really pay to search those thousands of non-captures that don't to spot the occasional one that does?

[Michel]

A Bishop still seems a pretty large margin to me. Which fraction of the non-captures would increase the eval by more than a Bishop? Would it really pay to search those thousands of non-captures that don't to spot the occasional one that does?

Well futility pruning is not done solely on the basis of evaluation. Some types of moves are excluded from futility pruning because they are interesting otherwise. You'd expect there to be a price to pay for skipping these additional safeguards. But as said, the value 800 was never tuned.

[hgm]

Well futility pruning is not done solely on the basis of evaluation. Some types of moves are excluded from futility pruning because they are interesting otherwise.

Normally these would be only checks.

It doesn't help to qualify moves as too 'interesting' to prune when the opponent would happily stand pat against them. Futility pruning is not about good or bad moves, it is about not wasting time on moves that will face the harsh reality of stand pat. So if you don't have something like

if(eval >= beta && !interesting) return eval;

in your QS there is really no point in taking anything else into account for deciding about futility.

If there is an easily identifiable class of non-captures that can cause such extreme eval swings, (e.g. King or Pawn moves in connection to King Safety, or Pawn pushes to 7th rank), it would be wise to have a separate generator for them, and also search them in QS. Otherwise you should expect severe horizon effects.

[Ferdy]

I have this uci engine called CDrill without search reduction and pruning not even NMP, it only has hash table. In the evaluation only piece values and pst for P, N, B and K. No mobility, no passers, no king shelter, no weak pawns eval nothing.
It scored 100 (+61,=12,-27), 67.0 % vs Robin 0.983 (CCRL40/4 1755).

Created a branch from this engine and added razoring at depth 1. Run some self-test of 100 games each (TC 40moves/60s) from different test suites. Here is the result.

[hgm]

Razoring at d=1? That is normal futility pruning, isn't it?

How did you implement it then, to save you any time compared to just latting stand-pat in the daughter take care of it? With only incremental PST for eval, stand-pat must be nearly as cheap as pruning. But your results suggest it is a least 35% faster.

Is this a hash-probe problem?

[Michel]

By interesting moves I mean moves which can cause large eval swings without being captures.

As I said the value 800 was never tuned. Perhaps it can be lower but I would expect that in any case it needs to be higher than the futility margin for depth 1 since the latter takes into account that interesting moves will not be pruned.

Of course there are different implementations possible of the same idea (one could subcase futility pruning for depth=1). But IMHO the current implementation expresses the idea in the most concise way.

[hgm]

By interesting moves I mean moves which can cause large eval swings without being captures.

But if non-captures exist where you can gain on the order of a Bishop, not considering them in QS would have the same effect as not considering Bishop captures in QS. And when you consider them in QS, there wouldn't be any need to not do QS instead of d=1 already at a much lower margin. I would say the margin should always be smaller as a Pawn, to avoid severe horizon effect. When I gave castling a bonus of more than a Pawn, my engine would make non-sensical Pawn sacs in the opening all the time, to push the opponent's castling over the horizon.

[Ferdy]

It is just similar to this.

Code: Select all

// Razoring
	if &#40;depth < 2 && !pv_node && !incheck&#41;&#123;
		int seval = eval&#40;);
		if &#40;seval + 150 <= alpha&#41;&#123;
			return qsearch&#40;alpha, beta, 0&#41;;
		&#125;
	&#125;

Code: Select all

int search(int alpha, int beta, int depth, bool incheck){
    
    pv_node = beta-alpha > 1;

    if depth < 1 return qsearch&#40;)

    check_rep&#40;)

    probe_hash&#40;)

    // Razoring here
    
    gen_moves&#40;)
    ...

&#125;

[hgm]

It is just similar to this.

Code: Select all

// Razoring
	if &#40;depth < 2 && !pv_node && !incheck&#41;&#123;
		int seval = eval&#40;);
		if &#40;seval + 150 <= alpha&#41;&#123;
			return qsearch&#40;alpha, beta, 0&#41;;
		&#125;
	&#125;

Well, that is just futility pruning, implemented by letting QS do it.

You mean that you otherwise would search all non-captures in this node? Then I can imagine why it saves you so much time. The more efficient implementation of this would be

Code: Select all

int search(int alpha, int beta, int depth, bool incheck){
   
    pv_node = beta-alpha > 1;

    if depth < 1 return qsearch&#40;)

    check_rep&#40;)

    probe_hash&#40;)

    int seval = eval&#40;);

    if&#40;depth < 2 && !pv_node && !incheck && seval + 150 < alpha&#41;
        gen_captures&#40;alpha - seval - 150&#41;; // generate captures of sufficiently valuable victims
    else
        gen_moves&#40;)

    ...

&#125;

That would save you duplicate evaluations, incheck tests, hash probes etc.

And I wonder why you would not do it while in check. The non-capture check evasions will be just as futile as any other non-capture. They will not approach alpha, and the opponent is sort of guaranteed to make them fail low by standing pat.