Razoring vs Futility pruning

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
zd3nik
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Razoring vs Futility pruning

Post by zd3nik » Sun Aug 16, 2015 6:03 pm

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.

jdart
Posts: 3835
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Razoring vs Futility pruning

Post by jdart » Sun Aug 16, 2015 6:41 pm

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

zd3nik
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Re: Razoring vs Futility pruning

Post by zd3nik » Sun Aug 16, 2015 7:35 pm

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.

zd3nik
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Re: Razoring vs Futility pruning

Post by zd3nik » Sun Aug 16, 2015 7:39 pm

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.

Henk
Posts: 5832
Joined: Mon May 27, 2013 8:31 am

Re: Razoring vs Futility pruning

Post by Henk » Sun Aug 16, 2015 10:01 pm

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.

mar
Posts: 2010
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Razoring vs Futility pruning

Post by mar » Sun Aug 16, 2015 10:15 pm

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

jdart
Posts: 3835
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Razoring vs Futility pruning

Post by jdart » Sun Aug 16, 2015 11:26 pm

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

bob
Posts: 20640
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Razoring vs Futility pruning

Post by bob » Mon Aug 17, 2015 1:29 am

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.

Post Reply