Is SF DD greater efficiency would be null move pruning?

[hgm]

In case you have some knowledge of chess engine programming I'd suggest to read search() sources so to clarify your confusion, if not, perhaps I can help you noticing that razoring is another thing from what you think, in particular razoring cuts nodes well below alpha (and so requires a verification, usually a qsearch), instead this pruning scheme cuts nodes well above beta without verification.

Well, I am sure you know that beta in one node is -alpha in the parent, and that the concepts 'above' and 'below' map onto each other on negating all values. So if it is anything different than what I am thinking, it is most certainly not because of what you say above. So why say it, other than just to dress up a snide remark?

Regarding usual futility pruning (that is also another thing), normally it is done in the moves loop _before_ move is actually made. In this case is a kind of futility but done after the move is made (and so with comparison sign reversed).

Well, 'normally' is not nearly the same as 'always'. I would say it depends on how lazy you want your evaluation to be, and whether the eval accuracy you need can already be achieved without making the move. Especially when you need a large margin anyway because of the large remaining depth calculating the small terms hardly makes any sense.

But those are implementation details. It does not really make it a different pruning.

[mcostalba]

Your comment about razoring made me wonder if it could be worth verifying the child node futility pruning too.

The reason why in razoring verification is mandatory is because it is your turn to move: so even if well below alpha maybe you are about to recapturing a queen...instead this does not apply when you are well above beta because the move you are going to do is not so sensible (you are already winning by far).

Actually my idea was pretty pointless anyway. It would be the same as the normal null move pruning (give or take the different of which depth we enter the QS).

A possible speed optimization instead would be to use (SEE > Threshold) instead of qsearch as the verification step in razoring. I think I already tried it in a far past but now could be retested.

[lucasart]

Your comment about razoring made me wonder if it could be worth verifying the child node futility pruning too.

The reason why in razoring verification is mandatory is because it is your turn to move: so even if well below alpha maybe you are about to recapturing a queen...instead this does not apply when you are well above beta because the move you are going to do is not so sensible (you are already winning by far).

Actually my idea was pretty pointless anyway. It would be the same as the normal null move pruning (give or take the different of which depth we enter the QS).

A possible speed optimization instead would be to use (SEE > Threshold) instead of qsearch as the verification step in razoring. I think I already tried it in a far past but now could be retested.

You mean the SEE of the threat move? But you need to do the null search before to know what the threat move it, no?

[mcostalba]

You mean the SEE of the threat move? But you need to do the null search before to know what the threat move it, no?

I mean see on the parent move, but I understand this works only for recaptures.

[Eelco de Groot]

You mean the SEE of the threat move? But you need to do the null search before to know what the threat move it, no?

I mean see on the parent move, but I understand this works only for recaptures.

I think Lucas basically sums it up that any kind of search here instead of outright pruning (as in the name "static null move pruning") overlaps even more with null move. And it is going back further in the past to times before null move... But Rebel and Pro Deo still search this way possibly, using null move as a sort of verification search only, at least that is what Ed said, but that was already a few years back.

Just for comparison, Scid Serpent put SEE back in the futility margin, that is not a new idea either, see alo the EvalMarginV brach in the testing of a few months ago. I have the impression the effectiveness of SEE quickly dimishes though, the further you get from the leaves and near the leaves again you are already pruning everything with a a negative SEE. So the extra inclusion in the futility margin may not be such a great idea. You could argue that quiescence search has so far proven superior to SEE, so maybe a futility margin with quiecence search calls instead of SEE? But I have never tried that.

Scid Serpent's Futility Margin looks like this, I went back to more complexity by also including the movenumbers again using (ss-1)->futilityMoveCount also and it is fairly aggressive as it is now, maybe a little too much.

Code: Select all

inline Value futility_margin(Depth d, bool negativeSEE, bool improving, int mn) {
    return negativeSEE ? Value(128 + int(d) * int(d) * int(d)) - Value(int(d + (improving ? 3 : 5)) * (mn + 1)) 
	                    : Value(128 + int(d) * int(d) * int(d)) - Value((improving ? 1 : int(d)) * (mn + 1));
  }

Eelco

[lucasart]

You mean the SEE of the threat move? But you need to do the null search before to know what the threat move it, no?

I mean see on the parent move, but I understand this works only for recaptures.

ok, so if you do that at the parent node, it's basically futility pruning using the SEE. I tried that (futility pruning also captures when eval + see(move) < alpha-margin). But in the end it did not work so well, and doing eval + optimistic_gain(move) like Fruit was better. Stockfish however does not do futility pruning of captures at all. I think in the end, I stopped pruning captures too, as I realized I could push futility pruning deeper.

