It seems to me that razoring and futility pruning are mirror images of the same thing, with razoring being just a little less error prone and less aggressive. But since both approaches exist and are often used together there must be some key difference between them that I'm overlooking.
Here's my understanding:
* Razoring: return <= alpha at shallow depths if static eval far below alpha and qsearch doesn't find any tactical shots to regain any of the deficit.
* Futility pruning: return >= beta at shallow depths if static eval is far above beta. Null move observation says there will likely be a move that improves our score (or at least keeps it the same) so there's no need to do any searching, just return >= beta immediately.
My assumptions (perhaps this is where I am missing something):
* If you don't do razoring, futility pruning would prune most of the same lines anyway (a ply sooner and without any validation so it will prune slightly more but is also more error prone).
* If you don't do futility pruning, razoring would prune most of the same lines anyway (a ply later and with validation, so slightly less aggressive but less error prone).
Is there a reason to use futility pruning AND razoring? And if not which of the two is superior? I tend to lean toward razoring. I'm in the midst of testing to answer my own questions. But if anyone out there already understands the problem I would appreciate your feedback.
Razoring vs Futility pruning
Moderators: hgm, Rebel, chrisw
-
- Posts: 193
- Joined: Wed Mar 11, 2015 3:34 am
- Location: United States
-
- Posts: 4368
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: Razoring vs Futility pruning
There is some overlap but they are not the same, and can be (usually are) used together.
Futility pruning is selective, because not all moves are prunable (captures for example typically aren't).
Razoring is less selective: for me at least, any node not in the PV and not in check and with pieces on the board can be razored.
--Jon
Futility pruning is selective, because not all moves are prunable (captures for example typically aren't).
Razoring is less selective: for me at least, any node not in the PV and not in check and with pieces on the board can be razored.
--Jon
-
- Posts: 193
- Joined: Wed Mar 11, 2015 3:34 am
- Location: United States
Re: Razoring vs Futility pruning
I guess the confirmation that there is overlap between futility/razor pruning is the first thing I was looking for. Thanks.jdart wrote:There is some overlap but they are not the same, and can be (usually are) used together.
Futility pruning is selective, because not all moves are prunable (captures for example typically aren't).
Razoring is less selective: for me at least, any node not in the PV and not in check and with pieces on the board can be razored.
--Jon
But I'm still unclear on the differences between the two. It's not that I don't believe you. The evidence clearly points to there being differences in the two approaches. I'm just trying to understand what the differences are exactly.
Do you know of an example where razoring would work but futility pruning wouldn't and vise versa?
I'm not sure what you mean by selectivity. In code that I've seen there isn't any kind of check for captures or promotions in futility pruning. Because you prune (return >= beta) in nodes where the side to move is already ahead. So what's the point in checking for captures/promos when that would simply put you more ahead if the cap/promo was any good.
-
- Posts: 193
- Joined: Wed Mar 11, 2015 3:34 am
- Location: United States
Re: Razoring vs Futility pruning
OOPS! I just realized I have my terminology mixed up.
What I've been calling razoring is actually futility pruning according to https://chessprogramming.wikispaces.com ... ty+Pruning
Let me spend some time on chessprogramming wiki refreshing my vocabulary and then revisit.
What I've been calling razoring is actually futility pruning according to https://chessprogramming.wikispaces.com ... ty+Pruning
Let me spend some time on chessprogramming wiki refreshing my vocabulary and then revisit.
-
- Posts: 7221
- Joined: Mon May 27, 2013 10:31 am
Re: Razoring vs Futility pruning
It may still be: you get part of PV from hash and hash is infected by razoring. So PV is also infected.jdart wrote:
Razoring is less selective: for me at least, any node not in the PV and not in check and with pieces on the board can be razored.
--Jon
-
- Posts: 2567
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: Razoring vs Futility pruning
PV from hash is dangerous if you want a reasonable PV (I switched to triangular some time ago and I'm happy so farHenk wrote:It may still be: you get part of PV from hash and hash is infected by razoring. So PV is also infected.
and I'd recommend anyone who wants a PV that makes sense to do the same => just say no to PV from hash).
The problem I see with fpruning is that if eval is bad for stm, basically all quiet moves except checks get pruned betting they won't be able to beat alpha,
so you have to trust your eval and/or margins
But who cares, right? Search will fix it at higher depths (if you can outsearch the opponent).
-
- Posts: 4368
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: Razoring vs Futility pruning
All of these forward-pruning techniques are quite speculative. They work most of the time. There will be cases where they don't work, but you are trusting that those aren't frequent enough to matter.
--Jon
--Jon
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Razoring vs Futility pruning
One just tosses the move if the current score is too bad, the other drops into q-search and uses that score instead. The latter is (a) more accurate and (b) more costly.zd3nik wrote:I guess the confirmation that there is overlap between futility/razor pruning is the first thing I was looking for. Thanks.jdart wrote:There is some overlap but they are not the same, and can be (usually are) used together.
Futility pruning is selective, because not all moves are prunable (captures for example typically aren't).
Razoring is less selective: for me at least, any node not in the PV and not in check and with pieces on the board can be razored.
--Jon
But I'm still unclear on the differences between the two. It's not that I don't believe you. The evidence clearly points to there being differences in the two approaches. I'm just trying to understand what the differences are exactly.
Do you know of an example where razoring would work but futility pruning wouldn't and vise versa?
I'm not sure what you mean by selectivity. In code that I've seen there isn't any kind of check for captures or promotions in futility pruning. Because you prune (return >= beta) in nodes where the side to move is already ahead. So what's the point in checking for captures/promos when that would simply put you more ahead if the cap/promo was any good.