Inverse delta pruning

[michiguel]

Why prune good moves with SEE > 0?

Because you speculate with some degree of confidence that some of these moves beat beta and you don't want to spend the effort to verify that. Instead you get out and search other parts of the tree. It is the classical trade-off and I agree that it would be a small fish. But if the fish is there why not try to catch it.

I will try it. Conceptually, it should work if saving one eval and makemove is more work than running a given number of SEE. My concern is that the accuracy of SEE is critical here, more than in the regular delta pruning. For instance, you could consider a capture as winning when the capturing piece is pinned without further analysis. This is more serious than in the regular delta pruning, There, you prune the move _even_ if the capture works. Here, you prune assuming that the capture works. How problematic this is can only be answered by testing.

Miguel

[bob]

I get how delta pruning works. But my question was why pruning good moves would bring a significant benefit if pruning bad ones didn't ? It is _not_ that pruning good looking moves is not a bad idea. And if i have to guess why crafty do not use delta pruning now is because it has been doing redundunt staff with the lazy eval and pretty much saves only a makemove.

No, it was removed when I changed the MVV/LVA ordering and deferred using SEE until just before I make a capture and then recurse. I have had it on my to-do list to go back and revisit that. The problem is, at ordering time, I don't have the SEE score, which changed the way the code would work... I removed it when I made that change...

[Daniel Shawul]

No, it was removed when I changed the MVV/LVA ordering and deferred using SEE until just before I make a capture and then recurse. I have had it on my to-do list to go back and revisit that. The problem is, at ordering time, I don't have the SEE score, which changed the way the code would work... I removed it when I made that change..

But it is redundunt with lazy eval , isn't it ? We don't need the exact SEE score to apply delta pruning.
A move's materialistic upperbound is the piece it just captured (= C ) and its lower bound
is if it loses its piece P (= C - P). So if we just take its upperbound for delta pruning :

Code: Select all

if(score_before_move + C + positional_margin < alpha)  prune

And the lazy eval part on the next ply

Code: Select all

if(score_after_move - positional_margin > beta) prune; //prune because stand pat score > beta

Now the above two are exactly the same since (alpha = -beta, and scores also negate each other before and after move).
That is why it never made sense me to do both. I prefer the lazy eval method because I can
include big "positional" scores like a trapped piece in the score calculation. You can do the same
before making the move but it is not as convinient.

Lazy eval also have additional check that basically saves eval time only without pruning.

Code: Select all

if(score_after_move + positional_margin < alpha) use lazy_score //we dont prune here but stand pat will
                                                                  do it on the next ply if next move is not good enough;

[Daniel Shawul]

I just noticed that the inverse delta pruning is also taken care of by lazy eval. But it is more riskier since it never considers opponent replies as you said. So in conclusion

i) Delta pruning is equivalent to lazy eval 1
Delta

Code: Select all

   if(score_before_move + C + positional_margin < alpha)  prune 
   

lazy eval 1

Code: Select all

   if(score_after_move - positional_margin > beta) prune; //prune because   stand pat score > beta 
   

ii) Inverse delta pruning is equivalent to lazy eval 2

Inverse delta

Code: Select all

   if(score_before_move + margin >= alpha)  prune 
   

Lazy eval 2

Code: Select all

   if(score_after_move + positional_margin < alpha) use lazy_score
   

There is a slight difference between inverse and its lazy counterpart as the later do not prune but try all opponent moves until it passes alpha. There is no reason why one shouldn't use a bigger margin and prune outright, in which case it becomes exactly like inverse delta pruning (except for the makemove).

Delta & lazy eval 1 have approximately the same risk i.e positional margin only but Inverse delta is much much more riskier than lazy eval 2.
The opponent could simply capture a queen on the next ply...

Another reason why I should stick with my lazy eval

[Daniel Shawul]

Ed schroeder has a similar method as the inverse delta pruning . While your version uses a big margin, ed schroeder's version calculates hanging pieces and then takes largest threatened piece to get the margin. That requires calculation of attack tables to determine if our pieces are hanging ( a full board swap).
typo: The inverse delta pruning formula in my previous post should have >=beta instead of alpha

[bob]

No, it was removed when I changed the MVV/LVA ordering and deferred using SEE until just before I make a capture and then recurse. I have had it on my to-do list to go back and revisit that. The problem is, at ordering time, I don't have the SEE score, which changed the way the code would work... I removed it when I made that change..

But it is redundunt with lazy eval , isn't it ? We don't need the exact SEE score to apply delta pruning.
A move's materialistic upperbound is the piece it just captured (= C ) and its lower bound
is if it loses its piece P (= C - P). So if we just take its upperbound for delta pruning :

Code: Select all

if(score_before_move + C + positional_margin < alpha)  prune

And the lazy eval part on the next ply

Code: Select all

if(score_after_move - positional_margin > beta) prune; //prune because stand pat score > beta

Now the above two are exactly the same since (alpha = -beta, and scores also negate each other before and after move).
That is why it never made sense me to do both. I prefer the lazy eval method because I can
include big "positional" scores like a trapped piece in the score calculation. You can do the same
before making the move but it is not as convinient.

Lazy eval also have additional check that basically saves eval time only without pruning.

Code: Select all

if(score_after_move + positional_margin < alpha) use lazy_score //we dont prune here but stand pat will
                                                                  do it on the next ply if next move is not good enough;

No. Lazy eval just avoids doing evaluation work. And it is excluded in some kinds of positions (remove last opponent piece, you might have unstoppable pawn.)