[hgm]

SEE is too pessimistic for futility. In many nodes the best way to get above beta is to start with a SEE=0 trade of a high piece, followed by the actual cashing in of the gain with a SEE>0 capture of a lesser piece. This is why MVV ordering in general works better than pure SEE ordering. Pruning the MVV capture because its SEE is too low wrecks that.

[Eelco de Groot]

"Would be null move pruning" is not such a bad term actually That is actually a difference in code with Stockfish 4, it is an idea from Lucas. Stockfish 4 and all the older Stockfishes already did much the same, but only in the last 4 plies. It was called "static null move pruning" but there was no null move involved and the engine did not even do a search, or a reduced search for it. It just looked at the eval and if static evaluation of the node was sufficiently good above alpha, futility margin above alpha, it just returned the eval minus the futility margin.

Pruning based on the static evaluation (and some margin) is what has been known as 'futility pruning' / 'razoring' (depending on the depth where you did it) for the past few decades, right?

Okay Harm asked for something new, I just had a very little idea related to this piece of code; Static null move pruning is related to null move pruning, not only because of the similar precondition that the static evaluation has to be good. I thought however, we could relax the condition of not doing static null move pruning in late endgames, because we are not really passing the move so, I thought, less danger of Zugzwang... However we are standing pat when at the same time we do have the move here (as opposed to the related piece of futility pruning code in the parent node). I call this little piece of code 'standing pat' in Serpent instead of static nullmove or futility, because of its relation to standing pat in quiescence search.

By the way for those not familiar with the term standing pat (pat I think is a Dutch chess term for stalemate, but I'm not quite sure that is the origin of its use in chess programming, and it is generally used by computer chess programmers now, not only Dutch so maybe it is known in other languages as well as a a general chess term), there is more about standing pat on HGM's page of MicroMax http://home.hccnet.nl/h.g.muller/futile.html

I remember reading a little bit on this page about standing pat, it was some years ago though, and I have not studied things like MVV/LVA QS that is also described there by Harm-Geert.

So I'm not so sure about relaxing the condition anymore, if we should require here also that the side to move has to have some piece, not just pawns to allow static null move/standing pat. But if this is related to standing pat in general, should it maybe not be the same in the quiescence search? Currently Stockfish does not do this. I have not actually tried it yet but at least the bench is about the same for the version that limits standing pat for quiescence search in pawn endgames:

Stockfish-master20131219_003
with Scid Serpent changes

===========================
Total time (ms) : 9037
Nodes searched : 6794514
Nodes/second : 751855

Just made this:

Stockfish-master20131219_008
with Scid Serpent changes and 'stand pat'
change

===========================
Total time (ms) : 9063
Nodes searched : 6641453
Nodes/second : 732809

I'm always happy when the bench goes down

Code: Select all

// Stand pat. Return immediately if static value is at least beta
        if (   bestValue >= beta
		      && pos.non_pawn_material&#40;pos.side_to_move&#40;))) // <-new condition here
        &#123;
            if (!tte&#41;
                TT.store&#40;pos.key&#40;), value_to_tt&#40;bestValue, ss->ply&#41;, BOUND_LOWER,
                         DEPTH_NONE, MOVE_NONE, ss->staticEval&#41;;

            return bestValue;
        &#125;

Eelco

[Rebel]

Yes, I suppose that is right Harm but in this particular instance, in the last plies and when the eval is above alpha it overlaps with the null move pruning conditions, but you bet here that you do not even have to search if you are so close to the leaves, so no (nullmove or otherwise) search is necessary and that was called "static null move pruning" in Stockfish. But because it is just another form of futility pruning Lucas changed the name.

So the 'idea' was actually just to call it by another name?

It is a bit confusing that any old thing suddenly has to be called by another name wen it gets used in Stockfish...

I guess we could rename null-move pruning to "verified deep razoring"!

In case you have some knowledge of chess engine programming I'd suggest to read search() sources so to clarify your confusion, if not, perhaps I can help you noticing that razoring is another thing from what you think, in particular razoring cuts nodes well below alpha (and so requires a verification, usually a qsearch), instead this pruning scheme cuts nodes well above beta without verification.

HGM has a valid point regarding the terminology.

The origin goes back to 1996 with the Rainier Feldmann FHR document on FAIL HIGH REDUCTIONS. It's good terminology. What most of us use today is its offshoot Fail_High_Pruning (FHP).

I don't like the term "Static null move" either because there is no null move involved at all.

But it will be hard to turn back the clock I guess and find consensus