Confused by 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.
Michel
Posts: 1964
Joined: Sun Sep 28, 2008 11:50 pm

Confused by futility pruning

Post by Michel » Wed Mar 03, 2010 12:22 pm

For futility pruning should one use

(1) the material evaluation;
(2) the result of Eval;
(3) the result of quiescence search?

I would guess (3) but the examples I looked at use (1).

I realize quiescence search would be too expensive but It seems to me that the material evaluation would be highly unstable as pieces might be hanging.

Comments?

EDITED

yoshiharu
Posts: 56
Joined: Sat Nov 11, 2006 10:14 pm

Re: Confused by futility pruning

Post by yoshiharu » Wed Mar 03, 2010 12:35 pm

Michel wrote:
It seems to me that the material evaluation would be highly unstable as pieces might be hanging.
Well, futility is about skipping moves that are not good enough to improve a poor position, so if a piece is hanging, a fortiori those insufficient captures are futile.
What might happen is that the capture you are about to skip, captures the piece that is going to take the hanging one, but I think that this risk is offset by what you earn in terms of more plies searched.

BTW, I use (2) - i.e. full eval.

Cheers, Mauro

Michel
Posts: 1964
Joined: Sun Sep 28, 2008 11:50 pm

Re: Confused by futility pruning

Post by Michel » Wed Mar 03, 2010 12:38 pm

I guess I misunderstood futility pruning.

Thx

metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Re: Confused by futility pruning

Post by metax » Wed Mar 03, 2010 2:27 pm

I would never prune captures in normal search (in qsearch I prune some of course), no matter how bad they appear to be, but maybe I am too conservative about this...

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

Re: Confused by futility pruning

Post by hgm » Wed Mar 03, 2010 2:51 pm

If you are more than a Rook below alpha, and there is only one more ply to go, capturing a Knight is completely pointless. The opponent will fail high even without doing anything. (i.e., he will comfortably stand pat.) Capturing anything less than a Queen is doomed.

Sven
Posts: 3634
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Confused by futility pruning

Post by Sven » Wed Mar 03, 2010 5:11 pm

hgm wrote:If you are more than a Rook below alpha, and there is only one more ply to go, capturing a Knight is completely pointless. The opponent will fail high even without doing anything. (i.e., he will comfortably stand pat.) Capturing anything less than a Queen is doomed.
And futility pruning is not about pruning captures only. In the mentioned case, even not capturing anything is pointless when being more than a certain value below alpha - provided the move does not give check.

It should be noted that the given example with Rook/Knight is based on the assumption that the positional evaluation of the current position and the position after capturing the knight will not differ by more than the difference of material values of a Rook and a Knight, possibly also taking into account any further differences caused by material imbalance. Usually there is a futility margin value that estimates such a threshold.

Sven

metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Re: Confused by futility pruning

Post by metax » Wed Mar 03, 2010 5:17 pm

hgm wrote:If you are more than a Rook below alpha, and there is only one more ply to go, capturing a Knight is completely pointless. The opponent will fail high even without doing anything. (i.e., he will comfortably stand pat.) Capturing anything less than a Queen is doomed.
At depth 1 you are right (even if stand-pat in quiescence will prune these moves anyway, so you are just saving make(), unmake() and an evaluation), but if you do more aggressive futility pruning at higher depths pruning captures can be risky. Captures are tactical moves and should therefore be searched, no matter how bad they appear to be.

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

Re: Confused by futility pruning

Post by hgm » Wed Mar 03, 2010 5:26 pm

Well, not really. At d=3, when you are at alpha-900, and the Queens are already traded, so that the highest thing on the board to capture is a Rook, capturing a Knight would not really "cut wood". You would still be down more than the highest piece you can capture on the next move, after which he will stand pat. Unless you can checkmate him, of course. But that depends more on King safety than on making captures. So it is not more risky to prune non-captures than it is to prune captures in this situation. Because the captures are nor forcing at all. He can completely ignore them, and devote all his attention to preventing the mate, so much as he is ahead already.

Sven
Posts: 3634
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Confused by futility pruning

Post by Sven » Wed Mar 03, 2010 5:41 pm

metax wrote:
hgm wrote:If you are more than a Rook below alpha, and there is only one more ply to go, capturing a Knight is completely pointless. The opponent will fail high even without doing anything. (i.e., he will comfortably stand pat.) Capturing anything less than a Queen is doomed.
At depth 1 you are right (even if stand-pat in quiescence will prune these moves anyway, so you are just saving make(), unmake() and an evaluation), but if you do more aggressive futility pruning at higher depths pruning captures can be risky. Captures are tactical moves and should therefore be searched, no matter how bad they appear to be.
At higher depths the futility margin is usually much higher than at depth 1. Furthermore, I think you miss one important point: most moves that can be pruned as being futile are non-captures.

Sven

metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Re: Confused by futility pruning

Post by metax » Wed Mar 03, 2010 6:37 pm

If your futility margin is really much higher (you wrote m=900 at depth 3), then you are write. Many programs use much lower futility margins, pruning until depth 5-7 (I think Edsel Apostol once wrote that he pruned up to depth 9 in Twisted Logic, even if that is an extreme case!). For them it is really risky to prune captures as the opponent can often not ignore them.

Post Reply