Questions on Razoring and Code Structure for Pruning

[Desperado]

You do not need to know that! The reason why a move is strong and why you decide to search the subtree might be different.
If you exclude a killer move because you expect a killer to be strong for any reason it might be because of a double attack or anything else.
Of course killer move is only one ad hoc example.

The problem is that it doesn't help to know that the move is winning due to what it does at larger depth (where it could very well have become killer, because the sibbling, searched earlier, suffered less LMR). At d=1 threats that gain Queens will not be able to fail high unless they actually capture that Queen. Any gain that comes later, even if it was verified by a deeper search, will remain invisible. It would only make sense to search a futile killer when you extend it. The maximum it could raise eval by itself (as opposed to what followed from the threat it made) should have been taken care of by the margin for the in-loop FP. An extra large margin on the killers seems useless. The same would hold for any other move that for some reason you know to be very good. At d=1 they just don't stand a chance.

Ok, i see the discussion is now mainly for d=1.

Well, it was said that Stockfish only does this at d=1.

The stand pat situation is a good point ( for discussion ), but you can print easily situations where our imagination fails and you find moves where some evaluation criterias sum together and will exactly do what you described (avoiding stand pat). Just an example...

Code: Select all

[static_eval: -70 static_eval-alpha: -88 score_from_qs: 31 : alpha:18]
move: e1g1

CTM : WHITE
woo : 1
wooo: 1
boo : 1
booo: 1
R50 : 0
EPT : --
br -- bb bq bk bb -- br
bp bp bp -- bp bp bp bp
-- -- -- -- -- bn -- --
-- -- -- -- -- -- -- --
-- -- -- bn -- -- -- --
-- -- wn wb -- wn -- --
wp wp wp wp -- wp wp wp
wr -- wb wq wk -- -- wr

I don't get this. The move is castling, is that searched in QS? Or is this from a d=1 node, where castling was searched with a QS reply? There doesn't seem to be any good capture for black after white castles in the given position, so the score must have been obtained from stand-pat after the castling. It is 101 larger than the eval before the castling. So castling increases eval by 101. Is that centi-Pawn? That seems a gross over-estimate for the value of castling. It would for instance sacrifice a Pawn to push it over the horizon. If castling gets you more than gaining a Pawn, then castling should be searched in QS...

Especially in advanced engines, positional criterias sum easiliy up to a value of a pawn and more.
Looks like getting the king out of the center and some shield bonuses are enough in that case.

You argue from the assumption that the in-loop futility pruning is done on the basis of the full evaluation after the move. Because that is where these positional criteria are summed up. But this is not how it is usually done: one just adds a cheap estimate (such as the victim value, and possibly the change in PST score) of what the move gains to the full evaluation before the move. Subtle effects due to relation with other pieces, such as mobility or pawn-structure changes are supposed to be taken care of by the margin.

If most moves gain or lose you more than a Pawn, in-loop FP only makes sense if you use a margin larger than a Pawn, because you don't want to habitually prune a lot of stuff that scores above alpha. If castling is the only non-capture that earns such an exceptionally high score, it is silly to test all moves individually for raising the score that much (in fact testing whether they are castlings). If you see before the loop that alpha - eval is large enough to prune all non-captures except castlings, you should just try the castlings. It wouldn't be that hard to have a dedicated move geerator that only generates castlings. In fact it is likely that this is already part of your regular move generator.

I think you would agree that for d > 1 all this stuff becomes more complicated, but the frontier nodes (whatever frontier means today ) include quiets.(Guess:) In most positions quiet moves turn out to be better than captures, otherwise we would never examine quiets at all.

Yes, at d > 1 the situation is quite different. But you would use large margins in the first place, for that reason. And the 'dropping into QS' stuff seems to be done only at d=1 (in Stockfish). At d > 1 it would even make less sense; by reducing the depth you get yourself back in the d <= 1 situation. Reducing depth because of futility is totally pointless in general: if you don't believe there is a reasonable chance to pump up the score to alpha in a number of moves, allowing fewer moves for it will certainly not get you there. You should just fail low in that case.

The castling move is from d=1. The score returned from QS. The static score is from d=1.
That there are only bad captures for black is just one more reason to check the position.

I did not want to focus on a castle move or any other special group of moves.
I just want to point out that quiet moves are able avoid stand pat when entering QS, even when there is mentionable delta.
The list can be very long and situations can be very different for moves. That works...and there are some other reasons.

