Problem understanding futility pruning

[nionita]

In the following I will refer to the terms as defined in CPW (http://chessprogramming.wikispaces.com/Futility+Pruning).

I understand the logic of futility pruning (d==1), as most quiet moves will not improve alpha anymore if the position itself is pretty low scored (by a margin under current alpha).

But then exactly the same should be valid also for d==2 (which in CPW is described as extended futilty pruning)! If I can't improve alpha by my own move, for sure it will not be improved by a further move of the opponent! So why take a higher margin for d==2?

In my understanding the pruning rule should be: given some conditions (e.g. not in check), if d==1 or d==2, and if eval is under alpha by some margin, then prune all quiet moves (also not giving check and maybe some other conditions like passed pushes, I don't know).

Where is my mistake?

NB: In Barbarossa I got last time about 35 ELO implementing something like this but with variable futility margin and also using a 4 times higher margin for d==3 (something corresponding very roughly to deep futility pruning).

[kbhearn]

a d=2 move could be an irresistable threat or inbetween move as a quiet move such that search looks like :

d = 2 : apparently 'futile' move that creates a threat (or just leaves a threat for next move)
d = 1 : have to move something
d = 0 : capture in quiescence improving alpha

vs

d = 1 : insufficient move
d = 0 : stand pat and ignore any threats d = 1 move created.

[bob]

In the following I will refer to the terms as defined in CPW (http://chessprogramming.wikispaces.com/Futility+Pruning).

I understand the logic of futility pruning (d==1), as most quiet moves will not improve alpha anymore if the position itself is pretty low scored (by a margin under current alpha).

But then exactly the same should be valid also for d==2 (which in CPW is described as extended futilty pruning)! If I can't improve alpha by my own move, for sure it will not be improved by a further move of the opponent! So why take a higher margin for d==2?

In my understanding the pruning rule should be: given some conditions (e.g. not in check), if d==1 or d==2, and if eval is under alpha by some margin, then prune all quiet moves (also not giving check and maybe some other conditions like passed pushes, I don't know).

Where is my mistake?

NB: In Barbarossa I got last time about 35 ELO implementing something like this but with variable futility margin and also using a 4 times higher margin for d==3 (something corresponding very roughly to deep futility pruning).

Purely semantics. FP = pruning with remaining depth = 1, extended FP = pruning with remaining depth = 2. These came from Heinz's writings. Now most call futility pruning as any pruning done near the leaves where as you get farther from the tips you raise the margin required for the score to be below alpha.

I'd have to look, but I believe I currently do this now in the last 6 plies but I am not 100% certain of that...

[Ferdy]

In the following I will refer to the terms as defined in CPW (http://chessprogramming.wikispaces.com/Futility+Pruning).

I understand the logic of futility pruning (d==1), as most quiet moves will not improve alpha anymore if the position itself is pretty low scored (by a margin under current alpha).

But then exactly the same should be valid also for d==2 (which in CPW is described as extended futilty pruning)! If I can't improve alpha by my own move, for sure it will not be improved by a further move of the opponent! So why take a higher margin for d==2?

It is dangerous because your opponent is making the move (also depends on the position, but even then you will observe that the engine will be out-positioned as the game progresses). It is different when you are to move at depth 1 and choose to prune. Of course you can verify it thru testing.

[PK]

Technically speaking, move at depth 1 or depth 2 does not have to be the last move. There quiescence search afterwards, and the side that enters it with a bad score still can find a capture that reverses the situation. This is a difference between futility pruning at d1 and d2.

[Henk]

If at depth d=2 there is a pawn move that attacks a trapped queen, it will be overlooked by futility pruning for it is a quiet move. Or what about a pawn move that forks two rooks.

[Ferdy]

Also d2 has more chances than d1 that the depth gets extended, this is why margin in d2 should be higher.

[nionita]

Thank you all for the answers, now I have more points which are valid explanations or at least give a vague intuition why the margin for d==2 has to be higher.

Anyway I can now understand that even for d==1 we have to see the margin more as a probabilistic approximation, as also there a quiet move can modify the following QS (by opening a new hot point, for example when attacking a queen by a pawn). Knowing that we deal with probabilities (and means over them), it is obviously that in a d==2 search more unexpected situations can occur than in a d==1 search.

I will do a bit more tests with these ideas in mind.

[hgm]

..., as also there a quiet move can modify the following QS

Not really. The margin at d=1 is because you usually do not have the exact evaluation after each non-capture available, but just estimate it from the evaluation before the move. But the move could have a positional gain, e.g. by increasing mobility, centralization, Pawn structure or King safety.

There is no change in QS for futile moves at d=1, because the opponent will immediately stand pat, the eval being >= beta. There will never be any need to try a capture, so you don't care whether new captures are created, or existing captures disappear. Even when the non-capture at d=1 would be a material-gaining move, like a fork or a skewer, you could still not see that gain, because forks and skewers against him won't prevent the opponent to stand pat.

[Henk]

Futility pruning at depth 2 is not sound for you don't know the margin. Could be value of Queen worst case.