Is SF DD greater efficiency would be null move pruning?

Discussion of anything and everything relating to chess playing software and machines.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jplchess
Posts: 115
Joined: Mon Jan 25, 2010 6:13 am

Is SF DD greater efficiency would be null move pruning?

Post by jplchess » Sun Dec 22, 2013 3:19 am

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

User avatar
Eelco de Groot
Posts: 4148
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Is SF DD greater efficiency would be null move pruning?

Post by Eelco de Groot » Sun Dec 22, 2013 4:20 am

jplchess wrote: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&#58; child node &#40;skipped when in check&#41;
    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!" :P

Regards Eelco
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

User avatar
lucasart
Posts: 3037
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Is SF DD greater efficiency would be null move pruning?

Post by lucasart » Sun Dec 22, 2013 5:01 am

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.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
hgm
Posts: 23617
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Is SF DD greater efficiency would be null move pruning?

Post by hgm » Sun Dec 22, 2013 12:04 pm

Eelco de Groot wrote:"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?

User avatar
Eelco de Groot
Posts: 4148
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Is SF DD greater efficiency would be null move pruning?

Post by Eelco de Groot » Sun Dec 22, 2013 12:59 pm

hgm wrote:
Eelco de Groot wrote:"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
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

User avatar
hgm
Posts: 23617
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Is SF DD greater efficiency would be null move pruning?

Post by hgm » Sun Dec 22, 2013 1:16 pm

Eelco de Groot wrote: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"! :idea:

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Is SF DD greater efficiency would be null move pruning?

Post by mcostalba » Sun Dec 22, 2013 1:31 pm

hgm wrote:
Eelco de Groot wrote: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"! :idea:
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).

User avatar
lucasart
Posts: 3037
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Is SF DD greater efficiency would be null move pruning?

Post by lucasart » Sun Dec 22, 2013 1:46 pm

mcostalba wrote: 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.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Is SF DD greater efficiency would be null move pruning?

Post by mcostalba » Sun Dec 22, 2013 1:52 pm

lucasart wrote: 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).

User avatar
lucasart
Posts: 3037
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Is SF DD greater efficiency would be null move pruning?

Post by lucasart » Sun Dec 22, 2013 1:57 pm

mcostalba wrote:
lucasart wrote: 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).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Post Reply