Page 1 of 1

Razoring vs Futility pruning

Posted: Sun Aug 16, 2015 6:03 pm
by zd3nik
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.

Re: Razoring vs Futility pruning

Posted: Sun Aug 16, 2015 6:41 pm
by jdart
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

Re: Razoring vs Futility pruning

Posted: Sun Aug 16, 2015 7:35 pm
by zd3nik
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
I guess the confirmation that there is overlap between futility/razor pruning is the first thing I was looking for. Thanks.

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.

Re: Razoring vs Futility pruning

Posted: Sun Aug 16, 2015 7:39 pm
by zd3nik
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.

Re: Razoring vs Futility pruning

Posted: Sun Aug 16, 2015 10:01 pm
by Henk
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
It may still be: you get part of PV from hash and hash is infected by razoring. So PV is also infected.

Re: Razoring vs Futility pruning

Posted: Sun Aug 16, 2015 10:15 pm
by mar
Henk wrote:It may still be: you get part of PV from hash and hash is infected by razoring. So PV is also infected.
PV from hash is dangerous if you want a reasonable PV (I switched to triangular some time ago and I'm happy so far
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).

Re: Razoring vs Futility pruning

Posted: Sun Aug 16, 2015 11:26 pm
by jdart
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

Re: Razoring vs Futility pruning

Posted: Mon Aug 17, 2015 1:29 am
by bob
zd3nik wrote:
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
I guess the confirmation that there is overlap between futility/razor pruning is the first thing I was looking for. Thanks.

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.
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.