One is,a QS node might able to return a hash value instead of a stand pat score. (Perhaps that happend in my example, i didn't check it)
As you can see, the real word situation brings a lot more situations than we can think of and the interaction of the components are very complex.

My pawn values are: mg 80 eg 100

Code: Select all

if(prunable && is_quiet && !pv_node) {
       if(depth <= 8 && moves_searched > lmp[progress > 0][depth]) continue;
       
       // INNER LOOP EXAMPLE
       if(depth <= 3 && dynamic_eval + 40 + depth * 40 <= alpha) continue;
}

Code: Select all

// OUTSIDE THE LOOP
if(!pv_node && !evasion && !eMove && !IsMate(beta)) {
    static const int RM[4] = {0, 120, 160, 200};

    if(depth <= 3 && dynamic_eval + RM[depth] <= alpha) {
        score = qs(pt, pos, alpha, beta, 0, ply);

        if(score <= alpha)
            return score;
    }

I my engine i only use the static_eval as fallback, but use hash values (dynamic_eval) if available.
You won't be able to think about all interactions as i already said and you don't need to.

The simple point is:

1. both types of futility checks have nothing in common unless all branches are useless, then the position is also useless
2. using different constraints in the loop than outside is ok because i test for something different (the branch not the position).
3. Moves that are in the category "not prunable" get a chance to be searched even after capture moves and even when they drop into QS directly.

All i do is talking about (my) ideas and my conclusion is still, that we are talking of two pruning techniques which complement.
You are right, that both techniques at the end can give the same information, that the position is futile.
That does not mean looking at different groups of moves (including quiets) is useless. I think i was able to provide some good reasons.

To be honest, i implemented the inner loop pruning before one or two weeks and was faced with the same questions.
I checked some real world situations an understood that there are a lot of situations i never thought of before and there are more than i am able to examine. But that is enough, at least for me, to abstract that there can be futile moves beside the not prunable moves.
So, i found an implementation for my engine that also gained some elo (2 or 3 elo i think).

[Desperado]

Another thing i would like to mention...

...
You argue from the assumption that the in-loop futility pruning is done on the basis of the full evaluation after the move. Because that is where these positional criteria are summed up....

That is what usually happens when entering the QS, a static eval is performed.

We should not mix up the two groups in the loop for (d=1):
1. the "not prunable": these are the moves that are exluded from the futility check like in the example
2. quiet moves that are pruned because of a futility check.

So, if all moves will be in the category prunable we come closer to your argumentation.

Prunable can depend on different data like isKiller, history stats, checking move, movecount and so on.
My first implementation was like

Code: Select all

dynamic_eval - movecount * 4 <= alpha - margin 

The idea was, the more moves i tried the less likely another move will do it (basically a combination of lmp and futility pruning).

[hgm]

The castling move is from d=1. The score returned from QS. The static score is from d=1.
That there are only bad captures for black is just one more reason to check the position.

It cannot be a reason to check anything, as you did not know it before checking. A normal situation would be that stand-pat would be already enough to fail high, and having good captures would make that much worse.

I did not want to focus on a castle move or any other special group of moves.
I just want to point out that quiet moves are able avoid stand pat when entering QS, even when there is mentionable delta.

That just means your in-loop margin is too small. And then it isn't really futility pruning. If your approximate eval that you use do decide whether to search the move differs so much from move to move that some non-captures qualify, and others don't, the difference between that approximate eval and the full eval should be able to swing that decision so often that it becomes almost random. Unless you have a very simple eval that is almost entirely PST.

One is,a QS node might able to return a hash value instead of a stand pat score. (Perhaps that happend in my example, i didn't check it)

Yes it could. But it is unlikely, and the same thing could be said from any move that you prune by futility. On the face of things it looks like a poor move that doesn't do anything useful. But it could have been searched much deeper in another branch, and that could have shown that it in fact is a brilliant attack that gains you tons of material. If that was a good-enough reason, nothing would ever be futile.

The point is that the approximate gain from the move itself tells you absolutely nothing about its chances to be the key move to a deeper tactical gain, nor about the probability that this tactical gain has already been discovered by a deeper search, and will now be handed to you through the TT. That makes it rather pointless to judge the individual moves; the ones that you prune are just as likely to fail high by such coincidences that the ones you search.

The simple point is:

1. both types of futility checks have nothing in common unless all branches are useless, then the position is also useless
2. using different constraints in the loop than outside is ok because i test for something different (the branch not the position).
3. Moves that are in the category "not prunable" get a chance to be searched even after capture moves and even when they drop into QS directly.

All i do is talking about (my) ideas and my conclusion is still, that we are talking of two pruning techniques which complement.
You are right, that both techniques at the end can give the same information, that the position is futile.
That does not mean looking at different groups of moves (including quiets) is useless. I think i was able to provide some good reasons.

To be honest, i implemented the inner loop pruning before one or two weeks and was faced with the same questions.
I checked some real world situations an understood that there are a lot of situations i never thought of before and there are more than i am able to examine. But that is enough, at least for me, to abstract that there can be futile moves beside the not prunable moves.
So, i found an implementation for my engine that also gained some elo (2 or 3 elo i think).

You are applying the pre-loop test at d <= 3, and at larger depth it is indeed different. But it does seem a rather strange thing to do: say the search asks for d=3, and you see you are 7 Pawns below alpha. That makes you decide to do QS instead. In this QS the only non-futile move will be capture of a Queen. Now suppose that you can capture a Queen. That brings you 2-3 Pawns above alpha. Apparently the position was not bad at all, it just had a poor eval because you were in the middle of some tactics, which in the end makes you grab a Queen. So what justification do you have now for reducing that branch by 2 ply? You found a good move, and have been exaggerating its depth.

This 'not prunable' is a fishy concept at d <= 1. Indeed checks are not futile, by virtue of the search giving an extension for the evasion. If there was no extension, and the opponent could happily stand pat when in check, checks that do not get you above alpha fail low just like any other move, whether you prune them or not. Even if some move sorting technique promises the move is good, it will not help you when you don't have enough depth to discover it. At d > 1 you might have such depth. So it doesn't seem very sensible to apply the same criteria to d=3 and d=1 for what is prunable and what is not.

[Desperado]

The castling move is from d=1. The score returned from QS. The static score is from d=1.
That there are only bad captures for black is just one more reason to check the position.

It cannot be a reason to check anything, as you did not know it before checking. A normal situation would be that stand-pat would be already enough to fail high, and having good captures would make that much worse.

I did not want to focus on a castle move or any other special group of moves.
I just want to point out that quiet moves are able avoid stand pat when entering QS, even when there is mentionable delta.

That just means your in-loop margin is too small. And then it isn't really futility pruning. If your approximate eval that you use do decide whether to search the move differs so much from move to move that some non-captures qualify, and others don't, the difference between that approximate eval and the full eval should be able to swing that decision so often that it becomes almost random. Unless you have a very simple eval that is almost entirely PST.

One is,a QS node might able to return a hash value instead of a stand pat score. (Perhaps that happend in my example, i didn't check it)

Yes it could. But it is unlikely, and the same thing could be said from any move that you prune by futility. On the face of things it looks like a poor move that doesn't do anything useful. But it could have been searched much deeper in another branch, and that could have shown that it in fact is a brilliant attack that gains you tons of material. If that was a good-enough reason, nothing would ever be futile.

The point is that the approximate gain from the move itself tells you absolutely nothing about its chances to be the key move to a deeper tactical gain, nor about the probability that this tactical gain has already been discovered by a deeper search, and will now be handed to you through the TT. That makes it rather pointless to judge the individual moves; the ones that you prune are just as likely to fail high by such coincidences that the ones you search.

The simple point is:

1. both types of futility checks have nothing in common unless all branches are useless, then the position is also useless
2. using different constraints in the loop than outside is ok because i test for something different (the branch not the position).
3. Moves that are in the category "not prunable" get a chance to be searched even after capture moves and even when they drop into QS directly.

All i do is talking about (my) ideas and my conclusion is still, that we are talking of two pruning techniques which complement.
You are right, that both techniques at the end can give the same information, that the position is futile.
That does not mean looking at different groups of moves (including quiets) is useless. I think i was able to provide some good reasons.

To be honest, i implemented the inner loop pruning before one or two weeks and was faced with the same questions.
I checked some real world situations an understood that there are a lot of situations i never thought of before and there are more than i am able to examine. But that is enough, at least for me, to abstract that there can be futile moves beside the not prunable moves.
So, i found an implementation for my engine that also gained some elo (2 or 3 elo i think).

You are applying the pre-loop test at d <= 3, and at larger depth it is indeed different. But it does seem a rather strange thing to do: say the search asks for d=3, and you see you are 7 Pawns below alpha. That makes you decide to do QS instead. In this QS the only non-futile move will be capture of a Queen. Now suppose that you can capture a Queen. That brings you 2-3 Pawns above alpha. Apparently the position was not bad at all, it just had a poor eval because you were in the middle of some tactics, which in the end makes you grab a Queen. So what justification do you have now for reducing that branch by 2 ply? You found a good move, and have been exaggerating its depth.

This 'not prunable' is a fishy concept at d <= 1. Indeed checks are not futile, by virtue of the search giving an extension for the evasion. If there was no extension, and the opponent could happily stand pat when in check, checks that do not get you above alpha fail low just like any other move, whether you prune them or not. Even if some move sorting technique promises the move is good, it will not help you when you don't have enough depth to discover it. At d > 1 you might have such depth. So it doesn't seem very sensible to apply the same criteria to d=3 and d=1 for what is prunable and what is not.

1. i do not check anything! if you look at the code snippet more closely you can see that lmp is right in front. That means the list
for quiet moves that are splitted into a pruning group and moves that are examined is short. That's one more interaction of different components...

2. To choose a candidate to search (exclude from pruning) does not require to know about the dynamics in the subtree. Like checking moves...

3. No, the value is not too small and futility pruning is not about some big margins. It is about to decide if the subtree or the position needs further investigation. if you have a good reason to assume that the move won't be above alpha, you can prune it. You simply define it as futile/useless to examine.. If you do not rely on available information (history information, move ordering) then you examine the move.

4. There is no fishy concept at d=1. You argue that a check is not futile because of a virtue extension. I say it is another reason,the delay of a threat, and now... We do not need to discuss something like this because i explained already that it is not important which dynamics are included in the subtree. It varies for checks and for other moves too. There is a reason for every killer move to be a killer, but you sort it to the front, not because of the reason but because it is a refutation for the current ab-window. (i am sure you won't discuss that the same position an move might be handled in a different way when the windows would be different. Does that mean that the killer heuristic is fishy ? Does that really mean that the move is good? Oviously not! We handle a concret situation in a tree with the information that is available. Most of the time in a statistcal context).

5. How many plies/depth do you need to check a strong quiet move. Well, if you have a hash hit on the next ply you need 1 ply.(implicit more depth)
if you have a move that sums up values for mobility,king safety or tactics(peace,pawn threats) 1 ply. If you have "Zwischenzüge" (e.g. checks, delays of threats,simple threats like in the 1st example) the QS will start to produce capture sequences as usual.
You have a lot of hash hits when entering the QS. Having a position in QS (depth=0) without standpat and a quiet move at d=1 does not change the behaviour of QS. It computes sequences like it does, if there was a capture at d=1. I do not need a different depth behaviour because of a different move type in front of the QS.

So, to be futile is an abstract concept an has not much to do with captures and big margins (these are implementation tricks based on assumtions).
You can modify/extend these implementation ideas. You can even define a futile position if a rook and a queen is hanging and you are only 100 points above alpha (static criterias). I would not do that, i only want to point out that the question is about, do we have a good reason to continue searching or will our self defined heuristic tell us to stop because we end with a score below alpha.

The assumtion (outside the loop) that only good captures can rescue a position is fine (but that is not the complete story).There are still other strong moves, non captures, that might be strong enough. In my implemention, my assumtion is, that based on move ordering some quiet moves might be candidates to gain something useful. So, before lmp kicks in, i exclude some moves and then, if move characteristics do not match, it will be pruned if the conditions are met.

Nobody can have the complete picture about how components like (lmp,futility formula,exluded moves,move ordering,see captures and all the things mentioned in this thread already) work together.

1. there are reasons why quiets can drop into q-search and there won't be a stand-pat although we had a negative delta to alpha at d=1.
That is no theoretical idea, that is reality. (hash hits, sum of important eval features are two)
2. there is a common idea between outside the loop and inside the loop futility check
strong moves can raise above alpha and should be checked. (but the definition of strong is different)
3. checking inside and outside the loop is not congruent (checking a branch,checking a position)
4. the reason why a move is excluded from futility pruning must not be the same as the reason why it is strong (e.g. killers)

I can only talk of my observations to release your imagination. Finally you can check all of that in your own engines.
There might be things you do not agree, but that does not mean that these things are wrong.