More importantly, avoiding searching moves that have no hope of getting score back to alpha saves time. I don't need to make the move, recursively call quiesce(), and waste that time. Once you get to the next ply, LE might get you out quickly because of stand pat. But to get there, you do a Make(), Quiesce(), Evaluate() and Unmake(). With the futility pruning (I hate the term delta pruning, I simply chose the variable name "delta" since that is the minimum score needed to get back to alpha (delta = alpha - material). It was then named "delta pruning" by someone that looked at Crafty. It's a poor name. It is just another form of futility pruning...

[Daniel Shawul]

No. Lazy eval just avoids doing evaluation work. And it is excluded in some kinds of positions (remove last opponent piece, you might have unstoppable pawn.)

The point is they are fundamentally searching the same tree for a given risk. The futility pruning only takes more
risk (considering only material) for speed. But lazy eval is safer and also a lower margin can be used since it already considers passed pawns, trapped pieces unlike the futility value. But in the futility case you just use a big margin! The inverse delta pruning also boils down to lazy eval on the alpha side but is much more riskier since it doesn't consider opponent response at all.

More importantly, avoiding searching moves that have no hope of getting score back to alpha saves time. I don't need to make the move, recursively call quiesce(), and waste that time. Once you get to the next ply, LE might get you out quickly because of stand pat. But to get there, you do a Make(), Quiesce(), Evaluate() and Unmake(). With the futility pruning (I hate the term delta pruning, I simply chose the variable name "delta" since that is the minimum score needed to get back to alpha (delta = alpha - material). It was then named "delta pruning" by someone that looked at Crafty. It's a poor name. It is just another form of futility pruning...

Cost of function calls qsearch() and evaluate() is negiligble. unmake() is a lot more faster than make() atleast in my engine. I tested delta pruning in the past on top of lazy eval and got nothing in my engine.. May be you should test it now that you have only lazy eval ? Inverse delta pruning should not bring anything either since it is again redundent.

You said you can't use delta pruning now because you don't have SEE score ? But you can use the upperbound value for that ...

[bob]

No. Lazy eval just avoids doing evaluation work. And it is excluded in some kinds of positions (remove last opponent piece, you might have unstoppable pawn.)

The point is they are fundamentally searching the same tree for a given risk. The futility pruning only takes more
risk (considering only material) for speed. But lazy eval is safer and also a lower margin can be used since it already considers passed pawns, trapped pieces unlike the futility value. But in the futility case you just use a big margin! The inverse delta pruning also boils down to lazy eval on the alpha side but is much more riskier since it doesn't consider opponent response at all.

Depends on how/when you "lazy exit". The benefit with the futility approach is saving a lot of work. It is a simple speedup, not a great technical advance. Sort of like the idea of not using SEE to cull losing captures until you actually get ready to try them... As opposed to when you sort them.

More importantly, avoiding searching moves that have no hope of getting score back to alpha saves time. I don't need to make the move, recursively call quiesce(), and waste that time. Once you get to the next ply, LE might get you out quickly because of stand pat. But to get there, you do a Make(), Quiesce(), Evaluate() and Unmake(). With the futility pruning (I hate the term delta pruning, I simply chose the variable name "delta" since that is the minimum score needed to get back to alpha (delta = alpha - material). It was then named "delta pruning" by someone that looked at Crafty. It's a poor name. It is just another form of futility pruning...

Cost of function calls qsearch() and evaluate() is negiligble. unmake() is a lot more faster than make() atleast in my engine. I tested delta pruning in the past on top of lazy eval and got nothing in my engine.. May be you should test it now that you have only lazy eval ? Inverse delta pruning should not bring anything either since it is again redundent.

Q-search is not negligible. It does work, from calling Evaluate() to attempting to generate capture moves. Etc. Even the procedure call overhead for setting up the call instruction is not free...

As far as "delta pruning" + lazy eval, I have always done both, until the MVV/LVA change last year. And both helped. Significantly.

You said you can't use delta pruning now because you don't have SEE score ? But you can use the upperbound value for that ...

[Daniel Shawul]

Q-search is not negligible. It does work, from calling Evaluate() to attempting to generate capture moves. Etc. Even the procedure call overhead for setting up the call instruction is not free...

One can even eliminate the evaluate() call all in all if we just take material only as in futility pruning. Also move generation is not called before evaluate (we test for standing pat first through eval() call).
When I converted to iterative search from recursive search, I didn't gain any speed gain despite my "misinformed" expectations.
Maybe setting up the stack in recursive searchers can be significant but i doubt it.

As far as "delta pruning" + lazy eval, I have always done both, until the MVV/LVA change last year. And both helped. Significantly.

It may be because one is used weekly (not aggressive enough). So what I propose is to use an unsophisticated lazy eval , one with material only done outside eval, with the same margin as futility. Hence both search exactly the same tree except that futility do it early to save some time. How significant will that be ? If two prunings that do not complement each other (fail high reductions & null move) are used together and give a better result, it implies one of them is not done aggressively enough.

[marcelk]

I will try it. Conceptually, it should work if saving one eval and makemove is more work than running a given number of SEE. My concern is that the accuracy of SEE is critical here, more than in the regular delta pruning.

Thanks. I have the same concern here. My SEE knows about pins against the king, but I cannot judge if that makes it more vulnerable to errors if you prune on both sides. I will try it as well of course and post results, but I cannot do so before the end of this month.

Perhaps "double-edged delta pruning" is a better name than "inverse delta pruning". (I don't share Bob's objection that naming the technique after a variable name makes a bad choice for a name. After all, "alpha-beta" got away with that pretty well :-) ...)