A question about futility prunning

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
User avatar
xr_a_y
Posts: 1104
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

A question about futility prunning

Post by xr_a_y » Thu Jul 26, 2018 1:05 pm

In stockfish, there is a

Code: Select all

if (futilityValue < beta)
inside the move loop.

I have some difficulty to understand why futility is verified against beta and not alpha. Wiki says
in its pure form implemented at the frontier nodes (depth == 1) with one ply left to the horizon. It discards the moves that have no potential of raising alpha, which in turn requires some estimate of a potential value of a move.

jorose
Posts: 277
Joined: Thu Jan 22, 2015 2:21 pm
Location: Zurich, Switzerland
Full name: Jonathan Rosenthal

Re: A question about futility prunning

Post by jorose » Thu Jul 26, 2018 2:00 pm

Could you give a link to the source you are referring to? I can't find it in the current source: https://github.com/official-stockfish/S ... search.cpp. I'm not an expert on this topic, but maybe previously SF restricted futility pruning to Null Window searches? In that case futilityValue <= alpha would be the same as futilityValue < beta. Otherwise it doesn't make sense for me either.
-Jonathan

User avatar
xr_a_y
Posts: 1104
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: A question about futility prunning

Post by xr_a_y » Thu Jul 26, 2018 2:11 pm

jorose wrote:
Thu Jul 26, 2018 2:00 pm
Could you give a link to the source you are referring to? I can't find it in the current source: https://github.com/official-stockfish/S ... search.cpp. I'm not an expert on this topic, but maybe previously SF restricted futility pruning to Null Window searches? In that case futilityValue <= alpha would be the same as futilityValue < beta. Otherwise it doesn't make sense for me either.
You are right, and is was in an old source.

https://github.com/kobolabs/stockfish/b ... h.cpp#L921

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

Re: A question about futility prunning

Post by Sven » Thu Jul 26, 2018 2:16 pm

xr_a_y wrote:
Thu Jul 26, 2018 1:05 pm
In stockfish, there is a

Code: Select all

if (futilityValue < beta)
inside the move loop.

I have some difficulty to understand why futility is verified against beta and not alpha. Wiki says
in its pure form implemented at the frontier nodes (depth == 1) with one ply left to the horizon. It discards the moves that have no potential of raising alpha, which in turn requires some estimate of a potential value of a move.
SF9, SF8, SF7 and most probably many older SF versions compare "if (futilityValue <= alpha)" in qsearch(), and have a more complex expression (but essentially with the same semantics) in full-width search. So I'm not sure where you found this. Only in non-PV nodes the condition alpha == beta-1 holds but FP is not necessarily restricted to non-PV nodes.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

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

Re: A question about futility prunning

Post by Sven » Thu Jul 26, 2018 2:23 pm

xr_a_y wrote:
Thu Jul 26, 2018 2:11 pm
jorose wrote:
Thu Jul 26, 2018 2:00 pm
Could you give a link to the source you are referring to? I can't find it in the current source: https://github.com/official-stockfish/S ... search.cpp. I'm not an expert on this topic, but maybe previously SF restricted futility pruning to Null Window searches? In that case futilityValue <= alpha would be the same as futilityValue < beta. Otherwise it doesn't make sense for me either.
You are right, and is was in an old source.

https://github.com/kobolabs/stockfish/b ... h.cpp#L921
Not just an "old source" but something from a non-official place, with just one "initial commit" from 2013 and nothing else, so I wonder how G**gle took you there :D
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

User avatar
xr_a_y
Posts: 1104
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: A question about futility prunning

Post by xr_a_y » Thu Jul 26, 2018 2:25 pm

Sven wrote:
Thu Jul 26, 2018 2:23 pm
Not just an "old source" but something from a non-official place, with just one "initial commit" from 2013 and nothing else, so I wonder how G**gle took you there :D
Yeah me too, and how I didn't realize sooner I was reading a strange source ...

Post Reply