Is SF DD greater efficiency would be null move pruning?

[jplchess]

I noticed that Stockfish DD is doing one extra ply in efficiency on blitz games (against Houdini 1.5 or Stockfish 4). Would that be called null move or is it something else?

Your most humble chess player with pattern recognition,
Jonathan Lee

[Eelco de Groot]

I noticed that Stockfish DD is doing one extra ply in efficiency on blitz games (against Houdini 1.5 or Stockfish 4). Would that be called null move or is it something else?

Your most humble chess player with pattern recognition,
Jonathan Lee

"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.

old Stockfish code:

Code: Select all

    // Step 7. Static null move pruning (skipped when in check)
    // We're betting that the opponent doesn't have a move that will reduce
    // the score by more than futility_margin(depth) if we do a null move.
    if (   !PvNode
        && !ss->skipNullMove
        &&  depth < 4 * ONE_PLY
        &&  eval - futility_margin&#40;depth, false, &#40;ss-1&#41;->futilityMoveCount&#41; >= beta
        &&  abs&#40;beta&#41; < VALUE_MATE_IN_MAX_PLY
        &&  abs&#40;eval&#41; < VALUE_KNOWN_WIN
        &&  pos.non_pawn_material&#40;pos.side_to_move&#40;)))
        return eval - futility_margin&#40;depth, false, &#40;ss-1&#41;->futilityMoveCount&#41;;

However the engine also did much the same thing one ply before this, but there it did not have an eval yet. An engine first has to make a move before it can evalate the position after the move. But apart from that, it was much the same, but just had to use the evaluation of the ply before , -the evaluation before the move-, so that was much less accurate. Lucas' idea was to bring all that over to the next ply, when you had done an evaluation, that costs something extra but it makes the pruning more accurate. And the name static null move pruning disappeared also, because it did not have much to do with null move. It is done in the last six plies and this you might call your "would be null move pruning"

In Stockfish DD, the above code block is now:

Code: Select all

    // Step 7. Futility pruning: child node (skipped when in check)
    if (   !PvNode
        && !ss->skipNullMove
        &&  depth < 7 * ONE_PLY
        &&  eval - futility_margin&#40;depth&#41; >= beta
        &&  abs&#40;beta&#41; < VALUE_MATE_IN_MAX_PLY
        &&  abs&#40;eval&#41; < VALUE_KNOWN_WIN
        &&  pos.non_pawn_material&#40;pos.side_to_move&#40;)))
        return eval - futility_margin&#40;depth&#41;;

If a node is pruned in this stage, it could also have been pruned by null move later, so there is some overlap near the leaves with null move and I am not sure, it may be a little less null move is done now (you would have to measure that with a profiler). This can help a very little bit, in theory, against Zugzwang and it also might mean a little less threatmoves were found, but the very latest development Stockfish of the last two weeks or so, does not even use threatmoves anymore... The speed up in code compensates.

In Scid Serpent, I now do "would be null move pruning" not in six but in the last eight plies, but I try to be a little more careful doing that than Stockfish DD, because threatmoves have also disappeared. I do not always outright prune but sometimes a reduced search. This I called a ProbCut search because I don't search against alpha, but against alpha + the futility margin.

The short answer would be "Yes, SF DD greater efficiency: would be null move pruning!"

Regards Eelco

[lucasart]

Null move per se did not change. It's hard to pinpoint one reason for the extra depth. A sum of many changed between SF 4 and SF DD simply make the search more efficient. Actually, most of the elo gain between SF 4 and SF DD was in the search, not the veal.

Qsearch is also wider now in the first 2 plies, as it does not prune the "useless" checks (testing demonstrated that useless checks were in fact useful).

There were also some interesting changes to dynamic time management.

Well, as I said, it's a sum of details, none of which seems a breakthrough by itself, that explains a big elo increase in the end. Improving a 3200+ elo monster is a slow and tedious process. But with many people (hence more diversity in the source of ideas) and a lot of CPU resources, Stockfish seems to be able to continue progressing, where other engines are struggling.

[hgm]

"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?

[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?

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.

In the past, in the days before null moving pruning was implemented in I think every strong engine, programmers relied on this sort of pruning much more. From the commercial programmers I think it was Chrilly Donninger who first wrote about null move in the ICCA Journal, but it came from I believe American programmers before that, I don't remember exactly, I think it is somewhere in the WiKi. Then Frans Morsch made an assembler version of null move that sped up his early Fritz programs a lot I think and he was enthusiastic about it to Ed. It took a while though for Ed to implement null move in Rebel and Vincent would criticize Rebel often for doing "dangerous forward pruning" I think that was all still in Rebel Dos days. The program Genius from Richard Lang also did not have null move yet as far as I know, the hardware part of Deep Blue, also not. So these programs had to try getting enough depth to overcome horizon problems in another way and you might call all of that, sometimes elaborate pruning schemes, "Would-be null-move". I am not being entirely serious with the term, it was Jonathan's

Eelco

[hgm]

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"!

[mcostalba]

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.

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).

[lucasart]

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.

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

Currently, if the TT refined eval >= beta + margin, we return that eval. How about doing a null move and letting the opponent do a search() to see if the opponent could bring us below beta + margin. That way you account for pieces hanging we may have. I have a condition on pieces hanging in DiscoCheck there, but that would be more general.

It may (probably will) be too costly and too conservative. But it's worth a shot.

[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).

[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).