Problem understanding futility pruning

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
nionita
Posts: 160
Joined: Fri Oct 22, 2010 7:47 pm
Location: Austria

Problem understanding futility pruning

Post by nionita » Mon May 11, 2015 8:34 pm

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
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Problem understanding futility pruning

Post by kbhearn » Mon May 11, 2015 8:49 pm

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
Posts: 20372
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Problem understanding futility pruning

Post by bob » Mon May 11, 2015 9:51 pm

nionita wrote: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
Posts: 3933
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: Problem understanding futility pruning

Post by Ferdy » Tue May 12, 2015 1:46 am

nionita wrote: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).
nionita wrote: 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
Posts: 798
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: Problem understanding futility pruning

Post by PK » Tue May 12, 2015 6:12 am

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
Posts: 5610
Joined: Mon May 27, 2013 8:31 am

Re: Problem understanding futility pruning

Post by Henk » Tue May 12, 2015 7:16 am

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
Posts: 3933
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: Problem understanding futility pruning

Post by Ferdy » Tue May 12, 2015 10:23 am

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

nionita
Posts: 160
Joined: Fri Oct 22, 2010 7:47 pm
Location: Austria

Re: Problem understanding futility pruning

Post by nionita » Tue May 12, 2015 5:19 pm

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.

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

Re: Problem understanding futility pruning

Post by hgm » Tue May 12, 2015 6:47 pm

nionita wrote:..., 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
Posts: 5610
Joined: Mon May 27, 2013 8:31 am

Re: Problem understanding futility pruning

Post by Henk » Tue May 12, 2015 10:09 pm

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

Post Reply